12
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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... $\endgroup$
    – YCor
    Oct 25, 2017 at 16:34
  • $\begingroup$ 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. $\endgroup$
    – YCor
    Oct 25, 2017 at 16:43
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Derek Holt
    Oct 25, 2017 at 16:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Oct 25, 2017 at 17:22

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Would you quote all 5 conditions? (I only get access to a preprint version with 9 sections) $\endgroup$
    – YCor
    Oct 25, 2017 at 22:29
  • $\begingroup$ @YCor I just did. $\endgroup$
    – Luc Guyot
    Oct 25, 2017 at 23:33
  • 1
    $\begingroup$ 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$? $\endgroup$
    – YCor
    Oct 25, 2017 at 23:41
  • 1
    $\begingroup$ What's a subgroup in Case (5) not in Case (4)? $\endgroup$
    – YCor
    Oct 26, 2017 at 0:19
  • 1
    $\begingroup$ I think you mean $Tr([A,B])=Q(Tr(A),Tr(B),Tr(AB))$. $\endgroup$
    – YCor
    Oct 26, 2017 at 23:18
15
$\begingroup$

The answer to your question is yes.

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.

$\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.