# Regular left-orders on groups

Yago Antolín, Cristóbal Rivas, Hang Lu Su

###### Abstract

A regular left-order on a finitely generated group $G$ is a total, left-
multiplication invariant order on $G$ whose corresponding positive cone is the
image of a regular language over the generating set of the group under the
evaluation map. We show that admitting regular left-orders is stable under
extensions and wreath products and we give a classification of the groups
whose left-orders are all regular left-orders. In addition, we prove that a
solvable Baumslag-Solitar group $B(1,n)$ admits a regular left-order if and
only if $n\geq-1$. Finally, Hermiller and S̆unić showed that no free product
admits a regular left-order. We show that if $A$ and $B$ are groups with
regular left-orders, then $(A*B)\times\mathbb{Z}$ admits a regular left-order.

MSC 2020 classification: 06F15, 20F60, 68Q45

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries about languages and left-orderability
    1. 2.1 Review of abstract families of languages
    2. 2.2 Closure properties of families of languages
    3. 2.3 Subsets of groups described by languages
    4. 2.4 Left-orders and complexity classes
    5. 2.5 Relative left-orders
  3. 3 Lexicographic left-orders of group extensions
    1. 3.1 Lexicographic left-orders where the quotient leads
      1. 3.1.1 Polycyclic groups
      2. 3.1.2 Solvable Baumslag-Solitar groups
    2. 3.2 Lexicographic left-orders where the kernel leads
      1. 3.2.1 Wreath products
  4. 4 Groups where all positive cones are regular
    1. 4.1 Order-convex subgroups and language-convex subgroups
    2. 4.2 Groups whose left-orders are all regular
  5. 5 Ordering quasi-morphisms
    1. 5.1 Ordering quasi-morphism
    2. 5.2 Ordering quasi-morphism computable through rational transducers
    3. 5.3 Embedding theorem
  6. A Appendix: pre-images of positive cones

##  1 Introduction

A group $G$ is _left-orderable_ if there exists a total order $\prec$ on the
elements of $G$ which is invariant under left-multiplication, that is

$g\prec h\iff fg\prec fh,\qquad\forall g,h,f\in G.$

In this case, the relation $\prec$ is called a left-order. It is sometimes
easier to understand left-orders in terms of sets of elements which are
greater than the identity. Such sets are called positive cones (of the order).
A positive cone completely encodes its associated left-order and vice-versa.
Equivalently, a positive cone is a subset $P\subset G$ which is closed under
multiplication $PP\subseteq P$, and partitions $G$ as $G=P\sqcup
P^{-1}\sqcup\\{1_{G}\\}$ where the union is disjoint.

This paper discusses the computational complexity of left-orders (or
equivalently positive cones). This is a topic that has gained interest in
recent years: Darbinyan [10] and Harrison-Trainor [15] have constructed groups
with solvable word problems but no computable left-orders. Rourke and Weist
have studied the complexity of left-orders on certain mapping class groups
[29]. S̆unić [32, 33] proved the existence of one-counter left-orders and
later, with Hermiller [17], proved that S̆unić’s left-orders on free groups
are the computationally the simplest possible by showing that no positive cone
on a free product admits a regular left-order.

We are interested in finding groups that admit a computationally simple left-
order and in describing such orders. Specifically, we investigate which
finitely generated groups admit a regular left-order or, equivalently, a
regular positive cone. A positive cone $P\subseteq G$ is called regular if
there is a finite generating set $X$ of $G$ and a regular language
$\mathcal{L}\subseteq X^{*}$ such that $\mathcal{L}$ evaluates onto $P$. By a
formal language we mean a subset of a finitely generated free monoid $X^{*}$.
A formal language $\mathcal{L}\subseteq X^{*}$ is regular if it is accepted by
a finite state automaton. A finite state automaton for $\mathcal{L}$ is a
directed $X$-edge-labelled finite graph such that $\mathcal{L}$ consists of
the set of labels of paths from a fixed initial vertex to a vertex in a fixed
subset of vertices called accepted states. Positive cones which are
represented by a regular language are the simplest ones computationally from
the point of view of the Chomsky hierarchy of formal languages [9]. Section 2
will be devoted to reviewing the necessary material about formal languages and
left-orders.

In previous works, the authors have given examples of groups not admitting
regular left-orders [1, 31]. In this paper we focus instead on constructing
regular left-orders. We show that regularity of positive cones is preserved
under the constructions of the following theorem.

######  Theorem 1.1 (Propositions 2.18, 3.3 and 3.20).

The class of finitely generated groups admitting regular positive cones is
closed under passing to finite index subgroups, extensions and wreath
products.

The inheritance under passing to finite index subgroups is due to H. L. Su
[31]. The other two closure properties are proved in Section 3 where we study
left-orders associated to group extensions. A basic fact is that the group of
additive integers $\mathbb{Z}$ admits regular left-orders. Starting from this,
and the known fact that amenable left-orderable groups are locally indicable
[24], the closure under group extensions property provides the following
family of examples of groups which admit regular positive cones.

######  Corollary 1.2 (Proposition 3.7).

Left-orderable virtually polycyclic groups admit regular positive cones.

For the case of wreath products $G=N\wr Q$, we have an exact sequence
$1\to\oplus_{q\in Q}N\to G\to Q\to\\{1\\}$ but here $\oplus_{q\in Q}N$ does
not admit a regular positive cone as, in general, it is not finitely
generated. Therefore, the construction of regular left-orders on wreath
products differs from the construction for the extensions.

It is already known that one cannot expect to generalize Corollary 1.2 for
solvable non-polycyclic groups. Indeed, Darbinyan [10, Theorem 2] showed that
there is a two-generated recursively presented left-orderable solvable group
of derived length 3 with undecidable word problem (in fact, their order turns
out to be two-sided invariant). As we will see in the Appendix, this implies
that no left-order on this group is computable (i.e. described by a language
that can be recognized by a Turing machine).

In the present paper, we are able to decide when a solvable Baumslag-Solitar
group $BS(1,q)$ admits a regular positive cone or not. Recall that
$BS(1,q)=\langle a,b\mid aba^{-1}=b^{q}\rangle$ and it is isomorphic to
$\mathbb{Z}[1/q]\rtimes\mathbb{Z}$. Note that $q\in\mathbb{Z}$ and for $q=0$
we adopt the convention that $BS(1,0)=\mathbb{Z}$.

######  Theorem 1.3 (Theorem 3.14).

For all $q\in\mathbb{Z}$, the solvable Baumslag-Solitar group $BS(1,q)$ admits
a one-counter left-order. Moreover, $BS(1,q)$ admits a regular left-order if
and only if $q\geq-1$.

The class of one-counter languages generalizes the class of regular languages.
These are languages that can be recognized by finite state automaton (the same
machine as for regular languages) equipped with a very simple memory which
consists on a stack that contains copies of the same letter (the counter). The
machine, depending on the input and whether the stack is empty or not, can
modify the stack by adding or removing a counter from the stack. See Section 2
for a formal definition.

From this theorem, we observe that while the existence of regular of left-
orders passes to finite index subgroups (Theorem 1.1), it is not true that it
passes to finite-index overgroups (even if the overgroup is left-orderable).
Indeed, $BS(1,-2)$ is a left-orderable group that does not admit any regular
left-order but contains $BS(1,4)$ as an index 2 subgroup that does admit
regular left-orders. Therefore, admitting a regular order is not a property
preserved by commensurability among left-orderable groups.

The reason why $BS(1,q)$ for $q<-1$ does not admit regular positive cones is a
combination of an algebraic argument and a geometric argument. The algebraic
argument goes back to Tararin [34] (see also [28]) and describes all possible
left-orders in these groups. The geometric argument uses Bieri-Neumann-Strebel
theory [7] and implies that positive cones associated to the orders described
by Tararin are not coarsely connected (see Definition 3.9) which is a
necessary condition for regularity (see Lemma 3.10).

We will use Tararin’s classification [34] of groups admitting finitely many
left-orders to describe the groups admitting only regular left-orders. More
precisely, in Section 4 we prove the following theorem.

######  Theorem 1.4 (Theorem 4.9).

A finitely generated group $G$ admits only regular left-orders if and only if
it is Tararin poly-$\mathbb{Z}$, that is, it admits a unique subnormal series

$G=G_{0}\unrhd G_{1}\unrhd\dots\unrhd G_{n}=\\{1\\}$

where $G_{i}/G_{i+1}\cong\mathbb{Z}$ and $G_{i}/G_{i+2}\cong K=\langle a,b\mid
aba^{-1}=b^{-1}\rangle$.

Finally, the last construction that preserves left-orderability that we will
discuss are free products [26]. We know from the work of Hermiller and S̆unić
that no non-trivial free product (in particular free groups) admits a regular
positive cone. One might think that then it is helpless to pursue this route,
however we have the following.

######  Theorem 1.5 (Corollary 5.15).

Suppose that $A$ and $B$ are groups admitting regular left-orders. Then
$(A*B)\times\mathbb{Z}$ admits a regular left-order.

