arXiv:1803.08301v1 [math.GR] 22 Mar 2018

The Herzog-Schonheim conjecture for finitely
generated groups
Fabienne Chouraqui
March 23, 2018

Abstract
Let G be a group and H1 ,...,Hs be subgroups of G of indices
d1 ,...,ds respectively. In 1974, M. Herzog and J. Schönheim coni=s
jectured that if {Hi αi }i=1
, αi ∈ G, is a coset partition of G, then
d1 ,..,ds cannot be distinct. We consider the Herzog-Schönheim conjecture for free groups of finite rank and develop a new combinatorial
approach, using covering spaces. We give some sufficient conditions
on the coset partition that ensure the conjecture is satisfied. Furthermore, under a certain assumption, we show there is a finite number
of cases to study in order to show the conjecture is true for every
coset partition. Since every finitely generated group is a quotient of
a free group of finite rank, we show these results extend to finitely
generated groups.

1

Introduction

Let G be a group and H1 ,...,Hs be subgroups of G. If there exist αi ∈ G
i=s
S
such that G =
Hi αi , and the sets Hi αi , 1 ≤ i ≤ s, are pairwise disjoint,
i=1

then {Hi αi }i=s
i=1 is a coset partition of G (or a disjoint cover of G). In this
case, all the subgroups H1 ,...,Hs can be assumed to be of finite index in G
[30, 22]. We denote by d1 ,...,ds the indices of H1 ,...,Hs respectively. The
coset partition {Hi αi }i=s
i=1 has multiplicity if di = dj for some i 6= j. The
Herzog-Schönheim conjecture is true for the group G, if any coset partition
of G has multiplicity.
If G is the infinite cyclic group Z, a coset partition of Z is {di Z + ri }i=s
i=1 ,
ri ∈ Z, with each di Z + ri the residue class of ri modulo di . These coset
partitions of Z were first introduced by P. Erdös [10] and he conjectured

1

that if {di Z + ri }i=s
i=1 , ri ∈ Z, is a coset partition of Z, then the largest index ds appears at least twice. Erdös’ conjecture was proved independently
by H. Davenport, L. Mirsky, D. Newman and R.Rado using analysis of
complex function [11, 30, 31]. Furthermore, it was proved that the largest
index ds appears at least p times, where p is the smallest prime dividing
ds [30, 31, 46], that each index di divides another index dj , j 6= i, and
that each index dk that does not properly divide any other index appears
at least twice [31]. We refer also to [34, 35, 36, 37, 47] for more details on
coset partitions of Z (also called covers of Z by arithmetic progressions)
and to [15] for a proof of the Erdös’ conjecture using group representations.
In 1974, M. Herzog and J. Schönheim extended Erdös’ conjecture for
i=s , α ∈ G, is a coset pararbitrary groups and conjectured that if {Hi αi }i=1
i
tition of G, then d1 ,..,ds cannot be distinct. In the 1980’s, in a series of papers, M.A. Berger, A. Felzenbaum and A.S. Fraenkel studied the HerzogSchönheim conjecture [2, 3, 4] and in [5] they proved the conjecture is true
for the pyramidal groups, a subclass of the finite solvable groups. Coset
partitions of finite groups with additional assumptions on the subgroups
of the partition have been extensively studied. We refer to [6, 50, 51, 45].
In [26], the authors very recently proved that the conjecture is true for all
groups of order less than 1440.
The common approach to the Herzog-Schönheim conjecture is to study
it in finite groups. Indeed, given any group G, every coset partition of G
induces a coset partition of a particular finite quotient group of G with
the same indices (the quotient of G by the intersection of the normal cores
of the subgroups from the partition) [22]. In this paper, we adopt a completely different approach to the Herzog-Schönheim conjecture. Instead
of finite groups, we consider free groups of finite rank and develop a new
approach to the problem. This approach has two advantages. First, it permits to study the Herzog-Schönheim conjecture in the free groups of finite
rank for their own sake and secondly it provides some answers for every
finitely generated group. Indeed, we show any coset partition of a finitely
generated group G induces a coset partition of F with the same indices.
In order to study the Herzog-Schönheim conjecture in free groups of
finite rank, we use the machinery of covering spaces. A pair (X̃, p) is a
covering space of a topological space X if X̃ is a path connected space,
p : X̃ → X is an open continuous surjection and every x ∈ X has an
open neighborhood Ux such that p−1 (Ux ) is a disjoint union of open sets
in X̃, each of which is mapped homeomorphically onto Ux by p. For each
x ∈ X, the non-empty set Yx = p−1 (x) is called the fiber over x and for all
2

x, x′ ∈ X, | Yx |=| Yx′ |. If the cardinal of a fiber is m, one says that (X̃, p)
is a m-sheeted covering (m-fold cover) of X. The fundamental group of
the bouquet with n leaves (or the wedge sum of n circles), X, is Fn , the
free group of finite rank n. As X is a “good” space (connected, locally path
connected and semilocally 1-connected), X has a universal covering which
can be identified with the Cayley graph of Fn , an infinite simplicial tree.
Furthermore, there exists a one-to-one correspondence between the subgroups of Fn and the covering spaces (together with a chosen point) of X.
Using these covering spaces, J. Stallings gave a topological proof of some
classical results about finitely generated subgroups of Fn and introduced
the notion of folding [43].
For any subgroup H of Fn of finite index d, there exists a d-sheeted covering space (X̃H , p) with a fixed basepoint, which is also a combinatorial
object. Indeed, the underlying graph of X̃H is a directed labelled graph,
with d vertices, that can be seen as a finite complete bi-deterministic automaton; fixing the start and the end state at the basepoint, it recognises
the set of elements in H. It is called the Schreier coset diagram for Fn relative to the subgroup H [44, p.107] or the Schreier automaton for Fn relative to the subgroup H [42, p.102]. The d vertices (or states) correspond
a
to the d right cosets of H, each edge (or transition) Hg −
→ Hga, g ∈ Fn ,
a a generator of Fn , describes the right action of a on Hg. The transition
group T of the Schreier automaton for Fn relative to H describes the action of Fn on the set of the d right cosets of H, and is generated
 by n perF
n
, where
mutations. The group T is a subgroup of Sd such that T ≃
NH
T −1
g Hg is the normal core of H.
NH =
g∈Fn

Given H ≤ Fn of index d, we consider the covering (X̃H , p) of X with
basepoint x̃0 , from several points of view in parallel: as a covering, as a
Schreier coset diagram for Fn relative to the subgroup H, as a complete
automaton. We use the following terminology. Let X̃H denote the Schreier
coset diagram for Fn relative to the subgroup H. Let x̃0 , ..., x̃d−1 be the d
vertices in X̃H . Let ti denote the label of a minimal path from x̃0 to any
vertex x̃i , 1 ≤ i ≤ d − 1. Let T = {1, ti | 1 ≤ i ≤ d − 1}. As X̃H is the
Schreier coset diagram for Fn relative to the subgroup H, x̃0 represents the
subgroup H and x̃1 , ..., x̃d−1 represent the cosets Hti accordingly. We call
X̃H the Schreier graph of H, with this correspondence between the vertices
x̃0 , x̃1 , ..., x̃d−1 and the cosets H, Ht1 ,...,Hts accordingly.
The intuitive idea behind our approach is as follows. Let {Hi αi }i=s
i=1 be
a coset partition of Fn , n ≥ 2, with Hi < Fn of index di > 1, αi ∈ Fn ,

3

1 ≤ i ≤ s. Let w ∈ Fn . For every Schreier graph X̃i , 1 ≤ i ≤ s, we define a graph X̃i (w) that describes the action of w on the vertices of X̃i . We
denote by o∗i (w) the minimal natural number, 1 ≤ o∗i (w) ≤ di , such that
wo∗i (w) is a loop at the vertex Hi αi . Combining in some way the s graphs,
X̃1 (w),...,X̃s (w), we define a new finite graph, the HS-colored graph, to describe graphically the coset partition of Fn .
We show the HS-colored graph is the disjoint union of loops of the same
length, that satisfies many interesting properties. In particular, we show
that each loop ℓ describes a coset partition of Z, with subgroups of indices
{o∗i (w) | i ∈ Iℓ }, where Iℓ ⊆ {1, 2, ..., s} and we can then apply the results
on the Erdös’ conjecture. Indeed, if omax (w) = max{o∗i (w) | 1 ≤ i ≤ s},
then o∗i (w) = omax (w), for at least p values of i, where p is the smallest
prime dividing omax (w). Since each o∗i (w) is the length of a cycle in some
permutation in Ti , we can formulate our results in terms of cycles in the
permutation groups T1 ,...,Ts . In particular, if omax = max{omax (w) | w ∈
Fn } = ds , we have the following first result.
Theorem 1. Let Fn be the free group on n ≥ 2 generators. Let {Hi αi }i=s
i=1
be a coset partition of Fn with Hi < Fn of index di , αi ∈ Fn , 1 ≤ i ≤ s,
and 1 < d1 ≤ ... ≤ ds . Let X̃i denote the Schreier graph of Hi , with
transition group Ti , 1 ≤ i ≤ s. If there exists a ds -cycle in Ts , then the
index ds appears in the partition at least p times, where p is the smallest
prime dividing ds . Furthermore, all the subgroups Hi with same index are
isomorphic.
The transition group Ts is a subgroup of the symmetric group Sds , generated by n ≥ 2 permutations. Dixon proved that the probability that a
random pair of elements of Sn generate Sn approaches 3/4 as n → ∞, and
the probability that they generate An approaches 1/4 [8]. As ds → ∞, the
probability that Ts is the symmetric group Sds approaches 3/4. So, asymptotically, the probability that there exists a ds -cycle in Ts is greater than
3/4. If Ts is cyclic, there exists a ds -cycle in Ts , since ds divides the order
of Ts . That is, Theorem 1 is satisfied with very high probability and the
conjecture is “asymptotically satisfied with probability greater than 3/4”
for free groups of finite rank.
Theorem 2 provides a list of conditions on a coset partition that ensure
multiplicity. Let k = max{omax (w) | w ∈ Fn }, k is the maximal length of a
i=s
S
cycle in
Ti . Let p denote the smallest prime dividing k. We show there
i=1

exists u ∈ Fn such that omax (u) = k and # ≥ 2, where # =| {1 ≤ i ≤ s |
o∗i (u) = k} |. Using this notation, we have the following result.
4

Theorem 2. Let Fn be the free group on n ≥ 2 generators. Let {Hi αi }i=s
i=1
be a coset partition of Fn with Hi < Fn of index di , αi ∈ Fn , 1 ≤ i ≤ s,
and 1 < d1 ≤ ... ≤ ds . Let r be an integer, 4 ≤ r ≤ s − 1. If k, p and #, as
defined above, satisfy one of the following conditions:
(i) k > ds−2 .
(ii) k > ds−3 , p ≥ 3.
(iii) k > ds−3 , p = 2, and # = 2 or # ≥ 4.
(iv) k > ds−r and p ≥ r, or # = p, or # ≥ r + 1.
Then the coset partition {Hi αi }i=s
i=1 has multiplicity.
Assuming that k > d1 , there is a finite number of cases that are not
covered by Theorem 2. For k > ds−3 , there is only one case which is not
covered: p = 2, # = 3. For k > ds−4 , there are three cases which are not
covered: p = 2, # = 3, 4 and p = 3, # = 4. As r grows, the number
of cases not covered by Theorem 2 grows also, but as s is finite, the total
number of cases not covered by Theorem 2 is finite.
In the following Theorem, we give a condition that ensures the same
subgroup appears at least twice in the partition.
Theorem 3. Let Fn be the free group on n ≥ 2 generators. Let {Hi αi }i=s
i=1
be a coset partition of Fn with Hi < Fn of index di > 1, αi ∈ Fn , 1 ≤ i ≤ s.
If one of the following conditions holds:
(i) There exist 1 ≤ j, k ≤ s such that

i=s
T

i=1

α−1
i Hi αi $

T

i6=j,k

α−1
i Hi αi .

(ii) There exist 1T≤ j, k ≤ s such that ℓcm(dj , dk ) does not divide the
α−1
index [Fn :
i Hi αi ].
i6=j,k

i=s has multiplicity. Furthermore, H = H .
Then {Hi αi }i=1
j
k

In the paper, we give several conditions that ensure the coset partition
{Hi αi }i=s
i=1 has multiplicity, with a fixed number of repetitions of one of the
indices. We present here a more restrictive condition that ensures that, but
easier to describe in the introduction and algorithmically speaking very
easy to check.

5

Theorem 4. Let Fn be the free group on n ≥ 2 generators. Let {Hi αi }i=s
i=1
be a coset partition
of
F
with
H
<
F
of
index
d
>
1,
α
∈
F
,
1
≤
i
≤
s.
n
i
n
i
i
n
T −1
g Hi g of index mi . If there exists a prime p such that
Let Ni =
g∈Fn

