2
$\begingroup$

I am poking at reproducing some fundamental research in group theory. In particular, I want to reproduce the OEIS sequence #1. The crux of the problem is not generating potential groups, this can be accomplished by a sat-solver and about 20 lines of code, but determining which of those groups so generated are isomorphic.

The finite group isomorphism algorithms are tractable, but computationally a bit hairy, so I am keen to determine what heuristics can be employed to save some compute on clearly not isomorphic groups. A few obvious examples are:

  • Groups with different order
  • Groups with different Caylee skeleton (number of non-self identity elements)

In short, I would love some form or precomputation or fingerprint that I can compute to avoid comparing obviously different groups.

$\endgroup$
2
$\begingroup$

I think you will want to look at the publications by James Wilson at Colorado State University who has been doing this kind of thing for quite large groups.

$\endgroup$
  • $\begingroup$ Though interesting, if I understand correctly the algorithms only apply to a limited class of finite groups $\endgroup$ – doetoe Jul 20 at 21:52
0
$\begingroup$

You could apply the KBMAG procedure [GAP algebra package].

It attempts to obtain an automatic structure for the group: essentially a collection of finite state automata that define the group, which can then be compared for equality. All finite groups have such a structure.

An alternative implementation is MAF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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