This sort of phenomenon was already observed in [31], where H.L. Su found a
finitely generated positive cone for $F_{2}\times\mathbb{Z}$ (and hence a
regular positive cone). In Section 5 we prove Theorem 1.5 and give an
explanation of the role of the factor $\mathbb{Z}$. To do so, we will define
the concept of an ordering quasi-morphism. A quasi-morphism on $G$ is a map
$\phi\colon G\to\mathbb{R}$ that is close to a homomorphism in the sense that
there is a constant $R$ such that $|\phi(g)+\phi(h)-\phi(gh)|\leq R$. An
ordering quasi-morphism $\phi$ (Definition 5.5) has the property that elements
whose image under $\phi$ is positive form a (relative) positive cone (see
Definition 2.19. This will allow to construct a left-order on the group, as we
will see.

While we coin the name of ordering quasi-morphism in this paper, the original
idea comes from the work of S̆unić [32, 33] about orders on free groups, Dicks
and S̆unić [11] about orders on free products and Antolín, Dicks and S̆unić
[3] about orders on certain fundamental groups of graph of groups. We show
that when the ordering-quasimorphism can be computed with a transducer
(another type of machine similar to a finite state automaton, see Definition
2.8) the corresponding left-order is one-counter. More precisely, our chosen
function $\phi$ has image $\mathbb{Z}$, and when embedding $G$ in
$G\times\mathbb{Z}$, we use the $\mathbb{Z}$ factor to compensate the
increments/decrements in $\phi$ so that we no longer need a stack to keep
track of the value of $\phi$ on the elements of $G$, hence constructing the
desired regular left-order on $G\times\mathbb{Z}$.

One of the motivations for studying left-orders on free products is to get a
better understanding of the influence of negative curvature on the complexity
of positive cones. In particular, we are interested in the following.

######  Question 1.6.

Is there a non-elementary hyperbolic group admitting a regular positive cone?

This question has some history. Hermiller and S̆unić [17] proved that non-
abelian free groups do not admit regular positive cones. Su [31] proved that
acylindrically hyperbolic groups do not have positive cones that are quasi-
geodesic and regular. This formalized and strengthened an argument sketched by
Calegari [8]. Finally, Alonso, Antolín, Brum and Rivas [1] proved that non-
abelian limit groups (in particular free groups and surface groups) do not
admit coarsely connected positive cones, and therefore do not admit regular
positive cones.

Nevertheless, if $G$ is hyperbolic (finitely generated free)-by-$\mathbb{Z}$,
then the Bieri-Neumann-Strebel theory guarantees that $G$ admits coarsely
connected left-orders (see discussion before Lemma 3.11). Thus, one might
initially think that those left-orders on hyperbolic (f.g.
free)-by-$\mathbb{Z}$ groups might be regular. As a consequence of the methods
developed to prove Theorem 1.5 we get that this is almost the case.

######  Theorem 1.7 (Theorem 5.17).

Let $G$ be (finitely generated free)-by-$\mathbb{Z}$ group. Then
$G\times\mathbb{Z}$ admits a regular positive cone, whose restriction to $G$
is coarsely connected, one-counter, but not regular.

We conclude Section 5 showing that certain Artin groups admit regular positive
cones.

Finally, we close the paper with an appendix. Let $X$ be finitely generating
set of a group $G$ and $\pi\colon X^{*}\to G$ be a monoid surjection. If $P$
is a positive cone, one can ask about the complexity of $\pi^{-1}(P)$ as a
formal language, which is in more direct analogy with studying formal
languages with the Word Problem. We explore this question for regular and
context-free languages (the lowest ones in the Chomsky hierarchy), and show
that there are extremely few examples of such left-orders (for instance, it is
never the case that the language of preimages of a positive cone is regular).
This gives partial justification as to why we have focus on our definition of
regular positive cones.

##  2 Preliminaries about languages and left-orderability

In this section we review some formal language theory needed in the paper,
focusing on the classes of regular and context-free languages. We also review
the definition of left-orderability and we explain what we mean by a regular
or context-free left-order on a group. Most of the content of this section is
standard or well-known and the main purpose is to set the notation and the
definitions for the rest of the paper.

###  2.1 Review of abstract families of languages

By a formal language we refer to a subset of $\mathcal{L}$ of $X^{*}$, where
$X$ is a finite set and $X^{*}$ denotes the set of all finite sequences over
$X$, also called words. We denote the empty word by $\epsilon$. Note that
$X^{*}$ is a monoid with respect to concatenation. We denote by $X^{+}$ the
set $X^{*}\setminus\\{\epsilon\\}$, which is a semi-group with concatenation.

A non-deterministic finite state automaton is a 5-tuple
$\mathbb{M}=(\mathcal{S},X,\delta,s_{0},\mathcal{A})$, where $\mathcal{S}$ is
a finite set whose elements are called states, $\mathcal{A}$ is a subset of
$\mathcal{S}$ of whose states are called accepting states, $s_{0}$ is a
distinguished element of $\mathcal{S}$ called initial state, $X$ is a finite
set called the input alphabet, and
$\delta\colon\mathcal{S}\times(X\sqcup\\{\epsilon\\})\to\textrm{Subsets}(\mathcal{S})$
is a function called the transition function.

We extend $\delta$ to a function
$\delta\colon\mathcal{S}\times(X\sqcup\\{\epsilon\\})^{*}\to\textrm{Subsets}(\mathcal{S})$
recursively, by setting
$\delta(s,wx)=\cup_{\sigma\in\delta(s,w)}\delta(\sigma,x)$ where $w\in X^{*}$,
$x\in X$ and $s\in\mathcal{S}$. A language $\mathcal{L}$ is regular if there
is a non-deterministic finite state automaton $\mathbb{M}$ such that

$\mathcal{L}=|\mathbb{M}|:=\\{w\in
X^{*}\mid\delta(s_{0},w)\cap\mathcal{A}\neq\emptyset\\}.$

We denote by $\mathsf{Reg}$ the class of all regular languages.

The outputs of $\delta$ under input $\epsilon$ should be thought as the
machine acting spontaneously. Images with input $\epsilon$ are usually called
$\epsilon$-moves or $\epsilon$-transitions. Informally, the machine
$\mathbb{M}$ at a certain step is at a state $s\in\mathcal{S}$ and can change
to another state $s^{\prime}\in\mathcal{S}$ either because it reads some $x\in
X$, and $s^{\prime}\in\delta(s,x)$ or is at state $s^{\prime}$ spontaneously,
meaning that $s^{\prime}\in\delta(s,\epsilon)$.

######  Remark 2.1.

The class $\mathsf{Reg}$ coincides with the class of languages accepted by
non-deterministic finite state automata without $\epsilon$-moves, and even
with the class of languages accepted by deterministic finite state automata
(See [19, Chapter 2]). Deterministic automata do not have $\epsilon$-moves and
in that setting $\delta(s,x)$ is always a singleton. Depending on our needs,
we will choose to allow $\epsilon$-moves or not (therefore choosing whether we
impose determinism).

######  Remark 2.2.

A finite state automaton $\mathbb{M}$ can be regarded as a labelled directed
graph. The vertices are the states of the automaton, and edges are given by
the transition function $\delta$. There is an edge from $s\in\mathcal{S}$ to
$s^{\prime}\in\mathcal{L}$ labeled by $x\in X\sqcup\\{\epsilon\\}$ if and only
if $s^{\prime}\in\delta(s,x)$. A word $w$ is accepted by $\mathbb{M}$ if it is
a label of a path from $s_{0}$ to some accepting state $\mathcal{A}$.

######  Notation 2.3.

Given a word $w\in X^{*}$, and $x\in X$, we use $\sharp_{x}(w)$ to denote the
number of times the letter $x$ appears in the word $w$.

######  Example 2.4.

Let $\mathbb{M}$ be the finite state automaton given in Figure 1. The
automaton is described as a graph following Remark 2.2.

$s_{0}$
---
$t$
---
$t$
---
$t$
---
$t$
---
$t$
---
$t$
---
$t$
---
$t$
---
$t^{-1}$
---
$t^{-1}$
---
$t^{-1}$
---
$t^{-1}$
---
$t$
---
accepting states
---
Figure 1: Finite state automaton accepting the language of Example 2.4.

The language accepted by $\mathbb{M}$ in Figure 1, consists on all the $w$ in
$\\{w\in\\{t^{-1},t\\}^{*}\mid\sharp_{t}(w)\geq\sharp_{t^{-1}}(w)\\}$ such
that for all subword $u$ of $w$, $\sharp_{t}(u)-\sharp_{t^{-1}}(u)\geq-2$
holds.

A (non-deterministic) pushdown automaton is a 7-tuple
$\mathbb{M}=(\mathcal{S},X,\Sigma,\delta,s_{0},u_{0},\mathcal{A})$, where
$\mathcal{S}$ is a finite set whose elements are called states, $\mathcal{A}$
is a subset of $\mathcal{S}$ whose states are called accepting states,
$s_{0}\in\mathcal{S}$ is a distinguished element called initial state, $X$ is
a finite set called the input alphabet, $\Sigma$ is a finite set called the
stack alphabet, $u_{0}$ is a distinguished word over $\Sigma$ called the
initial stack, and $\delta$ is a non-deterministic transition function

$\delta\colon\mathcal{S}\times(X\sqcup\\{\epsilon\\})\times(\Sigma\sqcup\\{\epsilon\\})\to\textrm{Finite
subsets of }(\mathcal{S}\times\Sigma^{*}).$

The pushdown automaton $\mathbb{M}$ at each stage of the computation is at a
certain state and contains a certain word over $\Sigma$ which we call stack
word. At the start stage, the state is $s_{0}$ and the stack word is $u_{0}$.
To describe how the stack words change, it is convenient to extend $\delta$ so
we allow stack words (and not only stack letters) as inputs. The behavior of
$\mathbb{M}$ will depend only on the last letter $\sigma$ of the stack word
(if the stack word is empty we take $\sigma=\epsilon$). Precisely, we extend
$\delta$ to a function
$\delta\colon\mathcal{S}\times(X\sqcup\\{\epsilon\\})\times\Sigma^{*}\to\textrm{Finite
subsets of }(\mathcal{S}\times\Sigma^{*})$, where if we write $w=u\sigma$ with
$\sigma\in\Sigma$, then
$\delta(s,x,w)=\\{(s^{\prime},uu^{\prime})\mid(s^{\prime},u^{\prime})\in\delta(s,x,\sigma)\\}$.
Note that $\delta$ on input word $w=u\sigma\in\Sigma^{*}$ operates by deleting
$\sigma$ and appending $u^{\prime}$ to the end to get the word $uu^{\prime}$
as output.

As in the case of finite state automata, we extend $\delta$ to a function
$\delta\colon\mathcal{S}\times(X\sqcup\\{\epsilon\\})^{*}\times\Sigma^{*}\to\textrm{Finite
subsets of }(\mathcal{S}\times\Sigma^{*})$ recursively.

A language $\mathcal{L}$ is context-free if there is a non-deterministic
pushdown automaton such that

$\mathcal{L}=|\mathbb{M}|:=\\{w\in
X^{*}\mid\exists(s,u)\in\delta(s_{0},w,u_{0})\text{ with }s\in\mathcal{A}\\}.$

We denote by $\mathsf{CF}$ the class of all context-free languages.

A language $\mathcal{L}$ is one-counter if there is a non-deterministic
pushdown automaton with $|\Sigma|=1$ and such that $\mathcal{L}=|\mathbb{M}|$.
The class of one-counter languages will be denoted by $\mathsf{1C}$.

######  Remark 2.5.

In many computer science books, they use a model of pushdown automaton that
has access to a tape where they write the stack word and read the last letter
from it. In that model, the stack alphabet must include an extra symbol to
denote the blank space on the tape.

We clearly have

$\mathsf{Reg}\subseteq\mathsf{1C}\subseteq\mathsf{CF}.$

Note that $\mathsf{Reg}$ and $\mathsf{CF}$ are the simplest complexities in
the Chomsky hierarchy [9].

######  Example 2.6.

Consider the language
$\mathcal{L}=\\{w\in\\{t^{-1},t\\}^{*}\mid\sharp_{t}(w)>\sharp_{t^{-1}}(w)\\}$.
This language is in the class $\mathsf{1C}$ and will appear many times in the
paper. For completeness, we give in Figure 2 a one-counter push-down automaton
for $\mathcal{L}$ with the graphical notation found in Hopcroft, Motwani and
Ullman [19, Section 6.1.3]. The vertices of the graph represent the states of
the automaton. An arrow from state $s$ to state $s^{\prime}$ has label
$x,\alpha/\beta$, where $x\in X=\\{t,t^{-1}\\}$,
$\alpha\in\Sigma\cup\\{\epsilon\\}$ and $\beta\in\Sigma^{*}$, if and only if
$(s^{\prime},\beta)\in\delta(s,x,\alpha)$. That is, the label tells what input
is used and gives the old and new suffixes of the stack word.

$s_{0}$
---
$-$
---
$+$
---
$t,\sigma/\sigma\sigma$
---
$t^{-1},\sigma/\epsilon$
---
$t,\epsilon/\sigma$
---
$t,\epsilon/\sigma$
---
$t^{-1},\epsilon/\sigma$
---
$t^{-1},\sigma/\sigma\sigma$
---
$t,\sigma/\epsilon$
---
$t^{-1},\epsilon/\sigma$
---
Figure 2: 1-counter pushdown automaton accepting
$\mathcal{L}=\\{w\in\\{t^{-1},t\\}^{*}\mid\sharp_{t}(w)\geq\sharp_{t^{-1}}(w)\\}$.

We note that this language is not regular. This follows easily from the
pumping lemma for regular languages (see [19, Theorem 4.1]). However, the
reader not familiar with the pumping lemma will find a proof that
$\mathcal{L}$ is not regular in Lemma 4.4.

###  2.2 Closure properties of families of languages

Let $X,Y$ be finite sets. The set $X^{*}$ equipped with concatenation has the
structure of a free monoid over the set $X$.

Let $\mathcal{C}$ be a class of languages. We say that $\mathcal{C}$ is closed
under concactenation if for every $\mathcal{L},\mathcal{M}\in\mathcal{C}$ the
language $\mathcal{L}\cdot\mathcal{M}\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=\\{uv\mid u\in\mathcal{L},\,v\in\mathcal{L}\\}$
belongs to $\mathcal{C}$. Given a language $\mathcal{L}$, we denote by
$\mathcal{L}^{n}$ the concatenation of $\mathcal{L}$ with itself $n$ times,
i.e. $\mathcal{L}^{n}=\mathcal{L}\cdot\mathcal{L}\cdots\mathcal{L}$. By
$\mathcal{L}^{0}$ we denote the language with just the empty word. The Kleene
closure  of $\mathcal{L}$ is the language
$\mathcal{L}^{*}\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=\cup_{n\geq 0}\mathcal{L}^{n}$. We say that the
class $\mathcal{C}$ is closed under homomorphism if for every
$\mathcal{L}\subseteq X^{*}$ with $\mathcal{L}\in\mathcal{C}$ and every monoid
homomorphism $f\colon X^{*}\to Y^{*}$ we have that
$f(\mathcal{L})\in\mathcal{C}$. Similarly, the class is closed under inverse
homomorphism if for every $\mathcal{L}\subseteq X^{*}$ with
$\mathcal{L}\in\mathcal{C}$ and every monoid homomorphism $f\colon Y^{*}\to
X^{*}$ we have that preimage of $\mathcal{L}$ under $f$, here denoted
$f^{-1}(\mathcal{L})$, belongs to $\mathcal{C}$. Finally, the reversal or
mirror image of $\mathcal{L}\subseteq X^{*}$ is the language
$\mathcal{L}^{R}:=\\{x_{n}x_{n-1}\dots x_{1}\mid x_{1}\dots
x_{n}\in\mathcal{L}\\}$.

A class of languages is called _full abstract family of languages_ (or full
AFL for short) if it is closed under homomorphisms, inverse homomorphisms,
intersections with regular languages, unions, concatenations and Kleene
closure.

######  Proposition 2.7.

The classes $\mathsf{Reg},\mathsf{1C}$ and $\mathsf{CF}$ languages are full
AFL.

The classes $\mathsf{Reg}$ and $\mathsf{CF}$ languages are closed under
reversal.

The class $\mathsf{Reg}$ is closed under complement, but $\mathsf{CF}$ is not.

###### Proof.

All the claims are contained in either [27, Page 30] for all classes but
$\mathsf{1C}$. For $\mathsf{1C}$ the claims are contained in [4, Chapter VII
Theorem 4.4]. ∎

We introduce a last type of machines that will play an important role in the
paper.

######  Definition 2.8.

A rational transducer is a finite state automaton which can output a finite
number of symbols for each input symbol. Formally, a rational transducer is a
six-tuple $\mathbb{T}=(\mathcal{S},X,Y,\delta,s_{0},\mathcal{A})$ where
$\mathcal{S}$, $X$, and $Y$ are finite sets called the states, input alphabet,
and output alphabet, respectively. The function $\delta$ is a map from
$\mathcal{S}\times(X\sqcup\\{\epsilon\\})\to\textrm{Finite
Subsets}(\mathcal{S}\times Y^{*})$. The element $s_{0}\in\mathcal{S}$ is the
initial state and $\mathcal{A}\subseteq\mathcal{S}$ is the subset of accept
states. The interpretation of $(r,w)\in\delta(s,x)$ is that $\mathbb{T}$ in
state $s$ with input symbol $x$ may, as one possible choice of move, enter the
state $r$ and output the string $w\in Y^{*}$.

As usual, we extend recursively $\delta$ to a function $\mathcal{S}\times
X^{*}\to\textrm{Finite Subsets}(\mathcal{S}\times Y^{*})$. We have that
$(r,v)\in\delta(s,ux)$ for some $x\in X$ and $u\in X^{*}$ if there is
$(t,v^{\prime})\in\delta(s,u)$ and $(r,w)\in\delta(t,x)$ such that
$v=v^{\prime}w$.

######  Remark 2.9.

We will also use a graph representation of a transducer $\mathbb{T}$. This is
the graph associated to the underlying finite state automaton of $\mathbb{T}$,
with labels on the edges indicating the output of reading a certain input.
More precisely, if $\mathbb{T}=(\mathcal{S},X,Y,\delta,s_{0},\mathcal{A})$ is
a rational transducer, we consider a graph with vertices $\mathcal{S}$. There
is a directed edge from $s\in\mathcal{S}$ to $s^{\prime}\in\mathcal{S}$ if
$(s^{\prime},u)\in\delta(s,x)$ for some $x\in X\sqcup\\{\epsilon\\}$ and $u\in
Y^{*}$. In that case, we put a label $x/u$ on that edge. It means that we can
move along that edge from $s$ to $s^{\prime}$ if we have input $x$ and on
doing so we output the word $u$. An example of a graphical representation can
be found in Figure 7.

For $u\in X^{*}$ let $\mathbb{T}(u)\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=\\{v\in Y^{*}\mid(a,v)\in\delta(s_{0},u)\text{ and
}a\in\mathcal{A}\\}$. With this, we can define the image of
$\mathcal{L}\subseteq X^{*}$ under $\mathbb{T}$ as
$\mathbb{T}(\mathcal{L})\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=\\{\mathbb{T}(u)\mid u\in\mathcal{L}\\}$. Finally,
for $\mathcal{L}\subseteq Y^{*}$, we can define the inverse image of
$\mathcal{L}$ under $\mathbb{T}$ as the set
$\mathbb{T}^{-1}(\mathcal{L})\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=\\{u\in X^{*}\mid(a,v)\in\delta(s_{0},u)\text{ with
}a\in\mathcal{A}\text{ and }v\in\mathcal{L}\\}$.

######  Proposition 2.10.

Full AFL classes are closed under rational transducers and inverse image under
rational transducers.

###### Proof.

The inverse image of a language $\mathcal{L}$ under a rational transducer
$\mathbb{T}$, is also the image of the language under some rational transducer
$\mathbb{T}^{\prime}$ (See [4, III.4 and III.Theorem 6.1]). Nivat’s theorem
(see [4, III.Theorem 4.1 in view of III.Theorem 6.1]) says that if
$\mathbb{T}$ is a rational transducer with input alphabet $X$, output alphabet
$Y$ and $\mathcal{L}\subseteq X^{*}$ is a language, then there is a finite
alphabet $Z$, a regular language $\mathcal{R}\subseteq Z^{*}$ and
homomorphisms $f\colon Z^{*}\to X^{*}$ and $h\colon Z^{*}\to Y^{*}$ such that
$\mathbb{T}(\mathcal{L})=h(f^{-1}(\mathcal{L})\cap\mathcal{R})$. Now it
follows that full AFL classes are closed under rational transducers. ∎

###  2.3 Subsets of groups described by languages

Let $G$ be a group. A (monoid) generating set for $G$ is a set $X$ together
with a surjective monoid homomorphism map $\pi\colon X^{*}\to G$. If $\pi$ is
known (for example if $X$ is a subset of $G$) we often just say that $X$ is a
generating set. We refer to images under $\pi$ as evaluations.

We will use $\ell(w)$ to denote the length of a word $w\in X^{*}$. For an
element $g\in G$, we set $|g|_{X}=\min\\{\ell(w)\mid\pi(w)=g\\}$. For $g,h\in
G$, the word distance between $g$ and $h$, is equal to $|g^{-1}h|_{X}$ and is
denoted by $\operatorname{d}_{X}(g,h)$. We might drop the subscript X if the
generating set is clear from the context.

The next lemma is standard and the proof is omitted.

######  Lemma 2.11.

Let $\mathcal{C}$ be a class of languages closed under homomorphisms and
inverse homomorphism. Let $(X,\pi_{X})$ and $(Y,\pi_{Y})$ be two finite
generating sets of a group $G$. Let $S\subseteq G$ be any subset.

  1. 1.

There is a language $\mathcal{L}_{X}\subseteq X^{*}$ in the class
$\mathcal{C}$ such that $\pi_{X}(\mathcal{L}_{X})=S$ if and only if there is a
language $\mathcal{L}_{Y}\subseteq Y^{*}$ in the class $\mathcal{C}$ such that
$\pi_{Y}(\mathcal{L}_{Y})=S$.

  2. 2.

There is a language $\mathcal{L}_{X}\subseteq X^{*}$ in the class
$\mathcal{C}$ such that $\mathcal{L}_{X}=\pi_{X}^{-1}(S)$ if and only if there
is a language $\mathcal{L}_{Y}\subseteq Y^{*}$ in the class $\mathcal{C}$ such
that $\mathcal{L}_{Y}=\pi_{Y}^{-1}(S)$.

The following observation will be useful.

######  Lemma 2.12.

Let $(X,\pi)$ be a finite generating set of $G$ and $P\subset G$. Let
$\mathcal{C}$ be a class of languages closed by homomorphisms, inverse
homomorphisms and reversal. Then

  1. (i)

there is a language $\mathcal{L}\in\mathcal{C}$ such that $\pi(\mathcal{L})=P$
if and only there is a language $\mathcal{L}^{\prime}\in\mathcal{C}$ such that
$\pi(\mathcal{L}^{\prime})=P^{-1}$,

  2. (ii)

$\pi^{-1}(P)\subseteq X^{*}$ is in the class $\mathcal{C}$ if and only if
$\pi^{-1}(P^{-1})\subseteq X^{*}$ is in the class $\mathcal{C}$.

###### Proof.

Since $\mathcal{C}$ is closed by homomorphisms and inverse homorphisms, Lemma
2.11 implies that the properties claimed in (i) and (ii) are independent of
the generating set. So we will assume that $X\subseteq G$ is a finite
generating set closed under taking inverses.

Let $f\colon X^{*}\to X^{*}$ be the map sending $x_{1}\dots x_{n}\mapsto
x_{n}^{-1}\dots x_{1}^{-1}$. Then $f$ is a composition of the homomorphism map
sending $x\mapsto x^{-1}$ and the reversal map. Moreover $f^{2}=id\colon
X^{*}\to X^{*}$. In particular, $\mathcal{L}\subseteq X^{*}$ is in
$\mathcal{C}$ if and only if $f(\mathcal{L})$ is in $\mathcal{C}$.

Note that we have that $P^{-1}=\pi(f(\mathcal{L}))$ and so (i) follows. Also
$\pi^{-1}(P^{-1})=f^{-1}(\pi^{-1}(P))$ and (ii) follows. ∎

We will now recall a property that allows us to pass the complexity of sets to
subsets.

######  Definition 2.13.

Let $(X,\pi)$ be a finite generating set of $G$. Let $\mathcal{L}$ be a
regular language over $X$. A subset $H\subseteq G$ is language-convex with
respect to $\mathcal{L}$ (or $\mathcal{L}$-convex for short) if there exists
an $R\geq 0$ such that for each $w\in\mathcal{L}$ with $\pi(w)\in H$, where
$w=x_{1}\dots x_{n}$ and $w_{i}=x_{1}\dots x_{i}$, all prefixes $w_{i}$ of $w$
satisfy that $\operatorname{d}(\pi(w_{i}),\pi(\mathcal{L}))\leq R$.

The following result was proved by the second author in [31, Corollary 4.4].

######  Proposition 2.14.

Let $\mathcal{L}$ be a regular language, let $(X,\pi)$ be a finite generating
set of a group $G$ and let $H$ be a subgroup of G. If $H$ is language-convex
with respect to $\mathcal{L}$, then there exists a regular language
$\mathcal{L}^{\prime}\subseteq X^{*}$ that evaluates onto
$H\cap\pi(\mathcal{L})$.

###  2.4 Left-orders and complexity classes

A left-order $\prec$ on a group $G$ is a total order on $G$ that is invariant
under left $G$-multiplication. That is, for all $a,b,c\in G$, $a\prec b$ holds
if and only if $ca\prec cb$ holds. If a left-order exists on $G$ we say that
$G$ is left-orderable. A positive cone  of $G$ is a subsemigroup $P$ of $G$
with the property that $G$ is the disjoint union of $P$, $P^{-1}$ and
$\\{1_{G}\\}$. A positive cone $P$ defines a left-order $\prec_{P}$ on $G$ by
$a\prec_{P}b\Leftrightarrow a^{-1}b\in P$. Conversely, a left-order $\prec$ on
$G$ defines a positive cone $P_{\prec}=\\{g\in G\mid 1_{G}\prec g\\}$.

A group $G$ is bi-orderable if there is a left-order $\prec$ on $G$ such that
it is also invariant under right $G$-multiplication. In that case, $\prec$ is
a bi-order.

We now link positive cones with formal languages.

######  Definition 2.15.

Let $\mathcal{C}$ be a class of languages. Let $(X,\pi)$ be a generating set
of $G$. Let $\prec$ a left-order. We say that $\prec$ is a $\mathcal{C}$-left-
order, or equivalently $P_{\prec}$ is a $\mathcal{C}$-positive cone, if there
exists a language $\mathcal{L}\subseteq X^{*}$ in the class $\mathcal{C}$ such
that $\pi(\mathcal{L})=P_{\prec}$.

######  Example 2.16.

An infinite cyclic group $G=\langle t\mid\;\rangle$ is left-orderable.
Consider the generating set $\\{t,t^{-1}\\}$ of $G$. The set $\\{t^{n}\mid
n>0\\}\subseteq G$ is a positive cone and it is easy to check that $\langle
t\rangle^{+}=\\{t^{n}\mid n>0\\}\subseteq\\{t,t^{-1}\\}^{*}$ is a regular
language. Thus $\mathbb{Z}$ admits $\mathsf{Reg}$-left-orders.

In Example 2.6, we saw that $\pi^{-1}(\mathbb{Z}_{\geq
1})=\\{w\in\\{t,t^{-1}\\}^{*}\mid\sharp_{t}(w)>\sharp_{t^{-1}}(w)\\}$ is
$\mathsf{1C}$ but not regular. Taking the full pre-image of a positive cone
under $\pi$ gives a language that represents the positive cone but it might
not be of minimal language complexity. This will be discussed in more detail
in the Appendix.

We now get some applications from the lemmata we proved for the complexity of
subsets in the previous subsection. By Lemma 2.11, we get the following
result.

######  Corollary 2.17.

Let $\mathcal{C}$ be a class of languages closed under homomorphisms (eg.
$\mathcal{C}=\mathsf{Reg}$ or $\mathcal{C}=\mathsf{CF}$). Admitting a
$\mathcal{C}$-left-order is a group property, independent of the generating
set.

Left-orders restrict to left-orders on subgroups. It is natural to ask if
their complexity is preserved. This is a subtle question. For example
$F_{2}\times\mathbb{Z}$ has a $\mathsf{Reg}$-left-order (Theorem 1.5 or [31]),
however $F_{2}$ does not have $\mathsf{Reg}$-left-orders [17].

A sufficient condition for a left-order to inherit the complexity class when
passing to a subgroups is given in terms of language-convexity (see Definition
2.13). For instance, since finite index subgroups of a finitely generated
group are always language-convex, we get the following consequence of
Proposition 2.14 (which was stated as [31, Theorem 1.1]).

######  Proposition 2.18.

A $\mathsf{Reg}$-left-order on a finitely generated group $G$ restricts to a
$\mathsf{Reg}$-left-order on any finite index subgroup.

###  2.5 Relative left-orders

We recall now some properties of relative positive cones. See [3, Definition
4] or [20, Corollary 5.1.5] for more details.

######  Definition 2.19.

Let $G$ be a group and $H$ be a subgroup of $G$. A subsemigroup $P\subseteq G$
is a positive cone relative to $H$ if $G=P\sqcup H\sqcup P^{-1}$.

Suppose that $P\subseteq G$ is a positive cone relative to $H$. Then $P\cdot
H\subseteq P$ holds. Indeed, that $P\cdot H$ has a non-trivial intersection
with $P^{-1}\cup H$ in order to derive a contradiction. If $P\cdot H\cap
P^{-1}\not=\emptyset$. Then there exists $p_{1},p_{2}\in P$ and $h\in H$ such
that $p_{1}h=p_{2}^{-1}$, meaning that $h=p_{1}^{-1}p_{2}^{-1}$, so $H$ is not
disjoint from $P^{-1}$, a contradiction. Similarly, if $P\cdot H\cap H$ is
non-empty, then there exists $h_{1},h_{2}\in H$ and $p\in P$ such that
$ph_{1}=h_{2}$, meaning that $p=h_{2}h_{1}^{-1}$, which implies that $P$ and
$H$ are not disjoint, a contradiction. A similar argument shows that $H\cdot
P\subseteq P$.

With the previous remark, we see that if $P$ is a positive cone relative to
$H$ then we can define a total $G$-invariant order on $G/H$ by setting
$g_{1}H\prec g_{2}H\Leftrightarrow g_{1}^{-1}g_{2}\in P$. This is well-
defined, since if we pick different coset representatitives such that
$g_{1}^{\prime}=g_{1}h$ and $g_{2}^{\prime}=g_{2}h^{\prime}$ then
$g_{1}^{-1}g_{2}\in P$ implies that $h^{-1}g_{1}^{-1}g_{2}h^{\prime}\in H\cdot
P\cdot H\subseteq P$. The fact that $\prec$ is a total left-invariant order on
$G/H$ follows now easily.

######  Definition 2.20.

Let $\mathcal{C}$ be a class of languages. Let $(X,\pi)$ be a generating set
of $G$. Let $\prec$ a left-order. We say that $P\subseteq G$ is
$\mathcal{C}$-positive cone relative to $H\leqslant G$, if $P$ is a positive
cone relative to $H$ and there exists a language $\mathcal{L}\subseteq X^{*}$
in the class $\mathcal{C}$ such that $\pi(\mathcal{L})=P_{\prec}$.

The following argument will be used several times:

######  Lemma 2.21.

Let $G$ be a group and $H$ a subgroup. Let $P_{rel}$ be a positive cone
relative to $H$ and $P_{H}$ a positive cone for $H$. Then $P=P_{rel}\cup
P_{H}$ is a positive cone for $G$.

Moreover, if $\mathcal{C}$ is a class of languages closed under union,
$P_{rel}$ is $\mathcal{C}$-positive cone relative to $H$ and $P_{H}$ is a
$\mathcal{C}$-positive cone for $H$, then $P$ is a $\mathcal{C}$-positive
cone.

###### Proof.

We have that $G=P_{rel}\sqcup H\sqcup P_{rel}^{-1}=(P_{rel}\sqcup
P_{H})\sqcup\\{1\\}\sqcup(P_{H}^{-1}\sqcup P_{rel}^{-1})=P\sqcup\\{1\\}\sqcup
P^{-1}.$ To see that $P$ is a semigroup, note that we have
$P_{rel}P_{rel}\subseteq P_{rel}$ and $P_{H}P_{H}\subseteq P_{H}$ by
assumption, and that we observed previously that $P_{rel}H\subseteq P_{rel}$
and $HP_{rel}\subseteq P_{rel}$, therefore $(P_{rel}\cup P_{H})(P_{rel}\cup
P_{H})\subseteq(P_{rel}\cup P_{H})$.

The moreover part is clear by definition of $P$. ∎

##  3 Lexicographic left-orders of group extensions

In this section we study left-orders on group extensions. Suppose that $N$ and
$Q$ are groups and that $G$ is an extension of $N$ by $Q$. That is, there is a
short exact sequence $1\to N\to G\stackrel{{\scriptstyle f}}{{\to}}Q\to 1$.
Fixing a right inverse $s$ of $f$ (i.e. a section of $f$), with
$s(1_{Q})=1_{G}$, we obtain the bijection $G\to N\times Q$,
$g\mapsto(gs(f(g))^{-1},f(g))$. In particular, it is natural to try to order
$G$ out of this bijection with $N\times Q$.

######  Definition 3.1 (Lexicographic order on direct products of totally
ordered sets).

