# SSDL: Self-Supervised Dictionary Learning

###### Abstract

The label-embedded dictionary learning (DL) algorithms generate influential
dictionaries by introducing discriminative information. However, there exists
a limitation: All the label-embedded DL methods rely on the labels due that
this way merely achieves ideal performances in supervised learning. While in
semi-supervised and unsupervised learning, it is no longer sufficient to be
effective. Inspired by the concept of self-supervised learning (e.g., setting
the pretext task to generate a universal model for the downstream task), we
propose a Self-Supervised Dictionary Learning (SSDL) framework to address this
challenge. Specifically, we first design a $p$-Laplacian Attention Hypergraph
Learning (pAHL) block as the pretext task to generate pseudo soft labels for
DL. Then, we adopt the pseudo labels to train a dictionary from a primary
label-embedded DL method. We evaluate our SSDL on two human activity
recognition datasets. The comparison results with other state-of-the-art
methods have demonstrated the efficiency of SSDL.

Index Terms—  Dictionary learning, self-supervised learning, $p$-Laplacian
Attention Hypergraph Learning, human activity recognition

##  1 Introduction

In dictionary learning, the ultimate goal is to obtain an overcomplete
dictionary to represent original samples. Similar to subspace learning, the
to-be-learned dictionary can be further utilized to solve different categories
of problems, such as image denoising [1], visual classification [2]. Many
classical methods, including D-KSVD [3], LC-KSVD [4], LEDL [5] _et al._ ,
introduce discriminative information by adding the one-hot label matrix to the
objective function. These label-embedded approaches are powerful in supervised
learning, while in semi-supervised and unsupervised learning, the deficiency
of labels leads to a big reduction in the effect.

Fortunately, the development of Self-Supervised Learning (SSL) provides us a
novel perspective to solve this challenge. The core idea of SSL is to set a
pretext task to generate a universal model for the downstream task. SSL has
been demonstrated to effectively address the problem caused by inadequate
labeled data in the training process. Combined with SSL, we propose a Self-
Supervised Dictionary Learning (SSDL) framework. Like most SSL-based methods,
the critical point of the challenge is setting up an appropriate pretext task.

Fig. 1: The comparison among Graph, Hypergraph, and the proposed $p$-Laplacian
Attention Hypergraph (pLA-Hypergraph). In graph structure, each edge contains
two vertices. In hypergraph structure, the hyperedge is able to connect multi
vertices. And in our pLA-Hypergraph, different hyperedges have different
weights, which are represented by different thicknesses. Fig. 2: The Self-
Supervised Dictionary Learning framework. There are two steps: $i)$ Employ the
pAHL block to generate pseudo label $\mathbf{F}$ for the unlabeled data. $ii)$
Embed the pseudo label into the dictionary learning model to obtain the
dictionary $\mathbf{D}$. More details please refer to section 2.

This paper proposes a $p$-Laplacian Attention Hypergraph Learning (pAHL) based
pretext task to generate a pseudo label matrix and then employ it in the
downstream task (e.g., DL methods). Hypergraph learning was first proposed by
Zhou _et al._[6] in 2007. It is capable of predicting labels according to
mining and aggregating high-order relations within data. A hypergraph is
composed of a vertex set and hyperedge set. Each hyperedge can connect any
number of vertices. Compared with the simple graph, which is only able to
reflect the pair-wise relations among vertices, hypergraph is more flexible
and can mine deeper relations of data.

But there exists an inadequate part in traditional Laplacian-based hypergraph
learning: Each hyperedge plays the equal important role in police decisions,
which may lead to lose the key information sometimes. (As an example, assume
that a person’s weight is relevant to their diet habits and genes, but
obviously, the diet habit contributes more. If we consider that these two
attributes are equally important in predicting people’s weight, the results
would be affected.) Thus, we follow [7] and introduce $p$-Laplacian
regularizer to generate attention weight for each hyperedge. Note that, when
$p=2$, the $p$-Laplacian regularizer is equal to the Laplacian one. We show
the differences among Graph, Hypergraph, and p-Laplacian Attention Hypergraph
(pLA-Hypergraph) in Figure 1. After $p$-Laplacian Attention Hypergraph
Learning, we embed the generated pseudo label matrix into a basic dictionary
learning model. Figure 2 shows the flowchart.

In summary, the main contributions focus on:

  * •

We propose a Self-Supervised Dictionary Learning (SSDL) approach. To our best
knowledge, it is the first attempt to enhance dictionary learning from the
perspective of self-supervising. Specifically, we introduce $p$-Laplacian
Attention Hypergraph Learning (pAHL) as the pretext task to generate a pseudo
label matrix for label-embedded dictionary learning.

  * •

The proposed pAHL block is a model-agnostic method that can be employed in
arbitrary standard dictionary learning to construct SSDL framework. In this
paper, we just try to embed the pAHL block into a basic dictionary learning
approach.

  * •

We utilize the learned dictionary in two human activity recognition tasks. The
experimental results demonstrate that our SSDL is powerful, and the proposed
pAHL block significantly improve the dictionary structure’s performances.

##  2 Methodology

In this section, we introduce the details of the self-supervised dictionary
learning algorithm. First, we introduce $p$-Laplacian based Attention
Hypergraph to generate pseudo labels for the unlabeled training data. Then, we
embed the pseudo label information into the standard dictionary learning
framework. Figure 2 shows the flowchart, and Algorithm 1 elaborates the
algorithm procedure.

###  2.1 Pseudo Label Generation via $p$-Laplacian Attention Hypergraph

Hypergraph Construction A suitable hypergraph structure is beneficial to mine
high-order relations among samples. Different from simple graph structure, a
hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W})$ is composed of
vertex set $\mathcal{V}$, hyperedge set $\mathcal{E}$, and weight matrix of
hyperedge $\mathbf{W}$. The $\mathbf{W}$ is a diagonal matrix, each element
denotes the weight of the corresponding hyperedge. Besides, there exist two
degree matrices in hypergraph learning, including vertex degree matrix
$\mathbf{D}_{v}$ and hyperedge degree matrix $\mathbf{D}_{e}$. We use the
incidence matrix
$\mathbf{H}\in{\mathbb{R}}^{|\mathcal{V}|\times{|\mathcal{E}|}}$ to represent
connections between hyperedges and vertices, and define the elements in the
incidence matrix as follows:

