8
$\begingroup$

From the introduction of the article Construction of Finite Groups written by Hans Ulrich Besche and Bettina Eick:

When attempting to determine up to isomorphism the groups of a given order it is often known how to compute a list of groups of this order which contains each isomorphism type at least once. The central problem is to reduce to isomorphism type representatives.

Is it really known how to compute a list of groups of a given order that contains each isomorphism type at least once? If so, please tell me where to find such algorithm.

  • 0
    Brute force counts?2016-01-22

2 Answers 2

16

The algorithms of Eick and O'Brien for computing a complete list of groups of a given order are not general algorithms, because they make use of known (i.e. pre-computed) properties of the finite simple groups. But these known properties are known for simple groups of much larger order than it is remotely feasible to find a complete list of groups of that order, and that is likely to remain the case. Interestingly, for prime powers $p^n$, which is the most difficult case, the algorithm in question is general purpose. It would be meaningful to ask whether there is an algorithm for doing this that is polynomial in the output length - I don't the answer to that!

Concerning testing groups of order $n$ for isomorphism, there is no known algorithm for doing this that is polynomial in $n$, so if you have found such an algorithm then you could certainly publish it in a good journal. It probably doesn't make much difference how the groups are given, since you can move between permutation or matrix representations and finite presentations in time polynomial in $n$. It is easy to test for isomorphism in time $O(n^{{\rm log}\, n})$ (find a generating set of size $O({\rm log}\, n)$ and test every possible set of generator images for inducing an isomorphism) and no essentially better method is known.

Of course the implemented algorithms use lots of tricks. One published paper on this topic is:

J. Cannon and D.F. Holt. Automorphism group computation and isomorphism testing in finite groups. J. Symbolic Computation 35, 241-267 (2003).

6

Of course it's theoretically possible to "compute a list of groups" in any given order, if time and memory aren't limited. Just enumerate over all possible multiplication tables, or over subsets of a sufficiently large permutation group. What you're really asking about, I suppose, is how to do this efficiently, and as far as I know this is a hard problem even for relatively modest values of $n$, the required size of the group.

Computer packages such as GAP are pretty good at knowing or computing such lists, and there are papers by the folks who wrote them that detail the algorithms they've used. You can find a few references in this closed MO question (closed because the question is ill-defined).

What are you actually trying to achieve? Do you really have any use for the complete list of groups of order 1024, for example? There's over 49 billion of them.

  • 0
    Actually I mean is there a practical algorithm to compute the list?2011-11-27
  • 1
    "Practical" in what sense? For which values of $n$? What resources are at your disposal? In what form do you wish to have the groups presented? If you want to make this an answerable question, you'll need to think through and provide a lot more detail.2011-11-27
  • 0
    What are you actually trying to achieve? well, I am trying to find an algorithm (another algorithm to construct finite groups)2011-11-27
  • 0
    "Practical" or has a polynomial time2011-11-27
  • 0
    "another"...? What the first one? Have you read the paper by Besche, Eick and O'Brien mentioned in the link I gave?2011-11-27
  • 0
    There can be no polynomial time algorithm since the sheer *number* of groups of a given order $n$ is (potentially) exponential in $n$ ("potentially" since it depends on the structure of the prime decomposition of $n$.)2011-11-27
  • 0
    so the word "compute a list" in the article is not about a practical algorithm?2011-11-27
  • 0
    "another"...? What the first one? the algorithms introduced by Eick and O'Brien2011-11-27
  • 0
    1) "practical" is a very fluid term, so I don't know. 2) notice that they say "often". 3) The system is already complaining that we're having an excessively long discussion in comments. Again, please consider rephrasing the question in very specific terms, or just read the rest of the paper since most of what is known about the problem is already in there.2011-11-27
  • 0
    but they didn't introduce a "general" algorithm to test whether two groups are isomorphic2011-11-27
  • 0
    @Jawad: they couldn't do that, because the problem is undecidable -- there is no general algorithm deciding whether two groups are isomorphic.2011-11-27
  • 7
    @Damian: It depends on how the groups are "given". If they are finite and given in terms of Cayley tables, there certainly is: just consider all possible bijections and test. But this method is not practical; there are better methods for certain kinds of groups and certain kinds of "givens" (e.g., two groups given by polycyclic presentation). But this is irrelevant: the OP is trying to figure out how "important" or "interesting" a 'method' he has found is, but doesn't want to say anything about that method. [see previous question and comments](http://math.stackexchange.com/questions/85910/).2011-11-27
  • 6
    In fact, it doesn't matter how the groups are given to you. For instance, if you are given a group presentation and told that the group presented is finite, then there is a silly brute-force algorithm to compute the multiplication table, so any question about the group "can" be solved. Of course, there is no algorithm to determine whether or not a group given by a presentation is finite.2011-11-27