Let $(N,\prec_{N})$ and $(Q,\prec_{Q})$ be two totally ordered sets.

  * •

The lexicographic order $\prec_{lex}$ on $N\times Q$ with leading factor $Q$
is given by $(n,q)\prec_{lex}(n^{\prime},q^{\prime})$ if and only if
$q\prec_{Q}q^{\prime}$ or $q=q^{\prime}$ and $n\prec_{N}n^{\prime}$.

  * •

The lexicographic order $\prec_{lex}$ on $N\times Q$ with leading factor $N$
is given by $(n,q)\prec_{lex}(n^{\prime},q^{\prime})$ if and only if
$n\prec_{N}n^{\prime}$ or $n=n^{\prime}$ and $q\prec_{Q}q^{\prime}$.

We will see that the lexicographic order on $N\times Q$ where $Q$ leads,
always induces a left-order on the underlying group $G$ (Lemma 3.2). This is
not the case for the lexicographic order where $N$ leads, yet in Section 3.2,
we will find conditions on orders on $N$ and $Q$ (and the structure of $G$) so
that the lexicographic order where $N$ leads induces a left-order on the group
$G$.

###  3.1 Lexicographic left-orders where the quotient leads

######  Lemma 3.2.

Let $f\colon G\to Q$ be a group epimorpishm with kernel $N$. Let $P_{Q}$ and
$P_{N}$ be positive cones on $Q$ and $N$ respectively. Then
$P_{\prec_{lex}}\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=f^{-1}(P_{Q})\cup P_{N}$ is a positive cone of $G$.
The left-order on $G$ induced by $P_{\prec_{lex}}$ is called _lexicographic
led by the quotient $Q$_.

###### Proof.

Clearly $f^{-1}(P_{Q})$ is a subsemigroup as it is the pre-image of a semi-
group under a homomorphism. Also, as $Q=P^{-1}_{Q}\sqcup\\{1_{Q}\\}\sqcup
P_{Q}$ we get that $G=f^{-1}(P_{Q})^{-1}\sqcup N\sqcup f^{-1}(P_{Q})$ and
hence $f^{-1}(P_{Q})$ is a positive cone relative to $N$. The result now
follows from Lemma 2.21. ∎

Let $(N,\prec_{N})$ and $(Q,\prec_{Q})$ be left-ordered groups, and let
$P_{N}$ and $P_{Q}$ be the corresponding positive cones. It is easy to check
that indeed, the left-order of the previous lemma on $G$ coincides to the
lexicographic order on the set $N\times Q$ (which is naturally in bijection
with $G$) with leading factor $Q$.

######  Proposition 3.3.

Let $\mathcal{C}$ be a class of languages closed under unions and inverse
homomorphisms. Let $N$ and $Q$ be finitely generated groups and $G$ an
extension of $N$ by $Q$. Let $P_{N}$ and $P_{Q}$ be $\mathcal{C}$-positive
cones for $N$ and $Q$ respectively. Then $P_{\prec_{lex}}$ constructed as in
Lemma 3.2 is a $\mathcal{C}$-positive cone for $G$.

In particular, $\mathcal{C}$ can be any class of full AFL languages as the
classes $\mathsf{Reg},\mathsf{1C}$ or $\mathsf{CF}$.

###### Proof.

Fix finite generating sets $(X,\pi_{N})$ and $(Y,\pi_{Q})$ for $N$ and $Q$.
Let $P_{N}$ and $P_{Q}$ be $\mathcal{C}$-left-positive cones for $N$ and $Q$,
and let $\mathcal{L}_{N}\subseteq X^{*}$ and $\mathcal{L}_{Q}\subseteq Y^{*}$
be in $\mathcal{C}$ such that $\pi_{N}(\mathcal{L}_{N})=P_{N}$ and
$\pi_{Q}(\mathcal{L}_{Q})=P_{Q}$.

Denote by $f$ the epimorphism of $G$ onto $Q$, i.e. $f\colon G\to Q$. We can
define a generating set $(X\sqcup Y,\pi)$ for $G$ such that
$\pi_{N}(x)=\pi(x)$ for $x\in X$ and $\pi_{Q}(y)=f(\pi(y))$ for $y\in Y$.

Let $\widetilde{\mathcal{L}_{Q}}$ be the preimage of $\mathcal{L}_{Q}$ under
the monoid morphism $\pi_{X\sqcup Y\to Y}\colon(X\sqcup Y)^{*}\to Y^{*}$ that
is the identity on $Y$ and sends elements of $X$ to the empty word. Note that
$f(\pi(\widetilde{\mathcal{L}_{Q}}))=P_{Q}$ and hence
$\pi(\widetilde{\mathcal{L}_{Q}})\subseteq f^{-1}(P_{Q})$.

To see that $\pi(\widetilde{\mathcal{L}_{Q}})\supseteq f^{-1}(P_{Q})$, let
$g\in G$ such that $f(g)\in P_{Q}$. Then, there exists $w\in\mathcal{L}_{Q}$
such that $\pi_{Q}(w)=f(\pi(w))$. There is
$\tilde{w}\in\widetilde{\mathcal{L}_{Q}}$ such that $\pi_{X\sqcup Y\to
Y}(\tilde{w})=w$ and therefore if $\tilde{g}=\pi(\tilde{w})$ we get that
$f(g)=f(\tilde{g})$ and hence $g(\tilde{g})^{-1}\in N$. There is $u\in X^{*}$
such that $\pi(u)=\pi_{N}(u)=g(\tilde{g})^{-1}$. Note that $\pi_{X\sqcup Y\to
Y}(u\tilde{w})=w$, therefore $u\tilde{w}\in\widetilde{\mathcal{L}_{Q}}$ and
$\pi(u\tilde{w})=g(\tilde{g})^{-1}\tilde{g}=g$.

As $\mathcal{C}$ is closed under inverse homomomorphism and
$\widetilde{\mathcal{L}_{Q}}\in\mathcal{C}$, we get that $f^{-1}(P_{Q})$ is
$\mathcal{C}$-positive cone relative to $N$. By Lemma 2.21,
$P_{G}=f^{-1}(P_{Q})\cup P_{N}$ is a $\mathcal{C}$-positive cone. ∎

####  3.1.1 Polycyclic groups

We use Proposition 3.3 to show that left-orderable virtually polycyclic groups
admit $\mathsf{Reg}$-left-orders. Let us recall some definitions.

######  Definition 3.4.

Let $G$ be a group. A subnormal series for $G$ is a decreasing sequence of
subgroups of $G$

$G=G_{0}\unrhd G_{1}\unrhd\dots\unrhd G_{n}=\\{1\\}$

such that $G_{i+1}$ is normal in $G_{i}$ for $0\leq i<n$. The quotients
$G_{i}/G_{i+1}$ are called factors.

######  Definition 3.5.

A group $G$ is polycyclic (resp. poly-$\mathbb{Z}$) if there is a finite
subnormal series for $G$ with cyclic (resp. infinite cyclic) factors.

As a consequence of Proposition 3.3 we have the following.

######  Corollary 3.6.

Poly-$\mathbb{Z}$ groups have $\mathsf{Reg}$-left-orders.

###### Proof.

The corollary follows by induction on the length of the subnormal series. The
base case is $\mathbb{Z}$ and Example 2.16 shows that $\mathbb{Z}$ has
$\mathsf{Reg}$ positive cones. Proposition 3.3 allows the inductive argument.
∎

Finally, we use a theorem of Morris [24] to show the following.

######  Proposition 3.7.

Left-orderable virtually polycyclic groups are poly-$\mathbb{Z}$. In
particular, they have $\mathsf{Reg}$-left-orders.

###### Proof.

Recall that if $G$ is polycyclic, the number of $\mathbb{Z}$-factors in a
subnormal series of cyclic factors is well-defined and called the Hirsch
length and denoted $h(G)$. For a virtually polycyclic group $G$, we can define
$h(G)$ to be the Hirsch length of any finite index polycyclic subgroup, and it
is still well-defined (see for example [30]). Moreover, if $H$ is a normal
subgroup in $G$ then both $H$ and $G/H$ are virtually polycyclic and
$h(G)=h(H)+h(G/H)$.

We argue by induction on the Hirsch length that a virtually polycyclic left-
orderable group is poly-$\mathbb{Z}$. If $h(G)=0$, then $G$ left-orderable and
finite, so $G$ is trivial. Suppose that $h(G)>0$, and recall that Morris’
theorem says that finitely generated, left-orderable amenable groups have
infinite abelianization [24]. Thus, there is a normal subgroup $N\unlhd G$
such that $G/N\cong\mathbb{Z}$. Since $N$ is virtually polycyclic, left-
orderable and $h(N)=h(G)-1$, we get by hypothesis that $N$ is
poly-$\mathbb{Z}$, and so is $G$. ∎

####  3.1.2 Solvable Baumslag-Solitar groups

The result about regularity of left-orders on polycyclic groups cannot be
promoted to the case of solvable groups [10]. Here we give the complete
picture for when a solvable Baumslag-Solitar groups $BS(1,q)$,
$q\in\mathbb{Z}$ admits a regular positive cone. Recall that for $q=0$,
$BS(1,0)\cong\mathbb{Z}$ and for $q\neq 0$ these groups are defined by the
presentation

$BS(1,q)=\langle a,b\,|\,aba^{-1}=b^{q}\rangle.$

For $q\neq 0$, it is well known that
$BS(1,q)\simeq\mathbb{Z}[1/q]\rtimes\mathbb{Z}$ (see for instance [14]). Under
this isomorphism, the element $b$ can be identified with the unity of the ring
$\mathbb{Z}[1/q]$ (the minimal sub-ring of $\mathbb{Q}$ containing
$\mathbb{Z}$ and $1/q$). The element $a$ can be identified with the generator
for the $\mathbb{Z}$-factor which acts on $\mathbb{Z}[1/q]$ by multiplying by
$1/q$. Therefore, an element $r/q^{s}\in\mathbb{Z}[1/q]$ where $s\geq 0$ and
$r\in\mathbb{Z}-\\{0\\}$, can be written as $a^{-s}b^{\varepsilon r}a^{s}$
where $\varepsilon\in\\{-1,1\\}$ depends on the parity of $s$ and the sign of
$r$ and $q$ as in the following table.

$\text{sign}(q)$ | $s$ | $\varepsilon$
---|---|---
$+$ | even/odd | $\text{sign}(r)$
$-$ | even | $\text{sign}(r)$
$-$ | odd | $-\text{sign}(r)$

In particular, for solvable Baumslag-Solitar groups, every group element can
be written in the form $a^{n}(a^{-m}b^{k}a^{m})$ with $m\geq 0$,
$n,k\in\mathbb{Z}$.

Notice that the groups $\mathbb{Z}$ and $\mathbb{Z}[1/q]$ admit only two left-
orders each. Therefore, there are only four lexicographic left-orders on
$BS(1,q)\cong\mathbb{Z}[1/q]\rtimes\mathbb{Z}$ where the quotient leads. These
four left-orders have the following positive cones,

$P_{1}=\\{(r/q^{s},n)\in\mathbb{Z}[1/q]\rtimes\mathbb{Z}\mid n>0\text{ or
}(n=0\text{ and }r/q^{s}>0)\\},$
$P_{2}=\\{(r/q^{s},n)\in\mathbb{Z}[1/q]\rtimes\mathbb{Z}\mid n<0\text{ or
}(n=0\text{ and }r/q^{s}>0)\\},$

$P_{3}:=P_{1}^{-1}$ and $P_{4}:=P_{2}^{-1}$. We first remark that these are
one-counter positive cones.

######  Proposition 3.8.

For each, $q\neq 0$ and each $i=1,2,3,4$, there is a one-counter language over
$\\{a,a^{-1},b,b^{-1}\\}^{*}$ evaluating onto the positive cone $P_{i}$ of
$BS(1,q)$ described above.

###### Proof.

We only deal with the case $q<1$ and $i=1,2$ and we indicate the needed
modifications for $q>1$ at the end of the proof. The cases $i=3,4$ are
identical. The following two languages

$\mathcal{L}_{1}=\\{a^{n}(a^{-m}b^{k}a^{m})\mid n>0\text{ or }[n=0\text{ and
}(m\text{ odd }\text{ and }k<0)\text{ or }(m\text{ even }\text{ and }k>0)]\\}$
$\mathcal{L}_{2}=\\{a^{n}(a^{-m}b^{k}a^{m})\mid n<0\text{ or }[n=0\text{ and
}(m\text{ odd }\text{ and }k<0)\text{ or }(m\text{ even }\text{ and }k>0)]\\}$

where we assume $m\geq 0$ and $k\in\mathbb{Z}$, evaluate to $P_{1}$ and
$P_{2}$. This follows easily from our description of normal forms at the
beginning of the subsection.

We see that
$\mathcal{L}_{1}=\\{a\\}^{+}\cdot\mathcal{L}_{quot}\cup\mathcal{L}_{ker}$ and
$\mathcal{L}_{2}=\\{a^{-1}\\}^{+}\cdot\mathcal{L}_{quot}\cup\mathcal{L}_{ker}$
where

$\mathcal{L}_{quot}=\\{a^{-m}b^{k}a^{m}\mid m\geq 0,k\in\mathbb{Z}\\}$

and

$\mathcal{L}_{ker}=\\{a^{-m}b^{k}a^{m}\mid m\geq 0,k\in\mathbb{Z},(m\text{ odd
}\text{ and }k<0)\text{ or }(m\text{ even }\text{ and }k>0)\\}.$

By the closure properties of the class $\mathsf{1C}$, to see that
$\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ are one-counter languages, it is
enough to see that $\mathcal{L}_{quot}$ and $\mathcal{L}_{ker}$ are in
$\mathsf{1C}$. Moreover,

$\displaystyle\mathcal{L}_{ker}$
$\displaystyle=\mathcal{L}_{quot}\cap(\\{a^{-1}a^{-1}\\}^{*}\cdot\\{b\\}^{*}\cdot\\{aa\\}^{*})$
$\displaystyle\cup\mathcal{L}_{quot}\cap(\\{a^{-1}\\}\cdot\\{a^{-1}a^{-1}\\}^{*}\cdot\\{b^{-1}\\}^{*}\cdot\\{aa\\}^{*}\cdot\\{a\\})$

Again, since the class $\mathsf{1C}$ is closed under union and intersection
with regular languages, we see that it is enough to show that
$\mathcal{L}_{quot}$ is one-counter. We illustrate a pushdown automaton
accepting $\mathcal{L}_{quot}$ in Figure 3 and leave the rest of the proof of
this case to the reader.

$s_{0}$
---
$a,\epsilon/\sigma$
---
$a,\sigma/\sigma\sigma$
---
$a,\sigma/\epsilon$
---
$a,\sigma/\epsilon$
---
$a,\sigma/\epsilon$
---
$\epsilon,\epsilon/\epsilon$
---
$b$
---
$b$
---
$b^{-1}$
---
$b^{-1}$
---
Figure 3: Pushdown automaton accepting $\mathcal{L}_{quot}$. Here
$\\{\sigma\\}$ is the stack alphabet (i.e the counter symbol).

For the case $q>1$, observe that

$\mathcal{L}_{1}^{\prime}=\\{a^{n}(a^{-m}b^{k}a^{m})\mid n>0\text{ or
}[n=0\text{ and }k>0]\\}$
$\mathcal{L}_{2}^{\prime}=\\{a^{n}(a^{-m}b^{k}a^{m})\mid n<0\text{ or
}[n=0\text{ and }k<0]\\},$

evaluate to $P_{1}$ and $P_{2}$ respectively. An easy modification of the
previous automaton allows to conclude this case. ∎

We are going to show now that the previous proposition is optimal, in the
sense that $P_{1},P_{2},P_{3}$ and $P_{4}$ can not be regular. To show this we
need to recall some facts.

######  Definition 3.9.

Let $(\mathcal{M},\operatorname{d})$ be a metric space. A subset
$Y\subseteq\mathcal{M}$ is coarsely connected  if there is $R>0$ such that
$\\{p\in\mathcal{M}\mid\operatorname{d}(p,Y)\leq R\\}$, the $R$-neighborhood
of $Y$, is connected.

The following is [1, Proposition 7.2], in view of Lemma 2.12.

######  Lemma 3.10.

