arXiv:1704.08214v1 [math.GR] 26 Apr 2017

Nilpotency and the number of word maps of a finite
group
Alexander Bors∗
February 8, 2018

Abstract
For a finite group G and a non-negative integer d, denote by Ωd (G) the number
of functions Gd → G that are induced by substitution into a word with variables
among X1 , . . . , Xd . In this note, we show that nilpotency of G can be characterized
through the asymptotic growth rate of Ωd (G) as d → ∞.

1

Introduction

1.1

Motivation and main results

In recent years, various authors have made contributions to the theory of word maps
on groups; we refer interested readers to the survey article [2] for an overview of
results and open problems of this theory.
Recall that a word is just an element w of some free group F(X1 , . . . , Xd ) and
that each such word gives rise to a word map wG : Gd → G on every group G,
induced by substitution. For a fixed finite group G, denote by Ωd (G) the number of
functions Gd → G that are of the form wG for some w ∈ F(X1 , . . . , Xd ). Moreover, set
ωd := log2 Ωd (G) (binary logarithm). The aim of this note is to show the following:
Theorem 1.1.1. Let G be a finite group, c a non-negative integer.
1. If G is nilpotent of class exactly c, then ωd (G) = Θ(dc ) as d → ∞.
2. If G is not nilpotent, then ωd (G) ≥ 2d − 1.
∗
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: 20D15, 20D60. Secondary: 20E05, 20E10, 20F18.
Key words and phrases: Word map, Finite group, Nilpotent group.

1

Alexander Bors

Nilpotency and word maps

In particular, if G is nilpotent of class c, then for some large enough constant
c
C = C(G) > 0, we have Ωd (G) ≤ C d for all non-negative integers d, whereas Ωd (G)
grows doubly exponentially in d if G is not nilpotent. Note that the trivial upper
d
bound Ωd (G) ≤ |G||G| is also doubly exponential in d for fixed G. By Theorem
1.1.1, we also have the following quantitative characterization of nilpotency of finite
groups:
Corollary 1.1.2. A finite group G is nilpotent (of class exactly c) if and only if the
sequence (ωd (G))d≥0 is of polynomial growth (of degree exactly c).

1.2

Notation

We denote by N the set of natural numbers (including 0) and by N+ the set of positive
integers. The set of all nonempty subsets of a set X is denoted by P6=∅ (X). The
exponent of a finite group G is denoted by exp(G). As in the previous subsection,
we denote by F(X1 , . . . , Xd ) the free group on the formal generators X1 , . . . , Xd , and
we will denote by Fc (X1 , . . . , Xd ) the free nilpotent group of class exactly c on the
formal generators X1 , . . . , Xd .

1.3

Normal forms of elements in free nilpotent groups

For the reader’s convenience, we briefly recall a result on normal forms of elements
in free nilpotent groups (based on a certain polycyclic decomposition of such groups)
which we will need, see the blog post [3] or the textbook [1, Theorem 5.13A, p. 343,
and its proof] for more details.
Fix d, c ∈ N, and assign to each i ∈ {1, . . . , d} the weight wt(i) := 1. Consider formal iterated commutators of the numbers 1, . . . , d (we will henceforth call
them formal d-commutators) and define the weight of a formal d-commutator recursively via wt([α, β]) := wt(α) + wt(β). Moreover, for a formal d-commutator γ,
define Xγ , a word in the variables X1 , . . . , Xd , recursively via X[α,β] := [Xα , Xβ ] =
Xα−1 Xβ−1 Xα Xβ .
(d,c)

(d,c)

Then there exists an explicitly constructible finite ordered tuple (α1 , . . . , αNd,c )
of pairwise distinct formal d-commutators each of weight at most c such that every
QNd,c
(Xα(d,c) )kj
element of Fc (X1 , . . . , Xd ) has a unique representation of the form j=1
j

with kj ∈ Z.
For later use, we also note the following, which can be easily proved by induction
on c:
Lemma 1.3.1. For each c ∈ N, there exists a polynomial Pc (X) ∈ Z[X] of degree c
such that for every d ∈ N, the number of formal d-commutators of weight at most c
is exactly Pc (d).
See also [1, Problems for Section 5.2, Problem 5] for a precise formula for the
coefficients of Pc (d).

2

Alexander Bors

2

Nilpotency and word maps

Proof of Theorem 1.1.1

We begin by providing a lower bound on Ωd (G) which will yield both statement (2)
of Theorem 1.1.1 and half of statement (1). For this, we need some notation.
Notation 2.1. Let G be a group.
1. For r ∈ N+ and elements g1 , . . . , gr ∈ G, we define their nested commutator
[g1 , . . . , gr ] recursively via [g1 ] := g1 and [g1 , . . . , gr+1 ] := [[g1 , . . . , gr ], gr+1 ].
2. If G is finite and r ∈ N+ , then denote by expr (G) the least common multiple of
the orders of the elements of G of the form [g1 , . . . , gr ], where the gi range over
G.
Note that for fixed finite G, the sequence (expr (G))r≥1 is monotonically decreasing
and that exp1 (G) = exp(G).
Definition 2.2. Let G be a finite group, d ∈ N.
1. A function f : P6=∅ ({1, . . . , d}) → N is called G-admissible if and only if for
each r ∈ {1, . . . , d}, we have f (M ) < expr (G) for every r-element subset M ⊆
{1, . . . , d}.
2. To each G-admissible function f , we assign a word wf (X1 , . . . , Xd ), defined as
follows:

