arXiv:1608.00131v2 [] 13 Oct 2016

Fibers of automorphic word maps and an application
to composition factors
Alexander Bors∗
October 14, 2016

Abstract
In this paper, we study the fibers of “automorphic word maps”, a certain generalization of word maps, on finite groups and on nonabelian finite simple groups
in particular. As an application, we derive a structural restriction on finite groups
G where, for some fixed nonempty reduced word w in d variables and some fixed
ρ ∈ (0, 1], the word map wG on G has a fiber of size at least ρ|G|d : No sufficiently
large alternating group and no (classical) simple group of Lie type of sufficiently high
rank can occur as a composition factor of such a group G.

1
1.1

Introduction
Motivation and main result

Word maps on groups have been studied intensely in recent years, resulting in substantial progress on interesting questions and a beautiful theory using tools from
various areas such as representation theory and algebraic geometry; interested readers are referred to the survey article [5].
Recall that a (reduced) word w in d variables X1 , . . . , Xd is an element of the free
group F (X1 , . . . , Xd ). Each such word gives, for each group G, rise to a word map
wG : Gd → G induced by substitution. Studying the fibers of wG means studying
the solution sets in Gd to equations of the form w = w(X1 , . . . , Xd ) = g for g ∈ G.
By Larsen and Shalev’s result [3, Theorem 1.1], for fixed w, the maximum number
of solutions to such an equation in a nonabelian finite simple group S is in o(|S|d )
∗
University of Salzburg, Mathematics Department, Hellbrunner Straße 34, 5020 Salzburg, Austria.
E-mail: alexander.bors@sbg.ac.at
The author is supported by the Austrian Science Fund (FWF): Project F5504-N26, which is a part of the
Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
2010 Mathematics Subject Classification: Primary: 20D05, 20D06, 20D45. Secondary: 15A03, 15A04,
20B30.
Key words and phrases: Finite groups, Word maps, Composition factors, Finite simple groups.

1

Alexander Bors

Automorphic word maps

as |S| → ∞. In particular, for each fixed number ρ ∈ (0, 1], for only finitely many
nonabelian finite simple groups S, wS has a fiber of size at least ρ|S|d .
Based on this, it is near-lying to ask what one can say more generally about the
nonabelian composition factors of a finite group G where the word map wG has a
fiber of size at least ρ|G|d . In order to be able to use [3, Theorem 1.1] for this,
it would be useful if one could somehow relate the maximum fiber size of wG with
the maximum fiber sizes of the word maps associated with w over the composition
factors of G. For example, it would be nice to have an inequality of the form Πw (G) ≤
Πw (N ) · Πw (G/N ) for all finite groups G and all normal subgroups N of G, where
Πw denotes the function that maps each finite group G to the maximum fiber size of
wG . Unfortunately, this is not the case, even if we assume that N is characteristic
in G; consider, for example, G = D2o , the dihedral group of order 2o, for some odd
integer o ≥ 3, N the unique cyclic subgroup of index 2 in G, and w = X12 .
In this paper, we will describe a way to circumvent these difficulties and provide
some strong restrictions on possible composition factors of a finite group G such
that Πw (G) ≥ ρ|G|d in the form of Theorem 1.1.2 below. First, we introduce some
constants:
Notation 1.1.1. Let w be a reduced word of length l ≥ 1 in d distinct variables. We
introduce the following constant, depending only on w:

M = M (d, l) := 1+2l(d+1)+(2l(d+1))2 +· · ·+(2l(d+1))2l+2 =

(2l(d + 1))2l+3 − 1
.
2l(d + 1) − 1

Furthermore, we set M ′ := M (l, l).
Our main result is the following (as usual, the “untwisted Lie rank” of a Lie type
group is the Lie rank of the corresponding untwisted group):
Theorem 1.1.2. Let w be a reduced word of length l ≥ 1 in d distinct variables.
Then for all ρ ∈ (0, 1] and all finite groups G such that the word map wG has a fiber
of size at least ρ|G|d , the following hold:
1. No alternating group of order larger than
max{⌈256l16 e16M

′ l−2

′

⌉!, ρ−16M }

is a composition factor of G.
2. No (classical) simple group of Lie type of untwisted Lie rank larger than
max{72(l + 1)2 l2 ,
is a composition factor of G.

p

72(l + 1)2 l2 log2 (ρ−1 )}

In other words, the list of potential composition factors for such a group G consists
of finitely many alternating groups, the sporadic groups, and all simple Lie type
groups of bounded rank.

2

Alexander Bors

1.2

Automorphic word maps

Main ideas and overview of the paper

The main idea for proving Theorem 1.1.2 is to make up for the above mentioned
“flaw” of the function Πw by replacing it by an evaluation-wise larger function Pw
which satisfies the inequality Pw (G) ≤ Pw (N ) · Pw (G/N ) at least when N is characteristic in G and study Pw instead. To this end, we generalize the notion of a word
map in a certain way.
Let us first fix some notation. For a fixed reduced word w in the d variables
X1 , . . . , Xd and of length l, write w = xǫ11 · · · xǫl l , where x1 , . . . , xl ∈ {X1 , . . . , Xd }
and ǫi = ±1. Denote by ι the unique function {1, . . . , l} → {1, . . . , d} such that for
i = 1, . . . , l, xi = Xι(i) . Thus for each group G, the word map wG is just the map
ǫl
ǫ1
.
Gd → G sending (g1 , . . . , gd ) 7→ gι(1)
· · · gι(l)
Definition 1.2.1. We introduce the following terminology and notation:
1. With notation as above, let G be a group, and let α1 , . . . , αl be automorphisms
(α ,...,αl )
is the map Gd → G sending
of G. The automorphic word map wG 1
(g1 , . . . , gd ) 7→ α1 (gι(1) )ǫ1 · · · αl (gι(l) )ǫl .

2. By Pw , we denote the function that maps each finite group G to the maxi(α ,...,αl )
, α1 , . . . , αl
mum size of a fiber of one of the automorphic word maps wG 1
automorphisms of G.
(α ,...,α )

l
is like wG , except that in the i-th factor of the l factor product
Hence wG 1
as which the evaluation wG (g1 , . . . , gd ) is defined, we additionally apply αi , one of l
(id,...,id)
= wG .
automorphisms fixed beforehand. In particular, wG
The approach of studying fibers of automorphic word maps will actually allow us
to prove the following stronger form of Theorem 1.1.2:

Theorem 1.2.2. Let w be a reduced word of length l ≥ 1 in d distinct variables and
M = M (w) as in Notation 1.1.1. Then for all ρ ∈ (0, 1] and all finite groups G with
Pw (G) ≥ ρ|G|d , the following hold:
1. No alternating group of order larger than
max{⌈256l16 e16M

′ l−2

′

⌉!, ρ−16M }

is a composition factor of G.
2. No (classical) simple group of Lie type of untwisted Lie rank larger than
max{72(l + 1)2 l2 ,
is a composition factor of G.

p

72(l + 1)2 l2 log2 (ρ−1 )}

We now give an overview of the rest of this paper:
1. In Section 2, we prove our main lemma, Lemma 2.1, which includes the inequality Pw (G) ≤ Pw (N ) · Pw (G/N ) for characteristic subgroups N of G. It
also includes the observation that the element of G having the largest fiber size
under any automorphic word map on G is the identity element of G.

3

Alexander Bors

Automorphic word maps

2. Having gained a basic understanding of automorphic word maps in Section
2, the next goal is to extend, as far as necessary, Larsen and Shalev’s result
[3, Theorem 1.1] on fibers of word maps on nonabelian finite simple groups
mentioned above to fibers of automorphic word maps. This will be done in
Section 3, see Theorem 3.1.2.
3. Section 4 consists of the proof of Theorem 1.2.2 based on the results developed
so far.
4. Finally, in Section 5, we give some concluding remarks concerning further extensions of Larsen and Shalev’s techniques to automorphic word maps and an
interesting consequence thereof.

1.3

Notation

We denote by N the set of natural numbers (including 0) and by N+ the set of
positive integers. Euler’s constant is denoted by e, which is to be distinguished
from the variable e. The image and preimage of a set M under a function f are
denoted by f [M ] and f −1 [M ] respectively. When fi : Xi → Yi for i = 1, Q
. . . , n, then
n
we
denote
by
f
×
·
·
·
×
f
the
product
of
the
maps
f
,
i.e.,
the
map
1
n
i
i=1 Xi →
Qn
i=1 Yi , (x1 , . . . , xn ) 7→ (f1 (x1 ), . . . , fn (xn )). The n-fold product of a map f with
itself is denoted by f (n) . These last two notations will be used in the proofs of
Lemma 4.4 and of the implication “Conjecture 5.2⇒ Conjecture 5.3” in Section 5.
For a group G and an element g ∈ G, we denote by conj(g) the conjugation by g
on G, i.e., the inner automorphism of G of the form x 7→ gxg −1 . The automorphism
group of G is denoted by Aut(G), and the inner automorphism group of G by Inn(G).
For a finite set X, we denote by SX the symmetric group on X; for a positive integer
n, Sn and An denote the symmetric and alternating group on {1, . . . , n} respectively.
For a prime power q, the finite field with q elements is denoted by Fq . For n ∈ N+
and a prime power q, Matn (q) denotes the ring of (n × n)-matrices over Fq . For a
vector space ∆ over some field F , we denote by EndF (∆) the endomorphism ring of
∆, i.e., the ring of F -linear maps ∆ → ∆.
At some points in our arguments, we will not consider all possible automorphic
(α ,...,αl )
over some finite group G, but only those where the αi are from
word maps wG 1
a certain subset of Aut(G). Also, we sometimes want to talk about the maximum
fiber size of a particular element of G under an automorphic word map or about
the proportion of a fiber of an (automorphic) word map associated with w within
the entire argument set Gd , rather than the actual size of the fiber. We therefore
introduce the following notation that supplements the notation already introduced:
Notation 1.3.1. Let G be a finite group, w a reduced word of length l in d distinct
variables, A ⊆ Aut(G).
1. We set πw (G) := Πw (G)/|G|d and pw (G) := Pw (G)/|G|d . Note that always
πw (G), pw (G) ∈ (0, 1].
(A)

2. We denote by Pw (G, g) the maximum size of the fiber of g under an automor(α ,...,αl )
, where αi ∈ A for i = 1, . . . , l, and we set
phic word map of the form wG 1

4

Alexander Bors

Automorphic word maps

(A)

(A)

(Aut(G))

Pw (G) := maxg∈G Pw (G, g) (so that Pw
(A)

(G) = Pw (G)).

