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).
Are there methods to well order a finite group in a meaningful way?
-
3Other than the trivial group, there is no well-ordering on any finite group in a way that $m$akes the group operation order-preserving. (Obvious.) – 2012-06-07
5 Answers
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.
-
2This 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. – 2012-06-07
I'm not sure what you want but you cannot have an order that respects the group operation in the sense that $a implies $ac < bc$.
Indeed, suppose $1 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$.
-
0I am $i$nterested $i$n more exotic ways to yield an order. – 2012-06-07
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.
-
0One 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. – 2012-06-08
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
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.
-
0@Oo3: Take three people you find from the street, and without talking to them assign one to supervise the others. Did you make *any* choice, or was this choice immaterial? Of course this analogy does not go very far, since different people come with different skills. However the point I am trying to make is the same, this is not just about the name. This is about the fact that given three completely arbitrary objects in the mathematical universe you have no uniform way to assign them$a$group structure without making a very arbitrary choice which of them is going to be $0$, and so on. – 2012-06-07
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 ;-)