$\scriptsize\begin{split}\mathbf{H}=\left\\{\begin{array}[]{cc}{\exp\left(-dis\left(v,v_{c}\right)^{2}\right)}&{\text{
if }v\in e}\\\ {0}&{\text{ o.w. }}\end{array}\right.\end{split}$ (1)

where $e$ denotes one hyperedge in $\mathcal{E}$, $v$ denotes a vertex in
$\mathcal{V}$. $dis$ indicates the operator to compute the distance.
Following, we formulate the degree matrices as:

$\scriptsize\begin{split}\delta({e})=\sum_{{v}\in\mathcal{V}}\mathbf{H}({v},{e})\end{split}$
(2)
$\scriptsize\begin{split}d({v})=\sum_{{e}\in\mathcal{E}}\mathbf{W}({e})\mathbf{H}({v},{e})\end{split}$
(3)

$p$-Laplacian Attention Hypergraph Learning Follow [8], we formulate the
normalized hypergraph Laplacian regularizer as:

$\scriptsize\begin{split}\mathbf{\Delta}_{l}=\mathbf{I}_{v}-\mathbf{D}_{v}^{-\frac{1}{2}}\mathbf{H}\mathbf{W}\mathbf{D}_{e}^{-1}\mathbf{H}^{T}\mathbf{D}_{v}^{-\frac{1}{2}}\end{split}$
(4)

where $\mathbf{I}_{v}\in\mathcal{R}^{|\mathcal{V}|\times|\mathcal{V}|}$
denotes the identity matrix. In most hypergraph learning tasks, the elements
in $\mathbf{W}$ are set to $1$, represent that different hyperedges contribute
equally for nodes aggregation. While in our paper, we introduce $p$-Laplacian
to approximate the relations of hyperedges, to further aggregate high-order
information, which can be formulated as:

$\scriptsize\begin{split}\mathbf{\Delta}_{pl}=\mathbf{I}_{v}-\mathbf{D}_{v}^{-\frac{1}{2}}\mathbf{H}\left(\mathbf{I}_{e}-\mathbf{L}_{p}\right)\mathbf{D}_{e}^{-1}\mathbf{H}^{T}\mathbf{D}_{v}^{-\frac{1}{2}}\end{split}$
(5)

where $\mathbf{I}_{e}\in\mathbb{R}^{|\mathcal{E}|\times|\mathcal{E}|}$ denotes
the identity matrix. $\mathbf{L}_{p}=\mathcal{Q}\Lambda\mathcal{Q}^{T}$.
$\mathcal{Q}=\left(q^{1},q^{2},\cdots,q^{M}\right)$ denotes the full
eigenvector, and
$\Lambda=\left(\Lambda^{1},\Lambda^{2},\cdots,\Lambda^{M}\right)$ denotes the
corresponding eigenvalue. According to [9], we solve the $p$-Laplacian
embedding as:

$\scriptsize\begin{split}&\mathop{\arg\min}\limits_{\mathcal{Q}}f_{1}(\mathcal{Q})=\sum_{{m}\in\mathcal{M}}\frac{\sum_{i,j\in|\mathcal{V}|}w_{ij}|q_{i}^{m}-q_{j}^{m}|^{p}}{\left\|q^{m}\right\|_{p}^{p}}\\\
&{\rm{s}}.t.{\kern 4.0pt}\mathcal{Q}^{T}\mathcal{Q}=\mathbf{I}\end{split}$ (6)

where $w_{ij}$ is the element in $\mathbf{W}$. Here, we use the gradient
method to solve Equation 6 as:

$\scriptsize\begin{split}\frac{\partial f_{1}}{\partial
q_{i}^{m}}=\frac{1}{\left\|q^{m}\right\|_{p}^{p}}\left[\sum_{j}w_{ij}\phi_{p}\left(q_{i}^{m}-q_{j}^{m}\right)-\frac{\phi_{p}\left(q_{i}^{m}\right)}{\left\|q^{m}\right\|_{p}^{p}}\right]\end{split}$
(7)

where $\phi_{p}$ is defined that
$\phi_{p}\left(x\right)=|x|^{p-1}sig\left(x\right)$. $sig$ denotes the
operator to compute the negative and positive signs. To enforce the
orthogonality, we follow [10] to update $\mathcal{Q}$ until convergence as:

$\scriptsize\begin{split}\mathcal{Q}=\mathcal{Q}-\beta\left(\frac{\partial
f_{1}}{\partial\mathcal{Q}}-\mathcal{Q}\left(\frac{\partial
f_{1}}{\partial\mathcal{Q}}\right)^{T}\mathcal{Q}\right)\end{split}$ (8)

where $\beta$ is the step length. At last, we obtain the corresponding
eigenvalue as :

$\scriptsize\begin{split}\Lambda^{m}=\frac{\sum_{i,j\in|\mathcal{V}|}w_{ij}|q_{i}^{m}-q_{j}^{m}|^{p}}{\left\|q^{m}\right\|_{p}^{p}}\end{split}$
(9)

Pseudo Label Generation Assume parts of training data have labels, define
initial label embedding matrix as $\mathbf{O}\in\mathbb{R}^{C\times N}$, where
$C$ denotes the total number of classes. For labeled samples,
$\mathbf{O}_{ij}$ is $1$ if the $j$-th sample belongs to the $i$-th class, and
it is $0$ otherwise. For unlabeled samples, we set all elements to $0.5$. We
formulate the objective function as:

$\scriptsize\begin{split}&\mathop{\arg\min}\limits_{\mathbf{F}}f_{2}(\mathbf{F})=\text{tr}\left(\Delta_{pl}\mathbf{F}^{T}\mathbf{F}\right)+\lambda\left\|\mathbf{F}-\mathbf{O}\right\|_{F}^{2}\\\
\end{split}$ (10)

where $\lambda$ is the parameter to balance the objective function. According
to [6], we directly obtain the pseudo label as:

$\scriptsize\begin{split}\mathbf{F}=\left(\mathbf{I}_{v}+\frac{1}{\lambda}\mathbf{\Delta}_{pl}\right)^{-1}\mathbf{O}\end{split}$
(11)

where $\mathbf{F}\in\mathbb{R}^{C\times N}$ is the predicted pseudo label
matrix. Unlike the one-hot truth label matrix, the $\mathbf{F}$ is soft.

###  2.2 Self-Supervised Dictionary Learning

The above section shows that the learned pseudo label information only relies
on the hypergraph structure. That is to say, the proposed $p$-Laplacian
Attention Hypergraph Learning (pAHL) is a model-agnostic approach, which can
be embedded into any dictionary learning framework. Here, we just introduce
the pAHL block into a standard dictionary learning. The objective function can
be formulated as:

$\scriptsize\begin{split}&\mathop{\arg\min}\limits_{\mathbf{D},\mathbf{S},\mathbf{B}}f_{3}(\mathbf{D},\mathbf{S},\mathbf{B})\\\
&=\left\|\mathbf{X}-\mathbf{D}\mathbf{S}\right\|_{F}^{2}+2\alpha\left\|\mathbf{S}\right\|_{\ell_{1}}+\gamma{\kern
2.0pt}\left\|\mathbf{F}-\mathbf{B}\mathbf{S}\right\|_{F}^{2}\\\ &{\kern
5.0pt}{\rm{s}}.t.\left\|{{{\bf{d}}_{\bullet k}}}\right\|_{2}^{2}\leq 1,{\kern
5.0pt}\left\|{{{\bf{b}}_{\bullet k}}}\right\|_{2}^{2}\leq 1{\kern
4.0pt}\left({k=1,2,\cdots K}\right)\\\ \end{split}$ (12)

where
$\mathbf{X}=[{\mathbf{x}}_{1},{\mathbf{x}}_{2},\dots,{\mathbf{x}}_{N}]\in\mathbb{R}^{dim\times
N}$ denotes the training data, ${\mathbf{x}}_{i}$ ($i=1,2,\dots$) denotes the
feature embedding of the $i$-${th}$ sample, $dim$ denotes the dimension size
of each sample, $N$ is the number of training samples.
$\mathbf{D}\in\mathbb{R}^{dim\times K}$ represents the to-be-learned
dictionary, $K$ is the dictionary base size. $\mathbf{B}\in\mathbb{R}^{C\times
K}$ represents the to-be-learned classifier, $C$ denotes the class number.
$\mathbf{S}\in\mathbb{R}^{K\times N}$ denotes the sparse codes for dictionary.
$\alpha$ and $\gamma$ are the positive scalar constants.

We alternate update $\mathbf{S}$, $\mathbf{D}$ and $\mathbf{B}$ until the
objective function doesn’t descend. $\mathbf{S}$ can be solved as:

$\scriptsize\begin{split}\mathbf{S}_{kn}={\frac{max\left(\mathcal{J},\alpha\right)+min\left(\mathcal{J},\alpha\right)}{\left(\mathbf{D}^{T}\mathbf{D}+\gamma{\kern
2.0pt}\mathbf{B}^{T}\mathbf{B}\right)_{kk}}}\end{split}$ (13)

where

$\scriptsize\begin{split}\mathcal{J}&=\left(\mathbf{D}^{T}\mathbf{X}+\gamma\mathbf{B}^{T}\mathbf{F}\right)_{kn}-\sum_{l=1,l\neq
k}^{K}\left(\mathbf{D}^{T}\mathbf{D}+\gamma\mathbf{B}^{T}\mathbf{B}\right)_{kl}\mathbf{S}_{ln}\end{split}$
(14)

Then we introduce BCD [11] to update $\mathbf{B}$ and $\mathbf{D}$ as:

$\scriptsize\begin{split}\mathbf{D}_{\bullet
k}=\frac{\mathbf{X}\left(\mathbf{S}_{k\bullet}\right)^{T}-\mathbf{\tilde{D}}^{k}\mathbf{S}\left(\mathbf{S}_{k\bullet}\right)^{T}}{\|\mathbf{X}\left(\mathbf{S}_{k\bullet}\right)^{T}-\mathbf{\tilde{D}}^{k}\mathbf{S}\left(\mathbf{S}_{k\bullet}\right)^{T}\|_{2}}\end{split}$
(15) $\scriptsize\begin{split}\mathbf{B}_{\bullet
k}=\frac{\mathbf{F}\left(\mathbf{S}_{k\bullet}\right)^{T}-\mathbf{\tilde{B}}^{k}\mathbf{S}\left(\mathbf{S}_{k\bullet}\right)^{T}}{\|\mathbf{F}\left(\mathbf{S}_{k\bullet}\right)^{T}-\mathbf{\tilde{B}}^{k}\mathbf{S}\left(\mathbf{S}_{k\bullet}\right)^{T}\|_{2}}\end{split}$
(16)

where $\mathbf{\tilde{D}}=\left\\{\begin{array}[]{cc}{\mathbf{D}_{\bullet
p}}&{p\neq{k}}\\\ {\mathbf{0}}&{p=k}\end{array}\right.$,
$\mathbf{\tilde{B}}=\left\\{\begin{array}[]{cc}{\mathbf{B}_{\bullet
p}}&{p\neq{k}}\\\ {\mathbf{0}}&{p=k}\end{array}\right.$, $\mathbf{0}$ denotes
zero matrix. We conduct the Self-Supervised Dictionary Learning method in
Algorithm 1.

1

Input: $\mathbf{X}\in\mathbb{R}^{dim\times N}$

Output: $\mathbf{D}\in\mathbb{R}^{dim\times K}$,
$\mathbf{S}\in\mathbb{R}^{K\times N}$

2 Construct hypergraph $\mathbf{H}$ by Equation 1.

3

4while  _i <maxitem_ do

5 Solve $p$-Laplacian embedding, update eigenvector $\mathcal{Q}$ by Equation
7, 8.

6 Update eigenvalue $\Lambda$ by Equation 9.

7

8

9Obtain $p$-Laplacian-based attention hypergraph regularizer
$\mathbf{\Delta}_{pl}$ by Equation 5.

10

11Generate pseudo label $\mathbf{F}$ by Equation 10, 11.

12

13while  _j <maxitem_ do

14 Update sparse codes $\mathbf{S}$ by Equation 13,14.

15 Update dictionary $\mathbf{D}$ by Equation 15.

16 Update classifier $\mathbf{B}$ by Equation 16.

17

18

Algorithm 1 Self-Supervised Dictionary Learning

##  3 Experiment

Dictionary learning has been widely applied in many fields. Here we evaluate
the learned dictionary in human activity recognition tasks. There are two
datasets, including Stanford 40 Actions (Stanford40) [12] dataset and UIUC
Sports Event (UIUC-SE) [13] dataset. We first introduce the experimental
setup. Then compare the proposed SSDL with state-of-the-art methods. Next, we
try to embed the proposed pAHL block into other classical methods to evaluate
the model-agnostic ability. Following, we conduct ablation studies to analyze
our method. At last, we discuss something about the pretext task.

###  3.1 Experimental Setup

For all the datasets, we employ standard Resnet to extract feature embedding
with $2,048$ dimensions, select $70\%$ for training, the rest for testing, and
only $40\%$ training data has labels. For the $p$ and $\lambda$ in pretext
task, they play the key roles to obtain a suitable pseudo label matrix for
dictionary learning. We fix them to $1.8$, $0.1$ for Stanford40, and $2.2$,
$0.1$ for UIUC-SE. There is a trick to tune the two parameters, for more
details, please refer to section 3.3. In dictionary learning, we set the
dictionary size $K$ to half the number of training samples for the two
datasets, and $\alpha=2^{-14}$, $\gamma=2^{-12}$ for Stanford40 dataset,
$\alpha=2^{-12}$, $\gamma=2^{-12}$ for UIUC-SE dataset. The details are also
discussed in section 3.3.

Table 1: Recognition results with $40\%$ label rates. Methods$\backslash$Datasets | Stanford40 | UIUC-SE
---|---|---
SRC (TPAMI [14], 2009) | 66.0$\%$ | 88.4$\%$
CRC (ICCV [15], 2011) | 70.1$\%$ | 94.2$\%$
NRC (PR [16], 2019) | 67.7$\%$ | 89.7$\%$
SLRC (TPAMI [17], 2018) | 65.3$\%$ | 93.4$\%$
Euler-SRC (AAAI [18], 2018) | 66.9$\%$ | 90.2$\%$
ADDL (TNNLS [19], 2018) | 74.8$\%$ | 95.7$\%$
FDDL (ICCV [20], 2011) | 73.3$\%$ | 94.2$\%$
LC-KSVD (TPAMI [4], 2013) | 67.7$\%$ | 89.1$\%$
LC-PDL (IJCAI [21], 2019) | 73.3$\%$ | 91.3$\%$
LEDL (NC [5], 2020) | 72.9$\%$ | 91.8$\%$
CDLF (SP [2], 2020) | 72.7$\%$ | 92.4$\%$
SSDL | 75.9$\%$ | 96.4$\%$
Fig. 3: Comparison results about pAHL-LEDL and pAHL-CDLF on Stanford40 dataset
with $40\%$ label rates.

Fig. 4: Ablation studies

###  3.2 Experimental Results

We compare our SSDL with other state-of-the-art methods. We split these
approaches into two categories, which are separated by horizontal lines in
Table 1: $i)$ Traditional machine learning methods (directly use the testing
samples to fit the training samples), including SRC [14], CRC [15], NRC [16],
SLRC [17] and Euler-SRC [18]. $ii)$ Dictionary learning methods, including
ADDL [19], FDDL [20], LC-KSVD [4], LC-PDL [21], LEDL [5], CDLF [2]. We show
the recognition results with $40\%$ labeled training data in Table 1 and have
the following observations.

From Table 1, we can see that our SSDL can outperform all other methods at
least $1.1\%$ and $0.7\%$ on the Stanford40 and UIUC-SE datasets,
respectively. Compared with the traditional methods, our SSDL has significant
improvements, but we need to consume more resources when training the
dictionary. Compared with other state-of-the-art dictionary learning based
approaches, SSDL has at least $0.7\%$ improvement. For the label-embedded
dictionary learning methods (LC-KSVD, LC-PDL, LEDL, CDLF), SSDL’s recognition
accuracies can exceed them at least $2.6\%$. This phenomenon has demonstrated
the efficiency of our method to some extent.

However, our SSDL just embeds the pAHL based pretext task into a basic
dictionary learning model. As mentioned in section 1, the pAHL block is a
model-agnostic method that can be embedded into any standard dictionary
learning algorithm, such as LC-KSVD, LC-PDL, LEDL, CDLF. That is to say, we
may achieve higher recognition accuracies if we try to embed our pAHL block
into these models. To evaluate this statement, we expand pAHL block to LEDL
and CDLF on the Stanford40 dataset. The results are shown in Figure 3.
Obviously see that, compared with original methods, the pAHL-embedded LEDL and
CDLF can achieve more powerful performances than SSDL.

###  3.3 Ablation Studies

The SSDL approach has achieved outstanding performance. It is interesting to
recognize what are the factors affecting the experimental results. For this
purpose, we design two ablation studies to discuss the proposed SSDL method.

$i)$ One of our approach’s main contributions is to reduce the dependence on
labeled data for dictionary learning. Thus, we design an ablation study on the
UIUC-SE dataset to observe the effect of label rates. From Figure 4, we can
see that, with the decrease of label rates, the performances of the two
methods are decreasing, but our method is much slower than the other one.

$ii)$ There are mainly four parameters ($p$, $\lambda$, $\alpha$, $\gamma$)
influence the results. We set all the evaluated experiments to $40\%$ label
rate on the UIUC-SE dataset. Here, we first discuss the $p$ and $\lambda$ in
the pretext task. We adjust $p$ and $\lambda$ to obtain a pseudo label matrix.
Usually, we fine-tune the two parameters according to the final results (as an
example, in our paper, we can adjust the two parameters by the recognition
accuracy). Here, we give a trick to easier ensure the two optimal parameters.
Specifically, we first use the training data to generate a model with $p$ and
$\lambda$. Then employ the training model to compute the cross-entropy loss of
testing data. At last, adjust the parameters until achieving the minimum loss.
The influence of $p$ and $\lambda$ are separately shown in Figure 4, 4. The
y-axis denotes the testing data’s loss. We obtain the minimum loss near
$p=2.2$ and $\lambda=0.1$. For $\alpha$ and $\gamma$, they interact with each
other. Thus we explore the impact of these two parameters simultaneously.
Figure 4 shows the experimental results. The proposed SSDL approach is not
sensitive to these two parameters.

###  3.4 Pretext Task

In our framework, we set our proposed pAHL as the pretext task. Actually, it
is flexible to select other methods, such as GL [22], HL [6], HL-W [23], DHSL
[24], to predict the pseudo label for dictionary learning. We employ the cross
entropy loss to describe the influence. Results are shown in Table 2.
Obviously see that, our pAHL is able to get better performance than GL, HL,
and HL-W, but obtain similar results with DHSL.

Table 2: Cross-entropy loss on pretext task with $40\%$ label rates. Methods$\backslash$Datasets | Stanford40 | UIUC-SE
---|---|---
GL (NIPS [22], 2003) | 0.47 | 0.51
HL (NIPS [6], 2007) | 0.64 | 0.42
HL-W (TIP [23], 2012) | 0.51 | 0.36
DHSL (IJCAI [24], 2018) | 0.49 | 0.27
pAHL | 0.43 | 0.31

##  4 Conclusion

Label-embedded dictionary learning is a typical technology in machine
learning. However, limited to introducing the label information, this category
of approaches is only appliable in supervised learning. Inspired by the self-
supervised idea, we propose a self-supervised dictionary learning method to
expand label-embedded dictionary learning to semi-supervised and unsupervised
learning. To our best knowledge, this is the first attempt to solve this
dictionary learning challenge from the self-supervised perspective.
Experimental results have demonstrated the efficiency of our method.

##  5 Acknowledgements

The paper was supported by the National Natural Science Foundation of China
(Grant No. 62072468), the Natural Science Foundation of Shandong Province,
China (Grant No. ZR2019MF073, ZR2018MF017), the Open Research Fund from
Shandong Provincial Key Laboratory of Computer Network (No. SDKLCN-2018-01),
Qingdao Science and Technology Project (No. 17-1-1-8-jch), the Fundamental
Research Funds for the Central Universities, China University of Petroleum
(East China) (Grant No. 20CX05001A), the Major Scientific and Technological
Projects of CNPC (No. ZD2019-183-008), and the Creative Research Team of Young
Scholars at Universities in Shandong Province (No.2019KJN019).

