TRANSVERSALS AS GENERATING SETS IN FINITELY
GENERATED GROUPS

arXiv:1402.0799v2 [math.GR] 20 Oct 2016

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS
Abstract. We explore transversals of finite index subgroups of finitely generated groups. We show that when H is a subgroup of a rank n group G
and H has index at least n in G then we can construct a left transversal for
H which contains a generating set of size n for G, and that the construction
is algorithmic when G is finitely presented. We also show that, in the case
where G has rank n ≤ 3, there is a simultaneous left-right transversal for H
which contains a generating set of size n for G. We finish by showing that
if H is a subgroup of a rank n group G with index less than 3 ⋅ 2n−1 , and H
contains no primitive elements of G, then H is normal in G and G/H ≅ C2n .

1. Introduction
Let H be a subgroup of G (written H < G). A left transversal for H in G is a
choice of exactly one representative from each left coset of H. A right transversal
for H is G in defined in an analogous fashion. A left-right transversal for H is
a set S which is simultaneously a left transversal, and a right transversal, for H
in G. The existence of a left or right transversal is clear (assuming the Axiom of
Choice) whereas it is not immediate that a left-right transversal always exists.
We gave a short proof of this in [3] for the case where H is of finite index, as
well as a brief historical discussion of this result.
Transversals are natural objects of study, especially when H has finite index
in G. Moreover, finding generating sets for a group G is a well known problem
in the case when G is finitely generated. Therefore we can ask: given a finitely
generated group G and a finite index subgroup H of G, is there a (say) left
transversal for H in G which also generates G? In fact if T is a left transversal
for H in G, then it is clear that T −1 (the set of inverses of all elements in T ) is
a right transversal of H in G. Moreover ⟨S⟩ = ⟨S −1 ⟩ for any subset S of a group
G, so we need only consider left transversals throughout. Jain asked Cameron
this question under the added assumption that G is a finite group and H is
corefree in G, meaning that coreG (H) = {e} (coreG (H) is the intersection of all
conjugates of H in G: coreG (H) ∶= ⋂g∈G g −1 Hg). Cameron showed in [4] that in
this case a generating left transversal always exists (see also [5, Problem 100]).
2010 AMS Classification: 20E99, 20F05
Keywords: Transversals, generating sets, finite index subgroups, primitive elements.
The second author was partially funded by the Italian FIRB “Futuro in Ricerca” project
RBFR10DGUA 002 and the Swiss National Science Foundation grant FN PP00P2-144681/1.
The third author did part of this work while writing his thesis at the University of Cambridge, supported by the Mexican National Council for Science and Technology.
Date: October 21, 2016.
1

2

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

The proof is short but relies on a result [15] of Whiston on minimal generating
sets (ones where no proper subset generates) of the symmetric group which uses
the classification of finite simple groups (CFSG).
However there is an obvious necessary condition for a subgroup H of G to
possess a generating left transversal, which is that the index [G ∶ H] must be
at least d(G) (the rank of G), defined to be the minimal number of generators
for the finitely generated group G. In Theorem 3.8 we show that this condition
is also sufficient, for G any finitely generated group and H any subgroup of
finite index. We can then try to strengthen this result by examining whether
[G ∶ H] ≥ d(G) implies that there exists a left-right transversal for H that
generates G. We have not managed to establish this in general but we have
shown in Theorem 3.12 that it is true if d(G) ≤ 3.
Our main method of proof in Section 3 is a new technique which we call
shifting boxes. It involves using the transitive action of a group G on the set
of left (or right) cosets of a subgroup H < G to systematically apply Nielsen
transformations to a generating set of G, such that the resulting generators lie
inside (or outside) particular desired cosets of H. We have found this technique
to be very intuitive for developing proofs. Though similar to Schreier graphs,
the technique of shifting boxes is much more useful in finding solutions to the
problems we have considered. Many of our results can be reduced to the case
of subgroups of free groups (Proposition 3.13). However, even in this restricted
case, the use of Stallings graphs (Schreier graphs for free groups) leads to proofs
which are longer and more complicated than those by shifting boxes.
An element of a rank n group G is primitive if it lies in some generating set of
size n for G. The location of primitive elements relative to cosets of subgroups
is already an area of interest. Parzanchevski and Puder [14] show that if w ∈ Fn
is a non-primitive element then there is a finite index subgroup H < Fn such
that the coset wH does not contain any primitive elements. Taking w = e gives
a finite index subgroup containing no primitive elements.
By applying the technique of shifting boxes developed in Section 3, we are
able to show in Theorem 4.4 that if G is a rank n group, then the only subgroup
of G with index less than 3 ⋅ 2n−1 that can contain no primitive elements is
[G, G]G2 , and even then this only occurs when G/([G, G]G2 ) ≅ C2n . This
gives an exponential lower bound on the index of subgroups which contain
no primitive elements. Beyond the special case [G, G]G2 , the lower bound
of 3 ⋅ 2n−1 can be sharp: the free group F2 has a subgroup of index 3 ⋅ 22−1
containing no primitive elements. Moreover, Fn always has a subgroup of index
2n+1 containing no primitive elements (Example 4.5).
We first announced many of the results of this paper in [2].
Acknowledgements: We wish to thank Rishi Vyas and Andrew Glass for
their many useful conversations and comments about this work. Thanks also
go to Zachiri McKenzie and Philipp Kleppmann for discussions on the Axiom
of Choice.

TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

3

2. Coset intersection graphs
A useful tool for studying the way left and right cosets interact, and obtaining transversals, is the coset intersection graph. In this section we re-state
important results from our earlier work [3] on this concept. We denote the
complete bipartite graph on (m, n) vertices by Km,n .
Definition 2.1. Let H, K < G. We define the coset intersection graph ΓG
H,K to
be a graph with vertex set consisting of all left cosets of H ({li H}i∈I ) together
with all right cosets of K ({Krj }j∈J ), where I, J are index sets. If a left coset
of H and right coset of K correspond, they are still included twice. Edges
(undirected) are included whenever any two of these cosets intersect, and an
edge between aH and Kb (written aH − Kb) corresponds to the non-empty set
aH ∩ Kb.
Theorem 2.2. Let H, K < G. Then the graph ΓG
H,K is a disjoint union of
complete bipartite graphs. Moreover, suppose that [G ∶ H] = n, [G ∶ K] = m.
Then each connected component of ΓG
H,K is of the form Ksi ,ti with si /ti = n/m.
Corollary 2.3. Let H, K < G. Suppose that [G ∶ H] = n and [G ∶ K] = m,
where m ≥ n. Then there exists a set T ⊆ G which is a left transversal for H in
G, and which can be extended to a right transversal for K in G. If H = K in
G, then T becomes a left-right transversal for H.
Under the hypothesis of Theorem 2.2, we see that sets of si left cosets of H
completely intersect sets of ti right cosets of K, with si /ti constant over i. With
this in mind, another way of visualising ΓG
H,K is by the following simultaneous
double-partitioning G: draw left cosets of H as columns, and right cosets of K
as rows, partitioning G into irregular ‘chessboards’ denoted Ci , each with edge
ratio n ∶ m. Each chessboard Ci corresponds to the connected component Ksi ,ti
of ΓG
H,K , and individual tiles in Ci correspond to the non-empty intersection
of a left coset of H and a right coset of K (i.e., edges in Ksi ,ti ). Corollary
2.3 would then follow by choosing one element from each tile on the leading
diagonals of the Ci ’s. An example of chessboards is given in [3].
The chessboard pictorial representation of partitioning G into left and right
cosets is extremely useful in the analysis of transversals as generating sets carried out in the next section. Note that the union of all the elements of G in
a single chessboard gives a unique double coset KgH in G, and that a single chessboard is simply a double-partitioning of a double coset KgH into its
respective left cosets of H and right cosets of K.
3. Transversals as generating sets
We have developed a technique which we call shifting boxes that, for the sake
of brevity, we will describe here as a systematic way to apply Nielsen transformations to a generating set of a group G, such that the resulting generators
lie inside (or outside) particular desired cosets of a subgroup H < G. We can’t
‘shift’ generators in/out of any coset we like, but we do have a substantial degree of control. For ease of notation, we will often refer to the coset eH as the
identity coset. We begin with the following definitions.

4

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

Definition 3.1. Let G be a group, and S ∶= (g1 , . . . , gn ) a generating n-tuple
of G (where n ∈ N), that is, an element of the direct product Gn such that
{g1 , . . . , gn } generates G. A standard Nielsen move on S is the replacement of
some entry gi of S with one of gj gi , gj−1 gi , gi gj or gi gj−1 , where we must have
i ≠ j. A Nielsen move is defined to be either a standard Nielsen move or an
extended Nielsen move, where the latter consists of either replacing an entry
gi by its inverse, or transposing two entries gi and gj for i ≠ j. Note that on
applying any Nielsen move to S, the resulting n-tuple still generates.
Definition 3.2. Let G be a group. Two generating n-tuples S1 , S2 of G are
said to be Nielsen equivalent if they differ by a finite number of Nielsen moves.
Definition 3.3. Let G be a group, H a subgroup of G, and S a generating
n-tuple of G. We say a left coset gH is full (with respect to S) if some entry
of S lies in gH, otherwise we say gH is empty (with respect to S). To save on
notation, we will usually suppress the term ‘with respect to S’ when there is
no ambiguity.
In the introduction we mentioned that the Axiom of Choice was necessary
to show that for every group G and every subgroup H < G there exists a
left transversal for H in G (in fact, the Axiom of Choice is equivalent to this
condition; see [1, Theorem 2.1]). However, choice is not necessary for the groups
we will be considering, as they are all finitely generated. To see this, take a
finite generating set {x1 , . . . , xn } for G and form the canonical enumeration of
words w1 , w2 , . . . on X ∪X −1 , ordered lexicographically. Then the set T ∶= {wn ∈
G ∣ (∀i < n)(wi ∉ wn H)} is a left transversal for H in G (and we have not used
choice here). Moreover, if we have a set S ⊂ G for which no two elements of S
lie in the same left coset of H, then this set extends to a left transversal for H
by adjoining TS ∶= {wn ∈ G ∣ (wn ∉ S) ∧ (∀i < n)(wi ∉ wn H)} (again, without
the need for choice).
We now give several techniques, which we rely on heavily for our main results.
Note that in this section we prove our results under very general conditions,
and all techniques are (for now) existential.
Definition 3.4. Let H < G be groups. A n-tuple S ′ with entries in G is said
to be left-cleaned if all of its entries lie in distinct left cosets of H (apart from
eH which may contain many entries of S ′ ). An analogous definition applies for
a right-cleaned n-tuple, dealing with right cosets instead.
Lemma 3.5. Let G be a group, H a subgroup of G, and S a generating n-tuple
of G. Then there is a left-cleaned generating n-tuple S ′ of G, Nielsen equivalent
to S. An identical result holds for right cosets of H.
Proof. We call the following process left-cleaning an n-tuple. Let S = (g1 , . . . , gn ).
We can assume that there is gi , gj with i ≠ j both lying in the same non-identity
left coset of H, so that gi H = gj H ≠ eH. Then gj−1 gi ∈ H so we can apply the
standard Nielsen move on S which replaces gi with gj−1 gi to obtain S1 . Then
S1 has fewer entries lying in this left coset of H, and the same number in all
other non-identity left cosets. Iterating this procedure and then moving to other
non-identity left cosets, we eventually reach a left-cleaned n-tuple S ′ .


TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

5

An analogous definition, result, and proof, applies for right cosets and right
cleaning.
Lemma 3.6. Let G be a group, H a subgroup of G, and S a generating ntuple of G. If there exists at least one empty left coset of H, then there are
entries sj , sk of S (possibly the same entry) and  ∈ {±1} such that sj sk H is an
empty left coset. That is, there is some full left coset of H which is taken to
some empty left coset of H by left multiplication under some entry of S or its
inverse.
Proof. Recall that G acts transitively on the set of left cosets by left multiplication. Assume that no entry of S or its inverse sends a full left coset to an
empty left coset. Then, as the entries of S generate G, the collection of full left
cosets is invariant under this action. Seeing as there exists at least one empty
left coset, this contradicts the transitive action of G.

Lemma 3.7. Let G be a group, H a subgroup of G, and S a generating n-tuple
of G. Suppose that at least one entry of S lies in H, and moreover that there
exists an empty left coset of H with respect to S. Then there is a finite sequence
of Nielsen moves on some entry s of S which is contained in H such that s is
taken into an empty left coset of H.
Proof. By Lemma 3.6 there are (possibly identical) entries s1 , s2 of S, and
 ∈ {±1}, with sj sk H an empty left coset of H with respect to S. We consider
all possible cases:
1. The case sj , sk ∈ H never occurs, as then sj sk H = H which is a full left
coset by hypothesis.
2. In the case sj ∉ H, sk ∈ H, the subcase s+1
j sk H can’t occur, as then
+1
H
which
is
clearly
full.
In
the
subcase
s−1
sj sk H = s+1
j sk H, we replace sk with
k
−1
−1
sj sk lying in the left coset sj sk H which is empty.
3. In the case sj ∈ H, sk ∉ H, we replace sj with sj sk , as the left coset sj sk H
is empty.
4. In the case sj , sk ∉ H, take some si ∈ H and replace si with sj sk si , which
lies in the empty left coset sj sk si H = sj sk H. As si is a different entry from
sj and sk , this is a composition of two standard Nielsen moves on the entry si
(even if sj = sk ).
We call this replacement process a left-extraction of an entry of S from H. 
Using these techniques, we state the condition below for a finite index subgroup of a group to possess a left transversal which generates the whole group.
For simplicity, when S is an n-tuple, we write S̃ for the set of entries of S.
Theorem 3.8. Let G be a finitely generated group, and H a subgroup of finite
index in G. Then the following are equivalent:
1. [G ∶ H] ≥ d(G).
2. There exists a left transversal T for H in G which contains a generating set
X for G of size ∣X∣ = d(G).
As mentioned in the introduction, the above result also carries over to right
transversals.

6

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

Proof. That 2 ⇒ 1 is immediate. We show 1 ⇒ 2:
Let n = d(G), and let S be a generating n-tuple for G. Use Lemma 3.5 to
produce an n-tuple S ′′ Nielsen-equivalent to S which is left-cleaned. Now repeatedly apply Lemma 3.7 to begin left-extracting elements from inside H (thus
Nielsen-transforming S ′′ ). As n ≤ [G ∶ H], we can keep left-extracting until we
reach S ′ which is Nielsen-equivalent to our original S, and for which no two
entries of S ′ lie in the same left coset of H. Now simply choose one element
from each left coset of H which is empty with respect to S ′ , and add these to
S̃ ′ to form the set T . Then T is clearly a left transversal for H, and contains
S̃ ′ .

A slight variant of the above proof also shows the following result: when
[G ∶ H] ≤ d(G) then there is a generating set for G of size d(G) which contains
a set of left coset representatives for H.
For ease of writing, we will often refer to the overall process of cleaning and/or
extracting elements (either left, or right) as shifting boxes, and will usually just
write this follows by shifting boxes to mean that it follows by the process of
cleaning and/or extracting elements. Our remarks in this section give sufficient
conditions for cleaning and/or extracting to be algorithmic.
The most natural question to ask now is ‘When does a finite index subgroup
have a left-right transversal which generates the whole group?’ This requires
a deeper understanding of how cosets intersect, as discussed in Section 2. We
urge the reader to consider the discussion of ‘chessboards’ given after Corollary
2.3, and to consult [3] for an example. These are vital in proving what follows.
Let G be a group, H a subgroup of G, and S a generating n-tuple of G. Then
by Lemma 3.5 we can first perform a left-cleaning of S to form S ′ , followed by a
right-cleaning of S ′ (which will stay left-cleaned) to obtain a further generating
n-tuple S ′′ such that:
1. S and S ′′ are Nielsen-equivalent.
2. S ′′ is left-cleaned.
3. S ′′ is right-cleaned.
We say that S ′′ is left-right-cleaned.
Lemma 3.9. Let G be a group, H a subgroup of finite index in G, and S
a generating n-tuple of G. Then S is left-right-cleaned if and only if one can
draw chessboards for H in G with distinct entries of S lying in distinct diagonal
tiles of chessboards, except for the chessboard corresponding to the double coset
HeH = H which may contain several elements of S.
Proof. This is immediate from the fact that columns in chessboards correspond
to left cosets of H, and rows correspond to right cosets. Thus, a column
(resp. row) in the chessboards contains multiple entries of S if and only if the
corresponding left (resp. right) coset of H contains multiple entries of S.