Let $G$ be a finitely generated group. If $P$ is a $\mathsf{Reg}$-positive
cone of $G$, then $P$ and $P^{-1}$ are coarsely connected subsets of the
Cayley graph of $G$.

For Lemma 3.10 recall that given a finitely generated group $G$, a non-trivial
homomorphism $\phi\colon G\to\mathbb{R}$ belongs to $\Sigma^{1}(G)$, the
Bieri-Neumann-Strebel invariant (BNS invariant for short), if and only if
$\phi^{-1}((0,\infty))$ is coarsely connected. Moreover, the kernel of $\phi$
is finitely generated if and only if both $\phi$ and $-\phi$ belong to
$\Sigma^{1}(G)$ (see [7]). Therefore we have the following.

######  Lemma 3.11.

Suppose that $G$ is an extension of $N$ by $\mathbb{Z}$. If $N$ is not
finitely generated, then no lexicographic order on $G$ where $\mathbb{Z}$
leads is $\mathsf{Reg}$.

###### Proof.

Suppose that $f\colon G\to\mathbb{Z}$ is a homomorphism with kernel $N$.
Without loss of generality, we can assume that a lexicographic order where
$\mathbb{Z}$ leads has a positive cone of the form
$P_{G}\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=f^{-1}(\mathbb{Z}_{\geq 1})\cup P_{N}$ where
$P_{N}$ is a positive cone for $N$.

Since $f(P_{N})=0$, and there is a group generator mapped under $f$ to a
positive integer, we have that $f^{-1}(\mathbb{Z}_{\geq 1})$ is coarsely
connected if and only if $f^{-1}(\mathbb{Z}_{\geq 1})\cup P_{N}$ is coarsely
connected. Therefore, $f\in\Sigma^{1}(G)$ if and only if
$f^{-1}(\mathbb{Z}_{\geq 1})\cup P_{N}$ is coarsely connected. Similarly,
$-f\in\Sigma^{1}(G)$ if and only if $f^{-1}(\mathbb{Z}_{\leq-1})\cup
P_{N}^{-1}$ is coarsely connected.

Assume that $N$ is not finitely generated and $P_{G}$ is a
$\mathsf{Reg}$-positive cone. From BNS theory, either
$P_{G}=f^{-1}(\mathbb{Z}_{\geq 1})\cup P_{N}$ or
$P_{G}^{-1}=f^{-1}(\mathbb{Z}_{\leq-1})\cup P_{N}^{-1}$ is not coarsely
connected. By Lemma 3.10 if the left-order given by $P_{G}$ is $\mathsf{Reg}$,
then both cones $P_{G}$ and $P_{G}^{-1}$ would be coarsely connected. We have
a contradiction. ∎

######  Corollary 3.12.

For each, $q\notin\\{-1,0,1\\}$ and each $i=1,2,3,4$, the positive cone
$P_{i}$ of $BS(1,q)$ is not regular.

###### Proof.

It follows from Lemma 3.11 and the fact that $\mathbb{Z}[1/q]$ is not finitely
generated, that $P_{1},P_{2},P_{3}$ and $P_{4}$ can not be regular. ∎

Let $q>1$. From the point of view of orders, $BS(1,q)$ and $BS(1,-q)$ behave
quite differently. On one hand, $BS(1,-q)$ falls into the classification of
groups admitting only finitely many left-orders obtained by Tararin [34] (see
also [20, 13], or Subsection 4). In fact, $B(1,-q)$ admits only the four left-
orders we described before.) On the other hand $BS(1,q)$ admits uncountably
many left-orders. Beside the four left-orders described above, its other left-
orders appears as induced orders from the (order-preserving) affine action of
$BS(1,q)$ on the real line

$a\colon x\mapsto qx\,,\;b\colon x\mapsto x+1.$

This classification of left-orders is shown in [28] for the case of $BS(1,2)$
but the same proof works for general $q>1$.

We next observe that some of these induced orders have regular positive cones.

######  Lemma 3.13.

Let $BS(1,q)=\langle a,b\mid aba^{-1}=b^{q}\rangle$ with $q\geq 2$. Then

$P_{0}=\\{a^{n}(a^{-m}b^{k}a^{m})\mid k>0,m,n\in\mathbb{Z}\\}$

is a $\mathsf{Reg}$-positive cone relative to $\langle a\rangle$. In
particular, $P=\langle a\rangle^{+}\cup P_{0}$ is $\mathsf{Reg}$-positive
cone.

###### Proof.

Consider the action of $BS(1,q)$ on $\mathbb{R}$ given by $a\colon x\mapsto
qx$ and $b\colon x\mapsto x+1$. If $g\in BS(1,q)$ is an element with normal
form $g=a^{n}(a^{-m}b^{k}a^{m})$, then $g$ maps $x$ to
$q^{n}x+\frac{k}{q^{m}}$, which implies that this affine representation is
faithful.

We let $P_{0}=\\{g\in BS(1,q):g(0)>0\\}$. Note that an element of the form
$g=a^{n}(a^{-m}b^{k}a^{m})$ belongs to $P_{0}$ if and only if $k>0$. This
coincides with the set $P_{0}$ of the statement, and therefore $P_{0}$ is a
positive cone relative to $Stab_{BS(1,q)}(0)=\langle a\rangle\cong\mathbb{Z}$.
From Lemma 2.21, the set $P$ given by

$P=\\{a^{n}\mid n>0\\}\cup\\{a^{n}(a^{-m}b^{k}a^{m})\mid
k>0,m,n\in\mathbb{Z}\\},$

is a positive cone for $BS(1,q)$.

Viewing the elements of $P$ as words in $\\{a,b,a^{-1},b^{-1}\\}^{*}$, $P$ can
be represented as a language accepted by the automaton of Figure 4. One can
construct an automaton that gives a regular language for $P_{0}$ from the
automaton of Figure 4 by just changing the state right to $s_{0}$ to a non-
accepting state.

$s_{0}$
---
$a^{-1}$
---
$a$
---
$a$
---
$a$
---
$a$
---
$a$
---
$a$
---
$a^{-1}$
---
$a^{-1}$
---
$a^{-1}$
---
$a^{-1}$
---
$a^{-1}$
---
$b$
---
$b$
---
$b$
---
$b$
---
Figure 4: Finite state automaton accepting a positive cone language for
$BS(1,q)$ with $q>1$.

Remark that this is a subgraph of the automaton-graph describing the language
of normal forms in $BS(1,q)$. ∎

######  Theorem 3.14.

All solvable Baumslag-Solitar groups $BS(1,q)=\langle a,b\mid
aba^{-1}=b^{q}\rangle$ admit one-counter left-orders, and $BS(1,q)$ admits a
regular left-order if and only if $-1\leq q$. Moreover, for $q\geq 2$ all
$\mathsf{Reg}$-left-orders on $BS(1,q)$ are induced by affine actions on
$\mathbb{R}$.

###### Proof.

From Propositions 3.8 all solvable Baumslag-Solitar groups admit a one-counter
left-order.

If $q\in\\{-1,0,1\\}$, then $BS(1,q)$ is poly-$\mathbb{Z}$ and then has
regular left-orders (our convention is that $BS(1,0)=\mathbb{Z}$).

If $q\leq-2$, by Tararin’s classification discussed above and Corollary 3.12,
we have that $BS(1,q)$ do not admit regular orders.

Finally, suppose that $q\geq 2$. From [28], a left-order on $G$ is either one
induced from an affine action on $\mathbb{R}$ or a lexicographic order with
leading factor $\mathbb{Z}$ coming from the semidirect product
$\mathbb{Z}[1/q]\rtimes\mathbb{Z}$. We saw in Corollary 3.12 that the
lexicographic left-orders on $BS(1,q)$ with leading factor $\mathbb{Z}$ cannot
be regular. We saw in Lemma 3.13 that $BS(1,q)$ admits regular orders and thus
such left-order must be induced by affine actions (as it is shown in the proof
of the lemma). ∎

###  3.2 Lexicographic left-orders where the kernel leads

In general, if $G$ is an $N$ by $Q$ extension of left-orderable groups, the
lexicographic order on $N\times Q$ with leading factor $N$ is not $G$-left-
invariant. However, in some special situations it is. The following lemma will
be used to produce left-orders on extensions where the kernel leads.

######  Lemma 3.15.

Let $G$ be a semidirect product of the subgroups $N\unlhd G$ and $Q\leqslant
G$. Let $P_{N}$ and $P_{Q}$ be positive cones of $N$ and $Q$ respectively, and
assume that $qP_{N}q^{-1}=P_{N}$ for all $q\in Q$. Then, the lexicographic
order on the underlying set $N\times Q$ with leading factor $N$ is $G$-left-
invariant. In particular, it is a left-order on $G$.

###### Proof.

Since $G$ is a semidirect product of $N$ and $Q$, we have that $N\cap
Q=\\{1_{G}\\}$ and $NQ=G$. There is a natural bijection between $N\times Q$ to
$G=NQ$, and under this bijection, the subset of elements of $N\times Q$ that
are lexicographical greater to $(1_{N},1_{Q})$ corresponds to the subset
$P\mathrel{\mathop{\mathchar 0\relax}"303A}\mkern-1.2mu=P_{N}Q\cup P_{Q}$ of
$G$. Note that $P^{-1}=Q^{-1}P_{N}^{-1}\cup P_{Q}^{-1}$ and since
$qP_{N}q^{-1}=P_{N}$ for all $q\in Q$, we get that $P^{-1}=P_{N}^{-1}Q\cup
P_{Q}^{-1}$. Therefore $G=P\sqcup P^{-1}\sqcup\\{1_{G}\\}$.

To show that $P$ is a subsemigroup, let $nq,n^{\prime}q^{\prime}\in P$, with
$n,n^{\prime}\in N$ and $q,q^{\prime}\in Q$. Recall that $n$ and $n^{\prime}$
either are trivial or belong to $P_{N}$. Then
$nqn^{\prime}q^{\prime}=n(qn^{\prime}q^{-1})qq^{\prime}$ and we see that if
$n\neq 1_{G}$ or $n^{\prime}\neq 1_{G}$ then $n(qn^{\prime}q^{-1})\in P_{N}$
and $nqn^{\prime}q^{\prime}\in P_{N}Q\subseteq P$. If $n=1_{G}=n^{\prime}$,
then $q,q^{\prime}\in P_{Q}$ and $nqn^{\prime}q^{\prime}=qq^{\prime}\in
P_{Q}\subseteq P$. ∎

This lemma will be helpful to construct regular left-orders on extensions when
the kernel is not finitely generated (and thus the kernel alone cannot support
a regular left-order). Our main example are wreath products, however we have
already observed this phenomenon in Baumslag-Solitar groups.

######  Example 3.16 (Lexicographic left-orders on $BS(1,q)$ where the kernel
leads).

For $q>0$ we have already seen that $BS(1,q)$ has regular orders, constructed
through an affine action on the real line. Viewing $BS(1,q)=\langle a,b\,\mid
aba^{-1}=b^{q}\rangle\cong\mathbb{Z}[1/q]\rtimes\mathbb{Z}$, the left-order of
Figure 4 is lexicographic where the factor $\mathbb{Z}[1/q]$ leads. Indeed, a
positive cone $P_{\mathbb{Z}[1/q]}$ for $\mathbb{Z}[1/q]$ is the set of
elements greater than $0$. Since $\langle a\rangle\cong\mathbb{Z}$ acts on
$\mathbb{Z}[1/q]$ by multiplying by $q$, we have that
$a^{n}P_{\mathbb{Z}[1/q]}a^{-n}=P_{\mathbb{Z}[1/q]}$ for all $n\in\mathbb{Z}$.
The previous lemma tell us that $\langle a\rangle\cdot
P_{\mathbb{Z}[1/q]}\cup\\{a\\}^{+}$ is a positive cone for $BS(1,q)$. This is
exactly the left-order of the automaton of Figure 4.

####  3.2.1 Wreath products

The wreath product $N\wr Q$ of groups $N$ and $Q$ is the semidirect product of
${\bf N}:=\oplus_{q\in Q}N$ by $Q$, where the conjugation action of $Q$ on
${\bf N}$ is given by the left-multiplication action on the indexes of the
copies of $N$. That is, if ${\bf n}=(n_{q})_{q\in Q}\in{\bf N}$ and
$q^{\prime}\in Q$, we have $q^{\prime}{\bf
n}q^{\prime-1}=(n_{q^{\prime}q})_{q\in G}$.

We begin with an example that will illustrate the construction we develop in
this section.

######  Proposition 3.17.

The group $\mathbb{Z}\wr\mathbb{Z}$ has $\mathsf{Reg}$-left-orders.

###### Proof.

The group $\mathbb{Z}\wr\mathbb{Z}$ is isomorphic to
$\mathbb{Z}[X,X^{-1}]\rtimes C_{\infty}$ where $C_{\infty}=\langle t\rangle$
acts by multiplying by $X$ on $\mathbb{Z}[X,X^{-1}]$. An element of
$\mathbb{Z}\wr\mathbb{Z}$ is therefore uniquely written as
$(p=a_{i_{0}}X^{i_{0}}+a_{i_{1}}X^{i_{1}}+\dots a_{i_{k}}X^{i_{k}},t^{s})$
with $i_{0}>i_{1}>i_{2}>\dots>i_{k}\in\mathbb{Z}$ and $s\in\mathbb{Z}$. We say
that $a_{i_{0}}$ is the leading coefficient of $p$, and define
$\mathsf{leadcoef}(p):=a_{i_{0}}$. It is easy to check that
$P=\\{(p,t^{s})\mid\mathsf{leadcoef}(p)>0\\}\cup\\{(0,t^{s})\mid s>0\\}$ is a
positive cone.

The group is generated by the constant polynomial $c=1$ and $t$, since
$t^{k}c^{m}t^{-k}$ represents the polynomial $mX^{k}$. Therefore a word
representing the element given by
$(a_{i_{0}}X^{i_{0}}+a_{i_{1}}X^{i_{1}}+\dots a_{i_{k}}X^{i_{k}},t^{s})$ is
$t^{{i_{0}}}c^{a_{i_{0}}}t^{{i_{1}}-{i_{0}}}c^{a_{i_{1}}}t^{{i_{2}}-{i_{1}}}\cdots
c^{a_{i_{k}}}t^{{-i_{k}}}t^{s}$. Since $i_{0}>i_{1}>i_{2}>\dots>i_{k}$, we
have that $i_{1}-i_{0},i_{2}-i_{1},\dots,i_{k}-i_{k-1}$ are all negative. A
language for this positive cone is

$\\{t^{n}c^{m}t^{n_{1}}c^{m_{1}}t^{n_{2}}c^{m_{2}}\dots c^{m_{k}}t^{l}\mid
m>0,n_{i}<0,m_{i}\in\mathbb{Z},k\geq 0,l\in\mathbb{Z}\\}\cup\\{t^{s}\mid
s>0\\}.$

This language is recognized by the finite state automaton of Figure 5.

$s_{0}$
---
$t$
---
$t$
---
$t^{-1}$
---
$t^{-1}$
---
$c$
---
$c$
---
$c$
---
$t^{-1}$
---
$c,c^{-1},t^{-1}$
---
$t$
---
$t$
---
Figure 5: Finite state automaton accepting a positive cone language for
$\mathbb{Z}\wr\mathbb{Z}$.

∎

The previous strategy also works in the more general case of wreath products
$N\wr Q$. Let $\prec_{N}$ and $\prec_{Q}$ be left-orders on $N$ and $Q$
respectively, with corresponding positive cones $P_{N}$ and $P_{Q}$. We can
construct a lexicographic order $\prec_{{\bf N}}$ on ${\bf N}=\oplus_{q\in
Q}N$ as follows. Given ${\bf n}=(n_{q})_{q\in Q},{\bf
n}^{\prime}=(n^{\prime}_{q})_{q\in Q}\in{\bf N}$ we put ${\bf n}\prec{\bf
n^{\prime}}$ if ${\bf n}\neq{\bf n^{\prime}}$ and for
$q^{\prime}=\max_{\prec_{Q}}\\{q\in Q\mid n_{q}\neq n^{\prime}_{q}\\}$ we have
that $n_{q^{\prime}}\prec_{N}n^{\prime}_{q^{\prime}}$.

######  Lemma 3.18.

The lexicographic order on $N\wr Q={\bf N}\rtimes Q$ extending $\prec_{\bf N}$
and $\prec_{Q}$ is an $N\wr Q$-left-invariant lexicographic order with leading
factor ${\bf N}$.

###### Proof.

Observe that $P_{\bf N}$, the positive cone ${\bf N}$ associated to
$\prec_{{\bf N}}$, is equal to

$\\{(n_{q})_{q\in G}\in{\bf N}\setminus\\{1_{\bf N}\\}\mid n_{q}\in
P_{N}\text{ where }q^{\prime}=\max\\{q\in G\mid n_{q}\neq 1_{N}\\}\\}.$

Now, given ${\bf n}\in P_{\bf N}$ and $q^{\prime}=\max\\{q\in Q\mid n_{q}\neq
1_{N}\\}$, and given $q\in Q$, we set ${\bf n}^{\prime}=q{\bf
n}q^{-1}=(n^{\prime}_{q})_{q\in Q}$, and we see that
$qq^{\prime}=\max_{\prec_{Q}}\\{p\in Q\mid n^{\prime}_{p}\neq 1_{N}\\}$ since
$\prec_{Q}$ is left $Q$-invariant. Therefore
$n^{\prime}_{qq^{\prime}}=n_{q^{\prime}}\in P_{N}$ and thus ${\bf
n}^{\prime}\in P_{\bf N}$. We have showed that $qP_{\bf N}q^{-1}\subseteq
P_{\bf N}$ for all $q\in Q$, which implies $qP_{\bf N}q^{-1}=P_{\bf N}$ for
all $q\in Q$. The proof then follows from Lemma 3.15. ∎

Let $X$ and $Y$ be generating sets of $N$ and $Q$ respectively. The set $X\cup
Y$ generates $N\wr Q$ since the $q$-th copy of $N$ in $\oplus_{q\in Q}N$ is
identified with $qNq^{-1}$ and thus it can be generated by $qXq^{-1}$ (the
conjugates of $X$ by $q$) and each element of $qXq^{-1}$ can be expressed in
terms of $X$ and $Y$.

An element $({\bf n}=\\{n_{q}\\}_{q\in Q},p)\in N\wr Q$ can be written as
$(\prod_{q\in Q}qn_{q}q^{-1})p$, and we can use the $\prec_{Q}$-order to write
this element uniquely as

$(q_{1}n_{1}q_{1}^{-1})(q_{2}n_{2}q_{2}^{-1})\cdots(q_{n}n_{m}q_{m}^{-1})p$

with the property that
$q_{1}\succ_{Q}q_{2}\succ_{Q}q_{3}\succ_{Q}\dots\succ_{Q}q_{m}$.

Thus, with this unique way of writing the elements of $N\wr Q$, the
lexicographic positive cone of $N\wr Q$ is

$P=\left\\{(q_{1}n_{1}q_{1}^{-1})(q_{2}n_{2}q_{2}^{-1})\cdots(q_{m}n_{m}q_{m}^{-1})p\middle|\begin{array}[]{c}q_{1}\succ_{Q}q_{2}\succ_{Q}\dots\succ_{Q}q_{m}\\\
(n_{1}\in P_{N}\wedge p\in Q)\vee(m=0\wedge p\in P_{Q})\end{array}\right\\}.$
(1)

We will now define a positive cone language for wreath products of groups in
terms of the positive (and negative) cone languages for $N$ and $Q$.

######  Proposition 3.19.

