29
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ $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$. $\endgroup$ Oct 24, 2012 at 10:17
  • $\begingroup$ 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)". $\endgroup$ Oct 24, 2012 at 11:01
  • $\begingroup$ @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. $\endgroup$ Oct 24, 2012 at 11:05
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 24, 2012 at 13:07
  • 1
    $\begingroup$ (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.) $\endgroup$ Oct 24, 2012 at 13:08

1 Answer 1

18
+100
$\begingroup$

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 $(\operatorname{deg}(p_1),\ldots,\operatorname{deg}(p_k))$ for $i=1,\ldots ,|V|$, where $\operatorname{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.

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$ Oct 30, 2012 at 7:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – Alexander Gruber
    Oct 30, 2012 at 23:54
  • $\begingroup$ 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. $\endgroup$
    – Alexander Gruber
    Oct 30, 2012 at 23:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .