# A note on the paper arXiv:2112.14547

Michael E. Zieve  Department of Mathematics, University of Michigan, 530
Church Street, Ann Arbor, MI 48109-1043 USA<EMAIL_ADDRESS>http://www.math.lsa.umich.edu/$\sim$zieve/

###### Abstract.

We give historical remarks related to arXiv:2112.14547. In particular, we show
that the “new” permutation polynomials in that paper are actually well known.
In addition we give a simpler derivation of these permutation polynomials than
had been given previously, which demonstrates the general method of producing
permutation polynomials that was introduced in arXiv:1310.0776.

##  1\. Introduction

A polynomial $f(X)\in\mathbb{F}_{q}[X]$ is called a _permutation polynomial_
if the function $c\mapsto f(c)$ permutes $\mathbb{F}_{q}$. The recent paper
[3] purports to provide new classes of permutation polynomials. Here we show
that these permutation polynomials are in fact well-known.111Shortly after [2]
(the first version of [3]) appeared on the arXiv, I emailed the content of
this note to the third and fifth authors of that paper (I cannot find email
addresses for the other authors), and suggested that [2] should be revised in
light of the content of this note. Since I did not receive a reply, and no new
version of [2] was posted in the following days, I posted the first version of
this note to the arXiv on 04 Jan 2022, in order to help members of the
permutation polynomials community avoid spending further time and effort on
rediscovering known results. The updated version [3] of [2] was posted to the
arXiv on 29 Apr 2022, but it did not incorporate the information from the
present note or from my emails, although it did remove the claim from [2] that
that paper was the first to prove three conjectures which had in fact been
resolved long ago. We also give a new proof of the main result of [3], which
is significantly simpler and more direct than all previous proofs, and which
demonstrates the general method of producing permutation polynomials that was
introduced in [12].

The main result of [3] is as follows.

######  Theorem 1.1.

Let $k,\ell,m$ be positive integers with $\ell\neq m$, and write $q:=2^{k}$,
$Q:=2^{\ell}$, and $R:=2^{m}$. Let $u$ be an integer, and let
$d_{1},d_{2},d_{3}$ be positive integers such that

$\displaystyle d_{1}$ $\displaystyle\equiv Q-R+u(q+1)\pmod{q^{2}-1}$
$\displaystyle d_{2}$ $\displaystyle\equiv Q+R+(u-R)(q+1)\pmod{q^{2}-1}$
$\displaystyle d_{3}$ $\displaystyle\equiv-(Q+R)+(u+Q)(q+1)\pmod{q^{2}-1}.$

If $\gcd(d_{1},q^{2}-1)=1$ then $f(X):=X^{d_{1}}+X^{d_{2}}+X^{d_{3}}$ permutes
$\mathbb{F}_{q^{2}}$.

######  Remark.

The above statement includes all permutation polynomials that can be inferred
from any interpretation of [3, Thm. 3.1]. The statement of the latter result
does not require the $d_{i}$ to be positive, and does not say that its
expressions for the $d_{i}$’s should be interpreted as congruences mod
($q^{2}-1$). However, we assume that the authors of [3] intended to state
their result as above. The positivity condition is needed in order to make
their result be true (and indeed, negative $d_{i}$’s would not yield
polynomials), and after imposing positivity then the congruences becomes
natural, since such congruences do not affect whether $f(X)$ permutes
$\mathbb{F}_{q^{2}}$.

We will use the following definition.

######  Definition 1.2.

We say that polynomials $f,g\in\mathbb{F}_{q}[X]$ are _multiplicatively
equivalent_ if $f(X)\equiv\alpha g(\beta X^{n})\pmod{X^{q}-X}$ for some
$\alpha,\beta\in\mathbb{F}_{q}^{*}$ and some positive integer $n$ such that
$\gcd(n,q-1)$.

The following properties of multiplicative equivalence are immediate:

  1. (1)

Multiplicative equivalence is an equivalence relation on $\mathbb{F}_{q}[X]$.

  2. (2)

If $f,g\in\mathbb{F}_{q}[X]$ are multiplicatively equivalent then $f(X)$
permutes $\mathbb{F}_{q}$ if and only if $g(X)$ permutes $\mathbb{F}_{q}$.

  3. (3)

If $f(X)$ and $g(X)$ are multiplicatively equivalent and $\deg(f)<q$ then
$f(X)$ has at most as many terms as does $g(X)$.

In light of the above properties, multiplicative equivalence is a natural
equivalence relation to use when deciding whether one permutation polynomial
with few terms is essentially the same as another.

######  Remark.

What we call multiplicative equivalence has been called “quasi-multiplicative
equivalence” in previous papers. The term “multiplicative equivalence” has
been defined previously to mean two different things, neither of which is
equivalent to the above definition. However, we suggest that the above
definition should be used in the future, for the betterment of the subject –
for instance, the use of the previous definitions has led authors to spend
time and effort producing permutation polynomials that could have been
obtained immediately from previously known permutation polynomials by
composing with $\beta X$.

We will show that the permutation polynomials in Theorem 1.1 have appeared in
the following previous results (listed according to the order in which the
relevant papers were posted in the public domain):

  1. (1)

Some instances of the permutation polynomials in Theorem 1.1 are special cases
of the much more general classes of permutation polynomials in [12, Thm. 1.1
and 1.2]; however, the paper [12] does not draw attention to the relevant
special cases.

  2. (2)

If $\ell$ is odd and $m$ is even then every permutation polynomial in Theorem
1.1 appears in one of [8, Cor. 3.8, 3.9, 3.12, and 3.13]. If $\ell$ is even
and $m$ is odd then every permutation polynomial in Theorem 1.1 is
multiplicatively equivalent to a permutation polynomial in one of [8, Cor.
3.8, 3.9, 3.12, and 3.13].

  3. (3)

Every permutation polynomial in Theorem 1.1 is multiplicatively equivalent to
a permutation polynomial in [5, Thm. 1].

  4. (4)

Every permutation polynomial in Theorem 1.1 is multiplicatively equivalent to
a permutation polynomial in [1, Thm. 4.2].

  5. (5)

Every permutation polynomial in Theorem 1.1 is multiplicatively equivalent to
a permutation polynomial in [9, Thm. 3.2].

  6. (6)

If $k$ is odd and $\gcd(2k,\ell-m)=1$ then every permutation polynomial in
Theorem 1.1 is multiplicatively equivalent to a permutation polynomial in [6,
Thm. 1].

  7. (7)

Every permutation polynomial in Theorem 1.1 is multiplicatively equivalent to
a permutation polynomial in [10, Thm. 1.1].

In addition, [2] (the first version of [3]) purports to be the first paper to
resolve three conjectures from the literature. However, in fact those
conjectures were proved previously. Specifically, the two conjectures from [7]
were first resolved as parts (a) and (b) of [12, Cor. 1.4], and Conjecture 2
of [4] was first resolved in [8, Thm. 4.2].

In the next section we give a very short and simple proof of Theorem 1.1,
based on the arguments in [12], which pinpoints the key reason why $f(X)$
permutes $\mathbb{F}_{q^{2}}$. This proof avoids the non-conceptual
computations occurring in all previous proofs of Theorem 1.1. It turns out
that the same approach can be used to deduce all the results mentioned above,
in addition to dozens of other results from the literature and arbitrarily
many as-yet unpublished results. We encourage readers interested in
permutation polynomials to look into [12], so that they can focus their
attention and time on producing results which do not follow immediately from
the arguments in that paper. We conclude this note in Section 3 by explaining
how Theorem 1.1 connects with previous results.

##  2\. Proof of Theorem 1.1

In this section we give a new proof of Theorem 1.1. We write $\mu_{q+1}$ for
the set of $(q+1)$-th roots of unity in $\mathbb{F}_{q^{2}}$, and if
$A(X)\in\mathbb{F}_{q^{2}}[X]$ then we write $A^{(q)}(X)$ for the polynomial
obtained from $A(X)$ by raising all coefficients to the $q$-th power. We first
restate the condition for certain polynomials to permute $\mathbb{F}_{q^{2}}$
in terms of whether an associated polynomial permutes $\mu_{q+1}$, via the
following special case of an easy and much-used lemma from [11].

######  Lemma 2.1.

Write $f(X):=X^{r}A(X^{q-1})$ where $r$ is a positive integer, $q$ is a prime
power, and $A(X)\in\mathbb{F}_{q^{2}}[X]$. Then $f(X)$ permutes
$\mathbb{F}_{q^{2}}$ if and only if $\gcd(r,q-1)=1$ and
$g_{0}(X):=X^{r}A(X)^{q-1}$ permutes $\mu_{q+1}$.

We next translate the condition that $g_{0}(X)$ permutes $\mu_{q+1}$ into the
condition that an associated rational function $g(X)$ permutes $\mu_{q+1}$,
where typically $g(X)$ has much lower degree than does $g_{0}(X)$. We do this
in the following trivial lemma, which encodes a procedure introduced in [12].

######  Lemma 2.2.

Write $g_{0}(X):=X^{r}A(X)^{q-1}$ where $r$ is an integer, $q$ is a prime
power, and $A(X)\in\mathbb{F}_{q^{2}}[X]$. Then $g_{0}(X)$ maps $\mu_{q+1}$
into $\mu_{q+1}\cup\\{0\\}$, and if $A(X)$ has no roots in $\mu_{q+1}$ then
$g_{0}(X)$ induces the same function on $\mu_{q+1}$ as does
$g(X):=X^{s}A^{(q)}(1/X)/A(X)$ for any integer $s$ with $s\equiv r\pmod{q+1}$.
In particular, $g_{0}(X)$ permutes $\mu_{q+1}$ if and only if $g(X)$ permutes
$\mu_{q+1}$ and $A(X)$ has no roots in $\mu_{q+1}$.

A key ingredient in [12] is degree-one rational functions which map
$\mu_{q+1}$ to either $\mu_{q+1}$ or
$\mathbb{P}^{1}(\mathbb{F}_{q}):=\mathbb{F}_{q}\cup\\{\infty\\}$. In this note
we use

$\rho(X):=\frac{X+\omega}{\omega X+1}$

where $\omega$ is a prescribed order-$3$ element of $\mathbb{F}_{q^{2}}^{*}$,
with $q$ being a power of $2$. The following result is a special case of [12,
Lemmas 2.1 and 3.1], and also is easy to verify directly.

######  Lemma 2.3.

Let $q:=2^{k}$ where $k>0$. If $k$ is even then $\rho(X)$ permutes
$\mu_{q+1}$, and if $k$ is odd then $\rho(X)$ interchanges $\mu_{q+1}$ and
$\mathbb{P}^{1}(\mathbb{F}_{q})$.

Pick any nonconstant $h(X)\in\mathbb{F}\hbox
to0.0pt{\hss$\overline{\phantom{\rm\mathbb{F}}}$}_{q}(X)$. In light of Lemma
2.3, if $k$ is even then $\rho\circ h\circ\rho$ permutes $\mu_{q+1}$ if and
only if $h(X)$ permutes $\mu_{q+1}$, and if $k$ is odd then $\rho\circ
h\circ\rho$ permutes $\mu_{q+1}$ if and only if $h(X)$ permutes
$\mathbb{P}^{1}(\mathbb{F}_{q})$. We will show that the permutation
polynomials $f(X)$ in Theorem 1.1 correspond to rational functions $g(X)$
permuting $\mu_{q+1}$ (via Lemmas 2.1 and 2.2) where $g(X)=X^{i}\circ\rho\circ
X^{R+jQ}\circ\rho$ with $i,j\in\\{1,-1\\}$. The following result presents
these compositions in the cases we need; it can be verified by a routine
computation.

######  Lemma 2.4.

Let $k,\ell,m$ be positive integers with $\ell\neq m$, and write $q:=2^{k}$,
$Q:=2^{\ell}$, and $R:=2^{m}$. Then

$X^{(-1)^{m}}\circ\frac{X^{Q+R}+X^{Q}+1}{X^{Q+R}+X^{R}+1}=\begin{cases}\rho\circ
X^{R-Q}\circ\rho&\text{ if $\ell\equiv m\pmod{2}$}\\\ \rho\circ
X^{R+Q}\circ\rho&\text{ if $\ell\not\equiv m\pmod{2}$.}\end{cases}$

Now we prove Theorem 1.1.

###### Proof of Theorem 1.1.

Note that $d_{1}\equiv d_{2}+R(q-1)\pmod{q^{2}-1}$ and $d_{3}\equiv
d_{2}+(Q+R)(q-1)\pmod{q^{2}-1}$. Thus $d_{2}\equiv d_{1}\pmod{q-1}$, so the
hypothesis $\gcd(d_{1},q-1)=1$ implies that $\gcd(d_{2},q-1)=1$. By Lemma 2.1
and Lemma 2.2, it suffices to show that $A(X):=X^{R}+1+X^{Q+R}$ has no roots
in $\mu_{q+1}$ and $g(X)$ permutes $\mu_{q+1}$, where

$g(X):=X^{Q+R}\frac{A^{(q)}(1/X)}{A(X)}=\frac{X^{Q+R}+X^{Q}+1}{X^{Q+R}+X^{R}+1}.$

We first show that $A(X)$ has no roots in $\mu_{q+1}$. Suppose to the contrary
that $\alpha\in\mu_{q+1}$ satisfies $A(\alpha)=0$. Then also

$0=\alpha^{Q+R}A(\alpha)^{q}=\alpha^{Q+R}A(\alpha^{q})=\alpha^{Q+R}A\bigl{(}\frac{1}{\alpha}\bigr{)}=\alpha^{Q}+\alpha^{Q+R}+1.$

Thus $0=A(\alpha)+\alpha^{Q+R}A(\alpha)^{q}=\alpha^{R}+\alpha^{Q}$, so
$\alpha^{Q-R}=1$. Since $\gcd(Q-R,q+1)=1$, it follows that $\alpha=1$; but
plainly $A(1)=1\neq 0$, contradiction.

It remains to show that $g(X)$ permutes $\mu_{q+1}$. First suppose $\ell\equiv
m\pmod{2}$. Then the hypothesis $\gcd(Q-R,q+1)=1$ implies that $k$ is even, so
that $X^{R-Q}$ permutes $\mu_{q+1}$ and also $\rho(X)$ permutes $\mu_{q+1}$ by
Lemma 2.3. Thus Lemma 2.4 implies that $g(X)$ permutes $\mu_{q+1}$

Now suppose $\ell\not\equiv m\pmod{2}$. If $k$ is odd then $\rho(X)$
interchanges $\mu_{q+1}$ and $\mathbb{P}^{1}(\mathbb{F}_{q})$, and we have
$\gcd(Q+R,q-1)=1$ so that $X^{Q+R}$ permutes $\mathbb{P}^{1}(\mathbb{F}_{q})$,
whence $g(X)$ permutes $\mu_{q+1}$ by Lemma 2.4. Finally, if $k$ is even then
$\rho(X)$ permutes $\mu_{q+1}$, and since $k\not\equiv\ell-m\pmod{2}$ we have
$\gcd(Q+R,q+1)=1$, so that $X^{Q+R}$ permutes $\mu_{q+1}$, whence again $g(X)$
permutes $\mu_{q+1}$. ∎

