arXiv:1607.03010v1 [math.GR] 11 Jul 2016

INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS OF
LEFT ORDERED GROUPS
S. V. IVANOV
Abstract. A conjecture of Dicks and the author on rank of the intersection
of factor-free subgroups in free products of groups is proved for the case of left
ordered groups.

1. Introduction
Recall that the Hanna Neumann conjecture [16] claims that if F is a free group
of rank r(F ), r̄(F ) := max(r(F ) − 1, 0) is the reduced rank of F , and H1 , H2 are
finitely generated subgroups of F , then r̄(H1 ∩ H2 ) ≤ r̄(H1 )r̄(H2 ). It was shown
by Hanna Neumann [16] that r̄(H1 ∩ H2 ) ≤ 2r̄(H1 )r̄(H2 ). For more discussion and
results on this problem, theQreader is referred to [2], [3], [6], [15], [17], [18].
∗
More generally, let F = α∈I Gα be the free product of some groups Gα , α ∈ I.
According to the classic
theorem [13], every subgroup H of F is
Q∗Kurosh subgroup
−1
sα,β Hα,β sα,β
, where Hα,β is a subgroup of Gα , sα,β ∈ F,
a free product F (H) ∗
and F (H) is a free subgroup of F such that, for every s ∈ F and γ ∈ I, it is
true that F (H) ∩ sGγ s−1 = {1}. We say that H is a factor-free subgroup of F
if H = F (H) in the above form of H, i.e., for every s ∈ F and γ ∈ I, we have
H ∩ sGγ s−1 = {1}. Since a factor-free subgroup H of F is free, the reduced rank
r̄(H) := max(r(H) − 1, 0) of H is well defined. Let q ∗ = q ∗ (Gα , α ∈ I) denote the
minimum of orders > 2 of finite subgroups of groups Gα , α ∈ I, and q ∗ := ∞ if
∗
there are no such subgroups. If q ∗ = ∞, define q∗q−2 := 1. It was shown by Dicks
and the author [4] that if H1 , H2 are finitely generated factor-free subgroups of F,
then
∗
r̄(H1 ∩ H2 ) ≤ 2 q∗q−2 r̄(H1 )r̄(H2 ).
It was conjectured by Dicks and the author [4] that if groups Gα , α ∈ I, contain
no involutions then, similarly to the Hanna Neumann conjecture, the coefficient 2
could be left out and
∗
r̄(H1 ∩ H2 ) ≤ q∗q−2 r̄(H1 )r̄(H2 ).
(1)
A special case of this generalization of the Hanna Neumann conjecture is established by Dicks and the author [5] by proving that if H1 , H2 are finitely generated
factor-free subgroups of the free product F all of whose factors are groups of order
∗
3, then, indeed, r̄(H1 ∩ H2 ) ≤ q∗q−2 r̄(H1 )r̄(H2 ) = 3r̄(H1 )r̄(H2 ). We remark that it
follows from results of [4] that the last inequality (as well as (1)) is sharp and may
not be improved. Here is another special case when the conjectured inequality (1)
holds true.
2010 Mathematics Subject Classification. Primary 20E06, 20E07, 20F60, 20F65.
Supported in part by the NSF under grant DMS 09-01782.
1

2

S. V. IVANOV

Theorem
1. Suppose that Gα , α ∈ I, are left (or right) ordered groups, F =
Q∗
G
is
their free product, and H1 , H2 are finitely generated factor-free subα
α∈I
groups of F. Then
r̄(H1 ∩ H2 ) ≤

q∗
q∗ −2 r̄(H1 )r̄(H2 )

= r̄(H1 )r̄(H2 ).

Moreover, let S(H1 , H2 ) denote a set of representatives of those double cosets H1 tH2
of F, t ∈ F, that have the property H1 ∩ tH2 t−1 6= {1}. Then
X
r̄(H1 ∩ sH2 s−1 ) ≤ r̄(H1 )r̄(H2 ).
r̄(H1 , H2 ) :=
s∈S(H1 ,H2 )

We remark that Antolı́n, Martino, and Schwabrow [1] proved a more general
result on Kurosh rank of the intersection of subgroups of free products of right
ordered groups by utilizing the Bass–Serre theory of groups acting on trees and
some ideas of Dicks [3]. Our proof of Theorem 1 seems to be of independent
interest as it uses explicit geometric construction of graphs, representing subgroups
of free products, that are often more suitable for counting arguments, see [9], [11].
It is fairly easy to see that Theorem 1 implies both the Hanna Neumann conjecture and the strengthened Hanna Neumann conjecture, put forward by W. Neumann [17], see Sect. 5. The strengthened Hanna Neumann conjecture claims that
if H1 , H2 are finitely generated subgroups of a free group F , then
X
r̄(H1 ∩ sH2 s−1 ) ≤ r̄(H1 )r̄(H2 ),
s∈S(H1 ,H2 )

where the set S(H1 , H2 ) is defined as in Theorem 1 with F in place in F. Recall
that Friedman [6] proved the strengthened Hanna Neumann conjecture by making
use of sheaves on graphs and Mineyev [15] gave a proof to the strengthened Hanna
Neumann conjecture by using Hilbert modules and group actions, see also Dicks’s
proof [3]. Similarly to Dicks [3] and Mineyev [15], we also use the idea of group
ordering and special sets of edges, however, our arguments deal directly with core
graphs of subgroups of free products that are analogous to Stallings graphs [18]
representing subgroups of free groups.
In Sect. 2, we introduce necessary definitions and basic terminology. In Sect. 3,
we define and study strongly positive words in free products of left ordered groups.
Sect. 4 contains the proof of Theorem 1. In Sect. 5, we briefly look at the case of
free groups.
2. Preliminaries
Q
Let Gα , α ∈ I, be nontrivial groups, F = ∗α∈I Gα be their free product, and
H a finitely generated factor-free subgroup of F, H 6= {1}. Consider an alphabet
A = ∪α∈I Gα , where Gα ∩ Gα′ = {1} if α 6= α′ .
Similarly to the graph-theoretic approach of article [9], in a simplified version
suitable for finitely generated factor-free subgroups of F, see [7], [8], [10], we first
define a labeled A-graph Ψ(H) which geometrically represents H in a fashion analogous to the way the Stallings graph represents a subgroup of a free group, see
[18].
If Γ is a graph, V Γ denotes the vertex set of Γ and EΓ denotes the set of oriented
edges of Γ. If e ∈ EΓ, e− , e+ denote the initial, terminal, resp., vertices of e and e−1
is the edge with opposite orientation, where e−1 6= e for every e ∈ EΓ, (e−1 )− = e+ ,
(e−1 )+ = e− . A finite path p = e1 . . . ek in Γ is a sequence of edges ei such that

INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS

3

(ei )+ = (ei+1 )− , i = 1, . . . , k − 1. Denote p− := (e1 )− , p+ := (ek )+ , and |p| := k,
where |p| is the length of p. We allow the possibility |p| = 0 and p = {p− } = {p+ }.
A finite path p is called closed if p− = p+ . An infinite path p = e1 . . . ek . . . is
an infinite sequence of edges ei such that (ei )+ = (ei+1 )− for all i = 1, 2, . . . . If
p = e1 . . . ek . . . and q = f1 . . . fℓ . . . are infinite paths such that (e1 )− = (f1 )− ,
then q −1 p := . . . fℓ−1 . . . f1−1 e1 . . . ek . . . is a biinfinite path. A path p is reduced if
p contains no subpath of the form ee−1 , e ∈ EΓ. A closed path p = e1 . . . ek is
cyclically reduced if |p| > 0 and both p and the cyclic permutation e2 . . . ek e1 of p
are reduced paths. The core of a graph Γ, denoted core(Γ), is the minimal subgraph
of Γ that contains every edge e which can be included into a cyclically reduced path
in Γ.
Let Ψ be a graph whose vertex set V Ψ consists of two disjoint parts VP Ψ, VS Ψ,
so V Ψ = VP Ψ ∪ VS Ψ. Vertices in VP Ψ are called primary and vertices in VS Ψ are
termed secondary. Every edge e ∈ EΨ connects primary and secondary vertices,
hence Ψ is a bipartite graph. Ψ is called a labeled A-graph, or simply A-graph if Ψ
is equipped with a map ϕ : EΨ → A, called labeling, such that, for every e ∈ EΨ,
ϕ(e) ∈ A = ∪α∈I Gα , ϕ(e−1 ) = ϕ(e)−1 and if e+ = f+ ∈ VS Ψ, then ϕ(e), ϕ(f ) ∈ Gα
for the same α = θ(e+ ) ∈ I, called the type of the vertex e+ ∈ VS Ψ and denoted
α = θ(e+ ). If e+ ∈ VS Ψ, define θ(e) := θ(e+ ) and θ(e−1 ) := θ(e+ ). Thus, for every
e ∈ Ψ, we have defined an element ϕ(e) ∈ A, called the label of e, and θ(e) ∈ I,
the type of e.
The reader familiar with van Kampen diagrams over a free product of groups,
see [14], will recognize that our labeling function ϕ : EΨ → A is defined in the
way analogous to labeling functions on van Kampen diagrams over free products of
groups. Recall that van Kampen diagrams are planar 2-complexes whereas graphs
are 1-complexes, however, apart from this, the ideas of cancelations and edge foldings work equally well for both diagrams and graphs.
An A-graph Ψ is called irreducible if properties (P1)–(P3) hold true:
(P1) If e, f ∈ EΨ, e− = f− ∈ VP Ψ, and e+ 6= f+ , then θ(e) 6= θ(f ).
(P2) If e, f ∈ EΨ, e 6= f , and e+ = f+ ∈ VS Ψ, then ϕ(e) 6= ϕ(f ) in Gθ(e) .
(P3) Ψ has no multiple edges, degΨ v > 0 for every v ∈ V Ψ, and there is at most
one vertex of degree 1 in Ψ which, if exists, is primary.
Suppose Ψ is a connected irreducible A-graph and a primary vertex o ∈ VP Ψ is
distinguished so that degΨ o = 1 if Ψ happens to have a vertex of degree 1. Then o
is called the base vertex of Ψ = Ψo .
Q
As usual, elements of the free product F = ∗α∈I Gα are regarded as words over
the alphabet A = ∪α∈I Gα . A syllable of a word W over A is a maximal subword
of W all of whose letters belong to the same factor Gα . The syllable length kW k
of W is the number of syllables of W , whereas the length |W | of W is the number
of all letters in W . A nonempty word W over A is called reduced if every syllable
of W consists of a single letter. Clearly, |W | = kW k if W is reduced. An arbitrary
nontrivial element of the free product F can be uniquely written as a reduced word.
A word W is called cyclically reduced if W 2 is reduced. We write U = W if words
U , W are equal as elements of F. The literal (or letter-by-letter) equality of words
U , W is denoted U ≡ W .
The significance of irreducible A-graphs for geometric interpretation of factorfree subgroups H of F is given in the following.

4

S. V. IVANOV