(A)

(A)

(A)

3. Moreover, we set pw (G, g) := Pw (G, g)/|G|d and pw (G) := Pw (G)/|G|d .

2

Basic results on automorphic word maps

In this section, we prove the following lemma containing some basic bounds on fiber
sizes of automorphic word maps:
Lemma 2.1. Let w be a reduced word, G a finite group, A a subgroup of Aut(G)
containing Inn(G). Furthermore, let N be a characteristic subgroup of G, and denote
by
• ind(A) the subgroup of Aut(G/N ) consisting of all automorphisms of G/N induced by some automorphism from A,
• res(A) the subgroup of Aut(N ) consisting of all restrictions of automorphisms
from A to N ,
• π : G → G/N the canonical projection.
Then the following hold:
(A)

(ind(A))

(res(A))

1. For all g ∈ G, Pw (G, g) ≤ Pw
(G/N, π(g)) · Pw
(N, 1), or in terms
(A)
(ind(A))
(res(A))
of proportions, pw (G, g) ≤ pw
(G/N, π(g)) · pw
(N, 1).
(A)

(A)

(A)

2. For all g ∈ G, Pw (G, g) ≤ Pw (G, 1), or in terms of proportions, pw (G, g) ≤
(A)
(A)
(A)
pw (G, 1). Hence Pw (G, 1) = Pw (G).
(A)

(ind(A))

(res(A))

3. Pw (G) ≤ Pw
(G/N ) · Pw
(res(A))
(ind(A))
pw
(G/N ) · pw
(N ).

(A)

(N ), or in terms of proportions, pw (G) ≤

Proof. For (1): As before, we write w = xǫ11 · · · xǫl l with ǫi ∈ {±1}, x1 , . . . , xl ∈
{X1 , . . . , Xd } and ι : {1, . . . , l} → {1, . . . , d} such that xi = Xι(i) . Furthermore, fix
an l-tuple (α1 , . . . , αl ) of elements of A such that the size of the fiber Φ of g under
(A)
(α ,...,αl )
equals Pw (G, g). For i = 1, . . . , l, denote by α̃i the automorphism of G/N
wG 1
induced by αi .
We will establish the inequality by a coset-wise counting argument. More precisely, we will show the following two assertions, which together imply the inequality:
1. The number of cosets of N d in Gd having nonempty intersection with Φ is at
(ind(A))
most Pw
(G/N, π(g)).
(res(A))

2. Φ intersects each coset of N d in Gd in at most Pw

(N, 1) many elements.

For the first assertion, let (g1 , . . . , gd ) ∈ Φ. In other words,
α1 (gind(1) )ǫ1 · · · αl (gind(l) )ǫl = g.
Applying π to both sides of Formula (1) yields

5

(1)

Alexander Bors

Automorphic word maps

α˜1 (π(gind(1) )) · · · α̃l (π(gind(l) )) = π(g),
(α˜ ,...,α̃ )

1
l
. The
and thus that (π(g1 ), . . . , π(gd )) lies in the fiber of π(g) under wG/N
assertion follows immediately from this.
For the second assertion, fix a coset C of N d in Gd , say C = N d (g1 , . . . , gd ). We
(res(A))
want to show that |C ∩ Φ| ≤ Pw
(N, 1). Of course, we may assume that C ∩ Φ is
nonempty, and w.l.o.g. even that the coset representative (g1 , . . . , gd ) which we fixed
lies in Φ. Hence Formula (1) holds. We now characterize those (n1 , . . . , nd ) ∈ N d
(α ,...,αl )
(n1 g1 , . . . , nd gd ) = g as well, i.e., such that
such that wG 1

g = α1 (nι(1) gι(1) )ǫ1 · · · αl (nι(l) gι(l) )ǫl = t1 · · · tl ,

(2)

where
ti =

(

αi (nι(i) )ǫi αi (gι(i) )ǫi , if ǫi = +1,
αi (gι(i) )ǫi αi (nι(i) )ǫi , if ǫi = −1.

Note that under the assumed Formula (1), Formula (2) is equivalent to the following:
1 = g · g −1 = t1 t2 · · · tl · αl (gι(l) )−ǫl · · · α2 (gι(2) )−ǫ2 α1 (gι(1) )−ǫ1 .

(3)

We now transform the product expression on the RHS of Formula (3) without changing its value as follows: The product has a unique subproduct of the
form αl (gι(l) )ǫl wl αl (gι(l) )−ǫl (where wl is either empty or equal to αl (nι(l) )ǫl , depending on whether ǫl = 1 or ǫl = −1). Replace this subproduct by the expression conj(αl (gι(l) )ǫl )(w1 ). The resulting product expression has a unique subproduct of the form αl−1 (gι(l−1) )ǫl−1 wl−1 αl−1 (gι(l−1) )−ǫl−1 . Replace this subproduct
by conj(αl−1 (gι(l−1) )ǫl−1 )(wl−1 ) and distribute the application of the automorphism
conj(αl−1 (gι(l−1) )ǫl−1 ) onto the single factors of the expression wl−1 . Continuing in
(β ,...,β )

l
(n1 , . . . , nd ),
this fashion, we eventually receive an expression of the form wN 1
where each βi is the restriction to N of an element of A, namely of the composition
of some inner automorphism of G with αi ; see also Example 2.2 for an illustration.
For (2): This follows by setting N := G in point (1) of this lemma.
For (3): By points (1) and (2), we have

(A)
(ind(A))
(res(A))
P(A)
(G/N, π(1)) · Pw
(N, 1)
w (G) = Pw (G, 1) ≤ Pw
(res(A))
= P(ind(A))
(G/N ) · Pw
(N ),
w

using that ind(A) resp. res(A) contains Inn(G/N ) resp. Inn(N ).
Example 2.2. We illustrate the transformations of expressions described in the proof
of Lemma 2.1(1) by the following example: Say w = [X1 , X2 ] = X1 X2 X1−1 X2−1 .
Then Formula (1) becomes

6

Alexander Bors

Automorphic word maps

α1 (g1 )α2 (g2 )α3 (g1 )−1 α4 (g2 )−1 = g,
and Formula (2) becomes
g = α1 (n1 g1 )α2 (n2 g2 )α3 (n1 g1 )−1 α4 (n2 g2 )−1
= α1 (n1 )α1 (g1 )α2 (n2 )α2 (g2 )α3 (g1 )−1 α3 (n1 )−1 α4 (g2 )−1 α4 (n2 )−1 .
Together, this yields
1 = g · g −1

= α1 (n1 )α1 (g1 )α2 (n2 )α2 (g2 )α3 (g1 )−1 α3 (n1 )−1 · α4 (g2 )−1 α4 (n2 )−1 α4 (g2 )

· α3 (g1 )α2 (g2 )−1 α1 (g1 )−1

= α1 (n1 )α1 (g1 )α2 (n2 )α2 (g2 ) · α3 (g1 )−1 α3 (n1 )−1 (conj(α4 (g2 )−1 ) ◦ α4 )(n2 )−1 α3 (g1 )

· α2 (g2 )−1 α1 (g1 )−1

= α1 (n1 )α1 (g1 )α2 (n2 )α2 (g2 ) · conj(α3 (g1 )−1 )(α3 (n1 )−1 (conj(α4 (g2 )−1 ) ◦ α4 )(n2 )−1 )

· α2 (g2 )−1 α1 (g1 )−1

= α1 (n1 )α1 (g1 )α2 (n2 )α2 (g2 ) · (conj(α3 (g1 )−1 ) ◦ α3 )(n1 )−1

· (conj(α3 (g1 )−1 α4 (g2 )−1 ) ◦ α4 )(n2 )−1 · α2 (g2 )−1 α1 (g1 )−1

= α1 (n1 )α1 (g1 )α2 (n2 ) · (conj(α2 (g2 )α3 (g1 )−1 ) ◦ α3 )(n1 )−1

· (conj(α2 (g2 )α3 (g1 )−1 α4 (g2 )−1 ) ◦ α4 )(n2 )−1 · α1 (g1 )−1

= α1 (n1 ) · (conj(α1 (g1 )) ◦ α2 )(n2 ) · (conj(α1 (g1 )α2 (g2 )α3 (g1 )−1 ) ◦ α3 )(n1 )−1

· (conj(α1 (g1 )α2 (g2 )α3 (g1 )−1 α4 (g2 )−1 ) ◦ α4 )(n2 )−1

(α ,conj(α1 (g1 ))◦α2 ,conj(α1 (g1 )α2 (g2 )α3 (g1 )−1 )◦α3 ,conj(α1 (g1 )α2 (g2 )α3 (g1 )−1 α4 (g2 )−1 )◦α4 )

= wN 1

(n1 , n2 ),

where in the last expression, all automorphisms are understood to be restricted
to N .

3 On fibers of automorphic word maps on nonabelian finite simple groups
3.1 Larsen and Shalev’s result and the main result of
this section
The following theorem is an equivalent reformulation of [3, Theorem 1.1]:
Theorem 3.1.1. For each nonempty and reduced word w in d distinct variables,
there exist constants N (w), η(w) > 0 such that for all nonabelian finite simple groups
S with |S| ≥ N (w), the inequality Πw (S) ≤ |S|d−η(w) holds.

7

Alexander Bors

Automorphic word maps

The proof of this theorem in [3] is split into three parts (note that the sporadic
groups can be ignored here, as the fiber size bound only needs to be shown for large
enough S):
• First, the bound is established for large enough alternating groups by means of
a certain combinatorial construction.
• Next, the bound is established for all simple Lie type groups of sufficiently high
rank, where the lower bound on the rank is so large that only classical groups
need to be considered in this case. As Larsen and Shalev say themselves, the
argument is conceptually similar to the one for alternating groups.
• Finally, the simple Lie type groups of bounded rank are treated by means of an
argument using results of algebraic geometry.
It turns out that Larsen and Shalev’s arguments in the first two cases can be
modified to prove the following, which is the main result of this section:
Theorem 3.1.2. Let w be a reduced word of length l ≥ 1 in d distinct variables, and
M = M (w) as in Notation 1.1.1. Then the following hold:
1. For all n ∈ N+ with n ≥ 256l16 e16M d−2 , we have Pw (An ) ≤ |An |d−1/(16M ) .

2. For all simple Lie type groups S of untwisted Lie rank at least 72(d + 1)2 l2 , we
2
have Pw (S) ≤ |S|d−1/(72(d+1)l ) .
Whether such bounds can also be established for the simple Lie type groups of
“small” rank is open; see Section 5 for some more remarks on this.

3.2

Reduction of Theorem 3.1.2 to Theorem 3.2.6

Similarly to [3], the main part of the argument for Theorem 3.1.2 will not provide
(A)
upper bounds on Pw (S) for the simple groups S in question directly, but on Pw (G),
where G is a finite group “closely related with S” and A a certain subgroup of Aut(G).
That we can do this without loss of generality is justified by the following lemma, a
modification of [3, Lemma 2.1], which served the same purpose:
Lemma 3.2.1. Let w be a nonempty reduced word in d distinct variables, G and H
infinite classes of finite groups, N, η > 0. Assume that for each H ∈ H with |H| ≥ N ,
(A(H))
there is associated a subgroup A(H) ≤ Aut(H) such that Pw
(H) ≤ |H|d−η (and
note that this implies η ≤ d). Set ǫ := η/(2(1 + d − η)) > 0. Finally, assume that
there exists C > 0 such that for all G ∈ G with |G| ≥ C, the following exist:
• an H ∈ H such that |H| ≤ |G|1+ǫ ,

∼ H ′ /K (we
• characteristic subgroups K and H ′ of H with K ≤ H ′ such that G =
say that G is a characteristic section of H) and such that every automorphism
of G can be induced by the restriction to H ′ of a suitable automorphism of H
from A(H).
Then the following holds: For all G ∈ G with |G| ≥ max{N, C}, Pw (G) ≤
|G|d−η/2 .

8

Alexander Bors

Automorphic word maps

Proof. Let G ∈ G with |G| ≥ max{N, C}. Fix H ∈ H with |H| ≤ |G|1+ǫ containing
characteristic subgroups K and H ′ as described in the assumptions. We assume
w.l.o.g. that G = H ′ /K (not just isomorphic). Note that we have in particular that
(A(H))
|H| ≥ |G| ≥ N , so that Pw
(H) ≤ |H|d−η by assumption.
We want to bound the fiber sizes of automorphic word maps over G. To this end,
(α˜ ,...,α̃l )
equals Pw (G)
fix α˜1 , . . . , α̃l ∈ Aut(G) and g ∈ G such that the fiber size of wG 1
(note that since we are not assuming that A(H) contains Inn(H), we also cannot
assume w.l.o.g. here that g = 1, as would otherwise follow from Lemma 2.1(2)). Fix
h ∈ H ′ projecting onto g ∈ G = H ′ /K, and fix α1 , . . . , αl ∈ A(H) ≤ Aut(H) such
that for i = 1, . . . , l, (αi )|H ′ induces α̃i on G.
((α1 )

(α ,...,α )

′ ,...,(αl )

′)

|H
l
,
Since each fiber of wH 1
, and thus in particular each fiber of wH ′ |H
(α˜1 ,...,α̃l )
d−η
can be expressed as
has size at most |H| , and since the fiber of g under wG
′
the image under the canonical projection H → G of a disjoint union of at most |G|ǫ

((α1 )|H ′ ,...,(αl )|H ′ )

many fibers of wH ′

(α˜ ,...,α̃l ) −1

Pw (G) = |(wG 1

)

, we get that

[{g}]| ≤ |G|ǫ · |H|d−η ≤ |G|ǫ+(1+ǫ)(d−η) = |G|d−η/2 ,

where the last equality is by definition of ǫ.
In accordance with our announcement before Lemma 3.2.1, below, we will prove
Lemmata 3.2.3 and 3.2.5, which allow us to reduce the proof of Theorem 3.1.2 to the
proof of a theorem concerning fibers of automorphic word maps in slightly different
classes of groups, Theorem 3.2.6. For example, for the alternating groups, these
“closely related” groups will be just the symmetric groups. To make the formulations
of the lemmata shorter, let us first introduce the following terminology:
Definition 3.2.2. Let w be a nonempty reduced word in d distinct variables, and
let N, η > 0. Furthermore, let G be a class of finite groups and A a function that
maps each G ∈ G to a subgroup A(G) ≤ Aut(G). We say that G is (A, N, η)-nice for
w, or that (A, N, η) is a niceness tuple of G for w, if and only if for all G ∈ G with
(A(G))
|G| ≥ N , we have Pw
(G) ≤ |G|d−η .
The following lemma allows us to reduce Theorem 3.1.2(1) to the study of automorphic word map fibers in symmetric groups:
Lemma 3.2.3. Let w be a nonempty reduced word in d distinct variables. Assume
that for some N ≥ |A7 | = 2520 and some η > 0, the class of finite symmetric groups is (Aut, N, η)-nice for w. Then the class of finite alternating groups is
(Aut, max{N, 22(1+d−η)/η+1 }, η/2)-nice for w.
Proof. Set ǫ := η/(2(1 + d − η)). We want to apply Lemma 3.2.1 with H the class of
finite symmetric groups and G the class of finite alternating groups. Let us first find
C0 > 0 such that for all An with |An | ≥ C0 , |Sn | ≤ |An |1+ǫ . Taking logarithms, the
inequality turns into log n! ≤ (1 + ǫ)(log n! − log 2), which is equivalent to log n! ≥
log 2 · (1 + ǫ)/ǫ = log 2(1 + 1/ǫ) = log 2(1 + 2(1 + d − η)/η). Hence we want that n! ≥
21+2(1+d−η)/η) , which is satisfied if |An | ≥ 21+2(1+d−η)/η) , and so C0 := 21+2(1+d−η)/η)