######  Remark.

The method used in the above proof can be used to produce enormous collections
of permutation polynomials over $\mathbb{F}_{q^{2}}$, for any prime power $q$.
One can start with any rational function $h(X)\in\mathbb{F}_{q}(X)$ which
permutes $\mathbb{P}^{1}(\mathbb{F}_{q})$, and any degree-one
$\rho,\eta\in\mathbb{F}_{q^{2}}(X)$ such that
$\rho(\mu_{q+1})=\mathbb{P}^{1}(\mathbb{F}_{q})$ and
$\eta(\mathbb{P}^{1}(\mathbb{F}_{q}))=\mu_{q+1}$, in order to obtain a
rational function $g(X):=\eta\circ h\circ\rho$ which permutes $\mu_{q+1}$. It
turns out that $g(X)$ can always be written in infinitely many ways as
$X^{s}A^{(q)}(1/X)/A(X)$ where $s\in\mathbb{Z}$ and
$A(X)\in\mathbb{F}_{q^{2}}[X]$ has no roots in $\mu_{q+1}$. If either $q$ is
even or $s$ is odd then there exist positive integers $r$ such that $r\equiv
s\pmod{q+1}$ and $\gcd(r,q-1)=1$, so that $X^{r}A(X^{q-1})$ permutes
$\mathbb{F}_{q^{2}}$. By applying this procedure to the most well-known
permutation rational functions over $\mathbb{F}_{q}$, and using certain
choices of $\rho(X)$, $\eta(X)$, and $A(X)$, one obtains huge classes of
permutation polynomials over $\mathbb{F}_{q^{2}}$ which include as very
special cases essentially all known permutation polynomials of the form
$X^{r}B(X^{q-1})$. We will elaborate on this remark in forthcoming joint
papers with Zhiguo Ding.

##  3\. Connection with previous results

In this section we explain the connection between Theorem 1.1 and previous
results. The combination of [8, Cor. 3.8, 3.9, 3.12, and 3.13] is as follows.

######  Proposition 3.1.

Let $k,s,t,r$ be positive integers with $s$ odd and $t$ even, and write
$q:=2^{k}$, $S:=2^{s}$, and $T:=2^{t}$. If $r\equiv S+T\pmod{q+1}$ then

$g(X):=X^{r}\Bigl{(}X^{(S+T)(q-1)}+X^{T(q-1)}+1\Bigr{)}$

permutes $\mathbb{F}_{q^{2}}$ if and only if $\gcd(r,q-1)=1$.

This implies Theorem 1.1 in case $\ell$ is odd and $m$ is even, since if we
put $s:=\ell$, $t:=m$, and $r:=d_{2}$ then the polynomial $g(X)$ in
Proposition 3.1 is congruent mod $X^{q^{2}}-X$ to the polynomial $f(X)$ in
Theorem 1.1. Next suppose that $\ell$ is even and $m$ is odd, and put $s:=m$,
$t:=\ell$, and $r\equiv-d_{3}-(Q+R)(q-1)\pmod{q^{2}-1}$. Then one can check
that the polynomials $g(X)$ from Proposition 3.1 and $f(X)$ from Theorem 1.1
satisfy

$f(X)\equiv g(X^{q^{2}-2})\pmod{X^{q^{2}}-X},$

so that $f(X)$ and $g(X)$ are multiplicatively equivalent.

Theorem 1 of [5] is as follows:

######  Proposition 3.2.

Let $k$ and $n$ be positive integers, and write $q:=2^{k}$ and $T:=2^{n}$.
Suppose that $\gcd(T-1,q+1)=1$, and let $r$ and $s$ be positive integers such
that $r(T-1)\equiv T\pmod{q+1}$ and $s(T-1)\equiv-1\pmod{q+1}$. Then
$g(X):=X+X^{1+r(q-1)}+X^{1+s(q-1)}$ permutes $\mathbb{F}_{q^{2}}$.

######  Remark.

The statement of [5, Thm. 1] has the additional hypothesis $n<k$, but that
hypothesis is not used in the proof of that result.

We now show that all the permutation polynomials in Theorem 1.1 are
multiplicatively equivalent to permutation polynomials in Proposition 3.2.
Assume the hypotheses of Theorem 1.1. Replace $\ell$ by $\ell+2ki$ for a
positive integer $i$ which is large enough so that $Q>R$; note that this
replacement does not change the congruence class of $Q$ mod $(q^{2}-1)$, and
hence does not affect the truth of the hypotheses or conclusion of Theorem
1.1, while also not affecting the multiplicative equivalence class of the
permutation polynomial $f(X)$ in Theorem 1.1. Write $n:=\ell-m$ and
$T:=2^{n}$, so that the hypotheses of Theorem 1.1 imply that
$\gcd(T-1,q+1)=1$. Writing $v:=d_{1}$, we see that the polynomial $g(X)$ in
Proposition 3.2 satisfies

$g(X^{v})=X^{v}+X^{v+rv(q-1)}+X^{v+sv(q-1)}.$

Since $v\equiv Q-R\pmod{q+1}$, we have

$\displaystyle rv(q-1)$ $\displaystyle\equiv r(Q-R)(q-1)\pmod{q^{2}-1}$
$\displaystyle=r(T-1)R(q-1)$ $\displaystyle\equiv TR(q-1)\pmod{q^{2}-1}$
$\displaystyle=Q(q-1),$

and likewise

$sv(q-1)\equiv-R(q-1)\pmod{q^{2}-1}.$

It follows that the polynomial $f(X)$ in Theorem 1.1 satisfies

$g(X^{v})\equiv f(X)\pmod{X^{q^{2}}-X},$

so that $f(X)$ and $g(X)$ are multiplicatively equivalent.

Each of the results [1, Thm. 4.2], [9, Thm. 3.2], and [10, Thm. 1.1]
generalizes [5, Thm. 1], and hence includes special cases that are
multiplicatively equivalent to each of the permutation polynomials in Theorem
1.1. If $k$ is odd and $\gcd(2k,\ell-m)=1$ then the same is true of [6, Thm.
1].

## References

  * [1] D. Bartoli and L. Quoos, Permutation polynomials of the type $x^{r}g(x^{s})$ over $\mathbb{F}_{q^{2n}}$, Des. Codes Cryptogr. 86 (2018), 1589–1599.
  * [2] H. Guo, S. Wang, H. Song, X. Zhang, and J. Liu, A new method of construction of permutation trinomials with coefficients $1$, arXiv:2112.14547v1, 29 Dec 2021.
  * [3] H. Guo, S. Wang, H. Song, X. Zhang, and J. Liu, A new method of construction of permutation trinomials with coefficients $1$, arXiv:2112.14547v2, 29 Apr 2022.
  * [4] R. Gupta and R. K. Sharma, Some new classes of permutation trinomials over finite fields with even characteristic, Finite Fields Appl. 41 (2016), 89–96.
  * [5] N. Li and T. Helleseth, New permutation trinomials from Niho exponents over finite fields with even characteristic, Cryptogr. Commun. 11 (2019), 129–136.
  * [6] N. Li, M. Xiong, and X. Zeng, On permutation quadrinomials and 4-uniform BCT, IEEE Trans. Inf. Theory 67 (2021), 4845–4855.
  * [7] T. Tu, X. Zeng, L. Hu, and C. Li, A class of binomial permutation polynomials, arXiv:1310.0337v1, 28 Sep 2013.
  * [8] D. Wu, P. Yuan, C. Ding, and Y. Ma, Permutation trinomials over $\mathbb{F}_{2^{m}}$, Finite Fields Appl. 46 (2017), 38–56.
  * [9] L. Zheng, H. Kan, and J. Peng, Two classes of permutation trinomials with Niho exponents over finite fields with even characteristic, Finite Fields Appl. 68 (2020), 101754, 14 pp.
  * [10] L. Zheng, B. Liu, H. Kan, J. Peng, D. Tang, More classes of permutation quadrinomials from Niho exponents in characteristic two, Finite Fields Appl. 78 (2022), Paper No. 101962, 22 pp.
  * [11] M. E. Zieve, Some families of permutation polynomials over finite fields, Int. J. Number Theory 4 (2008), 851–857.
  * [12] M. E. Zieve, Permutation polynomials on $\mathbb{F}_{q}$ induced from Rédei function bijections on subgroups of $\mathbb{F}_{q}^{*}$, arXiv:1310.0776v2, 7 Oct 2013.


# Criterion of unrecognizability of a finite group by its Gruenberg–Kegel
graph

Peter J. Cameron111University of St Andrews, St Andrews, UK, email:pjc20@st-
andrews.ac.uk and Natalia V. Maslova 222Krasovskii Institute of Mathematics
and Mechanics UB RAS, Ekaterinburg, Russia and Ural Federal University,
Ekaterinburg, Russia, email<EMAIL_ADDRESS>333Corresponding author.

###### Abstract

The Gruenberg–Kegel graph $\Gamma(G)$ associated with a finite group $G$ has
as vertices the prime divisors of $|G|$, with an edge from $p$ to $q$ if and
only if $G$ contains an element of order $pq$. This graph has been the subject
of much recent interest; one of our goals here is to give a survey of some of
this material, relating to groups with the same Gruenberg–Kegel graph.
However, our main aim is to prove several new results. Among them are the
following.

  * •

There are infinitely many finite groups with the same Gruenberg–Kegel graph as
the Gruenberg–Kegel of a finite group $G$ if and only if there is a finite
group $H$ with non-trivial solvable radical such that $\Gamma(G)=\Gamma(H)$.

  * •

There is a function $F$ on the natural numbers with the property that if a
finite $n$-vertex graph whose vertices are labelled by pairwise distinct
primes is the Gruenberg–Kegel graph of more than $F(n)$ finite groups, then it
is the Gruenberg–Kegel graph of infinitely many finite groups. (The function
we give satisfies $F(n)=O(n^{7})$, but this is probably not best possible.)

  * •

If a finite graph $\Gamma$ whose vertices are labelled by pairwise distinct
primes is the Gruenberg–Kegel graph of only finitely many finite groups, then
all such groups are almost simple; moreover, $\Gamma$ has at least three
pairwise non-adjacent vertices, and $2$ is non-adjacent to at least one odd
vertex.

  * •

Groups whose power graphs, or commuting graphs, are isomorphic have the same
Gruenberg–Kegel graph.

  * •

The groups ${{}^{2}}G_{2}(27)$ and $E_{8}(2)$ are uniquely determined by the
isomorphism types of their Gruenberg–Kegel graphs.

In addition, we consider groups whose Gruenberg–Kegel graph has no edges.
These are the groups in which every element has prime power order, and have
been studied under the name _EPPO groups_ ; completing this line of research,
we give a complete list of such groups.

Dedicated to the memory of Jan Saxl

##  1 Introduction

Throughout the paper we consider only finite groups and simple graphs, and
henceforth the term group means finite group, the term graph means simple
graph (undirected graph without loops and multiply edges).

Let $G$ be a group. Denote by $\pi(G)$ the set of all prime divisors of the
order of $G$ and by $\omega(G)$ the spectrum of $G$, i.e. the set of all its
element orders. The set $\omega(G)$ defines the Gruenberg–Kegel graph (or the
prime graph) $\Gamma(G)$ of $G$; in this graph the vertex set is $\pi(G)$, and
distinct vertices $p$ and $q$ are adjacent if and only if $pq\in\omega(G)$.

The concept of Gruenberg–Kegel graph appeared in the unpublished manuscript
[32] by K. Gruenberg and O. Kegel, where they have characterized groups with
disconnected Gruenberg–Kegel graph. This result was published later in the
paper [84] by J. Williams, who was a student of K. Gruenberg, and now this
theorem is well-known as the Gruenberg–Kegel theorem (see Lemma 2.3 in Section
2). The concept of Gruenberg–Kegel graph proved to be very useful with
connection to research of some cohomological questions in integral group
rings: the augmentation ideal of an integral group ring is decomposable a as
module if and only if the Gruenberg–Kegel graph of the group is disconnected
(see [33]).

Later connected components of Gruenberg–Kegel graphs of simple groups were
described. J. Williams [84] has obtained this description for all simple
groups except simple groups of Lie type in characteristic $2$. Connected
components of Gruenberg–Kegel graphs of simple groups of Lie type in
characteristic $2$ were described by A. S. Kondrat’ev [50], later this result
was obtained independently by N. Iiyori and H. Yamaki [37, 38]. Unfortunately,
all the papers [84, 50, 37, 38] contain rather serious inaccuracies. Most of
these inaccuracies was corrected in [55], and then the corrections were
finished in [51]. Now the correct description of connected components of
Gruenberg–Kegel graphs of simple groups can be found, for example, in [4] or
in [67]; finite simple groups $P$ with at least $4$ connected components of
Gruenberg–Kegel graph can be found in Section 2 of this paper, see Table 1.
Criteria of adjacency of vertices in Gruenberg–Kegel graphs of simple groups
were obtained by A. V. Vasil’ev and E. P. Vdovin in [82] with some corrections
in [83]. Moreover, at this moment all the cases of coincidence of
Gruenberg–Kegel graphs of a simple group and its proper subgroup are described
by the second author [61] and, independently, by T. Burness and E. Covato [9].
In Section 2 we provide some known properties of Gruenberg–Kegel graphs of
groups as well as some facts from Group Theory and Number Theory which we use
to prove the main results of this paper.

This paper aims to discuss the questions:

  * •

Which groups $G$ are uniquely determined by their Gruenberg–Kegel graph?

  * •

For which groups are there only finitely many groups with the same
Gruenberg–Kegel graph as $G$?

  * •

Which groups $G$ are uniquely determined by isomorphism type of their
Gruenberg–Kegel graph?

The concept of Gruenberg–Kegel graph and the Gruenberg–Kegel theorem proved
very useful for recognition questions of a group by its spectrum. It is easy
to see that for groups $G$ and $H$, if $G\cong H$, then $\omega(G)=\omega(H)$;
and if $\omega(G)=\omega(H)$, then $\Gamma(G)=\Gamma(H)$ and $\pi(G)=\pi(H)$.
The converse does not hold in each case, as the following series of examples
demonstrates (see, for example, [13]):

  * •

$S_{5}\not\cong S_{6}$ but $\omega(S_{5})=\omega(S_{6})$;

  * •

$\omega(A_{5})\not=\omega(A_{6})$ but $\Gamma(A_{5})=\Gamma(A_{6})$;

  * •

$\Gamma(A_{10})\not=\Gamma(\mathop{\mathrm{Aut}}\nolimits(J_{2}))$ but
$\Gamma(A_{10})$ and $\Gamma(\mathop{\mathrm{Aut}}\nolimits(J_{2}))$ are
isomorphic as abstract graphs and
$\pi(A_{10})=\pi(\mathop{\mathrm{Aut}}\nolimits(J_{2}))$, see the picture
below

$2$$3$$7$$5$$\Gamma(A_{10})$;
$3$$2$$7$$5$$\Gamma(\mathop{\mathrm{Aut}}\nolimits(J_{2}))$.

We say that the group $G$ is

  * •

recognizable by its spectrum (Gruenberg–Kegel graph, respectively) if for each
group $H$, $\omega(G)=\omega(H)$ ($\Gamma(G)=\Gamma(H)$, respectively) if and
only if $G\cong H$;

  * •