Let $\mathcal{L}_{N}\subseteq X^{*}$ and
$\mathcal{L}_{Q},\mathcal{M}_{Q}\subseteq Y^{*}$ be languages such that
$\pi_{N}(\mathcal{L}_{N})=P_{N}$ and $\pi_{Q}(\mathcal{L}_{Q})=P_{Q}$ are
positive cones for $N$ and $Q$ respectively, and
$\pi_{Q}(\mathcal{M}_{Q})=P_{Q}^{-1}$. Then, the language

$\mathcal{L}\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=Y^{*}\mathcal{L}_{N}\mathcal{M}_{Q}(X^{*}\mathcal{M}_{Q})^{*}Y^{*}\cup\mathcal{L}_{Q}$
(2)

evaluates onto the positive cone $P$ of Equation (1).

###### Proof.

First observe that

$\mathcal{L}=\left\\{vu_{1}w_{1}u_{2}w_{2}\dots
u_{m}w_{m}z\middle|\begin{array}[]{c}v,z\in Y^{*},\\\
u_{1}\in\mathcal{L}_{N}\text{ or }(m=0,v=\varepsilon\text{ and
}z\in\mathcal{L}_{Q}),\\\ u_{i}\in X^{*},w_{i}\in\mathcal{M}_{Q}\\\
\end{array}\right\\}.$ (3)

Let $P$ be the positive cone described in (1).

Let us first prove that $P\subseteq\pi(\mathcal{L})$. Let $g\in P$, and assume
that
$g=(q_{1}n_{1}q_{1}^{-1})(q_{2}n_{2}q_{2}^{-1})\cdots\break(q_{m}n_{m}q_{m}^{-1})p$
with $q_{i},n_{i},p$ as in (1). Let $z\in Y^{*}$ such that $\pi(z)=p$. If
$m=0$, then $g=p\in P_{Q}$. We can assume that $z\in\mathcal{L}_{Q}$. If
$m>0$, there is $v\in Y^{*}$ such that $\pi(v)=q_{1}$,
$u_{1}\in\mathcal{L}_{N}$ such that $n_{1}\in P_{N}$, and
$w_{i}\in\mathcal{M}_{Q}$ such that $\pi(w_{i})=q_{i}^{-1}q_{i+1}\in
P_{Q}^{-1}$, $u_{i}\in X^{*}$, such that $\pi(u_{i})=n_{i}$ for $2\leq i\leq
m$. We see that $g=\pi(vu_{1}w_{2}u_{2}\dots u_{m}w_{m}z).$

To prove that $\pi(\mathcal{L})\subseteq P$, let ${\bf
w}=vu_{1}w_{1}u_{2}w_{2}\dots u_{m}w_{m}z\in\mathcal{L}$ as in the description
in (3). If $m=0$, then ${\bf w}=z$ and $z\in\mathcal{L}_{Q}$. Thus $\pi({\bf
w})\in P$. If $m>0$, let $q_{1}=\pi(v)$ and for $i>1$,
$q_{i}=q_{i-1}\pi(w_{i})$, thus $\pi(w_{i})=q_{i-1}^{-1}q_{i}$. For
$i=1,\dots,m$ let $n_{i}=\pi(u_{i})$ and $p=\pi(z)$. Therefore $\pi({\bf
w})=(q_{1}u_{1}q_{1}^{-1})(q_{2}u_{2}q_{2}^{-1})\cdots(q_{m}u_{m}q_{m}^{-1})p$.
Note that since $w_{i}\in\mathcal{M}_{Q}$, we have that
$q_{i}\prec_{Q}q_{i-1}$. It follows that $\pi({\bf w})\in P$. ∎

We now state a generalization of Proposition 3.17.

######  Proposition 3.20.

Let $\mathcal{C}$ be a full AFL closed under reversal. Let $N$ and $Q$ be
finitely generated groups. Suppose that $N$ and $Q$ have a $\mathcal{C}$-left-
order represented by $\mathcal{L}_{N}$ and $\mathcal{L}_{Q}$ respectively.
Then, the wreath product of $N\wr Q$ admits a $\mathcal{C}$-left-order.

In particular admitting $\mathsf{Reg}$-left-orders is closed under wreath
products.

###### Proof.

Assume that $N$ is generated by a finite set $X$ and $Q$ is generated by a
finite set $Y$. We will construct a language over the generating set $X\sqcup
Y$. Let $\mathcal{M}_{Q}=\mathcal{L}_{Q}^{-1}$ be the negative cone language
associated to $\mathcal{L}_{Q}$ obtained by reversal and sending each letter
$x\mapsto x^{-1}$. Let $\mathcal{L}$ be the language of Equation (2). By
Proposition 3.19, $\mathcal{L}$ is a positive cone language for $N\wr Q$.
Since a class full AFL is closed by concatenation, concatenation closure and
union, we see that $\mathcal{L}$ is in $\mathcal{C}$. ∎

##  4 Groups where all positive cones are regular

In this section we classify the groups that only admit $\mathsf{Reg}$-left-
orders.

###  4.1 Order-convex subgroups and language-convex subgroups

######  Definition 4.1.

Let $(G,\prec)$ be a left-ordered group. A subgroup $H\leqslant G$ is called
$\prec$-convex if for all $h_{1},h_{2}\in H$ and $g\in G$ satisfying
$h_{1}\prec g\prec h_{2}$ we have that $g\in H$.

Left-order convexity relates to relative left-orders introduced in Section 2.5
in the following way.

######  Lemma 4.2.

If $H$ is $\prec$-convex for a left-order $\prec$ on G, then $P=\\{g\in G\mid
H\prec g\\}$ is a positive cone relative to $H$.

###### Proof.

First, we observe that for all $g\not\in H$ and all $h\in H$, we have that
$g\prec h$ or $h\prec g$. Indeed, otherwise we would have that $h\prec g\prec
h^{\prime}$ for $h,h^{\prime}\in H$, which by $\prec$-convexity of $H$ implies
that $g\in H$. Therefore, for all $g\in G-H$ either $g\prec H$ or $H\prec g$.
Now, if $H\prec g$, then $g^{-1}\prec 1\in H$. As $g^{-1}\notin H$ this means
that $g^{-1}\prec H$. This shows that $G=P\sqcup P^{-1}\sqcup H$. Finally, to
show that $P$ is a semigroup, notice that since $1\in H$, we have that $1\prec
g_{1}$ and $1\prec g_{2}$ for $g_{1},g_{2}\in P$. This implies that $H\prec
g_{1}\prec g_{1}g_{2}$. ∎

Thanks to the previous lemma and the discussion in Section 2.5, we can
conclude that if $H$ is $\prec$-convex, then for every $g_{1}\prec g_{2}$,
$g_{1},g_{2}\in G$ one has that $g_{1}h_{1}\preceq g_{2}h_{2}$ for all
$h_{1},h_{2}\in H$. Moreover, if $H$ is $\prec$-convex, then $\prec$ induces a
left-order on the coset space $G/H$.

The proposition below says that for certain subgroups being $\prec$-convex
implies being language-convex.

######  Proposition 4.3.

Let $G=H\rtimes\mathbb{Z}$ be finitely generated by $(X,\pi)$. Let $\prec$ be
a lexicographical $\mathsf{Reg}$-left-order on $G$ led by $\mathbb{Z}$, with
$\mathcal{L}\subseteq X^{*}$, a regular positive cone language. If $H$ is
finitely generated, then $H$ is language-convex with respect to $\mathcal{L}$.

In particular, the restriction of $\prec$ to $H$ is a $\mathsf{Reg}$-left-
order.

Recall that we set in Notation 2.3, that given word $w\in X^{*}$, and $x\in
X$, we use $\sharp_{x}(w)$ to denote the number of times the letter $x$
appears in the word $w$.

Before proving the Proposition 4.3 we need to describe all regular languages
over the alphabet $\\{t,t^{-1}\\}$ mapping onto a positive cone of
$\mathbb{Z}$. Given a word $w=x_{1}\dots x_{n}\in\\{t,t^{-1}\\}^{*}$, with
$x_{i}\in\\{t,t^{-1}\\}$ we define a function
$f_{w}\colon\\{0,1,\dots,n\\}\to\mathbb{Z}$ by $f_{w}(i)=\sharp_{t}(x_{1}\dots
x_{i})-\sharp_{t^{-1}}(x_{1}\dots x_{i})$.

######  Lemma 4.4.

Let
$\mathcal{L}\subseteq\\{w\in\\{t,t^{-1}\\}^{*}\mid\sharp_{t}(w)-\sharp_{t^{-1}}(w)\geq
0\\}$ be a regular language. Then every $f_{w}$ is coarsely non-decreasing in
the following sense: there is a constant $K\geq 0$ such that for all
$w\in\mathcal{L}$ and for all $i,j\in\\{0,1\dots,\ell(w)\\}$, if $j>i$ then
$f_{w}(j)>f_{w}(i)-K$.

###### Proof.

Let $\mathbb{M}=(\mathcal{S},X=\\{t,t^{-1}\\},\delta,s_{0},\mathcal{A})$ be an
automaton accepting $\mathcal{L}$. We will consider $\mathbb{M}$ to be without
$\epsilon$-moves and the image of transition function $\delta$ being
singletons (see Remark 2.1). We will think of this automaton as a directed
graph as explained in Remark 2.2. Every edge has a label from $X$, and from
every vertex there is at most one outgoing edge with label $x\in X$. Hence,
every $w\in\mathcal{L}$ labels a unique a path in $\mathbb{M}$ starting at the
initial state $s_{0}$.

Every $w\in\mathcal{L}$ can be decomposed as $w=xyz$, where $y$ is a (possibly
trivial) loop in $\mathbb{M}$. Then, $w\in\mathcal{L}$ implies that
$xy^{n}z\in\mathcal{L}$ for any $n\in\\{0,1,2,\dots\\}$. In other words, for
each word $w$ accepted in the automaton for $\mathcal{L}$, we may remove or
insert words $y$ representing loops in $\mathbb{M}$ and still get an accepted
word $xy^{n}z$.

Let $w\in\mathcal{L}$. Let $g(w):=\\#_{t}(w)-\\#_{t^{-1}}(w)$. Write $w=xyz$
where $y$ is a (possibly) trivial loop. Observe that $g(y)\geq 0$, for
otherwise $xy^{i}z\in\mathcal{L}$ for any $i$, as we may pick $i$ large enough
such that $g(xy^{i}z)<0$, contradicting our assumption about $\mathcal{L}$. In
other words, for any loop $y$ in $w=xyz$,

$g(xz)\leq g(xyz)$ (4)

and $xz\in\mathcal{L}$ since we have only removed a loop $y$.

Let $n$ be the number of states of $\mathbb{M}$. For any subword $u$ of
$w\in\mathcal{L}$, decompose $u=x_{1}y_{1}x_{2}y_{2}\dots
x_{k-1}y_{k-1}x_{k}$, where the $y_{i}$ are loops and the length of the word
$x_{1}x_{2}\dots x_{k}$ is minimal. We allow the subwords $x_{i}$ to be empty.
Viewing $u$ as a subpath of $w$ in $\mathbb{M}$, we construct a new path whose
label is $u^{\prime}=x_{1}\dots x_{k}$ which consists of removing all loops
from $u$. In particular, by the pigeonhole principle we have that
$\ell(u^{\prime})\leq n$ as otherwise the path associated to $u^{\prime}$
would go through the same vertex in $\mathbb{M}$ twice. Thus, we have a
factorization of $u$ with a loop such that removing it produces a word shorter
than $u^{\prime}$. By (4) we have that $g(u)\geq g(u^{\prime})$, and as
$\ell(u^{\prime})\leq n$, this implies that

$g(u)\geq-n\text{ for all subword $u$ of $w\in\mathcal{L}$,}$ (5)

since each transition can only contribute one $t$ or $t^{-1}$ and
$\ell(u^{\prime})\leq n$.

Let $1\leq i<j\leq\ell(w)$. We need to show that there is a constant $K\geq 0$
such that $f_{w}(j)-f_{w}(i)\geq-K$. But $f_{w}(j)-f_{w}(i)=g(u)$ for $u$
equal to the subword of $w$ consisting of taking the prefix of $w$ of length
$j$ and removing to it the prefix of length $i$. Now the result follows from
(5) and taking $K=n$. ∎

Now we can prove Proposition 4.3.

###### Proof of Proposition 4.3.

Let $(X,\pi_{H})$ be a generating set for $H$ and $\\{t,t^{-1}\\}$ a
generating set for $\mathbb{Z}$. We combine them to make
$(X^{\prime}=X\sqcup\\{t,t^{-1}\\},\pi)$ a generating set for $G$ with
evaluation map $\pi$. Let $\mathcal{L}\subseteq(X^{\prime})^{*}$ be a regular
language such that $\pi(\mathcal{L})$ is a lexicographic positive cone with
the quotient being the leading factor.

Let $\phi\colon(X^{\prime})^{*}\to\\{t,t^{-1}\\}^{*}$ consisting on deleting
the letters of $X$. This is monoid morphism, and hence $\phi(\mathcal{L})$ is
regular. Since $\mathcal{L}$ is the language of a lexicographic order,
$\phi(\mathcal{L})$ is contained in
$\\{w\in\\{t,t^{-1}\\}^{*}\mid\sharp_{t}(w)-\sharp_{t^{-1}}(w)\geq 0\\}$. By
Lemma 4.4, we get that there is a $K\geq 0$ such that
$f_{\phi(w)}(j)>f_{\phi(w)}(i)-K$ for all $w\in\mathcal{L}$ and for all $j>i$.

To see that $H$ is language-convex with respect to $\mathcal{L}$, let
$w\in\mathcal{L}$, with $\pi(w)\in H$. Then, we get that
$\sharp_{t}\phi(w)-\sharp_{t^{-1}}\phi(w)=0$. Then,
$0=f_{\phi(w)}(\ell(w))\geq\max_{i}f_{\phi(w)}(i)-K$, so
$\max_{i}f_{\phi(w)}(i)\leq K$. Also,
$\min_{i}f_{\phi(w)}(i)>f_{\phi(w)}(0)-K=-K$. It follows that for every prefix
$u$ of $w$, $|\sharp_{t}\phi(u)-\sharp_{t^{-1}}\phi(u)|\leq K$. Therefore

$\operatorname{d}_{G}(\pi(u),\pi(ut^{-\sharp_{t}\phi(u)+\sharp_{t^{-1}}\phi(u)}))\leq
K.$

Observe that $\pi(ut^{-\sharp_{t}\phi(u)+\sharp_{t^{-1}}\phi(u)})\in H$ since
the exponent ${-\sharp_{t}\phi(u)+\sharp_{t^{-1}}\phi(u)}$ cancels the $t$’s
in $u$. This shows that $H$ is language-convex.

By Proposition 2.14, we get that the restriction of the left-order to $H$ is
regular. ∎

###  4.2 Groups whose left-orders are all regular

Now we will characterize the groups whose left-orders are all regular. Since
the set of finite state automatons is countable, a left-orderable group can
have at most a countable number of regular left-orders. The following result
of Linnell [23] implies that if all the left-orders are regular, then there
should be finitely many of them.

######  Theorem 4.5.

[23] If a group admits infinitely many left-orders, then it admits uncountably
many.

The case when a group admits finitely many left-orders was classified by
Tararin [34] (see also [20, 13]). Recall that a torsion-free abelian group has
rank 1 if for any two non-identity elements $a$ and $b$ there is a non-trivial
relation between them over the integers: $na+mb=0$. Torsion-free abelian
groups of rank $1$ are, up to isomorphism, subgroups of $\mathbb{Q}$.

A group $G$ is a Tararin group if it admits a unique subnormal series

$G=G_{0}\unrhd G_{1}\unrhd\dots\unrhd G_{n}=\\{1\\}$

such that all the factors are torsion-free abelian groups of rank 1 and such
that no quotient $G_{i}/G_{i+2}$ is bi-orderable.

A group admits finitely many left-orders if and only if it is Tararin group
(see [13, Theorem 2.2.13]). Moreover, for any left-order $\prec$ on a Tararin
group with the subnormal series as above, the unique proper $\prec$-convex
subgroups are the subgroups $G_{1},G_{2},\dots,G_{n}$. It follows that there
are $2^{n}$ left-orders on $G$ and each of them is completely determined by
choosing the positivity of a non-trivial element of $G_{i}/G_{i+1}$ for
$i=1,\dots,n$. More concretely, all left-orders on $G_{i}$ are lexicographic
orders associated to the extension $G_{i+1}\to G_{i}\to G_{i}/G_{i+1}$ where
the quotient leads.

######  Lemma 4.6.

Suppose that $G$ is a finitely generated Tararin group with all the left-
orders being regular. Then $G$ is is poly-$\mathbb{Z}$.

###### Proof.

Let

$G=G_{0}\unrhd G_{1}\unrhd\dots\unrhd G_{n}=\\{1\\}$

be the unique subnormal series of $G$ where all the factors are torsion-free
abelian groups of rank 1. We have to show that all factors are cyclic. We
argue by induction on the length of the series. If the length is $0$,
$G\cong\\{1\\}$.

Suppose that the length is $>0$. Since $G$ is finitely generated, we get that
$G_{0}/G_{1}$ is a finitely generated subgroup of $\mathbb{Q}$ and hence
$G_{0}/G_{1}\cong\mathbb{Z}$. Thus, $G=G_{1}\rtimes\mathbb{Z}$.

Suppose that $G_{1}$ is finitely generated. Then by Proposition 4.3 all the
induced left-orders on $G_{1}$ are regular. Since $G$ is a Tararin group, all
left-orders on $G_{1}$ are restrictions of left-orders in $G$. Therefore, all
left-orders in $G_{1}$ are regular, and by induction $G_{1}$ is
poly-$\mathbb{Z}$ and so is $G$.

The remaining case is that $G_{1}$ is not finitely generated. Then, it follows
from Lemma 3.11 that the lexicographic orders cannot be regular. ∎

Conversely we have the following.

######  Lemma 4.7.

All left-orders on a poly-$\mathbb{Z}$ Tararin group are regular.

###### Proof.

The proof is by induction on the Hirsch length. If $h(G)=0$, then
$G\cong\\{1\\}$ and the lemma holds.

Now assume that $h(G)>0$. Let $G_{1}\unlhd G$ such that $G/G_{1}$ is infinite
cyclic. Since $G$ is a Tararin group $G_{1}$ is $\prec$-convex in $G$ for any
left-order $\prec$. Thus, any order on $G$ is a lexicographic order associated
to an extension $G_{1}$-by-$\mathbb{Z}$ in which the quotient group is the
leading lexicographic factor. Since $G_{1}$ is a poly-$\mathbb{Z}$ Tararin
group with $h(G_{1})<h(G)$, we get by induction that all the left-orders on
$G_{1}$ are regular. Recall from Example 2.16 that the two left-orders that
$\mathbb{Z}$ admits are regular. Therefore, all the left-orders of $G$ are
lexicographic extensions of a regular order on $G_{1}$ and a regular order on
$\mathbb{Z}$ and by Proposition 3.3 all left-orders of $G$ are regular. ∎

######  Remark 4.8.

Although we will not use this, it is worth pointing out that a group $G$ is
poly-$\mathbb{Z}$ Tararin if and only if there exists a unique subnormal
series

$G=G_{0}\unrhd G_{1}\unrhd\dots\unrhd G_{n}=\\{1\\}$

such that for all $i$, $G_{i}/G_{i+1}\cong\mathbb{Z}$ and $G_{i}/G_{i+2}\cong
K$ where $K=\langle a,b\mid aba^{-1}=b^{-1}\rangle$ is the Klein bottle group.

######  Theorem 4.9.

A group only admits regular left-orders if and only if it is Tararin
poly-$\mathbb{Z}$.

###### Proof.

By the previous discussion a group that admits only regular left-orders must
admit only a countable number of left-orders and therefore it must be a
Tararin group.

