arXiv:1609.06288v2 [] 15 Nov 2017

NO POSITIVE CONE IN A FREE PRODUCT IS REGULAR
SUSAN HERMILLER AND ZORAN ŠUNIĆ
Abstract. We show that there exists no left order on the free product
of two nontrivial, finitely generated, left-orderable groups such that the
corresponding positive cone is represented by a regular language. Since
there are orders on free groups of rank at least two with positive cone
languages that are context-free (in fact, 1-counter languages), our result
provides a bound on the language complexity of positive cones in free
products that is the best possible within the Chomsky hierarchy. It
also provides a strengthening of a result by Cristóbal Rivas which states
that the positive cone in a free product of nontrivial, finitely generated,
left-orderable groups cannot be finitely generated as a semigroup. As
another illustration of our method, we show that the language of all
geodesics (with respect to the natural generating set) that represent
positive elements in a graph product of groups defined by a graph of
diameter at least 3 cannot be regular.

1. Introduction
1.1. Basic definitions, background, and notation. A total left order
on a group G is a total order ≤ on G compatible with left multiplication;
that is, g ≤ g′ implies hg ≤ hg′ for all g, g′ , h ∈ G. Throughout this paper
we assume that all group orders are total left orders (and we will not use
the adjectives total or left again).
A group G is called orderable if G admits an order. Saying that (G, ≤)
is an ordered group means that we consider the group G along with some
specific order ≤ on G.
The positive cone of an ordered group (G, ≤) is the set G+ = {g ∈ G |
e < g} of positive elements with respect to ≤. The positive cone is a
subsemigroup of G and G is partitioned as G = G+ ⊔ {e} ⊔ G− , where e is
the identity element of G and G− = (G+ )−1 is the set of negative elements
in G.
Let X be a finite set of symbols and φ : X ∗ → G a surjective homomorphism from the free monoid X ∗ to the group G. We sometimes suppress φ
from the notation and denote φ(w) by w and φ(L) by L.
A language over X is a subset L ⊂ X ∗ . Let λ denote the empty word. The
class of regular languages over X is the closure of the finite languages under
2010 Mathematics Subject Classification. 20E06, 06F15, 68Q45.
Key words and phrases. left-orderable groups, free products, graph products, regular
languages.
1

2

SUSAN HERMILLER AND ZORAN ŠUNIĆ

the operations of finite union, finite intersection, complementation, concatenation, and Kleene star. Regular languages are the languages accepted by
finite state automata. The reverse of any regular language is regular, and
for any finite set Y and monoid homomorphism α : X ∗ → Y ∗ the image
α(L) of any regular language L over X is a regular language over Y .
We say that a language L ⊆ X ∗ represents a subset S of G if φ(L) = S.
A subset S of G represented by a regular language is often called a rational
subset of G. A language over X that represents the positive cone G+ of an
ordered group (G, ≤) is called a positive cone language for (G, ≤) over X
(and with respect to φ).
1.2. Regular positive cones. We are interested in the question of which
finitely generated groups admit a representation of a positive cone by a
regular language. Several examples of such groups have been shown to
exist.
As a first example, note that there are orders on Z2 that have a regular positive cone language. Indeed, let X = hx, y, x−1 , y −1 i. The regular
language
{xn y m | n ≥ 1, m ∈ Z} ∪ {y m | m ≥ 1}
represents the positive cone of the “lexicographic order” on Z2 = hx, yi.
Both the Dehornoy order [Deh94] and the Dubrovina-Dubrovin order [DD01]
on the braid group Bn , with n ≥ 3, admit positive cone languages that are
regular. Moreover, the positive cone for the latter is finitely generated as a
semigroup.
Rourke and Wiest [RW00] provided regular positive cone languages for
certain orders on mapping class groups of compact surfaces with a finite
number of punctures and non-empty boundary.
On the negative side, Calegari [Cal03] showed that no hyperbolic 3manifold group admits a positive cone language that is simultaneously regular and geodesic. His argument applies only to languages consisting of
(quasi-)geodesics because it uses the fact that hyperbolic 3-manifold groups
contain quasi-geodesically embedded copies of the free group of rank 2. Note
that the issue is subtle, since groups admitting regular positive cone languages may contain free subgroups. Indeed, braid groups along with the
Dehornoy orders and the Dubrovina-Dubrovin orders provide such examples.
1.3. The main result. It is well known that the free product of two orderable groups is orderable [Vin49]. Rivas [Riv12] showed that the space
of all orders on a free product G = A ∗ B, where A and B are nontrivial,
finitely generated, orderable groups, is uncountable and has the structure of
a Cantor set. Navas [Nav10] pointed out that, in the case of the free group
Fk of finite rank k, k ≥ 2, the same conclusion follows from the earlier work
of McCleary [McC85], and also provided another proof in this case. In our