p divides mi for exactly p values of i, j1 , ..., jp , then the coset partition
{Hi αi }i=s
i=1 has multiplicity, with dj1 = ... = djp .
We now turn to finitely generated groups in general.

Theorem 5. Let G ≃ Fn K , with canonical epimorphism π : Fn → G.
Let {Ki gi }i=s
i=1 be a coset partition of G with Ki < G of index di > 1,
gi ∈ G, 1 ≤ i ≤ s. Let Hi = π −1 (Ki ) and αi = π −1 (gi ). Then there exists
{Hi αi }i=s
i=1 an induced coset partition of Fn , with Hi < Fn of index di ,
αi ∈ Fn , 1 ≤ i ≤ s. Furthermore, if for {Hi αi }i=s
i=1 , one of the conditions
from Theorem 1, 2, 3, or 4 is satisfied, then the coset partition {Ki gi }i=s
i=1
has multiplicity.
The paper is organized as follows. The two first sections are background
sections: Section 1 on free groups and covering spaces and Section 2 on
graphs and automatons. In Section 3, we describe the equivalent approaches
to covering spaces in the special case of free groups and in particular we
present the Schreier graph and its properties. In Section 4, we give a graphical description of the coset partition of Fn in terms of the Schreier graphs,
and in particular in the case of Z. Sections 6 is devoted to the proofs of
the main results. In Section 7, we consider the case of any finitely generated group. In many places, we write the HS conjecture instead of the
Herzog-Schönheim conjecture.
Acknowledgment. I am very grateful to Yuval Ginosar for introducing
me to the Herzog-Schönheim conjecture, to Luis Paris for suggesting me
to study the conjecture in free groups, and to Aryeh Juhasz for his useful
comments on the paper.

2
2.1

Free Groups and Covering spaces
Free Groups

For more details, we refer the reader to the books [24, Chapter 1], [25, Section 1.4], [1, Chapter 1]. Let X be a non-empty set. The group generated
by X is hXi = {xǫ11 xǫ22 ..xǫnn | xi ∈ X, ǫi = ±1, n ≥ 0}, this is the set of all
words on X. If X is finite, the group generated by X is finitely generated.
A word w = xǫ11 xǫ22 ..xǫnn is reduced if xi = xi+1 implies ǫi + ǫi+1 6= 0 and
6

in this case the length of w, ℓ(w), is equal to n. A word w = xǫ11 xǫ22 ..xǫnn
is cyclically reduced if x1 = xn implies ǫ1 + ǫn 6= 0. If F = hXi and every non-empty reduced word w 6= 1 in F , then we say that X is a free set
of generators of F or that F is free with base X. It holds that all bases
for a given free group have the same cardinal and this common cardinal
is termed the rank of the free group F and denoted by rank(F ). The free
group of rank n is denoted by Fn and Fn is isomorphic to Fm (Fn ≃ Fm ) if
and only if n = m. The free group is torsion-free and the Nielsen-Schreier
theorem states that every subgroup of a free group is free.
Theorem 2.1. [24, p.20] If H is a subgroup of Fn of finite index d, then
(i) H is a free group of rank d(n − 1) + 1.
(ii) H has non-trivial intersection with every non-trivial subgroup of Fn .
(iii) If K is a subgroup of Fn of same index d, then K ≃ H.
Note that a finitely generated subgroup of Fn is not necessarily of finite
index and that there exist infinitely generated subgroups in Fn . A set S of
representatives of the right cosets of a subgroup H in a group G generated
by X is called a (right) Schreier transversal if whenever xǫ11 xǫ22 ..xǫnn ∈ S,
ǫn−1
xi ∈ X, then xǫ11 xǫ22 ..xn−1
is also in S. If H is a subgroup of the free group
Fn , then there exists a right Schreier transversal of H in Fn .
Theorem 2.2. [24,p.1] If G is a group generated by a set of n of its elements, then G ≃ Fn N , with N ⊳ Fn .

If G ≃ Fn N , then the group G has a presentation hX | Ri, where X is a
base of Fn and the normal closure of the set R is equal to N . If X and R
are finite, the group G is finitely presented.

2.2

Covering spaces

For more details, we refer the reader to the books [40, Chapter 10], [19,
Chapter 1], [24, Chapter 3], [44], [13].
Definition 2.3. If X is a topological space, then (X̃, p) is a covering space
of X if:
(i) X̃ is a path connected topological space;
(ii) p : X̃ → X is continuous;

7

(iii) Each point x ∈ X has an open neighborhood Ux such that p−1 (Ux )
is a disjoint union of open sets in X̃, each of which is mapped homeomorphically onto Ux by p.
If (X̃, p) is a covering space of X, then p is an open continuous surjection and X is path connected. For each x ∈ X, the non-empty set
Yx = p−1 (x) is called the fiber over x and for all x, x′ ∈ X, | Yx |=| Yx′ |.
The cardinal of a fiber is called the multiplicity of the covering. One also
says that (X̃, p) is a m-sheeted covering (m-fold cover ) of X.
Example 2.4. The exponential map exp : R → S 1 with exp(t) = e2πit is
an example of an infinite-sheeted covering of S 1 .

Figure 2.4.1: An infinite-sheeted covering of S 1 .
Let X be a space and x0 ∈ X a point. Roughly, the fundamental group of
X with basepoint x0 , denoted by π1 (X, x0 ), is the set of equivalence classes
of closed loops based at x0 (up to homotopy), with the operation of
concatenation. If X is path-connected, the fundamental group of X is
independent of the choice of the basepoint, that is if x0 , x1 ∈ X, then
π1 (X, x0 ) ≃ π1 (X, x1 ). A space X is simply connected, if it is
path-connected and π1 (X, x0 ) = 1, for every x0 ∈ X. If X and X̃ are
spaces and there is a continuous map p : X̃ → X, with p(x̃0 ) = x0 , then
there is an induced homomorphism p∗ : π1 (X̃, x̃0 ) → π1 (X, x0 ). If [f ] is a
loop class in X̃, then p∗ ([f ]) = [p(f )], a loop class in X. For more details,
we refer the reader to [40, Chapter 3].
Theorem 2.5. [40, p.279-281] Let (X̃, p) be a covering space of X. Let G
denote the fundamental group of X, π1 (X, x0 ), with basepoint x0 ∈ X. Let
Y0 denote the fiber over x0 and π1 (X̃, x̃0 ) denote the fundamental group of
X̃ with x̃0 ∈ Y0 . Then
(i) The induced homomorphism p∗ : π1 (X̃, x̃0 ) → G is an injection.
8

(ii) G acts transitively on Y0 .
(iii) The stabilizer of x̃0 is p∗ (π1 (X̃, x̃0 )).
(iv) | Y0 |= [G : p∗ (π1 (X̃, x̃0 ))].
(v) p∗ (π1 (X̃, x̃0 )) and p∗ (π1 (X̃, x̃1 )) are conjugates subgroups of G, for
every x̃1 ∈ Y0 .
(vi) If K ≤ G is conjugate to p∗ (π1 (X̃, x̃0 )), then there exists x̃1 ∈ Y0
such that K = p∗ (π1 (X̃, x̃1 )).
Example 2.6. Let X be the two-leaves bouquet, with
π1 (X̃, x̃0 ) = F2 = ha, bi. Let (X̃, p) be the following covering space, with
p(x̃0 ) = p(x̃1 ) = p(x̃2 ) = x0 . Then G = p∗ (π1 (X̃, x̃0 )) = hb, a2 , ab2 a, ababai
is a subgroup of F2 of index 3, since the fiber over x0 contains 3 elements.
Moreover, every closed loop at x̃0 is an element of G and stabilizes x̃0 . The
group p∗ (π1 (X̃, x̃1 )) is a subgroup of F2 , conjugate to G:
p∗ (π1 (X̃, x̃1 )) = hb2 , a2 , bab, abai = a−1 Ga. Also,
p∗ (π1 (X̃, x̃2 )) = (ab)−1 G(ab).
a
b

x̃0

b

x̃1
a

x̃2

a

b

↓p

b

x0

a

Figure 2.6.1: A 3-sheeted covering space of the two-leaves bouquet.

Definition 2.7. Let (X̃, p) be a covering space of X. Let G denote the
fundamental group of X, π1 (X, x0 ), with basepoint x0 ∈ X and π1 (X̃, x̃0 )
the fundamental group of X̃ with x̃0 in the fiber over x0 .
(i) The covering space (X̃, p) of X is universal if X̃ is simply-connected.
9

(ii) The covering space (X̃, p) of X is regular if p∗ (π1 (X̃, x̃0 )) ⊳ G.
(iii) A Deck transformation of X̃ is a homeomorphism h : X̃ → X̃ with
p ◦ h = p.
(iv) The Deck group, Cov(X̃/X), is the group of Deck transformations.
The Deck group Cov(X̃/X) acts freely on X̃.
Theorem 2.8. [40, p.289-294] Let X be a locally path connected space.
Let G denote the fundamental group of X, π1 (X, x0 ), with basepoint
x0 ∈ X. Let (X̃, p) be a covering space of X and let H denote the
fundamental group of X̃, π1 (X̃, x̃0 ), with x̃0 in the fiber over x0 . Then

(i) Cov(X̃/X) ≃ N (H) H , where N (H) is the normaliser of H in G.

(ii) (X̃, p) is regular if and only if Cov(X̃/X) ≃ G H .
(iii) If (X̃, p) is universal, then Cov(X̃/X) ≃ G.
(iv) If X is connected, then (X̃, p) is regular if and only if Cov(X̃/X)
acts transitively on the fiber over x0 .
Example 2.9. The following covering space (X˜H , p) over the two-leaved
bouquet X, with p(x̃0 ) = p(x̃1 ) = x0 , is regular. Let H = π1(X̃, x̃0 ) (or
π1 (X̃, x̃1 )), then H = hb, a2 , abai ⊳ F2 and Cov(X̃/X) ≃ F2 H ≃ S2 (the
symmetric group).
a
b

x̃0

x̃1

b

a

↓p

b

x0

a

Figure 2.9.1: The 2-sheeted regular covering (X̃H , p) over X.

10

Two covering spaces (X̃, p) and (Ỹ , q) of a space X are equivalent if there
exists a homeomorphism ϕ : Ỹ → X̃ making this diagram commute:
ϕ
Ỹ
X̃
q

X

p

If X is a locally path connected space, then the covering spaces (X̃, p) and
(Ỹ , q) of X are equivalent if and only if p∗ (π1 (X̃, x̃0 )) and q∗ (π1 (Ỹ , ỹ0 ))
are conjugate subgroups of π1 (X, x0 ), with x̃0 ∈ p−1 (x0 ) and ỹ0 ∈ q −1 (x0 ).
If X satisfies several conditions, a converse to Theorem 2.5 is true, that is
given x0 ∈ X and a subgroup H of π1 (X, x0 ), there exists a covering space
(X̃, p) of X, with p∗ (π1 (X̃, x˜0 )) = H for a suitably chosen basepoint
x̃0 ∈ X̃. A space X is semilocally 1-connected if each x ∈ X has an open
neighborhood U so that i∗ : π1 (U, x) → π1 (X, x) is the trivial map (where
i : U ֒−
→ X is the inclusion). A connected and locally path connected space
X has a universal covering if and only if X is semilocally 1-connected.
Theorem 2.10. [40, p.295-300] Let X be a connected, locally path
connected and semilocally 1-connected space. Let x0 ∈ X. Let H be a
subgroup of π1 (X, x0 ). Then there exists a covering space (X̃, p) of X, and
x̃0 ∈ p−1 (x0 ) such that p∗ (π1 (X̃, x̃0 )) = H.
The free group of finite rank n, Fn , is the fundamental group of the wedge
sum of n circles, the bouquet with n leaves, which is a space that satisfies
all the conditions of Theorem 2.10. So, we can take for granted the
one-to-one correspondence between the subgroups of Fn and the covering
spaces (together with a chosen point) of the bouquet with n leaves.
Furthermore, the n-leaves bouquet has a universal covering which can be
identified with the Cayley graph of the free group, an infinite tree. In this
work, our main interest is on subgroups of finite index of the free group of
finite rank n. Our approach consists in considering the corresponding
covering space (together with a chosen point) over the bouquet with n
leaves.
Example 2.11. Let K = hb, a2 , ab2 a, aba2 ba, (ab)3 ai be a subgroup of
index 4 in F2 . So, there exist a covering space (X̃K , p′ ) over X (the
2-leaves bouquet) and a chosen basepoint x̃00 (or x̃01 ) such that
p′∗ (π1 (X̃K , x̃00 )) = K. Note that this covering is not regular, since x̃00
cannot be mapped homeomorphically to x̃10 , although they both belong to
the fiber p′−1 (x0 ), so K is not normal in F2 .
11

a
b

b

x̃00

a

x̃10
a

x̃11

x̃01
a

b

↓p

′

x0

b

b

a

