Fresh Orderings of Groups

G. C. Smith  O. M. Tabachnikova

January 10, 1998

Abstract

The classes of freshly and well freshly orderable groups are introduced, and various closure properties obtained. A short-lex ordering is a well fresh order on a free group.

Introduction

The class of unique product groups (U.P. groups) has attracted attention because of a connection with a well-known problem in the theory of group rings. These are groups G with the property that if A and B are a pair of finite subsets of G, each of size at least two, then there is an element ab of AB which is uniquely expressed via a ∈ A, b ∈ B. It is an open question as to whether all torsion-free groups have integral group rings containing no zero-divisors, but clearly the answer is affirmative for U.P. groups. There are examples known of torsion-free groups which are not U.P. groups ([1], [2]). We introduce a possible strengthening of the U.P. condition.

Definition 1 A fresh order < of a group G is a linear order of the underlying set G with the property that if P is a non-empty finite subset of G, then

P g ⊈ ⋃_{x<g} P x.

The reason for the terminology is that (informally) each multiplication by g yields at least one “fresh” element of P g. One can show that if the ordering is allowed to vary with P, we obtain a condition equivalent to the U.P. condition – we thank D. S. Richardson for this observation. Left and right invariant orderings of groups are fresh orders, by Proposition 1.

A group which admits a fresh ordering is said to be freshly orderable. We let F denote this class of groups, and W denote the class of groups which admit a fresh well ordering. Thus W ⊆ F, but W ≠ F by Proposition 2. Notice if 1 ≠ x ∈ G and P = ⟨x⟩ is finite, then P 1 = P x so G ∉ F. Thus if G ∈ F, then G is torsion-free. It is clear that F and W are closed under taking subgroups, but not closed under quotients. We will show that F and W are closed under forming extensions and arbitrary Cartesian products, and that one-sided invariant group orderings are fresh orderings. Free groups are orderable and so are in F. We show that short-lexicographic orderings of free groups are fresh, and thus that free groups are in W.

Results

Left or right invariant group orderings (in the sense of the theory of ordered groups) are never well orders, but they do yield fresh orders.

Proposition 1 A left or right invariant ordering < of a group G is a fresh ordering.

We have two results about specific groups:

Proposition 2 (i) The infinite cyclic group has 2^{ℵ_{0}} fresh orderings, all except for two of which are well orders.

(ii) The additive group of rational numbers is in F but is not in W.

Thus the classes F and W do not coincide.

Proposition 3 Let X be either W or F.

(i) If H ≤ G ∈ X , then H ∈ X .

(ii) If K ⊴ G and K, G/K ∈ X , then G ∈ X .

(iii) If G_{i} ∈ X ∀i ∈ I, then ∏_{i∈I} G_{i} ∈ X .

Free groups are residually torsion-free nilpotent, and therefore residually poly-C_{∞}. Thus every free group can be embedded in a Cartesian product of poly-C_{∞} groups. By Proposition 3 it follows that all free groups are in W. These orderings of free groups are not transparent. However, there are much studied well orderings of free groups F called short-lex orderings. Here a set of free generators of F (and their inverses) is well ordered, and then reduced words on these symbols are ordered by length, and ties are broken lexicographically. Each word in the generators has a unique reduced form, so we have an ordering of F.

Proposition 4 A short-lex ordering of a free group F renders F ∈ W.

We announce without detailed proof a result which will appear in a forthcoming paper.

Proposition 5 If G is a group and every finitely generated subgroup of G admits a fresh ordering, then G admits a fresh ordering.

Our proof (with C. F. Miller III) is via the compactness theorem of mathematical logic, and follows the spirit of Mal’cev’s proof that a locally linear group is linear.

Proofs

We make a technical definition.

Definition 2 Let G be a group with a linear order < of its underlying set. A pseudocycle in G is a sequence (a_{1}, …, a_{n}; g) of elements of G such that a_{i}g ≤ g for all i, and a_{1}a_{2} … a_{n} = 1. A pseudocycle is trivial if a_{1} = a_{2} = … = a_{n} = 1.

The relevance of this definition stems from the next result.

Lemma 1 Let < be a linear order of the underlying set of a group G. This order is fresh if and only if every pseudocycle in G is trivial.

Proof If G is not fresh choose P ⊂ G of minimal size n which witnesses this fact. There is g ∈ G such that P g ⊆ ⋃_{x<g} P x. Choose p_{n} ∈ P, and by reverse finite induction select p_{i−1} ∈ P such that p_{i−1}^{−1}p_{i}g < g. By minimality of |P | the reversed finite sequence (p_{i}) will not repeat until p_{i} has run through all n elements of P, and then p_{0} = p_{n}. Let a_{i} = p_{i−1}^{−1}p_{i} for 1 ≤ i ≤ n, then (a_{1}, …, a_{n}; g) is a non-trivial pseudocycle.