## References

  * [1] Yi Peng, Deyu Meng, Zongben Xu, Chenqiang Gao, Yi Yang, and Biao Zhang,  “Decomposable nonlocal tensor dictionary learning for multispectral image denoising,”  in CVPR, 2014, pp. 2949–2956.
  * [2] Yan-Jiang Wang, Shuai Shao, Rui Xu, Weifeng Liu, and Bao-Di Liu,  “Class specific or shared? a cascaded dictionary learning framework for image classification,”  Signal Processing, vol. 176, pp. 107697, 2020.
  * [3] Qiang Zhang and Baoxin Li,  “Discriminative k-svd for dictionary learning in face recognition,”  in CVPR. IEEE, 2010, pp. 2691–2698.
  * [4] Zhuolin Jiang, Zhe Lin, and Larry S Davis,  “Label consistent k-svd: Learning a discriminative dictionary for recognition,”  TPAMI, vol. 35, no. 11, pp. 2651–2664, 2013.
  * [5] Shuai Shao, Rui Xu, Weifeng Liu, Bao-Di Liu, and Yan-Jiang Wang,  “Label embedded dictionary learning for image classification,”  Neurocomputing, vol. 385, pp. 122–131, 2020.
  * [6] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf,  “Learning with hypergraphs: Clustering, classification, and embedding,”  in NeurIPS, 2007, pp. 1601–1608.
  * [7] Xueqi Ma, Weifeng Liu, Shuying Li, Dapeng Tao, and Yicong Zhou,  “Hypergraph $p$-laplacian regularization for remotely sensed image recognition,”  TGRS, vol. 57, no. 3, pp. 1585–1595, 2018.
  * [8] Shenghua Gao, Ivor Wai-Hung Tsang, and Liang-Tien Chia,  “Laplacian sparse coding, hypergraph laplacian sparse coding, and applications,”  TPAMI, vol. 35, no. 1, pp. 92–104, 2013.
  * [9] Dijun Luo, Heng Huang, Chris Ding, and Feiping Nie,  “On the eigenvectors of p-laplacian,”  Machine Learning, vol. 81, no. 1, pp. 37–51, 2010.
  * [10] Weifeng Liu, Xueqi Ma, Yicong Zhou, Dapeng Tao, and Jun Cheng,  “$p$-laplacian regularization for scene recognition,”  TCB, vol. 49, no. 8, pp. 2927–2940, 2018.
  * [11] Bao-Di Liu, Yu-Xiong Wang, Bin Shen, Yu-Jin Zhang, and Yan-Jiang Wang,  “Blockwise coordinate descent schemes for sparse representation,”  in ICASSP. IEEE, 2014, pp. 5267–5271.
  * [12] Bangpeng Yao, Xiaoye Jiang, Aditya Khosla, Andy Lai Lin, Leonidas Guibas, and Li Fei-Fei,  “Human action recognition by learning bases of action attributes and parts,”  in ICCV. IEEE, 2011, pp. 1331–1338.
  * [13] Li-Jia Li and Li Fei-Fei,  “What, where and who? classifying events by scene and object recognition,”  in ICCV. IEEE, 2007, pp. 1–8.
  * [14] John Wright, Allen Y Yang, Arvind Ganesh, S Shankar Sastry, and Yi Ma,  “Robust face recognition via sparse representation,”  TPAMI, vol. 31, no. 2, pp. 210–227, 2009.
  * [15] Lei Zhang, Meng Yang, and Xiangchu Feng,  “Sparse representation or collaborative representation: Which helps face recognition?,”  in ICCV. IEEE, 2011, pp. 471–478.
  * [16] Jun Xu, Wangpeng An, Lei Zhang, and David Zhang,  “Sparse, collaborative, or nonnegative representation: Which helps pattern classification?,”  PR, vol. 88, pp. 679–688, 2019.
  * [17] Weihong Deng, Jiani Hu, and Jun Guo,  “Face recognition via collaborative representation: Its discriminant nature and superposed representation,”  TPAMI, vol. 40, no. 10, pp. 2513–2521, 2018.
  * [18] Yang Liu, Quanxue Gao, Jungong Han, and Shujian Wang,  “Euler sparse representation for image classification,”  in AAAI, 2018, pp. 3691–3697.
  * [19] Zhao Zhang, Weiming Jiang, Jie Qin, Li Zhang, Fanzhang Li, Min Zhang, and Shuicheng Yan,  “Jointly learning structured analysis discriminative dictionary and analysis multiclass classifier,”  TNNLS, vol. 29, no. 8, pp. 3798–3814, 2018.
  * [20] Meng Yang, Lei Zhang, Xiangchu Feng, and David Zhang,  “Fisher discrimination dictionary learning for sparse representation,”  in ICCV. IEEE, 2011, pp. 543–550.
  * [21] Zhao Zhang, Weiming Jiang, Zheng Zhang, Sheng Li, Guangcan Liu, and Jie Qin,  “Scalable block-diagonal locality-constrained projective dictionary learning,”  in IJCAI, 2019, pp. 4376–4382.
  * [22] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf,  “Learning with local and global consistency,”  NeurIPS, vol. 16, pp. 321–328, 2003.
  * [23] Yue Gao, Meng Wang, Dacheng Tao, Rongrong Ji, and Qionghai Dai,  “3-d object retrieval and recognition with hypergraph analysis,”  TIP, vol. 21, no. 9, pp. 4290–4303, 2012.
  * [24] Zizhao Zhang, Haojie Lin, Yue Gao, and KLISS BNRist,  “Dynamic hypergraph structure learning.,”  in IJCAI, 2018, pp. 3162–3169.


# Quasirandom and quasisimple groups

Marco Barbieri and Luca Sabatini  Dipartimento di Matematica “Felice
Casorati”, University of Pavia, Via Ferrata 5, 27100 Pavia, Italy
<EMAIL_ADDRESS>Luca Sabatini, Queen’s University
Belfast<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Fix $\varepsilon>0$. We say that a finite group $G$ is
$\varepsilon$-quasirandom if every nontrivial irreducible complex
representation of $G$ has degree at least $|G|^{\varepsilon}$. In this paper,
we give a structure theorem for large $\varepsilon$-quasirandom groups, and we
completely classify the $\frac{1}{5}$-quasirandom groups.

###### Key words and phrases:

Quasirandom groups, quasisimple groups.

###### 2020 Mathematics Subject Classification:

Primary: 20D99, 20C99.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Quasirandom groups of affine type
  4. 4 Proof of the main theorems

##  1\. Introduction

Informally, a finite group is called quasirandom if its nontrivial complex
irreducible representations have “large” degree, where the precise meaning of
“large” depends on context. The terminology was introduced explicitly in [11],
where the name arises because dense Cayley graphs in quasirandom groups are
quasirandom graphs in the sense of Chung, Graham, and Wilson [6]. This
property had already been used implicitly to construct expander graphs in [22,
9]. After Gowers’ groundbreaking paper, quasirandom groups have been at the
center of spectacular development. Bourgain and Gamburd [3] used the
quasirandomness of $\mathrm{SL}_{2}(p)$ to show that random Cayley graphs on
these groups are expanders with high probability. Their work has inspired an
impressive series of articles, culminating in [4]. In a more subtle way,
quasirandomness played a key role in Helfgott’s work [13] and generalizations,
most notably [5, 20, 8]. Tao dedicated an entire chapter of his book [25] to
quasirandom groups.
As said, being quasirandom is a quantitative property. For applications to
expansion in Cayley graphs, one needs that every nontrivial irreducible
representation has degree at least $|G|^{\varepsilon}$, for some constant
$\varepsilon>0$ independent of the size of $G$. This motivates the following
definition:

######  Definition.

Let $\varepsilon>0$. A finite group $G$ is $\varepsilon$-quasirandom if every
nontrivial irreducible complex representation of $G$ has degree at least
$|G|^{\varepsilon}$.

It is well known that the finite simple groups of Lie type are
$\varepsilon$-quasirandom for some $\varepsilon>0$ which depends only on the
rank [15], a fact that is exploited in all the papers we mentioned above. A
more general discussion on quasirandomness is taken by Babai, Nikolov and
Pyber [2], and Nikolov and Pyber [19]. The celebrated Gowers’ trick [19] says
that, if $G$ is $\varepsilon$-quasirandom and $S\subseteq G$ is a large
subset, namely $|S|\geq|G|^{1-\frac{\varepsilon}{3}}$, then $S^{3}=G$. This
fact, as well as other natural invariants of $G$, can be used to characterize
quasirandomness. Such equivalences look particularly nice when expressed in
the exponential regime (see Theorem 2.6 below).
The algebraic structure of quasirandom groups remains unexplored. The present
article was born from our need to answer the question: what, concretely, is a
quasirandom group? In the first main result we describe the large
$\varepsilon$-quasirandom groups, for any fixed $\varepsilon>0$. They are
precisely the groups whose quotient by the solvable radical is a relatively
large direct product of boundedly many finite simple groups of Lie type of
bounded rank.

######  Theorem A.

Fix $\varepsilon>0$. If $G$ is an $\varepsilon$-quasirandom group, then
$|G/Sol(G)|\geq|G|^{\varepsilon}$. If $|G|$ is sufficiently large depending on
$\varepsilon$, then $G/Sol(G)$ is a direct product of boundedly many finite
simple groups of Lie type of bounded rank.
Conversely, suppose that $G$ is perfect, $|G/Sol(G)|\geq|G|^{\varepsilon}$,
and that $G/Sol(G)$ is $\varepsilon$-quasirandom. If $|G|$ is sufficiently
large depending on $\varepsilon$, then $G$ is
$\frac{\varepsilon^{2}}{3}$-quasirandom.

For the second main result, we study the groups that are
$\varepsilon$-quasirandom with a relatively large $\varepsilon$. It is a
widespread belief that $(\mathrm{PSL}_{2}(q))_{q\geq 4}$ is the “most
quasirandom” family of groups [23, 28], but not much is known. Not only this
is actually the case, but we prove that the vast majority of highly
quasirandom groups are quasisimple, shedding a good light on the issue.

######  Theorem B.

Let $G$ be a $\frac{1}{5}$-quasirandom group. Then one of the following holds:

  1. $(a)$

$G\cong(\mathbb{F}_{3})^{3}\rtimes\mathrm{SL}_{3}(3)$;

  2. $(b)$

$G$ is a perfect central extension of
$(\mathbb{F}_{2^{f}})^{4}\rtimes\mathrm{Sp}_{4}(2^{f})$, $f\geq 6$;

  3. $(c)$

$G$ is quasisimple.

The low dimensional representations of the quasisimple groups are known [26],
thus it is an easy (although laborious) task to recover the full list of the
$\frac{1}{5}$-quasirandom groups from Theorem B. An interesting consequence is
the following:

######  Corollary C.

Every $\frac{3}{14}$-quasirandom group is quasisimple.

The constant $\frac{3}{14}$ is best possible, precisely because of the family
in Theorem Bb. On the other hand, the value $\frac{1}{5}$ is the result of a
compromise, as with our machinery and more work one can obtain a deeper
classification. There are some reasons to prefer $\frac{1}{5}$: first, it is
small enough to provide Corollary C. Second, it makes the theorem sharp in
some sense, because there exist infinitely many nonquasisimple groups which
are $(\frac{1}{5}-\varepsilon)$-quasirandom, for any $\varepsilon>0$ (see
Section 3). It also makes the proof a little cleaner, because every
$\frac{1}{5}$-quasirandom group has a unique maximal normal subgroup (Lemma
4.8). We point out that similar methods are useful to study quasirandomnes at
other regimes different from the exponential, which could be of interest as
well (see also Remark 4.6). The shallow version of Theorem B is the following:

######  Corollary D.

The only $\frac{1}{3}$-quasirandom groups are the sporadic simple groups
$J_{1}$ and $O^{\prime}N$.

We will actually prove Corollary D as a “baby” Theorem B. The philosophy
behind the proofs is that quasirandom groups are pretty rigid, and lend
themselves very little to nontrivial extensions, especially the noncentral
ones. To make this idea really say something, we use various properties of the
finite simple groups and their representations. Particularly for Theorem B, we
need a detailed (i.e. quantitative) analysis of quasirandom degrees, modular
and projective representations.
The paper is structured as follows. In Section 2 we introduce the
(exponential) quasirandom degree $\bm{\varepsilon}(G)$ of a finite group, and
give basic results about quasisimple groups, modular and projective
representations. In Section 3, we provide some highly quasirandom
nonquasisimple groups: they are of affine type as in Theorem Bb. We prove the
main theorems in Section 4. Fundamental to our discussion is the knowledge of
the quasirandom degrees of the finite simple groups, so we collect these data
in the Appendix.

##  2\. Preliminaries

###  2.1. Minimal degree of a nontrivial representation

In this paper, every group is finite. For a nontrivial finite group $G$, we
denote by $\mathbf{D}_{0}(G)$ the minimal degree of a nontrivial irreducible
complex representation of $G$, that is,

$\mathbf{D}_{0}(G)\>:=\>\min\left\\{\dim(\pi)\mid\pi\in\mathrm{Irr}(G)\setminus\\{1\\}\right\\}.$

We start with the following, which appears as [25, Ex. 1.3.2].

######  Lemma 2.1.

Let $N\lhd G$ be a nontrivial proper normal subgroup. Then

$\mathbf{D}_{0}(G/N)\>\geq\>\mathbf{D}_{0}(G).$

If the previous inequality is strict, then

$\mathbf{D}_{0}(G)\>\geq\>\mathbf{D}_{0}(N).$

###### Proof.

Each nontrivial irreducible representation of $G/N$ provides a nontrivial
representation of $G$. The first inequality follows. For the second one,
suppose there exists $\pi\in\mathrm{Irr}(G)$ such that
$\dim(\pi)=\mathbf{D}_{0}(G)<\mathbf{D}_{0}(G/N)$. Observe that the
restriction $\pi_{\downarrow_{N}}$ of $\pi$ to $N$ is nontrivial: otherwise
$N\subseteq Ker(\pi)$, and $\pi$ would induce a nontrivial irreducible
representation of $G/N$ whose degree is $\dim(\pi)$, against the minimality of
$\mathbf{D}_{0}(G/N)$. Therefore, $\pi_{\downarrow N}$ contains a nontrivial
irreducible representation of $N$, and so
$\dim(\pi)=\dim(\pi_{\downarrow_{N}})\geq\mathbf{D}_{0}(N)$. ∎

