21
$\begingroup$

I would like a method to efficiently generate a random finite group of a given order $n$. If there are $g(n)$ non-isomorphic groups of order $n$, ideally each group would occur with probability $1/g(n)$. So if $n=64$, each of the $267$ groups would be generated with equal probability. ($g(n)$ is A000001 in OEIS.) Groups of order $n=2^k$ would be of special interest.

This is far from my expertise, and my searches must be using the wrong terminology, because I have not found such methods. I'd appreciate pointers—Thanks!

Addendum. The comments indicate that this appears to be an open problem, with little chance of resolution in the near future. Now so tagged.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ You may want to weight groups by their automorphism groups. That is, if $a(G)$ denotes $1/\#\text{Aut}(G)$, and $b(n)$ is the sum of $a(G)$ over all groups $G$ of order $n$, then have an order-$n$ group $G$ occur with probability $a(G)/b(n)$. This is the philosophy behind the Cohen-Lenstra heuristics. For instance, see Qiaochu Yuan's answer to mathoverflow.146861. $\endgroup$
    – Michael Zieve
    Commented May 2, 2014 at 11:58
  • 3
    $\begingroup$ This sounds very pessimistic, but I would be very surprised if there were any reasonably accurate way of doing that except in cases where it is possible to produce a complete list of all groups of order $n$. It would be challenging to come up with any plausible ideas for this for groups of order a power of $2$, and even if you could do so, the results would be dependent on unproved conjectures that "almost all" such groups are $2$-step nilpotent with elementary abelian layers. $\endgroup$
    – Derek Holt
    Commented May 2, 2014 at 13:16
  • 1
    $\begingroup$ When I was a student, I thought about the problem of generating a random group in search of an improvement of the Elliptic Curves Method (ECM) for factoring integers. The idea was that since most finite groups are 2-groups, in particular one would almost always hit a group with smooth order, and hence under reasonable circumstances obtain a factorization almost instantly -- in contrast to ECM, which uses abelian groups only. However, thinking a bit more about the issue, I realized the problems with feasibility ... . $\endgroup$
    – Stefan Kohl ♦
    Commented May 2, 2014 at 13:47
  • 2
    $\begingroup$ As other have said, getting a uniform distribution on groups of order $n$ looks unlikely. Most groups of order $n$ are nilpotent, and most nilpotent ones have class at most $2$- these statements can be made reasonably precise. $\endgroup$
    – Geoff Robinson
    Commented May 2, 2014 at 14:32
  • 3
    $\begingroup$ This is related in spirit :) mathoverflow.net/questions/36735/… $\endgroup$
    – Gjergji Zaimi
    Commented Jul 9, 2015 at 1:29

2 Answers 2

Reset to default
6
+50
$\begingroup$

Are you running computer experiments to verify conjectures? If so, the GAP SmallGroups library will give you exactly what you want up to $n = 1023$.

For example, the GAP commands

  n:=16;; G:=SmallGroup(n, Random(1,NumberSmallGroups(n)));

will return you a group chosen uniformly at random from the groups of order $n=16$. Similar commands will work up to $n=1023$. Indeed, it will work for also for all orders up to 2000 except for 1024, and for a considerable number of other orders.

You might also find the SmallGroups library web page to be helpful.

It describes some of the methods involved. If you're willing to select a group uniformly at random from a subcollection of all the groups of order $2^k$, then there are several papers on groups of order $2^k$ (for varying values of $k$) cited there. Applying the methods therein might be enough for you, depending on what your specific needs are.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ As there are $49487365422 \approx 5 \times 10^{10}$ groups of order $2^{10}$, it is reasonable for GAP to pass over $1024$! $\endgroup$
    – Joseph O'Rourke
    Commented Jul 13, 2015 at 13:04
  • $\begingroup$ Indeed, GAP even knows the count of these groups with NumberSmallGroups (but it won't let you get at the groups themselves via the SmallGroups library). $\endgroup$
    – Russ Woodroofe
    Commented Jul 13, 2015 at 13:07
  • 1
    $\begingroup$ You may be interested also in SmallGroupsInformation function - it gives some more details how the groups of a given order are sorted in the library. $\endgroup$
    – Olexandr Konovalov
    Commented Jul 14, 2015 at 15:03
4
$\begingroup$

Here is a stupid approach: Fill in a $n\times n$ multiplication table randomly, then check whether if satisfies the properties of a group.

(The hard part is associativity, apart from that we basically want our multiplication table to be a "magic square", maybe there's more efficient ways to uniformly generate magic squares, and then only check associativity).

Repeat until you actually get a group.

The end result should be uniformly distributed over all group multiplication tables, and since each group $G$ admits $(n-1)!/\left|Aut(G)\right|$ different multiplication tables, this leads to a distribution as described in Michael Zieve's comment.

This is of course far from practical, but illustrates that what you want is, in principle, possible.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Somewhat related: "How many binary operations are associative?." $\endgroup$
    – Joseph O'Rourke
    Commented Jul 13, 2015 at 13:07
  • 2
    $\begingroup$ It's not clear to me that the procedure described above wouldn't favor certain isomorphism classes. The original question wanted an equal chance at each isomorphism class of groups of order $n$. $\endgroup$
    – Russ Woodroofe
    Commented Jul 13, 2015 at 13:10
  • $\begingroup$ Yeah, it doesn't do that, as I explained. Rather, it weights the probability of each isomorphism class by the inverse of the order of the automorphism group, as I explained. (Which is apparently the more natural thing according to Michael Zieve's comment) $\endgroup$
    – Achim Krause
    Commented Jul 13, 2015 at 21:39

You must log in to answer this question.

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