Lemma
Q∗ 1. Suppose H is a finitely generated factor-free subgroup of the free product
F = α∈I Gα , H 6= {1}. Then there exists a finite connected irreducible A-graph
Ψ = Ψo (H), with the base vertex o, such that a reduced word W over the alphabet A
belongs to H if and only if there is a reduced path p in Ψo (H) such that p− = p+ = o,
ϕ(p) = W in F, and |p| = 2|W |.
Proof. The proof is based on Stallings’s folding techniques and is somewhat analogous to the proof of van Kampen lemma for diagrams over free products of groups,
see [14] (in fact, it is simpler because foldings need not preserve the property of
being planar for the diagram). A more general approach, suitable for an arbitrary
subgroup of F, is discussed in Lemmas 1, 4 [9].
Let H = hV1 , . . . , Vk i be generated by reduced words V1 , . . . , Vk ∈ F. Consider
e which consists of k closed paths p1 , . . . , pk such that they have a single
a graph Ψ
common vertex o = (pi )− , and |pi | = 2|Vi |, i = 1, . . . , k. Furthermore, we dise and call o primary, the vertices adjacent to o
tinguish o as the base vertex of Ψ
are called secondary vertices and so on. The labeling function ϕ on pi is defined
so that ϕ(pi ) = Vi , i = 1, . . . , k, where ϕ(p) := ϕ(e1 ) . . . ϕ(eℓ ) if p = e1 . . . eℓ and
e
e1 , . . . , eℓ ∈ E Ψ.
e
e o is a finite connected A-graph with the base vertex o that has
Clearly, Ψ = Ψ
the following property
e o such that
(Q) A word W ∈ F belongs to H if and only if there is a path p in Ψ
p− = p+ = o and ϕ(p) = W .
e o need not be irreducible and we will do foldings of edges in Ψ
e o which
However, Ψ
preserve property (Q) and which aim to achieve properties (P1)–(P2).
e o so that
Assume that property (P1) fails for edges e, f with e− = f− ∈ VP Ψ
′
e+ 6= f+ and θ(e) = θ(f ). Let us redefine the labels of all edges e with e′+ = e+ so
that ϕ(e′ )ϕ(e)−1 does not change and ϕ(e) = ϕ(f ) in Gθ(e) . Now we identify the
edges e, f and vertices e+ , f+ . Observe that this folding preserves property (Q)
e o |.
((P2) might fail) and decreases the edge number |E Ψ
If property (P2) fails for edges e, f and ϕ(e) = ϕ(f ) in Gθ(e) , then we identify the
e o|
edges e, f . Note property (Q) still holds ((P1) might fail) and the number |E Ψ
decreases.
e o such that
Suppose property (P3) fails and there are two distinct edges e, f in Ψ
e o . By property (Q), it follows from H being factor-free
e− = f− , e+ = f+ ∈ VS Ψ
that ϕ(e) = ϕ(f ) in Gθ(e) . Therefore, we can identify the edges e, f , thus preserving
e o |. If property (P3) fails so that there
property (Q) and decreasing the number |E Ψ
is a vertex v of degree 1, different from o, then we delete v along with the incident
e o | decreases.
edge. Clearly, property (Q) still holds and the number |E Ψ
e o |, in polynomial time of size of input, which is the
Thus, by induction on |E Ψ
Pk
total length i=1 |Vi |, we can effectively construct an irreducible A-graph Ψo with
property (Q). Other stated properties of Ψo are straightforward.

The following lemma further elaborates on the correspondence between finitely
generated factor-free subgroups of the free product F and irreducible A-graphs.
Lemma 2. Let Ψo be a finite connected irreducible A-graph with the base vertex
o, and H = H(Ψo ) be a subgroup of F that consists of all words ϕ(p), where p

INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS

5

is a path in Ψo with p− = p+ = o. Then H is a factor-free subgroup of F and
r̄(H) = −χ(Ψo ), where χ(Ψo ) = |V Ψo | − 21 |EΨo | is the Euler characteristic of Ψo .
Proof. This follows from the facts that the fundamental group π1 (Ψo , o) of Ψo at
o is free of rank −χ(Ψo ) + 1 and that the homomorphism π1 (Ψo , o) → F, given by
p → ϕ(p), where p is a path with p− = p+ = o, has the trivial kernel following from
properties (P1)–(P2).

Suppose
H is a nontrivial finitely generated factor-free subgroup of a free product
Q∗
F = α∈I Gα , and Ψo = Ψo (H) is an irreducible A-graph for H as in Lemma 1.
Let Ψ(H) denote the core of Ψo (H). Clearly, Ψ(H) has no vertices of degree ≤ 1
and Ψ(H) is also an irreducible A-graph. It is easy to see that the graph Ψo (H)
of H can be obtained back from the core graph Ψ(H) of H by attaching a suitable
path p to Ψ(H) so that p starts at a primary vertex o, ends in p− ∈ VP Ψ(H), and
then by doing foldings of edges as in the proof of Lemma 1.
Now suppose H1 , H2 are nontrivial finitely generated factor-free subgroups of
F. Consider a set S(H1 , H2 ) of representatives of those double cosets H1 tH2 of
F, t ∈ F, that have the property H1 ∩ tH2 t−1 6= {1}. For every s ∈ S(H1 , H2 ),
define the subgroup Ks := H1 ∩ sH2 s−1 . Analogously to the case of free groups, see
[17], [18], we now construct a finite irreducible A-graph Ψ(H1 , H2 ) whose connected
components are core graphs Ψ(Ks ), s ∈ S(H1 , H2 ).
First we define an A-graph Ψ′o (H1 , H2 ). The set of primary vertices of Ψ′o (H1 , H2 )
is VP Ψ′o (H1 , H2 ) := VP Ψo1 (H1 ) × VP Ψo2 (H2 ). Let
τi : VP Ψ′o (H1 , H2 ) → VP Ψoi (Hi )
denote the projection map, τi ((v1 , v2 )) = vi , i = 1, 2.
The set of secondary vertices VS Ψ′o (H1 , H2 ) of Ψ′o (H1 , H2 ) consists of equivalence
classes [u]α , where u ∈ VP Ψ′o (H1 , H2 ), α ∈ I, with respect to the minimal equivaα
α
lence relation generated by the following relation ∼ on VP Ψ′o (H1 , H2 ): Define v ∼ w
if there are edges ei , fi ∈ EΨoi (Hi ) such that (ei )− = τi (v), (fi )− = τi (w), (ei )+ =
(fi )+ , i = 1, 2, the edges ei , fi have type α, and ϕ(e1 )ϕ(f1 )−1 = ϕ(e2 )ϕ(f2 )−1 in
α
Gα . It is easy to see that ∼ is symmetric and transitive on distinct pairs and triples
(but it could lack reflexive property).
The edges in Ψ′o (H1 , H2 ) are defined so that u ∈ VP Ψ′o (H1 , H2 ) and [v]α ∈
VS Ψ′o (H1 , H2 ) are connected by an edge if and only if u ∈ [v]α .
The type of a vertex [v]α ∈ VS Ψ′o (H1 , H2 ) is α and if e ∈ EΨ′o (H1 , H2 ), e− = u,
e+ = [v]α , then ϕ(e) := ϕ(e1 ), where e1 ∈ EΨo1 (H1 ) is an edge of type α with
(e1 )− = τ1 (u), when such an e1 exists, and ϕ(e1 ) := bα 6= 1, bα ∈ Gα , otherwise.
It follows from the definitions and properties (P1)–(P2) of Ψoi (Hi ), i = 1, 2,
that Ψ′o (H1 , H2 ) is an A-graph with properties (P1)–(P2). Hence, taking the core
of Ψ′o (H1 , H2 ), we obtain an irreducible A-graph which we denote Ψ(H1 , H2 ).
In addition, it is not difficult to see that, when taking the connected component
Ψ′o (H1 , H2 , o) of Ψ′o (H1 , H2 ) that contains the vertex o = (o1 , o2 ) and inductively
removing from Ψ′o (H1 ∩ H2 , o) vertices of degree 1 different from o, we obtain an
irreducible A-graph Ψo (H1 ∩ H2 ) with the base vertex o that corresponds to the
intersection H1 ∩ H2 as in Lemma 1.
Observe that it follows from the definitions and property (P1) for Ψ(Hi ), i = 1, 2,
that, for every edge e ∈ EΨ(H1 , H2 ) with e− ∈ VP Ψ(H1 , H2 ), there are unique
edges ei ∈ EΨ(Hi ) such that τi (e− ) = (ei )− , i = 1, 2. Hence, by setting τi (e) = ei ,

