3
$\begingroup$

Given two elements $a, b \in SL(2, \mathbb{F}_q)$, is there a way to find an efficient presentation $$\langle x, y \mid \text{relations}\rangle$$ of the subgroup $\langle a, b \rangle$?

My intention is taking two random matrices, computing the group law for the subgroup generated by them, and studying a particular recurrence relation using that group law.

$\endgroup$
  • $\begingroup$ Use the classification of subgroups of $\text{SL}_2$. The hardest case is finding generators and relations for $\text{SL}_2(\mathbb F_q)$ itself, and that must be known. $\endgroup$ – Noam D. Elkies Jul 28 '15 at 18:57
  • $\begingroup$ I have considered something similar before: Using Sternberg's presentation. I am interested in knowing if some algorithm exists for the task. Takes two matrices as an input, and spits the relations governing the group generated by them as an output. $\endgroup$ – user76098 Jul 28 '15 at 19:23
  • $\begingroup$ Two random matrices will generate the whole group, with high probability (which becomes higher as $q$ grows). There are certainly known presentations of the whole of $SL_2(q),$ basically due to Steinberg, as the OP says. $\endgroup$ – Igor Rivin Jul 29 '15 at 4:05
5
$\begingroup$

Yes there is algorithm for this due to John Cannon. The original reference is

CANNON, J.J. (1973): Construction of defining relators for finite groups, Discrete Math. 5, pp. 105–129.

You can also read about this and related algorithms in Chapter 6 of "Handbook of Computational Group Theory" by Holt, Eick, and O'Brien.

If you want an presentation on your own given generators, then it will only work for moderately small groups - perhaps up to about order $10^7$. You can compute presentations for much larger groups if you allow the algorithm to introduce new generators.

It is available in Magma as the command $\texttt{FPGroup}$ and also in $\textsf{GAP}$, although I am less familiar with $\textsf{GAP}$.

I just tried $\texttt{FPGroup}$ on ${\rm SL}(2,127)$ of order just over $2$ million and it took about 40 seconds to compute a presentation on two given generators with 5 relators and total relator length $70$.

The presentations computed in this way are not typically very nice in that the relators look like random strings of generators, but they are reasonably efficient in terms of relator length.

The algorithm works by attemtping coset enumeration over the trivial subgroup using the relators found so far. If this does not seem to be completing then you interrupt the process, introduce a new relator, and then resume the coset enumeration from where you left off. To find the new relator, you find the first missing entry in the coset table, use the group to work out what the entry should be, and then find the corresponding relator that will define that entry. A typical criterion for interrupting is when the total number of cosets that you have defined exceeds the actual number by $10\%$.

With a larger group, you could choose a subgroup $H$ of order about $\sqrt{|G|}$ (or for even larger groups, a chain of subsgroups with roughly equal indices), introduce generators of $H$ if necessary as new generators expressed as words in the original generators, and then comoute presentations first of $H$, and then of $G$, using coset enumeration over $H$.

Afterwards you could if eliminate the new generators to get a presentation on the original generators, but that would usually result in very long relators. Alternatively you can compromise by regarding the relators as straight line programs in the original generators, which can be helpful for example if you are trying to verfiy that a map defined on the group is a homomorphism.

I don't believe that the complexity has been analysed formally, but I would guess that it is between linear and quadratic in $|G|$. There is an obvious quadratic algorithm using the group multiplication table.

You can use the chain of subgroups idea using a stabilizer chain on a permutation group with base and strong generating set to get a presentation on the strong generators. This is polynomial in the degree of the permutation group.

$\endgroup$
  • $\begingroup$ Is there any complexity bound for this? $\endgroup$ – Igor Rivin Jul 29 '15 at 4:05
  • 1
    $\begingroup$ The command in GAP is IsomorphismFpGroupByGenerators(G,gens), which computes an isomorphism from the group G to a finitely presented group. One can then apply RelatorsOfFpGroup to the image of the computed isomorphism. $\endgroup$ – Frieder Ladisch Jul 29 '15 at 13:03
  • $\begingroup$ @IgorRivin If you are interested in complexity, probably MR1461483 Babai, L.(1-CHI-C); Goodman, A. J.(1-MOR-MS); Kantor, W. M.(1-OR); Luks, E. M.(1-OR-IS); Pálfy, P. P.(H-AOS) Short presentations for finite groups. J. Algebra 194 (1997), no. 1, 79–112. (and subsequent papers) is the better reference. It first computes a composition series and then uses information about the finite simple groups. (However Ree-groups are not done yet.) $\endgroup$ – ahulpke Jul 31 '15 at 12:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.