Conversely, suppose we have a non-trivial pseudocycle (a_{1}, …, a_{m}; g). By omitting any a_{i} which are 1 we may assume that no a_{i} = 1. Let

P = {a_{1}, a_{1}a_{2}, …, a_{1}a_{2} ⋯ a_{m−1}, 1}.

The non-triviality of the pseudocycle forces P not to be a singleton set. Observe that for j ≠ 1 we have a_{1}a_{2} ⋯ a_{j}g = a_{1}a_{2} ⋯ a_{j−1}(a_{j}g) and a_{j}g < g. The missing case is a_{1}g = 1 · (a_{1}g) and a_{1}g < g. Thus P witnesses the fact that < is not a fresh order, and we are done. Proof of Proposition 1 Suppose that (a_{1}, a_{2}, … a_{n}; g) is a pseudocycle. First we assume that < is right invariant. If any inequality a_{j}g ≤ g is strict, we have a_{j} < 1. Also a_{i} ≤ 1 for all i, so 1 = a_{1}a_{2} … a_{n} < 1 which is absurd. Thus every pseudocycle is trivial and, using Lemma 1, this ordering puts G ∈ F and we are half way home. Next assume that < is left invariant. If any inequality a_{j}g ≤ g is strict, we have g^{−1}a_{j}g < 1. Notice also that g^{−1}a_{i}g ≤ 1 for all i, so (a_{1}^{g}, a_{2}^{g}, …, a_{n}^{g}; 1) is a pseudocycle, but 1 = a_{1}^{g}a_{2}^{g} … a_{n}^{g} < 1 which is absurd. It follows that this ordering puts G ∈ F. Proof of Proposition 2 First some notation: if G is a group with a linear order of its underlying set, and x ∈ G, we put I(x) = {y | y ∈ G, y < x}. A subset S of G an interval if whenever a, b ∈ S and a < c < b, then c ∈ S.

(i) Consider Z, the infinite cyclic group written additively. This group comes equipped with the standard order < _{std} . Suppose < is a fresh order of Z. Let I(x) = I_{Z,<}(x) = {y | y < x}. We show that I(x) is an interval with respect to < _{std} . Suppose that a, b ∈ I(x) and a < _{std} c < _{std} b. Suppose, for contradiction that c ∉ I(x). Let P = {0, 1, …, b − a} then P +c ⊆ P +a∪P +b which is absurd since < is a fresh ordering. Conversely, it is clear that if each I(x) is a (standard) interval then < is a fresh order.

The linear order < is fresh and a well order if and only if there is a a minimum element, and subsequent elements in the ordering are chosen to be (standard) adjacent to their predecessors. There are 2^{ℵ_{0}} such orders associated with each of countably many least elements (consider infinite binary sequences). The only remaining fresh orders are the standard order and its reverse, and these are not well orders.

(ii) Let Q denote the additive group of rational numbers. The standard order is a fresh order of Q. Now suppose, for contradiction, that there is a fresh well order < of Q. Suppose that a, b ∈ I_{Q,<}(x) and c ∈ Q with a < _{std} c < _{std} b. Now Q is locally cyclic, so restricting to ⟨a, b, c⟩ and applying (i) we deduce that c < x, so initial subsets I_{Q,<}(x) are standard intervals. If < is also a well order, and the first three elements of Q are q_{1}, q_{2}, q_{3}, then I_{Q,<}(q_{3}) = {q_{1}, q_{2}} absurdly contains (q_{1} + q_{2})/2.

Proof of Proposition 3 Part (i) is a triviality. Now for part (ii). Let the natural map be π : G → G/K = H and suppose that H, K have fresh orderings <_{H}, <_{K} . Choose a transversal T = {t_{h}|h ∈ H} for K in G, where Kt_{h} = h. If x, y ∈ G we write x <_{G} y if xπ <_{H} yπ, or if xπ = yπ = l and x = k_{x}t_{l}, y = k_{y}t_{l}, where k_{x} <_{K} k_{y}.

Suppose that (a_{1}, a_{2}, … a_{n}; g) is a pseudocycle in G. Apply π to get a pseudocycle in H which must be trivial. Thus a_{i} ∈ K for every i and g = kt_{gπ}. It follows that (a_{1}, a_{2}, … a_{n}; k) is a pseudocycle in K and must be trivial. Each a_{i} = 1 and every pseudocycle in G is trivial. Now using Lemma 1 we are done.