Figure 2.11.1: The 4-sheeted covering (X̃K , p′ ) over X.
Let H = hb, a2 , abai ⊳ F2 with covering described in Figure 2.9.1 (Example
2.9). As H has index 2 in F2 , it is a free group of rank 3 (from Theorem
2.1) and so it is the fundamental group of a 3-leaves bouquet XH with
leaves labelled b, a2 and aba. Consider K = hb, a2 , ab2 a, aba2 ba, (ab)3 ai
from Figure 2.11.1, K is a subgroup of H of index 2 in H. So, there exists
a covering space (X̂K , q) over XH such that q(x̃00 ) = q(x̃01 ) = x̃0 :
b

b
aba

a2

x̃00

x̃01

a2

aba

↓q
b
aba
a2

x̃0

Figure 2.11.2: The 2-sheeted regular covering (X̂K , q) over XH .
Consider again Figure 2.11.1. If we choose another basepoint x̃10 (or x̃11 )
in X̃K , then L = p′∗ (π1 (X̃K , x̃10 )) = a−1 Ka is a conjugate subgroup of K
which is also a subgroup of H. So, there exists also a covering space
(X̂L , q ′ ) over XH such that q ′ (x̃10 ) = q ′ (x̃11 ) = x̃1 (or x̃0 ). Each of these
coverings is regular. Indeed, H acts freely and transitively on each fiber in
12

X̂K and in X̂L . In Figure 2.11.3, we describe the regular coverings of
(X̂K , q) over XH and of (X̂L , q ′ ) over XH together, in order to keep as
much information as possible.
b

aba

x̃01

a2

x̃11

a2

aba

b
aba

b

x̃00

a2

x̃10

a2

b

aba
′
↓q

↓q
b

b
aba

aba

x̃0

x̃1

a2

a2

Figure 2.11.3: At left, the regular covering (X̂K , q) over XH . At right, the
regular covering (X̂L , q ′ ) over XH .

3
3.1

Graphs and Automata
Graphs

For more details, we refer the reader to [41], [43], [18]. A graph Γ consits of
two sets V and E, and two maps E → V × V : e 7→ (i(e), t(e)) and E → E
: e 7→ ē, which satisfy the following conditions: ∀e ∈ E, ē 6= e, ē¯ = e and
i(ē) = t(e). An element v ∈ V is called a vertex of Γ, e ∈ E is called an
edge of Γ and ē is called the reverse of e. The vertex i(e) is the initial
vertex of e (or origin) and t(e) the terminal vertex of e (or terminus).
These two vertices are called the extremities of e and two vertices are
adjacent if they are the extremities of some edge. An orientation of Γ
consists of a choice of exactly one edge in each pair {e, ē}, and in this case

13

Γ is called a directed graph. The indegree(v) is the cardinal of
{e ∈ E | t(e) = v} and the outdegree(v) is the cardinal of
{e ∈ E | i(e) = v}. A map of graphs f : Γ → ∆ consits of a pair of
functions, edges to edges, vertices to vertices, preserving the structure.
A path p in Γ of length n ≥ 0, with origin v1 and terminus vn is an
n−tuple of edges of Γ, p = e1 e2 ...en , such that for j = 1, .., n − 1,
t(ej ) = i(ej+1 ) and v1 = i(e1 ), vn = t(en ). For n = 0, given any vertex v,
there is a unique path of lenth 0 whose initial and terminal vertices
coincide and are equal to v. A path p is reduced if ej 6= ēj+1 ,
1 ≤ j ≤ n − 1. A path p is a loop at v if v is both its origin and its
terminus. A loop of length 1 at v contributes 1 to the indegree of v and 1
to its outdegree. Informally, the fundamental group π1 (Γ, v) is the group
generated by all the reduced loops based at v (up to some equivalence).
For a more precise definition, see [43][p.553], [40][p.44]. A map of graphs
f : Γ → ∆ induces a homomorphism of groups f∗ : π1 (Γ, v) → π1 (∆, f (v)).
A graph Γ is connected, if any pair of vertices is joined by some path and
in this case for any chosen basepoint v the groups π1 (Γ, v) are isomorphic
groups.

3.2

Automata

We refer the reader to [42, p.96], [9, p.7], [32]. A finite state automaton is
a quintuple (S, A, µ, Y, s0 ), where S is a finite set, called the state set, A is
a finite set, called the alphabet, µ : S × A → S is a function, called the
transition function, Y is a (possibly empty) subset of S called the accept
(or final) states, and s0 is called the start state. It is a directed graph with
a
vertices the states and each transition s −
→ s′ between states s and s′ is an
edge with label a ∈ A. The label of a path p of length n is the product
a1 a2 ..an of the labels of the edges of p. The finite state automaton
M = (S, A, µ, Y, s0 ) is deterministic if there is only one initial state and
each state is the source of exactly one arrow with any given label from A.
In a deterministic automaton, a path is determined by its starting point
and its label [42, p.105]. It is co-deterministic if there is only one final
state and each state is the target of exactly one arrow with any given label
from A. The finite state automaton M = (S, A, µ, Y, s0 ) is bi-deterministic
if it is both deterministic and co-deterministic. An automaton M is
complete if for each state s ∈ S and for each a ∈ A, there is exactly one
edge from s labelled a.

14

a

s2

s2

a

a

s3

s3

a

s1

s1

Figure 3.0.1: Forbidden configurations in a bi-deterministic automaton
(a ∈ A, s1 , s2 , s3 states).
Definition 3.1. Let M = (S, A, µ, Y, s0 ) be a finite state automaton. Let
A∗ be the free monoid generated by A. Let Map(S, S) be the monoid
consisting of all maps from S to S. The map φ : A → Map(S, S) given by
µ can be extended in a unique way to a monoid homomorphism
φ : A∗ → Map(S, S). The range of this map is a monoid called the
transition monoid of M , which is generated by {φ(a) | a ∈ A}. An element
w ∈ A∗ is accepted by M if the corresponding element of Map(S, S), φ(w),
takes s0 to an element of the accept states set Y . The set L ⊆ A∗
recognized by M is called the language accepted by M , denoted by L(M ).
In order to extend this definition to languages in groups, one takes the
alphabet A of monoid generators to be closed under inverses and each
x
a
→ s,
transition s −
→ s′ labelled by a ∈ A induces a "reverse" transition s′ −
with x = a−1 .
Example 3.2. Let A = {a, b, x = a−1 , y = b−1 } be an alphabet. So, A∗ is
F2 . The transition monoid T of the following complete automaton M is
generated by {φa = φx = (s0 , s1 ), φb = φy = (s1 , s2 )}, that is S3 .
a/x
b/y

s0

b/y

s1

s2

a/x

a/x

b/y

Figure 3.2.1: A complete bi-deterministic automaton M on A = {a, b, x =
a−1 , y = b−1 }, with three states: s0 , s1 , s2 .
The automaton M from Figure 3.2.1 has no forbidden configurations and
in order to be a bi-deterministic automaton, we need to specify a unique
start state and a unique accept state. For this automaton M , we consider
several cases and describe the consequences of our choices on the accepted
15

language by M . If s0 is both the start and accept state of M , the language
recognized by M , L(M ), is the subgroup H of A∗ generated by
{b, a2 , ab2 a, ababa}. If s1 is both the start and accept state of M , then
L(M ) is the subgroup a−1 Ha of A∗ and if s2 is both the start and accept
state of M , then L(M ) is the subgroup (ab)−1 H(ab) of A∗ . If s0 is the
start state of M and s1 its accept state, then L(M ) is the coset Ha of H.
If s0 is the start state of M and s2 its accept state, then L(M ) is the coset
Hab of H. When s0 is both the start and accept state of M , M is called
the Schreier automaton for F2 relative to the subgroup H [42, p.102]. More
generally:
Definition 3.3. Let A be a finite set of monoid generators closed under
inverses. Let A∗ the free monoid generated by A. Let G be a group
generated by A and H a subgroup of finite index in G. The finite state
automaton M = (S, A, µ, H, H), with state set S the set of right cosets of
H in G, alphabet A, transition function µ the natural action of G on the
right cosets of H, H the start and accept state, is called the Schreier
automaton for G relative to the subgroup H.
The Schreier automaton M for G relative to a subgroup H of index d is a
finite, complete and bi-deterministic automaton, with transition monoid T
a group of permutations in Sd . Indeed, each state represents a right coset
of H and the transitions in the automaton describe the (right) action of G

T −1
g Hg is the
on the set of right cosets, with T ≃ G N , where NH =
H

g∈G

normal core of H.

4
4.1

Covering spaces in the context of free groups
How to look at the covering space of the n-leaves
bouquet ?

We refer to [44, Chapter 2], and [21] for details. Let X denote the n-leaves
bouquet with basepoint x0 . Its fundamental group π1 (X, x0 ) is Fn , the free
group of rank n. Given H ≤ Fn of index d, there exists a covering (X̃H , p)
of X with basepoint x̃0 , from the one-to-one correspondence between
subgroups of index d in Fn and d-sheeted covering spaces (X̃, p) of X with
a chosen basepoint (see Theorem 2.10). The covering (X̃H , p) can be
viewed as a directed and labelled graph. Using this covering space, J.
Stallings gave a topological proof of some classical results about finitely
generated subgroups of Fn . In [43], he introduced the topological notion of
16

a folding, and used it in the study of finitely generated subgroups of a free
group.
The folding corresponding to a finitely generated subgroup H of Fn is a
directed labelled graph, that can be considered as a finite deterministic
automaton; fixing the start and the end state at a distinguished vertex, it
recognises the set of elements in H. Stalling’s approach has been applied
to solve many combinatorial and algorithmic problems in group theory. In
the years 1980-90, similar graphical approaches were developed in the
study of finitely generated subgroups of the free group, in order to solve
many special cases of the Hanna Neumann conjecture [14, 28, 49], which
states: rank(H ∩ K) − 1 ≤ (rank(H) − 1)(rank(K) − 1), where H and K
are finitely generated subgroups of the free group (of ranks rank(H) and
rank(K) respectively). It was recently solved [27], [12], [7].
In this work, our approach is the following: given H ≤ Fn of index d, we
consider the covering (X̃H , p) of X with basepoint x̃0 , from several points
of view in parallel: as a covering, as a Schreier coset diagram for Fn
relative to the subgroup H, as a complete and "almost" bi-deterministic
automaton, in the sense that we do not fix the start and accept states in
advance, but we fix them differently at our needs. We will use all these
points of view together. More formally:
Definition 4.1. Let H < Fn be of finite index d. Let (X̃H , p) be the
covering of the n-leaves bouquet with basepoint x̃0 and vertices
x̃0 , x̃1 , ..., x̃d−1 . Let ti denote the label of a minimal path from x̃0 to x̃i .
Let T = {1, ti | 1 ≤ i ≤ d − 1}. As X̃H is the Schreier coset diagram for
Fn relative to the subgroup H, x̃0 represents the subgroup H and the
other vertices x̃1 , ..., x̃d−1 represent the cosets Hti accordingly. We call X̃H
the Schreier graph of H, with this correspondence between the vertices
x̃0 , x̃1 , ..., x̃d−1 and the cosets Hti accordingly.
Note that a minimal path from x̃0 to x̃i is not necessarily unique, so we
choose arbitrarily one. The transversal T may be a Schreier transversal or
any transversal with representatives of minimal length.
Example 4.2. Consider the covering (X̃, p) from Example 2.6 (see also
Figure 3.2.1), with G = p∗ (π1 (X̃, x̃0 )) = hb, a2 , ab2 a, ababai a subgroup of
F2 of index 3. Replacing x̃0 by G and the other vertices accordingly, this
covering is the following Schreier coset diagram with T = {1, a, ab} a
Schreier transversal for G:

17

b

a

G

b

Ga

a

Gab

a

b

Figure 4.2.1: The Schreier graph of G = hb, a2 , ab2 a, (ab)3 i.

Remark 4.3. If H ≤ Fn of index d with Schreier graph X̃H , then from

Theorem 2.10 (covering theory), the Deck group Cov(X̃/X) ≃ N (H) H ,
where N (H) is the normaliser of H in
 Fn . From Section 3.2 (automaton
F
n
, where NH is the normal core of
theory), the transition group T ≃
N
H

H. So, whenever H is a normal subgroup of Fn , Cov(X̃/X) ≃ T and it
can be read easily from the graph. If H is not normal in Fn , this is not
necessarily true. Indeed, in Example
4.2, G is not normal and is of index 3

in F2 , so Cov(X̃/X) ≃ N (H) H = {1}, while its transition group is S3 (see
Example 3.2).
A question that arises naturally is whether the transition group T uniquely
determines the Schreier graph. The answer is negative, as the following
example illustrates it.
Example 4.4. Let G2 = ha3 , b2 , ab, babai with transition group S3 and the
following Schreier graph:

G2

b
a
b

a

G2 a

G2 a2

b

a
Figure 4.4.1: The Schreier graph of G2 = ha3 , b2 , ab, babai.
The two Schreier graphs X̃G and X̃G2 , considered as covering spaces of the
two-leaves bouquet, are not equivalent. Indeed, G and G2 are not
conjugate groups. Yet, the subgroups G and G2 are isomorphic, as they
are free groups of the same rank (with an isomorphism G → G2 given by
the following Nielsen automorphism of Fn : a 7→ ba, b 7→ a−1 b−1 a).
18