Note that one can obtain a left-right transversal for H by taking one element
from each diagonal tile of each chessboard (by Corollary 2.3). More strongly,
by left-right-cleaning and choosing an element from each unused diagonal we
have:

TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

7

Lemma 3.10. Let G be a group, H a subgroup of finite index in G, and S
a generating n-tuple of G. If S is left-right-cleaned, and H contains at most
one entry of S, then there is a set T containing all the entries of S which is a
left-right transversal for H in G.
Proof. Given that columns in chessboards correspond to left cosets of H, and
rows correspond to right cosets, we have that no column or row in any chessboard contains more than one entry from S. Thus we can re-arrange the positioning of the columns and rows in each chessboard so that the entries of S are
all in tiles which lie on leading diagonals. Now simply choose one element from
each lead-diagonal tile which does not contain an entry of S, and add these to
the set S to form the set T . Then T contains precisely one element from each
lead-diagonal tile of each chessboard, and no other elements. Thus T contains
precisely one element in each left coset of H, and precisely on element in each
right coset of H. So T is our desired left-right transversal which contains S̃. 
Combining our shifting boxes technique, along with the properties of the
coset intersection graph from Theorem 2.2, we are able to show the following:
Theorem 3.11. Let G be a group, S a generating n-tuple for G with n ≤ 3, and
H a subgroup of finite index in G with n ≤ [G ∶ H]. Then there is a generating
n-tuple S ′ Nielsen-equivalent to S, and a left-right transversal T for H in G
with S̃ ′ ⊆ T .
Proof. The case when n = 1 is trivial. The case when n = 2 is done as follows:
Left-right-clean S to form S ′ = (a, b). Clearly we can’t have a, b ∈ H, or else H
can’t have index ≥ 2. So at most one of a, b lies inside H. But then by Lemma
3.10 we can extend S̃ ′ to a set T which is a left-right transversal for H. Seeing
as T contains S̃ ′ , then it generates G.
The case where n = 3 is much more complicated, and we need to consider
several sub-cases. So, left-right-clean S to form S ′ = (a, b, c). Clearly we cannot
have a, b, c ∈ H, or else H does not have index at least 3. So at most two of a, b
lie inside H. Again, if only one of a, b, c lies inside H then we can apply Lemma
3.10 as before. So we are left to consider what happens when two of a, b, c ∈ H
(without loss of generality, re-label them as h1 , h2 ∈ H and g ∉ H).
Case 1. g 2 ∉ HgH ∪ H (i.e., g 2 lies in a different chessboard to g and h1 , h2 ).
Make the Nielsen moves h1 ↦ g 2 h1 ; this clearly lies in the same left coset (and
hence same chessboard) as g 2 (see Figure 1).
g

2

g

h1 h2
2

g h1

Figure 1.
So now each of g, h2 , g 2 h1 lie in different chessboards, thus the triple S ′′ ∶=
(g, h2 , g 2 h1 ) is left-right cleaned. As only h2 lies inside H, we can use Lemma

8

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

3.10 to extend S̃ ′′ to a set T which is a left-right transversal for H. Seeing as
T contains S̃ ′′ , then it generates G.
If case 1 does not occur, then we proceed to case 2.
Case 2. g 2 ∈ HgH (i.e., g 2 lies in the same chessboard as g).
Clearly g 2 H ≠ gH and Hg 2 ≠ Hg; otherwise we would have g ∈ H which
contradicts our initial hypothesis. So g 2 lies in a different left coset and different
right coset to g (i.e., in a different column and row to g in HgH). Consider
h1 g 2 and h2 g 2 (which both lie in the same right coset as g 2 , and hence in a
different right coset to g). If hi g 2 H ≠ gH for some i ∈ {1, 2}, then make the
Nielsen moves hi ↦ hi g 2 which lies in a different left and different right coset
to g (but in the same chessboard) (see Figure 2).
g
h1 h2
2

g

2

hi g

Figure 2.
2
2
If on the other hand h1 g 2 H = h2 g 2 H = gH, then h−1
2 h1 g H = g H and so we
−1
2
make the Nielsen moves h1 ↦ h2 h1 g which lies in a different left and different
right coset to g (but in the same chessboard) (see Figure 3).

g
h1 h2
h1 g 2
g2
−1
2
h 2g 2 h 2h 1g

Figure 3.
Either way, we now have a triple S ′′ for which, after permutation of some
rows and columns, has entries which lie along diagonal tiles of the chessboards.
As only one such entry lies inside H, we can use Lemma 3.10 to extend S̃ ′′ to
a set T which is a left-right transversal for H. Seeing as T contains S̃ ′′ , then it
generates G.
If neither case 1 nor case 2 occur, then we proceed to case 3.
Case 3. g 2 ∈ H.
By the transitivity of the action of G on left (and right) cosets of H, there must
be some hi (i ∈ {1, 2}) and some  ∈ {±1} with hi gH ≠ gH, and similarly some

TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

9

hj (j ∈ {1, 2}) and some δ ∈ {±1} with Hghδj ≠ Hg. If i ≠ j, then we make the
Nielsen move hi ↦ hi g followed by the Nielsen move g ↦ ghδj (see Figure 4).
ε

g

hi g

h1 h2
g2
δ

gh j

Figure 4.
If on the other hand i = j (say i = j = 1, without loss of generality), then
consider the element h2 ghδ1 . If h2 ghδ1 H ≠ gH, then h2 ghδ1 lies in a different
left coset and different right coset to g, and so we make the Nielsen moves
h2 ↦ h2 ghδ1 (see Figure 5).
ε

g

h 1g

h1 h2
g2
δ

δ

gh 1 h 2 gh 1

Figure 5.
If however h2 ghδ1 H = gH, then h2 ghδ1 lies in a different left coset and different
right coset to h1 g, and so we make the Nielsen moves h2 ↦ h2 ghδ1 followed by
g ↦ h1 g (see Figure 6).
ε

g

h 1g

h1 h2
g2
δ

gh 1 δ
h 2 gh 1

Figure 6.
In all the subcases considered here, we end up with a triple S ′′ for which, after
permutation of some rows and columns, has entries which lie along diagonal tiles
of the chessboards. As only one such entry lies inside H, we can use Lemma

10

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

3.10 to extend S̃ ′′ to a set T which is a left-right transversal for H. Seeing as
T contains S̃ ′′ , then it generates G.

Given the existential nature of the results stated in this section, it is always
possible (via naive searches) to algorithmically construct the relevant generating
tuples and transversals mentioned in the results. However, by following our
proofs more closely, one can algorithmically construct these in a manner much
faster than mere naive searches.
Theorem 3.12. Let G be a group with d(G) ≤ 3, and H a subgroup of finite
index in G. Then the following are equivalent:
1. There exists a left-right transversal T for H in G with ⟨T ⟩ = G.
2. [G ∶ H] ≥ d(G).
Proof. That 1 ⇒ 2 is immediate; 2 ⇒ 1 can be seen from Theorem 3.11.



This leads us to pose the following question:
Question 1. Does Theorem 3.12 hold if we change the hypothesis ‘d(G) ≤ 3’
to ‘d(G) finite’ ?
In the proof of Theroem 3.11, each case n = 1, 2, 3 is shown by analysing
a (increasing) finite number of possible scenarios, via repeated application of
shifting boxes. We have not yet extended this to the case n ≥ 4, as the number
of scenarios to consider becomes very large and complex. We believe that the
most elegant way to do this would be to establish some technique that, given
a left-right-cleaned generating n-tuple S of G with more than one entry of S
lying in H, left-right-extracts an entry of S lying in H to an empty square on
the diagonal of one of the chessboards. We have not been able to do this, but
believe that it may indeed be possible.
There is an equivalence between our shifting boxes technique, and the Schreier
graph of the action of G on G/H with respect to a generating set for G. Though
the Schreier graph could be a valid approach to take, it seems more cumbersome
to work with for the problems we have considered, and proofs using Schreier
graphs appear to be longer and less intuitive than what we have done here.
We note that, in any extension of Theorem 3.12 to groups needing more than
three generators, we need only consider free groups, as the following shows:
Proposition 3.13. Theorem 3.12 holds for all finite rank groups (rather than
just groups of rank at most 3) if and only if it holds for all finite rank free
groups.
Proof. Suppose Theorem 3.12 holds for all finite rank free groups. Let G be a
group with d(G) = n, and H < G a subgroup of index [G ∶ H] = k ≥ n. Then
there is a surjection f ∶ Fn ↠ G, and it is a standard fact that the preimage
f −1 (H) also has index k in Fn . By hypothesis, there is a left-right transversal
T of f −1 (H) which generates Fn ; it follows that f (T ) is a left-right transversal
of H which generates G.

Thus we are able to restrict our investigation to the case of finite rank free
groups. By doing this, we are able to make use of the rich theory of Stallings

TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

11