For part (iii) we put a well order on I, and use the lexicographic product of orders on each G_{i}. Any failure of freshness will be witnessed by P, g and thus by finitely many equations pg = qh where p, q ∈ P, h ∈ G, and by finitely many inequalities h < g. Each inequality is established by virtue of an inequality h_{i} <_{i} g_{i} in a projection onto a particular factor G_{i}. Let the finite set of indices which arise in this way be J. Projecting onto G_{J} = ∏_{j∈J} G_{j} we obtain a witness to the failure of freshness of the induced ordering on G_{J}. However, J is finite, so this ordering on G_{J} is fresh by part (ii) and induction. This contradiction establishes the result. Note that in the course of this whole proof, well orders propagate appropriately as necessary. Proof of Proposition 4 We assume for contradiction that < is not fresh on F. Choose, as in Lemma 1, a P, g which witnesses the failure of freshness, choosing P of minimal size, and subject to that constraint, so that g is minimal in the short-lex ordering. Notice that g ≠ 1.

Given any p ∈ P, let Q = P −{p}. We have P g ⊆ ∪_{h<g}P h but Qg ⊈ ∪_{h<g}Qh. Thus there is a q ∈ Q such that qg = ph and h < g and moreover, p is the unique element of P such that p^{−1}qg < g.

As in the proof of Lemma 1, we can arrange the elements of P in a nonrepeating finite sequence (p_{i}) where 1 ≤ i ≤ n and h_{i} = p_{i−1}^{−1}p_{i}g < g. This time, however, we construct the sequence in ascending subscript order. Choose p_{1} arbitrarily, and inductively let p = p_{i}, and put p_{i+1} = q as in the previous paragraph. The uniqueness of p is the extra ingredient we need for this proof, and is the reason for this slightly more careful construction. Of course p_{n+1} = p_{1} and we put p_{0} = p_{n}. As before, put a_{i} = p_{i−1}^{−1}p_{i} to obtain a non-trivial pseudocycle (a_{1}, a_{2}, …, a_{n}; g) with n minimal, and g minimal in the short-lex ordering. In the Cayley graph of F on its free generators, the reduced form of a_{i} labels the geodesic edge path from p_{i−1} to p_{i}. Notice that the “uniqueness of p” has the important consequence that in traversing the geodesic from p_{i−1} to p_{i} no other element of P is encountered as a vertex label en route.

Suppose that g = g_{1}g_{2} … g_{m} is the reduced form of g, so each g_{i} is a generator or its inverse. Now a_{i} = h_{i}g^{−1} where h_{i} < g so the reduced form of each h_{i}g^{−1} ends in g_{1}^{−1}. Successive multiplications by the a_{i} take us from p_{1} = 1 to each p_{i} in turn. We visit each p_{i} exactly once, and return to 1. The path we traverse in the Cayley graph will give us a non-trivial cycle in a tree unless the reduced form of each a_{i+1} begins with g_{1}, so we backtrack at least one step along the path from p_{i−1} to p_{i} given by a_{i}. Write g = g_{1}ĝ and let â_{i} = g_{1}^{−1}a_{i}g_{1} for each i. We want to show that â_{i}ĝ < ĝ. The argument splits into two cases, as the vertex p_{i−1} is or is not on the geodesic path from the vertex p_{i} to the vertex p_{i}g. In the first case the geodesic path from p_{i−1} to p_{i} begins with g_{1} and ends with g_{1}^{−1}, and so has length at least 3. Thus the length of g is at least 3 more that the length of h_{i}, so the length of g_{1}^{−1}g = ĝ is at least 1 more than the length of â_{i}ĝ = g_{1}^{−1}h_{i}. On the other hand, if p_{i−1} is not on the geodesic path from p_{i−1} to p_{i}, the reduced form of h_{i} has first letter g_{1}. Now the lexicographic order ensures that â_{i}ĝ = g_{1}^{−1}h_{i} < g_{1}^{−1}g = ĝ. Thus (â_{1}, â_{2}, …, â_{n}; ĝ) violates the minimality of g, and we are done.

Acknowledgements

Some of this work formed part of the second author’s doctoral dissertation [3], the work being done in both the Universities of Bath and Melbourne. She acknowledges the financial support of the United Kingdom CVCP. We thank C. F. Miller III of Melbourne University for extremely useful conversations. We also thank the anonymous referee for many very helpful suggestions as to how to improve the presentation of these results, and for an excellent question – the answer to which is included in this revised version of the paper.

References

[1] E. Rips and Y. Segev, “Torsion free group without unique product property”, J. Algebra 108 (1987) No 1, 116-126.

[2] S. D. Promislow, “A simple example of a torsion-free, nonunique product group”, Bull. Lond. Math. Soc. 20 (1988) 302-304.

[3] O. M. Tabachnikova, Fresh Ordering of Groups, (Ph.D. thesis, University of Bath, 1995).