9

Alexander Bors

Automorphic word maps

does the job. Since by Lemma 3.2.1, we also need to ensure that every automorphism
of An is induced by an automorphism of Sn , we need to set C := max{2520, C0 }.
With this choice for C, an application of Lemma 3.2.1 yields that a possible niceness tuple of the class of finite alternating groups for w is (Aut, max{N, C}, η/2) =
(Aut, max{N, 2520, C0 }, η/2) = (Aut, max{N, 21+2(1+d−η)/η }, η/2), as required.
As for the classical groups of Lie type X(q) with which we are concerned in
Theorem 3.1.2(2), the groups “closely related” with them which we will study are,
just as in [3, beginning of Section 3], the isometry groups of trivial, perfect symmetric,
perfect anti-symmetric or perfect Hermitian pairings (depending on the case) of a
vector space over either the field Fq or (only in the Hermitian case) its degree 2
extension Fq2 . Set E := Fq , and moreover, set F := E except in the Hermitian case,
where F := Fq2 .
In the notation of §2.1 in Kleidman and Liebeck’s book [2], the classical simple Lie
type group X(q) is Ω and is the projective version of a subgroup Ω of the associated
isometry group, which is denoted by I. I, in turn, is contained as a normal subgroup
in some group A which (by its conjugation action on I) may be viewed as a subgroup
of Aut(I) and is just the group Γ of collineations over I except when I = GLn (q)
is the isometry group of a trivial form, in which case A is the subgroup of Aut(I)
generated by Γ and the inverse-transpose automorphism of I. For later purposes, we
set A(I) := A.
It follows from [2, Theorem 2.1.4] that if the untwisted Lie rank of Ω is at least
5 (this is just to exclude the groups C2 (2f ) = Sp4 (2f ) and D4 (q) = Ω+
8 (q)), then
every automorphism of Ω is induced by the restriction to Ω of an automorphism of
I from A = A(I), as required in Lemma 3.2.1. Furthermore, as Larsen and Shalev
observe in [3, beginning of Section 3], we always have |I| ≤ (q − 1)(r + 1)|Ω|, where
r is the untwisted Lie rank of Ω and q = |F |. They also observe that for every ǫ > 0,
|Ω|ǫ ≥ (r + 1)(q − 1) if r is sufficiently large. This “sufficiently large” can be made
explicit:
Lemma 3.2.4. For all ǫ > 0, the following holds: With notation as above, if r ≥ ǫ−1 ,
then |Ω|ǫ ≥ (r + 1)(q − 1), and so |I| ≤ |Ω|1+ǫ .
Proof. This follows from |Ω|1/r ≥ (r +1)(q −1), which can be easily verified in each of
the six cases Ω = Ar (q), Br (q), Cr (q), Dr (q), 2 Ar (q), 2 Dr (q) using the known formula
for |Ω|.
We can now show the following:
Lemma 3.2.5. Let N, η > 0 and G a class of finite groups consisting only of the
isometry groups I associated with the members of a subclass H of the class of finite
classical simple Lie type groups Ω of untwisted Lie rank at least max{5, 2(1+d−η)/η}.
Assume that G is (A, N, η)-nice for w. Then H is (Aut, N, η/2)-nice for w.
Proof. By the assumption on the untwisted Lie rank of members of H, the assumptions of Lemma 3.2.1 with C := 1 are satisfied; more precisely, fixing an element
Ω ∈ H:

10

Alexander Bors

Automorphic word maps

• Since the untwisted Lie rank of Ω is at least 5, by the observations before Lemma
3.2.4, considering the associated isometry group I ∈ G, Ω is a characteristic
section of I such that every automorphism of Ω “comes from” an automorphism
from A(I) ≤ Aut(I).

• Furthermore, since the untwisted Lie rank of Ω is at least 2(1 + d − η)/η = ǫ−1 ,
by Lemma 3.2.4, we also have |I| ≤ |Ω|1+ǫ .
Hence we are done by an application of Lemma 3.2.1.
We now give the aforementioned theorem to which Theorem 3.1.2 reduces:
Theorem 3.2.6. Let w be a reduced word of length l ≥ 1 in d distinct variables, and
let M be as in Notation 1.1.1. Then the following hold:
1. The class of finite symmetric groups is (Aut, ⌈256l16 e16M d−2 ⌉!, 1/(8M ))-nice for
w.
2. The class of isometry groups associated with the finite simple groups of Lie type
of untwisted Lie rank at least 72(d + 1)2 l2 is (A, 1, 1/(36(d + 1)l2 ))-nice for w.
Let us actually derive Theorem 3.1.2 from this.

Proof of Theorem 3.1.2 using Theorem 3.2.6. For (1): Applying Lemma 3.2.3, we
get from Theorem 3.2.6(1) that the class of finite alternating groups has the following
niceness tuple for w:
(Aut, max{⌈256l16 e16M d−2 ⌉!, 21+2(1+d−η)/η }, 1/(16M )),
where η = 1/(8M ). It is not difficult to check that the second term in the
maximum expression in the second entry of the tuple is smaller than the first term,
and we are done.
For (2): By Lemma 3.2.5 and Theorem 3.2.6(2), we only need to check that for
η = 1/(36(d + 1)l2 ), we have 2(1 + d − η)/η ≤ 72(d + 1)2 l2 , which is elementary.