$k$-recognizable by spectrum (Gruenberg–Kegel graph, respectively), where $k$
is a non-negative natural number, if there are exactly $k$ pairwise non-
isomorphic groups with the same spectrum (Gruenberg–Kegel graph, respectively)
as $G$;

  * •

almost recognizable by spectrum (Gruenberg–Kegel graph, respectively) if it is
$k$-recognizable by spectrum (Gruenberg–Kegel graph, respectively) for some
non-negative natural number $k$;

  * •

unrecognizable by spectrum (Gruenberg–Kegel graph, respectively), if there are
infinitely many pairwise non-isomorphic groups with the same spectrum
(Gruenberg–Kegel graph, respectively) as $G$.

If a group $G$ contains a non-trivial solvable normal subgroup, then there are
infinitely many groups with the same spectrum as $G$. This proposition,
formulated first by W. Shi, is well-known, and its proof was published in a
number of papers (see, for example, [68]). Moreover, in [68] the following
criteria of unrecognizability of a group by spectrum was obtained.

######  Theorem 1.1 (see [68])

Let $G$ be a group. The following statements are equivalent:

  * $(1)$

there exist infinitely many groups $H$ such that $\omega(G)=\omega(H)$;

  * $(2)$

there exists a group $H$ with non-trivial solvable radical such that
$\omega(G)=\omega(H)$.

Thus, the question of recognition of a group by its spectrum is interesting
only for groups with trivial solvable radical. This question is being actively
investigated. We do not pretend to provide a complete survey of this research
area but will mention some results which are interesting from our point of
view. A remarkable result is that if $G$ is a simple group and $H$ is a group,
then $|H|=|G|$ and $\omega(H)=\omega(G)$ if and only if $H\cong G$. (This was
put forward as a conjecture in the paper [74] and the final step of the proof
was made in the paper [81].) Moreover, for every nonabelian simple group $G$,
apart from a finite number of sporadic, alternating and exceptional groups and
apart from several series of classical groups of small dimensions, if $H$ is a
group such that $\omega(H)=\omega(G)$, then $H$ is an almost simple group with
socle isomorphic to $G$, therefore almost all finite simple groups are almost
recognizable by spectrum. This result was obtained in a large number of papers
and is still in progress in sense of investigation of recognition by spectrum
of low-dimensional classical groups. We recommend surveys of the results in
this area in papers [26, 28]; moreover, we recommend the following paper by A.
V. Vasil’ev [80], where an important contribution to the solution of the
problem of recognition by spectrum for simple classical groups of Lie type was
made, and some recent papers as [75, 27, 29, 30]. Moreover, some almost simple
groups are recognizable by spectrum, for example, see [22].

It is easy to see that if a group is recognizable by its Gruenberg–Kegel
graph, then it is recognizable by its spectrum. The converse does not hold
since, for example, $\Gamma(A_{5})=\Gamma(A_{6})$, but the group $A_{5}$ is
recognizable by spectrum (see [72]) while the group $A_{6}$ is not. Some
information about groups with the same spectrum as $A_{6}$ can be found in
[58, Theorem 2].

In Section 3 we prove the following criterion of unrecognizability of a group
by its Gruenberg–Kegel graph.

###### Theorem 1.2

Let $G$ be a group. The following statements are equivalent:

  * $(1)$

there exist infinitely many groups $H$ such that $\Gamma(G)=\Gamma(H)$;

  * $(2)$

there exists a group $H$ with non-trivial solvable radical such that
$\Gamma(G)=\Gamma(H)$.

Moreover, in Section 3 we characterize finite groups which are almost
recognizable by Gruenberg–Kegel graph. We prove the following theorem.

###### Theorem 1.3

Let $G$ be a group such that $G$ is $k$-recognizable by Gruenberg–Kegel graph
for some non-negative integer $k$. Then the following conditions hold:

  * $(1)$

$G$ is almost simple;

  * $(2)$

each group $H$ with $\Gamma(H)=\Gamma(G)$ is almost simple;

  * $(3)$

$2$ is non-adjacent to at least one odd prime in $\Gamma(G)$;

  * $(4)$

$\Gamma(G)$ contains at least $3$ pairwise non-adjacent vertices.

Note that a group with non-simple socle can be recognizable by spectrum,
therefore Theorem 1.3 can not be generalized for recognition by spectrum. Up
to a recent moment there were only two examples of groups with non-simple
socle which are recognizable by spectrum, namely,
$\mathop{\mathrm{Sz}}\nolimits(2^{7})\times\mathop{\mathrm{Sz}}\nolimits(2^{7})$
(see [66]) and $J_{4}\times J_{4}$ (see [24]). Recently, I. B. Gorshkov has
proved that if $m>5$, then the group
$\mathop{\mathrm{PSL}}\nolimits_{2^{m}}(2)\times\mathop{\mathrm{PSL}}\nolimits_{2^{m}}(2)\times\mathop{\mathrm{PSL}}\nolimits_{2^{m}}(2)$
is recognizable by spectrum, a preprint of this paper is available on the
arXiv (see [21]).

We conclude form Theorem 1.3 that if a group is recognizable by its
Gruenberg–Kegel graph, then the group is almost simple. The following problem
naturally arises.

###### Problem 1

Let $G$ be an almost simple group. Decide whether $G$ is recognizable,
$k$-recognizable for some integer $k>1$, or unrecognizable by its
Gruenberg–Kegel graph.

There are some known results on recognition of a group its by Gruenberg–Kegel
graph. Here we again will mention some results which are interesting from our
point of view; we do not pretend to provide the complete survey of this
research area.

The first result on recognition of a group by its Gruenberg–Kegel graph was
obtained by G. Chen [12], where it was proved that if $S$ is a sporadic simple
group and $H$ is a group with $|H|=|S|$ and $\Gamma(H)=\Gamma(S)$, then
$H\cong S$. Later M. Hagie [35] described groups with the same Gruenberg–Kegel
graphs as simple sporadic groups. In particular, Hagie has proved that the
groups $J_{1}$, $M_{22}$, $M_{23}$, $M_{24}$, and $Co_{2}$ are recognizable by
their Gruenberg–Kegel graphs, the group $M_{11}$ is $2$-recognizable, and the
groups $M_{12}$ and $J_{2}$ are unrecognizable by their Gruenberg–Kegel
graphs; moreover, if $S$ is one of groups $O^{\prime}N$, $Ly$, $Fi_{23}$,
$Fi_{24}$, $M$, $BM$, $Th$, $Ru$, and $Co_{1}$, then $S$ is quasirecognizable
by its Gruenberg–Kegel graph, i. e. any group $H$ with $\Gamma(H)=\Gamma(S)$
has a unique nonabelian composition factor which is isomorphic to the group
$S$. In 2006, A. V. Zavarnitsine [87] proved that the group $J_{4}$ is
recognizable by its Gruenberg–Kegel graph, moreover, $J_{4}$ is the unique
group whose Gruenberg–Kegel graph has exactly $6$ connected components. Later,
based on Hagie’s results, A. S. Kondrat’ev [48] has proved that the group $Ru$
is recognizable by its Gruenberg–Kegel graph, the group $HN$ is
$2$-recognizable, the group $Fi_{22}$ is $3$-recognizable, the groups $He$,
$McL$, and $Co_{3}$ are unrecognizable by their Gruenberg–Kegel graphs.
Recently A. S. Kondrat’ev [49] has proved that the groups $J_{3}$, $Suz$,
$O^{\prime}N$, $Ly$, $Th$, $Fi_{23}$, and $Fi_{24}$ are recognizable by their
Gruenberg–Kegel graphs, and the group $HS$ is $2$-recognizable. Thus, at this
moment only three large sporadic groups are left for which recognition by the
Gruenberg–Kegel graph is not completely studied: $Co_{1}$, $B$, and $M$. Due
to mentioned Hagie’s result, these groups are known to be quasirecognizable by
Gruenberg–Kegel graph.

M. Hagie [35] has proved that the group
$\mathop{\mathrm{PSL}}\nolimits_{2}(11)$ is $2$-recognizable by
Gruenberg–Kegel graph. In [45] Bahman Khosravi, Behman Khosravi, and Behrooz
Khosravi have proved that if $p>7$ is a Mersenne prime or a Fermat prime, then
the group $\mathop{\mathrm{PSL}}\nolimits_{2}(p)$ is recognizable by its
Gruenberg–Kegel graph. In [44] the same authors proved that if $p>11$ is a
prime number and $p\not\equiv 1\pmod{12}$, then the group
$\mathop{\mathrm{PSL}}\nolimits_{2}(p)$ is recognizable by its Gruenberg–Kegel
graph. A. Khosravi and B. Khosravi [41] have proved that if $p$ is a prime not
in $\\{2,3,7\\}$, then the group $\mathop{\mathrm{PSL}}\nolimits_{2}(p^{2})$
is $2$-recognizable by its Gruenberg–Kegel graph. In 2008, B. Khosravi [42]
proved that if $q=p^{k}$, where $k>1$ is odd and $p$ is an odd prime number,
then the group $\mathop{\mathrm{PSL}}\nolimits_{2}(q)$ is recognizable by its
Gruenberg–Kegel graph. Moreover, Z. Akhlaghi, B. Khosravi, and M. Khatami [2]
proved that if $p$ is an odd prime and $k>1$ is odd, then the group
$PGL_{2}(p^{k})$ is recognizable by its Gruenberg–Kegel graph, A. Mahmoudifar
[59] has proved that the group $PGL_{2}(25)$ recognizable by Gruenberg–Kegel
graph.

The question of recognition by Gruenberg–Kegel graph of alternating and
symmetric groups was studied in [47, 25, 76].

A. V. Zavarnitsine [87] has proved that the group
$\mathop{\mathrm{PSL}}\nolimits_{3}(7)$ is $2$-recognizable by Gruenberg–Kegel
graph. Later the question of recognition by Gruenberg–Kegel graph for simple
groups $S$ such that $|\pi(S)|\in\\{3,4\\}$ was studied in [53, 54].

A remarkable result is that the group $\mathop{\mathrm{PSL}}\nolimits_{16}(2)$
is recognizable by its Gruenberg–Kegel graph. This result was obtained
independently by A. V. Zavarnitsine [88] and by B. Khosravi, B. Khosravi, and
B. Khosravi [46]; the group $\mathop{\mathrm{PSL}}\nolimits_{16}(2)$ was the
first known example of a group with connected Gruenberg–Kegel graph which is
recognizable by its Gruenberg–Kegel graph.

Z. Momen and B. Khosravi [70] have proved that groups $B_{p}(3)$ and
$C_{p}(3)$, where $p>3$ is an odd prime, are $2$-recognizable by
Gruenberg–Kegel graph. Later M. F. Ghasemabadi, A. Iranmanesh, and N.
Ahanjideh [19] proved that if $n>5$ is an odd number, then groups $B_{n}(3)$
and $C_{n}(3)$ are $2$-recognizable by Gruenberg–Kegel graph. A. Babai and B.
Khosravi [6] have proved that the group ${{}^{2}}D_{2^{m}+1}(3)$ is
recognizable by Gruenberg–Kegel graph. Later in [18] M. F. Ghasemabadi, A.
Iranmanesh, and N. Ahanjideh proved that if $n\geq 5$ is odd, then the group
${{}^{2}}D_{n}(3)$ is recognizable by Gruenberg–Kegel graph. M. F. Ghasemabadi
and N. Ahanjideh [17] have proved that if $n\geq 6$ is even, then the group
$D_{n}(3)$ is recognizable by its Gruenberg–Kegel graph. Z. Akhlaghi, M.
Khatami, and B. Khosravi [3] have proved that if $p$ is an odd prime, then the
group $D_{p}(5)$ is recognizable by its Gruenberg–Kegel graph, and the group
$D_{p}(2)$ is quasirecognizable. Later A. Babai and B. Khosravi [7] proved
that if $n$ is odd, then the group $D_{n}(5)$ is recognizable by its
Gruenberg–Kegel graph and if $n$ is even, then $D_{n}(5)$ is
quasirecognizable.

A. V. Zavarnitsine [87] has proved that the groups $G_{2}(7)$ and
${{}^{2}}G_{2}(q)$ for each $q$ are recognizable by Gruenberg–Kegel graph. A.
S. Kondrat’ev [52] has proved that the groups $E_{7}(2)$ and $E_{7}(3)$ are
recognizable by Gruenberg–Kegel graph.

One more remarkable result was obtained in 2013 by A. V. Zavarnitsine [89], it
was proved that if $G$ is a finite group whose Gruenberg–Kegel graph has
exactly $5$ connected components, then $G\cong E_{8}(q)$, where $q\equiv
0,1,4\pmod{5}$. In particular, groups $E_{8}(q)$, where $q\equiv
0,1,4\pmod{5}$, are almost recognizable by Gruenberg–Kegel graph.

There are some other results on recognition of a simple group by its
Gruenberg–Kegel graph, in particular, some groups of Lie type are known to be
quasirecognizable by their Gruenberg–Kegel graphs. For example, we recommend
papers by Behrooz Khosravi et. al., Anatoly Kondrat’ev et. al, Neda Ahanjideh
et. al., and so on.

It is known that if $q$ is odd and $n\geq 3$, then
$\Gamma(B_{n}(q))=\Gamma(C_{n}(q))$ and $|B_{n}(q)|=|C_{n}(q)|$ but these
groups are not isomorphic. Thus, it is natural to consider the following
problem.

###### Problem 2

Let $G$ be a group and $S$ a simple group. If $\Gamma(G)$ = $\Gamma(S)$ and
$|G|=|S|$, for what kind of $S$, $G$ is forced to be isomorphic to $S$?

Problem 2 was formulated by Behrooz Khosravi in his survey paper [43, Question
4.2], by A.S. Kondrat’ev in frame of the Open Problems Session of the 13th
School–Conference on Group Theory Dedicated to V. A. Belonogov’s 85th Birthday
(see [63, Question 4]), and was independently formulated by W. Shi in a
partial communication with the second author.

Let $\Gamma$ be a simple graph whose vertices are labeled by pairwise distinct
primes. We call $\Gamma$ a labeled graph. Note that there are examples of
labeled graphs which are not equal (even not isomorphic as abstract graphs) to
Gruenberg–Kegel graphs of groups. To discuss the question of realizability of
a graph as Gruenberg–Kegel graph of a group see, for example, papers [15, 23,
31, 62]. However, the results we obtain in Section 3 allow to estimate an
upper bound for a number of groups with the same Gruenberg–Kegel graph. In
Section 4 we prove the following theorem.

###### Theorem 1.4

There exists a function $F(x)=O(x^{7})$ such that for each labeled graph
$\Gamma$ the following conditions are equivalent:

  * $(1)$

there exist infinitely many groups $H$ such that $\Gamma(H)=\Gamma$;

  * $(2)$

there exist more then $F(|V(\Gamma)|)$ groups $H$ such that
$\Gamma(H)=\Gamma$, where $V(\Gamma)$ is the set of the vertices of $\Gamma$.

The estimation which we obtain in Theorem 1.4 for the function $F$ can
certainly be improved. The following problem is of interest.

###### Problem 3