######  Lemma 2.2.

If $G$ acts nontrivially on a finite set $\Omega$, then
$\mathbf{D}_{0}(G)\leq|\Omega|-1$.

###### Proof.

Recall that $\mathrm{Sym}(n)$ has a natural embedding into $\mathrm{GL}_{n}$,
and that any permutation representation contains the trivial representation,
because the diagonal subspace is fixed by every element of $G$. ∎

We can obtain some useful bounds by considering the natural actions of $G$.

######  Corollary 2.3.

The following inequalities hold:

  1. $(i)$

if $H<G$ is a proper subgroup, then

$|G:H|\,\geq\,\mathbf{D}_{0}(G/\mathrm{Core}_{G}(H))+1\,;$

  2. $(ii)$

if $N\lhd G$ is a noncentral normal subgroup, then

$|N|\,\geq\,\mathbf{D}_{0}(G/\mathbf{C}_{G}(N))+2\,;$

  3. $(iii)$

if $C\subseteq G$ is a nontrivial conjugacy class, then

$|C|\,\geq\,\mathbf{D}_{0}(G)+1\,.$

###### Proof.

Use Lemma 2.2 on: the action of $G/\mathrm{Core}_{G}(H)$ on the right cosets
of $H$ by multiplication; the action of $G/\mathbf{C}_{G}(N)$ on
$N\setminus\\{1\\}$ by conjugation; the action of $G$ on $C$ by conjugation. ∎

We would like to mention some connections between $\mathbf{D}_{0}(G)$ and
other important parameters associated to a finite group: the number of
conjugacy classes $\mathbf{k}(G)$, the representation growth
$\mathbf{r}_{n}(G)$, and the minimal index of a proper subgroup, i.e.
$\bm{\iota}(G):=\min_{H<G}|G:H|$.

######  Remark 2.4.

By standard results in representation theory, we can write

$|G|=\sum_{\pi\in\mathrm{Irr}(G)}\dim(\pi)^{2}\geq
1+(\mathbf{k}(G)-1)\mathbf{D}_{0}(G)^{2}.$

Let $G$ be an $\varepsilon$-quasirandom group. It follows that
$\varepsilon<\frac{1}{2}$, and $\mathbf{k}(G)\leq|G|^{1-2\varepsilon}$.
Moreover, the number $\mathbf{r}_{n}(G)$ of the inequivalent irreducible
representations of degree $n$ is polynomially bounded, namely
$\mathbf{r}_{n}(G)\leq n^{\varepsilon^{-1}-2}$ for all $n$ (see [21, Lemma
25]).

######  Remark 2.5.

Using the Classification of the Finite Simple Groups, Nikolov and Pyber [19]
have proved that there is an absolute constant $c$ such that

$\bm{\iota}(G)\>\leq\>c\>\mathbf{D}_{0}(G)^{2}$

for every finite perfect group $G$. A converse inequality,
$\mathbf{D}_{0}(G)<\bm{\iota}(G)$, follows from the previous lemmas. Lev [16]
proved that $\bm{\iota}(G)\leq|G|^{0.5}$ for every finite group $G$ whose
order is not a prime (equality is achieved by groups of order $p^{2}$). From
Corollaries C and D, we obtain $\mathbf{D}_{0}(G)<|G|^{0.2143}$ whenever $G$
is not quasisimple, and $\mathbf{D}_{0}(G)<|G|^{0.3464}$ for every finite
group.

###  2.2. Quasirandom degree

Let $G$ be a nontrivial finite group. We introduce the (exponential)
quasirandom degree of $G$ by

$\bm{\varepsilon}(G)\>:=\>\log_{|G|}\mathbf{D}_{0}(G).$

By definition, $\mathbf{D}_{0}(G)=|G|^{\bm{\varepsilon}(G)}$, and
$\bm{\varepsilon}(G)$ is the maximum $\varepsilon\in[0,\frac{1}{2})$ such that
$G$ is an $\varepsilon$-quasirandom group. Observe that
$\bm{\varepsilon}(G)>0$ if and only if $G$ is perfect. We now report the
theorem of Nikolov and Pyber mentioned in the Introduction:

######  Theorem 2.6 (Theorem 3.1 in [19]).

Let $G$ be a finite perfect group. The following statements are roughly
equivalent, in the sense that if one statement holds for a small constant
$\varepsilon>0$, then all others hold with constants that are a positive
fraction of $\varepsilon$:

  * •

$G$ is $\varepsilon$-quasirandom;

  * •

every proper subgroup of $G$ has index at least $|G|^{\varepsilon}$;

  * •

for every subset $S$ of size at least $|G|^{1-\varepsilon}$ we have $S^{3}=G$;

  * •

every product-free subset of $G$ has size at most $|G|^{1-\varepsilon}$.

Let $N\lhd G$ be a proper normal subgroup. From an easy computation, we write

$\bm{\varepsilon}(G)\>=\>\bm{\varepsilon}(G/N)\cdot\frac{\log\mathbf{D}_{0}(G)}{\log\mathbf{D}_{0}(G/N)}\cdot\frac{\log|G/N|}{\log|G|}.$

(We remark here that, when we consider a ratio of logarithms, the base can be
chosen arbitrarily.) It is immediate from the equality above and Lemma 2.1
that $\bm{\varepsilon}(G/N)\geq\bm{\varepsilon}(G)$, with equality if and only
if $N$ is trivial. We will use this fact throughout the article without
mentioning it.
We now give a simple but very useful inequality. Let $N\lhd G$ be a proper
normal subgroup. By the definition of quasirandom degree, and Lemma 2.1,

$|G|\>=\>\mathbf{D}_{0}(G)^{1/\bm{\varepsilon}(G)}\>\leq\>\mathbf{D}_{0}(G/N)^{1/\bm{\varepsilon}(G)}.$

Hence, substituting $|G|=|G/N||N|$, we obtain

(2.1) $|N|\>\leq\>\frac{\mathbf{D}_{0}(G/N)^{1/\bm{\varepsilon}(G)}}{|G/N|}.$

What makes (2.1) so useful is that in many occasions we barely know that
$\bm{\varepsilon}(G)$ is large, but we have a good knowledge of $G/N$. The
next lemma provides a gap between $\bm{\varepsilon}(G)$ and
$\bm{\varepsilon}(G/N)$ when $N$ is abelian but noncentral, and it greatly
simplifies the proof of Theorem B.

######  Lemma 2.7.

Let $N\lhd G$ be a noncentral abelian normal subgroup. Then

$\bm{\varepsilon}(G/N)\>>\>\frac{\bm{\varepsilon}(G)}{1-\bm{\varepsilon}(G)}.$

###### Proof.

Since $N$ is abelian, we have $N\subseteq\mathbf{C}_{G}(N)\neq G$. Combining
Lemma 2.1, Corollary 2.3(ii), and (2.1), we write

$\begin{split}\mathbf{D}_{0}(G/N)&\leq\mathbf{D}_{0}(G/\mathbf{C}_{G}(N))\\\
&<|N|\\\
&\leq\frac{\mathbf{D}_{0}(G/N)^{1/\bm{\varepsilon}(G)}}{|G/N|}.\end{split}\,$

Writing $\mathbf{D}_{0}(G/N)=|G/N|^{\bm{\varepsilon}(G/N)}$, we obtain

$|G/N|^{\bm{\varepsilon}(G/N)}<|G/N|^{\frac{\bm{\varepsilon}(G/N)}{\bm{\varepsilon}(G)}-1},$

and the result is proven by comparing the exponents. ∎

Lemma 2.7 may fail if $N$ is central: for instance, we have

$\bm{\varepsilon}(\mathrm{SL}_{2}(7))\approx
0.1889,\quad\bm{\varepsilon}(\mathrm{PSL}_{2}(7))\approx 0.2144,$

and

$\bm{\varepsilon}(\mathrm{PSL}_{2}(7))\><\>\frac{\bm{\varepsilon}(\mathrm{SL}_{2}(7))}{1-\bm{\varepsilon}(\mathrm{SL}_{2}(7))}.$

Such a phenomenon suggests that quasisimple groups are strong candidates
looking for highly quasirandom groups, because $\bm{\varepsilon}(G)$ can be
very close to $\bm{\varepsilon}(G/\mathbf{Z}(G))$.
We now estimate the quasirandom degree of a direct product.

######  Lemma 2.8.

Let $A$ and $B$ be two finite groups, and suppose that
$\bm{\varepsilon}(A)\leq\bm{\varepsilon}(B)$. Then

$\frac{\bm{\varepsilon}(A)}{2}\>\leq\>\bm{\varepsilon}(A\times
B)\>\leq\>\frac{\bm{\varepsilon}(B)}{2}.$

###### Proof.

We have $\mathbf{D}_{0}(A\times
B)=\min\\{\mathbf{D}_{0}(A),\mathbf{D}_{0}(B)\\}$, so that we can write

$\begin{split}\bm{\varepsilon}(A\times
B)&=\frac{\log\left(\min\\{\mathbf{D}_{0}(A),\mathbf{D}_{0}(B)\\}\right)}{\log(|A||B|)}\\\
&=\frac{\log\left(\min\\{|A|^{\bm{\varepsilon}(A)},|B|^{\bm{\varepsilon}(B)}\\}\right)}{\log|A|+\log|B|}\\\
&\leq\bm{\varepsilon}(B)\cdot\frac{\min\\{\log|A|,\log|B|\\}}{\log|A|+\log|B|}\\\
&\leq\frac{\bm{\varepsilon}(B)}{2}.\end{split}\,$

The proof of the other inequality is similar. ∎

######  Corollary 2.9.

Let $(G_{i})_{i=1}^{n}$ be finite groups and suppose
$\bm{\varepsilon}(G_{1})\leq...\leq\bm{\varepsilon}(G_{n})$. Then
$\bm{\varepsilon}(A_{1})/n\leq\bm{\varepsilon}(\prod_{i=1}^{n}A_{i})\leq\bm{\varepsilon}(A_{n})/n$.

###  2.3. Quasisimple groups

We recall that a central extension of a group $Q$ is a short exact sequence

$1\>\to\>N\>\hookrightarrow\>G\>\mapsto\>Q\>\to\>1$

where $N\subseteq\mathbf{Z}(G)$. If $G$ is perfect, then $G$ is a perfect
central extension. A finite group is quasisimple if it is a perfect central
extension of a nonabelian finite simple group, that is, $G$ is perfect and
$G/\mathbf{Z}(G)$ is simple.
It is a key property of perfect groups that, if $G$ is perfect, then there is
a unique universal perfect central extension of $G$, which we denote by
$\widetilde{G}$. This extension is obtained by choosing $N$ isomorphic to the
Schur multiplier of $G$, that is, the second homology group
$H^{2}(G,\mathbb{Z})$. For more details on this, we refer to [1, Sec. 33].
The next two lemmas are essentially well known. We write down Lemma 2.11
below, which is a little more general, and will be useful later.

######  Lemma 2.10.

Let $G$ be a quasisimple group, and let $N\lhd G$ be a proper normal subgroup.
Then $N\subseteq\mathbf{Z}(G)$, and $G/N$ is again quasisimple. Moreover, a
perfect central extension of a quasisimple group is quasisimple.

###### Proof.

See [1, (31.2) and (33.5)]. ∎

######  Lemma 2.11.

Let $G$ be a finite perfect group. Let $N\subseteq\mathbf{Z}(G)$, and $N\lhd
N_{0}\lhd G$ such that $N_{0}/N\subseteq\mathbf{Z}(G/N)$. Then
$N_{0}\subseteq\mathbf{Z}(G)$.

###### Proof.

Let $Z=\mathbf{Z}(G)$. We first show that $\mathbf{Z}(G/N)=Z/N$. It is clear
that $Z/N\subseteq\mathbf{Z}(G/N)$. On the other hand, $\mathbf{Z}(G/N)$ is
certainly contained in the projection of $\mathbf{Z}(G/Z)$ in $G/N$. By Grün’s
Lemma [12] we have $\mathbf{Z}(G/Z)=1$, so $\mathbf{Z}(G/N)\subseteq Z/N$.
Now from the hypotheses we have $N_{0}/N\subseteq Z/N$, i.e. $N_{0}\subseteq
Z$. ∎

We conclude this subsection with the following observation, which is useful
for an inductive argument.

######  Lemma 2.12.

Let $G$ be a nonquasisimple group in which all the proper quotients are
quasisimple. Then either $G$ has a unique minimal normal subgroup, or $G$ is
the direct product of two nonabelian finite simple groups.

###### Proof.

We first notice that either $G$ is a group of prime order, or it is perfect.
In the first case the statement is trivial, thus we can suppose that $G$ is
perfect.
Let us suppose that $N_{1}$ and $N_{2}$ are two distinct minimal normal
subgroups of $G$, so that $N_{1}\cap N_{2}=1$. Let $H=N_{1}N_{2}$, and note
that $G/N_{i}$ is quasisimple for $i\in\\{1,2\\}$. If $G=H$, then $G$ is the
direct product of finite simple factors. In particular, it is easy to see that
these factors must be precisely two and nonabelian.
Aiming for a contradiction, suppose $H\neq G$. Since all the proper normal
subgroups of a quasisimple group are central,
$H/N_{i}\subseteq\mathbf{Z}(G/N_{i})$ for both $i\in\\{1,2\\}$. Let $h\in H$
and $g\in G$. For each $i\in\\{1,2\\}$, we have