3.3 First part of the proof of Theorem 3.2.6: Symmetric groups and isometry groups other than general linear
groups
We now turn to the proof of Theorem 3.2.6, which as mentioned before, is a modification of an argument by Larsen and Shalev from [3]. Let us first make some general
observations which will be used in the proof.
Note that each of the abstract groups G with which Theorem 3.2.6 deals can
actually be viewed as a permutation group, acting on a set ∆, in a natural way:
each symmetric group Sn through its natural action on the set {1, . . . , n}, and each
isometry group through its action on the corresponding vector space. Larsen and
Shalev also exploited this fact, and their argument consisted essentially in investigating to what extent a relation of the form w(g1 , . . . , gd ) = g for g ∈ G fixed imposes
restrictions on g1 , . . . , gd ∈ G when viewed as maps ∆ → ∆.

11

Alexander Bors

Automorphic word maps

In our setting, this gets more complicated because we are actually considering not
a word equation in g1 , . . . , gd , but a word equation in various images of the gi under
fixed automorphisms of G from some subgroup A(G) ≤ Aut(G). Hence it would be
useful if, from some single piece of mapping information of the form α(gi )(x) = y,
α ∈ A(G) and x, y ∈ ∆, we could derive such a condition on gi itself. It turns out
that this is actually possible for the G with which we are concerned except for the
case G = GLn (q), which will require some separate treatment.
In this subsection, we deal with the G not isomorphic with any GLn (q).
Notation 3.3.1. We introduce the following notation:
1. As G = Sn with n ≥ 7 is complete, for each automorphism α of G, there is
a unique σ ∈ G such that α = conj(σ). We set t(α) := σ −1 ∈ Sn = S∆ with
∆ = {1, . . . , n}.

2. Let G = I be the isometry group of either a perfect symmetric, perfect antisymmetric or perfect Hermitian pairing of a finite vector space ∆ = Fm
q e , where
e = 1 in the symmetric and anti-symmetric case and e = 2 in the Hermitian
case. By the definition of A(I) ≤ Aut(I) above, it is clear that every element α ∈ A(I) is of the form conj(U ) ◦ aut(σ), where U ∈ I and aut(σ) is
a field automorphism of I, induced by an automorphism σ of Fqe . σ also induces a permutation perm(σ) on ∆, namely the map ∆ → ∆, (x1 , . . . , xm ) 7→
(σ(x1 ), . . . , σ(xm )). We set t(α) := (U ◦ perm(σ))−1 ∈ S∆ .

The point behind Notation 3.3.1 is that in each of the cases considered, the
automorphism α of G can be seen as the restriction of the conjugation by t(α)−1 ∈ S∆
to the subgroup G of S∆ . Hence the following is clear:
Lemma 3.3.2. Let G be Sn for some n ≥ 7 resp. an isometry group as in Notation
3.3.1(2). Then for every α ∈ Aut(G) (resp. α ∈ A(G)), for every g ∈ G, and for
all x, y ∈ ∆, the set on which G acts naturally, we have α(g)(x) = y if and only if
g(t(α)(x)) = t(α)(y).
At last, we are now ready to discuss the proofs of Theorem 3.2.6(1) and of Theorem 3.2.6(2) except for general linear groups; we will present these proofs one after
the other.
Proof of Theorem 3.2.6(1). Let G = Sn with n ≥ 256l16 e16M d−2 . We need to show
that Pw (G) ≤ |G|d−1/(8M ) . By Lemma 2.1(2), we know that Pw (G) = Pw (G, 1),
so we only need to bound the maximum size of the fiber Φ of 1 = id under an
automorphic word map on G. Hence fix automorphisms α1 , . . . , αl ∈ Aut(G) ∼
= G,
and, as usual, write w = xǫ11 · · · xǫl l with ǫi ∈ {±1}, x1 , . . . , xl ∈ {X1 , . . . , Xd } and
ι : {1, . . . , l} → {1, . . . , d} such that xi = Xι(i) .
We associate with each fixed d-tuple ~g = (g1 , . . . , gd ) ∈ Gd a certain metric
(α ,...,αl )
d~g 1
on ∆ = {1, . . . , n}, as follows: For y, z ∈ ∆, if z can be obtained from y
through a finite number of applications of permutations on ∆, each of one of the two
forms
• αi (gj )±1 , where i ∈ {1, . . . , l} and j ∈ {1, . . . d}, or

12

Alexander Bors

Automorphic word maps

• t(αi )±1 , where i ∈ {1, . . . , l},
(α ,...,α )

l
then d~g 1
(y, z) is defined as the smallest number of such function applications
which it takes to pass from y to z. If, on the other hand, z cannot be obtained from
(α ,...,αl )
(α ,...,αl )
y in this way, we set d~g 1
(y, z) := n. It is easy to check that d~g 1
really is
a metric on ∆.
We call elements y, z ∈ ∆ independent if and only if there do not exist α, β ∈
{α1 , . . . , αl } such that t(α)(y) = t(β)(z), and else we call them dependent. Furtherǫl−j+1
more, we define uj := xl−j+1
· · · xǫl l for j = 0, . . . , l (the terminal segments of w), so

ǫ

(α

,...,α )

l−j
l
that xl−j
uj = uj+1 . Finally, we set νj := (uj )G l−j+1
(~g ) ∈ G, j = 0, . . . , l, and
L := ⌊n/(4M )⌋.
Now let ~z = (z1 , . . . , zL ) denote an ordered L-tuple of elements ∆. We consider
two sets X and X ′ :

(α1 ,...,αl )

X := {(~g , ~z) ∈ Gd × ∆L |∀i 6= j : d~g

(zi , zj ) > 2l + 2 and

∀i : |{zi , ν1 (zi ), . . . , νl (zi )}| ≤ l},
(α1 ,...,αl )

X ′ := {(~g , ~z) ∈ Gd × ∆L |∀i 6= j : d~g

(4)

(zi , zj ) > 2l + 2 and

∀i : ∃j1 , j2 ∈ {0, . . . , l} : (j1 6= j2 , and νj1 (zi ) and νj2 (zi )
are dependent)}.

(5)

Note that the second condition, |{zi , ν1 (zi ), . . . , νl (zi )}| ≤ l, in Formula (4) just
means that two of the elements zi , ν1 (zi ), . . . , νl (zi ) are equal, which is a stronger
condition than the second condition in Formula (5). Hence X ⊆ X ′ . Our goal is to
determine an upper bound on |X|, and to this end, we bound |X ′ |.
We begin by fixing two L-tuples (a1 , . . . , aL ) and (b1 , . . . , bL ) of non-negative
integers such that ai < bi ≤ l for all i, as well as two L-tuples (γ1 , . . . , γL ) and
(δ1 , . . . , δL ) with entries from the set {α1 , . . . , αl }. There are fewer than l4L choices
for this.
For each such choice, we count only the elements (~g , ~z) of X ′ such that for all
i ≤ L, the elements zi , ν1 (zi ), . . . , νbi −1 (zi ) ∈ ∆ are pairwise independent, while
the dependence relation t(γi )(νbi (zi )) = t(δi )(νai (zi )) holds. There are fewer than
nb1 +···+bL ways of choosing ordered tuples Z1 , . . . , ZL with entries from ∆ and of
length b1 , . . . , bL respectively such that the entries of each tuple are pairwise independent. For fixed (Z1 , . . . , ZL ), we count only elements of XZ′ 1 ,...,ZL , i.e., only elements
of X ′ as specified above such that additionally, (zi , ν1 (zi ), . . . , νbi −1 (zi )) = Zi for each
i = 1, . . . , L.
Now the distance condition in Formula (5) implies that if any coordinate of Zi
is in dependence with any coordinate of Zj for i 6= j, then XZ′ 1 ,...,ZL = ∅. We may
therefore assume that coordinates of Zi and Zj , i 6= j, are always independent, a
feature which we call the inter-independence of the Zi .
Note that for each i ∈ {1, . . . , L} and each j ∈ {1, . . . , bi }, we get the following
condition on one of the functions g1 , . . . , gd : ∆ → ∆:

13

Alexander Bors

Automorphic word maps

• if ǫl−j+1 = +1 and ι(l − j + 1) = k, then αl−j+1 (gk )(νj−1 (zi )) = νj (zi ), or
equivalently (by Lemma 3.3.2) gk (t(αl−j+1 )(νj−1 (zi ))) = t(αl−j+1 )(νj (zi )).
• if ǫl−j+1 = −1 and ι(l − j + 1) = k, then αl−j+1 (gk )(νj (zi )) = νj−1 (zi ), or
equivalently gk (t(αl−j+1 )(νj (zi ))) = t(αl−j+1 )(νj−1 (zi )).
Let us introduce some terminology for conditions of the form f (x) = y, where
f is a variable standing for a function ∆ → ∆ and x, y ∈ ∆ are fixed. We call x
the argument and y the image in the condition f (x) = y. Call two such conditions
f (x1 ) = y1 and g(x2 ) = y2 independent if and only if either f and g are distinct
variables or f = g and x1 6= x2 . Two conditions that are not independent are called
dependent. Finally, the conditions f (x1 ) = y1 and g(x2 ) = y2 are called contradictory
if and only if f = g, x1 = x2 and y1 6= y2 .
Equipped with this terminology, we note that for fixed i, either are two of the
bi conditions on the gk derived above contradictory (so that XZ′ 1 ,...,ZL = ∅ in this
case as well), or the conditions are pairwise independent. To see this, note that
if the conditions are not pairwise independent, then since we are assuming that
zi , ν1 (zi ), . . . , νbi −1 (zi ) are pairwise independent elements of ∆ (in the sense defined
before Formula (4)), the existing pair of dependent conditions is unique, and one
of the two conditions has an image of the form t(α)(νj (zi )) with 1 ≤ j ≤ bi − 1,
and the other condition is gk (t(αl−bi +1 )(νbi (zi ))) = t(αl−bi +1 )(νbi −1 (zi )). Now since
no two consecutive terms in the sequence xǫl l , . . . , xǫ11 are mutually inverse in the
corresponding free group, we must have j < bi − 1, but this, again by the pairwise
independence of zi , ν1 (zi ), . . . , νbi −1 (zi ), shows that the images in the two conditions
cannot be equal, and so the conditions are contradictory, as we wanted to show.
We may thus assume that for fixed i, the bi conditions listed above are pairwise
independent, and the inter-independence of the Zi then guarantees us that actually
all the b1 + · · · + bL conditions described above are pairwise independent. As the
number of elements of XZ′ 1 ,...,Zl is bounded from above by the number of d-tuples of
functions ∆ → ∆ satisfying all the b1 + · · · + bL conditions above, we conclude that
|XZ′ 1 ,...,Zl | ≤ ndn−b1 −···−bL . It follows that
|X| ≤ |X ′ | ≤ l4L ndn .

