arXiv:1605.08266v2 [] 14 Jul 2017

A CFSG-FREE ANALYSIS OF BABAI’S
QUASIPOLYNOMIAL GI ALGORITHM
LÁSZLÓ PYBER

Babai’s analysis of his algorithm [1] (corrected in [2]) uses the Classification of Finite Simple Groups (CFSG) in Section 8. In particular, he
uses Schreier’s Hypothesis (a well-known consequence of CFSG), which
states that the outer automorphism groups of finite simple groups are
solvable. We will make Babai’s bound worse, but still quasipolynomial,
and remove CFSG entirely from the analysis. Our short proof relies on
a little-known result of Wielandt [8].
More precisely, we give a CFSG-free proof of a weaker version of the
key group-theoretic result of Babai, Lemma 8.5 from [1], see Lemma 12.
It is acknowledged in [3] that our result is sufficient to make Babai’s
work CFSG-free.
All groups in this note are finite. Throughout log means logarithm
to the base 2. We use the following notation:
• |G| -the order of a group G;
• Sym(Ω) -the symmetric group on the set Ω;
• Alt(n) -the alternating group of degree n;
• For G < Sym(Ω), Gx denotes the pointstabiliser of a point x ∈
Ω (G will always be transitive and all pointstabilisers equivalent
as permutation groups);
• If G < Sym(Ω), and ∆ is a subset of Ω fixed by G, then the
image of the action of G on ∆ is called the permutation group
induced on ∆ by G, and written G∆ ;
• CompA (G) -the set of isomorphism types of abelian composition
factors of a group G. Note that we have CompA (G) ≤ log |G|.
For notation and definitions unexplained here and below see the
monograph of Dixon and Mortimer [6].
We will first prove a useful result for groups of odd order (without using even the Feit-Thompson theorem). We call the orbits of a
pointstabiliser in a transitive group suborbits. We need the following
basic lemma of Jordan (see [15, 18.2]):
The author was supported by the National Research, Development and Innovation Office (NKFIH) Grants K115799, ERC HU 15 118286.
1

2

LÁSZLÓ PYBER

Lemma 1. Let G be a primitive group of degree n and Gx a pointstabiliser. If a prime p divides |Gx | then p divides Gx ∆ for all suborbits
∆ of length at least 2.
Recall that the exponent of a group is the smallest common multiple
of the orders of its elements.
Lemma 2. Let G be a transitive group of degree n. If G has odd order
2
then the exponent of G is at most n(log n) .
Proof. We will actually prove the following claim:
Claim. The product π(G) of all different primes dividing |G| is at most
nlog n .
Since any element of G of prime power order has order at most n,
the claim implies our statement.
Assume first that G is primitive. Since G has odd order, G cannot
be doubly transitive. The smallest non-trivial
suborbit ∆ has size < n2 .

Lemma 1 implies that π(Gx ) = π Gx ∆ . It is clear that π(G) divides
log n2
≤ nlog n .
n · π(Gx ), hence by induction π(G) ≤ n · n2
Assume now that G is imprimitive. Let B1 be a minimal non-trivial
block of imprimitivity (of size b) and B1 , . . . , Bk the corresponding
system of blocks of imprimitivity. Then G permutes these blocks
transitively,
let K denote the kernel of this action. By induction

log k
π G/K ≤ k .
We may assume that K 6= 1. Then the minimality of B1 implies
that K acts transitively on each Bi , and the corresponding
 transitive
groups are permutation equivalent. Hence π(K) = π K B1 ≤ blog b .
Using kb = n we obtain that π(G) ≤ nlog n . This completes the
proof.

We now prove an easy result which implies that to obtain a polylogarithmic bound for CompA (G) in terms of the degree of the transitive
group G it is sufficient to obtain such a bound for CompA (Gx ) (where
Gx is a pointstabiliser).
Proposition 3. Let G < Sym(Ω) be a transitive group of degree n and
Gx a pointstabiliser. Then
CompA (G) \ CompA (Gx ) < log n.
Proof. Let G = G0 ⊲G1 ⊲G2 ⊲. . . be a composition chain of G. Then the
subgroups Gi ∩Gx form a subnormal chain Gx D G
G2 ∩Gx . . .
1 ∩Gx D 
∼
(possibly with repetitions). Now G G1 ≥ G1 · Gx G1 = Gx (G1 ∩ Gx )

A CFSG-FREE ANALYSIS

3




and similarly Gi Gi+1 ≥ Gi+1 ·(Gi ∩Gx ) Gi+1 ∼
= (Gi ∩Gx ) (Gi+1 ∩Gx )
for i ≥ 1.
If p is a prime
 not dividing n, then the product of the p-parts of
G
the orders i Gi+1 must
 be the same as the product of the p-parts