To finish the proof, we need to show that a Tararin group only admits regular
left-orders if and only if it is poly-$\mathbb{Z}$. That result follows from
Lemma 4.6 and Lemma 4.7. ∎

##  5 Ordering quasi-morphisms

In this section, we prove one of the main theorems of the paper and discuss
some type of one-counter positive cones. These one-counter positive cones will
be constructed through a quasi-morphism, that we will call _ordering quasi-
morphism_ , that is computable with a transducer. The interesting fact of
these one-counter positive cones, is that if $G$ has one of such cones, then
$G\times\mathbb{Z}$ will have a regular positive cone.

###  5.1 Ordering quasi-morphism

A quasi-morphism $\phi\colon G\to\mathbb{R}$ is a function that is at bounded
distance from a group homomorphism, i.e. there is a constant $D$ such that
$|\phi(g)+\phi(h)-\phi(gh)|\leq D$. A quasi-morphism naturally assigns a
positivity to elements of $G$. Dicks and S̆unić [11], found sufficient
conditions on a quasi-morphism $\phi$ so that $\phi^{-1}((0,\infty))$ is a
positive cone in the group.

The following is a slight generalization of [11, Lemma 2.3].

######  Lemma 5.1.

Let $G$ be a group and $\tau\colon G\to\mathbb{Z}$ be a function with the
following properties. For all $g,h\in G$,

  1. (i)

$C=\\{g\in G\mid\tau(g)=0\\}$ is a subgroup of $G$,

  2. (ii)

$\tau(g)=-\tau(g^{-1})$,

  3. (iii)

$\tau(g)+\tau(h)+\tau((gh)^{-1})\leq 1$.

Let $P=\\{g\in G\mid\tau(g)>0\\}$. Then $P$ is a positive cone relative to
$C$.

###### Proof.

We will first prove that $P^{-1}$ is disjoint from $P$.

$\displaystyle P^{-1}$ $\displaystyle=\\{g\in G\mid g^{-1}\in P\\}$
$\displaystyle=\\{g\in G\mid\tau(g^{-1})>0\\}$ $\displaystyle=\\{g\in
G\mid-\tau(g)>0\\}$ $\displaystyle=\\{g\in G\mid\tau(g)<0\\}.$

Thus $P\cap P^{-1}=\emptyset$. Further, since $\tau(g)=0\implies g\in C$, we
have that $G=P\sqcup P^{-1}\sqcup C$.

Now we check that $P$ is a semigroup. Let $g,h\in P$. Then $\tau(g)\geq 1$ and
$\tau(h)\geq 1$. Also, we have that $\tau(g)+\tau(h)+\tau((gh)^{-1})-1\leq 0$,
so

$\displaystyle\tau(gh)$
$\displaystyle\geq\tau(gh)+\tau(g)+\tau(h)+\tau((gh)^{-1})-1$
$\displaystyle=\tau(g)+\tau(h)-1\geq 1.$

Thus $gh\in P$. ∎

######  Definition 5.2.

A quasi-morphism $\tau\colon G\to\mathbb{Z}$ satisfying (i), (ii) and (iii) of
Lemma 5.1, will be called an ordering quasi-morphism. The subgroup $C$ of (i)
is called the _kernel_ of $\tau$.

######  Example 5.3 (Ordering quasi-morphism on free products).

Dicks and S̆unić proved in [11, Proposition 4.2] that if $G=*_{i\in I}G_{i}$
is a free product of left-ordered groups $(G_{i},\prec_{i})$, then one can
define an ordering quasi-morphism on $G$ as follows.

Let $\prec_{I}$ be a total order on the index set $I$. Given $g\in G$, the
normal form of $g$ is an expression $g=g_{1}g_{2}\dots g_{k}$, where each
$g_{i}$ (called syllable) is in some $G_{j}\setminus\\{1\\}$ and two
consecutive syllables $g_{i},g_{i+1}$ lie in different free factors. The
normal form of an element $g\in G$ is unique. For a syllable $g_{i}$, write
$\textrm{factor}(g_{i})=j$, to indicate that $g_{i}\in G_{j}$. A syllable
$g_{i}$ is positive if $1\prec_{\textrm{factor}(g_{i})}g_{i}$ and negative if
$1\succ_{\textrm{factor}(g_{i})}g_{i}$. An index jump in a normal form
$g_{1}\dots g_{k}$ is a pair of consecutive syllables $g_{i}g_{i+1}$ such that
$\textrm{factor}(g_{i})\prec_{I}\textrm{factor}(g_{i+1})$. Similarly, an index
drop in a normal form $g_{1}\dots g_{k}$ is a pair of consecutive syllables
$g_{i}g_{i+1}$ such that
$\textrm{factor}(g_{i})\succ_{I}\textrm{factor}(g_{i+1})$. Define

$\displaystyle\tau(g)$ $\displaystyle=\sharp(\text{positive syllables in
$g$})-\sharp(\text{negative syllables in $g$})$
$\displaystyle+\sharp(\text{index jumps in $g$})-\sharp(\text{index drops in
$g$}).$

Then [11, Proposition 4.2] shows that the previous function is an ordering
quasi-morphism on $G$ with trivial kernel.

######  Example 5.4 (Ordering quasi-morphism on amalgamated free products).

In [3, Theorem 17], the first author together with Dicks and S̆unić described
how to generalize the previous ordering quasi-morphism to more general groups
acting on trees. We describe here the case of amalgamated free products.
Suppose for example that $G$ is the free product of $G_{i}$, $i\in I$
amalgamated along a common subgroup $C\leqslant G_{i}$ for all $i$. For each
$i$, assume that $P_{i}$ is a positive cone relative to $C$ (i.e.
$G_{i}=P_{i}\sqcup C\sqcup P_{i}^{-1}$ and $P_{i}$ is a sub-semigroup of
$G_{i}$). Then, any element $g\in G$ can be written (uniquely fixing
transversals) as $g=g_{1}g_{2}\dots g_{k}c$ with $c\in C$ and $g_{i}\in
P_{j_{i}}\cup P_{j_{i}}^{-1}$, for $i\geq 0$. Define

$\displaystyle\tau(g)=\tau(g_{1}\dots g_{k})$
$\displaystyle=\sharp(\text{positive syllables in $g_{1}\dots
g_{k}$})-\sharp(\text{negative syllables in $g_{1}\dots g_{k}$})$
$\displaystyle+\sharp(\text{index jumps in $g_{1}\dots
g_{k}$})-\sharp(\text{index drops in $g_{1}\dots g_{k}$}).$

Thus, from [3, Theorem 17], $\tau$ is an ordering-quasimorphism on the free
product of the $G_{i}$ amalagamated over $C$ with kernel $C$.

###  5.2 Ordering quasi-morphism computable through rational transducers

We are interested in the situation when an ordering quasi-morphism can be
computed through a rational transducer.

######  Definition 5.5.

Let $G$ be a group finitely generated by $(X,\pi)$. Let $\mathbb{Z}$ be
generated by $(\\{t^{-1},t\\},\pi_{\mathbb{Z}})$. Let $\tau\colon
G\to\mathbb{Z}$ be an ordering quasi-morphism.

A $\tau$-transducer is a rational transducer $\mathbb{T}$ with input alphabet
$X$ and output alphabet $\\{t^{-1},t\\}$ such that

  1. 1.

$G=\pi(\mathbb{T}^{-1}(\\{t^{-1},t\\}^{*}))$,

  2. 2.

for every $w\in\mathbb{T}^{-1}(\\{t^{-1},t\\}^{*})$, one has that
$\tau(\pi(w))=\pi_{\mathbb{Z}}(\mathbb{T}(w))$.

In the following proposition we show that groups admitting a $\tau$-transducer
for an ordering quasi-morphism $\tau$ have one-counter positive cones.

######  Proposition 5.6.

Let $G$ be a group finitely generated by $(X,\pi)$ and $\tau\colon
G\to\mathbb{Z}$ an ordering quasi-morphism with kernel $C$. If a
$\tau$-transducer exists, then $P_{\tau}=\\{g\in G\mid\tau(g)>0\\}$ is a
$\mathsf{1C}$-positive cone relative to $C$.

In particular, if there is a $\mathsf{1C}$ language $\mathcal{L}_{C}$ such
that $\pi(\mathcal{L}_{C})=P_{C}$ is a positive cone for $C$, then
$P_{\tau}\cup P_{C}$ is a $\mathsf{1C}$ positive cone for $G$.

###### Proof.

By Lemma 5.1, $P_{\tau}$ is a positive cone relative to $C$. The language
$\mathcal{L}=\\{w\in\\{t^{-1},t\\}\mid\sharp_{t}(w)-\sharp_{t^{-1}}(w)>0\\}$
is a one-counter language (See Example 2.6). Let $\mathbb{T}$ be a
$\tau$-transducer. Since the class of one-counter languages is closed under
inverse image of rational transducers (Proposition 2.10 in view of Proposition
2.7), we have that $\tilde{\mathcal{L}}=\mathbb{T}^{-1}(\mathcal{L})$ is a
one-counter language. Now, observe that from the Definition 5.5, we get that
$\pi(\tilde{\mathcal{L}})=P_{\tau}$.

Finally, suppose that $\mathcal{L}_{C}$ is a $\mathsf{1C}$ language such that
$\pi(\mathcal{L}_{C})$ is a positive cone for $C$. Since one-counter languages
are closed under union, we get that $\tilde{\mathcal{L}}\cup\mathcal{L}_{C}$
is a one-counter language representing $P_{\tau}\cup P_{C}$. ∎

Let $\tau$ be an ordering quasi-morphism on a free product constructed as in
Example 5.4. Our objective now is to construct $\tau$-transducer when the free
factors have regular positive cones relative to $C$. The next lemma will be
useful for this construction.

######  Lemma 5.7.

Let $(X,\pi)$ be a finite generating set of $G$. Suppose that $P$ is a
$\mathsf{Reg}$-positive cone relative to $C\leqslant G$.

Then, there exists a non-deterministic finite state automaton
$\mathbb{M}=(\mathcal{S},X,\delta,s_{0},\mathcal{A})$ without $\epsilon$-moves
where the set of accepting states $\mathcal{A}$ is a disjoint union
$\mathcal{A}=\mathcal{A}^{-}\sqcup\mathcal{A}^{+}$ such that the language
$\mathcal{L}^{-}$ accepted by
$\mathbb{M}^{-}=(\mathcal{S},X,\delta,s_{0},\mathcal{A}^{-})$, and the
language $\mathcal{L}^{+}$ accepted by
$\mathbb{M}^{+}=(\mathcal{S},X,\delta,s_{0},\mathcal{A}^{+})$ satisfies that
$\pi(\mathcal{L}^{-})=P^{-1}$ and $\pi(\mathcal{L}^{+})=P$.

###### Proof.

By hypothesis, there is a regular language
$\mathcal{L}^{+}=\mathcal{L}\subseteq X^{*}$ that evaluates to $P$. Moreover,
by Lemma 2.12, there is a regular language $\mathcal{L}^{-}\subseteq X^{*}$
that evaluates to $P^{-1}$. Now there are non-deterministic finite state
automata $\mathbb{M}^{-}$ and $\mathbb{M}^{+}$ without $\epsilon$-moves
accepting $\mathcal{L}^{-}$ and $\mathcal{L}^{+}$ respectively (Remark 2.1).
Viewing this automata as directed graphs, we obtain the desired automaton by
identifying the start vertex of $\mathbb{M}^{-}$ with the start vertex of
$\mathbb{M}^{+}$ and designing that vertex to be $s_{0}$, the start vertex of
$\mathbb{M}$. In Figure 6 we see an example of this construction. ∎

$s_{0}$
---
$a$
---
$a$
---
$a^{-1}$
---
$a^{-1}$
---
$\mathbb{M}^{-}$
---
$\mathbb{M}^{+}$
---
Figure 6: Example of the construction of Lemma 5.7 for $\mathbb{Z}$, which
gives an automaton that have states for recognizing the positive cone and
states for recognizing the negative cone.

######  Proposition 5.8.

Let $I$ be a finite set. For each $i\in I$, let $G_{i}$ be a group finitely
generated by $(X_{i},\pi_{i})$ and assume that all $G_{i}$ have a common
finitely generated subgroup $C$. Let $G$ denote the free product of the
$G_{i}$ amalgamated over $C$.

Let $(Y,\pi_{C})$ be a finite generating set for $C$ and $(X=Y\sqcup\bigsqcup
X_{i},\pi)$ be a generating set for $G$ where for $x\in X_{i}$ we have that
$\pi(x)=\pi_{i}(x)$ and for $y\in Y$ we have that $\pi(y)=\pi_{C}(y)$.

For each $i\in I$, assume that $P_{i}$ is a positive cone relative to $C$.
Suppose that there is a regular language $\mathcal{L}_{i}\subseteq X_{i}^{*}$
such that $\pi_{i}(\mathcal{L}_{i})=P_{i}$.

Then $G$ has an ordering quasi-morphism $\tau\colon G\to
2\mathbb{Z}+1\cup\\{0\\}$ with kernel $C$ admitting a $\tau$-transducer
$\mathbb{T}$. Moreover, the following language

$\mathbb{T}^{-1}(\\{w\in\\{t,t^{-1}\\}^{*}:\sharp_{t}(w)-\sharp_{t^{-1}}(w)>0\\})$

evaluates onto a positive cone relative to $C$ and it is equal to

$\\{w=w_{i_{1}}\dots w_{i_{m}}z\in X^{*}\mid
i_{t}\in\\{1,\dots,n\\},i_{j}\not=i_{j+1},w_{i_{j}}\in\mathcal{L}^{+}_{i_{j}}\cup\mathcal{L}^{-}_{i_{j}},z\in
Y^{*},\tau(\pi(w))>0\\}.$

###### Proof.

By the previous Lemma 5.7, there are finite state automata
$\mathbb{M}_{i}=(\mathcal{S}_{i},X_{i},\delta_{i},s_{0i},\mathcal{A}_{i}^{-}\sqcup\mathcal{A}_{i}^{+})$
for $i=1,\dots,n$, such that the words accepted by $\mathbb{M}_{i}$ on a state
from $\mathcal{A}_{i}^{+}$ form a regular language $\mathcal{L}_{i}^{+}$
evaluating onto $P_{i}$ and the words accepted by $\mathbb{M}_{i}$ on a state
from $\mathcal{A}_{i}^{-}$ form a regular language $\mathcal{L}_{i}^{-}$
evaluating onto $P_{i}^{-1}.$

We first construct a non-deterministic finite state automaton $\mathbb{M}$
accepting the language

$\mathcal{L}:=\\{w=w_{i_{1}}\dots w_{i_{m}}z\in X^{*}\mid
i_{t}\in\\{1,\dots,n\\},i_{j}\not=i_{j+1},w_{i_{j}}\in\mathcal{L}^{+}_{i_{j}}\cup\mathcal{L}^{-}_{i_{j}},z\in
Y^{*}\\}.$

Then, we will modify this automaton $\mathbb{M}$ to produce a
$\tau$-transducer. An example of this construction can be found in Figure 7
and might help the reader check the example as they read the proof.

Note that $G-C$, the complement of $C$ in $G$, is equal to $\pi(\mathcal{L})$.
Note also that by Example 5.4, $\\{w\in\mathcal{L}\cdot
Y^{*}\mid\tau(\pi(w))>0\\}$ evaluates onto a positive cone relative to $C$ of
$G$.

We construct $\mathbb{M}$ taking the union of the automata $\mathbb{M}_{i}$,
$i=1,2,\dots,n$ with their transitions and we add an extra start state $s_{0}$
and a final state $f$ and the following $\epsilon$-moves:

  1. (I)

there is an $\epsilon$-move from $s_{0}$ to every start state each
$\mathbb{M}_{i}$.

  2. (II)

there is an $\epsilon$-move from each accepting states of $\mathbb{M}_{i}$ to
the start state of $\mathbb{M}_{j}$ with $i\neq j$.

  3. (III)

there is an $\epsilon$-move from each accepting states of $\mathbb{M}_{i}$ to
$f$.

The state $f$ is the only accepting state of $\mathbb{M}$. We add loops on $f$
with label $y$, for each $y\in Y$. It is easy to see that $\mathcal{L}$ is
accepted by $\mathbb{M}$.

Now we construct a $\tau$-transducer $\mathbb{T}$ from $\mathbb{M}$ by adding
some outputs on $T=\\{t^{-1},t\\}$ to the $\epsilon$-moves. It will be clear
from the construction that the output is a word in $t$ and $t^{-1}$ that
evaluates into an odd number, unless the input is a word in $Y$ in which case
the output evaluates to 0.

The $\epsilon$-moves of type I do not output any word.

The $\epsilon$-moves of type II output $tt$ if they start on some
$\mathcal{A}_{i}^{+}$ $i=1,\dots,j$ and go to the start state of
$\mathbb{M}_{j}$ with $i<_{I}j$. The $\epsilon$-moves of type II output
$t^{-1}t^{-1}$ if they start on some $\mathcal{A}_{i}^{-}$ $i=1,\dots,j$ and
go to the start state of $\mathbb{M}_{j}$ with $i>_{I}j$. The other
$\epsilon$-moves of type II do not output any word. Note that these encode the
contributions of index jumps and drops, and positive syllables and negative
syllable as defined in Example 5.4.

The $\epsilon$-moves of type III output a $t$ if they start on some vertex of
$\mathcal{A}^{+}_{i}$ and outputs a $t^{-1}$ if they start on some vertex of
$\mathcal{M}^{-}_{i}$.

It is easy to see that this gives a $\tau$-transducer. ∎

$a^{-1}$
---
$\epsilon$
---
$s_{0}$
---
$\epsilon$
---
$\epsilon$
---
$\epsilon$
---
$\epsilon/t^{-2}$
---
$a^{-1}$
---
$\epsilon/t^{2}$
---
$\epsilon/t$
---
$\epsilon/t$
---
$b^{-1}$
---
$b^{-1}$
---
$a$
---
$a$
---
$b$
---
$b$
---
$\epsilon/t^{-1}$
---
$\epsilon/t^{-1}$
---
$\mathbb{M}_{1}$
---
$\mathbb{M}_{2}$
---
Figure 7: The $\tau$-transducer $\mathbb{T}$ for $F_{2}=\langle
a\rangle*\langle b\rangle$ constructed following the proof of Proposition 5.8.
Observe that the three vertices on the left, and the three vertices of the
right are copies of the automaton of Figure 6. Observe also that
$\mathbb{T}^{-1}(\\{t,t^{-1}\\}^{*})$ consists of all reduced words in
$\\{a,b,a^{-1},b^{-1}\\}$.

From Propositions 5.6 and 5.8, we get the following corollary.

######  Corollary 5.9.

Let $A,B$ be groups admitting $\mathsf{Reg}$-left-orders. Then $A*B$ admits a
$\mathsf{1C}$-left-order.

This corollary is optimal in the view of a result of Hermiller and S̆unić [17]
that says that free products do not admit regular positive cones. We also note
that the first and second authors, together with J. Alonso and J. Brum [1,
Theorem 1.6], proved that certain free products with amalgamation also do not
admit regular positive cones.

To introduce an interesting example111Actions of $BS(1,m;1,n)$ on the closed
interval $[0,1]$ have been studied in [6], where it is showed that
$BS(1,m;1,n)$ has no faithful action on $[0,1]$ by diffeomorphisms. of an
amalgamated free product allowing a $\mathsf{1C}$ positive cone, let $n,m$ be
two positive integers and consider the group