NO POSITIVE CONE IN A FREE PRODUCT IS REGULAR

3

main result we show that, despite such an abundance of available orders, a
positive cone language in a free product is never regular.
Theorem 1. Let A and B be two nontrivial, finitely generated, orderable
groups. There exists no order on G = A ∗ B such that its positive cone is
represented by a regular language (for any finite alphabet X, any homomorphism φ : X ∗ → G, and any choice of a language representing the positive
cone).
The orders defined on free groups Fk in [Šun13a, Šun13b] have context-free
positive cone languages. More specifically, the sets of freely reduced words
representing the elements in their positive cones are 1-counter languages
(the stack of the push-down automaton uses a one-letter alphabet). In light
of Theorem 1, it follows that the orders on Fk from [Šun13a, Šun13b] are,
at least from the language theoretic point of view, among the simplest ones
possible in the context of free products.
1.4. Other results and remarks. The main result immediately provides
the following corollary.
Corollary 2. Let A and B be two nontrivial, finitely generated, orderable
groups. There exists no order on G = A ∗ B such that its positive cone is
finitely generated as a semigroup.
This corollary was already established by Rivas [Riv12] by using a very
different approach. In particular, Linnell [Lin06], [Nav10, Proposition 1.8]
observed that if a positive cone on a finitely generated group G is a finitely
generated semigroup, then the corresponding order is isolated in the space
of all orders. Since the space of orders on G = A ∗ B has no isolated
points [Riv12], no order on G has a finitely generated positive cone. This
is an excellent approach, but it seems that, in general, it is not easy to
establish that there are no isolated points in the space of orders of some
group (including the case of the free group). Also, the “no isolated points”
approach is not helpful in establishing stronger results in the spirit of Theorem 1. Namely, the space of orders on Z2 is a Cantor set, but, as we
already mentioned, there are orders on Z2 that have a regular positive cone
language.
Another approach to Corollary 2 is provided by Kielak [Kie15] who proved
that a finitely generated group with infinitely many ends cannot be a fraction
group of a proper, finitely generated subsemigroup.
The proof of Theorem 1 is based on the following lemma.
Lemma 3. Let (G, ≤) be a finitely generated ordered group and let L ⊆
X ∗ be a language representing the positive cone G+ . Denote by P ref (L)
the language of prefixes of the words in L. If there exists a set of positive
elements T in G such that T is unbounded (with respect to ≤) from above
and
T −1 ⊆ P ref (L),

4

SUSAN HERMILLER AND ZORAN ŠUNIĆ