wf (X1 , . . . , Xd ) :=

d Y
d
Y

d
Y

r=1 i1 =1 i2 =i1 +1

···

d
Y

[Xi1 , . . . , Xir ]f ({i1 ,...,ir }) .

ir =ir−1 +1

We now show:
Proposition 2.3. Let G be a finite group, d ∈ N.
1. Let f, g be distinct G-admissible functions P6=∅ ({1, . . . , d}) → N. Then the word
maps (wf )G and (wg )G are distinct functions Gd → G.
d
Q
2. Ωd (G) ≥ dr=1 expr (G)(r ) .
Proof. Statement (2) follows from statement (1), as the asserted lower bound is by
definition just the number of G-admissible functions P6=∅ ({1, . . . , d}) → N.
As for statement (1), let r ∈ N+ be minimal such that f and g disagree on some
r-element subset of {1, . . . , d} and let i1 < i2 < · · · < ir be such that {i1 , . . . , ir }
is minimal with respect to the lexicographical ordering among all r-element subsets
of {1, . . . , d} on which f and g have different values. Set a := f ({i1 , . . . , ir }) −
g({i1 , . . . , ir }) and note that a ∈ {1, . . . , expr (G) − 1}. By definition of expr (G), this
means that we can fix gi1 , . . . , gir ∈ G such that
[gi1 , . . . , gir ]f ({i1 ,...,ir })−g({i1 ,...,ir }) 6= 1G .
Moreover, set gi := 1G for i ∈ {1, . . . , d} \ {i1 , . . . , ir }.

3

Alexander Bors

Nilpotency and word maps

We claim that (wf )G and (wg )G disagree on the argument (g1 , . . . , gd ). To see
this, note that by choice of (i1 , . . . , ir ), we have
wf = w0 · [Xi1 , . . . , Xir ]f ({i1 ,...,ir }) · w1
and
wg = w0 · [Xi1 , . . . , Xir ]g({i1 ,...,ir }) · w2 ,
where w0 , w1 , w2 ∈ F(X1 , . . . , Xd ) and w1 , w2 are products of nested commutators
of length at least r distinct from [Xi1 , . . . , Xir ], so that when substituting gi for Xi ,
at least one of the entries of each such nested commutator will be 1G , forcing it to
be trivial. Therefore,
(wf )G (g1 , . . . , gd ) = w0 (g1 , . . . , gd ) · [gi1 , . . . , gir ]f ({i1 ,...,ir })
6= w0 (g1 , . . . , gd )[gi1 , . . . , gir ]g({i1 ,...,ir }) = (wg )G (g1 , . . . , gd ),
as required.
Corollary 2.4. Let G be a finite group, c ∈ N, and assume that the (c+1)-th

Pctermdin
the lower central series of G is nontrivial. Then for every d ∈ N, ωd (G) ≥ r=1 r .
Proof. By assumption, expr (G) ≥ 2 for r = 1, . . . , c, so the result follows immediately
from Proposition 2.3(2).
In particular, dc = O(ωd (G)) whenever G is nilpotent of class exactly c (which
is “half of Theorem 1.1.1(1)”) and if G is not nilpotent,
we
 can choose c := d in
P
Corollary 2.4 and get Theorem 1.1.1(2) using that dr=1 dr = 2d − 1. The second
half of Theorem 1.1.1(1) is provided by the following:
Lemma 2.5. Let c ∈ N, and let Pc (X) ∈ Z[X] be as in Lemma 1.3.1. Then for every
finite nilpotent group G of class exactly c, we have ωd (G) ≤ Pc (c) · log2 (exp(G)).
Proof. We show the equivalent Ωd (G) ≤ exp(G)Pc (c) . Let w ∈ F(X1 , . . . , Xd ). Then
the remarks in Subsection 1.3 yield that
Nd,c

wFc (X1 ,...,Xd ) (X1 , . . . , Xd ) =

Y
j=1

((Xα(d,c) )kj ).
j

for suitable integers kj . As Fc (X1 , . . . , Xd ) is the free object in the category of
nilpotent groups of class at most c, this relation among its generators translates to
an identity in all nilpotent groups of class at most c, yielding in particular that wG =
QNd,c
( j=1
((Xα(d,c) )kj ))G . Hence each word map on G is induced by a word of the form
j
QNd,c
kj
((X
(d,c) ) ) for suitable integers kj , which we may w.l.o.g. assume to be from
j=1
α
j

the finite range {0, . . . , exp(G) − 1}. Therefore, Ωd (G) ≤ exp(G)Nd,c ≤ exp(G)Pc (c) ,
as required.

4

Alexander Bors

Nilpotency and word maps

References
[1] W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory. Presentations of Groups in Terms of Generators and Relations, Interscience Publishers
(Pure and Applied Mathematics, XIII) (1966).
[2] 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.
[3] T.
Tao,
The
free
nilpotent
group,
blog
post
(2009),
https://terrytao.wordpress.com/2009/12/21/the-free-nilpotent-group/.

5