Get the exact value for the function $F$, or at least a better upper bound.

As a part of the solution of Problem 3, the following problem arises.

###### Problem 4

Improve an upper bound for the number of almost simple groups with the same
Gruenberg–Kegel graph, in particular answer the following question: is there a
constant $k$ such that for any almost simple group $G$ the number of pairwise
non-isomorphic almost simple groups $H$ such that $\Gamma(G)=\Gamma(H)$ is at
most $k$? What is the exact value of $k$?

Note that if $G$ is simple, then A. V. Vasil’ev has conjectured that there are
at most $4$ simple groups $H$ with $\Gamma(G)=\Gamma(H)$, see Problem 16.26 in
[56].

We say that the group $G$ is recognizable by isomorphism type of its
Gruenberg–Kegel graph if for each group $H$, graphs $\Gamma(G)$ and
$\Gamma(H)$ are isomorphic as abstract graphs if and only if $G\cong H$.

Since by A. V. Zavarnitsine [87], the sporadic group $J_{4}$ is the unique
group whose Gruenberg–Kegel graph has exactly $6$ connected components, we
have that $J_{4}$ is recognizable by isomorphism type of its Gruenberg–Kegel
graph. We construct some more examples of simple groups which are recognizable
by isomorphism type of Gruenberg–Kegel graph, namely, in Section 5 we prove
the following theorem.

###### Theorem 1.5

Simple groups ${{}^{2}}G_{2}(27)$ and $E_{8}(2)$ are recognizable by
isomorphism type of Gruenberg–Kegel graph. In particular, the group $E_{8}(2)$
is recognizable by its Gruenberg–Kegel graph.

It is easy to see that if a group $G$ is recognizable by isomorphism type of
its Gruenberg–Kegel graph, then $G$ is recognizable by its Gruenberg–Kegel
graph, therefore by Theorem 1.3, $G$ is almost simple. Thus, the following
problem naturally arises.

###### Problem 5

Let $G$ be an almost simple group. Decide whether $G$ is recognizable by
isomorphism type of its Gruenberg–Kegel graph.

Finally in this paper, we show how the Gruenberg–Kegel graph of a group gives
information about various other graphs whose vertex sets are the elements of
the group (so typically very much larger). The graphs we consider are the
following (we give the adjacency rule for distinct elements $g,h\in G$ in each
case):

  * •

the _commuting graph_ [8]: $gh=hg$.

  * •

the _power graph_ [40]: one of $g$ and $h$ is a power of the other.

  * •

the _enhanced power graph_ [1]: $\langle g,h\rangle$ is cyclic.

  * •

the _deep commuting graph_ [11]: the inverse images of $g$ and $h$ commute in
every central extension of $G$.

In Section 6, we prove the following results.

###### Theorem 1.6

For a finite group $G$, let $\mathrm{T}(G)$ denote one of the above four types
of graph on $G$. If $G$ and $H$ are groups with $T(G)=T(H)$, then the
Gruenberg–Kegel graphs of $G$ and $H$ are equal.

###### Theorem 1.7

Let $G$ be a finite group. Then the following are equivalent:

  * $(a)$

the enhanced power graph of $G$ is equal to the power graph;

  * $(b)$

the Gruenberg–Kegel graph of $G$ has no edges;

  * $(c)$

one of the following statements holds:

$(1)$ $|\pi(G)|=1$ and $G$ is a $p$-group;

$(2)$ $|\pi(G)|=2$ and $G$ is a (solvable) Frobenius group or $2$-Frobenius
group;

$(3)$ $|\pi(G)|=3$ and $G\in$ $\\{A_{6},$
$\mathop{\mathrm{PSL}}\nolimits_{2}(7),$
$\mathop{\mathrm{PSL}}\nolimits_{2}(17)$, $M_{10}\\}$;

$(4)$ $|\pi(G)|=3$, $G/O_{2}(G)$ is
$\mathop{\mathrm{PSL}}\nolimits_{2}(2^{n})$ for $n\in\\{2,3\\}$ and if
$O_{2}(G)\not=\\{1\\}$, then $O_{2}(G)$ is the direct product of minimal
normal subgroups of $G$, each of which is of order $2^{2n}$ and as a
$G/O_{2}(G)$-module is isomorphic to the natural
$\mathop{\mathrm{GF}}\nolimits(2^{n})SL(2^{n})$-module.

$(5)$ $|\pi(G)|=4$ and $G\cong\mathop{\mathrm{PSL}}\nolimits_{3}(4)$.

$(6)$ $|\pi(G)|=4$, $G/O_{2}(G)$ is $\mathop{\mathrm{Sz}}\nolimits(2^{n})$ for
$n\in\\{3,5\\}$ and if $O_{2}(G)\not=\\{1\\}$, then $O_{2}(G)$ is the direct
product of minimal normal subgroups of $G$, each of which is of order $2^{4n}$
and as a $G/O_{2}(G)$-module is isomorphic to the natural
$\mathop{\mathrm{GF}}\nolimits(2^{n})\mathop{\mathrm{Sz}}\nolimits(2^{n})$-module
of dimension $4$.

##  2 Preliminaries

Let $q>1$ be a natural number and $r$ be an odd prime such that $(q,r)=1$.
Denote by $e(r,q)$ the multiplicative order of $q$ modulo $r$, i. e. the
minimal natural number m such that $q\equiv 1\pmod{r}$. For odd $q$ define
$e(2,q)=1$ if $q\equiv 1\pmod{4}$ and $e(2,q)=2$ if $q\equiv 3\pmod{4}$.

######  Lemma 2.1 (Zsigmondy’s theorem, see [92])

Let $q>1$ be a natural number. For each $m$ there exists a prime $r$ such that
$e(r,q)=m$, except the following cases: $q=2$ and $m=1$; $q=3$ and $m=1$;
$q=2$ and $m=6$. In particular, $r$ divides $q^{n}-1$ and doesn’t divide
$q^{i}-1$ for $1\leq i\leq n-1$, except for the following three cases: $q=2$
and $n=6$; $q=2^{k}-1$ for some prime $k$ and $n=2$; $q=2$ and $n=1$.

In the notation of Lemma 2.1, any prime $r$ which divides $q^{n}-1$ and
doesn’t divide $q^{i}-1$ for $1\leq i\leq n-1$ is called a primitive prime
divisor of the number $q^{n}-1$. Note that a primitive prime divisor of a
number $q^{n}-1$ can be defined non-uniquely. For example, $11^{3}-1=2\times
5\times 7\times 19$, $11^{2}-1=2^{3}\times 3\times 5$, and $11-1=2\times 5$.
Thus, primitive prime divisors of the number $11^{3}-1$ are the primes $7$ and
$19$.

###### Lemma 2.2

(see [16]) Let $p$ and $q$ be primes such that $p^{a}-q^{b}=1$ for some
integer numbers $a\geq 0$ and $b\geq 0$. Then
$(p^{a},q^{b})\in\\{(3^{2},2^{3}),(2^{a},q),(p,2^{b})\\}$, where $a$ is a
prime and $b$ is a power of $2$.

Our graph-theoretic and group-theoretic terminology is mostly standard; but we
list a few points here.

Let $\pi$ be a set of primes. Given a natural number $n$, denote by $\pi(n)$
the set of its prime divisors. Then $\pi(|G|)$ is exactly $\pi(G)$ for any
group $G$. A natural number $n$ with $\pi(n)\subseteq\pi$ is called a
$\pi$-number, and a group $G$ with $\pi(G)\subseteq\pi$ is called a
$\pi$-group.

A $n$-clique (resp. a $n$-coclique) is a graph with $n$ vertices in which all
the vertices are pairwise adjacent (resp. non-adjacent).

If $G$ and $H$ are groups and $p$ is a prime, then we will denote by $S(G)$
the solvable radical of $G$ (i. e. the largest solvable normal subgroup of
$G$), by $F(G)$ the Fitting subgroup of $G$ (i. e. the largest nilpotent
normal subgroup of $G$), and by $\mathop{\mathrm{Soc}}\nolimits(G)$ the socle
of $G$ (i. e. the subgroup of $G$ generated by the set of all non-trivial
minimal normal subgroups of $G$), by $G.H$ we denote any extension of $G$ by
$H$, by $G:H$ (or $G\rtimes H$) we denote a split extension (or a semidirect
product) of $G$ by $H$, by $O_{p}(G)$ the largest normal $p$-subgroup of $G$,
and by $O(G)$ the largest normal subgroup of odd order of $G$. Denote the
number of connected components of $\Gamma(G)$ by $s(G)$, and the set of
connected components of $\Gamma(G)$ by $\\{\pi_{i}(G)\mid 1\leq i\leq
s(G)\\}$; for a group $G$ of even order, we assume that $2\in\pi_{1}(G)$.
Denote by $t(G)$ the _independence number_ of $\Gamma(G)$ (the greatest number
of verices of a coclique in $\Gamma(G)$), and by $t(r,G)$ the greatest
cardinality of a coclique in $\Gamma(G)$ containing a prime $r$.

######  Lemma 2.3 (Gruenberg–Kegel theorem, [84, Theorem A])

If $G$ is a group with disconnected Gruenberg–Kegel graph, then one of the
following statements holds:

  * $(1)$

$G$ is a Frobenius group;

  * $(2)$

$G$ is a $2$-Frobenius group;

  * $(3)$

$G$ is an extension of a nilpotent $\pi_{1}(G)$-group by a group $A$, where
$S\unlhd A\leq\mathop{\mathrm{Aut}}\nolimits(S)$, $S$ is a simple non-abelian
group with $s(G)\leq s(S)$, and $A/S$ is a $\pi_{1}(G)$-group.

$s(S)$ $S$ Restrictions $\pi_{1}(S)$ $\pi_{2}(S)$ $\pi_{3}(S)$ $\pi_{4}(S)$
$\pi_{5}(S)$ $\pi_{6}(S)$ 4 $A_{2}(4)$ $\\{2\\}$ {3} {5} {7} ${}^{2}B_{2}(q)$
$q{=}2^{2m{+}1}{>}2$ $\\{2\\}$ $\pi(q{-}1)$ $\pi(q{-}\sqrt{2q}{+}1)~{}$
$\pi(q{+}\sqrt{2q}{+}1)$ ${}^{2}E_{6}(2)$ $\\{2,3,5,7,11\\}$ {13} {17} {19}
$E_{8}(q)$ $q{\equiv}2,3(5)$ $\pi\big{(}q(q^{8}{-}1)(q^{12}{-}1)$
$\pi(\frac{q^{10}{+}q^{5}{+}1}{q^{2}{+}q{+}1})$ $\pi(q^{8}{-}q^{4}{+}1)$
$\pi(\frac{q^{10}{-}q^{5}{+}1}{q^{2}{-}q{+}1})$ $(q^{14}{-}1)(q^{18}{-}1)$
$(q^{20}{-}1)\big{)}$ $M_{22}$ $\\{2,3\\}$ {5} {7} {11} $J_{1}$ $\\{2,3,5\\}$
{7} {11} {19} $O^{\prime}N$ $\\{2,3,5,7\\}$ {11} {19} {31} $LyS$
$\\{2,3,5,7,11\\}$ {31} {37} {67} $Fi_{24}^{\prime}$ $\\{2,3,5,7,11,13\\}$
{17} {23} {29} $F_{1}=M$ $\\{2,3,5,7,11,13,$ {41} {59} {71} $17,19,23,29$,
$31,47\\}$ 5 $E_{8}(q)$ $q{\equiv}0,1,4(5)$ $\pi(q(q^{8}{-}1)(q^{10}{-}1)$
$\pi(\frac{q^{10}{+}q^{5}{+}1}{q^{2}{+}q{+}1}$)
$\pi(\frac{q^{10}{-}q^{5}{+}1}{q^{2}{-}q{+}1})$ $\pi(q^{8}{-}q^{4}{+}1)$
$\pi(\frac{q^{10}{+}1}{q^{2}{+}1})$ $(q^{12}{-}1)(q^{14}{-}1)$ $(q^{18}{-}1))$
6 $J_{4}$ $\\{2,3,5,7,11\\}$ {23} {29} {31} {37} {43}

Table 1: Finite simple groups $S$ with $s(S)>3$

Note that in the Gruenberg–Kegel graph of a nonabelian simple group, the
number $2$ is non-adjacent to at least one odd number [82]. The following
generalization of the Gruenberg–Kegel theorem was an important tool in
investigations of recognizability of a group by spectrum.

######  Lemma 2.4 ([79, Propositions 2 and 3])

Let $G$ be a non-solvable group such that $t(2,G)\geq 2$. Then the following
conditions hold:

  * $(1)$

there exists a simple non-abelian group $S$ such that $S\unlhd
G/S(G)\leq\mathop{\mathrm{Aut}}\nolimits(S)$;

  * $(2)$

if $\rho\subseteq\pi(G)$ is a coclique in $\Gamma(G)$ with $|\rho|\geq 3$,
then at most one of the primes from $\rho$ divides the product
$|S(G)|\cdot|G/S(G):S|$. In particular, $t(S)\geq t(G)-1$;

  * $(3)$

one of the following conditions holds:

    * $(a)$

every $p\in\pi(G)$ which is non-adjacent to $2$ in $\Gamma(G)$ doesn’t divide
the product $|S(G)|\cdot|G/S(G):S|$. In particular, $t(2,S)\geq t(2,G)$;

    * $(b)$

there exists $r\in\pi(S(G))$ which is non-adjacent to $2$ in $\Gamma(G)$; in
this case $t(G)=3$, $t(2,G)=2$ and $S\cong A_{7}$ or
$\mathop{\mathrm{PSL}}\nolimits_{2}(q)$ for any odd $q$.

To prove the main results of this paper, we need the following easily-proved
assertions.

###### Lemma 2.5

Let $G$ be a group with a normal series of length $r$ with cyclic factors.
Then any subgroup of $G$ can be generated by at most $r$ elements.

###### Proof

Let

$G=G_{0}>G_{1}>\cdots>G_{r}=1$

be the normal series with cyclic factors. Let $H$ be an arbitrary subgroup of
$G$. For each $i$, $G_{i+1}\cap H$ is a normal subgroup of $G_{i}\cap H$, with
factor group

$(G_{i-1}\cap H)/(G_{i}\cap H)\cong(G_{i-1}\cap H)G_{i}/G_{i}\leq
G_{i-1}/G_{i}$

which is cyclic; let $h_{i}$ be an element of $H$ such that $(G_{i}\cap
H)h_{i}$ generates this quotient.

We claim that $h_{1},\ldots,h_{r}$ generate $H$. This is proved by backward
induction. For $i=r$, we have that $h_{r}$ generates $H\cap G_{r-1}$. Suppose
that $h_{i+1},\ldots,h_{r}$ generate $H\cap G_{i}$. Then it is clear from the
above that $h_{i},\ldots,h_{r}$ generate $H\cap G_{i-1}$. So the induction
goes through, and the claim is proved on putting $i=1$. $\Box$

###### Lemma 2.6

Let $G$ be a group with a cyclic normal subgroup $C$ such that $G/C$ is
$k$-generated. Then the number of pairwise distinct supplements of $C$ in $G$
(subgroups $H$ such that $G=HC$) is at most $|C|^{k+1}$.