(6)
(α ,...,αl )

To get an upper bound on the size of Φ, the fiber of id under wG 1
note that for each ~g ∈ Gd lying in that fiber, we have
(α1 ,...,αL )

({~g } × ∆L ) ∩ X = {(~g , ~z) ∈ {~g } × ∆L | ∀i 6= j : d~g

, from this,

(zi , zj ) > 2l + 2}.
(α ,...,α )

l
Now the ball B2l+2 (z) of radius 2l + 2 with respect to the metric d~g 1
around
any z ∈ ∆ has, by definition of M , cardinality at most M . Furthermore, by definition
of L, LM < n/4. Hence if we select z1 , . . . , zL ∈ ∆ iteratively so that for each
j = 1, . . . , L,

(α1 ,...,αl )

zj ∈ {z ∈ ∆ | ∀i < j : d~g

(zj , zi ) > 2l + 2},

then the number of possibilities for zj is at least

14

Alexander Bors

Automorphic word maps

|∆ \
It follows that

j−1
[
i=1

B2l+2 (zi )| ≥ n/4.

|({~g } × ∆L ) ∩ X| ≥ (n/4)L .
Hence we also have a lower bound on the cardinality of X:
|X| ≥ |(Φ × ∆L ) ∩ X| ≥ |Φ| · (n/4)L .

(7)

Combining Formula (7) with the upper bound on |X| from Formula (6), we conclude that
|Φ| ≤ (n/4)−L l4L ndn
√
= ( 2l)4L ndn−L
√
≤ ( 2l)n/M · n1+(d−1/(4M ))n .

(8)

From the explicit Stirling-like bound n! ≥ (n/e)n (which, as noted in [6], is an
immediate consequence of the Taylor expansion of the exponential function), it is
clear from Formula (8) that |Φ| ≤ |G|d−1/(8M ) as long as
√
( 2l)n/M · n1+(d−1/(4M ))n ≤ (n/e)n(d−1/(8M )) ,

which is equivalent to
√
( 2l)1/M · ed−1/(8M ) · n1/n+d−1/(4M ) ≤ nd−1/(8M ) .

(9)

Now
note that our assumption n ≥ 256l16 e16M d−2 = (2l2 )8 e16M d−2 is equivalent
√ 1/M
to ( 2l)
· ed−1/(8M ) ≤ n1/(16M ) . Hence by Formula (9), all that we need to
finish the proof is to verify that n1/n+d−3/(16M ) ≤ nd−1/(8M ) , which is equivalent to
n ≥ 16M , and this is certainly true by our assumption on n.
For the other proof, we require the following lemma, which is essentially [3, Lemma
3.2]:
Lemma 3.3.3. Let G be the isometry group, acting naturally on a finite vector
space ∆, associated with a classical finite simple group of Lie type S = X(q). Set
E := Fq , and denote by F the finite field such that ∆ is an F -vector space (recall
that either F = E or, in the Hermitian case, F is a quadratic extension of E). Set
n := dimE (∆), and let v1 , . . . , vk be E-linearly independent vectors in V such that
2
n ≥ 2k + 2. Then | StabG (v1 , . . . , vk )| ≤ q k +k−kn · |G|.
Proof of Theorem 3.2.6(2) except for general linear groups. Let G be the isometry
group of either a perfect symmetric, perfect anti-symmetric or perfect Hermitian
pairing on a finite F -vector space ∆. In the first two cases, set E := F , and in the
Hermitian case, let E be the unique subfield of F such that [F : E] = 2. Furthermore,

15

Alexander Bors

Automorphic word maps

set q := |E| and n := dimE (∆) as well as m := dimF (∆) = n/e (with e as in Notation
3.3.1(2)), so that w.l.o.g. ∆ = Fm
q e and Notation 3.3.1(2) is applicable. Finally, fix
α1 , . . . , αl ∈ A(G).
Under these assumptions, we will actually show something stronger than what
is asserted in Theorem 3.2.6(2) for all isometry groups (including the general linear
groups), namely that if n ≥ 216l2 , then the size of the fiber Φ of 1G = id under
2
(α ,...,αl )
is at most |G|d−1/(72l ) (note that it is sufficient to consider that fiber by
wG 1
Lemma 2.1(2), as A(G) contains Inn(G)). As before, the argument is a modification
of a proof of Larsen and Shalev, namely of [3, proof of Proposition 3.3]. Compared
to their situation, we have the advantage that we only need to consider the fiber
of id, not of any isometry with an eigenvalue of multiplicity at least n/3, so that
some parts of the construction even get simpler, while others get more complicated
to make them still work for automorphic word maps.
Let ~g = (g1 , . . . , gd ) denote a d-tuple of elements of G. We define uj and νj by
the same formulas as in the proof of Theorem 3.2.6(1) above. Furthermore, we set
L := ⌊n/(9l2 )⌋ and let ~z = (z1 , . . . , zL ) denote an L-tuple of elements of ∆. We define
the lexicographic order ≺ on the set {1, . . . , L} × {0, . . . , l} through (i′ , j ′ ) ≺ (i, j)
if and only if i′ < i, or i = i′ and j ′ < j. Finally, we define
X := {(~g , ~z) ∈ Gd × ∆L | ∀i : (zi ∈
/ Span(i′ ,j ′ )≺(i,0),k=1,...,l t(αk )(νj ′ (zi′ )) and

νl (vi ) ∈ Span(i′ ,j ′ )≺(i,l),k=1,...,l t(αk )(νj ′ (zi′ )))}, (10)

where here and in the rest of this proof, for a subset A ⊆ ∆, Span A denotes the
E-span of A inside ∆.
For each (~g , ~z) ∈ X, we define bi to be the smallest positive integer such that
νbi (zi ) ∈ Span(i′ ,j ′ )≺(i,bi ),k=1,...,l t(αk )(νj ′ (zi′ )).

(11)

Note that 1 ≤ bi ≤ l, and so b1 + · · · + bL ≤ lL. We make Formula (11) more
explicit by fixing ai,i′ ,j ′ ,k ∈ E = Fq such that
X

νbi (zi ) =

ai,i′ ,j ′ ,k t(αk )(νj ′ (zi′ )).

(12)

(i′ ,j ′ )≺(i,bi ),k=1,...,l

There are fewer than q l

2 L2

lL ways in which the ai,i′ ,j ′ ,k and bi can be chosen:

• precisely lL ways for the choice of bi ,
• and less than the following number of ways for the choice of the scalars ai,i′ ,j ′ ,k
from E = Fq :
q l(b1 +(l+b2 )+(2l+b3 )+···+((L−1)l+bL )) ≤ q l(lL+l·L(L−1)/2) = q l

2 L(1+(L−1)/2)

< ql

2 L2

.

Furthermore, there are fewer than q n(b1 +···+bL ) possibilities for the sequence of
sequences

16

Alexander Bors

Automorphic word maps

z = (z1 , . . . , νb1 −1 (z1 ); z2 , . . . , νb2 −1 (z2 ); . . . ; zl , . . . , νbL −1 (zL ))
such that none of the vectors in the sequence lies in the E-span of all the vectors
obtained by applying one of the t(αk ), k = 1, . . . , l, to one of the previous vectors in
the sequence.
We estimate the number of elements (~g , ~z) of X for fixed choices of ai,i′ ,j ′ ,k , bi and
z. Note that ~z is already fixed now as a part of z, so we need to bound the number
of matching ~g = (g1 , . . . , gd ) ∈ Gd . Say αk = conj(Uk ) ◦ aut(σk ) for k = 1, . . . , l,
where Uk ∈ G and σk is an automorphism of F = Fqe . Note that by the definition
of t(αk ) in Notation 3.3.1(2), the map t(αk ) : ∆ → ∆ is F -semilinear (in the sense
of [2, bottom of p. 9]); more precisely, we have, for all v, w ∈ ∆ and all λ ∈ F = Fqe :
t(αk )(v + w) = t(αk )(v) + t(αk )(w) and t(αk )(λ · v) = σk−1 (λ) · t(αk )(v). Also, note
that if λ ∈ E, then σk−1 (λ) ∈ E as well.
We get the following b1 + · · · + bL conditions on the gk :
For each i = 1, . . . , L:
• for each j = 1, . . . , bi − 1:

– if ǫl−j+1 = +1 and ι(l − j + 1) = k: αl−j+1 (gk )(νj−1 (zi )) = νj (zi ), which by
Lemma 3.3.2 is equivalent to gk (t(αl−j+1 )(νj−1 (zi ))) = t(αl−j+1 )(νj (zi )).
– if ǫl−j+1 = −1 and ι(l − j + 1) = k: αl−j+1 (gk )(νj (zi )) = νj−1 (zi ), which by
Lemma 3.3.2 is equivalent to gk (t(αl−j+1 )(νj (zi ))) = t(αl−j+1 )(νj−1 (zi )).

• if ǫl−bi +1 = +1 and ι(l − bi + 1) = k, then
X

αl−bi +1 (gk )(νbi −1 (zi )) =

ai,i′ ,j ′ ,o νj ′ (zi′ ),

(i′ ,j ′ )≺(i,bi ),o=1,...,l

which by Lemma 3.3.2 and the semilinearity of the t(αk ) is equivalent to
X

gk (t(αl−bi +1 )(νbi −1 (zi ))) =

−1
(ai,i′ ,j ′ ,o ) t(αl−bi +1 )(νj ′ (zi′ )).
σl−b
i +1

(i′ ,j ′ )≺(i,bi ),o=1,...,l

• if ǫl−bi +1 = −1 and ι(l − bi + 1) = k, then
αl−bi +1 (gk )(

X

ai,i′ ,j ′ ,o νj ′ (zi′ )) = νbi −1 (zi ),

(i′ ,j ′ )≺(i,bi ),o=1,...,l

which is equivalent to

gk (

X

−1
(ai,i′ ,j ′ ,o ) t(αl−bi +1 )(νj ′ (zi′ ))) = t(αl−bi +1 )(νbi −1 (zi )).
σl−b
i +1

(i′ ,j ′ )≺(i,bi ),o=1,...,l

Like in the proof of Theorem 3.2.6(1), we now argue that this system of conditions
of the form gk (v) = w is either contradictory (i.e., not satisfiable for any choice of
the gk in EndF (∆)) or the conditions are independent, meaning here that for each

17

Alexander Bors

Automorphic word maps

k, the set of all vectors appearing as arguments in one of the conditions concerning
gk is E-linearly independent.
Indeed, assume that for some k, the set of argument vectors for gk is E-linearly
dependent. Note that the lexicographical order ≺ which we defined on {1, . . . , L} ×
{0, . . . , l} also induces a linear order on the conditions involving the variable gk ,
as each such condition is by definition associated with a pair (i, j) ∈ {1, . . . , L} ×
{0, . . . , l} in an injective way (for a condition as described in the last two bullet
points above, this pair is (i, bi )). By means of this linear order, list the conditions
involving gk as follows: gk (v1 ) = w1 , gk (v2 ) = w2 , . . . , gk (vtk ) = wtk . Since the set
{v1 , . . . , vtk } is E-linearly dependent by assumption, there exists u ∈ {2, . . . , tk } such
that vu ∈ Span{v1 , . . . , vu−1 }. Note that if the system of conditions is satisfiable
through a suitable choice of g1 , . . . , gd ∈ EndF (∆), then this implies that likewise
wu ∈ Span{w1 , . . . , wu−1 }. We will now argue that this is not the case.
By choice of z, the assumption that vu ∈ Span{v1 , . . . , vu−1 } implies that gk (vu ) =
w
as described in the third bullet point above, with vu =
Pu must be a condition
−1
σ
′
′
(i ,j )≺(i,bi ),o=1,...,l l−bi +1 (ai,i′ ,j ′ ,o ) t(αl−bi +1 )(νj ′ (zi′ )) and wu = t(αl−bi +1 )(νbi −1 (zi ))
(and thus ǫl−bi +1 = −1). Using that no two consecutive terms in the sequence
xǫl l , . . . , xǫ11 are mutually inverse in the corresponding free group, we get that none of
the conditions gk (v1 ) = w1 , . . . , gk (vu−1 ) = wu−1 is associated with the pair (i, bi −1),
and the assertion that wu ∈
/ Span{w1 , . . . , wu−1 } now follows again by choice of z.
Hence we may assume w.l.o.g. that the above described b1 + · · · + bL conditions
on the gk are independent, so that by Lemma 3.3.3 and the convexity of the function
r 7→ r 2 + r, we see that there are no more than
2 +(b +···+b )−(b +···+b )n
1
1
L
L

q (b1 +···+bL )

|G|d

elements of X, subject to the choices of ai,i′ ,j,k , bi and z. Hence
|X| ≤ lL q l

2 L2 +2(b +···+b )2
1
L

|G|d ≤ lL q l

2 L2 +2l2 L2

|G|d = lL q 3l

2 L2

|G|d .

(13)

On the other hand, if ~g ∈ Gd lies in Φ, then for all ~z ∈ ∆L , (~g , ~z) is an element of
X if and only if for all i = 1, . . . , L, the condition
zi ∈
/ Span(i′ ,j ′ )≺(i,0),k=1,...,l t(αk )(νj ′ (zi′ ))

(14)

is satisfied. Now for each i, the span on the RHS of Formula (14) has E-dimension
less than l2 L ≤ n/9 ≤ n − 1 and thus is a proper E-subspace of ∆. It follows that
in each step of iteratively fixing an L-tuple (z1 , . . . , zL ) ∈ ∆L according to Formula
(14), we have at least q n−1 many choices for zi . Hence the number of pairs (~g , ~z) ∈ X
with ~g ∈ Φ fixed is at least q L(n−1) , and it follows that
|X| ≥ |Φ| · q L(n−1) .

(15)

Combining Formulas (13) and (15), we get that
|Φ| ≤ lL q 3l

2 L2 −L(n−1)

≤ qn · qn

2

|G|d ≤ ln/(9l ) q 3l

2 (1/(27l2 )−1/(18l2 ))

2 ·n2 /(81l4 )−n/(9l2 )·n/2

|G|d = q n−n

18

2 /(54l2 )

|G|d
2

2

|G|d = (q n )1/n−1/(54l ) |G|d

Alexander Bors

Automorphic word maps
2

≤ (q n )1/(216l

2 )−1/(54l2 )

2

2

2

|G|d = (q n )−1/(72l ) |G|d ≤ |G|d−1/(72l ) ,
2

where in the last step, we used that |G| ≤ q n , which in the symmetric and antisymmetric cases is trivial since G ≤ GLn (q) then, and in the Hermitian case, it follows
from |G| = | GUn (q)| = q n(n−1)/2 (q n − (−1)n )(q n−1 − (−1)n−1 ) · · · (q 2 − 1)(q + 1), see,
for example, [1, p. x].

3.4 Second part of the proof of Theorem 3.2.6: General
linear groups
As mentioned before, for the general linear groups G = GLn (q), the argument used
for the other isometry groups from Theorem 3.2.6(2) needs to be modified. This
is because the automorphisms of G which can be written as conj(U ) ◦ aut(σ) for
some U ∈ G and σ ∈ Aut(Fq ) only form an index 2 subgroup, hitherto denoted by
B(GLn (q)) = B(G), in A(G). A representative for the other coset of B(G) in A(G)
is the inverse-transpose automorphism τ : U 7→ (U −1 )t = (U t )−1 . This also means
that it is not possible in general to rewrite a condition of the form α(g)(v) = w with
α ∈ A(G) equivalently into one of the form g(t(α)(v)) = t(α)(w) as before. However,
it is easy to see that we can at least rewrite each such condition equivalently into one
of two possible forms:
Lemma 3.4.1. Let G = GLn (q) for some n ∈ N+ and prime power q, and let
∆ := Fnq , an Fq -vector space on which G acts naturally. Furthermore, let α ∈ A(G),
g ∈ G and x, y ∈ ∆. Then the following hold:
1. If α ∈ B(G), say α = conj(U ) ◦ σ, then setting t(α) := (U ◦ perm(σ))−1 ∈ S∆
just as in Notation 3.3.1(2), we have that α(g)x = y is equivalent to g t(α)(x) =
t(α)(y).

2. If α ∈ A(G) \ B(G), say α = β ◦ τ with β = conj(U ) ◦ σ, then α(g)x = y is
equivalent to gt t(β)(y) = t(β)(x).
Proof. The argument for point (1) is like the one for Lemma 3.3.2: that α can be
viewed as the restriction of the inner automorphism conj(t(α)−1 ) : S∆ → S∆ to
G ≤ S∆ .
As for point (2), note that
α(g)x = y ⇔ β((gt )−1 )x = y ⇔ β(g t )−1 x = y ⇔ β(g t )y = x ⇔ g t t(β)(y) = t(β)(x),
as required.
In view of this, the following Lemma will act as a substitute for Lemma 3.3.3:
Lemma 3.4.2. Let n ∈ N+ , q a prime power, r1 , r2 ∈ N with r1 , r2 ≤ n. Let
(1)
(1)
(1)
(1) (2)
(2)
(2)
(2)
(1)
(1)
v1 , . . . , vr1 , w1 , . . . , wr1 , v1 , . . . , vr2 , w1 , . . . , wr2 ∈ Fnq such that v1 , . . . , vr1
(2)

(2)

are Fq -linearly independent and v1 , . . . , vr2 are Fq -linearly independent. Then the
(1)
(1)
(2)
(2)
number of g ∈ Matn (q) such that gvi = wi for i = 1, . . . , r1 and gt vj = wj for
j = 1, . . . , r2 is at most q n

2 −(r

1 +r2 )n+r1 r2

.

19

Alexander Bors

Automorphic word maps
(1)

Proof. Fix T ∈ GLn (q) such that vi = T −1 ei for i = 1, . . . , r1 , where ei denotes the
i-th “standard basis vector” of Fnq (which has i-th entry 1 and all other entries 0).
(1)

Then for i = 1, . . . , r1 , the condition gvi

(1)

= wi

is equivalent to

(1)

hei = yi ,
(1)

(16)

(1)

where h := T gT −1 and yi := T wi . Furthermore, for j = 1, . . . , r2 , the condi(2)
(2)
tion gt vj = wj is equivalent to
(2)

ht xj
(2)

(2)

(2)

= yj ,

(2)

(17)

(2)

where xj := T t vj and yj := (T −1 )t wj . Instead of counting the number of
g ∈ GLn (q) satisfying the r1 + r2 many mapping conditions from the assumptions, we
count the number of h ∈ GLn (q) satisfying all the equivalently rewritten conditions
from Formulas (16) and (17).
(1)
To this end, note that each of the conditions hei = yi , i = 1, . . . , r1 , completely
determines one of the first r1 many columns of the matrix h.
(2)
(2)
Note further that, since the xj = T t vj , j = 1, . . . , r2 , are Fq -linearly independent, there exist indices 1 ≤ t1 < t2 < · · · < tr2 ≤ n such that for j = 1, . . . , r2 , a
(2)
(2)
suitable Fq -linear combination of x1 , . . . , xr2 is a vector zj whose ij -th coordinate
is 1 and whose ik -th coordinate for k ∈ {1, . . . , r2 } \ {j} is 0. Hence the conditions
(2)
(2)
ht xj = yj , j = 1, . . . , r2 , together imply conditions of the form
ht zj = uj ,

(18)
(2)

(2)

where uj is a suitable linear combination of y1 , . . . , yr2 . However, by the conditions from Formula (18), the rows number t1 , . . . , tr2 of h can be expressed as Fq -linear
combinations of the rows of h whose number is not from the set {t1 , . . . , tr2 }.
Combining the two statements about how the conditions affect coefficients from
h, we see that h is completely determined by the conditions from Formulas (16) and
(17) if we additionally fix the coefficients of h that lie neither in one of the first r1
many columns nor in one of the rows number t1 , . . . , tr2 of h. As there are precisely
2
n2 − (r1 + r2 )n + r1 r2 such coeffcients of h, there are at most q n −(r1 +r2 )n+r1 r2 many
h ∈ GLn (q) that satisfy the conditions from Formulas (16) and (17), as required.
Proof of Theorem 3.2.6(2) for general linear groups. Let G = GLn (q), n ≥ 72(d +
1)2 l2 , and fix automorphisms α1 , . . . , αl ∈ A(G). We want to show that the size of
2
(α ,...,αl )
is at most |G|d−1/(36(d+1)l ) . As the argument
the fiber Φ of 1G = id under wG 1
is a modification of the one for the other isometry groups given at the end of the last
subsection, we will only indicate at which points the argument needs to be altered
here:
• Instead of L := ⌊n/(9l2 )⌋, we set L := ⌊n/(3(d + 1)l2 )⌋ here.

• As we said at the beginning of this subsection, we cannot write αk = conj(Uk ) ◦
aut(σk ) anymore in general, but we can write αk = conj(Uk ) ◦ aut(σk ) ◦ τ ak ,
where ak ∈ {0, 1}.

20

Alexander Bors

Automorphic word maps

• Accordingly, we use Lemma 3.4.1 for the equivalent reformulation of the mapping conditions on the gk . In those cases where the automorphism αk occurring
in the condition involves τ (i.e., ak = 1), the “mapping direction” in the equivalent reformulation of the condition is turned around. Hence even with our
careful choice of z, we cannot guarantee anymore that for each k = 1, . . . , d, the
argument vectors in the various reformulated conditions involving either gk or
gkt are linearly independent. However, this is not even necessary, since Lemma
3.4.2, which we want to apply in order to get an upper bound on the number of
possibilities for ~g, only requires that each of the two sets of argument vectors in
conditions involving gk and gkt separately be linearly independent, which is still
the case as long as the system of b1 + · · · + bL conditions is not contradictory,
by an analogous argument.
• Hence if we denote, for k = 1, . . . , d, the number of rewritten conditions involv(k)
(k)
ing gk by r1 and the number of those conditions involving gkt by r2 , then an
application of Lemma 3.4.2 yields that the number of elements of X, subject
to the choices of ai,i′ ,j,k , bi and z, is at most
q dn

2 −(b +···+b )n+r (1) r (1) +···+r (d) r (d)
1
L
1
2
1
2

≤ q dn

2 −(b +···+b )n+dl2 L2
1
L

.

Hence we get the following upper bound on |X| here:
|X| ≤ lL q l

2 L2 +dn2 +dl2 L2

= lL q (d+1)l

2 L2

2

(q n )d .

Now |G| = | GLn (q)| = (q n − 1)(q n − q) · · · (q n − q n−1 ) ≥ (q n−1 )n = q n(n−1) , and
2
2
so q n ≤ |G|n/(n−1) = |G|1+1/(n−1) ≤ q n /(n−1) · |G|. Therefore,
|X| ≤ lL q (d+1)l

2 L2 +dn2 /(n−1)

|G|d .

(19)

The lower bound on |X| is still the same as in Formula (15).

• Note that since we are assuming that n ≥ 72(d + 1)2 l2 , we have
2d + 1
1
1
−
≤−
.
2
n
18(d + 1)l
36(d + 1)l2

(20)

Indeed, Formula (20) is equivalent to n ≥ 36(2d+1)(d+1)l2 , and 36(2d+1)(d+
1)l2 ≤ 36(2d + 2)(d + 1)l2 = 72(d + 1)2 l2 .
Hence by combining the upper and lower bound on |X|, we get the following:
|Φ| ≤ lL q (d+1)l

2 L2 −L(n−1)+dn2 /(n−1)
2

≤ ln/(3(d+1)l ) q (d+1)l
2

≤ q n · (q n )(d+1)l
2

= (q n )1/(9(d+1)l

|G|d

2 n2 /(9(d+1)2 l4 )−n/(3(d+1)l2 )·n/2+2nd

2 /(9(d+1)2 l4 )−1/(6(d+1)l2 )+2d/n

2 )−1/(6(d+1)l2 )+(2d+1)/n

2

2

= (q n )(2d+1)/n−1/(18(d+1)l ) |G|d

21

|G|d

|G|d

|G|d

Alexander Bors

Automorphic word maps
2

2

2

≤ (q n )−1/(36(d+1)l ) |G|d ≤ |G|d−1/(36(d+1)l ) ,
where the second-to-last ≤ (i.e., the first ≤ in the last row) is by Formula (20).

4

Proof of Theorem 1.2.2

For proving Theorem 1.2.2, we are supposed to exclude certain nonabelian finite
simple groups as composition factors of a finite group G satisfying the condition
pw (G) ≥ ρ for some fixed nonempty reduced word w and ρ ∈ (0, 1].
Assume that S is a nonabelian composition factor of G. By Lemma 2.1(2),
we know that pw (G) ≤ pQ
w (N ) · pw (G/N ) whenever N is characteristic in G. It
follows that ρ ≤ pw (G) ≤ ri=1 pw (Fi ) ≤ mini=1,...,r pw (Fi ), where F1 , . . . , Fr are the
characteristic composition factors of G, i.e., the factors in any principal characteristic
series of G (see [4, p. 65]), counted with multiplicities. As each Fi is characteristically
simple and thus of the form Sini for some finite simple group Si and ni ∈ N+ by [4,
3.3.15, p. 87], there must exist i ∈ {1, . . . , r} such that Si = S. Hence we can derive
from the assumption that S is a composition factor of G that pw (S n ) ≥ ρ for some
n ∈ N+ .
Our next goal on the way to the proof of Theorem 1.2.2 thus is to study pw (T ),
where T = S n is a finite nonabelian characteristically simple group. In Lemma 4.4
below, we will show that pw (S n ) ≤ maxw′ pw′ (S), where w′ runs through a finite set
of words associated with w, the so-called “variations of w”:
ǫl
ǫ1
be a reduced word of length
Definition 4.1. Let w = xǫ11 · · · xǫl l = Xι(1)
· · · Xι(l)
l ∈ N in the variables X1 , . . . , Xd . For k = 1, . . . , d, denote by ak the number of
occurrences of Xk±1 in w (so that a1 + · · · + ad = l). A variation of w is a word of
ǫl
ǫ1
the form Xι(1),t
, where ti ∈ {1, . . . , aι(i) } for i = 1, . . . , l.
· · · Xι(l),t
1
l

Hence a variation of w is a word w′ of the same length as w and in variables of
the form Xk,t with k ∈ {1, . . . , d} and t ∈ {1, . . . , ak } that is obtained from w by
adding second indices to each occurrence of Xk±1 , k = 1, . . . , d, in w such that each
second index is from the “admissible range”, i.e., lies somewhere between 1 and the
number ak of occurrences of Xk±1 in w.
Example 4.2. Consider the commutator word w = [X1 , X2 ] = X1 X2 X1−1 X2−1 . The
−1 −1
−1 −1
following is a variation of w: X1,2 X2,1 X1,1
X2,1 . The word X1,3 X2,1 X1,2
X2,2 , however, is not a variation of w, since the second index 3 added to the first variable X1
does not lie within the admissible range {1, 2}.
Remark 4.3. Some simple observations concerning variations:

1. Each variation of a reduced word of length l is again a reduced word of length
l.
2. Each reduced word w only has finitely many variations. More precisely, if w is
a reduced word in the variables X1 , . . . , Xd , and Xi±1 occurs precisely ai times
Q
in w for i = 1, . . . , d, then the number of variations of w is precisely dk=1 aakk .

22

Alexander Bors

Automorphic word maps

3. Each reduced word w can be obtained from each of its variations w′ by substituting Xk for Xk,t , t = 1, . . . , ak , in w′ . Hence for each finite group G and
each variation w′ of w, πw′ (G) = 1 implies πw (G) = 1, and pw′ (G) = 1 implies
pw (G) = 1.
Lemma 4.4. Let w be a reduced word of length l ≥ 1 in the variables X1 , . . . , Xd , S a
nonabelian finite simple group and n ∈ N+ . Set ǫ = ǫ(S, w) := maxw′ pw′ (S) ∈ (0, 1],
2
where w′ runs through the variations of w. Then pw (S n ) ≤ ǫ⌈n/l ⌉ ≤ ǫ.
Proof. Fix automorphisms α~1 , . . . , α
~l of S n and an element ~g = (g1 , . . . , gn ) of S n .
By [4, 3.3.20, p. 90], we know that Aut(S n ) = Aut(S) ≀ Sn , and so for i = 1, . . . , l, we
can write α~i = (αi,1 × · · · × αi,n ) ◦ σi , where each αi,j is an automorphism S and σi
is a coordinate permutation on S n .
Let s~1 = (s1,1 , . . . , s1,n ), . . . , s~d = (sd,1 , . . . , sd,n ), where each sk,j is a variable
ranging over S, so that each s~k can be viewed as a variable element of S n . We want
to bound the number of solutions in (S n )d ∼
= S nd of the equation
(α~ ,...,α
~l )

wS n1
xǫ11

(s~1 , . . . , s~d ) = ~g .

· · · xǫl l

ǫ1
Xι(1)

(21)

ǫl
.
· · · Xι(l)

By computing the LHS in
As usual, let us write w =
=
Formula (21) and comparing the entries of the vectors on both sides of the resulting
equation, we see that the equation in Formula (21) is equivalent to the conjunction
of the following n “coordinate equations”, for i = 1, . . . , n:
α1,i (sι(1),σ−1 (i) )ǫ1 · · · αl,i (sι(l),σ−1 (i) )ǫl = gi .
1

(22)

l

The LHS of each of these equations is, up to a suitable renaming of the variables,
the evaluation of an automorphic word map associated with a variation of w in
variables ranging over S. In particular, if Ji denotes the set of those variables sk,j
that are mentioned in the i-th coordinate equation, then that same equation implies
that if we project the solution set Φ to the equation in Formula (21) onto those
coordinates that correspond to variables from Ji , the resulting image has size at
most ǫ|S||Ji | .
Our goal is to find ⌈n/l2 ⌉ pairwise distinct indices i1 , . . . , i⌊n/l2 ⌋ ∈ {1, . . . , n} such
that the associated coordinate equations are pairwise independent, i.e., such that
Jit ∩ Jiu = ∅ for t 6= u. Once we have found these indices, we are done, since it then
follows that the projection of Φ onto those coordinates that correspond to variables
S⌊n/l2 ⌋
from t=1 Jit has size at most
⌈n/l2 ⌉

Y
t=1

2

|Ji1 |+···+|Ji

ǫ|S||Jit | = ǫ⌈n/l ⌉ |S|

⌈n/l2 ⌉

|

,

and thus Φ itself has size at most
2

|Ji1 |+···+|Ji

ǫ⌈n/l ⌉ |S|

⌈n/l2 ⌉

|

n−(|Ji1 |+···+|Ji

⌈n/l2 ⌉

· |S|

as required.

23

|)

2

= ǫ⌈n/l ⌉ |S|n ,

Alexander Bors

Automorphic word maps

We choose the indices i1 , . . . , i⌈n/l2 ⌉ iteratively. i1 can be chosen arbitrarily from
{1, . . . , n}. Denote by M1 ⊆ {1, . . . , n} the set of second indices j in variables sk,j
that are mentioned in the i1 -th coordinate equation, and note that |M1 | ≤ l. Note
that for any i2 ∈ {1, . . . , n}, independence of the i1 -th and i2 -th coordinate equation
is guaranteed if the sets of second indices that occur in the two equations are disjoint.
Now if M2 denotes the set of second indices occurring in the i2 -th
Slequation, for M2
to be disjoint with M1 , we need that i2 does not lie in the set i=1 σi [M1 ], which
has size at most l2 . Hence as long as n > l2 , i.e., ⌈n/l2 ⌉ ≥ 2, we can choose such a
second index i2 . More generally, if we have already found indices i1 , . . . , it such that
the associated coordinate equations are pairwise independent and
S to find
S we want
another index it+1 , it is sufficient to choose it+1 outside of the set li=1 σi [ tu=1 Mu ],
where Mu denotes the set of second indices occurring in the iu -th equation. This set
of “forbidden” values for it+1 has size at most tl2 , and so as long as n > tl2 , i.e.,
⌈n/l2 ⌉ ≥ t + 1, we can choose it+1 as desired. This concludes the proof.
The proof of Theorem 1.2.2 is now easy:
Proof of Theorem 1.2.2. For (1): If S = Am is a composition factor of G, then by
the observations from the beginning of this subsection, it follows that pw (Anm ) ≥ ρ
for some n ∈ N+ , and thus pw′ (Am ) ≥ ρ for some variation w′ of w. However,
w′ is a reduced word of length l in at most l distinct variables, and so if |S| =
′
′
|Am | > max{⌈256l16 e16M l−2 ⌉!, ρ−16M }, we get a contradiction, since this implies by
Theorem 3.1.2(1) that
′

′

′

ρ ≤ pw′ (Am ) ≤ |Am |−1/(16M ) < (ρ−16M )−1/(16M ) = ρ.
For (2): Assume that
p S = Xr (q) is a (classical) simple group of Lie type with
2
2
r > max{72(l + 1) l , 72(l + 1)l2 log2 (ρ−1 )} and that S is a composition factor of
G. As before, it follows that pw′ (S) ≥ ρ for some variation w′ of w. In view of our
choice of r, and using again that w′ is a reduced word of length l in at most l distinct
2
2
variables and that |Xr (q)| ≥ q r ≥ 2r (which follows from the known formulas for
|Xr (q)|, for example from [1, Table 6, p. xvi]), we get by Theorem 3.1.2(2) that
ρ ≤ pw′ (Xr (q)) ≤ |Xr (q)|−1/(72(l+1)l

2)

≤ 2−r

2 /(72(l+1)l2 )

< ρ,

a contradiction.
Proof of Theorem 1.1.2. This follows immediately from Theorem 1.2.2, as Πw (G) ≤
Pw (G).

5

Concluding remarks

As mentioned at the beginning of Section 3, the generalization of the third case in
Larsen and Shalev’s proof (the simple Lie type groups of bounded rank) from the
word map setting to automorphic word maps is open. Described very briefly, Larsen
and Shalev’s approach to the third case is an algebro-geometric one and consists in
studying the fibers of word maps in simple Lie type groups as subvarieties of the Lie

24

Alexander Bors

Automorphic word maps

type groups viewed as linear algebraic groups. One of the problems with extending
this approach to automorphic word maps is that because of the existence of field
automorphisms on Lie type groups, the degrees of the polynomial equations defining
the fiber as a variety are, in contrast to the word map setting, in general not bounded
by a constant any more.
Still, hoping that this and other difficulties can be overcome with sufficiently
refined ideas, we will spend the rest of this concluding section discussing possible
consequences of a successful adaptation of the proof.
The following is a direct generalization of [3, Theorem 1.1] to automorphic word
maps and would most likely result from a suitable adaptation of their proof in its
entirety:
Conjecture 5.1. For each nonempty and reduced word w in d distinct variables,
there exist constants N (w), η(w) > 0 such that for all nonabelian finite simple groups
S with |S| ≥ N (w), the inequality Pw (S) ≤ |S|d−η(w) holds.
Consider also the following slightly stronger version of Conjecture 5.1:
Conjecture 5.2. Like Conjecture 5.1, but with the additional assumption that the
constants N (w) and η(w) are effective, i.e., they can be computed algorithmically
from the word w as input.
Our last goal in this paper is to show that Conjecture 5.2 implies another interesting statement, given as Conjecture 5.3 below. Before this, for the readers’ convenience, we briefly review some basic facts on the solvable radical and finite groups
with trivial solvable radical (for more details, readers are referred to [4, pp. 88ff. and
p. 122]), and we give some motivation.
Recall that every finite group G has a largest solvable normal subgroup, called the
solvable radical of G and denoted by Rad(G). The quotient G/ Rad(G) is semisimple, i.e., it has no nontrivial solvable normal subgroups at all. It can be shown that
the socle Soc(H) (the subgroup generated by all the minimal nontrivial normal subgroups) of a finite semisimple group H is isomorphic with a centerless CR-group, i.e.,
a direct product of nonabelian finite simple groups, and that H acts faithfully on
Soc(H) via conjugation, so that H is isomorphic with a subgroup of Aut(Soc(H))
containing Inn(Soc(H)) ∼
= Soc(H). Conversely, if R is a finite centerless CR-group,
and Inn(R) ≤ G ≤ Aut(R), then G is semisimple and Soc(G) = Inn(R) ∼
= R. Hence
the finite semisimple groups are, up to isomorphism, just those finite groups that
occur in between the inner and the full automorphism group of a finite centerless
CR-group.
The index [G : Rad(G)] is clearly an upper bound on the product of the orders
of all the nonabelian composition factors of G (counted with multiplicities), so that
deriving an upper bound on it means establishing some heavy restrictions on the
structure of G.
It would be nice if we had an algorithmic method to decide in general for a given
reduced word w whether a condition of the form pw (G) ≥ ρ is always strong enough
to imply that [G : Rad(G)] is bounded in terms of w and ρ or not. This is the case
if Conjecture 5.2 holds true.

25

Alexander Bors

Automorphic word maps

Conjecture 5.3. There exists an algorithm which, on input a reduced word w,
achieves the following:
• It decides whether there exists a function gw : (0, 1] → [1, ∞) such that for all
finite groups G and all ρ ∈ (0, 1], if pw (G) ≥ ρ, then [G : Rad(G)] ≤ gw (ρ).
• In case such a function gw exists, it also outputs a definition for a possible
choice of gw .

Proof that Conjecture 5.2 implies Conjecture 5.3. Write Soc(G/ Rad(G)) = S1n1 ×
· · · × Srnr , where the Si are pairwise nonisomorphic nonabelian finite simple groups.
Note that each Sini is a characteristic composition factor of G, and so ρ ≤ pw (G) ≤
pw (Sini ) ≤ maxw′ pw′ (Si ) for i = 1, . . . , r, where w′ runs through the variations of w.
Compute N0 (w) := maxw′ N (w′ ) and η0 := minw′ η(w′ ), and note that necessarily
maxi=1,...,r |Si | ≤ max{N0 (w), ρ−1/η0 (w) }, as otherwise, if |Si | is strictly larger than
that maximum, it follows that ρ ≤ maxw′ pw′ (Si ) ≤ |Si |−η0 (w) < (ρ−1/η0 (w) )−η0 (w) =
ρ, a contradiction.
Hence we can effectively reduce the list of nonabelian finite simple groups S
that could potentially occur as a factor of Soc(G/ Rad(G)) to a finite number of
possibilities. There are two cases to consider:
1. For one of those finitely many nonabelian finite simple groups S, we have
pw (S) = 1. In other words, there exist automorphisms α1 , . . . , αl of S such
(n)

(α

(α ,...,α )

(n)

,...,α

)

l
l
is constant on S d . Then it is easy to see that wS n1
that wS 1
is
n
d
n
+
constant on (S ) , and so pw (S ) = 1 for all n ∈ N . Hence in that case,
[G : Rad(G)] cannot be bounded under any of the assumptions pw (G) ≥ ρ,
ρ ∈ (0, 1].

2. For each of these finitely many S, pw (S) < 1. Then for every variation w′ of w,
pw′ (S) < 1 as well, by Remark 4.3(3). Hence
pw′ (S) ≤ 1 − 1/|S|l .
ǫ = ǫ(S, w) := max
′
w

Therefore, by Lemma 4.4, pw (S n ) ≥ ρ implies
n ≤ n0 (w, ρ) := ⌊l2 · log(ρ)/ log(1 − 1/|S|l )⌋.
It follows that | Soc(G/ Rad(G))|
is effectively bounded from above in terms
Q
of w and ρ, namely by S |S|n0 (w,ρ) , where S runs through the nonabelian
finite simple groups of order at most max{N0 (w), ρ−1/η0 (w) }. Since G/ Rad(G)
embeds into Aut(Soc(G/ Rad(G))), its order is thus also effectively bounded in
terms of w and ρ; more precisely,
Y
Y
|G/ Rad(G)| ≤ | Aut( |S|n0 (w,ρ) )| = |
Aut(S) ≀ Sn0 (w,ρ) |
S

=

Y

S

n0 (w,ρ)

(| Aut(S)|

S

26

· n0 (w, ρ)!).

Alexander Bors

Automorphic word maps

We can thus conclude the proof by noting that it can be effectively decided which
of the two cases occurs (just go through the effective finite list of groups S and check
for each of them, if necessary by brute force, whether pw (S) = 1).

References
[1] J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson, Atlas of
finite groups, Oxford, Clarendon Press (1985, reprinted 2013).
[2] P. Kleidman and M. Liebeck, The Subgroup Structure of the Finite Classical
Groups, Cambridge, Cambridge University Press (London Mathematical Society
Lecture Note Series 129) (1990).
[3] M. Larsen and A. Shalev, Fibers of word maps and some applications, J. Algebra
354 (2012), 36–48.
[4] D.J.S. Robinson, A Course in the Theory of Groups, New York, Springer (Graduate Texts in Mathematics 80) (2nd ed. 1996).
[5] A. Shalev, Some results and problems in the theory of word maps, in: Erdős
Centennial, Budapest, János Bolyai Math. Soc. (Bolyai Soc. Math. Stud. 25)
(2013), 611–649.
[6] T. Tao,
254A, Notes 0a:
Stirling’s formula,
online notes,
https://terrytao.wordpress.com/2010/01/02/254a-notes-0a-stirlings-formula/.

27