$[h,g]N_{i}=[hN_{i},gN_{i}]\subseteq N_{i}.$

It follows that $[h,g]\in N_{1}\cap N_{2}=1$, and since $h\in H$ is arbitrary,
we conclude $H\subseteq\mathbf{Z}(G)$. Finally, by Lemma 2.10, $G$ itself is
quasisimple, against our initial assumption. ∎

###  2.4. Linear and projective representations

So far, we have only dealt with complex linear representations, but modular
and projective representations will be a key tool in the proof of Theorem B.
For a prime $r\geq 2$, we use $\mathbf{D}_{r}(G)$ to denote the minimal degree
of a nontrivial irreducible modular representation of $G$ over a field of
characteristic $r$. We recall that a projective representation of $G$ is a
representation of a perfect central extension of $G$. Equivalently, it is a
group homomorphism

$\rho:\>G\to\mathrm{PGL}(V).$

The degree of the representation is the dimension of $V$. As for linear
representations, we denote by $\mathbf{R}_{0}(G)$ the minimal degree of a
nontrivial complex projective representation, and by $\mathbf{R}_{r}(G)$ the
minimal degree of a nontrivial projective representation over a field of
characteristic $r$. We remark that, if $G$ is finite and perfect, and
$\widetilde{G}$ is its universal perfect central extension, then

$\mathbf{R}_{0}(G)=\mathbf{D}_{0}(\widetilde{G})\leq\mathbf{D}_{0}(G),\quad\hbox{and}\quad\mathbf{R}_{r}(G)=\mathbf{D}_{r}(\widetilde{G})\leq\mathbf{D}_{r}(G).$

In the remainder of this subsection, we focus on the projective
representations of finite simple groups of Lie type. We recall that, if $G$ is
a group of Lie type over a field of characteristic $p$, then a modular
representation of $G$ over a vector space $V$ is in natural characteristic
when the characteristic of $V$ is $p$, while it is in cross-characteristic
otherwise.

######  Lemma 2.13.

Let $L$ be a finite simple group of Lie type over $\mathbb{F}_{q}$, $q=p^{f}$.
If $V$ is a vector space in natural characteristic $p$ on which
$\widetilde{L}$ acts nontrivially, then

$|V|\>\geq\>q^{\,\mathbf{R}_{p}(L)}.$

###### Proof.

It follows immediately from the definition. ∎

For the proof of Theorem B, we need detailed informations about the
$\frac{1}{4}$-quasirandom finite simple groups. The infinite families of
$\frac{1}{4}$-quasirandom simple groups are

$\displaystyle\mathrm{PSL}_{d}(q)\hbox{ with
}d\in\\{2,3\\},\quad\mathrm{Sp}_{4}(q)\hbox{ with }q\hbox{ even},$
$\displaystyle G_{2}(q)\hbox{ with
}q=3(\mathrm{mod}\,6),\quad^{2}B_{2}(q^{2}),\quad^{2}G_{2}(q^{2})\,.$

The relevant informations can be recovered from [15, 24] for classical groups,
and from [17, Sec. 4] for exceptional groups (see also the Appendix). We
collect these data in Table 1.

$\dfrac{1^{1}}{1_{1_{1}}}$ $L$ | Comments | $\mathbf{D}_{0}(L)$ | $\mathbf{R}_{0}(L)$ |  $\mathbf{R}_{r}(L)$, $r\neq p$ | $\mathbf{R}_{p}(L)$
---|---|---|---|---|---
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSL}_{2}(q)$ |  $q$ even | $q-1$ | $q-1$ | $q-1$ | $2$
| $q=1\,(\mathrm{mod}\,4)$ | $\dfrac{q+1}{2}$ | $\dfrac{q+1}{2}$ | $\dfrac{q-1}{2}$ | $2$
| $q=3\,(\mathrm{mod}\,4)$ | $\dfrac{q-1}{2}$ | $\dfrac{q-1}{2}$ | $\dfrac{q-1}{2}$ | $2$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSL}_{3}(q)$ | $q\neq 2,4$ | $q(q+1)$ | $q(q+1)$ | $q^{2}+q-1$ | $3$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{Sp}_{4}(q)$ |  $q$ even | $\dfrac{1}{2}q(q-1)^{2}$ | $\dfrac{1}{2}q(q-1)^{2}$ | $\dfrac{1}{2}q(q-1)^{2}$ | $4$
$\dfrac{1^{1}}{1_{1_{1}}}$ $G_{2}(q)$ | $q=3(\mathrm{mod}\,6)$ | $\phi_{3}(q)\phi_{6}(q)$ | $\phi_{3}(q)\phi_{6}(q)$ | $\phi_{3}(q)\phi_{6}(q)-\delta_{1}$ | $7$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{2}B_{2}(q^{2})$ | $q=\sqrt{2^{2m+1}}$ | $\dfrac{\sqrt{2}}{2}q\phi_{1}(q)\phi_{2}(q)$ | $\dfrac{\sqrt{2}}{2}q\phi_{1}(q)\phi_{2}(q)$ | $\dfrac{\sqrt{2}}{2}q\phi_{1}(q)\phi_{2}(q)$ | $4$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{2}G_{2}(q^{2})$ | $q=\sqrt{3^{2m+1}}$ | $\phi_{12}(q)$ | $\phi_{12}(q)$ | $\phi_{12}(q)-\delta_{2}$ | $7$
Table 1. The $\frac{1}{4}$-quasirandom simple groups of Lie type.

We denote by $\phi_{\ell}(q)$ the $\ell$-th cyclotomic polynomial in the
variable $q$. The value of $\delta_{1}$ is $1$ if $r=2$, $q=3^{f}$, $f\geq 2$,
or $r=3$, $3$ divides $q-1$, and it is $0$ otherwise. The value of
$\delta_{2}$ is $1$ if $r=2$, and $0$ otherwise.

######  Remark 2.14.

We observe that, if $L$ is a $\frac{1}{4}$-quasirandom simple group of Lie
type, in cross-characteristic we have

$\mathbf{R}_{r}(L)\>\geq\>\mathbf{D}_{0}(L)-1.$

Moreover, we point out that the comparison between $\mathbf{R}_{0}(L)$ and
$\mathbf{R}_{r}(L)$ ($r\neq p$) can be explicitly found, for all simple groups
of Lie type, in [26, Sec. 3].

##  3\. Quasirandom groups of affine type

In this short section, we provide some highly quasirandom nonquasisimple
groups. The key tool is Lemma 3.2 below. Before giving the results, we revise
some notions from the representation theory of finite groups. Let $V$ be a
finite vector space, and let $V^{*}$ be its dual space. We remark that
$V^{*}\cong Hom(V,\mathbb{C}^{*})$. If $\phi:V\rightarrow V$ is a homomorphism
of vector spaces, then $\phi^{*}:V^{*}\rightarrow V^{*}$ is defined by

$\phi^{*}(f)\>:=\>\phi\circ f.$

Let $K$ be a finite group. If $\rho:K\rightarrow\mathrm{GL}(V)$ is a
representation of $K$, then the dual representation
$\rho^{*}:K\rightarrow\mathrm{GL}(V^{*})$ is defined by

$\rho^{*}(g)\>:=\>\rho(g^{-1})^{*}$

for every $g\in K$. It is well known that the representations $\rho$ and
$\rho^{*}$ are not isomorphic in general.

######  Lemma 3.1.

Let $V$ be a finite vector space, and $K\leqslant\mathrm{GL}(V)$. Then the
number of orbits of $K$ on $V$ equals the number of orbits of $K$ on $V^{*}$.

###### Proof.

Let $V=(\mathbb{F}_{q})^{n}$ and $g\in K$. The number of $g$-fixed points in
$V$ is $q^{\dim(Ker(g-I))}$, while the number of $g$-fixed points in $V^{*}$
is $q^{\dim(Ker((g^{-1})^{T}-I))}$, where $g^{T}$ is the transpose of $g$. Now
$\dim(Ker(g-I))$ is the multiplicity of $1$ as an eigenvalue of $g$. We remark
that the eigenvalues of $(g^{-1})^{T}$ are the eigenvalues of $g^{-1}$, which
are the inverses of the eigenvalues of $g$. In particular, the two quantities
above are equal. Since $g$ is arbitrary, the proof follows from Burnside’s
lemma, i.e. the number of orbits is equal to the average number of fixed
points. ∎

######  Lemma 3.2.

Let $G=V\rtimes K$ be a $2$-transitive affine group. Then

$\mathbf{D}_{0}(G)\>=\>\mathbf{D}_{0}(K).$

###### Proof.

Since $K$ is a quotient of $G$, it is sufficient to show that
$\mathbf{D}_{0}(G)\geq\mathbf{D}_{0}(K)$. We first notice that $K$ acts
nontrivially on $V\setminus\\{0\\}$, so $\mathbf{D}_{0}(K)\leq|V|-2$ from
Lemma 2.2. Moreover, we can identify $V^{*}$ with $\mathrm{Irr}(V)$. Let
$\pi\in\mathrm{Irr}(G)\setminus\\{1\\}$. If $\pi_{\downarrow V}$ is the
trivial representation of $V$, then $\pi\in\mathrm{Irr}(G/V)$ is an
irreducible representation of $K$. In particular,
$\dim(\pi)\geq\mathbf{D}_{0}(K)$. On the other hand, if $\pi_{\downarrow V}$
is a nontrivial representation of $V$, then, by Clifford theory, there is an
irreducible character $\theta\in\mathrm{Irr}(V)\setminus\\{1\\}$ such that
$\dim(\pi)$ is a multiple of $|K:I_{K}(\theta)|$, where $I_{K}(\theta)$ is the
inertia subgroup of $\theta$. From Lemma 3.1, $K$ acts transitively on
$\mathrm{Irr}(V)\setminus\\{1\\}$. By the orbit-stabilizer theorem, we have

$|K:I_{K}(\theta)|=|\theta^{K}|=|V|-1.$

From the discussion above, we obtain

$\dim(\pi)\geq|V|-1>\mathbf{D}_{0}(K).$

Since $\pi\in\mathrm{Irr}(G)\setminus\\{1\\}$ is arbitrary, we conclude that
$\mathbf{D}_{0}(G)\geq\mathbf{D}_{0}(K)$ as desired. ∎

######  Example 3.3.

Let $q\geq 4$ range among the powers of $2$, and let
$G_{q}=(\mathbb{F}_{q})^{4}\rtimes\mathrm{Sp}_{4}(q)$. Since
$\mathrm{Sp}_{4}(q)$ is transitive on $(\mathbb{F}_{q})^{4}\setminus\\{0\\}$,
from Lemma 3.2 we have

$\begin{split}\bm{\varepsilon}(G_{q})&=\frac{\log\mathbf{D}_{0}(\mathrm{Sp}_{4}(q))}{\log|G_{q}|}\\\
&=\frac{\log\left(\dfrac{q(q-1)^{2}}{2}\right)}{\log(q^{8}(q^{4}-1)(q^{2}-1))}.\end{split}\,$

A direct computation shows that this value is more than $\frac{1}{5}$ for
$q\geq 64$, and it lies between $\frac{3}{14}-\frac{1}{\log_{2}q}$ and
$\frac{3}{14}$, for all $q$. In particular,
$\lim_{q\rightarrow+\infty}\bm{\varepsilon}(G_{q})=\left(\frac{3}{14}\right)^{-}$.
Similarly, if $q$ is a prime power and
$H_{q}=(\mathbb{F}_{q})^{2}\rtimes\mathrm{SL}_{2}(q)$, then from Lemma 3.2 we
have

$\bm{\varepsilon}(H_{q})=\frac{\log\mathbf{D}_{0}(\mathrm{SL}_{2}(q))}{\log|H_{q}|}.$

A direct computation shows that $\bm{\varepsilon}(H_{q})$ lies between
$5^{-1}-q^{-1}$ and $5^{-1}$ for all $q$, so in particular
$\lim_{q\rightarrow+\infty}\bm{\varepsilon}(H_{q})=\left(\frac{1}{5}\right)^{-}$.

##  4\. Proof of the main theorems

###  4.1. Proof of Theorem A

We immediately prove the second part of the theorem. We restate it as follows.

######  Lemma 4.1.

Fix $\varepsilon,\delta>0$, and let $G$ be a perfect group. Suppose that
$G/Sol(G)$ is $\varepsilon$-quasirandom, and that
$|G/Sol(G)|\geq|G|^{\delta}$. If $|G|$ is sufficiently large with respect to
$\varepsilon$ and $\delta$, then $G$ is
$\frac{\varepsilon\delta}{3}$-quasirandom.

###### Proof.

By [8, Lemma 4.10], we have

$\mathbf{D}_{0}(G)\>\geq\>c\,\mathbf{D}_{0}(G/Sol(G))^{1/2},$

where $c$ is an absolute constant. Looking back at [19], we check that
$c=10^{-10}$ works. It follows that

$|G|^{\bm{\varepsilon}(G)}\>\geq\>10^{-10}|G/Sol(G)|^{\bm{\varepsilon}(G/Sol(G))/2},$

and passing to the logarithms,

$\bm{\varepsilon}(G)\>\geq\>\frac{\bm{\varepsilon}(G/Sol(G))}{2}\cdot\frac{\log|G/Sol(G)|}{\log|G|}-\frac{10\log
10}{\log|G|}.$

The proof follows. ∎