###### Proof

Let $\overline{g}_{1},\ldots,\overline{g}_{k}$ be generators of $G/C$, and
$g_{1},\ldots,g_{k}$ be their preimages in $G$. Define $C_{i}=Cg_{i}$ to be
the corresponding right cosets. It is clear that $|C_{i}|=|C|$ for each $i$.

Now let $H$ be a supplement to $C$ in $G$. Consider $H_{1}=H\cap C$. Since $C$
is cyclic, we have $H_{1}=\langle h\rangle$ is cyclic. Since $G=HC$, we have
$H/(H\cap C)\cong G/C$. Let $h_{1},\ldots,h_{k}$ be preimages in $H$ of the
elements $\overline{g}_{1},\ldots,\overline{g}_{k}$ from $H/(H\cap C)\cong
G/C$.

It is clear that $h\in C$ and $h_{i}\in C_{i}$ for each $i$. We claim that

$H=\langle h,h_{1},\ldots,h_{k}\rangle.$

It is easy to see that $h,h_{1},\ldots,h_{k}\in H$, therefore, $\langle
h,h_{1},\ldots,h_{k}\rangle\leq H$. Let $K=\langle
h,h_{1},\ldots,h_{k}\rangle$. Show that $|K|\geq|H|$ and, therefore, $K=H$.
Indeed, $h\in K$, therefore, $K\cap C\geq H\cap C=\langle h\rangle$, and
$K/(K\cap C)\geq\langle\overline{g}_{1},\ldots,\overline{g}_{k}\rangle=G/C$.
Thus, $|K|\geq|H\cap C|\cdot|G/C|=|H|$ and therefore, $|K|=|H|$.

So, we have proved that each supplement $H$ to $C$ in $G$ can be generated by
an element $h\in C$ and elements $h_{1},\ldots h_{k}$ such that $h_{i}\in
C_{i}$ for each $i$. It is easy to see that there are at most $|C|$
possibilities to chose $h$ and at most $|C_{i}|=|C|$ possibilities to chose
each $h_{i}$. Thus, there are at most $|C|^{k+1}$ pairwise distinct
supplements to $C$ in $G$. $\Box$

###### Lemma 2.7

Let $\pi$ be a finite set of primes, and $S=G_{n}(q)$, where $q=p^{l}$, be a
simple group of Lie type of Lie rank $n$ with base field $GF(q)$ such that
$\pi(S)\subseteq\pi$. Then the following statements hold:

  * $(1)$

there are at most $|\pi|$ choices for $p$;

  * $(2)$

there are at most $|\pi|+1$ choices for $l$;

  * $(3)$

$d(l)\leq|\pi|+1$, where $d(l)$ is the number of pairwise distinct divisors of
$l$;

  * $(4)$

If $S$ s a classical group, then $n\leq 2|\pi|+3$.

###### Proof

It is clear that $p$ divides $|S|$, therefore, $p\in\pi$ and $(1)$ holds.

Note that $q-1$ divides $|S|$, and by Lemma 2.1, excluding the cases $q=2$,
$q=2^{6}$, and $q$ is a Mersenne prime, the number $p^{l}-1$ has a primitive
prime divisor $r\in\pi(S)\setminus\\{p\\}$. Note that there are at most
$|\pi(S)|-1$ choices for $r$ and, therefore, at most $|\pi(S)|-1\leq|\pi|$
choices for $l$ (or at most $|\pi(S)|+1\leq|\pi|+1$ or $|\pi(S)|\leq|\pi|$
choices for $l$ if $p=2$ or $p$ is a Mersenne prime, respectively). Thus,
$(2)$ holds.

Note that if $d(l)$ is the number of pairwise distinct divisors of $l$, then
by Lemma 2.1, there exist at least $d(l)-2$ pairwise distinct primes dividing
$p^{l}-1$, and $p$ and all these primes are in $\pi$. Thus, $d(l)\leq|\pi|+1$
and $(3)$ holds.

If $S=A_{n}(q)$, then there is a divisor of $|S|$ of the form $q^{m}-1$ for
each $1\leq m\leq n+1$, therefore, with possible one or two exceptions due to
Lemma 2.1, the primitive prime divisor of the number $q^{m}-1$ for each $m\leq
n+1$ must lie in $\pi$. For each remainder family of classical groups, there
is a divisor of $|S|$ of the form $q^{2m}-1$ for each $m\leq m_{0}$, where
$m_{0}$ grows linearly with the rank. In the five families $B_{n}(q)$,
$C_{n}(q)$, $D_{n}(q)$, ${}^{2}A_{n}(q)$ and ${}^{2}D_{n}(q)$, we have
$m_{0}=n$, $m_{0}=n$, $m_{0}=n-1$, $m_{0}=\lfloor n/2\rfloor$, and
$m_{0}=n-1$, respectively. Now a primitive prime divisor of the number
$q^{2m}-1$ for each $m\leq m_{0}$ with possible one or two exceptions due to
Lemma 2.1 must lie in $\pi$. Thus, at least $n\leq 2|\pi|+3$ in each case and
$(4)$ holds. $\Box$

###### Lemma 2.8

(see [82, Propositions 2.5, 3.2, 4.5] and [83, Propositions 2.7]) Let $G\cong
E_{8}(q)$, where $q$ is a power of $p=2$. Let $r,s\in\pi(G)$ and $r\not=s$.
Then $r$ and $s$ are non-adjacent in $\Gamma(G)$ if and only if one of the
following conditions holds:

$(1)$ $2=p\not\in\\{r,s\\}$, $1\leq e(r,q)<e(s,q)$, and one of the following
conditions holds:

$(1a)$ $e(s,q)=6$ and $e(r,q)=5$;

$(1b)$ $e(s,q)\in\\{7,14\\}$ and $e(r,q)\geq 3$;

$(1c)$ $e(s,q)=9$ and $k\geq 4$;

$(1d)$ $e(s,q)\in\\{8,12\\}$, $e(r,q)\geq 5$, and $e(r,q)\not=6$;

$(1e)$ $e(s,q)=10$, $e(r,q)\geq 3$, and $e(r,q)\not=4,6$;

$(1f)$ $e(s,q)=18$ and $e(r,q)\not\in\\{1,2,6\\}$;

$(1g)$ $e(s,q)=20$ and $r\cdot e(r,q)\not=20$;

$(1h)$ $e(s,q)\in\\{15,24,30\\}$;

$(2)$ $r=p=2$ and $e(s,q)\in\\{15,20,24,30\\}$.

###### Lemma 2.9

Let $G=E_{8}(2)$. Then the following statements hold:

$(1)$ $|\pi(G)|=16$ and $\pi(G)=\\{2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$,
$31$, $41$, $43$, $73$, $127$, $151$, $241$, $331\\}$.

$(2)$ If $S=E_{8}(q)$ for $q>2$, then $|\pi(S)|>|\pi(G)|$.

$(3)$ Adjacency in $\Gamma(G)$ is presented in Table 2. In particular,
$s(G)=4$, $|\pi_{1}(G)|=13$, and $|\pi_{i}(G)|=1$ for $i\in\\{2,3,4\\}$.

$\mbox{Vertex }x$ Degree $\mbox{Neighbors of }x\mbox{ in }\Gamma(E_{8}(2))$
$2$ $11$ $3$, $5$, $7$, $11$, $13$, $17$, $19$, $31$, $43$, $73$, $127$ $3$
$11$ $2$, $5$, $7$, $11$, $13$, $17$, $19$, $31$, $43$, $73$, $127$ $5$ $8$
$2$, $3$, $7$, $11$, $13$, $17$, $31$, $41$ $7$ $7$ $2$, $3$, $5$, $13$, $17$,
$31$, $73$ $11$ $3$ $2$, $3$, $5$ $13$ $4$ $2$, $3$, $5$, $7$ $17$ $4$ $2$,
$3$, $5$, $7$ $19$ $2$ $2$, $3$ $31$ $4$ $2$, $3$, $5$, $7$ $41$ $1$ $5$ $43$
$2$ $2$, $3$ $73$ $3$ $2$, $3$, $7$ $127$ $2$ $2$, $3$ $151$ $0$ $241$ $0$
$331$ $0$

Table 2: Adjacency of vertices in $\Gamma(E_{8}(2))$

###### Proof

$(1)$ See, for example, [13].

$(2)$ We have $|S|=q\cdot\prod_{i\in\\{2,8,12,14,18,20,24,30\\}}(q^{i}-1)$,
therefore, by Lemma 2.1, $|\pi(S)|\geq 17>|\pi(G)|$.

$(3)$ Note that $e(3,2)=2$, $e(5,2)=4$, $e(7,2)=3$, $e(11,2)=10$,
$e(13,2)=12$, $e(17,2)=8$, $e(19,2)=18$, $e(31,2)=5$, $e(41,2)=20$,
$e(43,2)=14$, $e(73,2)=9$, $e(127,2)=7$, $e(151,2)=15$, $e(241,2)=24$,
$e(331,2)=30$. Now Lemma 2.8 gives adjacency in $\Gamma(G)$. $\Box$

###### Lemma 2.10

(see [85]) Let $G$ be the sporadic group $M$. Then the following statements
hold:

$(1)$ $|\pi(G)|=15$ and $\pi(G)=\\{2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$,
$23$, $29$, $31$, $41$, $47$, $59$, $71\\}$.

$(2)$ Adjacency in $\Gamma(G)$ is presented in Table 3.

$\mbox{Vertex }x$ Degree $\mbox{Neighbors of }x\mbox{ in }\Gamma(M)$ $2$ $10$
$3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $31$, $47$ $3$ $10$ $2$, $5$,
$7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$ $5$ $5$ $2$, $3$, $7$, $11$,
$19$ $7$ $4$ $2$, $3$, $5$, $17$ $11$ $3$ $2$, $3$, $5$ $13$ $2$ $2$, $3$ $17$
$3$ $2$, $3$, $7$ $19$ $3$ $2$, $3$, $5$ $23$ $2$ $2$, $3$ $29$ $1$ $3$ $31$
$2$ $2$, $3$ $41$ $0$ $47$ $1$ $2$ $59$ $0$ $71$ $0$

Table 3: Adjacency of vertices in $\Gamma(M)$

###### Lemma 2.11

(see [62, Lemma 14]) If $G$ is a group such that $\Gamma(G)$ is a bipartite
graph with parts of sizes $1$ and $5$, then $\pi(G)=\\{2,3,7,13,19,37\\}$ and
$G/O_{2}(G)\cong{{}^{2}}G_{2}(27)$.

###### Lemma 2.12

(see [87, Theorem A]) Groups ${{}^{2}}G_{2}(3^{2m+1})$ for $m>1$ are
recognizable by Gruenberg–Kegel graph.

###### Lemma 2.13

(see [65, Lemma 1]) Let $G$ be a group, $N$ its normal subgroup such that
$G/N$ a Frobenius group with kernel $F$ and cyclic complement $C$. If
$(|F|,|N|)=1$ and $F\not\leq NC_{G}(N)/N$, then $s\cdot|C|\in\omega(G)$ for
any $s\in\pi(N)$.

###### Lemma 2.14

(see [90, Lemma 10]) Let $V$ be a normal elementary abelian subgroup of a
group $G$. Put $H=G/V$ and denote by $G_{1}=V\rtimes H$ the natural semidirect
product. Then $\omega(G_{1})\subseteq\omega(G)$.

Let $S$ be a simple group of Lie type in characteristic $p$. Let $A$ be any
abelian $p$-group with an $S$-action. Any element $s\in S$ is said to be
unisingular on $A$ if $s$ has a (non-zero) fixed point on $A$. $S$ is said to
be unisingular if every element $s\in S$ acts unisingularly on every finite
abelian $p$-group $A$ with an $S$-action.

###### Lemma 2.15

(see [34, Theorem 1.3]) If $G=E_{8}(q)$ with q arbitrary, then $G$ is
unisingular.

###### Lemma 2.16

(see [89, Proposition 2]) Let $G={{}^{3}}D_{4}(q)$, where $q$ is a power of a
prime $p$. If $G$ acts on a non-trivial vector space $V$ over a field of
characteristic distinct from $p$, then each element $x\in G$ of order
$q^{4}-q^{2}+1$ fixes a non-zero vector $v(x)\in V$.

##  3 Proofs of Theorems 1.2 and 1.3

To prove the main results of this paper, for a given finite set $\pi$ of
primes we need to estimate the number of simple groups $S$ such that
$\pi(S)\subseteq\pi$. The following proposition is straightforward, and the
main idea of its proof can be found, for example, in [64] (see the remark
after Lemma 2 in [64]).

###### Proposition 3.1

Let $\pi$ be a finite set of primes. The number of pairwise non-isomorphic
non-abelian simple groups $S$ with $\pi(S)\subseteq\pi$ is finite, and is at
most $O(|\pi|^{3})$.

###### Proof

With respect to the Classification of Finite Simple Groups, we consider cases.

Case $S$ sporadic: There are clearly at most $26$ such groups.

Case $S$ alternating: The alternating group $A_{m}$ has order divisible by all
primes less than $m$. So, if $\pi(A_{m})\subseteq\pi$, then $m$ does not
exceed the $(|\pi|+1)$st prime number $p_{|\pi|+1}$. By the prime number
theorem, $p_{|\pi|+1}$ is roughly $|\pi|\log|\pi|$. So the number of
alternating groups does not exceed this number.

Case $S$ of Lie type: These groups fall into six families $A_{n}(p^{l})$,
$B_{n}(p^{l})$, $C_{n}(p^{l})$, $D_{n}(p^{l})$, ${}^{2}A_{n}(p^{l})$ and
${}^{2}D_{n}(p^{l})$ parametrised by rank (one parameter $n$) and field order
(two parameters $p$ and $l$), and ten families $E_{6}(p^{l})$, $E_{7}(p^{l})$,
$E_{8}(p^{l})$, $F_{4}(p^{l})$, $G_{2}(p^{l})$, ${}^{2}E_{6}(p^{l})$,
${}^{3}D_{4}(p^{l})$, ${}^{2}F_{4}(2^{l})$, ${}^{2}B_{2}(2^{l})$ and
${}^{2}G_{2}(3^{l})$ parametrised by field order (two parameters $p$ and $l$
and for the last three, only one parameter $l$).

By Lemma 2.7, there are at most at most $|\pi|$ choices for characteristic $p$
(except for one-parameter families), at most $|\pi|+1$ choices for $l$, and
for classical groups at most $2|\pi|+3$ choices for their ranks. Thus, there
are at most $O(|\pi|)$ groups in each of the one-parameter families,
$O(|\pi|^{2})$ groups in each of the two-parameter families, and at most
$O(|\pi|^{3})$ groups in each of the three-parameter families.

Thus, we conclude that there are at most $O(|\pi|^{3})$ simple groups $S$ of
Lie type such that $\pi(S)\subseteq\pi$. $\Box$

Proof of Theorem 1.2 We show first that $(2)\Rightarrow(1)$. Assume that a
group $G$ contains a non-trivial solvable normal subgroup. Then by Theorem
1.1, there exist infinitely many groups $H$ such that $\omega(G)=\omega(H)$,
and Gruenberg–Kegel graphs of all these groups coincide with $\Gamma(G)$.

