Suppose you know the following two things about a group $G$ with $n$ elements:

  1. the order of each of the $n$ elements in $G$;

  2. $G$ is uniquely determined by the orders in (1).

Question: How difficult is it to recover the group structure of $G$? In other words, what is the best way to use this information to construct a Cayley table for $G$?

Note: (1) alone is not enough to uniquely determine a group. See this MO post for more.

Information about identifying when (1) implies (2) would be welcomed as well.

  • $G$ will hardly be uniquely determined (that is beyond isomorphism) even if $G$ is abelian. For example in $\mathbb Z/8\mathbb Z$, if $a$ has order 8 and $b$ has order 4 it may or may not be the case that $b=a+a$. – Hagen von Eitzen Oct 24 '12 at 10:17
  • A group with 3 elements of order 2, 12 elements of order 4, and 1 element of order 1 can be either abelian or non-abelian, so I would disagree that when G is abelian 1 implies 2. One only has the weaker "1 implies 2-prime" where 2-prime is "G is uniquely determined amongst abelian groups by the orders in (1)". – Jack Schmidt Oct 24 '12 at 11:01
  • @Hagen: I mean to say: consider the possible orders of elements in groups of size $8$, of which there are $5$ non-isomorphic ones: [ 1, 2, 4, 4, 8, 8, 8, 8 ] [ 1, 2, 2, 2, 4, 4, 4, 4 ] [ 1, 2, 2, 2, 2, 2, 4, 4 ] [ 1, 2, 4, 4, 4, 4, 4, 4 ] [ 1, 2, 2, 2, 2, 2, 2, 2 ] Each of these order sequences uniquely determines a group (up to isomorphism) insofar as no two of them are the same. I'm wondering how one could take one of these order sequences and use it to build a Cayley table in a smart way. – Benjamin Dickman Oct 24 '12 at 11:05
  • 3
    This strikes me as trying to name beaches by the number of grains of sand they contain. Surely each beach is uniquely determined by this number, but the number says very little about the beach other than its general size (but nothing about its shape). In other words, surely you have the groups first, then count the element orders, rather than the other way. The papers that prove (2) are very interesting, but of course the G determined is (I believe) always a particular known group to start with. – Jack Schmidt Oct 24 '12 at 13:07
  • 1
    (In other words, the papers prove uniqueness, they do not somehow divine existence from the order sequence. Existence is already given; G is a known group.) – Jack Schmidt Oct 24 '12 at 13:08
up vote 18 down vote accepted

This is actually quite a nontrivial question and is related to a concept called OD-characterizability, a topic of current research. Let me throw some definitions at you.

Definition. The prime graph of a group $G$ is a graph $\Gamma_G=\langle V, E \rangle$ where the vertex set $V$ is comprised of the prime divisors of $|G|$ and $\{p,q\}\in E$ if and only if there exists an element of order $pq$ in $G$. The degree pattern of a group $G$ is defined as $(deg(p_1),\ldots,deg(p_k))$ for $i=1,\ldots ,|V|$, where $deg(p)$ denotes the degree of the vertex $p$ in $\Gamma_G$.

Definition. We say that a group $G$ is $n$-fold OD characterizable if there are exactly $n$ nonisomorphic finite groups with the same order and degree pattern as $G$. If a group $G$ is $1$-fold OD-characterizable, we simply say $G$ is OD-characterizable.

There is no reason why a group with a unique order sequence could not have the same degree pattern as another group of the same order. $p$-groups are an obvious example. On the other hand, assuming we know the order sequence of $G$, we can certainly construct the degree pattern of $G$. Of course, two groups with which have the same order sequence surely implies that they have the same degree pattern, so if a group is not uniquely determined by its order sequence it is not OD-characterizable. Thus every group which is OD-characterizable has a unique order sequence, and all the research which has been done about those should apply to your groups.

Unfortunately most OD-characterizability papers that I have seen focus on proving that certain classes of groups are OD-characterizable, e.g. alternating and symmetric groups, rather than on what OD-characterizability itself says about group structure. I suspect that's because it doesn't actually say a whole lot. For this reason I think that the best place to look if you planned to research this further would be at the order sequences of $p$-groups, as that is the primary place your condition differs from OD-characterizability.

However, not to be a bummer, but I wouldn't expect to be able to make any widesweeping statements. For example, amongst groups of order 32, there are $21$ order sequences. Out of those, the $10$ groups with unique order sequences are: $\mathbb{Z}_{32}$, $\left(\mathbb{Z}_{2}\right)^5$, $Q_{32}$, $D_{32}$, $D_{16}\times \mathbb{Z}_2$, $D_8 \times V$, the semidihedral group $SD_{32}$, the holomorph of $\mathbb{Z}_8$, and some nonabelian groups which are just referred to as $\text{SmallGroup}(32,7)$ and $\text{SmallGroup}(32,15)$. So whatever properties would be true of groups which are uniquely characterizable by their order sequences would have to be shared by all those groups, which as you can see are quite different.

  • This is a very helpful answer. Are there any papers on OD-characterizability that you would recommend starting with? Also, do you have any thoughts on algorithmic approaches to constructing a Cayley table given an order sequence (even if the sequence doesn't uniquely define a group)? – Benjamin Dickman Oct 30 '12 at 7:05
  • 1
    @B. Ali Reza Moghaddamfar has written a few papers about it. The first one I read was Recognizability of finite groups by order and degree pattern. – Alexander Gruber Oct 30 '12 at 23:54
  • As for the Cayley table, I am really not sure. Some order sequences will be quite obvious - for example those corresponding to elementary abelian or cyclic groups - but in general I do not know of any way to do this, even when we only look at order sequences for which this can be done (that is, those known to correspond to only one group). I think it would be difficult. – Alexander Gruber Oct 30 '12 at 23:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.