2
$\begingroup$

This is a question about rewriting systems & languages for finite groups. I'm sure everything must be in the literature somewhere, but I find it hard to navigate the references I have (for example Holt–Rees–Rover's Groups, languages and automata) probably because the focus is always on difficult, infinite groups — I think my questions are brushed aside because they are considered trivial. Or perhaps the issue is that most results focus on what is feasible at all (and for finite groups everything is in principle feasible), when my questions are more about efficiency.

So suppose you have a presentation by generators and relations for a finite group $G$.

  1. Is there always a nice theory of "normal forms" for the elements of $G$? or does it depend on the presentation?
  2. assuming we do have normal forms, is it always possible to compute efficiently the normal form of a given element? By "efficiently" I mean NOT something like "consider the automaton whose underlying graph is the Cayley graph…", because if $G$ is very large, this graph/automaton is not practical. (This would be what people call a rewriting system, right?)

Failing that, it would be very nice to be able to compute for each element of $G$ a representative word of bounded length, where the bound can be found explicitly and is not too bad.

As the answers may very well depend on the presentation, I'd like to add a side question:

  1. suppose $G$ is given explicitly, say as a permutation group generated by given permutations. What is the (current) best algorithm to compute a presentation for $G$? I mean either using the given generators, or perhaps, as a variant, allowing the addition of extra generators (in order to obtain a better presentation, in whatever sense).

I find it surprising that (3) is not discussed much in the references I have on computer algebra (there is an algorithm in Butler's old book). Also with GAP you cannot find a presentation for a group "by pressing a button", which I find again surprising, given how useful it can be, if only for reasons of pedagogy with very small groups.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ There are a few too many diverse questions here, but just to answer one of them, for a permutation groups you can adjoin extra generators to form a so-called strong generating set, and it is relatively easy to compute a presentation (sometimes called a strong presentation) on that set. Computing a presentation on the given generators is more difficult. Similarly you can easily compute words of bounded length for a given group element on the strong generators, but it is harder on the given generators. Using rewriting systems is not an efficient way to compute in large finite groups. $\endgroup$
    – Derek Holt
    Commented Aug 2 at 21:49
  • $\begingroup$ In addition to this being several questions in one, I think that the introductory paragraph isn't needed, or at least doesn't need to be introductory. $\endgroup$
    – LSpice
    Commented Aug 2 at 21:55
  • 1
    $\begingroup$ Also GAP of course allows to get a presentation for a permutation with essentially a single command: IsomorphismFpGroup $\endgroup$
    – Max Horn
    Commented Aug 3 at 17:25
  • $\begingroup$ @Derek Holt: thanks, I'll look into presentations on the strong generating set, sounds promising. Btw I was not suggesting at all that using rewriting systems should be more efficient than other methods (especially if you start with a permutation group), it's just that sometimes your favorite group also comes with favourite generators, and it may help to express the results of various computations in terms of these. I was wondering if it was possible at all, with performance not completely awful, to work directly with a presentation -- as opposed to solving the word problem lots of times. $\endgroup$
    – Pierre
    Commented Aug 3 at 21:04
  • 2
    $\begingroup$ That also exists: IsomorphismFpGroupByGenerators. Anyway, I recommend you take a look at the Handbook of Computational Group Theory by Holt et al, and at the book "Permutation group algorithms" by Seress $\endgroup$
    – Max Horn
    Commented Aug 4 at 7:42

0

Reset to default

Browse other questions tagged .