Now we show that $(1)\Rightarrow(2)$. Assume that $G$ is a group such that
there exist infinitely many groups $H$ such that $\Gamma(G)=\Gamma(H)$. Assume
that for each group $H$ with $\Gamma(G)=\Gamma(H)$, the solvable radical of
$H$ is trivial (otherwise the statement of the theorem holds trivially). If
$2$ is adjacent to each odd vertex of $\Gamma(G)$, then
$\Gamma(G)=\Gamma(C_{2}\times G)$, where $C_{2}$ is the cyclic group of order
$2$, and $S(C_{2}\times G)\not=1$, a contradiction. Thus, for each $H$ with
$\Gamma(G)=\Gamma(H)$, $t(2,H)=t(2,G)\geq 2$ and, therefore, by Lemma 2.4,
$\mathop{\mathrm{Soc}}\nolimits(H)$ is a non-abelian simple group such that
$\pi(\mathop{\mathrm{Soc}}\nolimits(H))\subseteq\pi(G)$. By Proposition 3.1,
for each finite set $\pi$ of primes, the number of simple groups $T$ such that
$\pi(T)\subseteq\pi$ is finite, therefore the number of almost simple groups
$H$ with $\pi(\mathop{\mathrm{Soc}}\nolimits(H))\subseteq\pi(G)$ is finite, a
contradiction. $\Box$

Proof of Theorem 1.3 Note that $G$ is non-solvable since otherwise by Theorem
1.2, there are infinitely many groups $H$ with $\Gamma(G)=\Gamma(H)$.
Moreover, in $\Gamma(G)$ the vertex $2$ is non-adjacent with at least one odd
vertex, otherwise $\Gamma(G)=\Gamma(G\times C_{2})$ and again by Theorem 1.2,
there are infinitely many groups $H$ with $\Gamma(G)=\Gamma(H)$. Thus,
$t(2,G)\geq 2$.

By Lemma 2.4, each group $H$ with $\Gamma(G)=\Gamma(H)$ is such that $H/S(H)$
is almost simple. Now again if $S(H)\not=1$ for some $H$ with
$\Gamma(G)=\Gamma(H)$, then by Theorem 1.2, there are infinitely many groups
$H$ with $\Gamma(G)=\Gamma(H)$. Therefore, each group $H$ with
$\Gamma(G)=\Gamma(H)$ is almost simple, in particular, $G$ is almost simple.

By Lemmas 7–14 from [23], if $G$ is almost simple and $t(G)<3$, then there
exists a solvable group $T$ such that $\Gamma(G)=\Gamma(T)$, therefore $G$ is
unrecognizable by Gruenberg–Kegel graph. $\Box$

##  4 Proof of Theorem 1.4

Let $\pi$ be a finite set of primes. We must show that there is a polynomial
function $F$ such that the number of almost simple groups $G$ such that
$\pi(G)\subseteq\pi$ is at most $F(|\pi|)$.

By Proposition 3.1, the number of simple groups $S$ such that
$\pi(S)\subseteq\pi$ is bounded by a polynomial function of $|\pi|$, moreover
the function is at most $O(|\pi|^{3})$. Thus, it is sufficient to show that
for each simple group $S$ such that $\pi(S)\subseteq\pi$, the number of almost
simple groups with socle $S$ is bounded by a polynomial function of $|\pi|$.
This is clear if $S$ is sporadic or alternating. Thus, it is sufficient to
consider the case when $S$ is a group of Lie type. Since there is a one-to-one
correspondence between almost simple groups with socle $S$ and subgroups of
$\mathop{\mathrm{Out}}\nolimits(S)$, we need to prove the following
proposition.

###### Proposition 4.1

Let $\pi$ be a finite set of primes and $S$ be a simple group of Lie type such
that $\pi(S)\subseteq\pi$. Then there is a polynomial function $f$ such that
the number of subgroups of $\mathop{\mathrm{Out}}\nolimits(S)$ is bounded by
$f(|\pi(S)|)$, and it is at most $O(|\pi|^{4})$.

###### Proof

Let $S=G_{n}(q)$, where $q=p^{l}$, be a simple group of Lie type of Lie rank
$n$ with base field $GF(q)$ such that $\pi(S)\subseteq\pi$.

Then it is well-known (see, for example [20, Theorem 2.5.12]) that

$\mathop{\mathrm{Out}}\nolimits(S)=C\rtimes(G_{1}\times G_{2}),$

where $C=\mathrm{Outdiag}(S)$ and either $|C|\leq 4$ or $S$ is of type
$A_{n}(q)$ or ${{}^{2}}A_{n}(q)$, $C$ is cyclic, and $|C|$ is bounded by
$n+1$; $G_{1}$ is cyclic and $|G_{1}|\in\\{l,2l,3l\\}$; and $G_{2}$ has order
at most $2$ except in the case when $S$ is of type $D_{4}$, when it is
isomorphic to $S_{3}$444Here it is sufficient that
$\mathop{\mathrm{Out}}\nolimits(S)=C.G_{2}.G_{1}$, where groups $C$, $G_{1}$,
and $G_{2}$ are as above..

Let $N(G)$ be the set of all the subgroups of a group $G$. Then

$N(\mathop{\mathrm{Out}}\nolimits(S))=\bigcup\limits_{T\leq G_{1}\times
G_{2}}\\{H\mid HC/C=T\\}$ (1)

Since $G_{1}$ is cyclic, there is a one-to-one correspondence between the
number of subgroups of $G_{1}$ and the number of pairwise distinct divisors of
$|G_{1}|$. Since by Lemma 2.7, $d(l)\leq|\pi|+1$, it is easy to see that the
number of subgroups of $G_{1}$ is bounded by a linear function of $|\pi|$. Now
by Goursat’s lemma, the number of subgroups of $G_{1}\times G_{2}$ is bounded
by a linear function of $|\pi|$. Thus, the number of classes in the union (1)
is bounded by a linear function of $|\pi|$.

By Lemma 2.5, each subgroup $T$ of the group
$\mathop{\mathrm{Out}}\nolimits(S)/C\cong G_{1}\times G_{2}$ is at most
$2$-generated except in the case when $S$ is of type $D_{4}$, when $T$ is at
most $3$-generated. Therefore by Lemma 2.6, if $S$ is not of type $D_{4}$,
then the number of subgroups $H$ of $Out(S)$ such that $HC/C=T$ is at most
$|C|^{3}\leq n^{3}\leq(2|\pi|+3)^{3}$; in the case of groups of type $D_{4}$
we have $|C|\leq 4$ and possible need to apply Lemma 2.6 twice. Moreover, the
number of classes in the union (1) is bounded by a linear function of $|\pi|$,
and therefore, $|N(\mathop{\mathrm{Out}}\nolimits(S))|$ is bounded by a
polynomial function of $|\pi|$, and it is at most $O(|\pi|^{4})$. $\Box$

Thus, we have proved the following proposition.

###### Proposition 4.2

There exists a polynomial function $F$ such that if $\pi$ is a finite set of
primes, then there are at most $F(|\pi|)$ pairwise non-isomorphic almost
simple groups $G$ such that $\pi(G)\subseteq\pi$, and this number is at most
$O(|\pi|^{7})$.

So, the following corollary completes the proof of Theorem 1.4.

###### Corollary 4.3

Let $G$ be a group such that there are more than $F(|\pi(G)|)$ pairwise non-
isomorphic groups $H$ such that $\Gamma(H)=\Gamma(G)$. Then $G$ is
unrecognizable by Gruenberg–Kegel graph.

###### Proof

Suppose that there is only a finite number of groups $H$ such that
$\Gamma(H)=\Gamma(G)$. Then by Theorem 1.3, each group $H$ with
$\Gamma(H)=\Gamma(G)$ is almost simple. Thus, there are more than
$F(|\pi(G)|)$ pairwise non-isomorphic almost simple groups $H$ with
$\pi(H)\subseteq\pi(G)$, a contradiction. $\Box$

##  5 Proof of Theorem 1.5

If $G={{}^{2}}G_{2}(27)$, then $\Gamma(G)$ is as follows:

$3$$7$$13$$19$$37$$2$

If $H$ is a group such that $\Gamma(H)$ and $\Gamma(G)$ are isomorphic as
abstract graphs, then $\Gamma(H)$ is a bipartite graph with parts of sizes $1$
and $5$. By Lemma 2.11, $\pi(H)=\\{2,3,7,13,19,37\\}$ and
$H/O_{2}(H)\cong{{}^{2}}G_{2}(27)$. In particular, $\Gamma(H)=\Gamma(G)$. But
$G$ is recognizable by Gruenberg–Kegel graph by Lemma 2.12. Thus, $H\cong G$.

Let $G=E_{8}(2)$ and $H$ be a group such that $\Gamma(H)$ and $\Gamma(G)$ are
isomorphic as abstract graphs. Lemma 2.9$(3)$, $\Gamma(H)$ is disconnected.
Now by Lemma 2.3, $H/F(H)$ is almost simple, moreover, if $S=Soc(H/F(H))$,
then $s(S)\geq s(G)\geq 4$. By Table $1$ and Lemma 2.9$(2)$, $S$ is one of the
following groups: $A_{2}(4)\cong\mathop{\mathrm{PSL}}\nolimits_{3}(4)$,
${{}^{2}}B_{2}(q)$, ${}^{2}E_{6}(2)$, $E_{8}(2)$, $M_{22}$, $J_{1}$,
$O^{\prime}N$, $LyS$, $Fi_{24}^{\prime}$, $F_{1}=M$, $J_{4}$.