of the orders (Gi ∩ Gx ) (Gi+1 ∩ Gx ) . This implies that if G has a
composition factor of order p then Gx also has such a composition
factor. Our statement follows.

The following result of Wielandt, that appeared first in [8] (which
the author found in the insightful survey of Cameron [5]) explains why
we have to concentrate on pointstabilisers of transitive groups, rather
than on transitive groups themselves (see [5, p 110–111] for a more
detailed explanation).
Since Wielandt’s beautiful result is at the heart of our argument, we
will reproduce here his short proof from [8].
For this we need some more notation.
The orbits of G ≤ Sym(Ω) on Ω × Ω are called the orbitals of G
on Ω. For each orbital ∆ there is a paired orbital denoted ∆′ , where
(y, x) ∈ ∆′ if and only if (x, y) ∈ ∆. For each orbital ∆ of G and each
x ∈ Ω we define ∆(x) = {y ∈ Ω|(x, y) ∈ ∆}. Such sets are exactly
the suborbits of Gx . If ∆ and ∆′ are paired orbitals, then ∆(x) and
∆′ (x) are called paired suborbits. A suborbit ∆(x) is called self-paired
if ∆(x) = ∆′ (x). (To simplify notation we often denote ∆(x) by ∆.)
Lemma 4. (Wielandt) Let G < Sym(Ω) be a nonregular primitive
group and let ∆(x) be a Gx -orbit 6= {x}, let y be an element of ∆(x)
and let y ′ be an element of ∆′ (x), where ∆′ (x) is the Gx -orbit paired
with ∆(x). Let T (x) be the kernel of the action of Gx on ∆(x). Then all
composition factors of T (x) appear as composition factors of (Gx,y )∆(x)
′
or of (Gx,y′ )∆ (x) .
Proof. For a subgroup H of G, denote by H ∗ the smallest subnormal
subgroup of H such that every composition factor between H and H ∗
∆(x)
∆′ (x)
is a composition factor of Gx,y or of Gx,y′ ; H ∗ is a characteristic sub
∆(x)
group of H (Wielandt [14, Th. 13, p. 220]). Now Gx,y ∼
= Gx,y T (x)
and therefore G∗x,y = T (x)∗ . Similarly G∗x,y′ ∼
= U(x)∗ , where U(x) de′
notes the pointwise stabiliser of {x}∪∆ (x). We can choose the notation
so that ∆(x)g = ∆(xg ) for all x ∈ Ω, g ∈ G. Then ∆′ (x)g = ∆′ (xg )
and y ∈ ∆(x) implies x ∈ ∆′ (y) so G∗x,y = U(y)∗ . Hence T (x)∗ =
U(y)∗ ⊳ hGx , Gy i = G, so that T (x)∗ = 1 (since a non-trivial normal
subgroup of a primitive group must be transitive), and the theorem is
proved.


4

LÁSZLÓ PYBER

It was a great surprise to the present author that one can prove a
useful result for pointstabilisers of arbitrary transitive groups by an
elementary induction argument (for transitive groups themselves using induction is quite standard). However a paper of Isaacs [9], where
abelian pointstabilisers in transitive groups are shown to have a distinctive numerical property gave a strong indication that such an argument
may exist and may not rely on CFSG. (The theorem of Isaacs in [9] in
turn may be traced back to some results and questions in [4]). Note
also that Theorem 7 below is not very hard to prove using well-known
consequences of CFSG.
Definition 1. Let D be a direct product of the groups D1 , D2 , . . . , Dt .
A subdirect product subgroup of D is a subgroup G which projects
onto all the constituents D1 , D2 , . . . , Dt .
The following well-known result (see [13, Ch.2 (4.19)]) describes the
structure of subdirect product subgroups of two groups.
Lemma 5. Let G be a subdirect product subgroup of D = D1 × D2 .
Then
 setting N1 = D
 1 ∩ G and N2 = D2 ∩ G we have N1 × N2 ⊳ G, and
∼
G (N1 × N2 ) = D1 N1 ∼
= D2 N2 .
Proposition 6. The composition factors of G are among the composition factors of D1 , D2 , . . . , Dt .
Proof. Easy induction using Lemma 5.



The key result of this note is the following.
Theorem 7. Let G be a transitive permutation group of degree n and
Gx a pointstabiliser. Then CompA (Gx ) < 2(log n)2 .
The proof of Theorem 7 is based on two reduction lemmas: Lemma 8
and Lemma 10.
Definition 2. A group G < Sym(Ω) is called quasiprimitive if it is
transitive and each of its non-trivial normal subgroups are also transitive. Primitive permutation groups are quasiprimitive (see [10] for
more on quasiprimitive qroups).
Lemma 8 (Reduction for transitive groups). Let G be a transitive
imprimitive group of degree n. We have
CompA (Gx ) ≤ CompA (Xα ) + CompA (Yβ ) + log n,