$\displaystyle BS(1,m;1,n)$ $\displaystyle\mathrel{\mathop{\mathchar
0\relax}"303A}\mkern-1.2mu=\langle a,b,c\mid
aba^{-1}=b^{m},\,aca^{-1}=c^{n}\rangle$ $\displaystyle\cong\langle a,b\mid
aba^{-1}=b^{m}\rangle*_{\langle a\rangle}\langle a,c\mid
aca^{-1}=c^{n}\rangle.$

By Lemma 3.13, $BS(1,n)$ has $\mathsf{Reg}$-positive cones relative to
$\langle a\rangle$. Therefore by Proposition 5.8, $BS(1,m;1,n)$ admits a
$\mathsf{1C}$-positive cone relative to $\langle a\rangle$ and by Proposition
5.6 we get the following.

######  Corollary 5.10.

For $n,m\geq 1$, the group $BS(1,m;1,n)$ has a $\mathsf{1C}$-positive cone.

###  5.3 Embedding theorem

The main result of this section is a construction of a regular left-order on
$G\times\mathbb{Z}$ starting from an ordering quasi-morphism $\tau\colon
G\to\mathbb{Z}$. We begin describing a positive cone for $G\times\mathbb{Z}$,
and then show that it is regular (Theorem 5.12).

######  Proposition 5.11.

Let $G$ be group, $C$ be a subgroup of $G$, and $\tau\colon G\to
2\mathbb{Z}+1\cup\\{0\\}$ be an ordering quasi-morphism with kernel $C$. Let

$P=\\{(g,n)\in G\times\mathbb{Z}\mid\tau(g)+2n>0\\}.$

Then, the set $P$ is a positive cone relative to $C\times\\{0\\}$ for
$G\times\mathbb{Z}$.

###### Proof.

We define a map $\tau^{\prime}\colon G\times\mathbb{Z}\to\mathbb{Z}$ as
$\tau^{\prime}((g,n))=\tau(g)+2n$ and show that it satisfies the conditions of
Lemma 5.1. For (i), since $\tau(g)$ is odd for every $g\in G-C$, we get that
$\tau^{\prime}((g,n))=0$ if and only if $g\in C$ and $n=0$. For (ii), observe
that
$-\tau^{\prime}((g,n))=-\tau(g)-2n=\tau(g^{-1})-2n=\tau^{\prime}((g^{-1},-n))$
for all $(g,n)\in G\times\mathbb{Z}$. Finally, for (iii), observe that
$\tau^{\prime}((g,n))+\tau^{\prime}((h,m))-\tau^{\prime}((g^{-1}h^{-1},-n-m))=\tau(g)+\tau(h)-\tau(g^{-1}h^{-1})\leq
1$ for all $(g,n),(h,m)\in G\times\mathbb{Z}$. ∎

Our main theorem is the following.

######  Theorem 5.12.

Let $G$ and $\tau$ be as in Proposition 5.11. If a $\tau$-transducer exists,
then the set $P=\\{(g,n)\in G\times\mathbb{Z}\mid\tau(g)+2n>0\\}$ can be
represented by a regular language.

Note that it is implicit in the hypothesis of the existence of a
$\tau$-transducer that $G$ is finitely generated.

######  Remark 5.13.

In the proof of Theorem 5.12 we will make use of the graph descriptions of
finite state automata (Remark 2.2) and transducers (Remark 2.9). In the case
of finite state automata we will allow ourselves to label edges by words in
the input alphabet and not just letters. To get a proper automaton, one has to
change the edges labelled by a word $w$ by a path of the length $\ell(w)$
whose label is $w$. This will allow us to simplify the presentation of the
proof.

###### Proof of Theorem 5.12.

Let $\tau^{\prime}\colon G\times\mathbb{Z}\to\mathbb{Z}$ be defined by
$\tau^{\prime}((g,n))=\tau(g)+2n$, so that
$P=\\{(g,n)\mid\tau^{\prime}((g,n))>0\\}$. Let $(X,\pi)$ be a finite
generating set for $G$, and extend it to a generating set $(X\sqcup Z,\pi)$ of
$G\times\mathbb{Z}$, where the elements of $Z=\\{z,z^{-1}\\}$ evaluate to $1$
and $-1$ on $\mathbb{Z}$ respectively. Let
$\mathbb{T}=(\mathcal{S},X,T=\\{t,t^{-1}\\},\delta_{\mathbb{T}},s_{0},\mathcal{A})$
be a $\tau$-transducer. We will modify $\mathbb{T}$ to construct a finite
state automaton $\mathbb{M}$ accepting a language ${\mathcal{L}}$ that will
evaluate onto ${P}$.

We will construct $\mathbb{M}$ to have a key property, called the _balancing
property_. To make the proof easier to follow, we have divided the steps of
construction so that we will first define the features of the automaton
unrelated to the balancing property. Then, we will define the balancing
property and show why this property is important. Finally, we will finish the
construction of the automaton such that the balancing property is respected.
As a visual aid, we remark that Figure 8 exemplifies our construction starting
from the transducer of Figure 7. The reader might find helpful to check these
examples while following the construction.

We construct $\mathbb{M}$ as follows. The alphabet of the finite state
automaton $\mathbb{M}$ is $X\sqcup Z$. The set of states
$\mathcal{S}_{\mathbb{M}}$ of $\mathbb{M}$ is equal to
$\\{f\\}\cup\left(\mathcal{S}\times\\{0,1\\}\right)$ where $\mathcal{S}$ are
the states of $\mathbb{T}$ and $f$ is a new state. The initial state of
$\mathbb{M}$ is $(s_{0},0)$. The accepting states of $\mathbb{M}$ are the
states $\\{(\alpha,1)\mid\alpha\in\mathcal{A}\\}\cup\\{f\\}$.

The transition function of $\mathbb{M}$ is denoted by $\delta_{\mathbb{M}}$.
The transitions that go to $f$ are as follows. First,
$\delta_{\mathbb{M}}(f,z)=f$ (i.e. if a word is accepted, we can keep reading
$z$’s). Second $\delta_{\mathbb{M}}((s_{0},0),z)=f$ (i.e. all words of
$\\{z\\}^{+}$ are accepted). We have that
$\delta_{\mathbb{M}}((\alpha,\dagger),z)=f$ for all $\dagger\in\\{0,1\\}$ and
$\alpha\in\mathcal{A}$.

There are no more transitions from the state $f$ or going to the state $f$.

We will complete the construction of $\mathbb{M}$ such that the following
property holds.

Balancing property: For $w\in(X\sqcup Z)^{*}$, $s\in\mathcal{S}$ and
$\dagger\in\\{0,1\\}$, we have that
$(s,\dagger)\in\delta_{\mathbb{M}}((s_{0},0),w)$ implies that
$\tau^{\prime}(\pi(w))=\dagger$.

Assuming the Balancing property we see that $\mathbb{M}$ only accepts words
that represent elements of $P$. Indeed, if a word $w$ is accepted at the
accepting state $(\alpha,1)$ with $\alpha\in\mathcal{A}$, then by the
Balancing property we have that $\tau^{\prime}(\pi(w))=1$, so $\pi(w)\in P$.
On the other hand, if $w$ is accepted at the accepting state $\\{f\\}$, then,
since all the edges in $\mathbb{M}$ that end in the accepting state $\\{f\\}$
have label $z$, we can assume that $w$ is of the form $w^{\prime}z^{n}$ where
$w^{\prime}$ does not end with $z$. Now, by the construction of transitions to
$\\{f\\}$, we see that $f\notin\delta_{\mathbb{M}}((s_{0},0),w^{\prime})$.
Suppose that $(s,\dagger)\in\delta_{\mathbb{M}}((s_{0},0),w^{\prime})$ for
some $s\in\mathcal{S}$. By the Balancing property we have that
$\tau^{\prime}(\pi(w^{\prime}))=\dagger\in\\{0,1\\}$, so
$\tau^{\prime}(\pi(w))=\tau^{\prime}(\pi(w^{\prime}z^{n}))=\tau^{\prime}(\pi(w^{\prime}))+2n>0$.
This implies that $\pi(w)\in P$ as well, and therefore that
$\pi(\mathcal{L})\subseteq P$.

We now define the other transitions so that the Balancing property is
satisfied. Recall that $\delta_{\mathbb{T}}$, the transition function of
$\mathbb{T}$, is of the form $\delta_{\mathbb{T}}\colon\mathcal{S}\times
X\to\textrm{Finite Subsets}(\mathcal{S}\times T^{*})$. We use $\pi_{T}$ to
denote the evaluation from $T^{*}=\\{t,t^{-1}\\}^{*}$ to $\mathbb{Z}$. Recall
our convention of Remark 5.13 as we will define the new transitions of
$\mathbb{M}$ as edges labelled by words. For each $\dagger\in\\{0,1\\}$,
$s\in\mathcal{S}$ and $x\in X\cup\\{\epsilon\\}$, and each edge in
$\mathbb{T}$ from $s$ to $r$ with label $x/u$ we now define a corresponding
edge in $\mathbb{M}$ starting from $(s,\dagger)$ and ending in
$(r,\dagger^{\prime})$ with label $xv$. The number
$\dagger^{\prime}\in\\{0,1\\}$ and the word $v\in Z^{*}$ are defined below
depending on the values of $\pi_{T}(u)$ and $\dagger$.

Suppose that $\pi_{T}(u)=2k+\eta$ with $\eta\in\\{0,1\\}$. We would like to
have the property that $\dagger^{\prime}=\pi_{T}(u)+\dagger+2\pi_{Z}(v).$ To
do so, we define $\dagger^{\prime}$ and $v$ as follows.

  * •

if $\dagger=0$ then $\dagger^{\prime}=\eta$ and $v=z^{-k}$,

  * •

if $\dagger=1$ and $\eta=0$ then $\dagger^{\prime}=1$ and $v=z^{-k}$,

  * •

if $\dagger=1$ and $\eta=1$ then $\dagger^{\prime}=0$ and $v=z^{-k-1}$.

Note that when we write $z^{-k}$, we mean the word in $Z$ which is either a
$k$-repetition of $z$ or $z^{-1}$.

There are no more states or transitions (i.e the transitions not described go
to the emptyset) and this completes the description of $\mathbb{M}$.

We now check that the Balancing property holds. Let $w\in(X\sqcup Z)^{*}$ and
$(\alpha,\dagger)\in\delta_{M}((s_{0},0),w)$. Then $w$ is the label of a path
in $\mathbb{M}$ from $(s_{0},0)$ to $(\alpha,\dagger)$. As each label of each
edge of $\mathbb{M}$ is of the form $xv$ with $x\in X\cup\\{\epsilon\\}$ and
$v\in\\{z,z^{-1}\\}^{*}$, we can write $w$ as $x_{1}v_{1}x_{2}v_{2}\dots
x_{\ell}v_{\ell}\in\mathcal{L}$ such that $x_{i}\in X\cup\\{\epsilon\\}$,
$v_{i}\in Z^{*}$, and the sequence $(x_{i}v_{i})_{i}$ is the sequence of the
labels of the edges in the path in $\mathbb{M}$ defined by $w$. We check the
Balancing property by induction on $\ell$.

For $\ell=1$, we have that $x_{1}v_{1}$ labels an edge of $\mathbb{M}$
starting at $(s_{0},0)$ and ends in some $(s,\dagger)$. Such edge comes from
an edge in $\mathbb{T}$ from $s_{0}$ with label $x_{1}/u$ to $s$. Moreover, we
have that if $\pi_{T}(u)=2k+\eta$ with $\eta\in\\{0,1\\}$ then $v_{1}=z^{-k}$
and $\dagger=\eta$. Observe that
$\tau^{\prime}(\pi(w))=\tau^{\prime}(\pi(x_{1}v_{1}))=\tau(\pi(x_{1}))-2k=2k+\dagger-2k=\dagger.$

We now show that the case $\ell$ implies the case $\ell+1$. By induction
hypothesis $(s,\dagger)\in\delta_{\mathbb{M}}((s_{0},0),x_{1}v_{1}\dots
x_{\ell}v_{\ell})$ and $\tau^{\prime}(\pi(x_{1}v_{1}\dots
x_{\ell}v_{\ell}))=\dagger$. Then, $x_{\ell+1}v_{\ell+1}$ labels and edge of
$\mathbb{M}$ starting at $(s,\dagger)$ and ends in some
$(s^{\prime},\dagger^{\prime})$. Such edge comes from an edge in $\mathbb{T}$
from $s$ with label $x_{\ell+1}/u$ to $s^{\prime}$. If $\pi_{T}(u)=2k+\eta$
with $\eta\in\\{0,1\\}$ then $v_{\ell+1}$ and $\dagger^{\prime}$ are
determined by $\dagger$, $\eta$ and $k$. We have

$\displaystyle\tau^{\prime}(\pi(w))$ $\displaystyle=\tau(\pi(x_{1}x_{2}\dots
x_{\ell}x_{\ell+1}))+2\pi_{Z}(v_{1}\dots v_{\ell+1})$
$\displaystyle=\tau(\pi(x_{1}x_{2}\dots
x_{\ell}))+\pi_{T}(u)+2\pi_{Z}(v_{1}\dots v_{\ell})+2\pi_{Z}(v_{\ell+1})$
$\displaystyle=\dagger+\pi_{T}(u)+2\pi_{Z}(v_{\ell+1})=\dagger^{\prime}$

Therefore the Balancing property holds.

Let $\mathcal{L}$ be the language accepted by $\mathbb{M}$. It was observed in
the paragraph after defining the Balancing property that
$\pi(\mathcal{L})\subseteq P$.

On the other hand, to see that $P\subseteq\pi(\mathcal{L})$, observe first
that given $(g,n)\in P$ there is some $w\in\mathbb{T}^{-1}(T^{*})$ such that
$\pi_{X}(w)=g$. Suppose that a possible way for $\mathbb{T}$ to process
$w=x_{1}\dots x_{\ell}$ is a sequence of states of $\mathbb{T}$ with outputs
in $T^{*}$ as follows

$s_{0},\;(s_{1},u_{1})\in\delta_{\mathbb{T}}(s_{0},x_{1}),\;(s_{2},u_{2})\in\delta_{\mathbb{T}}(s_{1},x_{2}),\dots,\;(s_{\ell},u_{\ell})\in\delta_{\mathbb{T}}(s_{\ell-1},x_{\ell})$

with $s_{i}\in\mathcal{S}$. Consider the word

${w}^{\prime}=x_{1}z^{\nu_{1}}x_{2}z^{\nu_{2}}\dots
x_{\ell}z^{\nu_{\ell}}\text{ and the sequence
}\dagger_{0}=0,\dagger_{1},\dots,\dagger_{\ell}\text{ in }\\{0,1\\}$

where the $\nu_{i}$’s and $\dagger_{i}$’s are determined by
$\dagger_{i+1}=\tau(\pi(x_{1}\dots
x_{i}))+\dagger_{i}+2(\nu_{1}+\dots+\nu_{i})$. Then, by the definition of the
transitions of $\mathbb{M}$ we see that, $(s_{i+1},\dagger_{i+1})$ is the end
point of an edge of $\mathbb{M}$ from $(s_{i},\dagger_{i})$ with label
$x_{i+1}z^{\nu_{i}+1}$.

Let now $m=n-\sum\nu_{i}$. Observe first that $\pi(w^{\prime}z^{m})=(g,n)$.
Indeed, $\pi(w^{\prime}z^{m})=\pi(x_{1}\dots x_{\ell})\pi(z^{\nu_{1}}\dots
z^{\nu_{\ell}}z^{m})=(g,m+\sum\nu_{i})=(g,n)$. Finally, observe that
$w^{\prime}z^{m}\in\mathcal{L}$. By the Balancing property and construction of
$w^{\prime}$ we have that
$(s_{\ell},\dagger_{\ell})\in\delta_{\mathbb{M}}((s_{0},0),w^{\prime})$ with
$\tau^{\prime}(\pi(w^{\prime}))=\dagger_{\ell}\in\\{0,1\\}$. As $(g,n)\in P$
and
$\tau^{\prime}((g,n))=\tau^{\prime}(\pi(w^{\prime}))+2m=\dagger_{\ell}+2m>0$
we have that $m\geq 0$ if $\dagger_{\ell}=1$ and $m>1$ if $\dagger_{\ell}=0$.
We have that if $m=0$, $(s_{\ell},\dagger_{\ell})$ is an accepting state, and
if $m>0$ then $\delta_{\mathbb{M}}((s_{\ell},\dagger_{\ell}),z^{m})=f$. In
either case
$\delta_{\mathbb{M}}((s_{\ell},\dagger_{\ell}),z^{m})\subseteq\delta_{\mathbb{M}}((s_{0},0),w^{\prime}z^{m})$
contains an accepting state and $w^{\prime}z^{m}\in\mathcal{L}$. ∎

$0$
---
$+1$
---
$0$
---
$+1$
---
$0$
---
$+1$
---
$0$
---
$+1$
---
$0$
---
$+1$
---
$s_{0}$
---
$f$
---
$z$
---
$z$
---
$z$
---
$a$
---
$a$
---
$a^{-1}$
---
$a^{-1}$
---
$0$
---
$+1$
---
$0$
---
$+1$
---
$0$
---
$+1$
---
$b$
---
$b$
---
$b^{-1}$
---
$b^{-1}$
---
$\epsilon$
---
$\epsilon$
---
$\epsilon$
---
$\epsilon$
---
$z^{-1}$
---
$z^{-1}$
---
$\epsilon$
---
$\epsilon$
---
$z$
---
$z$
---
$z$
---
$\epsilon$
---
$\epsilon$
---
$\epsilon$
---
$z$
---
$\epsilon$
---
$\epsilon$
---
$z^{-1}$
---
$z$
---
$\epsilon$
---
$a$
---
$a$
---
$z^{-1}$
---
$b$
---
$b$
---
$a^{-1}$
---
$a^{-1}$
---
$z$
---
$b^{-1}$
---
$b^{-1}$
---

Figure 8: A finite state automaton for $F_{2}\times\mathbb{Z}$. It looks
similar to Figure 7, with each state doubled and extra arrows added. The state
$(s_{0},1)$ could have been deleted as it has no incoming arrow, but we have
chosen to keep it in the picture as it is an state and arrows that appear from
the construction.

######  Theorem 5.14.

Let $G_{1},G_{2},\dots G_{n}$ be finitely generated groups with a common
subgroup $C$ such that each $G_{i}$ admits a $\mathsf{Reg}$-positive cone
relative to $C$ and $C$ admits a $\mathsf{Reg}$-positive cone. Let $G$ be the
free product of the $G_{i}$’s amalgamated over $C$. Then $G\times\mathbb{Z}$
admits a $\mathsf{Reg}$-left-order.

###### Proof.

By Proposition 5.8, $G$ admits a $\tau$-transducer where $\tau$ is an ordering
quasi-morphism $\tau\colon G\to 2\mathbb{Z}+1\cup\\{0\\}$ with kernel $C$. Now
by Theorem 5.12, $G\times\mathbb{Z}$ has $\mathsf{Reg}$-positive relative to
$C\times\\{0\\}$. Finally, since $C\cong C\times\\{0\\}$ has
$\mathsf{Reg}$-positive cones, we get from Lemma 2.21 that $G\times\mathbb{Z}$
has relative positive cones. ∎

######  Corollary 5.15.

Let $A,B$ be groups admitting $\mathsf{Reg}$-left-orders. Then
$(A*B)\times\mathbb{Z}$ admits $\mathsf{Reg}$-left-orders.

Also from the previous theorem, and by the discussion prior to Corollary 5.10
we have

######  Corollary 5.16.

For $n,m\geq 1$, the group $BS(1,m;1,n)\times\mathbb{Z}$ has a
$\mathsf{Reg}$-positive cone.

Another interesting application of the results of this paper, is the
following.

######  Theorem 5.17.

Suppose that $G$ is a (non-abelian finitely generated free)-by-$\mathbb{Z}$
group. Then, no lexicographic left-order $\prec$ on $G$ where $\mathbb{Z}$
leads is regular.

However, there is a lexicographic left-order on $G$ where $\mathbb{Z}$ leads
that is one-counter and extends to regular left-order on $G\times\mathbb{Z}$.

###### Proof.

From Proposition 4.3, if $G$ admits a regular lexicographic left-order where
$\mathbb{Z}$ leads, then there will be a regular order on a finitely generated
free group, contradicting the theorem of Hermiller and S̆unić [17] that says
that non-abelian free groups do not admit regular positive cones.

Suppose that $f\colon G\to\mathbb{Z}$ is a surjective homomorphism with kernel
$F_{n}$, a free group of rank $n$. By Proposition 5.8 (see also [32, 33]),
there is an ordering-quasimorphism $\tau\colon F_{n}\to
2\mathbb{Z}+1\cup\\{0\\}$ with trivial kernel admitting a $\tau$-transducer.
By Proposition 5.6, $F_{n}$ admits a one-counter positive cone, and by
Proposition 3.3, since $\mathbb{Z}$ has regular orders, $G$ has a one-counter
positive cone.

By Theorem 5.14, we see that $F_{n}\times\mathbb{Z}$ has a regular positive
cone. Note that $F_{n}\times\mathbb{Z}$ is the kernel of $\tilde{f}\colon
G\times\mathbb{Z}\to\mathbb{Z}$ given by $(g,n)\mapsto f(g)$. As $\mathbb{Z}$
has regular positive cones, Proposition 3.3 guaranties that
$G\times\mathbb{Z}$ has regular positive that is lexicographic with leading
factor the quotient, when viewing $G\times\mathbb{Z}$ as a
($F_{n}\times\mathbb{Z}$)-by-$\mathbb{Z}$ extension. The restriction of this
order on $G$ is still lexicographic. ∎

Some families of groups that are known to be (finitely-generated free)-by-
cyclic are provided in the next corollary. We first recall the notion of Artin
group.

######  Definition 5.18 (Artin groups and defining graphs).

Let $\Gamma$ be a finite simplicial graph with edges labeled by integers
greater or equal to two. We associate to $\Gamma$ a group $A(\Gamma)$ whose
presentation has generators corresponding to the vertices of $\Gamma$ and the
relations are of the form

$\underbrace{aba\dots}_{n\text{ letters }}=\underbrace{bab\dots}_{n\text{
letters }}$

where $\\{a,b\\}$ is an edge of $\Gamma$ labeled with $n$. The graph $\Gamma$
is called the _defining graph_ of the _Artin group_ $A(\Gamma)$.

######  Corollary 5.19.

Let $A(\Gamma)$ be an Artin group whose defining graph $\Gamma$ is a tree.
Then $G$ has one-counter left-orders and $G\times\mathbb{Z}$ has regular left-
orders.

###### Proof.

By a result of Hermiller and Meier [16], $A(\Gamma)$ admits a short exact
sequence of the form $1\to F_{m}\to A(\Gamma)\to\mathbb{Z}\to 1$ (and in fact
$m=\sum_{e_{i}\in\Gamma}(n_{i}-1)$, where $n_{i}$ is the label of the edge
$e_{i}$). Hence, $A(\Gamma)$ falls into the hypothesis of Theorem 5.17 and the
conclusion follows. ∎

######  Definition 5.20.

A right-angled Artin group is an Artin group whose defining graph only has
edges with label 2.

######  Corollary 5.21.

Let $G$ be a right-angled Artin group based on a connected graph with no
induced subgraph isomorphic to $C_{4}$ (the cycle with $4$ edges) or $L_{3}$
(the line with 3 edges). Then $G$ has regular left-orders.

###### Proof.

The proof is by induction on the size of the defining graph $\Gamma$. If the
graph has one vertex, then $G\cong\mathbb{Z}$ and we know that $\mathbb{Z}$
only has regular left-orders. Now suppose that the defining graph has more
than one vertex. Droms [12, Lemma] observed that in that case there is a
vertex connected to all other vertex of the graph $\Gamma$. That is
$G\cong\mathbb{Z}\times H$ where $H$ is right-angled Artin group based on a
graph $\Gamma^{\prime}$ that contains no induced subgraph isomorphic to
$C_{4}$ or $L_{3}$. Note that $\Gamma^{\prime}$ has fewer vertices that
$\Gamma$. Then, by induction, each connected component of $\Gamma^{\prime}$
defines a subgroup of $H$ that has regular left-orders. If $\Gamma^{\prime}$
is connected, then $H$ has regular left-orders and so does $G$. If
$\Gamma^{\prime}$ is not connected, then $H=A(\Gamma^{\prime})$ is a free
product of groups having regular left-orders. By Proposition 5.8 and Theorem
5.12 we get that $H\times\mathbb{Z}$ has regular left-orders. ∎

######  Remark 5.22.

It follows from [17, Theorem 4], that there is no positive cone $P$ on a
right-angled Artin group defined over a graph of diameter $\geq 3$ such the
set of all geodesic words in the standard generating set that represent
elements of $P$ form a regular language.

We remark that all the defining graphs of considered in Corollary 5.21 have
diameter at most two. We also point out that the words of the regular left-
orders constructed for $F_{2}\times\mathbb{Z}$ do not induce (uniformly
quasi)-geodesic paths.

##  Appendix A Appendix: pre-images of positive cones

In this appendix, we explore the following definition.

######  Definition A.1.

Let $\mathcal{C}$ be a class of languages. Let $G$ be a group finitely
generated by $(X,\pi)$ and $\prec$ a left-order on $G$. We say that $\prec$ is
a $\mathcal{C}$-preimage left-order if the language
$\pi^{-1}(P_{\prec})\in\mathcal{C}$.

Note that the difference between a $\mathcal{C}$-left-order and a
$\mathcal{C}$-preimage left-order is that given an element $g\in P_{\prec}$, a
$\mathcal{C}$-left-order does not contain all words which map to $g$, but has
at least one. For a given class $\mathcal{C}$, a left-order might be a
$\mathcal{C}$-left-order but not a $\mathcal{C}$-preimage left-order. In fact,
for the lower classes in the Chomsky hierarchy such as $\mathsf{Reg}$ and
$\mathsf{CF}$, we will see that there are few examples of
$\mathcal{C}$-preimage left-orders. On the other hand, for the class of
recursively enumerable languages, the highest in the Chomsky hierarchy, we
will see that admitting a $\mathcal{C}$-left-order and is equivalent to
admitting $\mathcal{C}$-preimage left-orders if $G$ is finitely presented.

The first observation follows from Lemma 2.11.

######  Lemma A.2.

If $\mathcal{C}$ is class of languages closed under inverse homomorphisms,
then having a $\mathcal{C}$-preimage left-order is independent of generating
set.

One of the advantages of studying $\mathcal{C}$-preimage left-orders compared
to $\mathcal{C}$-left-orders is that being a $\mathcal{C}$-preimage left-order
is preserved when passing to subgroups.

######  Lemma A.3.

Let $\mathcal{C}$ a class of languages closed under inverse homomorphism and
intersection with regular languages.

Let $H$ be a finitely generated subgroup of $G$. If $\prec$ is a
$\mathcal{C}$-preimage left-order on $G$ then the induced order on $H$ is also
a $\mathcal{C}$-preimage left-order.

###### Proof.

By the previous lemma, we can assume that we have a finite generating set
$(X,\pi)$ of $G$, and that there is a subset of $Y$ of $X$ such that
$(Y,\pi_{Y}=\pi|_{Y^{*}})$ is a generating set for $H$. Thus, if $P$ is a
positive cone of $G$ with $\pi^{-1}(P)$ in the class $\mathcal{C}$, we get
that $\pi_{Y}^{-1}(H\cap P)=\pi^{-1}(P)\cap Y^{*}$ is in $\mathcal{C}$. ∎

Now we will see that the classes of $\mathsf{Reg}$-preimage left-orders and
$\mathsf{CF}$-preimage orders are quite limited.

Let $(X,\pi)$ be a finite generating set of a group $G$. Recall that the set
$\mathrm{WP}(G,X)=\\{w\in X^{*}:\pi(w)=1\\}=\pi^{-1}(\\{1\\})$ is called the
the word problem of $G$ (with respect to $X$). A classic result of Anisimov
[2] states that $\mathrm{WP}(G,X)$ is regular if and only if $G$ is finite.

######  Proposition A.4.

A finitely generated group $G$ has a $\mathsf{Reg}$-preimage left-order if and
only if it is trivial.

###### Proof.

Let $(X,\pi)$ be finite generating set for $G$. If $G$ is trivial, the
positive cone is the empty set.

Suppose that $P$ is a $\mathsf{Reg}$-preimage positive cone. That is,
$\pi^{-1}(P)$ is a regular language. By Lemma 2.12, we have that
$\pi^{-1}(P^{-1})$ is also a regular language. Since
$WP(G,X)=X^{*}\setminus(\pi^{-1}(P^{-1})\cup\pi^{-1}(P))$, we get that
$WP(G,X)$ is regular, and by Anisimov’s theorem $G$ must be finite. Finally, a
finite left-orderable groups must be trivial. ∎

We now move on to the case of $\mathsf{CF}$-preimage left-orders. We start
showing that this class contains free groups.

######  Proposition A.5.

Finitely generated free groups have a $\mathsf{CF}$-preimage left-orders.

###### Proof.

Let $F$ be a finitely generated free group with generating set $X$. From
Corollary 5.9 there exists a $\mathsf{1C}$-language $\mathcal{L}\subseteq
X^{*}$ representing the positive cone $P$ of $F$. In fact, $\mathcal{L}$ can
be taken to be a sublanguage of reduced words over $X$ (see Proposition 5.8 or
Figure 7 for the rank 2 free group case).

Let $e$ be a symbol disjoint from $X$. Define $\phi:(X\cup\\{e\\})^{*}\to
X^{*}$ to be the monoid homomorphism sending $e$ to the empty word. Then
$\phi^{-1}(\mathcal{L})$ is the language of words in $w\in\mathcal{L}$ with
arbitrary insertions of symbols $e$ in between its letters. Let $s$ be a
substitution (in the sense of Hopcroft, Motwani, and Ullman [19]) such that
$s(e)=\text{WP}(F)$, meaning we replace the symbol $e$ with a word over $X$
which is equal to the identity in $F$, and $s(x)=x$ for $x\in X$ otherwise.

We claim that $s(\phi^{-1}(\mathcal{L}))$ is a context-free language which is
the preimage of $P$ under $\pi_{X}$. The language is context-free by closure
properties of context-free languages under substitution and inverse
homomorphism (see for example [19, Theorem 7.23 and Theorem 7.30]). Moreover,
$\pi_{X}(s(\phi^{-1}(\mathcal{L})))=\pi_{X}(\mathcal{L})$ by construction, as
each $e$-substitution is a word which is equal to the identity. Therefore,
$s(\phi^{-1}(\mathcal{L}))\subseteq\pi_{X}^{-1}(P)$. For the converse, observe
that for every positive element $g\in P$, there is a reduced word in
$w\in\mathcal{L}$ such that $\pi(w)=g$. The preimage of $g$ under the
evaluation map $\pi_{X}$ is $w$ with arbitrarily many insertion of words which
are equal to the identity. Therefore, $\pi^{-1}_{X}(g)\in
s(\phi^{-1}(\mathcal{L}))$, so $\pi^{-1}(P)\subseteq
s(\phi^{-1}(\mathcal{L}))$. ∎

However, the class of $\mathsf{CF}$-pre-image left-orders is still very
limited. Indeed, all finitely generated abelian subgroups of a group admitting
a $\mathsf{CF}$-preimage positive cone must be cyclic.

######  Proposition A.6.

$\mathbb{Z}^{2}$ does not have $\mathsf{CF}$-preimage left-orders. In
particular, if $G$ has a $\mathsf{CF}$-preimage left-order, then it does not
contain $\mathbb{Z}^{2}$ as a subgroup.

###### Proof.

Positive cones of $\mathbb{Z}^{2}$ are very well understood. See for example
[13, Section 1.2.1] and references therein. We view $\mathbb{Z}^{2}$ as
subspace of $\mathbb{R}^{2}$. A positive cone in $\mathbb{Z}^{2}$ is
determined by a line in $\mathbb{R}^{2}$ through the origin, and then
selecting one of the half-space (excluding the origin) delimited by the line.
If the slope of the line is rational, causing some elements of
$\mathbb{Z}^{2}$ to lie on the line, then one has to choose half of the line
(starting from but excluding the origin) to be in the positive cone as well.

Figure 9: $\mathbb{Z}^{2}$ with rational line and choices of orientation

By Lemma A.2 we may choose any generating set of $\mathbb{Z}^{2}$ for this
proof. Take $a$ and $b$ to be standard basis vectors, in the $x$ and $y$
direction respectively. We use $A$ and $B$ to denote $a^{-1}$ and $b^{-1}$
respectively.

Suppose that the half-space defining the positive cone is
$\texttt{y}>\lambda\texttt{x}$, where $\lambda\in\mathbb{R}$. The case
$\texttt{y}<\lambda\texttt{x}$ is analogous. If $\lambda\in\mathbb{Q}$, we
choose $\texttt{y}=\lambda\texttt{x}$, $\texttt{x}>0$ to be in the positive
cone. Again, the case $\texttt{x}<0$ is analogous.

Therefore, we can assume that words evaluating to the positive cone consists
on

$\left\\{w\in\\{a,b,A,B\\}^{*}\,\middle|\begin{array}[]{c}\text{ either
}(\sharp_{b}(w)-\sharp_{B}(w))>\lambda(\sharp_{a}(w)-\sharp_{A}(w))\text{ or
}\\\ ((\sharp_{b}(w)-\sharp_{B}(w))=\lambda(\sharp_{a}(w)-\sharp_{A}(w))\text{
and }(\sharp_{a}(w)-\sharp_{A}(w))>0)\end{array}\right\\}.$

Suppose the previous set is a $\mathsf{CF}$ language. Then if we take the
intersection with the regular language $a^{*}b^{*}A^{*}B^{*}$ we get that

$\mathcal{L}=\\{a^{\alpha}b^{\beta}A^{\gamma}B^{\delta}\,|\,(\beta-\delta)>\lambda(\alpha-\gamma)\text{
or }((\beta-\delta)=\lambda(\alpha-\gamma)\text{ and }(\alpha-\gamma)>0)\\}$

is $\mathsf{CF}$. We now use the pumping lemma for $\mathsf{CF}$-languages
(see [19] for example) to derive a contradiction. Suppose that the pumping
length is $p$ and take a word $s=a^{c}b^{d}A^{e}B^{f}\in\mathcal{L}$ with
$c,d,e,f>p$. The pumping lemma says that $s$ can be factorized as $s=uvwxy$
(i.e. $u,v,w,x,y$ are all subwords of $s$), with $\ell(vwx)\leq p$, and with
at least $v$ or $x$ is non-empty, such that for all $i\geq 0$ $uv^{i}wx^{i}y$
belongs to $\mathcal{L}$. Let $\texttt{v}=\pi(v)+\pi(x)$ be a vector in
$\mathbb{Z}^{2}$. Let $\texttt{p}=\pi(s)$ a point of $\mathbb{Z}^{2}$. Note
that the points $\pi(uv^{i}wx^{i}y)$ for $i\geq 0$ lie on the line
$L=\\{\texttt{p}+\mu\texttt{v}:\mu\in\mathbb{R}\\}$ that goes through $\pi(s)$
and there are points a $\pi(uv^{i}wx^{i}y)$ on both sides of
$L\setminus\\{\pi(s)\\}$, for instance $\pi(uwy)$ and $\pi(uv^{2}wx^{2}y)$.
Remark that the line $L$ has rational slope.

Now take $s=a^{c}b^{d}A^{e}B^{f}$ with $c,d,e,f>p$ and such that $\pi(s)$ is
very close to the line $\texttt{y}=\lambda\texttt{x}$ (or on the line if
$\lambda$ is rational) and with the property that for any line $L$ going
through $\pi(s)$ there is a half-line of $L\setminus\\{\pi(s)\\}$ such that
all rational points on this half-line are outside of $P$. If $\lambda$ is not
rational, then we can find such point $\pi(s)$ by taking a rational
approximation of $\lambda$. If $\lambda$ is rational, we take $\pi(s)$ to be
the first point with integer coordinates on the set
$\\{(\texttt{x},\texttt{y})\mid\texttt{y}=\lambda\texttt{x},\texttt{x}>0\\}$.

Then for that $s$, some choice of $i$ on the pumping lemma will give an
element not in $\mathcal{L}$. Indeed, evaluating pumped words with $i=0$ and
$i=2$, we get two different points on $\mathbb{Z}^{2}$ that lie on a line
going through $\pi(s)$, and moreover these points lie in different components
of the line minus $\pi(s)$, thus some of them are in the negative cone. This
gives the desired contradiction.

From Lemma A.3 we get that no group with $\mathsf{CF}$-preimage left-orders
can contain $\mathbb{Z}^{2}$. ∎

The celebrated result of Muller and Schupp [25] states that the word problem
of a group is context-free if and only if $G$ is virtually free.
Unfortunately, the argument of Lemma A.4, does not generalize directly to
context-free languages, since this class is not closed under complement. Thus,
it is natural to ask the following.

######  Problem A.7.

Is there a non-free group admitting a $\mathsf{CF}$-preimage left-order?

A simpler, but related question is the following.

######  Problem A.8.

Is there a non-cyclic group admitting a $\mathsf{1C}$-preimage left-order?

Recall that the class of languages that are complements of a context-free
languages are called co-context-free and we denote it by co-$\mathsf{CF}$. The
class of groups for which $WP(G,X)$ is co-$\mathsf{CF}$ was first studied by
Holt, Rees, Röver, and Thomas [18]. We have the following easy observation.

######  Proposition A.9.

Let $G$ be finitely generated group with $\mathsf{CF}$-preimage left-orders.
Then the word problem of $G$ is in the class co-$\mathcal{CF}$.

###### Proof.

Since $\mathsf{CF}$ is closed under reversal and homomorphisms, we get that
the full language of $\prec$-negative words is $\mathsf{CF}$. Since the class
$\mathsf{CF}$ is closed under union, $WP(G)$ is co-$\mathcal{CF}$. ∎

The class of groups of co-$\mathsf{CF}$ word problem is closed by taking
finite direct products, taking restricted standard wreath products $\oplus
H\rtimes Q$ with $Q$ having context-free word problem, passing to finitely
generated subgroups, and passing to finite index overgroups [18]. In [18,
Theorem 13] it is also shown that a Baumslag-Solitar group has a
co-$\mathsf{CF}$ word problem if and only if it is virtually abelian. Thus, we
obtain the following.

######  Corollary A.10.

Baumslag-Solitar groups do not admit $\mathsf{CF}$-preimage left-orders.

Note that $\mathbb{Z}^{2}$ embeds into every Baumslag-Solitar group, except
$BS(1,n)$ with $n\neq\pm 1$ [22, Proposition 7.11], thus, Corollary A.10 does
not follow from Proposition A.6 on the solvable case.

Lehnert and Schweitzer [21] showed that Thompson’s group $V$ has
co-$\mathsf{CF}$ word problem, and a conjecture of Lehnert can be formulated
as all groups with co-$\mathsf{CF}$ word problem are finitely generated
subgroups of $V$ [5]. Thus, a potential place to look for examples of groups
with $\mathsf{CF}$-preimage left-orders are left-orderable subgroups of $V$
that do not contain $\mathbb{Z}^{2}$.

##### Positive cones whose preimage is recursively enumerable.

We now recall some definitions and results that we will need.

######  Definition A.11.