I started this sequence to give myself an incentive to prove an old conjecture of mine; and this time it worked. Yesterday I put a paper on the arXiv; it should appear in Monday’s mailing. Here is a preview of what it contains.
The subject today is (total) orders and multiorders (n-tuples of orders).
Orders
A total order on a group G is a Cayley object for G if and only if it is right-invariant: that is, if x < y, then xg < yg for any g∈G. In the literature, this is called a right order for G, and G is said to be right orderable.
Let P be the set of positive elements (greater than the identity). Then
- P^{2} ⊆ P;
- G is the disjoint union of {1}, P, and P^{−1}.
Conversely, if a set P in a group satisfies these conditions, then the order defined by x < y if y = px for some p ∈ P is a right order on G.
The unique countable homogeneous total order is the order of the rational numbers Q; it is the Fraïssé limit of the class of all finite orders. (Cantor’s Theorem characterises this order as the unique countble dense order without endpoints.) The right order defined by P is dense if and only if the first condition above holds in the stronger form
- P^{2} = P.
There is a large literature on right orderable groups, but very little attention has been given to the question of whether the order is dense.
I will be interested in the free abelian group Z^{m}. The orderings of this group are described by the following result:
Theorem Let < be a right ordering on Z^{m}, where m > 1. Then there is a non-zero vector c in R^{m} such that x < y if c.x < c.y, where . denotes the usual inner product on R^{m}. If the components of c are linearly independent over Q, then the order is dense, and x < y if and only if c.x < c.y.
I will say a little about the proof of this theorem. A right order is archimedean if, given any two non-identity elements a and b, not all powers of b are contained between a and its inverse. If an order on an abelian group is not archimedean, the “infinitely small” elements form a subgroup, and the order induced on the quotient is archimedean. If the group is free abelian, then this quotient is free abelian of smaller rank. So it is enough to deal with the archimedean case. Now a theorem of Hölder asserts that an archimedean ordered abelian group is isomorphic (as ordered group) to a subgroup of the real numbers. The theorem follows, on taking the components of c to be the images of the standard generators of Z^{m} under the isomorphism.
It was first observed by Bernhard Neumann (I think) that free groups are right orderable. The argument uses the fact that the lower central factors of such a group are free abelian groups and intersect in the identity. (Their ranks are the so-called “Dedekind numbers” which also appear in the theory of Lie algebras, irreducible polynomials over finite fields, and other places.) Now take an order of each factor, and let P consist of elements whose first non-identity projection modulo the terms of the lower central series is positive in the order on the corresponding factor. It is clear that this order is dense.
Multi-orders
An n–order is just an n-tuple of orders on a set. (If the number of orders is not important, I will call this a multiorder.) It is easy to see that the class of finite n-orders is a Fraïssé class; its Fraïssé limit is an object which I will call the generic n-order.
2-orders have been extensively studied under the name “permutation patterns”. In this theory, the objects are permutations, and the notion of substructure works like this: the substructure of the permutation (2,1,4,5,3) induced on the second, fourth and fifth places is (1,3,2). In other words, we consider the order of the elements in the given positions and “slide them down” preserving the order to obtain a permutation of the first so many natural numbers.
Now in a finite 2-order, we can use the first order to number the set as 1,2,…n, and the second order is then a permutation of the first. So permutations and 2-orders match up naturally. With this interpretation, the notation of substructure in permutation patterns is precisely the induced substructure of the 2-order. So we could say that the theory of permutation patterns is the study of the age of the generic 2-order. (The theorem below gives a concrete representation of the generic 2-order, which may have some use.)
The theory of permutation patterns is largely concerned with enumerative and structural properties of classes defined by excluded substructures. Problem: Is there a similar theory for n-orders with n > 2?
My theorem is the proof of a conjecture I made in a paper in 2000:
Theorem The generic n-order is a Cayley object for the free abelian group Z^{m} if and only if m > n.
Here is a sketch of the proof. We need a construction for m > n and a non-existence proof for m ≤ n. Since omitting some of the orders from a generic multiorder gives a generic multiorder, it suffices to give a construction for n = m−1 and a non-existence proof for n = m.
The construction requires an m×m real matrix A with the properties
- A is invertible;
- the elements of each row of A are linearly independent over Q;
- the last row of A is orthogonal to all the others.
In the paper I give a non-constructive existence proof for such matrices based on the Baire category theorem. Problem: give an explicit construction!
Now use the first m−1 rows of A to define an (m−1)-order on Z^{m}. To show it is generic we need to show that the intersection of m−1 intervals, one in each order, is non-empty. This intersection is determined by m−1 parallel pairs of hyperplanes; since the first m−1 rows of A are linearly independent, the intersection in R^{m} is a cylinder with parallelepiped cross-section. The axis of this cylinder is in the direction of the last row of A. By the theorem of Kronecker which I asked about in a recent post, the axis passes arbitrarily near a lattice point; so there is a point of Z^{m} in the intersection.
The non-existence proofs are somewhat ad hoc. The m orders define m vectors in R^{m}, and we divide into three cases according as these vectors are linearly dependent, are linearly independent but at least one has components which are linearly dependent over Q, and the remainder.
Problem: Find other examples of groups having the generic multiorder as a Cayley object (or, perhaps, show that they don’t exist).
Robin Chapman has just answered one of my questions by providing an explicit construction of a matrix with the three properties I needed.