where X and Y are certain transitive groups acting on sets of size
t ≥ 2 and m ≥ 2 respectively, where tm ≤ n, and Xα and Yβ are
pointstabilisers.

A CFSG-FREE ANALYSIS

5

Proof. a) Let us first assume that G is quasiprimitive but not primitive. Since G is not primitive Gx is not a maximal subgroup
of G. Consider a proper maximal subgroup M of G containing
Gx . Let N be the (unique) maximal normal subgroup of G contained in M. If N 6= 1, then the quasiprimitivity of G implies
that G = NGx ≤ M, a contradiction. Hence the (primitive)
representation of G on the cosets of M is faithful of degree, say,
t.
Consider now the representation of M on the cosets of Gx .
The kernel of this action is a normal subgroup K of Gx , hence all
composition factors of K appear among the composition factors of
M, which by the above is the pointstabiliser of a transitive group
of degree |G : M| = t. The “remaining”
 composition factors
of Gx are the composition factors of Gx K, which is clearly a
pointstabiliser of a transitive group of degree |M : Gx | = n/t.
b) Let us next assume that G is a transitive group which has a nontrivial intransitive normal subgroup N. The orbits of N form a
system of imprimitivity B = B1 , B2 , . . . , Bt of G. Denote by K
the kernel of the action of G on this system of blocks. Denote
by G̃ the image of this action and by G̃B̃ the stabiliser of the
point B̃. Clearly this stabiliser has index t in G̃. Let H be the
inverse image of this stabiliser G̃B̃ in G, a subgroup of index t
in G. It is clear that H contains KGb for an element b of B.
Since K is transitive on B we have |B| = |K : K ∩ Gb |. But
this is equal to |KGb : Gb | and therefore actually H = KGb .
Now H/K = KGb /K is isomorphic to Gb /(K ∩ Gb ) hence the
composition factors in this quotient of Gb are the composition
factors of G̃B̃ .
The remaining composition factors of Gb are the composition
factors of Kb . Let J be the kernel of the action of Kb on B. Now J
is also the kernel of the action of K on B hence a normal subgroup
of K. Note that K is a subdirect product subgroup of the t-th
direct power of some transitive group T of degree n/t = m.
Now Kb /J is permutation equivalent to a pointstabiliser in T .
By Proposition 6 the composition factors of J are among the
composition factors of T . By Proposition 3, at most log m of
the composition factors of T (hence J) do not occur among the
composition factors of a pointstabiliser in T , hence the same is
true for Kb .


6

LÁSZLÓ PYBER

Recall that the socle Soc(G) of a group G is the product of its minimal normal subgroups. The following is well-known (see also [1]).
Proposition 9.
(1) The socle is a direct product of simple groups.
(2) The socle of a primitive permutation group is a direct product
of isomorphic simple groups.
(3) If the socle of a primitive permutation group G is abelian then
it is elementary abelian of order ps = n and G Soc(G) embeds

2
into GL(s, p). In particular we have G Soc(G) < p(s ) .
Lemma 10 (Reduction for primitive groups). Let G be a primitive
group of degree n with a self-paired suborbit ∆. Then one of the following holds:
(1) CompA (Gx ) ≤ (log n)2
(2) CompA (Gx ) ≤ CompA (Py ) for some primitive permutation
group P acting on ∆ and some y ∈ ∆,
(3) CompA (Gx ) ≤ CompA (Xα ) + CompA (Yβ ) + 2 log n, where
X and Y are certain transitive groups acting on sets of size
t ≥ 2 and m ≥ 2 respectively, where tm ≤ |∆| ≤ n, and Xα
and Yβ are pointstabilisers.
Proof. We may assume that G is nonregular. Let ∆ be the smallest
non-trivial self-paired orbit of Gx . Let P denote the image of the action
of Gx on ∆. By Lemma 4
(∗)

CompA (Gx ) ⊆ CompA (P ) ∪ CompA (Py ).

Assume first that P is primitive. If Soc(P ) is abelian, then using
Proposition 9(3) it is easy to see that
If Soc(P ) is non (1) holds.

abelian, then CompA (P ) = CompA P Soc(P ) . Clearly Soc(P )·Py =
P , hence



P Soc(P ) ∼
= Py Py ∩ Soc(P ) .
In particular, CompA (P ) ⊆ CompA (Py ), and (∗) implies (2).
Assume next that P is imprimitive. Proposition 3 and (∗) imply
that
CompA (Gx ) ≤ CompA (Py ) + log n.
Applying Lemma 8 to P acting on ∆ we obtain (3).