6

S. V. IVANOV

τi (e+ ) = (ei )+ , i = 1, 2, we extend τi to the graph map
τi : Ψ(H1 , H2 ) → Ψ(Hi ),

i = 1, 2.

It follows from definitions that τi is locally injective and τi preserves syllables of
ϕ(p) for every path p with primary vertices p− , p+ .
Lemma 3. Suppose H1 , H2 are finitely generated factor-free subgroups of the free
product F and the set S(H1 , H2 ) is not empty. Then the connected components of
the graph Ψ(H1 , H2 ) are core graphs Ψ(H1 ∩ sH2 s−1 ) of subgroups H1 ∩ sH2 s−1 ,
s ∈ S(H1 , H2 ). In particular,
X
r̄(H1 ∩ sH2 s−1 ) = −χ(Ψ(H1 , H2 )).
r̄(H1 , H2 ) =
s∈S(H1 ,H2 )

Proof. As in Lemma 1, let Ψoi (Hi ) be an irreducible A-graph, corresponding to
the subgroup Hi of F, i = 1, 2, and Ψ(Hi ) denote the core of Ψoi (Hi ). Let
vi ∈ VP Ψ(Hi ), i = 1, 2, and q(vi ) denote a path in Ψoi (Hi ) with q(vi )− = oi
and q(vi )+ = vi . Suppose Xi ∈ F, i = 1, 2, and H1X1 ∩ H2X2 6= {1}, where
HiXi := Xi Hi Xi−1 . Consider an irreducible A-graph Ψui (HiXi ), i = 1, 2. Note
that the core graph Ψ(H1X1 ∩ H2X2 ) can be identified with a connected component,
denoted Ψ(X1 ,X2 ) (H1 , H2 ), of the irreducible A-graph Ψ(H1 , H2 ). In addition, if
w ∈ VP Ψ(X1 ,X2 ) (H1 , H2 ), then there are paths pi (w) in Ψui (HiXi ), i = 1, 2, such
that (pi (w))− = ui , (pi (w))+ = τi (w), and ϕ(p1 (w)) = ϕ(p2 (w)). Furthermore, it
follows from the definitions that Xi ϕ(q(τi (w)))ϕ(pi (w))−1 ∈ HiXi , i = 1, 2. Therefore, there are words Vi ∈ Hi , i = 1, 2, such that Xi Vi ϕ(q(τi (w))) = ϕ(pi (w)).
Since ϕ(p1 (w)) = ϕ(p2 (w)), we further obtain
X1−1 X2 = V1 ϕ(q(τ1 (w)))ϕ(q(τ2 (w)))−1 V2−1 .

(2)

Now we can draw the following conclusion. For every pair (X1 , X2 ) ∈ F × F
such that H1X1 ∩ H2X2 6= {1} and a vertex w ∈ VP Ψ(X1 ,X2 ) (H1 , H2 ), there are
words Vi ∈ Hi , i = 1, 2, such that the equality (2) holds. Since the paths q(τi (w)),
i = 1, 2, in (2) depend only on a connected component of Ψ(H1 , H2 ), it follows from
(2) that if (1, X), (1, Y ) are some pairs such that Ψ(1,X) (H1 , H2 ) = Ψ(1,Y ) (H1 , H2 ),
then X ∈ H1 Y H2 ⊆ F.
Conversely, if X ∈ H1 Y H2 , then the equality Ψ(1,X) (H1 , H2 ) = Ψ(1,Y ) (H1 , H2 )
is obviously true. Thus, the set S(H1 , H2 ) is in bijective correspondence with
connected components of Ψ(H1 , H2 ) and, by Lemma 2, we have r̄(H1 ∩ sH2 s−1 ) =
−χ(Ψ(1,s) (H1 , H2 )) for every s ∈ S(H1 , H2 ). Adding up over all s ∈ S(H1 , H2 ), we
arrive to the required equality r̄(H1 , H2 ) = −χ(Ψ(H1 , H2 )).

3. Strongly positive words in free products of left ordered groups
Recall that G is called a left ordered group if G is equipped with a total order
≤ which is left invariant, i.e., for every triple a, b, c ∈ G, the relation a ≤ b implies
ca ≤ cb. If G is left ordered, then G can also be right ordered (and vice versa).
Indeed, if ≤ is a left order on G then, setting a  b if and only if a−1 ≤ b−1 , we
obtain a right order  on G.
Q
Let Gα , α ∈ I, be nontrivial left (or right) ordered groups and let F = ∗α∈I Gα
be their free product. Since it will be more convenient to work with left order, we
assume that Gα , α ∈ I, are left ordered. It is well known, see [12], and fairly easy

INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS

7

to show that there exists a total order  on F which extends the left orders on
groups Gα , α ∈ I, and which turns F into a left ordered group.
A reduced word W ∈ F is called positive if W ≻ 1. A reduced word W is called
strongly positive, denoted W ≻≻ 1, if every nonempty suffix of W is positive, i.e.,
if W ≡ W1 W2 with |W2 | > 0, then W2 ≻ 1. Clearly, a strongly positive word is
positive. Note if U, W are strongly positive and U W is reduced, then U W ≻≻ 1. A
word U is (resp. strongly) negative if U −1 is (resp. strongly) positive.
Lemma 4. Suppose S, T are strongly positive words and the word S −1 T is reduced.
Then S −1 T is either strongly positive or strongly negative.
Proof. Let S ≡ S1 S2 , T ≡ T1 T2 , where |S2 |, |T2 | > 0. Then S2 ≻ 1, T2 ≻ 1
by S, T ≻≻ 1. Since S −1 T is reduced, we have S −1 T 6= 1, hence S −1 T ≻ 1 or
S −1 T ≺ 1. Assume S −1 T ≻ 1. Then T ≻ S = S1 S2 or S1−1 T ≻ S2 ≻ 1, hence, in
view of T2 ≻ 1, all nonempty suffixes of S −1 T are positive. This implies S −1 T ≻≻ 1.
If S −1 T ≺ 1, then, switching S and T , we can show as above that T −1 S ≻≻ 1, hence
S −1 T is strongly negative.

Lemma 5. Suppose W is a reduced word. Then there exists a factorization W ≡
U1 U2−1 such that |U1 |, |U2 | ≥ 0 and each of U1 , U2 is either empty or strongly
positive.
Proof. Consider a factorization W ≡ U1ε1 . . . Ukεk , where, for every j, Uj ≻≻ 1 and
εj = ±1, that would be minimal with respect to k. Since for every letter a of W
either a ≻≻ 1 or a−1 ≻≻ 1, it follows that such a factorization exists and k ≤ |W |.
Note if εj = εj+1 = 1, then Uj Uj+1 is reduced and so Uj Uj+1 ≻≻ 1. Similarly, if
−1
εj = εj+1 = −1, then Uj−1 Uj+1
is reduced and so Uj+1 Uj ≻≻ 1. Hence, it follows
from the minimality of k that εj 6= εj+1 for all j = 1, . . . , k − 1. If now εj = −1
and εj+1 = 1 for some j, then we can use Lemma 4 and conclude that either
−1
Uj−1 Uj+1 ≻≻ 1 or Uj+1
Uj ≻≻ 1, contrary to minimality of k. Thus, it is proven that
either k = 1 or k = 2 and ε1 = 1, ε2 = −1, as required.

Lemma 6. Suppose W is a cyclically reduced word. Then there exists a factorization W ≡ W1 W2 such that the cyclic permutation W̄ ≡ W2 W1 of W is either
strongly positive or strongly negative.
Proof. By Lemma 5, W ≡ U1 U2−1 , where |U1 |, |U2 | ≥ 0 and Uj ≻≻ 1 if |Uj | > 0, j =
1, 2. Since W 2 is reduced, U2−1 U1 is reduced and, by Lemma 4, either U2−1 U1 ≻≻ 1
or U2−1 U1 ≺≺ 1. Hence, W̄ ≡ U2−1 U1 is a desired cyclic permutation of W .

4. Proving Theorem 1
Let Gα , α ∈ I, be nontrivial left (or right) ordered groups and let F be their free
product equipped with a left order . Also, fix a total order ≤ on the index set I.
Let Ψ be a finite irreducible A-labeled graph, where A = ∪α∈I Gα . An edge
e ∈ EΨ is called maximal if there are reduced infinite paths p = p(e) = e1 e2 . . . ,
q = q(e) = f1 f2 . . . in Ψ, where ej , fj ∈ EΨ, such that e = e1 , (e1 )− = (f1 )−
is primary, θ(e1 ) > θ(f1 ), and, for every j ≥ 1, both ϕ(e1 . . . e2j ) ≺ 1 and
ϕ(f1 . . . f2j ) ≺ 1. Note that the vertices (e1 . . . e2j )+ , (f1 . . . f2j )+ are primary
and q −1 p = . . . f2−1 f1−1 e1 e2 . . . is a reduced biinfinite path.
Lemma 7. Suppose Ψ is a finite irreducible A-labeled graph whose Euler characteristic is negative, χ(Ψ) < 0. Then Ψ contains a maximal edge.

8

S. V. IVANOV