4.2

A combinatorial approach to coverings of the leaves
bouquet

We keep the same terminology as in Section 4.1: H ≤ Fn of finite index d
and X̃H its Schreier graph. We develop a combinatorial approach to X̃H
and prove some of its properties.
Lemma 4.5. Let H ≤ Fn of index d. Let T = {1, ti | 1 ≤ i ≤ d − 1} be a
transversal of H in Fn . Then, for every w ∈ Fn , there exists a minimal
natural number 1 ≤ mw,i ≤ d such that wmw,i ∈ t−1
i Hti .
Proof. If H ≤ Fn is of index d, then each conjugate subgroup is also of
index d, in particular t−1
i Hti , 1 ≤ i ≤ d − 1.
Lemma 4.6. Let H ≤ Fn of index d. Let X̃H be the Schreier graph of H
with vertices x̃0 , x̃1 , ..., x̃d−1 . Then, for every w ∈ Fn , there exists a
minimal natural number 1 ≤ mw,i ≤ d such that wmw,i is a loop at x̃i .
Proof. From Lemma 4.5, there exists a minimal natural number
mw,i is a loop at x̃ , since
1 ≤ mw,i ≤ d such that wmw,i ∈ t−1
i
i Hti . So, w
−1
m
m
w w,i ∈ ti Hti if and only if w w,i is a loop at x̃i (see Section 3.2).
In [29], the authors count the number of normal subgroups of F2 and they
define the order of an element in regular coverings. We extend the
definition of the order of an element to any covering.
Definition 4.7. Let H < Fn of index d. Let X̃H be the Schreier graph of
H with vertices x̃0 , x̃1 , ..., x̃d−1 . Let T = {1, ti | 1 ≤ i ≤ d − 1} be a
transversal of H in Fn , with ti the label of a minimal path from x̃0 to x̃i .
Let w ∈ Fn .
(i) The order of w at x̃i in X̃H is the minimal natural number
1 ≤ o(w, i) ≤ d such that wo(w,i) is a loop at x̃i , or equivalently such
that wo(w,i) ∈ t−1
i Hti .
(ii) The k-th w-step, 1 ≤ k ≤ o(w, i), is the k-th path labelled w in the
loop wo(w,i) at x̃i .
(iii) The set Vw,i is the set of vertices in X̃H visited at each w-step in the
loop wo(w,i) at x̃i .
(iv) The loops of w at x̃i and x̃j are disjoint if Vw,i ∩ Vw,j = ∅

19

Remark 4.8. When we compute the set Vw,i , we can assume that w is a
reduced word. Indeed, beginning at the vertex x̃i , we are only interested in
the vertex attained after each w-step and we do not insert the vertices
visited before a w-step is attained. Note that we cannot assume that w is
a cyclically reduced word (the following example illustrates it).
Example 4.9. Consider Examples 4.2 and 2.6. For w = aba−1 ,
o(aba−1 , 0) = 2, Vaba−1 ,0 = Vaba−1 ,2 = {x̃0 , x̃2 } and o(aba−1 , 1) = 1,
Vaba−1 ,1 = {x̃1 }, that is the loops at x̃0 and x̃1 are disjoint. If we reduce
cyclically aba−1 , we get b, with o(b, 0) = 1, Vb,0 = {x̃0 };
o(b, 1) = o(b, 2) = 2, Vb,1 = Vb,2 = {x̃1 , x̃2 }. If w = ab,
o(ab, 0) = o(ab, 1) = o(ab, 2) = 3, Va,0 = Va,1 = Va,2 = {x̃0 , x̃1 , x̃2 }.
Lemma 4.10. Let H < Fn of index d. Let NH denote the normal core of
H. Let X̃H be the Schreier graph of H with vertices x̃0 , x̃1 , ..., x̃d−1 . Let
w ∈ Fn with o(w, i) and Vw,i , 0 ≤ i ≤ d − 1, as in Definition 4.7. Then
(i) | Vw,i |= o(w, i).
(ii) Either Vw,i ∩ Vw,j = ∅, or Vw,i = Vw,j , 0 ≤ i, j ≤ d − 1.
(iii)

i=d−1
S

Vw,i = {x̃0 , .., x̃d−1 }.

i=0

(iv)

P

o(w, i) = d, where the sum is on disjoint loops.

(v) If for some integer k, wk is a loop at x̃i , then o(w, i) divides k.
(vi) If o(w, i) = d for some 0 ≤ i ≤ d − 1, then wd ∈ NH .
(vii) If wk ∈ NH for k ∈ Z, then ℓcm{o(w, i) | 0 ≤ i ≤ d − 1} divides k.
(viii) o(w, i) divides [Fn : NH ].
In particular, w ∈ NH if and only if o(w, i) = 1, for all 0 ≤ i ≤ d − 1.
Proof. (i) Clearly, | Vw,i |≤ o(w, i). If | Vw,i |< o(w, i), then the loop
crosses a vertex at least twice and there exists a loop wj at x̃i with
j < o(w, i), so this contradicts the minimality of o(w, i).
(ii) Assume by contradiction there exists x̃k ∈ Vw,i ∩ Vw,j , with
Vw,i 6= Vw,j . So, from (i), o(w, k) = o(w, i) = o(w, j), and there are two
different loops of the same length o(w, i) at x̃k . So, beginning at x̃k , there
exists a first j < o(w, i), such that at the j-th w-step in one loop the
20

vertex x̃k′ is attained and in the other loop a different vertex x̃k′′ is
attained. That is, the element wj acts in two different ways on the coset of
H represented by x̃k and this is a contradiction.
(iii), (iv) The sets Vw,i partition the finite set {x̃0 , .., x̃d−1 }.
(v) From the minimality of o(w, i), o(w, i) ≤ k. We divide k by o(w, i):
k = q(o(w, i)) + r, with residue 0 ≤ r < o(w, i). So, wr = wk−q(o(w,i)) is a
loop at x̃i . From the minimality of o(w, i), r = 0, that is o(w, i) divides k.
(vi) If o(w, i) = d, then wd is a loop at all the d vertices. So, wd belongs to
all the conjugates of H, that is wd ∈ NH .
(vii), (viii) If wk ∈ NH , then from (v), o(w, i) divides k for every
0 ≤ i ≤ d − 1, that is ℓcm{o(w, i) | 0 ≤ i ≤ d − 1} divides k. As NH ⊳ Fn , k
divides [Fn : NH ] and so o(w, i) divides [Fn : NH ], for all 0 ≤ i ≤ d − 1.
Note that from Lemma 4.10(v), it results that for every integer q dividing
o(w,i)

o(w, i), there exists an element g ∈ Fn with o(g, i) = q (take g = w q ).
We now consider the case of a normal subgroup, with a regular covering.
Lemma 4.11. Let N ⊳ Fn of index m. Let X̃N be the Schreier graph of N
with vertices x̃0 , x̃1 , ..., x̃m−1 . Let T = {1, ti | 1 ≤ i ≤ m − 1} be a
transversal of N in Fn , with ti the label of a minimal path from x̃0 to x̃i .
Let w ∈ Fn with o(w, i) and Vw,i , 0 ≤ i ≤ m − 1, as in Definition 4.7. Then
(i) o(w, i) = o(w, j) = o(w), for all 0 ≤ i, j ≤ m − 1.
(ii) o(w) divides m.
(iii) There are exactly

m
o(w)

disjoint loops labelled wo(w) in X̃N .

Proof. (i) We recall that o(w, i) is the minimal natural number such that
−1
wo(w,i) ∈ t−1
i N ti . Since N ⊳ Fn , g N g = N for every g ∈ Fn . So, for all
0 ≤ i, j ≤ d − 1, o(w, i) = o(w, j) = o(w).
(ii) results from Lemma 4.10(iv) and (iii) from Lemma 4.10(iii).
We introduce a graph derived from the Schreier graph that describes the
w-steps, where w is a word in Fn .
Definition 4.12. Let w ∈ Fn . Let H < Fn of index d. Let X̃H be the
Schreier graph of H. We define X̃H (w) to be the Schreier graph of H, but
instead of being labelled by the generators of Fn , only the w-steps are
specified. We also call X̃H (w) the Schreier graph of H.
Example 4.13. Consider the subgroup G of index 3 in F2 from Example
4.2. Let w = ab. Then, X̃G (ab) is the following connected graph:
21

w

G

Ga

w

Gab

w

Figure 4.13.1: The graph X̃G (ab) for G = hb, a2 , ab2 a, (ab)2 ai.
Let w = a. The graph X̃G (a) is the following disconnected graph:
a

G

Ga

Gab

a

a
Figure 4.13.2: The graph X̃G (a) for G = hb, a2 , ab2 a, (ab)2 ai.
Note that the situation described in Figure 4.13.2 can never occur if the
subgroup is normal. Indeed, from Lemma 4.11, if N ⊳ Fn of index m, for
any w ∈ Fn the graph X̃N (w) is very regular: o(w) is the same at each
m
disjoint loops labelled wo(w) .
vertex and there are exactly o(w)

4.3

What happens when we look at a tower of covering
spaces?

Let H < Fn of index d. Let X̃H be the Schreier graph of H. Let N ⊳ Fn of
index m such that N ⊂ H. Such a subgroup always exists, since H has
non-trivial intersection with every non-trivial subgroup of Fn . Let X̃N be
the Schreier graph of N . The subgroup H is a free group of rank
d(n − 1) + 1, so it is the fundamental group of XH , the bouquet of
d(n − 1) + 1 circles. As N < H, there exists a regular covering X̂N over
XH , the Schreier coset diagram for H relative to the subgroup N . We
refer to Example 2.11 (see Figure 2.11.2) for an illustration and in the
following lemma we list some basic properties of the covering X̂N over XH
derived directly from Theorem 2.5.
Lemma 4.14. Let H < Fn of index d be the fundamental group of XH ,
the bouquet of d(n − 1) + 1 circles. Let N ⊳ Fn be a subgroup of index m
such that N ⊂ H. Let X̂N the regular covering over XH . Then
22

(i) The covering X̂N over XH is a

m
d -sheeted

(ii) The m
d vertices in X̂N represent the
disjoint union is H.

m
d

covering.

right cosets of N whose

We now introduce a graph that combines in some sense the Schreier graphs
of N and H, and gives a more complete picture.
Definition 4.15. Let w ∈ Fn . Let H < Fn of index d and let N ⊳ Fn of
index m such that N ⊂ H. Let X̃H be the Schreier graph of H with
vertices x̃0 , x̃1 , ..., x̃d−1 . Let T = {1, ti | 1 ≤ i ≤ d − 1} be a transversal of
H in Fn , with ti the label of a minimal path from x̃0 to x̃i . Let X̃H (w),
X̃N (w) as in Definition 4.12. We define the combined graph of N and H,
denoted by X̃N,H (w), to be the following two-levelled graph:
At the top layer, denoted Top: X̃N (w)
At the bottom layer, denoted Bot: X̃H (w)
The relative position of the vertices in Top and Bot is:
For each vertex x̃i representing Hti in Bot, there is above it a set of m
d
vertices N y1 ,..,N y md such that Hti is the disjoint union of N y1 ,..,N y md .
We call the set {N y1 , .., N y md } the fiber over Hti and denote it by
p−1
w (Hti ).
As N ⊂ H, the action of Fn on the right cosets of H induces an action of
Fn on the right cosets of N . That is, for each loop in Bot, there is at least
one loop induced in Top. Indeed, consider the loop labelled wo(w,i) at x̃i in
Bot and let Vw,i be the set of vertices visited at each w-step in this loop.
Then, if we denote by p−1
w (Vw,i ) the set of fibers in Top over the set of
visited vertices, then there are some loops connecting the fibers in
p−1
w (Vw,i ). We will study these loops in more detail in the following
lemmas.
Example 4.16. Let K < F2 of index 4 from Example 2.11. Let N ⊳ F2 be
of index 8 in F2 such that NK = N with Schreier graph X̃N :

23

b

N

Na
a

b

a

b

a

N ab

N aba

a

b

a

b
N bab

N(ab)2

N ba

a

b

a

b

Nb
a

b

Figure 4.16.1: The Schreier graph X̃N with N = NK .

N

Nb

w

w

N ab

N bab

w

w
w

N(ab)2

N aba

w

w

N ba

Na

w

⇓⇓

K

w

Kab

w

Kaba

w

Ka

w

Figure 4.16.2: The combined graph X̃N,K (w): Top:X̃N (w), and
Bot:X̃K (w), with w = ab.
The arrows delimit between Top and Bot. In Bot, there is one loop of
length 4, labelled w4 , since oK (w) = 4. In Top, there are 2 disjoint loops of
length 4, labelled w4 . The fiber of K is the set p−1
w (K) = {N, N b}, with all
−1
its elements just above K, the fiber of Kab is pw (Kab) = {N ab, N bab}
with all its elements just above Kab and so on. Consider H < F2 of index
2 from Figure 2.9.1. Then N < H and X̃N,H (ab) is:

