# For which series of finite simple groups is it algorithmically decidable whether they contain a homomorphic image of a given finitely presented group?

Let $G$ be a group given by a finite presentation. On the one hand, it is easy to determine the abelian invariants of $G$, or in other words, it is algorithmically decidable whether $G$ surjects to a cyclic group of prime order. On the other, it is known to be algorithmically undecidable whether $G$ has a finite quotient at all. Therefore there is at least one series of finite simple groups for which it cannot be decided by means of algorithms whether it contains a homomorphic image of $G$ or not.

Question: For which series of finite simple groups is it algorithmically decidable whether they contain a homomorphic image of a given finitely presented group?

• I don't see how your "therefore" follows. Can you elaborate? A priori it seems like it might be the case that the surjection problem can be solved for finite simple groups but that the classification of extensions is intractable enough to prevent it being solved for all finite groups. – Qiaochu Yuan May 20 '14 at 20:40
• @QiaochuYuan: A group has a finite simple quotient iff it has a finite quotient (or am I dense at the moment?) – Stefan Kohl May 20 '14 at 20:49
• @Stefan: ah, of course. I was being silly. – Qiaochu Yuan May 20 '14 at 20:55
• I suppose the answer could be "only the abelian ones"? – Ryan Budney May 20 '14 at 21:59
• @Ryan: Perhaps, or perhaps not -- I don't know. In any case the sporadics are covered by the low index subgroups procedure (not practically, but in theory at least) -- but I don't have a good feeling whether one can deal with any of the series, like e.g. the alternating groups or one of the 1-parameter series of groups of Lie type. – Stefan Kohl May 20 '14 at 22:08

UPDATE 22/10/17: The question is answered for many classes of simple quotients in this preprint of Bridson--Evans--Liebeck--Segal.

Here's what I know.

Martin Bridson and I proved the theorem mentioned in the question, namely that it is undecidable whether or not a fp group has a non-trivial finite quotient. As you say, it follow trivially that, for at least one infinite family $S$ of finite simple groups, it's undecidable whether or not a fp group has quotient from $S$, and so the question is raised of which families $S$ this is true for.

I have seen a very early preprint which resolves this in several cases. Since it isn't publicly available, I don't want to reveal the authors, but, iirc, it proves that this is undecidable for the alternating groups, and also for any family of classical Lie groups (eg PSL(n,q) for any q as n varies).

I believe that techniques of proof are expected to extend to the other families of groups of Lie type, and this may be work in progress.

Remarkably, although I don't recall the reference, it is known that the problem is decidable when $n=2$ and $q$ varies (that is, when $S=\{PSL(2,q)\}$), and I believe this also for the other classical groups. Based on this, Bridson has conjectured (in conversation) that the same holds for any fixed $n$ when $q$ varies (and similarly for the other classical groups).

• Derek Holt has given the missing reference in his answer. – HJRW May 20 '14 at 22:42
• Interesting answer. -- Thank you! -- By the way, my question arose from Bridson's talk on the workshop "Asymptotic properties of infinite groups" in Paris in March this year. – Stefan Kohl May 20 '14 at 22:47
• It's decidable more generally for any class of finite simple groups of bounded rank - this is a principle of Grothendieck. For example, if you want to see if there is an $SL(n,q)$ quotient, you compute the $SL(n)$ representation variety. There's a tautological representation into $SL(n,K)$, where $K$ is the field of functions. Then there are infinitely many $SL(n,q)$ quotients iff this map is Zariski dense (I think), essentially by strong approximation. – Ian Agol May 20 '14 at 23:48
• Perhaps I should also add that the Strong Approximation argument seems to address a slightly different question, namely whether or not a given group has infinitely many quotients from a family $S$. – HJRW May 21 '14 at 11:02
• Hmmm, I hadn't thought that through carefully. If there is a Zariski dense rep., then a generic rep. will be Zariski dense. So I think you just keep trying reps. until you hit a Zariski dense one, otherwise you'll find yourself on a proper subvariety. – Ian Agol May 21 '14 at 19:48