Proof. Since χ(Ψ) < 0, Ψ has a connected component Ψ1 with χ(Ψ1 ) < 0. Without
loss of generality, we may assume that core (Ψ1 ) = Ψ1 . It is not difficult to see from
χ(Ψ1 ) < 0 and from core (Ψ1 ) = Ψ1 that, for every pair h, h′ ∈ EΨ1 , there is a
reduced path p = h . . . h′ whose first, last edges are h, h′ , resp.. Pick a primary
vertex o in Ψ1 and two distinct edges t1 , u1 with (t1 )− = (u1 )− = o. Let t, u be
some reduced paths such that first edges of t, u are t1 , u1 , resp., and t+ , u+ have
degree > 2. Then it follows from the above remark that there are closed paths
r0 , s0 starting at t+ , u+ , resp., such that the path tr02 t−1 us20 u−1 is reduced. Since
Ψ1 is irreducible and r0 , s0 are reduced, it follows ϕ(r0 ) 6= 1, ϕ(s0 ) 6= 1 in F.
Let r, s be some cyclic permutations of the closed paths r0 , s0 , resp., that start
at some primary vertices and R = ϕ(r), S = ϕ(s) be reduced words. Clearly, R, S
are cyclically reduced and |R| = |r|/2 > 1, |S| = |s|/2 > 1. By Lemma 6, there
are cyclic permutations R̄, S̄ of R, S, resp., such that R̄εr , S̄ εs are strongly positive,
where εr , εs ∈ {±1}. Switching from r0 , s0 to r0−1 , s−1
0 , resp., if necessary, we may
assume that εr = εs = −1, i.e., R̄−1 , S̄ −1 ≻≻ 1. Let r̄, s̄ denote cyclic permutations
of r, s, resp., such that ϕ(r̄) = R̄, ϕ(s̄) = S̄. Also, let r̄ = r̄1 r̄2 , s̄ = s̄1 s̄2 be
factorizations of r̄, s̄, resp., defined by vertices t+ , u+ , resp..
Consider two infinite paths starting at o = t− = u− and defined as follows. Let
T = tr0+∞ whose prefixes are tr0k , k ≥ 0, and U = us+∞
whose prefixes are usℓ0 ,
0
ℓ ≥ 0. It follows from the definitions that T starts at t− = o, goes along t to t+ and
then cycles around r0 infinitely many times, in particular, T is reduced. Similarly,
U starts at u− = o, goes along u to u+ and then cycles around s0 .
Denote T = t1 t2 . . . , where tj ∈ EΨ1 , and U = u1 u2 . . . , where uk ∈ EΨ1 .
Let T (j1 , j2 ) := tj1 . . . tj2 , where j1 ≤ j2 , denote the subpath of T that starts at
(tj1 )− and ends in (tj2 )+ . It is convenient to set T (j, j − 1) := {(tj )− } for all j ≥ 1.
Similarly, U (j1 , j2 ) := uj1 . . . uj2 , where j1 ≤ j2 , and U (j, j − 1) := {(uj )− } if j ≥ 1.
Suppose 2j > |t| + |r̄2 |. Then 2j − |t| − |r̄2 | > 0. Let m be the remainder of
2j − |t| − |r̄2 | when divided by |r|. Set mr := m if m > 0 and mr := |r| if m = 0.
Note T (1, 2j) = T (1, 2j − mr )T (2j − mr + 1, 2j) and ϕ(T (2j − mr + 1, 2j)) ≡ R̄3 ,
where R̄3 is a prefix of ϕ(r̄) ≡ R̄3 R̄4 of even length mr > 0. Recall ϕ(r̄) = R̄ and
R̄−1 ≻≻ 1, hence R̄3−1 ≻ 1 and R̄3 ≺ 1. Note R̄3 = ϕ(T (2j − mr + 1, 2j)) ≺ 1
implies, by left invariance of the order , that
ϕ(T (1, 2j)) ≺ ϕ(T (1, 2j − mr )).

(3)

′

Now suppose 2j > |u| + |s̄2 |. Let m be the remainder of 2j − |t| − |s̄2 | > 0 when
divided by |s|. Set ms := m′ if m′ > 0 and ms := |s| if m′ = 0. Then we can derive
from S̄ −1 ≻≻ 1, similar to (3), that
ϕ(U (1, 2j)) ≺ ϕ(U (1, 2j − ms )).

(4)

The comparisons (3)–(4) prove that a maximal element of the infinite set
{ϕ(T (1, 2j)), ϕ(U (1, 2k)) | j ≥ 0, k ≥ 1} ⊆ F

(5)

exists and it is the maximal element of the finite set
{ ϕ(T (1, 2j)), ϕ(U (1, 2k)) | 0 ≤ 2j ≤ |t| + |r̄2 |, 0 < 2k ≤ |u| + |s̄2 | } ⊂ F.
Let ϕ(Q(1, 2jM )), where jM ≥ 0, Q ∈ {T, U }, denote the maximal element of
the set (5). Note vM = Q(1, 2jM )+ is primary. Observe that elements ϕ(T (1, 2j)),
ϕ(U (1, 2k)), j ≥ 0, k ≥ 1, in (5) are distinct and represent ϕ-labels of subpaths of
the biinfinite path U −1 T that connect the primary vertex o = t− to all primary
vertices of U −1 T along U −1 T (or its inverse). If we take another primary vertex v on

INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS

9

U −1 T and consider the set of labels of subpaths that connect v to primary vertices
of U −1 T as above, then the resulting set can be obtained from (5) by multiplication
on the left by ϕ(h(o, v))−1 , where h(o, v) = T (1, 2jv ) if v = T (1, 2jv )+ , 2jv ≥ 0,
and h(o, v) = U (1, 2kv ) if v = U (1, 2kv )+ , 2kv > 0. Since left multiplication
preserves the order, these remarks imply that the vertex vM = Q(1, 2jM )+ defines
a factorization of the biinfinite path U −1 T = q −1 p into infinite paths q, p, where
p = e1 e2 . . . , q = f1 f2 . . . , ej , fj are edges, j ≥ 1, so that, for every j ≥ 1, we have
ϕ(e1 e2 . . . e2j ) ≺ 1 and ϕ(f1 f2 . . . f2j ) ≺ 1. Therefore, if θ(e1 ) > θ(f1 ), then e1 is a
maximal edge of Ψ and if θ(f1 ) > θ(e1 ), then f1 is maximal in Ψ.