The main idea behind the other direction of Theorem A is the following. Under
the hypothesis that $Sol(G)=1$, we prove that $G=F^{*}(G)$, the generalized
Fitting subgroup of $G$. If this is not the case, then $G/F^{*}(G)$ has a
nontrivial simple quotient $L$. We use the quasirandomness of $L$ to obtain an
upper bound on $|G|$, while Bender’s theorem and other considerations provide
a lower bound on $|F^{*}(G)|$. These inequalities fight each other, giving the
desired contradiction. A similar argument will be used in a portion of the
proof of Theorem B. Going into details, we start reporting the Schreier
conjecture, which is now a theorem as a consequence of the Classification of
the Finite Simple Groups.

######  Theorem 4.2 (Schreier conjecture).

If $L$ is a finite simple group, then the group of the outer automorphisms
$\mathrm{Out}(L)$ is solvable.

The following two observations concern sections of finite groups.

######  Remark 4.3.

Let $N\lhd G$, and suppose that a section $H_{0}/N_{0}\cong L$ of $G$ is
simple. Then $N\subseteq N_{0}$, or $NN_{0}=H_{0}$. In the first case $L$
appears as a section of $G/N$, while in the second case $L$ appears as a
section of $N$.

######  Lemma 4.4.

Let $\Omega$ be a finite set, and let $N\lhd H\leqslant\mathrm{Sym}(\Omega)$.
If $H/N\cong L$ is simple, then $\mathrm{Sym}(\Omega)$ has a subgroup
isomorphic to $L$.

###### Proof.

Let $|\Omega|=n$, $x\in\Omega$, and work by induction on $n$. Let $H_{x}$ be
stabilizer of $x$. We claim that $NH_{x}/N$ is a corefree subgroup of $H/N$ of
index at most $n$. First,

$|(H/N):(NH_{x}/N)|=|H:NH_{x}|\leq|H:H_{x}|\leq n.$

Now, if $NH_{x}$ is neither $N$ nor $H$, then the proof is finished by the
fact that $H/N$ is simple. In the first case $|H/N|\leq n$, and the proof
follows by the Cayley embedding theorem. If $NH_{x}=H$, then $H_{x}/H_{x}\cap
N\cong H/N\cong L$, hence by induction $\mathrm{Sym}(\Omega\setminus\\{x\\})$
and so $\mathrm{Sym}(\Omega)$ has a subgroup isomorphic to $L$, as desired. ∎

In the following remark, we discuss the asymptotic behaviour of
$\mathbf{D}_{0}(L)$ and $\bm{\varepsilon}(L)$, when $L$ is a finite simple
group, and $|L|\rightarrow+\infty$. Of course, we do not care about the
sporadic simple groups in this context.

######  Remark 4.5.

For $n\geq 6$,

$\mathbf{D}_{0}(\mathrm{Alt}(n))=n-1,\quad\hbox{and}\quad\bm{\varepsilon}(\mathrm{Alt}(n))=\frac{\log(n-1)}{\log(n!/2)}.$

In particular, for $L=\mathrm{Alt}(n)$, we have

$\mathbf{D}_{0}(L)\sim\frac{\log|L|}{\log\log|L|},\quad\hbox{and}\quad\bm{\varepsilon}(L)\sim\frac{\log\log|L|}{\log|L|}$

when $|L|\rightarrow+\infty$. These are the less quasirandom among the
nonabelian finite simple groups. If $L=L_{d}(q)$ is a finite simple group of
Lie type, then it is easy to check from the Appendix that

$q^{10^{-1}d}\>\leq\>\mathbf{D}_{0}(L_{d}(q))\>\leq\>q^{10d},$

and

$10^{-1}d^{-1}\>\leq\>\bm{\varepsilon}(L_{d}(q))\>\leq\>10d^{-1}.$

In particular, if $L=L_{d}(q)$ and $q$ is fixed, then $\mathbf{D}_{0}(L)$ is
comparable with $c^{\sqrt{\log|L|}}$, while $\bm{\varepsilon}(L)$ is
comparable with $\frac{c}{\sqrt{\log|L|}}$.

###### Proof of Theorem A.

After Lemma 4.1, we have only to prove the first part of the theorem. Fix
$\varepsilon>0$. From Corollary 2.3(i), it is clear that
$|G/Sol(G)|\geq|G|^{\varepsilon}$. Moreover, $G/Sol(G)$ is again
$\varepsilon$-quasirandom. Up to replacing $G$ with $G/Sol(G)$, we can assume
that $G$ has a trivial solvable radical. Now it is well known that the
generalized Fitting subgroup $F=F^{*}(G)$ coincides with the socle of $G$, and
it is the direct product of nonabelian simple groups $T_{i}$’s. Let
$F=\prod_{i}(T_{i})^{n_{i}}$, where $n_{i}\geq 1$ for each $i$. Moreover, as
$\mathbf{C}_{G}(F)\subseteq F$ [1, (31.13)], we have
$\mathbf{C}_{G}(F)=\mathbf{Z}(F)=1$. It follows that $G$ can be embedded as a
subgroup of

$\mathrm{Aut}(F)\>\cong\>\prod_{i}\mathrm{Aut}(T_{i})^{n_{i}}\rtimes\mathrm{Sym}(n_{i}).$

In particular, all the composition factors of $G/F$ lie as sections of one
among $\mathrm{Out}(T_{i})$ or $\mathrm{Sym}(n_{i})$, for some $i$. We claim
that $G=F$. Otherwise, it is easy to see that $G/F$ has a simple quotient $L$
which is $\varepsilon$-quasirandom. By the definition of quasirandom degree,
we have

(4.1) $|G|\>\leq\>\mathbf{D}_{0}(L)^{1/\varepsilon}.$

So, if $\mathbf{D}_{0}(L)$ is bounded, then $|G|$ is bounded. Let
$n=\max_{i}n_{i}$, so that $|F|\geq 60^{n}$. From Remark 4.3 and Theorem 4.2,
$L$ has to appear as a section of $\mathrm{Alt}(n)$. From Lemma 4.4,
$\mathrm{Sym}(n)$ has a subgroup isomorphic to $L$. From Lemma 2.2 we obtain
$\mathbf{D}_{0}(L)\leq n$, and so

$|F|\>\geq\>60^{\mathbf{D}_{0}(L)}.$

When $\mathbf{D}_{0}(L)$ is sufficiently large, this gives a contradiction to
(4.1). We have proven that $G/Sol(G)=F^{*}(G/Sol(G))$, so $G/Sol(G)$ is an
$\varepsilon$-quasirandom direct product of finite simple groups, say
$G/Sol(G)=\prod_{i}(T_{i})^{n_{i}}$. From Remark 4.5, the $T_{i}$’s are all
simple groups of Lie type. Let $N=\sum_{i}n_{i}$. From Corollary 2.9, we have
$\varepsilon\leq\mathbf{D}_{0}(G/Sol(G))\leq N^{-1}$, so that
$N\leq\varepsilon^{-1}$. Moreover, each block $(T_{i})^{n_{i}}$ has to be
$\varepsilon$-quasirandom as a quotient of $G$. From Corollary 2.9 and Remark
4.5, we have

$\varepsilon\>\leq\>\bm{\varepsilon}((T_{i})^{n_{i}})\>=\>\frac{\bm{\varepsilon}(T_{i})}{n_{i}}\>\leq\>\frac{10}{n_{i}\,rank(T_{i})},$

so that $n_{i}\,rank(T_{i})\leq 10\varepsilon^{-1}$ for each $i$. ∎

######  Remark 4.6.

An attentive reader will have noticed that a bound of the type
$\mathbf{D}_{0}(G)\geq c\log|G|$ is strong enough to give that $G/Sol(G)$ is
the direct product of nonabelian finite simple groups.

It is natural to ask whether the condition $|G/Sol(G)|\geq|G|^{\varepsilon}$
is actually superflous in the second part of Theorem A, as it may be implied
by the quasirandomness of the sole $G/Sol(G)$. The answer is no, as it can
even happen that $|G/Sol(G)|$ is bounded: it is enough to consider the perfect
deleted permutation module $(C_{n})^{4}\rtimes\mathrm{Alt}(5)$ when $n$ is
large. The following example, where $|G/Sol(G)|$ is unbounded but too small,
is due to S. Eberhard.

######  Example 4.7.

Let $p\geq 5$ be a prime, and $d\geq 2$. We define $G_{d}$ as the group of the
$2d\times 2d$ upper triangular matrices whose diagonal entries are identical
matrices in $\mathrm{SL}_{2}(p)$, and the upper entries are arbitrary $2\times
2$ matrices over $\mathbb{F}_{p}$. For instance,

$G_{3}\>=\>\left(\begin{array}[]{ccc}g&*&*\\\ 0&g&*\\\ 0&0&g\\\
\end{array}\right),$

where $g\in\mathrm{SL}_{2}(p)$, and $*$ is arbitrary. We have

$|G_{d}|=\frac{1}{2}(p^{3}-p)p^{2d(d-1)}\geq p^{d^{2}}.$

It can be proven that $G_{d}$ is perfect, and its solvable radical is the
subgroup where $g\in\mathbf{Z}(\mathrm{SL}_{2}(p))$ is a scalar matrix. In
particular, $G_{d}/Sol(G_{d})$ is isomorphic to $\mathrm{PSL}_{2}(p)$, which
is $0.34$-quasirandom for large $p$, but its cardinality is less than $p^{3}$.

###  4.2. Proof of Theorem B

We first prove the shallow version of Theorem B. This is a nice application of
(2.1).

###### Proof of Corollary D.

From the data collected in the Appendix, we note that, among the finite simple
groups, $J_{1}$ and $O^{\prime}N$ are the only ones whose quasirandom degree
is at least $\frac{1}{3}$. Suppose that $G$ is of minimal cardinality among
the finite groups satisfying $\bm{\varepsilon}(G)\geq\frac{1}{3}$ that are not
isomorphic to either $J_{1}$ or $O^{\prime}N$. Of course, there exists a
nontrivial proper normal subgroup $N$ of $G$. We have
$\bm{\varepsilon}(G/N)\geq\frac{1}{3}$, and $G/N$ is isomorphic to either
$J_{1}$ or $O^{\prime}N$. In the former case, from (2.1), we have

$|N|\leq\frac{\mathbf{D}_{0}(J_{1})^{1/\bm{\varepsilon}(G)}}{|J_{1}|}\leq\frac{56^{3}}{175\,560}\approx
1.00031.$

So $N=1$, a contradiction. Now suppose $G/N\cong O^{\prime}N$. From (2.1),

$|N|\leq\frac{\mathbf{D}_{0}(O^{\prime}N)^{1/\bm{\varepsilon}(G)}}{|O^{\prime}N^{\prime}|}\leq\frac{10\,944^{3}}{460\,815\,505\,920}\approx
2.84446,$

so that $N$ is the cyclic group of order $2$. Since the only nonidentity
element of $N$ has to be fixed by conjugation, $N$ is central in $G$. In
particular, $G$ is a perfect central extension of $O^{\prime}N$ by $N$. On the
other hand, the Schur multiplier of $O^{\prime}N$ has cardinality $3$, and
such an extension does not exist. ∎

The following observation is not really needed in the proof of Theorem B, but
it makes the structure of $G$ more transparent.

######  Lemma 4.8.

Suppose that $\bm{\varepsilon}(G)\geq\frac{1}{5}$, or that
$\bm{\varepsilon}(G)\geq\frac{1}{6}$ and $|G|\geq 2\cdot 10^{24}$. Then $G$
has a unique maximal normal subgroup.

###### Proof.

From Corollary D, for every finite group $G$ we have

$\bm{\varepsilon}(G)\leq\max\left\\{\bm{\varepsilon}(J_{1}),\bm{\varepsilon}(O^{\prime}N)\right\\}=\bm{\varepsilon}(O^{\prime}N)<\frac{2}{5},$

while $\bm{\varepsilon}(G)<\frac{1}{3}$ if $G$ is not isomorphic to $J_{1}$ or
$O^{\prime}N$. Suppose that $M_{1}$ and $M_{2}$ are two distinct maximal
normal subgroups of the group $G$. Since $M_{1}M_{2}/M_{1}$ is a normal
subgroup of the simple group $G/M_{1}$, we obtain that $G=M_{1}M_{2}$. So
$M_{1}/(M_{1}\cap M_{2})$ and $M_{2}/(M_{1}\cap M_{2})$ are normal subgroups
of $G/(M_{1}\cap M_{2})$ with trivial intersection. It follows that

$G/(M_{1}\cap M_{2})=M_{1}/(M_{1}\cap M_{2})\times M_{2}/(M_{1}\cap
M_{2})\cong G/M_{2}\times G/M_{1}.$

Lemma 2.8 yields

$\bm{\varepsilon}(G)\leq\bm{\varepsilon}((G/M_{2})\times(G/M_{1}))<\frac{1}{5},$

and $\bm{\varepsilon}(G)<\frac{1}{6}$ if neither $J_{1}$ or $O^{\prime}N$
appears as a quotient of $G$. If one among $J_{1}$ or $O^{\prime}N$ appears as
a quotient, then

$|G|\leq\mathbf{D}_{0}(G)^{6}<\mathbf{D}_{0}(O^{\prime}N)^{6}=10\,944^{6}<2\cdot
10^{24},$

because $\mathbf{D}_{0}(J_{1})<\mathbf{D}_{0}(O^{\prime}N)$. ∎

We are ready to prove Theorem B. This proof has a number of cases, the most
difficult, which we treat in the end, being the following. We have an abelian
minimal normal subgroup $N$ of $G$ such that $G/N$ is quasisimple, and the
action of $G/N$ on $N$ by conjugation provides a projective modular
representation of the simple quotient of $G/N$, say $L$. The key point is that
the (complex, linear) quasirandomness of $L$ controls also the degrees of the
modular projective representations. This gives a lower bound on $|N|$, which
we put against the upper bound given by (2.1). We start with the details.

