# Realizable Order Sequences for Finite Groups

My post is motivated at least in part by this MO question.

Has there been any work done on realizable order sequences for finite groups? By an "order sequence" I mean a non-decreasing list of the orders of the elements of the group. By "realizable" I mean there is some finite group that has that particular order sequence.

For example, $(1, 2, 4, 4)$ is a realizable order sequence; it is the order sequence of $\mathbb{Z}/4\mathbb{Z}$.

Is this something that has been studied in any depth? (Perhaps under a different name?) Are there any non-trivial theorems about realizable order sequences? (Examples of trivial theorems: ones that fall immediately out of Lagrange's Theorem; the degree sequence of $\mathbb{Z}/n\mathbb{Z}$)

I know that there are some nice theorems about degree sequences in graph theory (e.g., Erdős-Gallai theorem; Havel-Hakimi theorem), and though I have seen "order sequence" defined in a few Abstract Algebra texts, I have yet to come across any results of much interest.

I also wonder whether results such as this problem solution (Problem 6636, F. Schmidt, Amer. Math. Monthly, Vol. 98, No. 10 (Dec., 1991), pp. 970-972) or this paper (Isaacs et al (2009). Sums of element orders in finite groups. Commun. Alg. 37(9):2978-2980) contain ideas that would be applicable to such a topic.

Finally, is there an easily accessible (and organized) database that lists order sequences for all finite groups up to a certain not-too-small size?

Edit 1: Is anyone up to computing such a list and posting it somewhere accessible?

Edit 2: Now that Alexander Gruber has kindly posted computations for a fair number of order sequences, I wonder: (a) when does the same order sequence correspond to more than one group? (b) given an order sequence that corresponds to precisely one group, how difficult is it to recover the corresponding group's structure?

Edit 3: Mr. Gruber has most recently pointed me toward a related area of research on "OD-characterizability." One mathematician who has done a fair bit of work in this area is AR Moghaddamfar. See, for example, Recognizing Finite Groups Through Order and Degree Pattern.

-
You could compute such a list using, say, GAP and the smallgroups library. –  Arturo Magidin Sep 16 '12 at 4:52

Here's a quick list for groups up to order 512. Format is group order, followed by a list of possible order sequences for groups of that order, then an empty space, then a list of the number of groups with each respective order sequence (in the order they were listed). You can see it starts to get pretty long. Let me know if there is another specific range of orders you'd like me to run this code on.

-
Since the motivating question has a purported proof for solvable groups, it would be great to see the code run on orders of non-solvable groups, which can be found at oeis.org/A056866 –  Benjamin Dickman Sep 27 '12 at 9:19
Here it is for the nonsolvable groups of those orders. docs.google.com/open?id=0B3X5C_7tdfR2Q0xwZ2FSZUUwcHc –  Alexander Gruber Sep 27 '12 at 14:53

I don't know if this constitutes an answer but... You might be interested in the paper by Mazurov called The set of orders of elements in a finite group.

Given a group $G$, Mazurov defines $\omega(G)$ to be the set of element of orders of a group $G$. (So $\omega(G)$ isn't quite what you're looking for. But, still, information about the behaviour of $\omega(G)$ as $G$ varies over all finite groups, will tell you a lot about the behaviour of order sequences as you define them in your question.)

Apparently there was a long-standing conjecture to the effect that if two distinct groups $G$ and $H$ satisfied the identity $\omega(G)=\omega(H)$, then there were infinitely many such groups. In the paper above Mazurov proves a counter-example to this but he also remarks that "we believe that almost all groups $G$ are characterized by $\omega(G)$ uniquely." Now what he means by "almost all groups" I couldn't possibly say but, still, if this is true then it has significant implications for your order sequences.

In a different direction you might also be interested in various work on $GK(G)$, the Gruenberg-Kegel graph, or prime graph, of a group $G$. This is a graph whose vertices are labelled by primes dividing $|G|$, with two such vertices $p$ and $q$ being connected if an element of order $pq$ exists in $G$. Lots of information about $GK(G)$ has been determined for different groups $G$, including recognition theorems of the form "Suppose the underlying graph of $GK(G)$ is isomorphic to the graph $X$, then $G$ is the group $Y$".

If $G$ is simple, there is also a series of papers by Vasil'ev and Vdovin (and probably others) which give information about different properties of $GK(G)$, including maximum clique size etc. Again information about order sequences can be derived from these results.

P.S. I have e-copies of all the papers I mention above and can email them if you need me to.

-
No nilpotent group $\neq 1$ is characterized by $\omega(G)$, and I would be surprised to see a solvable group that is, so maybe Mazurov wanted to say "almost all simple groups"? –  Frieder Ladisch Sep 25 '12 at 13:26
I should have also mentioned the notion of the spectrum' of a group, which is the set of maximal elements in the poset of element orders of the group (ordered by divisibility). I don't know the state of the literature on the spectrum' but I know the term crops up in various places. –  Nick Gill Sep 25 '12 at 16:40

Just to develop Ladish's comment. Every $p$-group is nilpotent. Yet it is not determined by its order sequence. For instance, both ${\mathbb F}_3^3$ and the unit-triangular group $UT_3({\mathbb F}_3)$ have $27$ elements, all of them, but the unit, being of order $3$.

This is related to the question Finite groups with elements of the same order .

-
Yes, indeed there are many non-isomorphic examples of $p$-groups of exponent $p,$ each pair providing a counterexample to the assertion that order sequence determines the isomorphism type of the group –  Geoff Robinson Sep 28 '12 at 6:18
Thanks for the note, example, and link. It's interesting that of the five groups of order $27$, there is of course the cyclic group $C_{27}$, and then not only do $UT(3,3)$ and $C_{3}^{3}$ have the same order sequence, but so do the other two groups of this order: namely, the direct product of $C_9$ and $C_3$ as well as the semidirect product of $C_9$ and $C_3$. From these examples alone, a whole host of possible conjectures on order sequences can be dismissed outright... –  Benjamin Dickman Sep 28 '12 at 15:22

At least for finite abelian groups the problem has been solved. See

Isomorphism of Finite Abelian Groups, by Ronald McHaffey, The American Mathematical Monthly, Vol. 72, No. 1 (Jan., 1965), pp. 48-50, Stable URL: http://www.jstor.org/stable/2313001

The author essentially proves that if the sequence of orders of two finite abelian groups are the same then the groups are isomorphic.

-