Suppose Γ is a finite graph. A set D ⊆ EΓ of edges is called good (for cutting)
if the graph Γ \ (D ∪ D−1 ) consists of connected components whose Euler characteristics are 0. Clearly, Γ contains a good edge set if and only if no connected
component of Γ is a tree.
Lemma 8. Suppose Ψ is a finite connected irreducible A-graph with χ(Ψ) < 0.
Then the set of all maximal edges of Ψ is good (for cutting).
Proof. Arguing on the contrary, assume that D ⊆ EΨ is the set of all maximal
edges of Ψ and D is not good. Then the graph Ψ \ (D ∪ D−1 ) contains a connected
component Ψ′1 with either χ(Ψ′1 ) < 0 or χ(Ψ′1 ) > 0. If χ(Ψ′1 ) < 0, then the core
Ψ1 = core(Ψ′1 ) of Ψ′1 is a finite irreducible A-graph with χ(Ψ1 ) < 0. By Lemma 7,
Ψ1 contains a maximal edge e. However, it follows from the definition that e is also
maximal for Ψ, hence, e ∈ D. This contradiction shows that χ(Ψ′1 ) > 0, hence Ψ′1
is a tree which we denote T .
Let C denote the set that consists of all c ∈ EΨ such that c+ ∈ V T and c 6∈ ET .
It follows from the definitions that if c ∈ C then c ∈ D or c−1 ∈ D. Since every
d ∈ D is maximal, there are infinite reduced paths p(d) = e1 (d)e2 (d) . . . and q(d) =
f1 (d)f2 (d) . . . such that e1 (d)− = f1 (d)− ∈ VP Ψ, e1 (d) = d, θ(e1 (d)) > θ(f1 (d))
and, for every j ≥ 1, ϕ(e1 (d) . . . e2j (d)) ≺ 1 and ϕ(f1 (d) . . . f2j (d)) ≺ 1.
Pick an arbitrary c ∈ C. Suppose c− is primary. Since d− ∈ VP Ψ if d ∈ D
and c or c−1 is in D, it follows that c ∈ D. Consider a shortest path of the form
h(c) := e1 (c) . . . e2ℓ (c), ℓ ≥ 1, such that either e2ℓ (c)−1 ∈ C or e2ℓ (c)−1 ∈ T and
e2ℓ+1 (c)−1 ∈ C. Define σ(c) := e2ℓ (c)−1 if e2ℓ (c)−1 ∈ C and σ(c) := e2ℓ+1 (c)−1
if e2ℓ+1 (c)−1 ∈ C. Since T is a finite tree, such a path h(c) exists, |h(c)| > 0,
σ(c) 6= c, and ϕ(h(c)) ≺ 1. Note h(c)− , h(c)+ are primary vertices of c, σ(c),
resp., and h(c) = chT (c)σ(c)−εσ(c) , where hT (c) is a subpath of h(c) in T with
hT (c)− = c+ , hT (c)+ = σ(c)+ , and εσ(c) = 1 if σ(c)+ is secondary and εσ(c) = 0 if
σ(c)+ is primary.
Now assume that c+ is primary. Then c−1 = dc ∈ D. Consider a shortest path
of the form h(c) := f1 (dc ) . . . f2ℓ−2 (dc ), where ℓ ≥ 1 and if ℓ = 1 then h(c) := {c+ },
such that either f2ℓ−2 (dc )−1 ∈ C or f2ℓ−2 (dc )−1 ∈ T (or f2ℓ−2 (dc ) is undefined if
ℓ = 1) and f2ℓ−1 (dc )−1 ∈ C. Define σ(c) := f2ℓ−2 (dc )−1 if f2ℓ−2 (dc )−1 ∈ C and
σ(c) := f2ℓ−1 (dc )−1 if f2ℓ−1 (dc )−1 ∈ C. Since T is a finite tree, such a path h(c)
exists, |h(c)| ≥ 0, σ(c) 6= c, and ϕ(h(c))  1. In addition, the equality ϕ(h(c)) = 1
implies that h(c) = {c+ }, σ(c) = f1 (c)−1 and θ(σ(c)) = θ(f1 (dc )) < θ(e1 (dc )) =
θ(c). As above, we remark that h(c)− , h(c)+ are primary vertices of c, σ(c), resp.,
and h(c) = hT (c)σ(c)−εσ(c) , where hT (c) is in T with hT (c)− = c+ , hT (c)+ = σ(c)+ ,
and εσ(c) = 1 if σ(c)+ is secondary and εσ(c) = 0 if σ(c)+ is primary.

10

S. V. IVANOV

Let us summarize. For every c ∈ C, we have defined an edge σ(c) ∈ C, σ(c) 6= c,
hence, σ : C → C is a function. Furthermore, there is a reduced path h(c) such that
h(c) = cεc hT (c)σ(c)−εσ(c) , where hT (c) is in T with hT (c)− = c+ , hT (c)+ = σ(c)+ ,
εc = 1 if c+ ∈ VS Ψ and εc = 0 if c+ ∈ VP Ψ. In addition, εσ(c) = 1 if σ(c)+ ∈ VS Ψ
and εσ(c) = 0 if σ(c)+ ∈ VP Ψ. Also, ϕ(h(c))  1 and ϕ(h(c)) = 1 implies that
h(c) = {c+ } = {σ(c)+ } and θ(c) > θ(σ(c)). Finally, h(c)− , h(c)+ are primary
vertices of c, σ(c), resp., whence h(c)+ = h(σ(c))− for every c ∈ C.
Since C is finite, there is a cycle c, σ(c), . . . , σ k (c) = c, k ≥ 2, for some c ∈ C.
Consider the closed path pc = h(c)h(σ(c)) . . . h(σ k−1 (c)). Since ϕ(h(σ j (c)))  1 for
every j, we obtain that ϕ(pc )  1 and the equality ϕ(pc ) = 1 implies ϕ(h(σ j (c))) =
1 and h(σ j (c)) = {σ j (c)+ } for every j. On the other hand,
pc = cεc hT (c)σ(c)−εσ(c) σ(c)εσ(c) hT (σ(c))σ 2 (c)−εσ2 (c) . . .
σ k−1 (c)εσk−1 (c) hT (σ k−1 (c))σ k (c)−εσk (c) = cεc hT (c)hT (σ(c)) . . . hT (σ k−1 (c))c−εc
following from σ k (c) = c. Since hT (c)hT (σ(c)) . . . hT (σ k−1 (c)) is a closed path in
the tree T , we have ϕ(pc ) = 1 in F. Therefore, h(σ j (c)) = {σ j (c)+ } = {σ(c)+ } and
θ(σ j (c)) > θ(σ j+1 (c)) for every j = 0, 1, . . . , k − 1, implying θ(c) > θ(σ k (c)) = θ(c).
This contradiction completes the proof.