If $S$ is one of groups $A_{2}(4)$, ${}^{2}E_{6}(2)$, $M_{22}$, $J_{1}$,
$O^{\prime}N$, $LyS$, $Fi_{24}^{\prime}$, $J_{4}$, then by [13],
$|\pi(\mathop{\mathrm{Aut}}\nolimits(S)|\leq 10$, therefore,

$|\pi(F(H))\setminus\pi(H/F(H))|\geq 6.$

Note that the primes from $\pi(F(H))$ form a clique in $\Gamma(H)$, therefore,
$\Gamma(H)$ contains at least $6$ vertices of degree at least $5$, a
contradiction to Lemma 2.9$(3)$.

Let $S\cong{{}^{2}}B_{2}(q)$ for some $q$. Since $s(G)=s(S)$, we have
$|\pi_{i}(S)|=1$ for $i\in\\{2,3,4\\}$. In particular, $q-1$ is a prime power.
By Lemma 2.2, $q=2^{a}$, where $a$ is a prime. Therefore,
$|\pi(H/F(H))|\leq|\pi(\mathop{\mathrm{Aut}}\nolimits(S)|=5$. Again we obtain
that

$|\pi(F(H))\setminus\pi(H/F(H))|\geq 11,$

therefore, $\Gamma(H)$ contains at least $11$ vertices of degree at least
$10$, a contradiction to Lemma 2.9$(3)$.

Let $S\cong M$. Since $\mathop{\mathrm{Aut}}\nolimits(M)\cong M$ and
$|\pi(M)|=15$, there is $p\in\pi(F(H))\setminus\pi(H/F(H))$. Note that by
Lemma 2.3, $p\in\pi_{1}(H)$. Since $s(G)=s(S)$, we have $|\pi_{i}(S)|=1$ for
$i\in\\{2,3,4\\}$. Thus, by Lemma 2.10, the primes $41$, $59$, and $71$ are
non-adjacent to $p$ in $\Gamma(H)$. By [13, 85], $M$ contains subgroups
$M_{1}\cong 41:40$, $M_{2}\cong 59:29$, $M_{3}\cong 71:35$, and $M_{4}\cong
23:11$ which are Frobenius groups with cyclic complements. By Lemma 2.13, the
prime $p$ is adjacent in $\Gamma(H)$ to the primes $2$, $5$, $7$, $29$, and to
at least one of the primes $11$ and $23$. Thus, degree of vertex $p$ in
$\Gamma(H)$ is at least $5$ as well as by Lemma 2.10, degree of vertex $5$ in
$\Gamma(H)$ is at least $6$, and degree of vertex $7$ in $\Gamma(H)$ is at
least $5$. Moreover, by Lemma 2.10, degree of vertex $2$ in $\Gamma(H)$ is at
least $11$ and degree of vertex $3$ in $\Gamma(H)$ is at least $10$. Thus,
$\Gamma(H)$ contains at least $5$ vertices of degree at least $5$, a
contradiction to Lemma 2.9$(3)$.

Thus, $S\cong G=E_{8}(2)$, therefore $\Gamma(H)=\Gamma(G)$,
$\pi(F(H))\subseteq\pi_{1}(G)$, and $H/F(H)\cong G$. Let $F(H)\not=1$ and
$r\in\pi(F(H))\subseteq\pi_{1}(G)$. Show that $r$ and $241$ are adjacent in
$\Gamma(H)$. Without loss of generality, we can assume that $F(H)=O_{r}(H)$
and $O_{r}(H)$ is elementary abelian. By Lemma 2.14, we can assume that
$H=O_{r}(H)\rtimes E_{8}(2)$. If $r=2$, then by Lemma 2.15, each element from
$E_{8}(2)$ has a non-zero fixed point on $O_{2}(H)$. In particular, $2$ and
$241$ are adjacent in $\Gamma(H)$. Thus, $r\not=2$. By [13], the group
$E_{8}(2)$ has a subgroup isomorphic to ${{}^{3}}D_{4}(4)$. Now by Lemma 2.16,
each element of order $241$ has a non-zero fixed point on $O_{r}(H)$. Thus, in
any case $s(H)\leq 3$, a contradiction. $\Box$

##  6 Other graphs

In this section we give the proofs of Theorems 1.6 and 1.7.

### Proof of Theorem 1.6

For each of the four possible types of graph, $G$ and $H$ have the same order,
so their Gruenberg–Kegel graphs have the same set of vertices.

We show that in all cases except the power graph, primes $p$ and $q$ are
adjacent in the Gruenberg–Kegel graph of $G$ if and only if there is a maximal
clique in the graph $\mathrm{T}(G)$ with size divisible by $pq$. This is clear
in the cases of the enhanced power graph and the commuting graph; for the
maximal cliques in these are maximal cyclic subgroups or maximal abelian
subgroups of $G$ respectively, and if their order is divisible by $pq$ then
they contain elements of order $pq$. Conversely an element of order $pq$ is
contained in a maximal cyclic (or abelian) subgroup.

Consider the deep commuting graph of a group $G$. It is shown in [11] that
this graph is the projection onto $G$ of the commuting graph of a _Schur
cover_ of $G$ [71]. Let $K$ be a Schur cover of $G$, with $K/Z\cong G$. A
maximal clique has the form $A=B/Z$, where $B$ is a maximal abelian subgroup
of $K$ (containing $Z$). So $A$ is an abelian subgroup of $G$, and if $pq$
divides $|A|$ then $A$ contains an element of order $pq$. Conversely, suppose
that $p$ and $q$ are joined in the Gruenberg–Kegel graph, and let $x$ and $y$
be commuting elements of orders $p$ and $q$ in $G$, and $a$ and $b$ their
lifts in $K$. Then $a$ and $b$ are contained in $\langle Z,ab\rangle$, which
is an extension of a central subgroup by a cyclic group and hence is abelian;
so $a$ and $b$ commute. Choosing a maximal abelian subgroup of $K$ containing
$a$ and $b$ and projecting onto $G$ gives a maximal clique in the deep
commuting graph of $G$, with order divisible by $pq$.

This fails for the power graph. Instead we use the fact, shown in [86], that
groups with isomorphic power graphs also have isomorphic enhanced power
graphs; so they have equal Gruenberg–Kegel graphs, by what has already been
proved. $\Box$

### Proof of Theorem 1.7

The equivalence of $(a)$ and $(b)$ is [1, Theorem 28]; we give the proof for
completeness. If the group $G$ contains an element $g$ of order $pq$, where
$p$ and $q$ are primes, then $\langle g^{p},g^{q}\rangle=\langle g\rangle$, so
$g^{p}$ and $g^{q}$ are joined in the enhanced power graph, but not in the
power graph. Conversely, suppose that there are no edges in the
Gruenberg–Kegel graph of $G$. Then every element of $G$ has prime power order.
Suppose that $g$ and $h$ are joined in the enhanced power graph of $G$, so
that they generate a cyclic group, necessarily of prime power order. This
group must be generated by one of $g$ and $h$, say $g$; then $h$ is a power of
$g$, so $g$ and $h$ are adjacent in the power graph.

We now turn to the equivalence of (b) and (c).

Finite groups whose Gruenberg–Kegel graphs do not have edges (these groups are
known as _EPPO-groups_) were investigating by many authors (seem for example,
[36, 73, 78], also see [53, 54] and [5, Proposition]). Let us just summarize
these results and obtain the explicit list of such groups given in (c). This
result does not depend on the Classification of Finite Simple Groups.

######  Lemma 6.1 (See [10], see also, for example, [91, Lemma 1])

Let $G=FH$ is a Frobenius group with kernel $F$ and complement $H$. Then

$(a)$ $F=F(G)$ is the Fitting subgroup of $G$ and $|H|$ divides $|F|-1$.

$(b)$ Each subgroup of order $pq$ from $H$, where $p$ and $q$ are (not
necessary distinct) primes, is cyclic. In particular, each Sylow subgroup of
$H$ is either cyclic or (generalized) quaternion group.

$(c)$ If $|H|$ is even, then $H$ contains a unique involution.

$(d)$ If $H$ is non-solvable, then $H$ contains a subgroup $K=S\times Z$,
where $S\cong SL_{2}(5)$, $(|S|,|Z|)=1$, and $|H:K|\in\\{1,2\\}$.

######  Lemma 6.2 (See, for example, [14, Lemma 4])

Let $G$ be a finite simple group, $F$ is a field of characteristic $p>0$, $V$
is a absolute irreducible $GF$-module, and $\beta$ is a Brauer character of
$V$. If $g\in G$ is an element of prime order distinct from $p$, then

$dimC_{V}(g)=(\beta_{\langle g\rangle},1_{\langle
g\rangle})=\frac{1}{|g|}\sum_{x\in{\langle g\rangle}}\beta(x).$

######  Lemma 6.3 (see, for example, [36, Theorem 1])

Assume that every non-trivial element of a finite solvable group $G$ of
composite order is of prime power order. Then $|\pi(G)|\leq 2$.

The following assertion is easy to prove, and can be found, for example, in
[57, Theorem 1].

###### Lemma 6.4

Let $G$ be a finite group with ${t(G)\geq 3}$. Then $G$ is non-solvable.

###### Proof

Let $G$ be a finite solvable group. Assume that $\\{p,q,r\\}$ is an induced
$3$-coclique in $\Gamma(G)$. By the Hall theorem, $G$ contains a
$\\{p,q,r\\}$-Hall subgroup $H$. Then $H$ is solvable, $|\pi(H)|=3$ and
$\Gamma(H)$ is a $3$-coclique, a contradiction to Lemma 6.3.

######  Lemma 6.5 (See [78, Theorem 16])

Assume that every non-trivial element of a finite simple group $G$ of
composite order is of prime power order. Then $G$ is isomorphic to one of the
following groups: $\mathop{\mathrm{PSL}}\nolimits_{2}(q)$ for
$q\in\\{5,7,8,9,17\\}$, $\mathop{\mathrm{PSL}}\nolimits(3,4)$,
$\mathop{\mathrm{Sz}}\nolimits(q)$ for $q\in\\{8,32\\}$.

######  Lemma 6.6 (See [77, Proposition 3.2])

Let $G$ be a finite group, $H\unlhd G$, and
$G/H\cong\mathop{\mathrm{PSL}}\nolimits_{2}(q)$, where $q$ is odd and $q>5$,
and let $C_{H}(t)=1$ for some element $t$ of order $3$ from $G\setminus H$.
Then $H=1$.

######  Lemma 6.7 (See [36, Theorem 8.2], [77, Proposition 4.2] )

Let $G$ be a finite group, $1\not=H\unlhd G$, and
$G/H\cong\mathop{\mathrm{PSL}}\nolimits_{2}(2^{n})$, where $n\geq 2$. Assume
that $C_{H}(t)=1$ for some element $t$ of order $3$ form $G$. Then
$H=O_{2}(G)$ and $H$ is the direct product of minimal normal subgroups of $G$,
each of which is of order $2^{2n}$ and as a $G/H$-module is isomorphic to the
natural $\mathop{\mathrm{GF}}\nolimits(2^{n})SL(2^{n})$-module.

######  Lemma 6.8 (See [60, Theorem, Remark 1])

Let $G$ be a finite group, $1\not=H\unlhd G$,
$G/H\cong\mathop{\mathrm{Sz}}\nolimits(q)$ for $q\in\\{8,32\\}$. Assume that
$C_{H}(t)=1$ for some element $t$ of order $5$ from $G$. Then $H=O_{2}(G)$ and
$H$ is the direct product of minimal normal subgroups of $G$, each of which is
of order $2^{4n}$ and as a $G/O_{2}(G)$-module is isomorphic to the natural
$\mathop{\mathrm{GF}}\nolimits(2^{n})\mathop{\mathrm{Sz}}\nolimits(2^{n})$-module
of dimension $4$

Let $G$ be a finite group such that $\Gamma(G)$ is a coclique.

The case $|\pi(G)|=1$ is clear. Let $|\pi(G)|=2$. In this case $G$ is
solvable. Now by Lemma 2.3, $G$ is a Frobenius group or $2$-Frobenius group.
It is easy to see that for any Frobenius group or $2$-Frobenius group $G$ with
$|\pi(G)|=2$, $\Gamma(G)$ is a $2$-coclique. Note that a rather detailed
description of solvable EPPO-groups can be found in [78, Section 2].

Suppose that $|\pi(G)|\geq 3$. Then by Lemma 6.4, $G$ is non-solvable. By
Lemma 2.3, either $G/F(G)$ is almost simple or $G$ is a non-solvable Frobenius
group. By Lemma 6.1, in the later case it is easy to see that $G/O(G)$
contains an element of order $10$, therefore $\Gamma(G)$ is not a coclique.
Thus, $G/F(G)$ is almost simple, moreover, $\Gamma(G/F(G))$ is a coclique, i.
e. $G/F(G)$ is an EPPO-group, and $|F(G)|\leq 1$ since $\pi(F(G))$ form a
clique in $\Gamma(G)$. By Lemma 6.5, $Soc(G/F(G))$ is one of the following
groups: $\mathop{\mathrm{PSL}}\nolimits_{2}(q)$ for $q\in\\{5,7,8,9,17\\}$,
$\mathop{\mathrm{PSL}}\nolimits_{3}(4)$, $\mathop{\mathrm{Sz}}\nolimits(q)$
for $q\in\\{8,32\\}$. Note that
$|\pi(\mathop{\mathrm{PSL}}\nolimits_{2}(q))|=3$ if $q\in\\{5,7,8,9,17\\}$ and
$|\pi(\mathop{\mathrm{PSL}}\nolimits_{3}(4)|=|\pi(\mathop{\mathrm{Sz}}\nolimits(8))|=|\pi(\mathop{\mathrm{Sz}}\nolimits(32)|=4$.
Using [13] we conclude that $G/F(G)$ is one of the following EPPO-groups:
$A_{5}\cong\mathop{\mathrm{PSL}}\nolimits_{2}(4)\cong\mathop{\mathrm{PSL}}\nolimits_{2}(5)$,
$A_{6}\cong\mathop{\mathrm{PSL}}\nolimits_{2}(9)$,
$\mathop{\mathrm{PSL}}\nolimits_{2}(7)$,
$\mathop{\mathrm{PSL}}\nolimits_{2}(8)$,
$\mathop{\mathrm{PSL}}\nolimits_{2}(17)$,
$M_{10}\cong\mathop{\mathrm{PSL}}\nolimits_{2}(9).{2_{3}}$,
$\mathop{\mathrm{Sz}}\nolimits(q)$ for $q\in\\{8,32\\}$. This list can be
found also in [78, Section 3].

Assume that $\mathop{\mathrm{Soc}}\nolimits(G/F(G))$ is
$A_{6}\cong\mathop{\mathrm{PSL}}\nolimits_{2}(9)$,
$\mathop{\mathrm{PSL}}\nolimits_{2}(7)$, or
$\mathop{\mathrm{PSL}}\nolimits_{2}(17)$. It is easy to see that in this case
if $F(G)\not=1$, then $F(G)=O_{p}(G)$ for some $p\in\pi(G)$. If $p\not=3$,
then by Lemma 6.6, $F(G)=1$. Now suppose that $F(G)=O_{3}(G)$. Consider an
involution $x\in G$. By Lemma 2.3, the subgroup $O_{3}(G)\langle x\rangle$ is
a Frobenius group with kernel $O_{3}(G)$ and complement $\langle x\rangle$.
Therefore, by Lemma 6.1, $|O_{3}(G)|$ divides $|x|-1=1$. Thus, $F(G)=1$.

If $G/F(G)\cong\mathop{\mathrm{PSL}}\nolimits_{3}(4)$, then by [13] $G/F(G)$
contains a maximal subgroup isomorphic to
$\mathop{\mathrm{PSL}}\nolimits_{2}(7)$ and again we conclude that $F(G)=1$ as
in the previous paragraph.

Assume that $G/F(G)$ is $\mathop{\mathrm{Sz}}\nolimits(8)$ or
$\mathop{\mathrm{Sz}}\nolimits(32)$. Again if $F(G)\not=1$, then
$F(G)=O_{p}(G)$ for some $p\in\pi(G)$. If $p\not=5$, then by Lemma 6.8,
$F(G)=O_{2}(G)$ is the direct product of minimal normal subgroups of $G$, each
of which is of order $2^{4n}$ and as a $G/O_{2}(G)$-module is isomorphic to
the natural
$\mathop{\mathrm{GF}}\nolimits(2^{n})\mathop{\mathrm{Sz}}\nolimits(2^{n})$-module
of dimension $4$. For converse, Lemma 6.2 and tables of the $2$-modular Brauer
characters of groups $\mathop{\mathrm{Sz}}\nolimits(8)$ and
$\mathop{\mathrm{Sz}}\nolimits(32)$ (see Pages 63 and 197 in [39],
respectuvely) imply that in this case $\Gamma(G)$ is a $4$-coclique. Now
suppose that $F(G)=O_{5}(G)$. As above, considering an involution $x\in G$ we
conclude that by Lemma 2.3, the subgroup $O_{5}(G)\langle x\rangle$ is a
Frobenius group with kernel $O_{5}(G)$ and complement $\langle x\rangle$.
Therefore, by Lemma 6.1, $|O_{5}(G)|$ divides $|x|-1=1$. Thus, $F(G)=1$.

Assume that $G/F(G)$ is $A_{5}\cong\mathop{\mathrm{PSL}}\nolimits_{2}(4)$ or
$\mathop{\mathrm{PSL}}\nolimits_{2}(8)$. Again if $F(G)\not=1$, then
$F(G)=O_{p}(G)$ for some $p\in\pi(G)$. If $p\not=3$, then by Lemma 6.7 we
conclude as above that $F(G)=O_{2}(G)$ is the direct product of minimal normal
subgroups of $G$, each of which is of order $2^{2n}$ and as a
$G/O_{2}(G)$-module is isomorphic to the natural
$\mathop{\mathrm{GF}}\nolimits(2^{n})SL(2^{n})$-module. For converse, Lemma
6.2 and tables of the $2$-modular Brauer characters of groups $A_{5}$ and
$\mathop{\mathrm{PSL}}\nolimits_{2}(8)$ (see Pages 2 and 6 from [39],
respectively) imply that in this case $\Gamma(G)$ is a $3$-coclique. As above,
we prove that if $F(G)=O_{3}(G)$, then ${F(G)=1}$. $\Box$

##  7 Acknowledgements

This work was supported by the Russian Science Foundation (project no.
19-71-10067).

The authors are thankful to Prof. Anatoly Kondrat’ev, Prof. Wujie Shi, Prof.
Andrey Vasil’ev, and Prof. Viktor Zenkov for their helpful comments which
improved this text.

Some results on this paper were obtained after discussions of the authors
during The 3rd Workshop on “Algebraic Graph Theory and its Applications”,
Mathematical Center in Akademgorodok, Zoom-conference, 2–8 November 2020. The
authors would like to thank Elena Konstantinova and Grigory Ryabov for their
roles in organising the workshop.

## References

  * [1] G. Aalipour, S. Akbari, P. J. Cameron, R. Nikandish and F. Shaveisi, On the structure of the power graph and the enhanced power graph of a group, Electronic J. Combinatorics 24(3) (2017), P3.16.
  * [2] Z. Akhlaghi, B. Khosravi, M. Khatami, Characterization by prime graph of $PGL(2,p^{k})$ where $p$ and $k>1$ are odd, International Journal of Algebra and Computation, 20:07 (2010), 847–873.
  * [3] Z. Akhlaghi, M. Khatami, B. Khosravi, On the prime graph of $D_{n}(q)$ where $q\in\\{2,5\\}$, Quaestiones Mathematicae, 36:4 (2013) , 517–535.
  * [4] O. A. Alekseeva and A. S. Kondrat’ev, On recognizability of some finite simple orthogonal groups by spectrum, Proc. Steklov Inst. Math. 266 (2009), 10–23.
  * [5] O. A. Alekseeva, A. S. Kondrat’ev, Finite groups whose prime graphs do not contain triangles. II. Proc. Steklov Inst. Math. 296 (2017), 19–30.
  * [6] A. Babai, B. Khosravi, Recognition by prime graph of ${{}^{2}}D_{2^{m}+1}(3)$, Sib. Math. J., 52:5 (2011), 788–795.
  * [7] A. Babai, B. Khosravi, Groups with the Same Prime Graph as the Simple Group $D_{n}(5)$. Ukr Math J., 66:5 (2014), 666–677.
  * [8] R. Brauer and K. A. Fowler, On groups of even order, Ann. Math. 62 (1955), 565–583.
  * [9] T. C. Burness and E. Covato, On the prime graph of simple groups, Bull. Australian Math. Soc. 91:2 (1995), 227–240.
  * [10] V. M. Busarkin and Yu. M. Gorchakov, Finite Splittable Groups, Nauka, Moscow, 1968 [in Russian].
  * [11] P. J. Cameron and B. Kuzma, Between the enhanced power graph and the commuting graph, https://arxiv.org/2012.03789
  * [12] G. Chen, A new characterization of sporadic simple groups, Algebra Colloq., 3:1 (1996), 49–58.
  * [13] J. H. Conway et al., Atlas of Finite Groups, Clarendon Press, Oxford, 1985.
  * [14] S. Dolfi, E. Jabara, M. S. Lucido, C55-groups, Siberian Math. J. 45:6 (2004), 1053–1062.
  * [15] A. L. Gavrilyuk, I. V. Khramtsov, A. S. Kondrat’ev, N. V. Maslova, On realizability of a graph as the prime graph of a finite group, Sib. Electron. Math. Rep., 11 (2014), 246–257.
  * [16] G. C. Gerono, Note sur la resolution en nombres entiers et positifs de l’equation $x^{m}=y^{n}-1$, Nouv. Ann. Math. (2), 9 (1870), 469–471.
  * [17] M. F. Ghasemabadi, N. Ahanjideh, Characterizations of the simple group $D_{n}(3)$ by prime graph and spectrum, Iran. J. Math. Sci. Inform., 7:1 (2012), 91–106.
  * [18] M. F. Ghasemabadi, A. Iranmanesh, N. Ahanjideh, Characterizations of the simple group ${{}^{2}}D_{n}(3)$ by prime graph and spectrum, Monatsh. Math., 168:3-4 (2012), 347–361.
  * [19] M. F. Ghasemabadi, A. Iranmanesh, N. Ahanjideh, 2-recognizability of the simple groups $B_{n}(3)$ and $C_{n}(3)$ by prime graph, Bull. Iranian Math. Soc., 39:6 (2013), 1273–1281.
  * [20] D. Gorenstein, R. Lyons, R. Solomon, The classication of the finite simple groups. Providence, RI: Amer. Math. Soc., 3 (1998).
  * [21] I. B. Gorshkov, Characterization of groups with non-simple socle, arXiv:2011.15088 [math.GR].
  * [22] I. B. Gorshkov, A. N. Grishkov, On recognition by spectrum of symmetric groups, Sib. Electron. Math. Rep., 13 (2016), 111–121.
  * [23] I. B. Gorshkov, N. V. Maslova, Finite almost simple groups whose Gruenberg–Kegel graphs coincide with Gruenberg–Kegel graphs of solvable groups, Algebra and Logic, 57:2 (2018), 115–129.
  * [24] I. B. Gorshkov, N. V. Maslova, The group $J_{4}\times J_{4}$ is recognizable by spectrum, J. Algebra and Its Applications, doi: https://doi.org/10.1142/S0219498821500614, arXiv:1905.06258 [math.GR].
  * [25] I. Gorshkov, A. Staroletov , On Groups Having the Prime Graph as Alternating and Symmetric Groups, Commun. Algebr., 47:9 (2019), 3905–3914.
  * [26] M. A. Grechkoseeva, On Spectra of Almost Simple Extensions of Even-Dimensional Orthogonal Groups, Sib. Math. J., 59:4 (2018), 623–640.
  * [27] M. A. Grechkoseeva, S. V. Skresanov, On element orders in covers of $L_{4}(q)$ and $U_{4}(q)$, Sib. Electron. Math. Rep. 17 (2020), 585–589.
  * [28] M. A. Grechkoseeva, A. V. Vasil’ev, On the structure of finite groups isospectral to finite simple groups, J. Group Theory, 18:5 (2015), 741–759.
  * [29] M. A. Grechkoseeva, A. V. Vasil’ev, M. A. Zvezdina, Recognition of Symplectic and Orthogonal Groups of Small Dimensions By Spectrum, J. Algebra. Appl., 18:12 (2019), 1950230.
  * [30] M. A. Grechkoseeva, M. A. Zvezdina, On recognizability by spectrum of the groups $L_{4}(q)$ and $U_{4}(q)$ Sib. Math. J., 61:6 (2020), ??–??.
  * [31] A. Gruber, T. M. Keller, M. L. Lewis, K. Naughton, B. Strasser, A Characterization of the Prime Graphs of Solvable Groups, J. Algebra, 442:SI (2015), 397–422.
  * [32] K. W. Gruenberg, O. Kegel, Unpublished manuscript, 1975.
  * [33] K. W. Gruenberg, K. W. Roggenkamp, Decomposition of the augmentation ideal and of the relation modules of a finite group, Proc. London Math. Soc. (3), 31:2 (1975), 149–166.
  * [34] R. M. Guralnick, P. H. Tiep, Finite simple unisingular groups of Lie type, J. Group Theory, 6:3 (2003), 271–310.
  * [35] M. Hagie, The prime graph of a sporadic simple group, Comm. Algebra, 31:9 (2003), 4405–4424.
  * [36] G. Higman, Odd characterizations of finite simple groups: lecture notes. Michigan: University of Michigan, 1968. 77 p.
  * [37] N. Iiyori, H. Yamaki, Prime graph components of the simple groups of Lie type over the fields of even characteristic, Proc. Japan Acad. Ser. A. Math. Sci., 67:3 (1991), 82–83.
  * [38] N. Iiyori, H. Yamaki, Prime graph components of the simple groups of Lie type over the fields of even characteristic, J. Algebra, 155:2 (1993), 335–343; Corrigenda, J. Algebra, 181:2 (1996), 659.
  * [39] C. Jansen et al., An atlas of Brauer characters, Clarendon Press, Oxford, 1995.
  * [40] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, (Proc. of the Vienna Conference, Vienna, 1999), Contrib. General Algebra 12 (2000), 229–235.
  * [41] A. Khosravi, B. Khosravi, 2-recognizability by prime graph of $\mathop{\mathrm{PSL}}\nolimits(2,p^{2})$, Sib. Math. J., 49:4 (2008), 749–757.
  * [42] B. Khosravi, $n$-recognition by prime graph of the simple group $\mathop{\mathrm{PSL}}\nolimits_{2}(q)$, J. Algebra Appl., 7:6 (2008), 735–748.
  * [43] B. Khosravi, On the prime graph of a finite group, London Mathematical Society Lecture Note Series, 388 (2009), 424–428.
  * [44] B. Khosravi, B. Khosravi, B. Khosravi, On the prime graph of $\mathop{\mathrm{PSL}}\nolimits(2,p)$ where $p>3$ is a prime number, Acta Math. Hungar., 116:4 (2007), 295–307.
  * [45] B. Khosravi, B. Khosravi, B. Khosravi, Groups with the same prime graph as a CIT simple group, Houston J. Math., 33:4 (2007), 967–977 (electronic).
  * [46] B. Khosravi, B. Khosravi, B. Khosravi, A characterization of the finite simple group $L_{16}(2)$ by its prime graph, Manuscripta math., 126:1 (2008), 49–58.
  * [47] B. Khosravi, A. Z. Moghanjoghi, Quasirecognition by prime graph of some alternating groups, Int. J. Contemp. Math. Sci., 2:28 (2007), 1351–1358.
  * [48] A. S. Kondrat’ev, On the recognizability of sporadic simple groups $Ru$, $HN$, $Fi_{2}2$, $He$, $McL$, and $Co_{3}$ by the Gruenberg–Kegel graph, Trudy Inst. Mat. i Mekh. UrO RAN, 25:4 (2019), 79–87 (in Russian).
  * [49] A. S. Kondrat’ev, On the recognition of the sporadic simple groups $HS$, $J_{3}$, $Suz$, $O^{\prime}N$, $Ly$, $Th$, $Fi_{23}$, and $Fi_{24}$ by the Gruenberg–Kegel graph, Sib. Math. J., 61:6 (2020), ??–??.
  * [50] A. S. Kondrat’ev, Prime graph components of finite simple groups, Math. USSR Sb. 67 (1990), 235–247.
  * [51] A. S. Kondrat’ev, Gruenberg–Kegel graph of a finite group and its applicatuons, Algebra and Linear Optimization, Proc. of Internation in honor of 90th Birthday S. N. Chernikov, UB RAS: Ekaterinburg, 2002, 141–158 (in Russian).
  * [52] A. S. Kondrat’ev, Recognizability of groups $E_{7}(2)$ and $E_{7}(3)$ by prime graph, Proc. Steklov Inst. Math. (Suppl.), 289:suppl. 1 (2015), 139–145.
  * [53] A. S. Kondrat’ev and I. V. Khramtsov, On finite triprimary groups, Trudy Inst. Mat. i Mekh. UrO RAN 16:3 (2010), 150–158 (in Russian).
  * [54] A. S. Kondrat’ev and I. V. Khramtsov, On finite tetraprimary groups, Proc. Steklov Inst. Math. 279:suppl. 1 (2012), 43–61, https://doi.org/10.1134/S0081543812090040.
  * [55] A. S. Kondrat’ev and V. D. Mazurov, Recognizibility of alternating groups of prime degree by their element orders, Siberian Math. J. 41:2 (2000), 359–369.
  * [56] The Kourovka Notebook: Unsolved Problems in Group Theory. Editors: E. I. Khukhro and V. D. Mazurov. Sobolev Institute of Mathematics SB RAS, Novosibirsk, 2018.
  * [57] M. C. Lucido, The diameter of the prime graph of finite groups, J. Group Theory 2:2 (1999), 157–172.
  * [58] Y. V. Lytkin, On groups critical with respect to a set of natural numbers, Sib. Electron. Math. Rep. 10 (2013), 666–675.
  * [59] A. Mahmoudifar, Recognition by prime graph of the almost simple group $PGL(2;25)$, J. Linear and Topological Algebra, 5:1 (2016), 63–66.
  * [60] R. P. Martineau, On 2-modular representations of the Suzuki groups, Amer. J. Math. 94 (1972), 55–72.
  * [61] N. V. Maslova, On the coincidence of Gruenberg–Kegel graphs of a finite simple group and its proper subgroup, Proc. Steklov Inst. Math. (Suppl.), 288:suppl. 1 (2015), 129–141.
  * [62] N. V. Maslova, D. Pagon, On the realizability of a graph as the Gruenberg–Kegel graph of a finite group, Sib. Electron. Mat. Rep., 13 (2016), 89–100.
  * [63] N. V. Maslova, I. N. Belousov, N. A. Minigulov, Open questions formulated at the 13th School-Conference on Group Theory Dedicated to V. A. Belonogov’s 85th Birthday, Trudy Inst. Mat. i Mekh. UrO RAN, 26:3 (2020), 275–285 (in Russian).
  * [64] V. D. Mazurov, The set of orders of elements in a finite group, Algebra Logic, 33 (1994) 49–55.
  * [65] V. D. Mazurov, Characterizations of finite groups by sets of orders of their elements, Algebra and Logic, 36:1 (1997), 23–32.
  * [66] V. D. Mazurov, A characterizations of finite nonsimple groups by the set of orders of their elements, Algebra and Logic, 36:3 (1997), 182–192.
  * [67] V. D. Mazurov, Recognition of Finite Simple Groups $S_{4}(q)$ by Their Element Orders, Algebra and Logic, 41:2 (2002), 93–110.
  * [68] V. D. Mazurov, W. J. Shi, A criterion of unrecognizability by spectrum for finite groups, Algebra Logic, 51 (2012) 160–162.
  * [69] A. R. Moghaddamfar, W. J. Shi, The characterization of almost simple groups $PGL(2,p)$ by their element or
  * [70] Z. Momen, B. Khosravi, On r-recognition by prime graph of $B_{p}(3)$ where $p$ is an odd prime, Monatsh. Math., 166:2 (2012), 239–253.
  * [71] I. Schur, Über die Darstellung der endlichen Gruppen durch gebrochene lineare Substitutionen, J. reine angew. Math. 127 (1904), 20–50.
  * [72] W. Shi, A characteristic property of $A_{5}$, Journal of Southwest-China Teachers’ University, 2 (1986), p.11–14 (in Chinese).
  * [73] W. Shi, W. Yang, On finite groups with elements of prime power orders, Journal of Yunnan Education College, 1 (1986), p.2–10 (in Chinese). English translation by Dr. Jinbao Li: arXiv:2003.09445v1 [math.GR].
  * [74] W. Shi, A new characterization of the sporadic simple groups, in: Group theory, Proc. 1987 Singapore Group theory conf., Berlin-New York, Walter de Gruyter, 1989, 531—540.
  * [75] A. Staroletov, On Almost Recognizability By Spectrum of Simple Classical Groups, Int. J. Group Theory, 6:4 (2017), 7–33.
  * [76] A. M. Staroletov, On recognition of alternating groups by prime graph, Sib. Electron. Math. Rep., 14 (2017), 994–1010.
  * [77] W. B. Stewart, Groups having strongly self-centralizing 3-centralizers, Proc. London Math. Soc. 426:4 (1973), 653–680.
  * [78] M. Suzuki, On a class of doubly transitive groups, Ann. Math. 75:1 (1962), 105–145.
  * [79] A. V. Vasil’ev, On Connection Between the Structure of a Finite Group and the Properties of Its Prime Graph, Sib. Math. J. 46 (2005) 396–404.
  * [80] A. V. Vasil’ev, On Finite Groups Isospectral To Simple Classical Groups, J. Algebra, 423 (2015), 318–374.
  * [81] A. V. Vasil’ev, M. A. Grechkoseeva, V. D. Mazurov, Characterization of the finite simple groups by spectrum and order, Algebra and Logic, 48:6 (2009), 385–409.
  * [82] A. V. Vasiliev, E. P. Vdovin, An Adjacency Criterion for the Prime Graph of a Finite Simple Group, Algebr Logic, 44 (2005) 381–406.
  * [83] A. V. Vasil’ev, E. P. Vdovin, Cocliques of maximal size in the prime graph of a finite simple group, Algebra Logic, 50 (2011), 291–322.
  * [84] J. S. Williams, Prime graph components of finite groups, J. Algebra 69 (1981), 487–513.
  * [85] Robert Wilson [et. al.], Atlas of finite group representations, http:brauer.maths.gmul.ac.uk/Atlas/
  * [86] Samir Zahirović, Ivica Bošnjak and Rozália Madarśz, A study of enhanced power graphs of finite groups, J. Algebra Appl. 19 (2020), 2050062.
  * [87] A. V. Zavarnitsine, Recognition of finite groups by the prime graph, Algebra and Logic, 45:4 (2006), 220–231.
  * [88] A. V. Zavarnitsine, Uniqueness of the prime graph of $L_{16}(2)$, Sib. Electron. Math. Rep., 7 (2010), 119–121.
  * [89] A. V. Zavarnitsine, Finite groups with a five-component prime graph, Sib. Math. J., 54:1 (2013), 40–-46.
  * [90] A. V. Zavarnitsine, V. D. Mazurov, Element orders in coverings of symmetric and alternating groups, Algebra and Logic, 38:3 (1999), 159–170.
  * [91] M. R. Zinov’eva and V. D. Mazurov, On finite groups with disconnected prime graph, Proc. Steklov Inst. Math. (Suppl.), 283:suppl. 1 (2013), 139–145.
  * [92] K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. Phys. 3 (1892), 265–284.