graphs, which are precisely Schreier graphs for subgroups of free groups [10].
This simplification to free groups also extends to all earlier results in this section before Theorem 3.12 (they are true for all groups if and only if they are
true for free groups). With the help of Enric Ventura and Jordi Delgado we
have replicated proofs of our 1-sided transversal results (Lemmata 3.5–3.7 and
Theorem 3.8) using the framework of Stallings graphs. However, we stress that
these are more complicated, and our attempts to generalise (or even re-prove)
Theorems 3.11 and 3.12 using Stallings graphs have so far been unsuccessful.
4. An application of shifting boxes: finding primitive elements
Recall that a primitive element of a finite rank free group Fn is one which
lies in some generating set of size precisely n, which is equivalent to being an
element of a free basis for Fn . If G is a group of finite rank n, then we say
a primitive element in G is an element lying in some generating set of size n
for G. This reduces to the standard definition of primitive elements in finitely
generated free groups.
An obvious question to ask is which subgroups of Fn (or more generally,
rank n groups) contain a primitive element (we can ask this for both finite and
infinite index subgroups). We first consider the case of normal subgroups.
The following is immediate by considering the image under the natural homomorphism of a generating set of minimal size containing the relevant primitive
element:
Lemma 4.1. Let G be a group of finite rank n, and N a normal subgroup of
G. If N contains some primitive element of G, then d(G/N ) < n.
The converse statement is not true, even in the special case that G = Fn , as
was shown in [12] and in [9] when N has infinite index. It is currently open
if N has finite index and here we briefly mention the connection with product
replacement graphs. Much more can be found in the survey article [13] of Pak
which contains a range of references.
Given a finitely generated group G and an integer n ≥ d(G), the product
replacement graph Γn (G) has vertices the generating n-tuples of G with edges
between two vertices if one is the image of another under a standard Nielsen
move. A big area of study in this topic is the connectivity of Γn (G). Now
if n ≥ d(G) + d(G), where d is the maximum size of a minimal generating
set (one in which no proper subset is a generating set), then it is known that
Γn (G) is connected. However d can be a very hard quantity to evaluate in
practice: indeed the result of Whiston mentioned earlier which was used by
Cameron is that d(Sn ) = n − 1 and the proof needs CFSG. It can happen that
Γn (G) is disconnected when n = d(G) (for instance finite abelian groups) but
no example is known of a finite group G and an integer n > d(G) where Γn (G)
is disconnected. If G is finite soluble and n > d(G) then Dunwoody showed in
[8] that Γn (G) is connected. The relation with primitive elements, as noted by
Dunwoody in that paper, is that if N is a normal subgroup of Fn containing
no primitive element but G = Fn /N has d(G) < n then Γn (G) is disconnected.
Hence there are examples of infinite finitely generated groups G with Γn (G)

12

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

disconnected by the papers cited above, but a normal subgroup N of finite
index containing no primitive element and with d(Fn /N ) < n would give rise to
a finite group G and integer n > d(G) with Γn (G) disconnected; the existence
of which is currently unknown.
Our shifting boxes technique enables us to explore the location of primitive
elements relative to cosets of a finite index subgroups, in the following ways. We
write [n] for the set of integers {1, . . . , n}, and X∆Y for symmetric difference.
Lemma 4.2. Let G be any group with d(G) = n, and H a subgroup of finite
index in G with [G ∶ H] < 3 ⋅ 2n−1 . If H contains no primitive elements of G,
then H contains the square of every primitive element of G.
Proof. Let S = (g1 , . . . , gn ) be any left-cleaned generating n-tuple for G. For
any ∅ ≠ M = {i1 , . . . , ik } ⊆ [n], ordered so i1 < . . . < ik , define the unique
word wM ∶= gik gik−1 ⋯gi1 Define the disjoint sets of words A ∶= {wM ∣ ∅ ≠ M ⊆
{2, . . . , n} or M = {1}}, B ∶= {wM g1 ∣ ∅ ≠ M ⊆ [n]}. Now set T ∶= A ⊔ B, and
thus ∣T ∣ = 3 ⋅ 2n−1 − 1. By construction, the only element in T which might
not be primitive is g12 , and the rest are primitive by Nielsen transformations:
for any wM g1 ∈ B with M ≠ {1} we take some 1 ≠ i ∈ M and perform the
Nielsen transformation gi ↦ wM g1 (gi appears precisely once in wM g1 ), a similar
argument works for any wM ∈ A.
We claim that, for any pair of distinct words x, y ∈ T , if xH = yH then either
H contains a primitive element or g12 ∈ H (possibly both). We consider all cases:
−1
wM ′ ∈ H is primitive,
1. x, y ∈ A, so x = wM , y = wM ′ , with M ≠ M ′ . Then wM
′
−1
as there is some i ∈ M ∆M so Nielsen transform gi ↦ wM wM ′ .
2. Precisely one of x, y lie in A (say x ∈ A), so x = wM and y = wM ′ g1 .
−1
wM ′ g1 ∈ H is
We consider all subcases: 2A) 1 ∉ M, M ′ . In this case, wM
′
−1
primitive (Nielsen transform g1 ↦ wM wM ′ g1 ). 2B) 1 ∈ M , 1 ∉ M , and M ′ =
−1
M ∪ {1}. In this case, wM
wM ′ g1 = g12 ∈ H. 2C) 1 ∈ M ′ , 1 ∉ M , and there is
−1
wM ′ g1 ∈ H is a primitive element, as
some 1 < j ∈ M ∆M ′ . In this case, wM
−1
we can Nielsen transform gj ↦ wM wM ′ g1 . 2D) M = {1}. If M ′ = {1} then
−1
wM
wM ′ g1 = g1 ∈ H is a primitive element. Otherwise, there is some 1 ≠ j ∈ M ,
−1
wM ′ g1 ∈ H is a primitive element as we can Nielsen transform
in which case wM
−1
gj ↦ wM wM ′ g1 .
3. x, y ∈ B. In this case, x = wM g1 , y = wM ′ g1 (M ≠ M ′ ). If there is some
−1
1 ≠ i ∈ M ∆M ′ , then the element g1−1 wM
wM ′ g1 ∈ H is primitive. Otherwise,
′
−1
M = M ∪{1} (or vice-versa), in which case g1−1 wM
wM ′ g1 = g1±1 ∈ H is primitive.
Suppose that H contains no primitive element. Since ∣T ∣ = 3⋅2n−1 −1 ≥ [G ∶ H]
then either two elements of T lie in the same coset (so by the claim above, g12 ∈ H
as H contains no primitive element), or one element of T lies in H (which must
be g12 , as all other elements of T are primitive). So g12 ∈ H.
Now, take any primitive element x ∈ G, which is part of some generating set
{x, y2 , . . . , yn } for G (which must be left-cleaned, otherwise H would contain a
primitive element). Using the exact same argument above, with g1 ∶= x, gi ∶= yi
for all 2 ≤ i ≤ n, we see that if H contains no primitive element then x2 ∈ H. So
H contains the square of every primitive element.