######  Remark 4.9.

The veracity of Theorem B has been checked with a computer for all the finite
groups of order up to $2\cdot 10^{6}$, using the library PerfectGroups in the
GAP System [10].

Let $G$ be a counterexample to Theorem B whose order is minimal. In
particular, $\bm{\varepsilon}(G)\geq\frac{1}{5}$ and $G$ is not quasisimple.
By Lemma 4.8, $G$ has a unique maximal normal subgroup and cannot be written
as a direct product of nontrivial groups. Therefore, using also Lemma 2.12, we
find a chain

$1\>\lhd\>N\>\lhd\>M\>\lhd\>G$

where $N$ is the unique minimal normal subgroup of $G$, and $M$ is the unique
maximal normal subgroup of $G$. It follows that $G/M$ is isomorphic to a
simple group $L$ satisfying $\bm{\varepsilon}(L)>\frac{1}{5}$, and that
$N\cong T^{n}$ is the direct product of isomorphic simple groups. We
distinguish two cases: either $G/N$ is quasisimple or not. Let us start from
the latter.

$G/N$ is not quasisimple. We have $\bm{\varepsilon}(G/N)>\frac{1}{5}$, and, by
the minimality of $G$, we are in one of the two cases:

  1. $(a)$

$G/N\cong(\mathbb{F}_{3})^{3}\rtimes\mathrm{SL}_{3}(3)$;

  2. $(b)$

$G/N$ is a perfect central extension of
$(\mathbb{F}_{q})^{4}\rtimes\mathrm{Sp}_{4}(q)$, $q=2^{f}$, $f\geq 6$.

If we are in case $(a)$, using (2.1) we obtain

$|N|\leq\frac{\mathbf{D}_{0}((\mathbb{F}_{3})^{3}\rtimes\mathrm{SL}_{3}(3))^{5}}{|(\mathbb{F}_{3})^{3}\rtimes\mathrm{SL}_{3}(3)|}=\frac{12^{5}}{151\,632}\approx
1,64.$

Hence $N$ is trivial, a contradiction.
If we are in case $(b)$, we remark that $G/M\cong\mathrm{Sp}_{4}(q)$ and
$\bm{\varepsilon}(G/N)<\frac{3}{14}$. Let $N\lhd N_{0}\lhd M$ such that
$G/N_{0}\cong(\mathbb{F}_{q})^{4}\rtimes\mathrm{Sp}_{4}(q)$,
$N_{0}/N\subseteq\mathbf{Z}(G/N)$. First suppose that $N$ is abelian. If
$N\subseteq\mathbf{Z}(G)$, then $N_{0}\subseteq\mathbf{Z}(G)$ by Lemma 2.11.
Thus $G$ is a perfect central extension of
$(\mathbb{F}_{q})^{4}\rtimes\mathrm{Sp}_{4}(q)$, against the assumptions. If
$N\nsubseteq\mathbf{Z}(G)$, then by Lemma 2.7,

$\frac{3}{14}>\bm{\varepsilon}(G/N)>\frac{\bm{\varepsilon}(G)}{1-\bm{\varepsilon}(G)}\geq\frac{1}{4}.$

This is impossible. It remains the case where $N$ is nonabelian, say $N=T^{n}$
where $T$ is a nonabelian finite simple group. We argue in a similar way as in
Theorem A: since $N$ is the unique minimal normal subgroup of $G$, we have
$\mathbf{C}_{G}(N)=1$ and the same argument works. We have

(4.2) $|G|\>\leq\>\mathbf{D}_{0}(\mathrm{Sp}_{4}(q))^{5}.$

Considering the embedding of $G$ into $\mathrm{Aut}(T^{n})$, and arguing as
before, we obtain $\mathbf{D}_{0}(\mathrm{Sp}_{4}(q))\leq n$. Since $|N|\geq
60^{n}$, and $60^{x}>x^{5}$ for every $x\geq 1$, this contradicts (4.2).

$G/N$ is quasisimple. Let $C=\mathbf{C}_{G}(N)$. We distinguish three cases.

Suppose that $C=G$. Here $N$ is central and $G$ is quasisimple by Lemma 2.10,
a contradiction.

Suppose that $C=1$. Here $N=T^{n}$ is the product of nonabelian finite simple
groups, and $G$ is embedded into $\mathrm{Aut}(T^{n})$. Let $G/M=L$. Arguing
again as in the proof of Theorem A, we obtain

$|G|\leq\mathbf{D}_{0}(L)^{5},\hskip 14.22636pt\mbox{and}\hskip
14.22636pt|N|\geq 60^{\mathbf{D}_{0}(L)}.$

This is impossible for any value of $\mathbf{D}_{0}(L)$.

Suppose that $N\subseteq C\subseteq M$. This case will take up the rest of the
proof. First, $N$ is an elementary abelian noncentral subgroup, and Lemma 2.7
provides

$\bm{\varepsilon}(L)\geq\bm{\varepsilon}(G/N)>\frac{1}{4}.$

Moreover, the action of $G/N$ on $N$ by conjugation provides a projective
modular representation of $L$ (recall that $G/N$ is quasisimple). As already
explained, the key idea is that the quasirandomness of $G/N$ gives a lower
bound on $|N|$, which we put against the upper bound given by (2.1). We
observe that $\mathrm{Alt}(5)$ and $\mathrm{Alt}(6)$ are
$\frac{1}{4}$-quasirandom, but if one among them appears as $L$, then

$|G|\leq\mathbf{D}_{0}(L)^{5}\leq 5^{5}=3\,125,$

and we can easily work wit a computer (see Remark 4.9). One last time, we
divide the discussion into three cases:

  1. $(i)$

$L$ is a simple group of Lie type over a field of characteristic $p$, and
$G/N$ induces a projective modular representation of $L$ in cross-
characteristic;

  2. $(ii)$

$L$ is a simple group of Lie type over a field of characteristic $p$, and
$G/N$ induces a projective modular representation of $L$ in natural
characteristic;

  3. $(iii)$

$L$ is a sporadic simple group.

Let $L$ be as described in $(i)$. We remark that $|L|>\mathbf{D}_{0}(L)^{3}$
by Corollary D. Hence, by (2.1),

$|N|\leq|M|\leq\frac{\mathbf{D}_{0}(L)^{5}}{|L|}<\mathbf{D}_{0}(L)^{2}.$

From Remark 2.14, and the definition of $\mathbf{R}_{r}(L)$ with $r\neq p$ a
prime, we obtain

$2^{\mathbf{D}_{0}(L)-1}\leq
2^{\mathbf{R}_{r}(L)}\leq|N|<\mathbf{D}_{0}(L)^{2}.$

The above inequality is possible only if $\mathbf{D}_{0}(L)\leq 6$, which
gives

$|G|\leq\mathbf{D}_{0}(L)^{5}\leq 6^{5}=7\,776.$

This case can be handled computationally.

Let $L$ be as described in $(ii)$. We first deal with
$L\cong\mathrm{Sp}_{4}(q)$ with $q$ even, $q\geq 4$. Since the Schur
multiplier is trivial, we have $N=M$. By (2.1), we find

$\begin{split}|N|&\leq\frac{\mathbf{D}_{0}(\mathrm{Sp}_{4}(q))^{5}}{|\mathrm{Sp}_{4}(q)|}\\\
&\leq\frac{(q^{2}-1)^{5}(q^{2}-q)^{5}}{2^{5}(q+1)^{5}}\cdot\frac{1}{q^{4}(q^{4}-1)(q^{2}-1)}\\\
&<q^{5}.\end{split}$

On the other hand, by Lemma 2.13 and Table 1,

$|N|\geq q^{4}.$

So $|N|=q^{4}$, and we are in the situation of Theorem Bb.
The argument to deal with the other cases is the same, using (2.1), Lemma 2.13
and Table 1. When $L\cong\mathrm{PSL}_{2}(q)$,

$|N|\leq\frac{\mathbf{D}_{0}(\mathrm{PSL}_{2}(q))^{5}}{|\mathrm{PSL}_{2}(q)|}\leq\frac{(q-1)^{5}}{q(q^{2}-1)}<q^{2}.$

On the other hand,

$|N|\geq q^{2},$

which provides a contradiction. If $L\cong\mathrm{PSL}_{3}(q)$, $q\geq 4$, we
obtain

$q^{3}\leq|N|\leq\frac{q^{5}(q+1)^{5}}{q^{3}(q^{3}-1)(q^{2}-1)(q-1)}<q^{3}.$

When $L\cong G_{2}(q)$, $q=3(\mathrm{mod}\,6)$, we have

$q^{7}\leq|N|\leq\frac{(q+1)^{5}(q^{2}-q+1)^{5}}{q^{6}(q^{6}-1)(q^{2}-1)}<q^{7}.$

For ${}^{2}B_{2}(q^{2})$,

$q^{8}\leq|N|\leq\frac{q^{5}(q^{2}-1)^{5}}{2^{5/2}q^{4}(q^{4}-1)(q^{2}-1)}<q^{5}.$

Finally, for ${}^{2}G_{2}(q^{2})$,

$q^{14}\leq|N|\leq\frac{(q^{4}-q^{2}+1)^{5}}{q^{6}(q^{6}-1)(q^{2}-1)}<q^{7}.$

In all these four cases, the chain of inequalities is impossible.

Let $L$ be as described in $(iii)$. Since $\bm{\varepsilon}(L)>\frac{1}{4}$,
the possibilities for $L$ are

$M_{11},\quad J_{1},\quad J_{3},\quad^{2}F_{2}(4)^{\prime},\quad O^{\prime}N.$

Observe that $M_{11}$, $J_{1}$ and ${}^{2}F_{2}(4)^{\prime}$ admit no central
perfect extensions, while the perfect central extensions of $J_{3}$ and
$O^{\prime}N$ are not $\frac{1}{5}$-quasirandom. Therefore $N=M$ is the unique
normal subgroup of $G$, and $N$ can be thought as the vector space of a
nontrivial modular representation of $L$. For each sporadic group, we use [14]
to obtain a lower bound on $|N|$, and we compare the result with (2.1). For
$L\cong M_{11}$, we have

$3^{5}\leq|N|\leq\frac{10^{5}}{|M_{11}|}\leq 13;$

For $L\cong J_{1}$,

$2^{20}\leq|N|\leq\frac{56^{5}}{|J_{1}|}\leq 3\,138;$

For $L\cong J_{3}$,

$3^{18}\leq|N|\leq\frac{85^{5}}{|J_{3}|}\leq 89;$

For $L\cong\>^{2}F_{2}(4)^{\prime}$,

$2^{26}\leq|N|\leq\frac{104^{5}}{|^{2}F_{2}(4)^{\prime}|}\leq 678;$

Finally, for $L\cong O^{\prime}N$,

$3^{154}\leq|N|\leq\frac{10\,944^{5}}{|O^{\prime}N|}\leq 10^{10}.$

These contradictions conclude the proof of Theorem B.

## Appendix: Quasirandom degree of finite simple groups

We already discussed the alternating groups in Remark 4.5. In particular, we
observed that they are the less quasirandom among the nonabelian finite simple
groups.
In the following tables, we collect the values $\mathbf{D}_{0}(L)$ and
$\bm{\varepsilon}(L)$ when $L$ is a finite simple group of Lie type or a
sporadic simple group. For a group of Lie type $L_{d}(q)$, we fix $d$ and make
$q$ go to infinity. The case where $L$ is of exceptional type is discussed in
detail by Lübeck [17]. So let $L$ be a classical group of Lie type. In [27],
Tiep and Zalesskii computed the minimal dimension of a projective complex
irreducible representation of $L$, which we denote by $\mathbf{R}_{0}(L)$. See
also [18]. In Table 2, we use these informations to record $\mathbf{D}_{0}(L)$
for the simple classical groups. We remark that
$\mathbf{R}_{0}(L)<\mathbf{D}_{0}(L)$ holds in some cases, for example for
some symplectic groups in odd characteristic.

$\dfrac{1^{1}}{1_{1_{1}}}$ $L$ | Comments | $\mathbf{D}_{0}(L)$
---|---|---
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSL}_{d}(q)$ |  $d=2$, $q$ even | $q-1$
|  $d=2$, $q=1\,(\mathrm{mod}\,4)$ | $\dfrac{q+1}{2}$
|  $d=2$, $q=3\,(\mathrm{mod}\,4)$ | $\dfrac{q-1}{2}$
|  $d\geq 3$, $(d,q)\neq(3,2),(4,2),(4,3)$ | $\dfrac{q^{d}-q}{q-1}$
|  $d=3$, $q=2$ | $3$
|  $d=4$, $q=2$ | $7$
|  $d=4$, $q=3$ | $26$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSU}_{d}(q)$ |  $d\geq 3$ odd | $\dfrac{q^{d}-q}{q+1}$
|  $d\geq 4$ even, $(d,q)\neq(4,2)$ | $\dfrac{q^{d}-1}{q+1}\leq\mathbf{D}_{0}(L)\leq\dfrac{q^{d}+q}{q+1}$
|  $d=4$, $q=2$ | $5$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSp}_{2d}(q)$ |  $d\geq 2$, $q$ even | $\dfrac{(q^{d}-1)(q^{d}-q)}{2(q+1)}$
|  $d\geq 2$, $q^{d}=1\,(\mathrm{mod}\,4)$ | $\dfrac{q^{d}+1}{2}$
|  $d\geq 2$, $q^{d}=3\,(\mathrm{mod}\,4)$ | $\dfrac{q^{d}-1}{2}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\Omega_{2d+1}(q)$ |  $d\geq 3$, $q\neq 3$ and $2(q^{2}-1)\nmid q^{2d}-1$ | $\dfrac{q^{2d}-1}{q^{2}-1}$
|  $d\geq 3$, $q=3$ or $2(q^{2}-1)\mid q^{2d}-1$ | $\dfrac{(q^{d}-1)(q^{d}-q)}{2(q+1)}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{P}\Omega^{-}_{2d}(q)$ | $d\geq 4$ | $\dfrac{(q^{d}+1)(q^{d-1}-q)}{q^{2}-1}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{P}\Omega^{+}_{2d}(q)$ |  $d\geq 4$, $q\neq 2,3$ | $\dfrac{(q^{d}-1)(q^{d-1}+q)}{q^{2}-1}$
|  $d=4$, $q=2$ | $28$
|  $d\geq 5$, $q=2$ or $d\geq 4$, $q=3$ | $\dfrac{(q^{d}-1)(q^{d-1}-1)}{q^{2}-1}$
Table 2. $\mathbf{D}_{0}(L)$ for simple classical groups.