There are algorithms that can find all quotients of a finitely presented group isomorphic to ${\rm PSL}(2,q)$ for some $q$: see W. Plesken and A. Fabianska. An L2-quotient algorithm for finitely presented groups. J. Algebra, 322(3):914--935, 2009, and arXiv:1402.6788.

I believe that some progress has been made also with general $L_3(q)$ and $U_3(q)$ quotient algorithms. Roughly speaking, they just introduce variables for entries in the $2 \times 2$ or $3 \times 3$ matrices, and solve for them, using Gröbner basis type methods, although of course a lot of clever tricks are needed to enable them to work in practice.

I would guess that for any fixed $n$, it is possible in theory to test for the existence of finite simple quotients that have Lie rank $n$. That might be possible to prove.

I would also speculate that it might be undecidable whether there exists a quotient of the form $A_n$ for some $n$. Or, if you fix the field and vary the rank then it might also be undecidable: do there exist quotients of form $L_n(2)$ for example.

• Unfortunately I couldn't accept two answers -- in any case it was not easy to decide! – Stefan Kohl May 22 '14 at 10:56

Here's the proof for the decidability when the family $\mathcal{F}$ consists of all abelian simple groups $C_p$ along with all $PSL(2,q)$ for $q$ prime power.

The first remark is that a group has a quotient in $\mathcal{F}$ iff it has a nontrivial representation in $SL(2,q)$ for some $q$. (Including abelian simple groups in $\mathcal{F}$ allows me not to care about the image.)

The second remark is that a finitely generated group has a nontrivial representation in $SL(2,q)$ for some $q$ iff it has a nontrivial representation in $SL(2,K)$ for some field $K$. This does not use any kind of strong approximation, but simple facts that are basically the same as those showing that a f.g. linear group is residually finite. Namely if there's a nontrivial rep. in $SL_2(K)$, there's a nontrivial rep. in $SL_2(A)$ for some f.g. domain $A$, and since $A$ is residually a finite field we get a nontrivial rep. in $SL_2(F)$ for some finite field $F$.

Now the set of representations of a finitely presented group $\Gamma$ into $SL_2(A)$ can be described as $V(A)$, where $V$ is a $\mathbf{Z}$-defined affine variety, whose equations are explicitly defined according to a presentation of $\Gamma$. Here $V(A)=Hom(B,A)$, where $B$ is a finitely generated commutative ring, defined by a finite presentation explicitely output from the presentation of $\Gamma$.

Thus we are reduced to: given a finitely generated commutative ring $B$, determine whether there exists a field $K$ such that $Hom(B,K)$ is not reduced to a singleton $\{f_0\}$. Here $B$ comes with an explicit ring homomorphism $f_0$ onto $\mathbf{Z}$, coming from the trivial representation. Again by the standard argument, the above field $K$ can be chosen finite. Hence if we check all finite fields, we can detect when $Hom(B,K)\neq\{f_0\}$ for some field $K$. Conversely, a simple lemma (*) shows that if $Hom(B,K)=\{f_0\}$ for every field $K$, then the kernel of $f_0$ consists of nilpotent elements. Since the kernel of $f_0$ has explicit generators (the $x_i-f_0(x_i)$ where $x_i$ range over generators of $B$), in case these generators are nilpotent this can be detected in finite time. So we have an algorithm.

[Edit: proof of lemma (*): if $f_0(x)=0$ and $x$ is not nilpotent, since $B$ is a Jacobson ring there exists a quotient field $K$ in which $x$ has a nonzero image; then $K$ is finite, say of characteristic $p$ and using $f_0$, $B$ admits $K\times\mathbf{Z}/p\mathbf{Z}$ as a quotient, and thus admits two distinct homomorphisms to $K$, a contradiction.]

The argument, for each given $n$, extends to the family of all simple subquotients of $SL(n,q)$ for all prime powers $q$. Also it probably adapts, for given $(n,p)$ to the family of all simple subquotients of $SL(n,p^k)$. Now if one wishes to hold the family of say all $PSL(n,q)$ ($n$ fixed) and not its subquotients, one needs additional arguments.

• Thank you very much for your proof of decidability for the case of the series of the groups ${\rm PSL}(2,q)$! – Stefan Kohl May 21 '14 at 12:37