24

w

N

Nab

w
w

w

N(ab)2

Nba

w

Nb

Nbab

w
w

w

Naba

Na

⇓⇓
w

H

Ha
w

Figure 4.16.3: The combined graph X̃N,H (w): Top: X̃N (w), and Bot:
X̃H (w), with w = ab.
In Bot, there is one loop of length 2, labelled w2 , since oH (w) = 2. In Top,
there are 2 disjoint loops of length 4, labelled w4 . The fiber of H is the set
2
p−1
w (H) = {N, N (ab) , N b, N aba}, with all its elements just above H and
the fiber of Ha is the set of elements just above Ha:
p−1
w (Ha) = {N ab, N ba, N bab, N a}. In each loop, each fiber contributes
exactly 2 elements. These are exactly the same loops as in Figure ??, but
their distribution into the fibers are different.
25

In the following lemmas, we describe the connection between the top layer
and the bottom layer in the combined graph. The next lemma describes
some basic properties of the combined graph that are derived directly from
its definition and the properties of the graphs X̃H (w) and X̃N (w) (see
Section 4.2).
Lemma 4.17. Let w ∈ Fn . Let H < Fn of index d and N ⊳ Fn of index m
such that N ⊂ H. Let X̃N,H (w) be their combined graph. Then
(i) In Bot, there are d vertices.
(ii) In Top, there are d fibers each of size

m
d.

(iii) In Top, the fiber over Hx is the set of
disjoint union is Hx.

m
d

(iv) In Top, there are exactly

m
oN (w)

right cosets of N whose

disjoint loops labelled woN (w) .

The following lemma is very important for the rest of the paper, as here
we describe entirely the induced loops in Top.
Lemma 4.18. Let w ∈ Fn . Let H < Fn of index d and N ⊳ Fn of index m
such that N ⊂ H. Let X̃N,H (w) be their combined graph, with
x̃0 , x̃1 , ..., x̃d−1 the vertices in Bot. Let o(w, j) be the order of w at a
chosen vertex x̃j in Bot and let Vw,j be the set of vertices visited at each
w-step in this loop. Let p−1
w (Vw,j ) be the set of fibers over Vw,j in Top.
Then
(i) | p−1
w (Vw,j ) |=| Vw,j |= o(w, j).
(ii) The loop in Bot labelled wo(w,j) between the vertices in Vw,j induces
m
d
oN (w)
o(w,j)

loops labelled woN (w) between the o(w, j) fibers in p−1 (Vw,j ) in

Top.
(iii) Each fiber in p−1
w (Vw,j ) contributes exactly
induced loop labelled

oN (w)
o(w,j)

elements in an

woN (w) .