Proof of Theorem 1. As in Sect. 2, consider a finite irreducible A-graph Ψ(H1 , H2 )
whose connected components correspond to core graphs of subgroups H1 ∩ sH2 s−1 ,
s ∈ S(H1 , H2 ). Without loss of generality, we may assume that −χ(Ψ(H1 , H2 )) > 0.
Let D be the set of all maximal edges in Ψ(H1 , H2 ). It is easy to see from the definitions that if d ∈ D, then τi (d) is maximal in Ψoi (Hi ), i = 1, 2. Hence, τi (D) ⊆ Di ,
where Di is the set of maximal edges of Ψoi (Hi ), i = 1, 2. By Lemma 8, Di is good
for Ψoi (Hi ) and it follows from Lemma 3 and definitions that
r̄(H1 , H2 ) = |D| ≤ |τ1 (D)| · |τ2 (D)| ≤ |D1 | · |D2 | = r̄(H1 ) · r̄(H2 ),
as desired.


5. The Free Group Case

Suppose H1 , H2 are finitely generated subgroups of a free group F = F (A),
where A = {a1 , . . . , am } is a set of free generators of F . Let F (a, b) be a free
group of rank 2 with free generators a, b. Note that the map µ : ai → ai bi a−i b−i ,
i = 1, . . . , m, extends to a monomorphism µ : F (A) → F (a, b) such that µ(H1 ),
µ(H2 ) are factor-free subgroups of the free product F (a, b) = A ∗ B, where A =
hai, B = hbi are infinite cyclic groups generated by a, b. We may assume that
µ(S(H1 , H2 )) ⊆ S(µ(H1 ), µ(H2 )). Since a cyclic group is left ordered, it follows
from Theorem 1 that
X
X
r̄(µ(H1 ) ∩ tµ(H2 )t−1 )
r̄(H1 ∩ sH2 s−1 ) ≤
r̄(H1 , H2 ) =
s∈S(H1 ,H2 )

t∈S(µ(H1 ),µ(H2 ))

≤ r̄(µ(H1 ))r̄(µ(H2 )) = r̄(H1 )r̄(H2 ).

(6)

We remark that there is a more direct way to prove the inequality (6) by repeating
verbatim the arguments of Sect. 4 with a few changes in basic definitions. To do this,
±1 ±1
consider a graph U with V U = {oP , oS } and EU = {a±1
1 , a2 , a3 }, where (aj )− =
oP and (aj )+ = oS , j = 1, 2, 3. The fundamental group F2 = π1 (U, oP ) of U at
−1
−1
−1
oP is free of rank 2, and F2 = ha1 a−1
2 , a1 a3 i is freely generated by a1 a2 , a1 a3 .
Let H1 , H2 be finitely generated subgroups of F2 , Xi be the Stallings graph of

INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS

11

Hi , i = 1, 2, and W be the core of the pullback X1 × X2 of X1 , X2 over U , see
U

[18]. If Q ∈ {X1 , X2 , W, U }, there is a canonical graph map ϕQ : Q → U which is
locally injective and which we call labeling. If v ∈ V Q and ϕQ (v) = oP , v is called
primary. If ϕQ (v) = oS , v is secondary. The image ϕQ (e) = a±1
is the label of an
j
edge e ∈ EQ and θ(e) := j ∈ {1, 2, 3} = I is the type of e. With this terminology,
the definitions and arguments of Sect. 4 for graphs Q, W , X1 , X2 and the group
F2 in place of Ψ, Ψ(H1 , H2 ), Ψo1 (H1 ), Ψo2 (H2 ) and F, resp., are retained.
References
[1]
[2]
[3]
[4]
[5]
[6]

[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]

Y. Antolı́n, A. Martino, and I. Schwabrow, Kurosh rank of intersections of subgroups of free
products of right-orderable groups, preprint, http://arxiv.org/abs/1109.0233v3
W. Dicks, Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated
graph conjecture, Invent. Math. 117(1994), 373–389.
W. Dicks, Simplified Mineyev, preprint, http://mat.uab.cat/∼dicks/SimplifiedMineyev.pdf
W. Dicks and S. V. Ivanov, On the intersection of free subgroups in free products of groups,
Math. Proc. Cambridge Phil. Soc. 144(2008), 511–534.
W. Dicks and S. V. Ivanov, On the intersection of free subgroups in free products of groups
with no 2-torsion, Illinois J. Math. 54(2010), 223–248.
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(2014),
no. 1100. xii+106 pp.
S. V. Ivanov, On the intersection of finitely generated subgroups in free products of groups,
Internat. J. Algebra and Comp. 9(1999), 521–528.
S. V. Ivanov, Intersecting free subgroups in free products of groups, Internat. J. Algebra
and Comp. 11(2001), 281–290.
S. V. Ivanov, On the Kurosh rank of the intersection of subgroups in free products of groups,
Adv. Math. 218(2008), 465–484.
S. V. Ivanov, A property of groups and the Cauchy-Davenport theorem, J. Group Theory
13(2010), 21–39.
S. V. Ivanov, Linear programming and the intersection of free subgroups in free products of
groups, submitted.
V. M. Kopytov and N. Y. Medvedev, Right ordered groups, Plenum Publ., New York, 1996.
A. G. Kurosh, The theory of groups, Chelsea, 1956.
R. C. Lyndon and P. E. Schupp, Combinatorial group theory, Springer-Verlag, 1977.
I. Mineyev, Submultiplicativity and the Hanna Neumann conjecture, Ann. Math. 175(2012),
393–414.
H. Neumann, On the intersection of finitely generated free groups, Publ. Math. 4(1956),
186–189; Addendum, Publ. Math. 5(1957), 128.
W. D. Neumann, On the intersection of finitely generated subgroups of free groups, Lecture
Notes in Math. (Groups-Canberra 1989) 1456(1990), 161–170.
J. R. Stallings, Topology of finite graphs, Invent. Math. 71(1983), 551–565.

Department of Mathematics, University of Illinois, Urbana, IL 61801, U.S.A.
E-mail address: ivanov@illinois.edu

