# Are there methods to well order a finite group in a meaningful way?

Can some finite groups be well ordered in a "meaningful" way? I mean, it is clear that we can trivially find a bijection between $\{1,...,n\}$ and a finite group $G$ with $n$ elements, but I am interested in well ordering that are based on some scheme or pattern with respect to some group property (for example, it is immediate to well-order a cyclic group).

-
How is it immediate to well-order a cyclic group? If you mean the ordering "identity, generator, square of generator, ...", then which of the many generators will you choose? –  Chris Eagle Jun 7 '12 at 11:52
You can obtain $n-1$ different wos, isn't it? –  Oo3 Jun 7 '12 at 11:54
Other than the trivial group, there is no well-ordering on any finite group in a way that makes the group operation order-preserving. (Obvious.) –  Zhen Lin Jun 7 '12 at 12:10

A finite group has a finite number of generators, which you can name $a,b,c,\dots$ (or $a_1,a_2,\dots,a_r$ for some $r$). Then you can write every group element as a word in the generators; among the many expressions for any given group element, consider only those of minimal length, and among those, pick the one that's lexicographically first. Then order the $n$ resulting expressions lexicographically.

A lot of choices to make along the way, so there's nothing canonical here, but that didn't seem to bother you for cyclic groups, so perhaps you'll accept it here, too.

-
This is crazy!! Well, +1 for the moment, waiting for further contributions... –  Oo3 Jun 7 '12 at 13:13
This is a lot less crazy than you think - this is one of the key ideas behind algorithms for (infinite) automatic groups, where there's a fast (linear in the size of the words) algorithm for computing the lexicographically first representation of the product of two words of the group. This can be useful, for instance, in doing calculations in some symmetry groups. –  Steven Stadnicki Jun 7 '12 at 15:15

I'm not sure what you want but you cannot have an order that respects the group operation in the sense that $a<b$ implies $ac < bc$.

Indeed, suppose $1<a$ and $a$ has order $m$. Then $1 < a < a^2 < \cdots < a^{m-1} < a^m=1$, a contradiction. The same holds if $1>a$.

-
I am interested in more exotic ways to yield an order. –  Oo3 Jun 7 '12 at 13:09

If you are prepared to represent the group as a permutation group on $\{1,...,n\}$, then the stabilizer chain produced by the Schreier-Sims algorithm leads to a fairly natural order (though of course the permutation representation itself is not canonical).

That is, given $\Delta\subseteq \{1,...,n\}$, let $G_{\Delta}$ be the pointwise stabilizer of $\Delta$ in $G$. Then there is a stabilizer chain:

$G = G_{\{\}} \supseteq G_{\{1\}} \supseteq G_{\{1,2\}} \supseteq ... \supseteq G_{\{1,...,n-1\}} \supseteq G_{\{1,...,n\}} = 1$.

Given some link $G_{\{1,...,i\}} \supseteq G_{\{1,...,i+1\}}$ in the chain, the cosets of $G_{\{1,...,i+1\}}$ in $G_{\{1,...,i\}}$ can be ordered by their action on i. This extends to an order on the whole group.

For example, $S_{3}$ would be ordered as: 1, (23), (12), (123), (13), (132).

First, the elements that send 1 to 1, then the elements that send 1 to 2, finally the elements that send 1 to 3. So these are the three cosets of $G_{\{1\}}$. Then, within the coset $(13)G_{\{1\}}$ (for example), we order recursively using the same order relation.

-
What do you mean exactly when you say: "if you are prepared to represent the group as permutation group on $\{1, \dots ,n\}$? –  Oo3 Jun 7 '12 at 18:08
@Oo3 Well, many finite groups arise as permutation groups on {1,...,n} (eg the symmetric, alternating, and dihedral groups). Still others have natural permutation actions on small sets (eg PGL(n,Fq)), so we just have to decide on a way to number the small set. Every finite group can be represented as a permutation group - it acts on itself by multiplication on the right. However, in this case, we would already need to have decided on a numbering of the group elements, which defeats the point. –  DavidA Jun 7 '12 at 19:46
One nice thing about this answer (other than it is actually used by gap) is that it replaces a large enumeration problem (the whole group) to a series of smaller ones (cosets of k+1 point stabilizer inside a k point stabilizer). In other words, you are just labeling the cosets with {1...n} instead of the group elements. There are many problems that become simpler when considered over a chain of subgroups than when just looking at the entire group. –  Jack Schmidt Jun 8 '12 at 3:47

The most meaningful way to well-order a finite group would be in such way that the addition coheres with the order. However no finite group can be ordered, since $$1<a<a^2<a^3<\ldots<a^{\mathrm{ord}(a)}=1$$

The above shows that you cannot take an order which respects the group operation on a finite group. To the question "more exotic" one has to think about, and note that every finite set can be given several (possibly interesting) different group structures. In fact, if I have a set $\{a,b,c\}$ then there are several ways in which it can be made into $\mathbb Z/3\mathbb Z$.

We do not have a canonical way of choosing a group structure on a set. Once there are very arbitrary choices there is no real way to generate interesting well orders. If you agree that a canonical way would be to take a group of a finite cyclic group then you still have to ask yourself which element of your set is $1$.

Once you agreed which element is $1$ then there is one reasonable way of choosing an enumeration of the group, namely $n\cdot 1$. However this is still very arbitrary.

-
I beat you to it... :-) –  lhf Jun 7 '12 at 12:53
Yes, and I have to go teach now... so you have time to beat me again! –  Asaf Karagila Jun 7 '12 at 12:54
Who's counting? –  lhf Jun 7 '12 at 12:54
Well, combinatorialists count. In particular Cameron counts :-) –  Asaf Karagila Jun 7 '12 at 12:55
I believe that if you just take into account addition and order that go together, then my question would have had not make any sense. –  Oo3 Jun 7 '12 at 13:06

The comment was too short, so I'm posting this as an answer.

Well order implies some linear structure so I don't see any meaningful orderings for groups other than cyclic (see Cayley graphs). For example you could take a group in which there are two (or even more) different elements that behave in the same way, e.g. $(0,1)$ and $(1,0)$ in $\mathbb{Z}_2\times\mathbb{Z}_2$, or generators of non-cyclic free group.

Note, that this is also the case also for cyclic groups, e.g. if $a$ is the generator, then is $a^{-1}$ too. In a way, they are symmetric, and any well order would destroy that.

On the other hand, I think that there are many well-founded partial orders that could apply here, and if you wish, you could make them total (by something like topological sorting). Moreover, this would actually correspond to the fact that you choose one element over the other (and thus destroy the symmetry).

Hope that helps ;-)

-