In Tables 3, 4, and 5, we collect the asymptotic quasirandom degrees of the
finite simple groups of Lie type, and the quasirandom degrees of the sporadic
simple groups [7]. We remark that, after $(\mathrm{PSL}_{2}(q))_{q\geq 4}$,
which is asymptotically $\frac{1}{3}$-quasirandom, the most quasirandom
families of finite simple groups are $(\mathrm{Sp}_{4}(q))_{q\,even}$ and the
Suzuki groups $(^{2}B_{2}(q^{2}))_{q\geq 8}$, whose quasirandom degrees are
asymptotically $\frac{3}{10}$.

$\dfrac{1^{1}}{1_{1_{1}}}$ $L$ | Comments | $\sim\log_{q}|L|$ | $\sim\log_{q}\mathbf{D}_{0}(L)$ | $\lim\limits_{q\rightarrow+\infty}\bm{\varepsilon}(L)$
---|---|---|---|---
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSL}_{d}(q)$ | $d\geq 2$ | $d^{2}-1$ | $d-1$ | $\dfrac{1}{d+1}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSU}_{d}(q)$ | $d\geq 3$ | $d^{2}-1$ | $d-1$ | $\dfrac{1}{d+1}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{PSp}_{2d}(q)$ |  $d\geq 2$, $q$ even | $2d^{2}+d$ | $2d-1$ | $\dfrac{2d-1}{2d^{2}+d}$
|  $d\geq 2$, $q$ odd | $2d^{2}+d$ | $d$ | $\dfrac{1}{2d+1}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\Omega_{2d+1}(q)$ |  $d\geq 3$, $q$ odd | $2d^{2}+d$ | $2d-2$ | $\dfrac{2d-2}{2d^{2}+d}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $\mathrm{P}\Omega^{\pm}_{2d}(q)$ | $d\geq 4$ | $2d^{2}-d$ | $2d-3$ | $\dfrac{2d-3}{2d^{2}-d}$
Table 3. Asymptotic quasirandom degree of simple classical groups. $\dfrac{1^{1}}{1_{1_{1}}}$ $L$ | Comments | $\sim\log_{q}|L|$ | $\sim\log_{q}\mathbf{D}_{0}(L)$ | $\lim\limits_{q\rightarrow+\infty}\bm{\varepsilon}(L)$
---|---|---|---|---
$\dfrac{1^{1}}{1_{1_{1}}}$ $E_{6}(q)$ |  | $78$ | $11$ | $\dfrac{11}{78}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $E_{7}(q)$ |  | $133$ | $17$ | $\dfrac{17}{133}$
$\dfrac{c1^{1}}{1_{1_{1}}}$ $E_{8}(q)$ |  | $248$ | $29$ | $\dfrac{29}{248}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $F_{4}(q)$ |  $q$ even | $52$ | $11$ | $\dfrac{11}{52}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $F_{4}(q)$ |  $q$ odd | $52$ | $8$ | $\dfrac{2}{13}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $G_{2}(q)$ | $q\neq 3\,(\mathrm{mod}\,6)$ | $14$ | $3$ | $\dfrac{3}{14}$
$\dfrac{1^{1}}{1_{1_{1}}}$ $G_{2}(q)$ | $q=3\,(\mathrm{mod}\,6)$ | $14$ | $4$ | $\dfrac{2}{7}$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{2}E_{6}(q^{2})$ |  | $78$ | $11$ | $\dfrac{11}{78}$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{3}D_{4}(q^{3})$ |  | $28$ | $5$ | $\dfrac{5}{28}$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{2}F_{4}(q^{2})$ | $q=\sqrt{2^{2m+1}}$ | $52$ | $11$ | $\dfrac{11}{52}$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{2}B_{2}(q^{2})$ | $q=\sqrt{2^{2m+1}}$ | $10$ | $3$ | $\dfrac{3}{10}$
$\dfrac{1^{1}}{1_{1_{1}}}$ ${}^{2}G_{2}(q^{2})$ | $q=\sqrt{3^{2m+1}}$ | $14$ | $4$ | $\dfrac{2}{7}$
Table 4. Asymptotic quasirandom degree of simple exceptional groups. $\dfrac{1^{1}}{1_{1_{1}}}$ $L$ | $|L|$ | $\mathbf{D}_{0}(L)$ | $\bm{\varepsilon}(L)$ | $L$ | $|L|$ | $\mathbf{D}_{0}(L)$ | $\bm{\varepsilon}(L)$
---|---|---|---|---|---|---|---
$\dfrac{1^{1}}{1_{1_{1}}}$ $M_{11}$ | $7\,920$ | $10$ | $\approx 0.2565$ | $Fi_{24}$ | $125\,520\,570\cdot 10^{16}$ | $8\,671$ | $\approx 0.1635$
$\dfrac{1^{1}}{1_{1_{1}}}$ $M_{12}$ | $95\,040$ | $11$ | $\approx 0.2093$ | $HS$ | $44\,352\,000$ | $22$ | $\approx 0.1756$
$\dfrac{1^{1}}{1_{1_{1}}}$ $M_{22}$ | $443\,520$ | $21$ | $\approx 0.2342$ | $McL$ | $898\,128\,000$ | $22$ | $\approx 0.1500$
$\dfrac{1^{1}}{1_{1_{1}}}$ $M_{23}$ | $10\,200\,960$ | $22$ | $\approx 0.1916$ | $He$ | $4\,030\,387\,200$ | $51$ | $\approx 0.1778$
$\dfrac{1^{1}}{1_{1_{1}}}$ $M_{24}$ | $244\,823\,040$ | $23$ | $\approx 0.1624$ | $Ru$ | $145\,926\,144\cdot 10^{3}$ | $378$ | $\approx 0.2309$
$\dfrac{1^{1}}{1_{1_{1}}}$ $J_{1}$ | $175\,560$ | $56$ | $\approx 0.3334$ | $Suz$ | $448\,345\,497\cdot 10^{3}$ | $143$ | $\approx 0.1850$
$\dfrac{1^{1}}{1_{1_{1}}}$ $J_{2}$ | $604\,800$ | $14$ | $\approx 0.1924$ | $O^{\prime}N$ | $460\,815\,505\cdot 10^{3}$ | $10\,944$ | $\approx 0.3464$
$\dfrac{1^{1}}{1_{1_{1}}}$ $J_{3}$ | $50\,232\,960$ | $85$ | $\approx 0.2506$ | $HN$ | $273\,030\,912\cdot 10^{6}$ | $133$ | $\approx 0.1472$
$\dfrac{1^{1}}{1_{1_{1}}}$ $J_{4}$ | $867\,755\,710\cdot 10^{11}$ | $1\,333$ | $\approx 0.1568$ | $Ly$ | $517\,651\,790\cdot 10^{8}$ | $2\,480$ | $\approx 0.2031$
$\dfrac{1^{1}}{1_{1_{1}}}$ $Co_{3}$ | $495\,766\,656\cdot 10^{3}$ | $23$ | $\approx 0.1165$ | $Th$ | $907\,459\,438\cdot 10^{8}$ | $248$ | $\approx 0.1413$
$\dfrac{1^{1}}{1_{1_{1}}}$ $Co_{2}$ | $423\,054\,213\cdot 10^{5}$ | $23$ | $\approx 0.1000$ | $B$ | $415\,478\,148\cdot 10^{24}$ | $4\,371$ | $\approx 0.1083$
$\dfrac{1^{1}}{1_{1_{1}}}$ $Co_{1}$ | $415\,777\,680\cdot 10^{10}$ | $276$ | $\approx 0.1311$ | $M$ | $808\,017\,424\cdot 10^{44}$ | $196\,883$ | $\approx 0.0983$
$\dfrac{1^{1}}{1_{1_{1}}}$ $Fi_{22}$ | $645\,617\,516\cdot 10^{5}$ | $78$ | $\approx 0.1371$ | ${}^{2}F_{4}(2)^{\prime}$ | $17\,971\,200$ | $104$ | $\approx 0.2781$
$\dfrac{1^{1}}{1_{1_{1}}}$ $Fi_{23}$ | $408\,947\,047\cdot 10^{10}$ | $782$ | $\approx 0.1555$ |  |  |  |
Table 5. Quasirandom degree of the sporadic simple groups.

Acknowledgments: We thank S. Eberhard for enlightening conversations on the
paper, and P. Tiep for useful informations about his articles.

## References

  * [1] M. Aschbacher, Finite Group Theory, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2000.
  * [2] L. Babai, N. Nikolov, L. Pyber, Product growth and mixing in finite groups, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2008), 248-257.
  * [3] J. Bourgain, A. Gamburd, Uniform expansion bounds for Cayley graphs of $\mathrm{SL}_{2}(\mathbb{F}_{p})$, Annals of Mathematics 167 (2008), 625-642.
  * [4] E. Breuillard, B. Green, R. Guralnick, T. Tao, Expansion in finite simple groups of Lie type, Journal of the European Mathematical Society 17 (2015), 1367-1434.
  * [5] E. Breuillard, B. Green, T. Tao, Approximate subgroups of linear groups, Geometric and Functional Analysis 21 (2011), 774-819.
  * [6] F.R.K. Chung, R.L. Graham, R.M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345-362.
  * [7] J.H. Conway, R. Curtis, S.P. Norton, R.A. Parker, R. Wilson, An ATLAS of Finite Groups, Oxford University Press, 2003.
  * [8] S. Eberhard, B. Murphy, L. Pyber, E. Szabó, Growth in linear groups, arxiv preprint: arxiv.org/abs/2107.06674 (2023).
  * [9] A. Gamburd, On the spectral gap for infinite index “congruence” subgroups of $\mathrm{SL}_{2}(\mathbb{Z})$, Israel Journal of Mathematics 127 (2002), 157-200.
  * [10] The GAP Group, Groups, Algorithms, and Programming, Version 4.11.1.
  * [11] W.T. Gowers, Quasirandom groups, Combinatorics, Probability and Computing 17 (2008), 363-387.
  * [12] O. Grün, Beiträge zur Gruppentheorie I, Journal für die reine und angewandte Mathematik 174 (1936), 1-14.
  * [13] H.A. Helfgott, Growth and generation in $\mathrm{SL}_{2}(\mathbb{Z}/p\mathbb{Z})$, Annals of Mathematics 167 (2008), 601-623.
  * [14] C. Jansen, The minimal degrees of faithful representations of the sporadic simple groups and their covering groups, LMS Journal of Computation and Mathematics 8 (2005), 122-144.
  * [15] V. Landazuri, G.M. Seitz, On the minimal degrees of projective representations of the finite Chevalley groups, Journal of Algebra 32 (1974), 418-443.
  * [16] A. Lev, On large subgroups of finite groups, Journal of Algebra 152 (1992), 434-438.
  * [17] F. Lübeck, Smallest degrees of representations of exceptional groups of Lie type, Communications in Algebra 29 (2001), 2147-2169.
  * [18] K. Magaard, G. Malle, Low-dimensional representations of finite orthogonal groups, Mathematical Proceedings of the Cambridge Philosophical Society 171 (2021), 585-606.
  * [19] N. Nikolov, L. Pyber, Product decompositions of quasirandom groups and a Jordan type theorem, Journal of the European Mathematical Society 13 (2011), 1063-1077.
  * [20] L. Pyber, E. Szabó, Growth in finite simple groups of Lie type, Journal of the American Mathematical Society 29 (2016), 95-146.
  * [21] L. Sabatini, The growth of abelian sections, Annali di Matematica Pura ed Applicata 202 (2023), 1197-1216.
  * [22] P. Sarnak, X. Xue, Bounds for multiplicities of automorphic representations, Duke Mathematical Journal 64 (1991), 207-227.
  * [23] C. Schildkraut (https://math.stackexchange.com/users/253966/carl-schildkraut), Groups with no small nontrivial representation, URL (version: 2020-03-09): https://math.stackexchange.com/q/3574456
  * [24] G.M. Seitz, A.E. Zalesskii, On the minimal degrees of projective representations of the finite Chevalley groups II, Journal of Algebra 158 (1993), 233-243.
  * [25] T. Tao, Expansion in Finite Simple Groups of Lie Type, Graduate Studies in Mathematics, vol. 164, AMS, 2015.
  * [26] P.H. Tiep, Low dimensional representations of finite quasisimple groups, In Groups, Combinatorics and Geometry (2003), 277-294.
  * [27] P.H. Tiep, A.E. Zalesskii, Minimal characters of the finite classical groups, Communications in Algebra 24 (1996), 2093-2167.
  * [28] Y. Zhao (https://mathoverflow.net/users/8297/yufei-zhao), Is $\operatorname{PSL}(2,q)$ the most quasirandom group?, URL (version: 2021-08-03): https://mathoverflow.net/q/400864