then L is not regular.
In our next result we consider graph products of groups which contain subgroups that are free products of pairs of vertex subgroups. (In the following
we use the convention that edges of the defining graph represent commuting relations). The graph product construction preserves many properties
of groups; for example, Chiswell [Chi12] has shown that graph products
preserve orderability, and Loeffler, Meier and Worthington [LMW02] have
shown that the graph product preserves regularity of the set of all geodesics,
using the union of the vertex group generating sets. One important family
of graph products is the class of right-angled Artin groups, which are graph
products of cyclic groups of infinite order; in their case both the language of
geodesics and the language of all geodesics representing elements in the positive cone are regular for each vertex group. In order to illustrate that the
applicability of Lemma 3 goes beyond free products, we modify the proof of
Theorem 1 to show that regularity of the geodesic positive cone languages
of orders on the vertex groups cannot be preserved in the graph product
for graphs of diameter at least 3, when using the same union of the vertex
group generating sets.
Theorem 4. Let Γ be a finite, simple graph of diameter at least 3 and V
its vertex set. For each v ∈ V let Gv be a nontrivial, orderable group with
generating set Yv for a finite set Yv , and let X = ⊔v∈V (Yv ⊔ Yv−1 ). Let GΓ
be the associated graph product group, and suppose that φ : X ∗ → GΓ has
the property that φ(x−1 ) = φ(x)−1 for all x ∈ X. Let Geo be the language
of all geodesics for GΓ with respect to X. There exists no order ≤ on GΓ
such that the positive cone language
Geo+ = { w ∈ Geo | w represents a positive element in GΓ }
is regular.
Remark 5. Let X = Y ⊔Y −1 , for some finite set Y , and let φ : X ∗ → G be a
homomorphism such that φ(x−1 ) = φ(x)−1 for all x ∈ X. Let L+ ⊆ X ∗ be a
regular language representing the positive cone in the ordered group (G, ≤).
Since the homomorphic image of the reverse of a regular language is regular,
the language (L+ )−1 of formal inverses of the words in L+ is also regular, and
hence the union L = L+ ⊔ {λ} ⊔ (L+ )−1 is a regular language representing
the entire group G (i.e., φ(L) = G). Thus, every regular language L+ over
X representing the positive cone G+ is induced from some regular language
L representing G, by
L+ = { w ∈ L | w represents a positive element in G }.
Using this viewpoint, Theorem 4 implies, in particular, that no regular positive cone language can be induced from the regular language of all
geodesics in a right-angled Artin group on a graph Γ, when the diameter of
the graph Γ is at least 3.

NO POSITIVE CONE IN A FREE PRODUCT IS REGULAR

5

2. Proofs
We first observe that the question of representability of a subset of a group
by a regular language is independent of the choice of the alphabet X and
the homomorphism φ : X ∗ → G.
Lemma 6. Let X and Y be two finite alphabets and φX : X ∗ → G and
φY : Y ∗ → G be two surjective homomorphisms to the finitely generated
group G. Let S be a subset of G represented by a regular language L ⊆ X ∗ .
Then there exists a regular language L′ ⊆ Y ∗ representing S.
Proof. For every letter x ∈ X, choose a word wx over Y such that φY (wx ) =
φX (x). Define a monoid homomorphism α : X ∗ → Y ∗ by α(x) = wx for
all x ∈ X. The homomorphic image α(L) is a regular language over Y
representing S.

Because of the independence on the alphabet, we can always work with
a group alphabet X = Y ⊔ Y −1 , for some finite set Y , and φ : X ∗ → G
with the property that φ(x−1 ) = φ(x)−1 for all x ∈ X. Moreover, by
Benois’ Lemma [Ben69] (see [BS10] for an exposition), we can always make
a further simplification and assume that a regular language representing a
set of elements of G lies within the set R(X) of freely reduced group words
over X.
Lemma 7 (Benois’ Lemma). Let X = Y ⊔Y −1 be a group alphabet, for some
finite set Y , and let φ : X ∗ → G be a surjective homomorphism to a group G
such that φ(x−1 ) = φ(x)−1 for all x ∈ X. Let L be a regular language over
X that represents S in G. Then there exists a regular language L′ ⊆ R(X)
representing S. Moreover, one such language is the language of freely reduced
words of the words in L.
Proof of Lemma 3. By way of contradiction, assume that L is regular and
let A be an automaton on k states accepting L.
Consider the ball B of radius k − 1 in G with respect to X. Since T is
unbounded from above, there exists an element t ∈ T that is greater (with
respect to the order ≤) than every element in B. Then t−1 ∈ T −1 , and
so there exists a word w in P ref (L) representing t−1 . Now w ∈ P ref (L)
implies that there exists a word u such that wu ∈ L. Since the word wu is
accepted by the automaton A on k states, there must be a word v of length
at most k − 1, such that the word wv is also accepted by the automaton.
Therefore e < wv = t−1 v, which implies that t < v. This is impossible since
v is an element in B.

