Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Michael Zieve May 2 at 11:58
2  
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. –  Derek Holt May 2 at 13:16
1  
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 ... . –  Stefan Kohl May 2 at 13:47
1  
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. –  Geoff Robinson May 2 at 14:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.