The proof of Theorem 7. The proof of the theorem will be simple induction based on Lemma 8 and Lemma 10.
Let us first assume that G is primitive. If G has odd order then our
statement follows from the Claim in the proof of Lemma 2. Otherwise
G contains an element of order two, hence it has a self-paired suborbit
[6, 3.2.5], and we can apply Lemma 10.

A CFSG-FREE ANALYSIS

7

In case (1) and (2) of Lemma 10 our statement follows. In case
√
(3) we may assume that m ≥ t, and set k = nt . Note that k ≥ n
and t ≥ 2. We have 2(log(tk))2 = 2(log t)2 + 2(log k)2 + 4 log t log k ≥
2(log t)2 +2(log k)2 +2 log n ≥ CompA (Xα ) + CompA (Yβ ) +2 log n ≥
CompA (Gx ) . The inductive step follows.
The inductive step for transitive imprimitive groups (using Lemma 8)
is similar, but easier.

Next we will use Theorem 7 to give a CFSG-free proof of a weaker
version of the key group-theoretic result of Babai [1].
We will also rely on the following well-known fact.
Proposition 11. The sum of the first m primes is O(m2 log m).
See [12] for a recent reference concerning sharp bounds.
Here is the promised weaker version of Lemma 8.5 of [1].
Lemma 12. Let G be a primitive group of degree n. Assume that
ϕ : G → Alt(k) is an epimorphism, where k > (log n)5 . If k is large
enough then ϕ is an isomorphism; hence G ∼
= Alt(k).
Proof. Assume that N = ker(ϕ) is non-trivial. Then N is transitive and
∼
G/N
p= Alt(k) contains a cyclic subgroup C whose order is a product
of c k/ log k different primes (for some absolute constant c > 0). This
follows easily using Proposition 11.
The extension H of N by C p
is transitive (since N itself is transitive)
and we have CompA (H) ≥ c k/ log k, which contradicts Theorem 7
for k large enough.

Remark 13. Babai [1] proves the same statement for k ≥ max{8, 2 +
log n} using Schreier’s Hypothesis.
Remark 14. In January 2017 Helfgott has found an error in the “Splitor-Johnson” section of Babai’s paper [1]. This has been corrected in
a week by Babai. See [7] and [3] for the description of the correction.
This does not effect the use of the present paper in the analysis of
Babai’s algorithm.

Acknowledgments
We thank Laci Babai for finding a gap in the first version of this proof
and his enthusiasm in closing it. We also thank Colva Roney-Dougal
whose thesis provided a crucial hint, as to how to close the gap, and
Peter Cameron for drawing our attention to her thesis. The gap was
actually closed during a pleasant workshop at the ESI. Finally we thank

8

LÁSZLÓ PYBER

Bandi Szabó for his help in writing this paper and for an essential
simplification of the proof.
References
[1] L. Babai, Graph Isomorphism in Quasipolynomial Time, Arxiv: 1512.03547
[2] L. Babai, Graph Isomorphism in Quasipolynomial time (Extended Abstract),
Proc. 48th ACM STOC (2016), 684–697.
[3] L. Babai, Fixing the UPCC case of Split-or-Johnson, manuscript on Babai’s
homepage.
[4] L. Babai, A. J. Goodman, L. Pyber, Groups without faithful transitive representations of small degree, J. Algebra 195 (1997), 1–29
[5] P. J. Cameron, Suborbits in transitive permutation groups, in Combinatorics
Math. Centre Tracts No 57 (1975), pp98–129
[6] J. D. Dixon, B. Mortimer, Permutation Groups, Springer Grad. Texts in Math
vol 163, 1996
[7] H. A. Helfgott, Isomorphismes de graphes en temps quasi-polynomial (d’après
Babai et Luks, Weisfeiler-Leman...), arXiv:1701.04372
[8] D. G. Higman, Primitive rank 3 groups with a prime subdegree, Math. Z. 91
(1966), 70–86
[9] I. M. Isaacs, Abelian point stabilisers in transitive permutation groups, Proc.
AMS 130 (2001), 1923–1925
[10] C. E. Praeger, Quasiprimitivity: structure and combinatorial applications, Discrete Math. 264 (2003), 211–224
[11] C. M. Roney-Dougal, Permutation Groups with a Unique Nondiagonal SelfPaired Orbital, Ph.D. thesis, University of London, 2001.
[12] N. K. Sinha, On the asymptotic expansion of the first n primes, ArXiv:
1011.1667
[13] M. Suzuki, Group Theory I, Springer, 1982
[14] H. Wielandt, Eine Verallgemeinerung der invarianten Untergruppen, Math. Z.
45 (1939), 209–244
[15] H. Wielandt, Finite Permutation Groups, Acad. Press, New York 1964

MTA Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13–15,
H–1053, Budapest, Hungary
E-mail address: pyber.laszlo@renyi.mta.hu