Our proof of Theorem 1 also relies on the structure of words representing
elements in a free product. Let A and B be nontrivial groups. For each
g ∈ A ∗ B, the reduced factorization of g is the unique expression of g in
the form g = a1 b1 · · · am bm where a1 ∈ A, ai ∈ A \ {e} for all i ≥ 2,
bi ∈ B \ {e} for all i ≤ m − 1, and bm ∈ B. The nontrivial elements ai , bi
in this factorization are the syllables of g. Similarly for each word w over a

6

SUSAN HERMILLER AND ZORAN ŠUNIĆ

partitioned alphabet ZA ⊔ ZB , the ZA /ZB factorization of w is the unique
∗ , u ∈ Z ∗ \ {λ} for
expression of the form w = u1 v1 · · · un vn where u1 ∈ ZA
i
A
∗
∗
all i ≥ 2, vi ∈ ZB \ {λ} for all i ≤ n − 1, and vn ∈ ZB .
Lemma 8. Let A and B be nontrivial groups with generating sets YA and
YB , respectively, where YA and YB are finite sets, and let G = A ∗ B and
X = YA ⊔ YB ⊔ YA−1 ⊔ YB−1 . Suppose that φ : X ∗ → G has the property
that φ(x−1 ) = φ(x)−1 for all x ∈ X. If w ∈ X ∗ and φ(w) has a reduced
factorization φ(w) = a1 b1 · · · am bm , then for all i the elements of A ∗ B with
reduced factorization a1 b1 · · · ai b̂i with b̂i ∈ {bi , e} are represented by prefixes
of the word w.
Proof. We prove this for the element g ′ = a1 b1 · · · ai bi with bi 6= e; the case
that b̂i = e is nearly identical. Let ZA = YA ⊔ YA−1 and ZB = YB ⊔ YB−1 , and
write the ZA /ZB factorization of w as w = u1 v1 · · · un vn .
Another reduced factorization of φ(w) can be obtained from the product
(u1 )(v1 ) · · · (un )(vn ) by finitely many applications of the following operation:
Remove a factor uj or vj that is the trivial element, and replace the resulting
product of two contiguous factors (uj )(uk ) from the same factor group by a
single factor (uj uk ) (and similarly, replace (vj )(vk ) by (vj vk )). Since φ(w)
only admits one reduced factorization, the result of applying this operation
until no further reduction can occur is the product a1 b1 · · · am bm .
If m = n, then no instance of this operation can occur, and uj = aj and
vj = bj for all j. In this case the prefix w′ = u1 v1 · · · ui vi of w satisfies
φ(w′ ) = g ′ .
Otherwise we have m > n, and for at least one index k a trivial element uk
or vk is removed and the resulting contiguous factors from the same factor
group are combined. The syllables of φ(w) obtained from this process can
be written as aj = (uj1 · · · ujℓj ) and bj = (vj1′ · · · vj ′ ′ ) where ℓj , ℓ′j ≥ 1 and
ℓ

j

j1 < · · · < jℓj ≤ j1′ < · · · < jℓ′ ′ . In this case the prefix w′ = u1 v1 · · · ui′ ′ vi′ ′
j

of w satisfies φ(w′ ) = g ′ .

ℓ

i

ℓ

i



