# Testing whether two elements of $\text{SL}(2, \mathbb{F}_{2^n})$ generate the entire group

Given two elements $A,B \in \text{SL}(2, \mathbb{F}_{2^n})$, is there a (computationally inexpensive) test one could perform to check whether together they generate the entire group?

• I'm writing as a comment as I'm not sure. First, you can check quickly whether they generate matrices as an algebra: namely this holds iff at least one of the families $(I,A,B,AB)$, $(I,A,B,BA)$, $(I,A,B,A^2)$, $(I,A,B,B^2)$ is linearly free. Second, you need to check that it's not contained in $SL_2$ of a smaller field. If this holds, then the traces $Tr(A)$, $Tr(B)$, $Tr(AB)$, $Tr(AB^{-1})$. I think that the converse is known (assuming absolute irreducibility) but I'm not 100% sure, namely that if these 4 traces belong to a subfield then so do all traces. Maybe somebody can confirm...
– YCor
Oct 25, 2017 at 16:34
• We also have to exclude the case of $A$, $B$ preserving a 1+1 decomposition. This should be easy, since then one of the following subgroups of index $\le 2$ is abelian: $\langle A,B^2,BAB\rangle$, $\langle A^2,B,ABA\rangle$, $\langle A^2,B^2AB,\rangle$. If I understand correctly the classification of maximal subgroups of $SL_2(q)$, this should be enough.
– YCor
Oct 25, 2017 at 16:43
• If it not equal to ${\rm SL}_2(2^n)$ then it is reducible, imprimitiive, semilinear, or defined over a proper subfield modulo scalars. Those are all easily tested for. In the imprimitive and semilinear cases, there is an abelian subgroup of index $2$. Oct 25, 2017 at 16:43
• It is worth mentioning that there is a fast Monte Carlo algorithm for deciding whenther an input subgroup $G$ of ${\rm GL}(n,q)$ contains ${\rm SL}(n,q)$. This takes a maximum error probability as input. A positive answer is guaranteed to be correct, but if $G$ does contain ${\rm SL}(n,q)$, then there is a probability of at most $\epsilon$ that it will incorrrectly answer no. Oct 25, 2017 at 17:22

The answer is yes, it is easy to check whether the ordered pair $(A, B)$ generates $\text{SL}_2(\mathbb{F}_q)$ for $q$ the power of a prime number. Indeed, there exist simple criteria according to Daryl McCullough and Marcus Wanderley, see [1, Section 11]. (Italic means that I am quoting the authors).

Claim. The pair $(A, B)$ generates $\text{SL}_2(\mathbb{F}_q)$ if and only if $$\text{Tr}(A, B) \Doteq (\text{Tr}(A), \text{Tr}(B), \text{Tr}(AB))$$ is an essential triple, i.e., doesn't satisfy any of the conditions $(1) - (5)$ of [1, Section 11].

For instance, the condition $(1)$ for a triple $(\alpha, \beta, \gamma) \in \mathbb{F}_q^3$ holds if at least two of $\alpha, \beta$ and $\gamma$ are zero. The image in $\text{PSL}_2(\mathbb{F}_q)$ of a pair $(A, B) \in \text{SL}_2(\mathbb{F}_q)^2$ such that $\text{Tr}(A, B) = (\alpha, \beta, \gamma)$ generates a dihedral group in this case. Condition $(2)$ holds if $\alpha^2 + \beta^2 + \gamma^2 - \alpha \beta \gamma - 2 = 2$, the left-hand side being the Fricke polynomial. This corresponds to the case of an affine subgroup of $\text{PSL}_2(\mathbb{F}_q)$, that is a subgroup which is conjugate to a subgroup of the image in $\text{PSL}_2(\mathbb{F}_q)$ of the subgroup of upper triangular matrices in $\text{SL}_2(\mathbb{F}_q)$. Condition $(4)$ holds if $\alpha, \beta$ and $\gamma$ lie in a proper subfield of $\mathbb{F}_q$. The remaining conditions are presented in the Addendum below.

It follows from the claim that OP's decision problem boils down to:

• deciding whether two elements of $\mathbb{F}_q$ are equal.
• deciding whether $k$ elements of $\mathbb{F}_q$ ($k \le 4$) generate a proper subfield.
• deciding whether an element of $\mathbb{F}_q$ belongs to a subfield of $\mathbb{F}_q$ generated by $k$ given elements ($k \le 4$).

The above claim follows from a theorem of Macbeath [1, Theorem 8.2] while the criteria are based on Dickson's Theorem [1, Theorem 6.1] and another theorem of Macbeath [1, Theorem 8.1].