Proof. (i) As N ⊂ H, the action of Fn on the right cosets of H induces an
action of Fn on the corresponding right cosets of N .
(ii), (iii) To simplify the notation, let k = o(w, j), let ℓ denote the loop in
Bot labelled wk at x̃j . Assume x̃j represents the right coset Hx and
p−1
}. Each w-step in Bot between two vertices
w (Hx) = {N y1 , N y2 , ..., N y m
d
Hx and Hxw induces a w-step in Top between N yi and N yi w, for every
26

1≤i≤ m
d . So, ℓ induces
N yi → N yi w → N yi w2 → ... → N yi wk−1 → N yi wk → N yi wk+1 .... From
Definition 4.7(i), k is the minimal natural number such that wk ∈ x−1 Hx
k+1 ∈ p−1 (Hxw)
or equivalently Hxwk = Hx. So, N yi wk ∈ p−1
w (Hx), N yi w
w
and so on.
If k = oN (w), then N yi wk = N yi , for all 1 ≤ i ≤ m
d and each fiber in
oN (w)
oN (w)
−1
p (Vw,j ) contributes exactly o(w,j) = k = 1 element in a loop labelled
woN (w) . Since there are
wk

induces

m
d
oN (w)
k

=

m
d

m
d

elements in each fiber, the loop in Bot labelled

loops labelled woN (w) between the o(w, j) fibers in

p−1 (Vw,j ).
Assume now that oNk(w) = p > 1. Then N yi wk ∈ p−1
w (Hx), but
N yi wk 6= N yi and N yi wpk = N yi . In fact, N yi wk = N yi1 ,
N yi w2k = N yi2 ,..., N yi w(p−1)k = N yip−1 for different i1 , i2 , ..., ip−1 between
1 and m
d . So, ℓ induces a loop of length oN (w) between the k fibers of the
form:
N yi
→
N yi w
→
N yi w 2
→ ... N yi wk−1 →
N yi w k
→
N yi wk+1
→
N yi wk+2
→ ... N yi w2k−1 →
...
...
...
...
...
...
(p−1)k
(p−1)k+1
(p−1)k+2
N yi w
→ N yi w
→ N yi w
→
N yi wkp−1
oN (w)
In such a loop, each fiber contributes exactly k = p elements. Since
there are

m
d

elements in each fiber, ℓ induces

between the o(w, j) fibers in p−1 (Vw,j ).

m
d
oN (w)
k

loops labelled woN (w)

Example 4.19. Let G from Examples 2.6, 4.2, N = NG with X̃N :
b
b

a

N

Na
a

a
N ab

b

Nb

N ba

Naba

a

a

b

b

a

b

Let w = b, with oN (w) = 2. Then X̃N,G (w) is the following:

27

w

N

Na

N ab

w
w

w

w

Nb

N ba

Naba

w

⇓⇓

w

G

Ga

w

Gab

w

Figure 4.19.1: The combined graph X̃NG ,G (w), w = b.
−1
We describe X̃N,G (w): p−1
w (G) = {N, N b}, pw (Gab) = {N ab, N aba},
−1
pw (Ga) = {N ba, N a}, each of size 2. In Top, there are 3 loops of length 2.
For the fiber p−1
w (G) = {N, N b}, the loop stays inside the fiber since
o(b) = 1 at the corresponding vertex in Bot and this fiber contributes
2
1 = 2 elements in the loop. For the other 2 loops, there are two
−1
participating fibers, p−1
w (Gab) and pw (Ga), and each fiber contributes 1
element in each loop:

Remark 4.20. As Examples 4.19 and 4.16 illustrate it, given N ⊳ Fn of
index m and w ∈ Fn , the number of loops and the length of the loops in
Top of any combined graph X̃N,H (w) are independent of the subgroup H.
Indeed, oN (w) is determined by X̃N and the loops correspond to the
action of w on the cosets of N , or more generally if w = a, b they describe
the action of Fn on the cosets of N . Yet, changing H changes the fibers,
(w)
the size of the fibers (= dmH ) and the number of elements (= ooN
)
H (w)
contributed by each fiber in a loop of length oN (w).

28

5

The HS conjecture and covering spaces

Let Fn be the free group on n generators. Let {Hi αi }i=s
i=1 be a coset
partition of Fn with Hi < Fn of index di , αi ∈ Fn , 1 ≤ i ≤ s. Let
i=s
T −1
T
g Hi g, the normal core of Hi of index mi . Let N =
Ni =
Ni of
i=1

g∈Fn

index m, N is the intersection of the normal cores of all the subgroups
H1 ,..,Hs . For every 1 ≤ i ≤ s, and for any w ∈ Fn , there exists a combined
graph X̃N,Hi (w), since N ⊳ Fn and N ⊂ Hi . At Top of every combined
graph X̃N,Hi (w), there are oNm(w) loops of length oN (w) labelled woN (w) .
Yet, for each i, Top of X̃N,Hi (w) looks different, since the fibers and the
connections between them are different and they depend on the subgroup
Hi (see Section 4.3). Our aim in the following section is to describe
graphically the HS conjecture in terms of the combined graphs X̃N,Hi (w),
for any w ∈ Fn . In particular, we introduce a new graph, the HS-colored
graph, that describes the partition and is a conjunction of the s combined
graphs.

5.1

A graphical description of a coset partition of Fn with
the Schreier graphs

Let w ∈ Fn , with order oN (w). Let X̃N (w) be the Schreier graph of N .
Let X̃N,i (w) denote the s combined graphs X̃N,Hi (w), 1 ≤ i ≤ s. Let
denote by p−1
w (Hi αi ) the fiber over Hi αi in Top of the combined graph
X̃N,i (w). In each X̃N,i (w), 1 ≤ i ≤ s, let color in color ci the vertex
representing the coset Hi αi at Bot, and all the elements in the fiber
p−1
w (Hi αi ) in Top. We keep record of the color attributed to each coset of
N , and color accordingly the vertices (i.e the cosets of N ) in X̃N (w).
Definition 5.1. Let {Hi αi }i=s
i=1 be a coset partition of Fn with Hi < Fn of
i=s
T T −1
index di , αi ∈ Fn , 1 ≤ i ≤ s. Let N =
g Hi g of index m, with
i=1 g∈Fn

Schreier graph X̃N (w), w ∈ Fn . Let X̃N,i (w) denote the s combined graphs
X̃N,Hi (w), 1 ≤ i ≤ s.
(i) We define X̄N (w), the HS-colored graph, to be X̃N (w) with colored
vertices: a vertex is colored in color ci if and only if it belongs to
p−1
w (Hi αi ) in Top of X̃N,i (w), 1 ≤ i ≤ s.
(ii) We define the order of w relative to Hi αi , o∗i (w), to be the order of
w in Bot of X̃N,i (w) relative to the vertex Hi αi , that is the minimal
29

o∗i (w)
natural number such that wo∗i (w) ∈ α−1
i Hi αi , or equivalently w
is a loop at the vertex Hi αi in Bot of X̃N,i (w).
−1
Since {Hi αi }i=s
i=1 is a coset partition of Fn and each fiber pw (Hi αi )
m
contains exactly di cosets of N , we have that all the vertices in X̄N (w) are
colored in one and only one color, and:

Lemma 5.2. m =

i=s
P

i=1

m
di .

ExampleS 5.3. S
Consider the following simple partition of F2 :
F2 = H1 H2 a H3 ab, where H1 = H and H2 = H3 = K as described in
Examples 2.9 and 2.11. Let N ⊳ F2 of index 8 from Example 4.16, N is
the intersection of the normal cores of H1 ,H2 and H3 . Let w = ab with
oN (w) = 4. So, from Lemma 4.17, there are oNm(w) = 2 disjoint loops
labelled woN (w) . The combined graphs X̃N,H (w) and X̃N,K (w) are
described in Figures 4.16.3 and 4.16.2 respectively. For w = ab, o∗1 (w) = 2,
o∗2 (w) = o∗3 (w) = 4. The HS-colored graph X̄N (w) is described below:

w

N

w

Nab

w

w

N(ab)2

Nba

w
Nb

w

Nbab

w

Naba

w

Na

Figure 5.3.1: The HS-colored graph X̄N (ab), with N ⊳ F2 of index 8.
30

2
The vertices in p−1
w (H1 ) = {N, N (ab) , N b, N aba} are colored in red
−1
(circles), those in pw (H2 a) = {N ba, N a} in green (stars) and those in
p−1
w (H3 ab) = {N ab, N bab} in blue (squares). From Lemma 4.18, the fiber

p−1
w (H1 ) participates in
oN (w)
o∗1 (w)
m
d2
oN (w)
o∗2 (w)

m
d1
oN (w)
o∗1 (w)

= 2 loops and in each loop it contributes

= 2 elements (cosets of N ), the fiber p−1
w (H2 a) participates in
= 2 loops and in each loop it contributes

oN (w)
o∗2 (w)

= 1 coset of N and

the same holds for the fiber p−1
w (H3 ab).
Before we go on with Fn with n > 1, we give a graphical description of a
coset partition in the special case F1 = Z.

5.2

A graphical description of a coset partition of Z

The group of integers Z = h1i is the fundamental group of the bouquet X
with only one circle labelled 1. For each subgroup H = oZ of index o > 1,
there exists a o-fold covering X̃H , which is also a Schreier coset diagram
for Z relative to oZ. It is an oriented loop of length o > 1 and labelled o:
1

1

H

H +1

1
H +2

H +3

1

↓p

x0

1

Figure 5.3.2: The 4-fold covering (X̃H , p) for H = 4Z
Let {oi Z + ri }i=t
i=1 , ri ∈ Z, be a coset partition of Z. Let fix w = 1, so that
oi (1) = oi , for all 1 ≤ i ≤ t, at any vertex. Let N = oN Z, with oN divisible
i=t
T
by ℓcm(o1 , ..., ot ), so N ⊆
oi Z and oN (1) = oN . Let X̃N be the Schreier
i=1

graph of oN Z. Note that for w = 1, the Schreier graphs X̃H and X̃H (1)
31

coincide, for any H < Z. Let X̃N,i (w) be the combined graph of N and Hi :
in Bot, there is a loop of length oi and in Top there is a unique loop of
length oN , such that above each vertex of Bot there is a fiber of size ooNi in
Top. From Lemma 4.18, each fiber contributes all its

oN (1)
oN
oi (= oi (1) )

elements

in this loop. In each X̃N,i (1), 1 ≤ i ≤ t, we color in color ci the vertex
representing the coset oi Z + ri in Bot, and all the elements in the fiber
p−1 (oi Z + ri ) in Top. So, keeping record of the color attributed to each
coset of N , and coloring accordingly the vertices (i.e the cosets of N ) in
X̃N , all the vertices in the unique loop of length oN in X̃N are colored in
one and only one color. Note that for w = 1 in Z, the HS-colored graph
defined in the previous section is the same as X̃N with colored vertices.
Since each fiber contributes ooNi elements in a loop and all the t fibers
P
oN
participate in this unique loop, we have i=t
i=1 oi = oN . And conversely,
Lemma 5.4. Let ci , 1 ≤ i ≤ t, be different colors. Let oN , oi > 1,
1 ≤ i ≤ t, be natural numbers P
such that ℓcm(o1 , ..., ot ) divides oN . If there
oN
oN
exists a loop ℓ of length oN = i=t
i=1 oi , with each package of oi vertices
colored in ci , 1 ≤ i ≤ t and such that any two consecutive vertices colored
in the same color ci are at oi distance. Then there exist ri ∈ Z, 1 ≤ i ≤ t,
i=t is a coset partition of Z.
such that {oi Z + ri }i=1
Proof. We set N = oN Z and Hi = oi Z, 1 ≤ i ≤ t. Since ℓcm(o1 , ..., ot )
i=t
T
divides oN , N ⊆
Hi . We show that a loop ℓ satisfying the conditions of
i=1

the lemma describes the Schreier graph of N and a coset partition
i=t . Choose any vertex in ℓ and call it N and the adjacent
{oi Z + ri }i=1
vertex N + 1 and so on until N + oN − 1. If in ℓ, any two consecutive
vertices colored in the same color ci are at oi distance, then there exist
ri ∈ Z, 1 ≤ i ≤ t, such that the vertices colored ci are N + ri , N + ri + oi ,
N + ri + 2oi ,...,N + ri + ( ooNi − 1)oi , that is these are ooNi cosets of N whose
union is oi Z + ri . Next, since each vertex in ℓ is colored inP
only one color,
oN
the sets oi Z + ri , 1 ≤ i ≤ t, are all disjoint. At last, oN = i=t
i=1 oi implies
that Z is partitioned by these disjoint cosets.
Theorem 5.5. [30, Theorem 2][31, Theorems 4,5]
Let {oi Z + ri }i=t
i=1 be a coset partition of Z. Then:
(i) The natural numbers {oi | 1 ≤ i ≤ t} are not pairwise prime.
(ii) omax = M ax{oi | 1 ≤ i ≤ t} appears at least p times, where p is the
smallest prime dividing omax .
32

(iii) Any ol divides another ok , where 1 ≤ k 6= l ≤ t.
(iv) Any ok that does not properly divide any other oi appears at least
twice, 1 ≤ k, i ≤ t.

6

Main results on the Herzog-Schönheim
conjecture for free groups of finite rank

In this section, we give some conditions that ensure a partition of the free
group of finite rank has multiplicity. The notation is the following for the
rest of this section. Let Fn be the free group on n ≥ 2 generators. Let
{Hi αi }i=s
n of index di > 1,
i=1 be a coset partition of Fn with Hi < FT
g−1 Hi g of index mi .
αi ∈ Fn , 1 ≤ i ≤ s, and d1 ≤ ... ≤ ds . Let Ni =
g∈Fn

Let N =

i=s
T

Ni of index m. Let w ∈ Fn . Let X̃i (w) denote the Schreier

i=1

graph X̃Hi (w), 1 ≤ i ≤ s and X̃N (w) be the Schreier graph of N . Let
X̃N,i (w) denote the combined graph X̃N,Hi (w), 1 ≤ i ≤ s. Let denote by
p−1
w (Hi αi ) the fiber over Hi αi in Top of the combined graph X̃N,i (w). Let
X̄N (w) be the HS-colored graph. Let o∗i (w), 1 ≤ i ≤ s, be the order of w
relative to the vertex Hi αi .

6.1

Description of the loops in the HS-colored graph

In Top of any combined graph, there are the same

m
oN (w)

disjoint loops of

length oN (w) from X̃N (w). But, for different subgroups Hi and Hj , the
fibers in Top of X̃N,i (w) and X̃N,j (w) are different and so Top of X̃N,i (w)
and X̃N,j (w) look also different. The HS-colored graph X̄N (w) describes
i=s , with each fiber p−1 (H α ) colored in a different
the partition {Hi αi }i=1
i i
w
color (see Figures 4.16.2, 4.16.3 and 5.3.1). The question now is how the
colored fibers are connected in X̄N (w). In the following lemmas, we aim to
answer this question and describe the loops in X̄N (w).
i=s
T −1
Note that w ∈
αi Hi αi if and only if o∗i (w) = 1 for every 1 ≤ i ≤ s, so
i=1

if w ∈ Fn \

i=s
T

i=1

α−1
i Hi αi , then there exists 1 ≤ i1 ≤ s such that o∗i1 (w) > 1.

Lemma 6.1. Let w ∈ Fn \

i=s
T

i=1

α−1
i Hi αi , with order oN (w). Then in

X̄N (w), the HS-colored graph, the following occurs:
33

(i) There are

m
oN (w)

disjoint loops of length oN (w) (labelled woN (w) ).

oN (w)
(ii) If the fiber p−1
w (Hi αi ) participates in a loop, then it contributes o∗i (w)
elements and the distance between two consecutive vertices is o∗i (w).

(iii) Each fiber p−1
w (Hi αi ) participates in

m
di
oN (w)
o∗i (w)

(iv) A fiber p−1
w (Hi αi ) participates in all the
o∗i (w) = di .

loops.

m
oN (w)

loops if and only if

−1
(v) Two fibers p−1
w (Hi αi ) and pw (Hj αj ) participate in the same number
o (w)
of loops if and only if o∗id(w)
= ∗jdj .
i

(vi) For each j-th loop, 1 ≤ j ≤

m
oN (w) ,

the following equation holds:

X oN (w)
= oN (w)
o∗i (w)

(6.1)

i∈Yj

where Yj = {1 ≤ i ≤ s | p−1 (Hi αi ) participates in the j-th loop }.
Proof. (i), (ii), (iii) result from Lemma 4.18, since from the definition of
the HS-colored graph, X̄N (w) is just X̃N (w) with colored vertices.
(iv) results from (iii):
(v) results from (iii):

m
di
oN (w)
o∗i (w)
m
di
oN (w)
o∗i (w)

=
=

m
oN (w)
m
dj
oN (w)
o∗j (w)

(vi) Consider a j-th loop, 1 ≤ j ≤

if and only if o∗i (w) = di .
if and only if

m
oN (w) .

o∗i (w)
di

o∗j (w)
dj .

If the fiber p−1 (Hi0 αi0 )

participates in this loop, then from (iii) it contributes
oN (w)
o∗i0 (w)

=

oN (w)
o∗i0 (w)

elements. If

= oN (w), that is o∗i0 (w) = 1, then Equation 6.1 holds trivially for

this loop. Since w ∈
/

i=s
T

i=1

α−1
i Hi αi , there is some 1 ≤ i1 ≤ s such that

o∗i1 (w) > 1 and there are loops with more than one participating fiber.
Assume the fiber p−1
w (Hi1 αi1 ) participates in such a loop, then from (iii) it
oN (w)
contributes o∗i (w) elements colored in ci1 . Next, another fiber,
1

oN (w)
o∗i2 (w) elements colored in ci2
oN (w)
(completely disjoint with the former). If oo∗iN (w)
(w) + o∗i2 (w) = oN (w),
1
oN (w)
Equation 6.1 holds for this loop. Otherwise, if oo∗iN (w)
(w) + o∗i2 (w) < oN (w),
1

p−1
w (Hi2 αi2 ), participates and contributes

34

oN (w)
then there is a fiber, p−1
w (Hi3 αi3 ), that participates and contributes o∗i (w)
3
elements colored in ci3 . We repeat the process until all the oN (w) vertices
in this loop are counted and Equation 6.1 holds for this loop. Since the
m
oN (w) loops are disjoint, we do the process for each loop independently.

Proposition 6.2. Let w ∈ Fn \

i=s
T

i=1

α−1
i Hi αi , with order oN (w). For each

j-th loop, 1 ≤ j ≤ oNm(w) , let Yj = {1 ≤ i ≤ s | p−1 (Hi αi ) participates in the
j-th loop}. Then, in X̄N (w), the following occurs:
(i) The natural numbers {o∗i (w) | i ∈ Yj } are not pairwise prime.
(ii) omax,j = M ax{o∗i (w) | i ∈ Yj } appears at least p times, where p is the
smallest prime dividing omax,j .
(iii) Any o∗l (w) divides another o∗k (w), for k, l ∈ Yj .
(iv) Any o∗k (w) that does not properly divide any other o∗i (w) appears at
least twice, for i, k ∈ Yj .
Proof. We consider only loops with more than one participating fiber.
From Lemma 6.1, any j-th loop is of length oN (w) and satisfies the
P oN (w)
oN (w)
following three conditions: oN (w) =
o∗i (w) , each package of o∗i (w)
i∈Yj

vertices are colored in color ci , i ∈ Yj , and any two consecutive vertices
colored in the same color ci are at o∗i (w) distance. So, from Lemma 5.4,
each such loop describes a coset partition of Z, {o∗i (w)Z + ri }i∈Yj ri ∈ Z.
(i), (ii), (iii), (iv) result then from the HS in Z and are a transcription of
(i), (ii), (iii), (iv) from Theorem 5.5 for a j-th loop.

6.2

Main Results on the Herzog-Schönheim conjecture for
free groups of finite rank

We prove the first Theorems that provide sufficient conditions for
multiplicity in the coset partition of Fn .
Theorem 6.3. Let Fn be the free group on n ≥ 2 generators. Let
{Hi αi }i=s
i=1 be a coset partition of Fn with Hi < Fn of index di , αi ∈ Fn ,
1 ≤ i ≤ s, and 1 < d1 ≤ ... ≤ ds . Let X̃i denote the Schreier graph of Hi ,
1 ≤ i ≤ s. For g ∈ Fn , let o∗i (g) denote the order of g relative to Hi αi ,
1 ≤ i ≤ s. If there exists w ∈ Fn such that o∗s (w) = ds , then the index ds
appears in the partition at least p times, where p is the smallest prime
dividing ds .
35

Proof. If there exists w ∈ Fn such that o∗s (w) = ds , then
omax (w) = M ax{o∗i (w) | 1 ≤ i ≤ s} = ds . Furthermore, from Lemma
6.1(iv), the fiber p−1
w (Hs αs ) participates in all the loops. Consider any j-th
loop. From Proposition 6.2, omax (w) appears at least p times in this loop,
where p is the smallest prime dividing omax (w). That is, there are at least
1 ≤ i1 , .., ip−1 ≤ s − 1 such that o∗i1 (w) = ... = o∗ip−1 (w) = omax = ds . But,
o∗i (w) ≤ di , so di1 = ... = dip−1 = ds .
Note that if there exists w ∈ Fn , such that o∗i (w) = di for every 1 ≤ i ≤ s,
then multiplicities occur as in Z. In particular, it ensures the existence of a
partition of Z with subgroups of indices d1 , ..., ds . For the partition of F2
in Example 5.3, o∗1 (ab) = d1 = 2, o∗2 (ab) = d2 = o∗3 (ab) = d3 = 4. If
Hs ⊳ Fn , then there exists a ds -cycle in Ts if and only if Ts ≃ Zds .
Example 6.4. Consider the partition of F2 given in Example 5.3. The
subgroup of maximal index is K with index 4 (see Figure 2.11.1). For
w = ab, oK (ab) = 4 in X̃K (see Figure 4.16.2), so Theorem 6.3(i) ensures
the HS is satisfied and in this example the index 4 appears exactly twice.
We keep the same notation as in Theorem 6.3. For g ∈ Fn , let
omax (g) = M ax{o∗i (g) | 1 ≤ i ≤ s}, and p be the smallest prime dividing
omax (g). We define # =| {1 ≤ i ≤ s | o∗i (g) = omax (g)} |.
Theorem 6.5. Let Fn be the free group on n ≥ 2 generators. Let
{Hi αi }i=s
i=1 be a coset partition of Fn with Hi < Fn of index di , αi ∈ Fn ,
1 ≤ i ≤ s, and 1 < d1 ≤ ... ≤ ds . Let r ∈ Z, 4 ≤ r ≤ s − 1. If there exists
w ∈ Fn that satisfies one of the following conditions:
(i) omax (w) > ds−2 .
(ii) omax (w) > ds−3 , p ≥ 3.
(iii) omax (w) > ds−3 , p = 2, and # ≥ 4.
(iv) omax (w) > ds−3 , p = 2, and # = 2
(v) omax (w) > ds−r , p ≥ r.
(vi) omax (w) > ds−r , # ≥ r + 1.
(vii) omax (w) > ds−r , # = p.
i=s has multiplicity.
Then the coset partition {Hi αi }i=1

36

Proof. (i) Let kw denote omax (w). If there exists w ∈ Fn with kw > ds−2 ,
then either o∗s (w) = kw or o∗s−1 (w) = kw . From Proposition 6.2, omax (w)
appears at least twice, so o∗s (w) = o∗s−1 (w) = kw . If kw occurs exactly
−1
twice, then the fibers p−1
w (Hs αs ) and pw (Hs−1 αs−1 ) participate together
in the same loops (otherwise there would be a repetition of kw for an
(w)
additional fiber). So, from Lemma 6.1(v), o∗sd(w)
= o∗s−1
implies
ds−1
s
ds−1 = ds . If kw occurs three times or more, then there is at least one
additional fiber p−1
w (Hi αi ), with o∗i (w) = kw > ds−2 and
o∗i (w) ≤ di ≤ ds−2 . So, the pigeonhole principle can be applied: there are
two values of indices ds and ds−1 to distribute to at least three fibers, that
is di = ds or di = ds−1 , and there is a repetition of one of the indices.
(ii), (iii), (v), (vi) The proof relies on the pigeonhole principle as it was
applied in the proof of (i).
(iv), (vii) Whenever # = p, there are p fibers that participate together in
the same loops. So, Lemma 6.1(v) implies they have the same index.
Theorem 1 and Theorem 2 from the introduction are computationally
speaking far easier to check than Theorems 6.3 and 6.5. We show that in
fact Theorems 1 and 2 are equivalent to Theorems 6.3 and 6.5 respectively.
For that, we need the following lemma. In the following, we assume the
permutations are decomposed into the product of disjoint cycles.
Lemma 6.6. Let H < Fn be of finite index d. Let X̃H be the Schreier
graph of H with vertices x̃0 , ..., x̃d−1 . Let T ≤ Sd be the transition group of
X̃H . Then
(i) There exists a d-cycle in T , if and only if there exists w ∈ Fn such
that o(w, j) = d, for some 0 ≤ j ≤ d − 1.
(ii) If there exists a permutation in T with a k-cycle at some x̃j , then for
every x̃r , there exists a permutation in T with a k-cycle at x̃r .
Proof. (i) Let w ∈ Fn . Assume o(w, j) = d, for some 0 ≤ j ≤ d − 1. Then,
from Lemma 4.10(i), o(w, j) = d, for all 0 ≤ j ≤ d − 1, that
is wd ∈ NH ,

where NH is the normal core of H. So, o(NH w) = d in Fn N ≃ T with
H
T ≤ Sd and w acts as a d-cycle on the right cosets of H. Conversely,
assume there is a d-cycle φ in T . Let w ∈ Fn be any inverse image of φ.
Then o(w, j) = d, for all 0 ≤ j ≤ d − 1.
(ii) Assume first that σ ∈ T is a permutation with a k-cycle at x̃0 . Let
g ∈ Fn be any inverse image of σ. Then there is a loop labelled gk at x̃0 .
Let w = t−1
r gtr , with tr the label of a minimal path from x̃0 to x̃r . Then
37

there is a loop labelled wk at x̃r and in the corresponding permutation in
T there is a k-cycle. The same proof applies for any x̃j .
Proofs of Theorem 1 and Theorem 2 . Using Lemma 6.6(i), Theorem 1
and Theorem 2 from the introduction are the transcription in terms of
cycles of Theorems 6.3 and 6.5 respectively.
In the following Theorem, we give a condition that ensures there is a
subgroup that appears at least twice in the partition.
Theorem 6.7. Let {Hi αi }i=s
i=1 be a coset partition of Fn with Hi < Fn of
index di > 1, αi ∈ Fn , 1 ≤ i ≤ s. If one of the following conditions holds:
(i) There exist 1 ≤ j, k ≤ s such that

i=s
T

i=1

α−1
i Hi αi (

T

i6=j,k

α−1
i Hi αi .

(ii) There exist 1T≤ j, k ≤ s such that ℓcm(dj , dk ) does not divide the
α−1
index [Fn :
i Hi αi ].
i6=j,k

(iii) There exist 1 ≤ j, k ≤ s such that ℓcm(dj , dk ) >

Q

di .

i6=j,k

Then {Hi αi }i=s
i=1 has multiplicity. Furthermore, Hj = Hk .
Proof. (i) Let w ∈

T

i6=j,k

α−1
/
i Hi αi and w ∈

i=s
T

i=1

α−1
i Hi αi , with order oN (w).

Then, o∗i (w) = 1, for all i 6= j, k, and o∗j (w) > 1, o∗k (w) > 1. We have the
following situation in X̄N (w). For every i 6= j, k, all the loops of length
oN (w) stay inside the fibers p−1
w (Hi αi ) and o∗j (w), o∗k (w) > 1 imply
necessarily o∗j (w) = o∗k (w) = 2. That is, the fibers p−1
w (Hj αj ) and
−1
pw (Hk αk ) participate in the same loops, so Lemma 6.1(v) implies dj = dk .
Furthermore, Hk αk = (Hj αj )w. So, αk ∈ Hj αj w, that is Hj αk = Hj αj w.
So, Hj αk = Hk αk , that is Hj = Hk .
(ii) If there exist 1 ≤ j, k ≤ s such that ℓcm(dj , dk ) does not divide
i=s
T −1
T −1
T −1
αi Hi αi and (i) applies.
αi Hi αi ], then
αi Hi αi (
[Fn :
i6=j,k

i6=j,k

i=1

Q
(iii) If there exist 1 ≤ j, k ≤ s such that ℓcm(dj , dk ) >
di , then
i6=j,k
T −1
αi Hi αi ] and (ii) applies.
ℓcm(dj , dk ) does not divide [Fn :
i6=j,k

38

Note that from the proof of Theorem 6.7(i), it results directly that
i=s
T −1
T −1
αi Hi αi , for every 1 ≤ j ≤ s and the same holds if
αi Hi αi =
i6=j

i=1
α−1
i Hi αi

is replaced byTNi . If any of the conditions in Theorem 6.7 holds,
then m, mj , mk and [
α−1
i Hi αi : N ] are necessarily even.
i6=j,k

Example 6.8. Consider
S another
S partition of F2 , with all the subgroups
normal in F2 : F2 = H1 H2 a H3 ab, where H1 = H = hb, a2 , abai and
H2 = H3 = M with X̃M described below:
b
b

a

M

Ma

a

M ab

a

Mb
a

b
b

Figure 6.8.1: X̃M for the normal subgroup M of index 4.
The subgroup of maximal index is M with index 4 (see Figure 6.8.1). The
transition group TM of X̃M is isomorphic to Z2 × Z2 . So, there is no
4-cycle in TM , no cycle of length greater than 2 (2 = d1 = ds−2 ) neither,
and Theorem 1 cannot apply. Nevertheless, Theorem 6.7 applies. Indeed,
i=3
T
the subgroup
Hi ( H1 , and this implies H2 = H3 .
i=1

6.3

Additional conditions for the HS conjecture for free
groups

In this part, we give some additional conditions that ensure the coset
partition {Hi αi }i=s
i=1 has multiplicity, with a fixed number of repetitions.
We begin with the following basic lemmas which are useful for the rest of
this section. These lemmas are very interesting by themselves as they
underline a connection between the indices of the normal cores of the
subgroups in the partition of Fn .
Lemma 6.9. Let {Hi αi }i=s
Fn with Hi < Fn of
i=1 be a coset partition
T of
−1
index di > 1, αi ∈ Fn , 1 ≤ i ≤ s. Let Ni =
g Hi g, the normal core of
g∈Fn

39

Hi of index mi . Let N =

i=s
T

Ni of index m. Let p be a prime dividing m.

i=1

Then p divides mi for at least p values of i.
Proof. We show that there exists an element w ∈ Fn with oN (w) = p and
o∗i (w) = p for at least p values of i. From Cauchy’s Theorem, there exists
w ∈ Fn with o(N w) = p in Fn N and as N ⊳ Fn , o(N w) = oN (w) = p.
Since oN (w) is the ℓcm of all the orders oj (w) at any vertex in every X̃j ,
1 ≤ j ≤ s, any order is equal to 1 or p. If o∗j (w) = p for some j, then from
Proposition 6.2(ii), o∗i (w) = p for at least p values of i, and as o∗i (w)
divides mi (Lemma 4.10(viii)), p divides mi for at least p values of i. Now,
assume o∗j (w) = 1 for every 1 ≤ j ≤ s. Then from Lemma 6.6(ii), there
exists u ∈ Fn , a conjugate element of w such that oN (u) = oN (w) = p,
o∗j (u) = p for some j and the same argument as above is applied for u.
Lemma 6.10. Let w ∈ Fn with oN (w) = pk11 ...pkr r , p1 , .., pr different
k
primes. Then, for every pj , pj j divides mi for at least pj values of i.
Proof. We denote by p the prime pj and by k the number kj . Let
u=w

oN (w)
p

. Then oN (u) = p and oi (u, j) =

oi (w,j)
o

(w)

gcd(oi (w,j), Np
only if pk divides

)

, for 1 ≤ i ≤ s

at any vertex x̃j . So, oi (u, j) = p if and
oi (w, j). From
k
Lemma 6.9, oi (u, j) = p for at least p values of i, so, p divides oi (w, j) for
at least p values of i, and as such divides mi for at least p values of i.
Proposition 6.11. Let {Hi αi }i=s
i=1 be a coset partition of Fn with Hi < Fn
of index di > 1, αi ∈ Fn , 1 ≤ i ≤ s. Let w ∈ Fn , with oN (w) = p, where p
is a prime. Assume there exist exactly p values, 1 ≤ j1 , j2 , ..., jp ≤ s, such
i=s
T
T −1
/
α−1
that o∗j1 (w) = p and such that w ∈
αi Hi αi .
i Hi αi , w ∈
i6=j1 ,..,jp

i=1

i=s has multiplicity, with d = ... = d .
Then the coset partition {Hi αi }i=1
j1
jp

Proof. From the assumption, o∗j1 (w),..., o∗jp (w) > 1 and o∗i (w) = 1, for all
i 6= j1 , .., jp . From the proof of Lemma 6.9, o∗j1 (w) = p implies
o∗j1 (w) = o∗j2 (w) = ... = o∗jp (w) = p. So, the situation is the following in
X̄N (w): for all i 6= j1 , .., jp , the loops of length oN (w) = p stay inside the
−1
−1
fibers p−1
w (Hi αi ), and for the fibers pw (Hj1 αj1 ),..., pw (Hjp αjp ), these p
fibers participate all together in the loops of length oN (w) = p. So, Lemma
6.1(v) implies dj1 = ... = djp .

40

Theorem 6.12. Let {Hi αi }i=s
i=1 be a coset partition
T −1 of Fn with Hi < Fn of
g Hi g, the normal core of
index di > 1, αi ∈ Fn , 1 ≤ i ≤ s. Let Ni =
g∈Fn

Hi of index mi . Let N =

i=s
T

Ni of index m. If there exists a prime p that

i=1

divides mi for exactly p values of i, 1 ≤ j1 , ..., jp ≤ s, then the coset
partition {Hi αi }i=s
i=1 has multiplicity, with dj1 = ... = djp .
Proof. From Lemma 6.9, p divides mi for at least p values of i. Here, we
assume p divides mi for exactly p values of i, 1 ≤ j1 , ..., jp ≤ s. From
Cauchy’s Theorem, there exists w ∈ Fn , with oN (w) = p. That is,
oi (w) = 1 or oi (w) = p at any vertex, for 1 ≤ i ≤ s. For every i 6= T
j1 , .., jp ,
p does not divide mi , so oi (w) = 1 at any vertex. That is, w ∈
Ni .
i6=j1 ,..,jp

Since oN (w) = p, we can assume o∗j1 (w) = o∗j2 (w) = ...T= o∗jp (w) = p,
Ni , oN (u) = p
since otherwise we can take u a conjugate of w: u ∈
i6=j1 ,..,jp
T
and o∗j1 (u) = o∗j2 (u) = ... = o∗jp (u) = p. So, w ∈
α−1
i Hi αi ,
i6=j1 ,..,jp

w∈
/

i=s
T

i=1

α−1
i Hi αi and Proposition 6.11 applies.

Theorem 6.13. Let {Hi αi }i=s
i=1 be a coset partition
T −1 of Fn with Hi < Fn of
g Hi g, the normal core of
index di > 1, αi ∈ Fn , 1 ≤ i ≤ s. Let Ni =
g∈Fn

Hi of index mi . Let N =

i=s
T

Ni of index m. Let p be the smallest prime

i=1

dividing
1 , j2 , ..., jp ≤ s, such that
T m. If there exist exactly p values, 1 ≤ ji=s
Ni . Then the coset partition {Hi αi }i=1 has multiplicity, with
N$
i6=j1 ,..,jp

dj1 = ... = djp .
Proof. From the assumption, there exists w ∈

T

Ni , so oN (w) > 1

i6=j1 ,..,jp

and oi (w) = 1 at every vertex, for i 6= j1 , .., jp (i.e. for these fibers all the
loops stay inside the fibers). Now, consider the remaining p fibers, and in
fact it is enough to consider only one fiber, the fiber p−1 (Hj1 αj1 ) say.
Since p is the smallest prime dividing m, o∗,j1 (w) = 1 or o∗,j1 (w) ≥ p. If
o∗,j1 (w) = 1, then o∗,j1 (w) = ... = o∗,jp (w) = 1, since p is the smallest
prime dividing m. Otherwise, as there are exactly p fibers, and
o∗,j1 (w), ..., o∗,jp (w) ≥ p, o∗,j1 (w) = p. That is, either
o∗,j1 (w) = ... = o∗jp = 1 or o∗,j1 (w) = ... = o∗jp = p from Lemma 6.9. If
o∗,j1 (w) = ... = o∗jp = p, then Proposition 6.11 applies. If
41

o∗,j1 (w) = ... = o∗jp (w) = 1, thenTfrom Lemma 6.6(ii), there exists u a
Ni , oN (u) = oN (w) and o∗,j1 (u) > 1.
conjugate of w such that u ∈
i6=j1 ,..,jp

Since p is the smallest prime dividing m, applying the same argument as
above gives o∗,j1 (u) = ... = o∗jp (u) = p and we apply Proposition 6.11 for
u.

7

The Herzog-Schönheim conjecture for any
finitely generated group

Let G be
 the group with presentation hX | Ri, with | X |= n. So,
F
n
G≃
, with the normal closure of the set R (not necessarily finite)
K
equal to K. There exists the canonical epimorphism π : Fn → G. We show
that this partition of G induces a partition of Fn with subgroups of the
same indices.

Lemma 7.1. Let G ≃ Fn K , with canonical epimorphism π : Fn → G. Let
{Ki gi }i=s
i=1 be a coset partition of G with Ki < G of index di , gi ∈ G,
1 ≤ i ≤ s. Let Hi = π −1 (Ki ) and αi = π −1 (gi ). Then {Hi αi }i=s
i=1 is a coset
partition of Fn , with Hi < Fn of index di , αi ∈ Fn , 1 ≤ i ≤ s.
Proof. From the third isomorphism theorem, there is a one-to-one
correspondence between the subgroups of G and the subgroups of Fn
containing Ker(π) = K. We set Hi = π −1 (Ki ), so Hi are subgroups of Fn
of index di containing K. Let αi = π −1 (gi ), that is αi are words in Fn
representing the elements gi ∈ G, in particular we can choose the words gi .
We show {Hi αi }i=s
i=1 is a coset partition of Fn . First, assume by
i=s
S
contradiction that
Hi αi $ Fn . So, there exists w ∈ Fn such that
i=1

w∈
/

i=s
S

Hi αi . The element π(w) = Kw ∈ G, so there exists 1 ≤ j ≤ s such

that Kw ∈ Kj gj . Since Kj gj = (Hj K )αj , there exists hj ∈ Hj , such that
Kw = Khj αj , that is w ∈ Khj αj . As K ⊂ Hj , w ∈ Hj αj . So, a
i=s
S
contradiction, that is
Hi αi = Fn . Next, we show that the cosets Hi αi ,
i=1

i=1

1 ≤ i ≤ s, are disjoint. Assume by contradiction that there is
w ∈ Hi αi ∩ Hj αj , i 6= j. So, there exist hj ∈ Hj , and hi ∈ Hi , such that
w = hj αj = hi αi , and Kw = Khj αj = Khi αi , with
Khj αj ∈ (Hj K )αj = Kj gj and Khi αi ∈ (Hi K )αi = Ki gi . So, a
contradiction, that is the cosets Hi αi , 1 ≤ i ≤ s, are disjoint.
42


Theorem 7.2. Let G ≃ Fn K , with canonical epimorphism π : Fn → G.
Let {Ki gi }i=s
i=1 be a coset partition of G with Ki < G of index di , gi ∈ G,
1 ≤ i ≤ s. Let Hi = π −1 (Ki ) and αi = π −1 (gi ). Let {Hi αi }i=s
i=1 be the
induced coset partition of Fn with Hi < Fn of index di , αi ∈ Fn , 1 ≤ i ≤ s.
If one of the conditions from Theorem 2, 3, 4 is satisfied, then the coset
partition {Ki gi }i=s
i=1 has multiplicity.
Proof. If one of the conditions from Theorem 2, 3, 4 or 5 is satisfied, then
i=s , with H subgroups of F of index d ,
in the induced partition {Hi αi }i=1
i
n
i
there exists an index dj that appears at least twice, and this is also true
for the partition of G.
Note that whenever the coset partition {Hi αi }i=s
i=1 has multiplicity, with
di = dj say, the subgroups Hi and Hj are isomorphic. Since from Theorem
2.1, if the subgroups Hi and Hj of Fn have the same index di = dj , then
Hi and Hj are isomorphic. This does not hold necessarily for any finitely
generated group G. Indeed, if the isomorphism ϕij between any pair of
isomorphic subgroups Hi and Hj preserves K = Ker(π), that is
ϕij (K) = K, then the corresponding subgroups Ki and Kj are also
isomorphic.

References
[1] G.Baumslag, Topics in Combinatorial Group Theory, Lectures in
Mathematics ETH Zurich, Birkhauser Verlag, Basel, 1993.
[2] M.A. Berger, A. Felzenbaum, A.S. Fraenkel, Improvements to two
results concerning systems of residue sets, Ars. Combin. 20 (1985),
69-82.
[3] M.A. Berger, A. Felzenbaum, A.S. Fraenkel, The Herzog-Schönheim
conjecture for finite nilpotent groups, Canad. Math. Bull.
29(1986),329-333.
[4] M.A. Berger, A. Felzenbaum, A.S. Fraenkel, Lattice parallelotopes and
disjoint covering systems, Discrete Math. 65 (1987), 23-44.
[5] M.A. Berger, A. Felzenbaum, A.S. Fraenkel, Remark on the
multiplicity of a partition of a group into cosets, Fund. Math. 128
(1987), 139-144.

43

[6] M.A. Brodie, R.F. Chamberlain, L.C Kappe, Finite coverings by
normal subgroups, Proc. Amer. Math. Soc. 104 (1988), 669-674.
[7] W.Dicks, Simplified Mineyev,
http://mat.uab.es/ dicks/SimplifiedMineyev.pdf.
[8] J. D. Dixon, The probability of generating the symmetric group,
Math. Z. 110 (1969), 199-205.
[9] D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson,
W.P. Thurston, Word Processing in Groups, Jones and Bartlett
Publishers (1992).
[10] P. Erdös, On integers of the form 2k + p and some related problems,
Summa Brasil. Math. 2 (1950), 113-123.
[11] P. Erdös, Problems and results in Number theory, Recent Progress in
Analytic Number Theory, vol. 1, Academic Press, London-New York,
1981, 1-13.
[12] J. Friedman, Sheaves on graphs, their homological invariants, and a
proof of the Hanna Neumann conjecture: with an appendix by Warren
Dicks, Mem. Amer. Math. Soc. 233 (2015).
[13] R. Geoghegan, Topological Methods in Group Theory, Graduate Texts
in Mathematics 243, Springer-Verlag, Berlin, Heidelberg, New York
(2008).
[14] S.M. Gersten, Intersections of finitely generated subgroups of free
groups and resolutions of graphs, Invent. Math. 71 (1983), 567-591.
[15] , Y. Ginosar, Tile the group, Elem. Math. 72, Swiss Math. Society, to
appear.
[16] Y. Ginosar, O. Schnabel, Prime factorization conditions providing
multiplicities in coset partitions of groups, J. Comb. Number Theory,
3 (2011), n.2, 75-86.
[17] D. Gorenstein, Finite Groups, Chelsea Publishing Company, New
York (1980).
[18] J.L. Gross, J. Yellen, Graph Theory and its applications, Discrete
Mathematics and its Applications (2006).
[19] A. Hatcher, Algebraic Topology, Cambridge University Press (2002).
44

[20] M. Herzog, J. Schönheim, Research problem no. 9, Canad. Math.
Bull., 17 (1974), 150.
[21] S.V. Ivanov, P.E. Schupp, A remark on finitely generated subgroups of
free groups, Algorithmic Problems in Groups and Semigroups,
Birkhauser 2000, 139-142.
[22] I. Korec, S̆. Znám, On disjoint covering of groups by their cosets,
Math. Slovaca, 27 (1977), 3-7.
[23] T. Lam, K. Leung, On vanishing sums of roots of unity, J. Algebra
224 (2000), n.1, 91-109.
[24] R.C. Lyndon, P.E. Schupp, Combinatorial Group Theory, Ergebnisse
der Mathematik und ihrer Grenzgebiete 89, Springer-Verlag, Berlin,
Heidelberg, New York (1977).
[25] W. Magnus, A. Karrass, D. Solitar, Combinatorial Group Theory,
Dover Publications, New York (1976).
[26] L. Margolis, O. Schnabel, The Herzog-Schonheim conjecture for small
groups and harmonic subgroups , ArXiv 1803.03569.
[27] I. Mineyev, Submultiplicativity and the Hanna Neumann Conjecture,
Annals of Math. 175 (2012), 393-414.
[28] P. Nickolas, Intersections of fintely generated free groups, Bull.
Austral. Math. Soc. 31 (1985), 339-348.
[29] S. Nieveen, A. Smith, Covering spaces and Subgroups of Free groups,
Adviser Dennis Garity, Oregon State University.
[30] M. Newman, Roots of unity and covering sets, Math. Ann. 191
(1971), 279-282.
[31] B. Novák, S̆. Znám, Disjoint covering systems, Amer. Math. Monthly,
81 (1974), 42-45.
[32] J.E. Pin, On reversible automata, Lecture Notes in Computer Science
583, Springer 1992, p. 401-416.
[33] J.E. Pin, Mathematical foundations of automata theory,
https://www.irif.fr/ jep/PDF/MPRI/MPRI.pdf

45

[34] S̆. Porubský, Natural exactly covering systems of congruences,
Czechoslovak Math. J. 24 (1974), 598-606.
[35] S̆. Porubský, Covering systems and generating functions, Acta Arith.
26 (1975), n.3, 223-231.
[36] S̆. Porubský, Results and problems on covering systems of residue
classes, Mitt. Math. Sem. Giessen, 150 (1981).
[37] S̆. Porubský, J. Schönheim, Covering systems of Paul Erdös. Past,
present and future. Paul Erdös and his mathematics, János Bolyai
Math. Soc., 11 (2002), 581-627.
[38] D.J.S. Robinson, A Course in the Theory of Groups, Graduate Texts
in Mathematics 80, Springer-Verlag, Berlin, Heidelberg, New York
(1980).
[39] J.S. Rose, A course on Group Theory, Cambridge Univ. Press,
Cambridge 1978.
[40] J.J. Rotman, An Introduction to Algebraic Topology, Graduate Texts
in Mathematics 119, Springer-Verlag, Berlin, Heidelberg, New York
(1988).
[41] J.P. Serre, Arbres, Amalgames SL2 , Astérisque 46, Société Math. de
France (1977).
[42] C.C. Sims, Computation with finitely presented groups, Encyclopedia
of Mathematics and its Applications 48 , Cambridge University Press
(1994).
[43] J.R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983),
551-565.
[44] J. Stillwell, Classical Topology and Combinatorial Group Theory,
Graduate Texts in Mathematics 72, Springer-Verlag, Berlin,
Heidelberg, New York (1980).
[45] Z.W. Sun, Finite covers of groups by cosets or subgroups, Internat. J.
Math. 17 (2006), n.9, 1047-1064.
[46] Z.W. Sun, An improvement of the Znám-Newman result, Chinese
Quart. J. Math. 6 (1991), n.3, 90-96.

46

[47] Z.W. Sun, Covering the integers by arithmetic sequences II Trans.
Amer. Math. Soc. 348 (1996),4279-4320.
[48] Z.W. Sun, Classified publications on covering systems,
http : //math.nju.edu.cn/ zwsun/Cref.pdf .
[49] G. Tardos, On the intersection of subgroups of a free group, Invent.
Math. 108 (1992), 29-36.
[50] M.J. Tomkinson, Groups covered by abelian subgroups,London Math.
Soc. Lecture Note Ser. 121, Cambridge Univ. Press (1986).
[51] M.J. Tomkinson, Groups covered by finitely many cosets or subgroups,
Comm. Algebra 15(1987), 845-859.

Fabienne Chouraqui,
University of Haifa at Oranim, Israel. E-mail:
fabienne.chouraqui@gmail.com fchoura@sci.haifa.ac.il

47