Proof of Theorem 1. By way of contradiction, assume that G admits an order ≤ with a regular positive cone language L.
In light of Lemma 6, we may assume that L ⊆ X ∗ , where X = YA ⊔ YB ⊔
YA−1 ⊔ YB−1 , YA and YB are finite sets, YA generates A and YB generates B,
and φ : X ∗ → G has the property that φ(x−1 ) = φ(x)−1 for all x ∈ X. In
light of Lemma 3 it is sufficient to prove that G ⊆ P ref (L).
Let g be an element of G. Since G is the free product of two nontrivial groups, there exists a letter x ∈ X such that the syllable length of gx
is strictly greater than the syllable length of g. The elements gxg −1 and
gx−1 g−1 form a pair of nontrivial, mutually inverse elements in G. Therefore, at least one of them is positive. Without loss of generality, assume that
gxg −1 is positive. There exists a word w ∈ L representing gxg −1 . By our

NO POSITIVE CONE IN A FREE PRODUCT IS REGULAR

7

choice of x, the reduced factorization of gxg −1 is the product (i.e., concatenation) of the reduced factorization of g, x, and the reduced factorization
of g −1 , and so Lemma 8 shows that there exists a prefix w′ of w that represents g. Since w′ ∈ P ref (L) and w′ = g, we see that g ∈ P ref (L). Thus,
G ⊆ P ref (L).

Proof of Theorem 4. Let t and u be vertices of Γ at distance at least 3 in
Γ. Note that this distance constraint implies that there is no vertex v of Γ
that is adjacent to both t and u.
Lemma 3 shows that it is sufficient to prove that Geo ⊆ P ref (Geo+ ).
For each vertex v of the graph Γ, let Geov denote the set of geodesic
words in the vertex group Gv over the generators Yv±1 , and let Zv be the
union of the sets Yv′ over all vertices v ′ adjacent to v in Γ. Define a monoid
homomorphism πv : X ∗ → (Yv±1 ∪ {$})∗ , where $ denotes a letter not in X,
by defining

±

a if a ∈ Yv
πv (a) := $ if a ∈ X \ (Yv± ∪ Zv± )


λ if a ∈ Zv± .
That is, the map πv records all of the occurrences of generators of Gv , as well
as all of the occurrences (replaced by $) of generators of vertex groups that
do not commute with Gv and hence do not allow letters from Gv on either
side to interact. A word w over X is a geodesic for GΓ with respect to X if
and only if for all v ∈ V , πv (w) ∈ Geov ($Geov )∗ (see, for example, [CH14,
Proposition 3.3]).
Now let w be any word in Geo. If πt (w) ends with a letter a in Yt±1 , then
we can write w = w1 aw2 such that no letter of Yu±1 lies in w2 , and so the
word πu (w) = πu (w1 )$πu (w2 ) ends with a nonempty string in $∗ . Similarly
if πu (w) ends with a letter in Yu±1 then πt (w) ends with $. By swapping the
roles of t and u if necessary, we may assume that πt (w) either ends with $
or is the empty word.
Let x ∈ Yt ∩ Geot and y ∈ Yu ∩ Geou (that is, neither x nor y is e), and let
w̃ ∈ X ∗ be the word w̃ = wxyx−1 w−1 . Then πv (w̃) = πv (w)πv (xyx−1 )πv (w)−1
where πv (w)−1 is the formal inverse of πv (w) in (Yv±1 ∪ {$})∗ , with $−1 = $,
and satisfies πv (w)−1 ∈ Geov ($Geov )∗ . If v ∈
/ {t, u}, then since v cannot be
adjacent to both t and u we have πv (xyx−1 ) = $i for some i ∈ {1, 2, 3}. For
the case that v = t, the word πt (w) ends with $, the word πt (w)−1 begins
with $, and πt (xyx−1 ) = x$x−1 ∈ Geot $Geot . And in the case that v = u
we have πu (xyx−1 ) = $y$ ∈ $Geou $. Hence for all vertices v of Γ, the image
πv (w̃) lies in Geov ($Geov )∗ , and so w̃ = wxyx−1 w−1 ∈ Geo. By symmetry,
the word wxy −1 x−1 w−1 also is in Geo.
Since wxyx−1 w−1 and wxy −1 x−1 w−1 represent a pair of nontrivial, mutually inverse elements, one of them represents a positive element, which
shows that w ∈ P ref (Geo+ ). Thus, Geo ⊆ P ref (Geo+ ).