We can strengthen Lemma 4.2 as follows:

TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

13

Lemma 4.3. Let G be any group with d(G) = n, and H a subgroup of finite
index in G with [G ∶ H] < 3 ⋅ 2n−1 . If H contains no primitive elements of G,
then H is normal in G and G/H ≅ C2m for some m ≤ n.
Proof. Suppose H contains no primitive element. Then, by Lemma 4.2, H contains the square of every primitive element. Set T ∶= {g 2 ∣ g is primitive in G}.
Then T is a normal subset of G, since the conjugate of a primitive element is
again a primitive element (conjugation is an automorphism). Thus ⟨T ⟩ ⊲ G; the
(normal) subgroup generated by all the squares of primitive elements of G. So
by hypothesis, T < H. Now take any generating set {t1 , . . . , tn } for G, then t−1
i tj
2 2
−1
2
is a primitive element, for any pair i, j with i ≠ j. Thus ti , tj , (ti tj ) lie in ⟨T ⟩,
2 −2
and hence so will t2i (t−1
i tj ) tj = [ti , tj ]. So G/⟨T ⟩ is abelian as ⟨T ⟩ is normal
and contains the commutator of every pair in the generating set {t1 , . . . , tn } for
G. So ⟨T ⟩, and hence H, contain the commutator subgroup [G, G]. Thus H is
normal in G and G/H is generated by the images of {t1 , . . . , tn }, all of which

have order 2 in this quotient. So G/H ≅ C2m for some m ≤ n.
We now give the following complete characterisation of finite index subgroups
of a group of rank n which contain primitive elements, up to index 3 ⋅ 2n−1 − 1.
Theorem 4.4. Let G be any group with d(G) = n and let H be a subgroup of
finite index in G with [G ∶ H] < 3⋅2n−1 . Then H contains no primitive elements
of G if and only if H is normal in G and the quotient G/H is isomorphic to
C2n , whereupon every coset distinct from H contains a primitive element of G.
Proof. First if H is normal and contains an element g of a generating n-tuple
for G then the image of this n-tuple gives rise to a generating (n − 1)-tuple of
G/H, just as in Lemma 4.1, but d(C2n ) = n.
Now suppose that H does not contain a primitive element of G and let
q ∶ G ↠ G/H be the quotient homomorphism, where we know H is normal in
G and G/H ≅ C2m for some m ≤ n by Lemma 4.3. Given a generating n-tuple
(g1 , . . . , gn ) for G, let Fn be the free group on x1 , . . . , xn and set θ ∶ Fn ↠ G to
be the homomorphism extending the map xi ↦ gi . Note that if we have k ≤ n
and integers 1 ≤ i1 < i2 < ⋅ ⋅ ⋅ < ik ≤ n then xi1 xi2 ⋯xik is primitive in Fn and
θ(xi1 xi2 ⋯xik ) = gi1 gi2 ⋯gik is primitive in G.
Assume that m < n and consider the map q ○ θ ∶ Fn ↠ C2m , which factors
through C2n via the abelianisation map ab ∶ Fn ↠ C2n and the map ψ ∶ C2n ↠ C2m .
That is, the following diagram commutes, and all maps are surjections:
Fn
θ

ab





G

/ Cn
2

q

ψ

/ Cm
2

As ψ is now a linear map from an n dimensional vector space over F2 to an
m dimensional space, we have a non-trivial element (v1 , . . . , vn ) of C2n in the
kernel of ψ. Now we can assume that each vi takes the value 0 or 1, so we form
the primitive element x = xv11 xv22 ⋯xvnn of Fn which maps to the identity under

14

JACK BUTTON, MAURICE CHIODO, MARIANO ZERON-MEDINA LARIS

ψ ○ ab, thus g1v1 g2v2 ⋯gnvn = θ(x) is a primitive element of G which maps to the
identity under q and so is in H; a contradiction.
Similarly if n = m then, for any (w1 , . . . , wn ) in Fn2 − {0}, the coset of H in
G corresponding to this point contains the primitive element g1w1 g2w2 ⋯gnwn of
G.