Side note. Let $G$ be a finite group generated by $k$ elements. Let $\varphi_k(G) = \frac{\vert \text{Epi}(F_k, G) \vert}{\vert \text{Hom}(F_k, G) \vert}$, where $F_k$ denotes the free group on $k$ generators. The ratio $\varphi_k(G)$ is the probability that two uniformly chosen random elements generate $G$. By a theorem of Liebeck and Shalev, we have $\lim_n \varphi_2(G_n) = 1$ for any sequence of non-isomorphic finite simple groups, see [3, Theorem 1.1.1]. For a simple group $G_n(q)$ of Lie type of untwisted rank $n$, we have $\varphi_2(G_n(q)) = 1 - O(\frac{n^3 \log^2(q)}{q^n})$ by results of Kantor, Lubotzky, Liebeck and Shalev, see [3, Theorem 1.1.2].

Addendum. Let $Q(\alpha, \beta, \gamma) \Doteq \alpha^2 + \beta^2 + \gamma^2 - \alpha \beta \gamma - 2$ be the Fricke polynomial. This name was coined because of Fricke's trace identity $$\text{Tr}([A, B]) = Q(\text{Tr}(A), \text{Tr}(B), \text{Tr}(AB)).$$ Here are the five conditions derived by Daryl McCullough and Marcus Wanderley from Dickson's Subgroup Classification Theorem and Macbeath's Fricke polynomial criterion:

$(1)$ Dihedral case. At least two of $\alpha, \beta$ and $\gamma$ are zero.

$(2)$ Affine case. $Q(\alpha, \beta, \gamma) = 2$.

$(3.A_4)$ The elements $\alpha, \beta$ and $\gamma$ lie in $\{-1, 0, 1\}$ and $Q(\alpha, \beta, \gamma) = 0$.

$(3.S_4)$ The elements $\alpha, \beta$ and $\gamma$ lie in $\{\pm 1, \pm \sqrt{2}\}$ and $Q(\alpha, \beta, \gamma) = 1$, where $\sqrt{2}$ denotes one root of $X^2 - 2$.

$(3.A_5)$ It's complicated! The authors redirect us to [2, Main Theorem (3)].

$(4)$ Affine or $SL_2(q')$. The elements $\alpha, \beta$ and $\gamma$ lie in a proper subfield of $\mathbb{F}_q$.

$(5)$ Affine or $SL_2(q')$ or $PGL_2(q')$. The integer $q$ is odd, $\alpha^2,\beta^2,\gamma^2$ and $\alpha \beta \gamma$ lie in a proper subfield $\mathbb{F}_{q'}$ of $\mathbb{F}_q$ and at least one of $\alpha, \beta$ and $\gamma$ does not lie in $\mathbb{F}_{q'}$.

The cited article (a very nice paper!) contains more details, and of course, the corresponding proofs.

[1] D. McCullough, M. Wanderley, "Nielsen equivalence of generating pairs of $\text{SL}(2, q)$", 2013.

[2] D. McCullough, "Exceptional subgroups of $\text{SL}(2, F )$". Preprint available here, accessed 4 January 2013.

[3] I. Pak, "What do we know about the product replacement algorithm?", 2000.

• Would you quote all 5 conditions? (I only get access to a preprint version with 9 sections)
– YCor
Oct 25, 2017 at 22:29
• @YCor I just did. Oct 25, 2017 at 23:33
• Thanks. Looking for "Fricke polynomial" in Google, I can find for only, for each group word $w\in F_2$, a Fricke polynomial $P_w$. What is $Q$?
– YCor
Oct 25, 2017 at 23:41
• What's a subgroup in Case (5) not in Case (4)?
– YCor
Oct 26, 2017 at 0:19
• I think you mean $Tr([A,B])=Q(Tr(A),Tr(B),Tr(AB))$.
– YCor
Oct 26, 2017 at 23:18

The subgroups of ${\rm SL}(2,q)$ were classified by Dickson in 1901 (and probably earlier). For more general questions about subgroups of ${\rm GL}(n,q)$, there is a theorem of Aschbacher that classifies them into nine types, and is used as the basis of algorithms for identifying these subgroups.

Using these results, we find that a proper subgroup of ${\rm SL}(2,q)$ with $q=2^n$ must be either reducible, imprimitive and isomorphic to $D_{2(q-1)}$, semilinear and isomorphic to $D_{2(q+1)}$, or conjugate to a subgroup of ${\rm SL}(2,r)$ where $r = 2^m$ with $m|n$.

For testing reducibility there is the efficient $\mathtt{MeatAxe}$ algorithm.

There are general tests for imprimitivity and semilinearity, but in this case it would probably be easiest to find look for an abelian subgroup of index $2$.

As YCor mentioned in the comments, you can test for definability over a subfield. Usually you start by calcuating the characteristic polynomials of lots of random group elements, and if their coefficients all lie in a subfield then it is is very likely that the whole group does. There is a method of finding the conjugating matrix to verify this, but I would have to look that up.

There are two software packages with extensive facilities for these types of calculations, GAP and Magma. I am more familiar with Magma, so I will mention some of the commands that you could use to do this. $\mathtt{IsIrreducible}$, $\mathtt{IsPrimitive}$, $\mathtt{IsOverSmallerField}$, and and $\mathtt{IsSemiLinear}$ do what you might expect.

It is possible that if $q$ is very large then you could run into some problems related to discrete log calculation, but I don't think so if you just want a yes or no answer.