8

SUSAN HERMILLER AND ZORAN ŠUNIĆ

Acknowledgments. We thank the referee for their knowledgeable input.
The work of the first author was supported by the National Science Foundation under Grant No. DMS-1313559.
References
[Ben69]

Michèle Benois. Parties rationnelles du groupe libre. C. R. Acad. Sci. Paris Sér.
A-B, 269:A1188–A1190, 1969.
[BS10]
Laurent Bartholdi and Pedro V. Silva. Rational subsets of groups. Available at
https://arxiv.org/abs/1012.1532, 2010.
[Cal03]
Danny Calegari. Problems in foliations and laminations of 3-manifolds. In
Topology and geometry of manifolds (Athens, GA, 2001), volume 71 of Proc.
Sympos. Pure Math., pages 297–335. Amer. Math. Soc., Providence, RI, 2003.
[Chi12]
I. M. Chiswell. Ordering graph products of groups. Internat. J. Algebra Comput., 22(4):1250037, 14, 2012.
[CH14]
Laura Ciobanu and Susan Hermiller. Conjugacy growth series and languages in
groups. Trans. Amer. Math. Soc., 366(5):2803–2825, 2014.
[Deh94] Patrick Dehornoy. Braid groups and left distributive operations. Trans. Amer.
Math. Soc., 345(1):115–150, 1994.
[DD01]
T. V. Dubrovina and N. I. Dubrovin. On braid groups. Mat. Sb., 192(5):53–64,
2001.
[Kie15]
Dawid Kielak. Groups with infinitely many ends are not fraction groups. Groups
Geom. Dyn., 9(1):317–323, 2015.
[Lin06]
Peter Linnell. The topology on the space of left orderings of a group.
http://arxiv.org/abs/math/0607470, 2006.
[LMW02] Joseph Loeffler, John Meier, and James Worthington. Graph products and
Cannon pairs. Internat. J. Algebra Comput., 12(6):747–754, 2002.
[McC85] Stephen H. McCleary. Free lattice-ordered groups represented as o-2 transitive
l-permutation groups. Trans. Amer. Math. Soc., 290(1):69–79, 1985.
[Nav10] Andrés Navas. On the dynamics of (left) orderable groups. Ann. Inst. Fourier
(Grenoble), 60(5):1685–1740, 2010.
[Riv12]
Cristóbal Rivas. Left-orderings on free products of groups. J. Algebra, 350:318–
329, 2012.
[RW00] Colin Rourke and Bert Wiest. Order automatic mapping class groups. Pacific
J. Math., 194(1):209–227, 2000.
[Šun13a] Zoran Šunić. Explicit left orders on free groups extending the lexicographic
order on free monoids. C. R. Math. Acad. Sci. Paris, 351(13-14):507–511, 2013.
[Šun13b] Zoran Šunić. Orders on free groups induced by oriented words. Available at
http://arxiv.org/abs/1309.6070, 2013.
[Vin49]
A. A. Vinogradov. On the free product of ordered groups. Mat. Sbornik N.S.,
25(67):163–168, 1949.
Department of Mathematics, University of Nebraska, Lincoln, NE 685880130, USA
E-mail address: hermiller@unl.edu
Department of Mathematics, Hofstra University, Hempstead, NY 11549,
USA
E-mail address: zoran.sunic@hofstra.edu