Thus if G is a group with d(G) = n we have two possibilities: either C2n is not
a quotient of G in which case all subgroups of G having index less than 3 ⋅ 2n−1
contain primitive elements, or G surjects to C2n in which case there is a single
subgroup of index less than 3 ⋅ 2n−1 which fails to contain a primitive element.
The uniqueness in the second case comes about because a homomorphism from
a rank n group G to an abelian group of exponent 2 must factor through
G/[G, G]G2 . As G/([G, G]G2 ) ≅ C2m for m ≤ n, we see that when n = m any
exceptional subgroup must be equal to [G, G]G2 .
Note that the inequality [G ∶ H] < 3 ⋅ 2n−1 in Theorem 4.4 is somewhat
necessary: here is an example of what occurs when the inequality doesn’t hold.
Example 4.5. Take the (free) subgroup H ∶= [Fn , Fn ]Fn2 < Fn of index 2n with
no primitive elements of Fn . Then H itself has several normal subgroups of
index 2, none of which contain primitive elements of Fn . In Fn , these subgroups
have index 2 ⋅ 2n > 3 ⋅ 2n−1 , so this is not a counterexample to Theorem 4.4.
We remark that the number of subgroups of Fn with index less than 3 ⋅ 2n−1
is vast: for instance by [11, Corollary 2.1.2] the number of subgroups of Fn
with index equal to 2n is bounded below by ((2n )!)n−1 , yet only one of these
subgroups fails to contain a primitive element by Theorem 4.4.
It would be interesting to find a closed form expression for M (n), which we
define to be the smallest number i such that Fn has a subgroup other than
[Fn , Fn ]Fn2 of index i which contains no primitive elements. By Theorem 4.4
and the example immediately proceeding it we have 3 ⋅ 2n−1 ≤ M (n) ≤ 2 ⋅ 2n . In
particular, consider any quotient map f ∶ F2 ↠ S3 ; the kernel N of this map
has index 6 = 3 ⋅ 22−1 , and moreover N contains no primitive elements of F2 by
Lemma 4.1. So M (2) = 6. Moreover, it is straightforward to see that M (1) = 3.
We do not know M (n) for any other values of n.
Our analysis of the possible location of primitive elements, relative to finite
index subgroups of Fn , was motivated by the following result of Parzanchevski
and Puder in [14]:
Theorem 4.6 ([14, Corollary 1.3]). The set P of primitive elements in Fn is
closed in the profinite topology.
Corollary 4.7. Given Fn , and w ∈ Fn a non-primitive element, there is a finite
index subgroup H < Fn such that the coset wH does not contain any primitive
elements (but of course contains w). Taking w = e gives a finite index subgroup
with no primitive elements.
Given that the above result is existential, we decided to apply our techniques
to look for explicit examples of subgroups with no primitive elements; Lemma
4.3 and Theorem 4.4 came about from this analysis, somewhat serendipitously.
We have shown that H = [Fn , Fn ]Fn2 is the (unique) finite index subgroup of

TRANSVERSALS AS GENERATING SETS IN FINITELY GENERATED GROUPS

15

Fn of smallest index to contain no primitive elements, and that the next such
example must have index i ≥ 3 ⋅ 2n−1 (with equality in the case n = 2).
We finish by remarking that a recent result of Clifford and Goldstein in [6]
proves there is an algorithm to determine whether or not a finitely generated
subgroup of Fn contains a primitive element, although they say that they do
not expect it to be implemented in practice. One of our overall aims is to
give a characterisation of such subgroups that leads to computationally-efficient
recognition.
References
[1] A. Blass, Injectivity, Projectivity, and the Axiom of Choice, Trans. Amer. Math. Soc.
255, 31–59, (1979).
[2] J. Button, M. Chiodo, M. Zeron-Medina Laris, Coset intersection graphs, and transversals as generating sets for finitely generated groups, J. González-Meneses et al. (eds.),
Extended Abstracts Fall 2012, Trends in Mathematics 5, 29–34, Birkhäuser, (2014).
[3] J. Button, M. Chiodo, M. Zeron-Medina Laris, Coset intersection graphs for groups,
Amer. Math. Monthly 121, No. 10, 922–926, (2014).
[4] P.
Cameron,
Generating
a
group
by
a
transversal
http://www.maths.qmul.ac.uk/∼pjc/papers.html
[5] P. Cameron, http://www.maths.qmul.ac.uk/∼pjc/oldprob.html
[6] A. Clifford and R. Goldstein, Subgroups of free groups and primitive elements, J. Group
Theory 13, 601–611, (2010).
[7] H. S. M. Coxeter, J. A. Todd, A practical method for enumerating cosets of a finite
abstract group, Proceedings of the Edinburgh Mathematical Society, Series II, 5, 26–34
(1936).
[8] M. Dunwoody, Nielsen transformations, 1970 Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967), 45–46, Pergamon, Oxford.
[9] M. J. Evans, Primitive elements in free groups, Proc. Amer. Math. Soc. 106, 313–316,
(1989).
[10] I. Kapovich, A. Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra.
248, 608–668, (2002).
[11] A. Lubotzky and D. Segal, Subgroup Growth, Progress in Mathematics 212, Birkhaüser
Verlag, Basel, (2003).
[12] G. A. Noskov, Primitive elements in a free group, Matematicheskie Zametki 30, 497–500,
(1981).
[13] I. Pak, What do we know about the product replacement algorithm?, Groups and computation, III, 301–347, Ohio State Univ. Math. Res. Inst. Publ. 8, de Gruyter, Berlin,
(2001).
[14] O. Parzanchevski, D. Puder, Measure preserving words are primitive, arXiv:1202.3269v1
(2012).
[15] J. Whiston, Maximal independent generating sets of the symmetric group, J. Algebra 232,
255–268, (2000).
Selwyn College, Cambridge
Grange Road, Cambridge, CB3 9DQ, UK
J.O.Button@dpmms.cam.ac.uk
Mathematics Department, University of Neuchâtel
Rue Emile-Argand 11, Neuchâtel, CH-2000, SWITZERLAND
maurice.chiodo@unine.ch
31 Mariner’s Way, Cambridge, CB4 1BN, UK
marianozeron@gmail.com

