{'fraction_non_alphanumeric': 0.040179491651735455, 'fraction_numerical': 0.017758891337783626, 'mean_word_length': 3.552331456619027, 'pattern_counts': {'":': 2, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 43, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The triviality problem for profinite completions

We prove that there is no algorithm that can determine whether or not a finitely presented group has a non-trivial finite quotient; indeed, this remains undecidable among the fundamental groups of compact, non-positively curved square complexes. We deduce that many other properties of groups are undecidable. For hyperbolic groups, there cannot exist algorithms to determine largeness, the existence of a linear representation with infinite image (over any infinite field), or the rank of the profinite completion.


Introduction
The basic decision problems for finitely presented groups provided a guiding theme for combinatorial and geometric group theory throughout the twentieth century. Activity in the first half of the century was framed by Dehn's articulation of the core problems in 1911 [16], and it reached a climax in 1957-58 with the proof by Novikov [28] and Boone [9] that there exist finitely presented groups with unsolvable word problem. In the wake of this, many other questions about general finitely presented groups were proved to be algorithmically unsolvable (cf. Adyan [1,2], Rabin [32], Baumslag-Boone-Neumann [5]). In the decades that followed, the study of decision problems shifted towards more refined questions concerning the existence of algorithms within specific classes of groups, and to connections with geometry and topology. However, certain basic decision problems about general finitely presented groups were not covered by the techniques developed in midcentury and did not succumb to the geometric techniques developed in the 1990s. The most obvious of these is the following: can one decide whether or not a group has a proper subgroup of finite index?
Our main purpose here is to settle this question.
Theorem A. There is no algorithm that can determine whether or not a finitely presented group has a proper subgroup of finite index.
The technical meaning of this theorem is that there is a recursive sequence of finitely presented groups G n with the property that the set of natural numbers tn P N | DH Ĺ G n , |G n {H| ă 8u is recursively enumerable but not recursive. More colloquially, it says that the problem of determining the existence of a proper subgroup of finite index is undecidable.
We shall strengthen Theorem A by proving that the existence of finite-index subgroups remains undecidable in classes of groups where other basic decision problems of group theory are decidable, such as biautomatic groups and the fundamental groups of compact, non-positively curved square complexes. We include this last refinement in the following geometric strengthening of Theorem A.
Theorem B. There is no algorithm that can determine if a compact square complex of non-positive curvature has a non-trivial, connected, finite-sheeted covering.
There are various other natural reformulations of Theorem A (and its refinements), each creating a different emphasis. For emphasis alone, one could rephrase Theorem A as "the triviality problem for finitely presented profinite groups is undecidable": there is no algorithm that, given a finitely presented group G, can decide whether the profinite completion p G is trivial. More substantially, since all finite groups are linear (over any field) and linear groups are residually finite, we can rephrase our main result as follows: There is no algorithm that can determine whether or not a finitely presented group has a non-trivial finite-dimensional linear representation (over any field); indeed the existence of such a representation is undecidable even for the fundamental groups of compact, non-positively curved square complexes.
In Section 2 we shall explain how classical work of Slobodskoi [35] on the universal theory of finite groups can be interpreted as a profinite analogue of the Novikov-Boone theorem: by definition, the profinite completion p G is the inverse limit of the finite quotients of G, and the kernel of the natural homomorphism G Ñ p G consists of precisely those g P G that have trivial image in every finite quotient of G; implicitly, Slobodskoi constructs a finitely presented group G in which there is no algorithm to determine which words in the generators represent such g P G. In the setting of discrete groups, one can parlay the undecidability of the word problem for a specific group into the undecidability of the triviality problem for finitely presented groups by performing a sequence of HNN extensions and amalgamated free products, as described in Section 3. Although the profinite setting is more subtle and does not allow such a direct translation, we will attack the triviality problem from a similar angle, deducing Theorem A from Slobodskoi's construction and the following Encoding Theorem. This is the key technical result in this paper; its proof is significantly more complex than that of the corresponding theorem for discrete groups and the details are much harder.
Theorem C (Encoding Theorem). There is an algorithm that takes as input a finite presentation xA | Ry for a group G and a word w P F pAq and outputs a presentation for a finitely presented group G w such that Theorems A and C imply that various other properties of finitely presented groups cannot be determined algorithmically. The properties that we shall focus on, beginning with the property p G -1 itself, are neither Markov nor co-Markov, so their undecidability cannot be established using the Adyan-Rabin method.
Some of the most profound work in group theory in recent decades concerns the logical complexity of (word-)hyperbolic groups. In that context, one finds undecidability phenomena associated to finitely generated subgroups but the logical complexity of hyperbolic groups themselves is strikingly constrained (see, for instance, [34] and [24]). Nevertheless, we conjecture that there does not exist an algorithm that can determine if a hyperbolic group has a non-trivial finite quotient (Conjecture 9.5). This conjecture would be false if hyperbolic groups were all residually finite. Indeed, we shall prove (Theorem 9.6) that this conjecture is equivalent to the assertion that there exist hyperbolic groups that are not residually finite.
We shall also prove that, as it stands, Theorem A allows one to establish various new undecidability phenomena for hyperbolic groups. We recall some definitions. The first betti number of a group Γ is the dimension of H 1 pΓ, Qq and the virtual first betti number vb 1 pΓq is the (possibly infinite) supremum of b 1 pKq over all subgroups K of finite index in Γ. A group is large if it has a subgroup of finite index that maps onto a non-abelian free group. Note that if Γ is large then vb 1 pΓq " 8.
The following theorem summarizes our undecidability results for hyperbolic groups.
Theorem D. There do not exist algorithms that, given a finite presentation of a torsion-free hyperbolic group Γ, can determine: (1) whether or not Γ is large; (2) for any 1 ď d ď 8, whether or not vb 1 pΓq ě d; (3) whether or not every finite-dimensional linear representation of Γ has finite image; (4) for a fixed infinite field k, whether or not every finite-dimensional representation of Γ over k has finite image; (5) whether or not, for any fixed d 0 ą 2, the profinite completion of Γ can be generated (topologically) by a set of cardinality less than d 0 .
We shall prove in Section 8 that the profinite-rank problem described in item (5) remains undecidable among residually-finite hyperbolic groups. In that context, the bound d 0 ą 2 is optimal, because the profinite rank of a residually-finite group Γ is less than 2 if and only if Γ is cyclic, and it is easy to determine if a hyperbolic group is cyclic. Furthermore, Theorem 9.6 tells us that for d 0 ď 2, problem (5) is decidable if and only if every hyperbolic group is residually finite.
Item (1) should be contrasted with the fact that there does exist an algorithm that can determine whether or not a finitely presented group maps onto a non-abelian free group: this is a consequence of Makanin's deep work on equations in free groups [26].
Our final application is to the isomorphism problem for the profinite completions of groups. The arguments required to deduce this from Theorem A are lengthy and somewhat technical, so we shall present them elsewhere [11].
Theorem E. There are two recursive sequences of finitely presentations for residually finite groups A n and B n together with monomorphisms f n : A n Ñ B n such that: (1) p A np B n if and only if the induced map on profinite completionŝ f n is an isomorphism; and (2) the set tn P N | p A n fl p B n u is recursively enumerable but not recursive.
This paper is organised as follows. In Section 2 we explain what we need from Slobodskoi's work. In Section 3 we lay out our strategy for proving Theorem C, establishing the notation to be used in subsequent sections and, more importantly, providing the reader with an overview that should sustain them through the technical arguments in Sections 4 and 5. Theorem C is proved in Section 6 and, with Slobodskoi's construction in hand, Theorem A follows immediately. Sections 5 and 6 form the technical heart of the paper. Many of the arguments in these sections concern malnormality for subgroups of virtually free groups. The techniques here are largely topological, involving the careful construction of coverings of graphs (and, implicitly, graphs of finite groups) and the analysis of fibre products in the spirit of John Stallings [36].
In Section 7 we prove that the existence of finite quotients remains undecidable in the class of non-positively curved square complexes. Section 8 deals with profinite rank, and the remaining results about hyperbolic groups are proved in Section 9. Acknowledgements. We first tried to prove Theorem A at the urging of Peter Cameron, who was interested in its implications for problems in combinatorics [14]. We are grateful to him for this impetus. We are also grateful to Jack Button and Chuck Miller for stimulating conversations about Theorem A and its consequences.

Slobodskoi's theorem
In this section we explain how the following theorem is contained in Slobodskoi's work on the universal theory of finite groups [35]. We write F pAq to denote the free group on a set A.
Theorem 2.1. There exists a finitely presented group G -xA | Ry in which there is no algorithm to decide which elements have trivial image in every finite quotient. More precisely, the set of reduced words tw P F pAq | w ‰ p G 1u is recursively enumerable but not recursive.
The theorem that Slobodskoi actually states in [35] is the following. 35]). The universal theory of finite groups is undecidable.
Slobodskoi's proof of Theorem 2.2 is clear and explicit. It revolves around a finitely presented group G " xa 1 , . . . , a n | r 1 , . . . , r m y that encodes the workings of a 2-tape Minsky machine M that computes a partially recursive function. Associated to this machine one has a disjoint pair of subsets S 0 , S 1 Ď N (denoted X and Y in [35]) that are recursively inseparable; S 0 is the set of natural numbers k such that M halts on input 2 k and S 1 is the set of k such that on input 2 k the machine M visits the leftmost square of at least one of its tapes infinitely often. To say that they are recursively inseparable means that there does not exist a recursive set D Ď N such that S 0 Ď D and S 1 X D " H.
By means of a simple recursive rule, Slobodskoi defines two sequences of words w pkq 1 , w pkq 2 pk P Nq in the letters A˘1. He then considers the following sentences Ψpkq in the first-order logic of groups: Ψpkq is the sentence that says the images of the words w pkq 1 and w pkq 2 are both trivial in any homomorphic image of the group G " xa 1 , . . . , a n | r 1 , . . . , r m y. More explicitly, one treats the a i as variables and defines Ψpkq " @a 1 , . . . , a n rpr 1 ‰ 1q _¨¨¨_ pr m ‰ 1q _ pw Slobodskoi proves that if k P S 1 then Ψpkq is true in every periodic group (in particular every finite group) [35,Lemma 6]. He then proves that if k P S 0 then Ψpkq is false in some finite group [35,Lemma 7].
Proof of Theorem 2.1. Let G " xA | Ry be the group constructed by Slobodskoi. The set tw P F pAq | w ‰ p G 1u is recursively enumerable: a naive search will eventually find a finite quotient of G in which w survives, if one exists. If the complement tw P F pAq | w " p G 1u were recursively enumerable, then the set would also be recursive. But S 1 Ď D and S 0 Ď N D, so this would contradict the fact that S 0 and S 1 are recursively inseparable. Remark 2.3. Kharlampovich proved an analogue of Slobodskoi's theorem for the class of finite nilpotent groups [23].
Remark 2.4. It follows easily from Theorem 2.1 and the Hopfian property of finitely generated profinite groups that there does not exist an algorithm that, given two finite presentations, can determine if the profinite completions of the groups presented are isomorphic or not. It is much harder to prove that the isomorphism problem remains unsolvable if one restricts to completions of finitely presented, residually finite groups [11].

A strategy for proving Theorem C
In this section we lay out a strategy for proving our main technical result, Theorem C. It is useful to think of Theorem C as a machine that, given a word in the seed group G, produces a group G w so that the (non)triviality of w P p G is translated into the (non)triviality of the profinite completion p G w . Although the techniques required to prove this are quite different from the arguments used to prove the corresponding result for discrete groups (which are straightforward from a modern perspective), the broad outline of the proof in that setting will serve us well as a framework on which to hang various technical results. The notation established here will be used consistently in later sections.
3.1. The discrete case. We fix a finitely presented group G " xA | Ry and seek an algorithm that, given a word w P F pAq, will produce a finitely presented group G w so that G w -1 if w " G 1 and G ãÑ G w if w ‰ G 1. The first such algorithm was described by Adyan [1,2] and Rabin [32]. There are many ways to vary the construction; cf. [19].
Replacing G by G˚xa 0 y and a P A by a 1 " aa 0 , if necessary, we may assume that A " ta 0 , . . . , a m u where each a i has infinite order. And replacing w by rw, a 0 s, we may assume that if w is non-trivial in G then it has infinite order. Let . . , myy and let G 2 " G 1˚x b m`1 y. Choose m`2 words that freely generate a subgroup of the normal closure of w P F pw, b m`1 q, say c j " pw b m`1 q j`1 wpw b m`1 q´1´j. Define The subgroup F 1 is free of rank m`2. If w " G 1 then F 2 ă G 2 is trivial. If w ‰ G 1 then F 2 is free of rank m`2 and F " F 1˚F2 is the free product.
We take two copies of G 2 and distinguish the elements and subgroups of the second by primes. Define G w to be the quotient of G 2˚G 1 2 by the relations where the isomorphism F -F 1 identifies F 1 with F 1 2 and F 2 with F 1 1 . In particular, the natural map G Ñ G 2 Ñ G w is injective and G w fl 1.
3.2. The profinite case. Given G " xA | Ry and w P F pAq, we have to construct, in an algorithmic manner, a finite presentation for a group G w so that p G w " 1 if and only if w " p G 1. The difficult thing to arrange is that G w have some non-trivial finite quotient if w ‰ p G 1.
Remark 3.1. Of the many problems one faces in adapting the preceding argument to the profinite setting, the most fundamental concerns our use of HNN (equivalently, Bass-Serre) theory to see that the natural map G Ñ G w is injective if w ‰ 1. Sobering examples in this connection are the simple groups of Burger and Mozes [12] groups: these are amalgamations L 1˚Λ 1 -Λ 2 L 2 where L 1 -L 2 is a finitely generated free group and Λ i ă L i is a subgroup of finite index. (Earlier examples in a similar vein were given by Bhattacharjee [8] and Wise [42].) Step 1: controlling the order of the generators a i and of w.
What matters now is the order of a i and w in finite quotients of G. In order to retain enough finite quotients after performing the HNN extensions in step 2, we must ensure that if w ‰ 1 in p G then w and the generators all have the same order in some finite quotient of G (or a proxy of G). It will transpire that in fact we need significantly more control than this. This control is established in Section 4, where the key result is Theorem 4.3.
Step 2: a map G Ñ p G 1 whose image is trivial iff w " 1. As in the discrete case, we define a group G 1 in which the generators of G are made conjugate to w. If w " p G 1 then G Ñ p G 1 is trivial and p G 1 is the profinite completion of the free group F 0 on the stable letters b i . When w ‰ p G 1, we obtain finite quotients of G 1 in which w survives. But this is not enough: for reasons that will become apparent in step 4, we have to work hard to find virtually free quotients η : G 1 Ñ Γ 0 where F 0 injects and is malnormal.
We remind the reader that a subgroup H ă G is termed malnormal if g´1Hg X H " 1 for all g R H. This is the central concept of Section 5 and continues to be a major focus in Section 6.
Step 3: the construction of Γ and F . In G 2 " G 1˚x b m`1 y we have to demand far more of the subgroup F 2 than in the discrete case. Consequently, a much more subtle construction of the elements c i is required, and this is the subject of Section 5. If w " where it is malnormal (Proposition 6.9).
Step 4. With our more sophisticated definition of c i and F in hand, we define G w to be the quotient of G 2˚G 1 2 by the relations as a malnormal amalgamation of virtually free groups, this is residually finite, by a theorem of Wise [41].
Remarks 3.2. (1) A crucial feature of the above process is that each step is algorithmic: judicious choices were made but these choices depended in an algorithmic manner on the parameter w alone. In particular, the algorithm gives an explicit finite presentation for G w .
(2) The definition of G w makes no assumption about the existence or nature of the finite quotients of G in which w has non-trivial image. Equally, the proof that G w has a non-trivial finite quotient if w ‰ p G 1 requires only the existence of a finite quotient in which w has nontrivial image; it does not require any knowledge about the nature of such a quotient.

A strengthening of omnipotence
The main result of this section (Theorem 4.3) strengthens Wise's theorem on the omnipotence of free groups [40].
Given a virtually free group Γ and a finite list of elements γ 1 , . . . , γ n P Γ, we would like to control the (relative) orders of these elements in finite quotients of Γ. Ideally, we would like to dictate orders arbitrarily, but this is too much to expect. For example, if γ 1 and γ 2 have conjugate powers in Γ, then the possible orders for the image of γ 2 are constrained by those of γ 1 . To isolate this problem, we make the following definition.
Definition 4.1. Let Γ be a group. Elements γ 1 , γ 2 P Γ are said to be independent if they are of infinite order and no non-zero power of γ 1 is conjugate to a non-zero power of γ 2 . An m-tuple pγ 1 , . . . , γ m q of elements from Γ is independent if γ i and γ j are independent whenever 1 ď i ă j ď m.
The next definition makes precise the idea that the orders of independent sets of elements can be controlled in finite quotients.

Definition 4.2.
A group Γ is omnipotent if, for every m ě 2 and every independent m-tuple pγ 1 , . . . , γ m q of elements in Γ, there exists a positive integer κ such that, for every m-tuple of natural numbers pe 1 , . . . , e m q there is a homomorphism to a finite group q : Γ Ñ Q such that opqpγ i qq " κe i for i " 1, . . . , m.
The preceding definitions are due to Wise [40], who proved that free groups are omnipotent. Bajpai extended this to surface groups [4], and the second author proved that all Fuchsian groups are omnipotent [37]. It follows from Wise's recent deep work on special cube complexes (specifically, from the Malnormal Special Quotient Theorem [39]), that fundamental groups of virtually special groups are omnipotent. In particular, virtually free groups are known to be omnipotent. However, we do not want to obscure this simpler setting with the extra complications of special cube complexes and, more importantly, Wise's method of proof does not provide the additional strengthening contained in item (2) of the following theorem. This refinement is a vital component of the strategy described in the previous section: it will be needed to establish malnormality in Lemma 6.4 and Proposition 6.9. Theorem 4.3. Let Γ be a virtually free group and let pγ 1 , . . . , γ m q be an independent m-tuple of elements of Γ. There is a positive integer κ such that, for every m-tuple of positive integers pe 1 , . . . , e m q, there is a homomorphism to a finite group q : Γ Ñ Q such that: (1) opqpγ i qq " κe i for i " 1, . . . , m; and, (2) furthermore, xqpγ i qy X xqpγ j qy " 1 whenever i ‰ j.
The following lemma is a key step in the proof of omnipotence for free groups [40,Theorem 3.6] and Fuchsian groups [37, Proposition 4.1]. To lighten the notation, we write o i for the order of the image of γ i P Γ in Γ{F .
Lemma 4.4. Let Γ be a free group. If pγ 1 , . . . , γ m q is an independent m-tuple, then there exists a normal subgroup F of finite index in Γ and We need to improve Lemma 4.4 to deal with virtually free groups Γ.
Lemma 4.5. Let Γ be a virtually free group. If pγ 1 , . . . , γ m q is an independent m-tuple, then there exists a normal subgroup F of finite index in Γ and retractions φ i : F Ñ xγ o i i y -Z with the property that φ i pδγ o j j δ´1q " 0 for any δ P Γ and any j ‰ i. Proof. By hypothesis, there is a short exact sequence with F free and Q finite.
Suppose, then, that we are given independent γ 1 , . . . , γ m P Γ. We replace each γ i by g i :" γ o i i . Note that g 1 , . . . , g n P F are independent. Next, we enlarge this list by adding to it elements of Γ that are conjugate to the g i in Γ but not in F . To this end, we fix a set of coset representatives r Q " tq | q P Qu for F in Γ, with1 " 1, and define g iq "qg iq´1 . Since the γ i are independent, no element of tg iq | q P Qu has a non-zero power that is conjugate to a non-zero power of an element of tg jq | q P Qu if i ‰ j. However, the indexed set pg iq | q P Qq may fail to be independent since it is quite possible that g iq will be conjugate to g˘1 iq 1 for some q ‰ q 1 . (In a virtually free group an element of infinite order x cannot be conjugate to x p with |p| ą 1, so higher powers are not a worry.) To account for such coincidences we make deletions from the list pg iq | q P Qq, reducing it to pg iq | q P Qrisq, say. This reduced list consists of a set of orbit representatives for the action of Q by conjugation on the F -conjugacy classes of cyclic subgroups of the form xf g i f´1y with f P F .
We now apply Lemma 4.4 to the concatenation of the lists pg 1q | q P Qr1sq, . . . , pg mq | q P Qrmsq, which is independent in F . Thus we obtain retractions φ i : F Ñ xg i1 y -Z with the property that φ i pδg jq δ´1q " 0 whenever δ P F and pj, qq ‰ pi, 1q.
Consider δ and g j for j ‰ i. Write δ " δ 1q for some δ 1 P F . Ifq P Qrjs then we have φ i pδg j δ´1q " φ i pδ 1 g jq pδ 1 q´1q " 0 as required. On the other hand, ifq R Qrjs then there exists f P F such that g jq " f g˘1 jq 1 f´1 for some q 1 P Qrjs. Therefore which finishes the proof.
With Lemma 4.5 in hand, we can prove Theorem 4.3.
Proof of Theorem 4.3. Let η : Γ Ñ Γ{F be as in Lemma 4.5. Fix a set of coset representatives c j for F in Γ with c 1 " 1. For each γ i , fix a positive integer N i (to be specified later) and consider the composition Then, consider the direct product where i c j is the automorphism of F given by conjugation by c j . It is now clear that opΨ i pγ therefore has the property that To prove the theorem, take κ " |Γ{F | 2 and N i " κe i {opηpγ i qq. Then we have opΦpγ i qq " κe i by the computation above, which proves the first assertion.
To prove the second assertion, suppose that the intersection xΦpγ 1 qy X xΦpγ 2 qy (say) is non-trivial. Then it contains a minimal non-trivial subgroup, which in a finite cyclic group is of prime order p. That is, the intersection contains the non-trivial subgroup We have opηpγ i qq | κe i {p (because κ " |Γ{F | 2 ), and so γ One of the coordinates of the homomorphism Ψ is φ 1 , and so it follows that On the one hand, we have φ 1 pγ κe i {p 2 q " 0 by the definition of φ 1 and Lemma 4.5. On the other hand, φ 1 pγ and κe i {popηpγ 1 qq ă opφ 1 pγ opηpγ 1 qq 1 qq " N 1 " κe 1 {opηpγ 1 qq. This contradiction completes the proof.

Constructing Malnormal Subgroups
The role that malnormality plays in our strategy was explained in Section 3. The main result in this section is Proposition 5.9, but several of the other lemmas will also be required in the next section. Fibre products of morphisms of graphs, as described by Stallings [36], play a prominent role in many of our proofs.
More generally, a family tH i u of subgroups of Γ is said to be almost malnormal if |H i X H γ j | " 8 implies that i " j and γ P H j . Similarly, we may also speak of malnormal families of subgroups.
Note that if H is torsion-free and almost malnormal then it is in fact malnormal.
The first fact we record is trivial but extremely useful.
The next lemma, which again admits a trivial proof, enables one to deduce almost malnormality from virtual considerations.
The malnormality of a family of subgroups of a free group can be determined by a computation using the elegant formalism of fibre products, as we will now explain.
Consider a pair of immersions of finite graphs ι 1 : Y 1 Ñ X and ι 2 : Y 2 Ñ X. Recall that the fibre product of the maps ι 1 and ι 2 is defined to be the graph The fibre product comes equipped with a natural immersion κ : Y 1ˆX Y 2 Ñ X. For any py 1 , y 2 q, Stallings pointed out that The next lemma follows immediately from this discussion. In particular, this gives an algorithm to determine whether or not a given family of subgroups of a free group is malnormal.
Unlike Lemma 5.4, the next lemma is not always applicable. However, it gives a useful sufficient condition for malnormality, which can sometimes be applied in situations where Lemma 5.4 is too cumbersome to apply in practice. Let Z Γ pgq denote the centralizer of an element g in a group Γ. Proof. Let ρ : Γ Ñ H be a retraction. Suppose that h P H 1 and h γ P H. Then h γ " h ρpγq , which implies that γρpγq´1 P Z Γ phq and so γ P H, as required.
We now develop some simple examples.
Example 5.6. If Γ is a group and H is a free factor then H is malnormal in Γ. This is an immediate consequence of Lemma 5.5, since free factors are retracts.
The following easy example, which will be useful later, illustrates how Lemmas 5.3 and 5.4 can be used to prove almost malnormality in virtually free groups.
Example 5.7. Suppose that A is a finite group and B is any subgroup of A. Then the natural copy of H " B˚Z inside Γ " A˚Z is almost malnormal.
To see this, realize Γ as the fundamental group of a graph of groups X with a single vertex labelled A and a single edge with trivial edge group. The kernel of the retraction Γ Ñ A implicit in the notation is a normal, free subgroup F of finite index. Let T be the Bass-Serre tree of X . The quotient F zT is a graph X with a single vertex and |A| edges te a | a P Au, and the natural A-action is by left translation. The subgroup H X F is carried by the subgraph Y " Ť bPB e b . The quotient map Γ Ñ A identifies HzΓ{F with BzA, so a set of double-coset representatives for the former is provided by any set ta i u of right-coset representatives for B in A. The subgroup H a i X F is carried by the subgraph a´1 i Y : under the immersion (where the map Z Ñ X is inclusion on each component), the fundamental groups of the components are mapped to the family of subgroups tH a i X F u.
Note that, as subgraphs of X, a´1 i Y and a´1 j Y have no edges in common if i ‰ j. Therefore, every off-diagonal component of ZˆX Z is a vertex and hence simply connected.
It follows that tH a i X F u forms a malnormal family in F by Lemma 5.4, and so H is almost malnormal in Γ by Lemma 5.3.
The following construction provides us with the supply of malnormal subgroups that we shall need to prove Theorem C.
Lemma 5.8. Let Λ 2 -xα, βy be free of rank two. For each integer N , let For all N ą 6, the subgroup q N pxα, u, vyq is malnormal in Q N and free of rank 3.
Proof. Consider the imagesᾱ " q N pαq,β " q N pβq,ū " q N puq and v " q N pvq. Let F be the kernel of the retraction Q N Ñ Z{N that maps α Þ Ñ 0 andβ Þ Ñ 1. As above, F may be thought of as the fundamental group of a graph X with a single vertex and with N edges te i u iPZ{N , on which Z{N " xβy acts by left translation. Represent xᾱ,ū,vy by the usual immersion of core graphs ι : Y Ñ X. As long as N ě 4, the core graph Y is easily computed explicitly using Stallings folds (see Figure  1), and is seen to have rank 3 as required.  Let Y i " Y for each i " 0, . . . , N´1, and consider the disjoint union where the map on Y i isβ i˝ι . To prove malnormality, it suffices to argue that every off-diagonal component of the fibre product ZˆX Z is simply connected.
Suppose some off-diagonal component is not simply connected. Translating by an element of xβy, we may assume that it arises as part of the fibre product Y 0ˆX Y i for some i. Since the image of ι only contains the edges e i for´1 ď i ď 2, this fibre product contains no edges unless 0 ď i ď 3 (because N ą 6).
Therefore, it is enough to check that the off-diagonal components of Y 0ˆX Y 0 are simply connected, and that every component of Y 0ˆX Y i is simply connected, where i " 1, 2, 3. The off-diagonal components of Y 0ˆX Y 0 are points; for i " 1, 2, 3, the fibre product Y 0ˆX Y i has 4´i edges, and a direct computation shows that each of these is a forest. The fibre products Y 0ˆX Y 0 and Y 0ˆX Y 1 are illustrated in Figure  2, while Y 0ˆX Y 2 and Y 0ˆX Y 3 are left as easy computations for the reader.  Figure 2. The fibre products Y 0ˆX Y 0 and Y 0ˆX Y 1 , displayed as subsets of the direct products Y 0ˆY0 and Y 0ˆY1 . Note that the only non-simply-connected component is the diagonal component of Y 0ˆX Y 0 .
From the 3-generator case, we immediately obtain malnormal subgroups with arbitrarily many generators. Proposition 5.9. Let Λ 2 and q N be as above. For any m, there exist tγ 0 , . . . , γ m u P rΛ 2 , Λ 2 s such that, for all N ą 6, the subgroup q N pxα, γ i yq is malnormal in Q N and free of rank m`2.
Proof. Take any malnormal, pm`1q-generator subgroup xγ i y of the subgroup xu, vy constructed in Lemma 5.8.

The proof of Theorem C
In this section we prove Theorem C, following the strategy laid out in Section 3. As mentioned in the introduction, Theorem A follows immediately, using Theorem 2.1.
We are given a finitely presented group G " xA | Ry " xa 1 , . . . , a m | r 1 , . . . , r n y and a word w P F pAq.
Step 1: improving the input. We start by proving some lemmas that improve the input G and w. Lemma 6.1. There is an algorithm that takes as input a finitely presented group G -xA | Ry and a word w P F pAq and outputs a finite presentation xA 1 | R 1 y for a group G 1 and a word w 1 P F pA 1 q such that: (1) w 1 " Proof. Take 2m`1 copies G pjq of G and let a ij be the copy of a i in G pjq ; similarly, let w j be the copy of w in G pjq . We will always take the j index modulo 2m`1. Set and note that w j " p G 1 1 if and only if w " p G 1. Now consider the following generating set A w for G 1 : Let η : G Ñ Q be a finite quotient in which w survives, and let η j : G pjq Ñ Q pjq be the corresponding quotient of G pjq . Let be the natural quotient map. Suppose now that η 1 pa ij w j`m`1 w i`j q " η 1 pa i 1 j 1 w j 1`m`1w i 1`j1 q for some i, j, i 1 , j 1 . Because i, i 1 ă m`1, all three terms lie in different free factors and one can deduce that j " j 1 and i " i 1 . Setting w 1 " w 1 finishes the proof.
Using Lemma 6.1, we may assume that the group G, the generating set A " ta 1 , . . . , a m u and w P F pAq have the properties provided by that lemma. Let G 1 " G˚xa 1 0 y, let a 1 i " a i a 1 0 and let w 1 " rw, a 1 0 s. This gives the following improvement: if w " p G 1 then w 1 " p G 1 1, and if w " p G 1 then there is an epimorphism η : G 1 Ñ Γ where: (1) Γ is virtually free; (2) the pm`2q-tuple pηpa 1 0 q, . . . , ηpa 1 m q, ηpw 1 qq is independent. By Theorem 4.3, we obtain the following consequence. Proposition 6.2. There is an algorithm that takes as input a finitely presented group G -xA | Ry and a word w P F pAq and outputs a finite presentation xA 1 | R 1 y for a group G 1 and a word w 1 P F pA 1 q such that: then, for any N P N, there exists a homomorphism to a finite group η : G 1 Ñ Q such that: (a) opηpa 1 qq " opηpw 1 qq ě N for all a 1 P A 1 ; and (b) xηpa 1 i qy X xηpa 1 j qy " xηpa 1 i qy X xηpw 1 qy " 1 whenever i ‰ j. To avoid being overwhelmed by notation, we rename G 1 as G, A 1 as A and w 1 as w.
Step 2: a map G Ñ p G 1 whose image is trivial iff w " 1. We define a new finitely presented group G 1 " G˚xb 0 , . . . , b m y{xxw b i " a i | i " 0, . . . , myy and let F 0 denote the subgroup xb 0 , . . . , b m y. Note that there is a retraction ρ : G 1 Ñ F 0 , whence F 0 is free of rank m`1. Note too that there is a simple algorithm for deriving a finite presentation of G 1 from G and w. The following lemma is clear. If w ‰ p G 1 then we have the finite quotient η : G Ñ Q guaranteed by Proposition 6.2. We will extend η to an epimorphism from G 1 to a virtually free group Γ 0 . We will continute to denote this epimorphism by η and, to further simplify notation, we will use bars to denote the image of an element or a subgroup under η, so ηpwq "w, ηpF 0 q " F 0 etc. This Γ 0 is the fundamental group of a graph of groups X 0 with a single vertex (which we take to be our basepoint), labelled Q, and edges e i for i " 0, . . . , m with both ends incident at the vertex. The stable letter associated to e i isb i , andwb i "ā i (note that opwq " opā i q in Q).
We write T 0 for the Bass-Serre tree of the graph of groups X 0 .
Lemma 6.4. If w ‰ p G 1 then, for all natural numbers N , the group G 1 has a virtually free quotient η : G 1 Ñ Γ 0 with the following properties: (1) for all a P A, N ď opwq " opāq ă 8; (2) F 0 is free of rank m`1 and malnormal in Γ 0 .
Proof. Let η : G Ñ Q be the quotient guaranteed by Proposition 6.2, and let η : G 1 Ñ Γ 0 be the extension constructed above. Then the first assertion is immediate, and the existence of the retractionρ : Γ 0 Ñ F 0 shows that F 0 is indeed free of rank m`1.
It remains to prove that F 0 is malnormal. By Lemma 5.5, it suffices to prove that Z Γ 0 phq Ď F 0 for all h P F 0 1.
Suppose therefore that h P F 0 1 and rh, γs " 1. Let h "b 1 i 1 . . .b k i k , where i P t˘1u for all i. We may assume that this decomposition is cyclically reduced.
We next claim thatρpγ´1qγ P Q. Because rh, γs " 1, γ preserves the line Axisphq Ď T 0 , with orientation. In particular, if˚is the vertex of T 0 stabilized by Q, the segment r˚, γ˚s is contained in Axisphq. There exists β P F 0 such that β˚" γ˚, so β´1γ P Q. Therefore 1 "ρpβ´1γq " β´1ρpγq and the claim follows.
We are trying to prove that γ P Z Γ 0 phq. Sinceρpγq P Z Γ 0 phq, it follows from the claim that we may assume that γ P Q. It follows that γ fixes the whole of Axisphq. But, by item (2)(b) of Proposition 6.2, no non-trivial element of Γ 0 fixes a subset of diameter greater than 2 in the minimal F 0 -invariant subtree of T , and therefore γ " 1 as required.
Step 3: the free subgroups F 1 , F 2 and F . Let G 2 " G 1˚x ty and let F 1 be the free subgroup F 0˚x ty of rank m`2. It will later be convenient to write b m`1 " t. Casting t and w in the roles of α and β, we choose c j " γ j as in Proposition 5.9, for j " 0, . . . , m`1, and write F 2 for the subgroup of G 2 generated by the c j .
Since c j is in the commutator subgroup of xt, wy, we have c j P xxwyy and hence F 2 is trivial if w " We analyse what happens when w ‰ p G 1. Let η : G 1 Ñ Γ 0 be the virtually free quotient guaranteed by Lemma 6.4. We will extend η to a homomorphism from G 2 onto a virtually free group Γ; we will then continue to denote this homomorphism by η, and continue to denote η-images by bars.
Consider the graph of groups X obtained from X 0 by adjoining a single loop e m`1 with trivial edge group; denote the corresponding stable letter byt (it will also sometimes be convenient to denote it byb m`1 ). We define Γ " π 1 X and extend η to η : G 2 Ñ Γ by setting ηptq "t.
Let F " xF 1 , F 2 y. The remainder of this section is devoted to an analysis of the image ηpF q " F Ď Γ.
Let K 0 Γ 0 be a normal, free subgroup of finite index. The quotient K 0 zT 0 is a graph X 0 with fundamental group K 0 ; X 0 may be thought of as a finite-sheeted covering space of the graph of groups X 0 (this can be made formal, but we will avoid using it explicitly). There is a natural vertex-transitive left-action of P " Γ 0 {K 0 on X 0 , in which the stabilizer of each vertex is conjugate to Q (note that Q embeds into P since Q X K 0 " 1). In particular, fixing a base vertex˚for X 0 , we may identify the vertices of X 0 with the coset space P {Q.
There is a minimal F 0 -invariant subtree The inclusion map descends to a combinatorial map Y 0 Ñ X 0 . Picking a base vertex in Y 0 , this map represents the inclusion F 0 X K 0 Ñ Γ 0 . In fact, this map is an embedding. Lemma 6.5. The graph Y 0 is a regular covering of the rose with m`1 petals, and the map ι : Y 0 Ñ X 0 is an embedding.
Proof. Note that F 0 acts freely on T F 0 0 and transitively on the vertices. Therefore, the quotient F 0 zT F 0 0 is the rose with m`1 petals, and pF 0 XK 0 qzT F 0 0 is a regular covering with deck group R " F 0 {pF 0 XK 0 q. The fact that Y 0 Ñ X 0 is an embedding now follows from Bass-Serre theory, using the fact that the natural map We will identify Y 0 with its image in X 0 , and hence we feel free to (without loss of generality) choose˚as the base point for Y 0 . Fixing a base point allows us to identify the vertices of Y 0 with the elements of R.
There is a natural retraction σ : Γ Ñ Γ 0 obtained by setting σptq " 1. The preimage K " σ´1pK 0 q is a normal, free subgroup of finite index in Γ with Γ{K -P . Let T be the Bass-Serre tree of X . Then X " KzT is a finite graph which, as before, can be thought of as a regular, finitesheeted covering space of X with deck group P .
In fact, there is a simple, concrete description of X. Consider the graph of groups Z with a single vertex, labelled by the finite group Q, and a single edge, with trivial edge group. Its fundamental group is Q˚Z, which can be identified with Q˚xty, a subgroup of Γ. There is an obvious retraction Q˚xty Ñ Q obtained by sendingt Þ Ñ 1, and the preimage is precisely pQ˚xtyq X K, a normal, torsion-free subgroup of finite index, with quotient group Q. The corresponding covering graph of Z can be constructed as follows. Let Z be the graph with one vertex and edges te q | q P Qu. This admits a natural Q-action, where Q acts freely on the edges e q by left translation, and its fundamental group can be identified with pQ˚xtyq X K.
For each coset pQ P P {Q, let Z pQ be a copy of Z. Now X can be constructed as a quotient where " identifies the unique vertex of Z pQ with the vertex of X 0 that corresponds to pQ (i.e. p˚). The group P acts on X; the vertex p˚is stabilized by Q p´1 , which acts freely on the edges of Z pQ .
The inclusion Y 0 Ñ X 0 provides us with a nice geometric representative for the inclusion of F 0 X K 0 into K 0 . We next extend this to a nice geometric representative for F X K in K.
Let W Ñ Z be an immersion (with basepoints) representing xtyF 2 " xt,c 0 , . . . ,c m`1 y as a subgroup of the canonical free subgroup of Q˚xty. (Note that this immersion exists because F 2 Ď xxtyy.) Take copies W p " W , one for each p P P , equipped with maps W p Ñ Z pQ , chosen so that if pQ " p 1 Q then the following diagram commutes: where we note that pp´1p 1 q p´1 P Q p´1 , which acts on Z pQ as remarked above. Now let where " identifies the base vertex of W r with the vertex r˚P Y 0 . The coproduct of the embedding Y 0 ãÑ X 0 and the immersions W r Ñ Z rQ is an immersion Y Ñ X, since adjacent edges of Y and W r map to distinct edges of X. Taking˚P Y 0 as a base vertex for Y , the immersion Y Ñ X represents the inclusion of F X K into K.
Lemma 6.6. If w ‰ p G 1 then F " F 1˚F 2 . Proof. Because free groups are Hopfian, it suffices to prove that rk F " rk F 1`r k F 2 . This can be deduced from a computation of the Euler characteristic of Y , as follows.
If d " |R|, then we have On the other hand, the fundamental group of Y is K X F , which is of index d in F . Therefore χpY q " dp1´rk F q .
So rk F " 2m`4 which is equal to rk F 1`r k F 2 .
Malnormality of F . We shall establish the malnormality of F using the immersion Y Ñ X. For each left coset pR P P {R, let Y pR 0 be a copy of Y 0 . For each coset pR we choose a representative p i and equip Y pR 0 with the inclusion in X 0 that is the composition of p i with the inclusion Y 0 Ñ X 0 . Consider the coproduct of the maps described above. There is a free action of the group P on U 0 obtained by insisting that R acts on Y R 0 in the usual way and that p i takes the base vertex˚R P Y R 0 to the base vertex˚p i R P Y p i R 0 , and with this definition the map U 0 Ñ X 0 is P -equivariant. Thus, the vertices of U 0 are in bijection with the elements of P . The vertices of X 0 are in bijection with P {Q, and under this correspondence the map U 0 Ñ X 0 on the vertices can be seen as the natural map P Ñ P {Q. Remark 6.7. Consider the fibre product U 0ˆX 0 U 0 . Note that the map U 0 Ñ X 0 represents the family of subgroups tF γ´1 i 0 u in K 0 , where γ i ranges over a set of representatives for K 0 zΓ 0 {F 0 (which is identified with P {R). Therefore, by Lemmas 5.3, 5.4 and 6.4, the off-diagonal components of U 0ˆX 0 U 0 are simply connected.
We now consider the same construction for Y Ñ X. Let Y pR " Y and consider the disjoint union where, as before, the map Y pR Ñ X is the composition of a choice of map p : X Ñ X with the immersion Y Ñ X. Alternatively, we can construct U from U 0 by attaching copies of W as follows: where " identifies the vertex p˚R P U 0 with the base vertex of W p .
The map U Ñ X represents the family of subgroups tF where γ i ranges over a set of representatives for KzΓ{F " P {R; therefore, we will be able to prove the malnormality of F by considering the fibre product UˆX U .
We can obtain a clearer picture of the map U Ñ X by first gathering together those copies of W whose images adjoin the same vertex of X.
Then p i V is precisely the preimage of Z p i Q Ď X under the map U Ñ X.
Lemma 6.8. If N ą 6 then the off-diagonal components of VˆZ V are simply connected.
Proof. By Lemmas 5.3 and 5.4, this is equivalent to the claim that xty˚F 2 Ď xty˚xwy is malnormal in xty˚Q. This follows from Lemma 5.9, Example 5.7 and Lemma 5.2.
The fibre product UˆX U decomposes as and the diagonal components of UˆX U consist of precisely the diagonal components of the fibre products on the right hand side of the equation.
Proposition 6.9. If N ą 6 and w ‰ p G 1 then F is malnormal in Γ.
Proof. By Lemmas 5.3 and 5.4, it suffices to show that every offdiagonal component of the fibre product UˆX U is simply connected. Suppose therefore that δ is a geodesic loop in an off-diagonal component of U . The fibre product is equipped with two projections π 1 , π 2 : UˆX U Ñ U and a P -action. Let δ i " π i˝δ . Translating by an element of P , we may assume that δ 1 is contained in Y R . If Ď Y pR for some p P P , so δ is an essential off-diagonal loop in U 0ˆX 0 U 0 , which contradicts the fact that F 0 is malnormal in Γ. Therefore, δ 1 has a non-trivial subpath contained in W r for some r P R. Let α 1 be a maximal such subpath, let α be the subpath of δ with π 1˝α " α 1 and let α 2 " π 2˝α .
The endpoints of α 1 lie in W r X Y R 0 Ď Y ; this intersection is a point, and hence α 1 and is a loop in W r . Likewise, the endpoints of α 2 lie in W p X Y pR 0 , which is also a point, and so α 2 is a loop in W p . Since they have the same image in X it follows that p " rq for some q P Q. The loop r´1δ is then a non-trivial loop in an off-diagonal component of VˆZ V , which contradicts Lemma 6.8 (since N ą 6).
Step 4: the end of the proof of Theorem C. We take two copies of G 2 , distinguishing elements and subgroups of the second by primes, and define G w to be the quotient of G 2˚G 1 2 by the relations where the isomorphism F -F 1 sends b i to c 1 i and c i to b 1 i for 0 ď i ď m`1. The map η : G 2 Ñ Γ constructed above is injective on F , so we obtain an epimorphism The latter is an amalgam of virtually free groups along malnormal subgroups, and Wise [41,Theorem 1.3] proved that such amalgams are residually finite. Therefore p G w fl 1, as required.

Non-positively curved square complexes
In this section we strengthen Theorem A by proving that the existence of finite-index subgroups remains undecidable among the fundamental groups of compact, non-positively curved square complexes. More precisely, we will prove the geometric form of this result stated in the introduction as Theorem B.
The arguments in this section are topological in nature and the basic construction is close in spirit to earlier constructions by Kan and Thurston [20], Leary [25] and others: the key point in each case is that one replaces a disc in some standard topological construction by a more complicated space that is equally as inessential as a disc from one point of view but at the same time admits geometric or topological properties that are more desirable from the point of view of the application at hand. In our setting, the standard construction is that of the 2-complex canonically associated to a group presentation, the desirable property is non-positive curvature, and the appropriate notion of inessential is having a profinitely trivial fundamental group, i.e. the spaces that replace the disc should have no connected finite-sheeted coverings.

7.
1. An adaptation of the standard 2-complex. Let P " xa 1 , . . . , a n | r 1 , . . . , r m y be a finite presentation for a group G " |P|. The standard 2-complex KpPq with fundamental group G is defined as follows: it has a single vertex, a 1-cell for each generator -oriented and labelled a i -and a 2cell for each relator, attached along the edge-loop labelled by the word r j , which we may assume to be cyclically reduced. In what follows, it will be useful to have a name, Rpa 1 , . . . , a n q or, more briefly, Rpaq, for the 1-skeleton of KpPq.
Let X be a compact, non-positively curved square complex with S " π 1 X infinite but p S -1 (such as the examples of [12] or [42]) and fix some edge-loop γ : S 1 Ñ X p1q in the 1-skeleton that is a local geodesic in X, based at a vertex. Definition 7.1. Given a finite presentation P " xA | Ry, let SpPq be the space obtained by attaching m copies of X to Rpaq, with the j-th copy attached by a cylinder joining γ to the edge-loop in R labelled r j . More formally, writing ρ j : S 1 Ñ Rpaq for this last loop, we define " to be the equivalence relation on Rpa 1 , . . . , a n q ž`S 1ˆr 0, 1s˘ˆt1, . . . , mu ž Xˆt1, . . . , mu defined by @t P S 1 @j P t1, . . . , mu : ρ j ptq " pt, 0, jq and pt, 1, jq " pγptq, jq, and define SpPq to be the quotient space. Define G S :" π 1 SpPq.
(1) For any fixed choice of γ, the construction of SpPq from P is algorithmic.
(2) There is a continuous map ρ : SpPq Ñ KpPq that is the identity on Rpaq, sends each copy of X to a point in the interior of the corresponding 2-cell of KpPq, and maps the interior of each attaching cylinder homeomorphically to the interior of a punctured 2-cell. This map induces epimorphisms ρ˚: G S Ñ G and p ρ˚: Proof. It is enough to show that any homomorphism f from G S to a finite group factors through ρ˚. By construction, S has no finite quotients, so f pS j q " 1 where S j -S is the fundamental group of the copy of X in SpPq indexed by j P t1, . . . , mu.
Lemma 7.4. For any finite group presentation P, the space SpPq has the structure of a finite, non-positively curved square complex.
Proof. Let k be the length of γ. We scale Rpa 1 , . . . , a n q by a factor of k and subdivide each edge into k pieces of length 1. For j " 1, . . . , m we take a copy of X scaled by a factor of the word-length of r j , subdivided in the natural way so that it is a (unit) square complex. The attaching maps in the definition of SpPq are then length-preserving, so if the connecting cylinders are subdivided into squares in the obvious manner, SpPq becomes a non-positively curved square complex [10,Proposition II.11.6].
Together, these lemmas establish the following proposition, which reduces Theorem B to Theorem A. Proposition 7.5. There is an algorithm that takes as input a finite group presentation P for a group G and outputs a compact, non-positively curved square complex SpPq with fundamental group G S such that Remark 7.6. A simple combinatorial check will determine if a finite square complex satisfies the link condition, i.e. supports a metric of non-positive curvature. Thus this class of 2-complexes (equivalently, group presentations) is recursive.

Largeness.
A group is called large (or as large as a free group, in the original terminology of Pride [31]), if it has a subgroup of finite index that maps surjectively to a non-abelian free group. Largeness is related to the existence of finite quotients by the following elementary observation.
Lemma 7.7. A group G has a non-trivial finite quotient if and only if G˚G˚G is large.
Proof. If G maps onto a non-trivial finite group Q, then G˚G˚G maps onto Q˚Q˚Q. The kernel of any homomorphism Q˚Q˚Q Ñ Q that restricts to an isomorphism on each of the free factors is non-abelian and free of finite index, and a subgroup of finite index in G˚G˚G maps onto it. Conversely, if G can only map trivially to a finite group, then so can G˚G˚G, so it is not large.
Combining Lemma 7.7 with Theorem B, we see that largeness is undecidable, even among the fundamental groups of non-positively curved square complexes.
Corollary 7.8. There is a sequence of finite, non-positively curved square complexes X n such that: (1) for each n P N, X n has a proper connected finite-sheeted covering space if and only if π 1 X n is large; (2) the set of natural numbers tn P N | π 1 X n is largeu is recursively enumerable but not recursive.
In particular, there is no algorithm to determine whether or not the fundamental group of a finite, non-positively curved square complex is large.
7.3. Biautomatic groups. Fundamental groups of compact, non-positively curved square complexes are biautomatic [17] (see also [27]). There is an algorithm to determine if a biautomatic group is trivial, but Theorem B tells us that there is no algorithm to determine if it is profinitely trivial.
Corollary 7.9. There is no algorithm that, given a biautomatic group G, can determine whether or not G has a proper subgroup of finite index. Nor is there an algorithm that can determine whether or not G is large.

Profinite Rank
By definition, the profinite rank of a group G, denoted bydpGq, is the minimum number of elements needed to generate p G as a topological group.
8.1. A profinite Grushko lemma. We want to show that there is no algorithm that can determine the profinite rank of a hyperbolic group. For this we shall use the following analogue of Grushko's theorem; we make no claim that the constant 59 60 is sharp. Lemma 8.1. Let G be a group with p G fl 1. Thendp˚n i"1 Gq ě 59 60 n. Proof. If G maps onto a finite cyclic group Z{p, then L n :"˚n i"1 G (and hence its profinite completion) maps onto pZ{pq n , and therefore requires at least n generators.
Suppose, therefore, that G maps onto a non-trivial finite perfect group S. Let Q n :"˚n i"1 S and let π : Q n Ñ S be a homomorphism that restricts to an isomorphism on each free factor. The kernel ker π acts freely on the Bass-Serre tree for Q n (since all of the torsion of Q n is conjugate into one of the free factors) and hence ker π is a free group; its rank is r :" pn´1qp|S|´1q, as can be calculated using rational Euler characteristic.
Thus Q n , and hence L n , has a normal subgroup of index |S| that maps onto a free group of rank r. Let K n ă L n be this subgroup and fix an epimorphism K n Ñ pZ{2q r ": A. We can induce this homomorphism to a homomorphism L n Ñ A S. The image of K n under this map lies in the base of the wreath product, where it projects onto each A summand; thus it is an elementary 2-group of rank at least r.
By the Nielsen-Schreier formula, if the image of L n has rank δ then the image of K n , which has index |S|, has rank at most |S|pδ´1q`1. Thus pn´1qp|S|´1q ď |S|pδ´1q`1 , whenced But S is perfect and non-trivial, so |S| ě 60.

8.2.
Profinite rank of hyperbolic groups. We shall appeal to the following version of the Rips construction.
Theorem 8.2. There is an algorithm that takes as input a finite presentation for a group G and outputs a finite presentation for a residually finite, torsion-free, hyperbolic group Γ such that there exists a short exact sequence Proof. Rips showed how to construct such a short exact sequence with Γ satisfying the C 1 p1{6q small-cancellation condition [33]. Wise proved that such groups are fundamental groups of compact, non-positively curved cube complexes [38]. By Agol's theorem [3], it follows that Γ is virtually special and, in particular, residually finite.
We can now prove part (5) of Theorem D. Note that the examples constructed are residually finite.
There is a sequence of torsion-free, residually finite, hyperbolic groups Γ n with the property that: (1) for any n P N,dpΓ n q ă d 0 ôdpΓ n q " 2; and (2) the set of natural numbers tn P N |dpΓ n q ě d 0 u is recursively enumerable but not recursive. In particular, there is no algorithm that can decide whether or not the profinite completion of a torsion-free, residually finite, hyperbolic group can be generated (topologically) by a set of cardinality less than d 0 .
Proof. Let G n be a sequence of finitely presented groups such that the set of natural numbers tn P N | p G n fl 1u is recursively enumerable but not recursive. Let M ě 60 59 d 0 and, for each n, let G 1 n be a free product of M copies of G n . Then either p G 1 n -1 ordpG 1 n q ě d 0 by Lemma 8.1. Apply Theorem 8.2 to obtain short exact sequences 1 Ñ N n Ñ Γ n Ñ G 1 n Ñ 1 with each N n a 2-generator group.

Undecidable properties of hyperbolic groups
In this section we prove the remaining parts of Theorem D. We also prove that either every hyperbolic group is residually finite, or else there is no algorithm to decide which hyperbolic groups have a finite quotient. All of these things will be proved by combining our previous results with the following refinement of the Rips construction [33], which is due to Belagradek and Osin [6]. Theorem 9.1 (Belegradek-Osin, [6]). There is an algorithm that takes as input a finite presentation for a non-elementary hyperbolic group H and finite presentation for a group G and outputs a presentation for a hyperbolic group Γ that fits into a short exact sequence such that N is isomorphic to a quotient group of H. Furthermore, if H and G are torsion-free then Γ can also be taken to be torsion-free.
Proof. The only point that is not addressed directly by Belegradek and Osin is the fact that the construction can be made algorithmic, but it is tacitly implied in Corollary 3.8 of [6]. Indeed, since the class of hyperbolic groups is recursively enumerable [30], a naive search will eventually find a hyperbolic group Γ and a homomorphism H Ñ Γ whose image is normal with quotient isomorphic to G.
In the torsion-free case, one needs the well known fact that the class of torsion-free hyperbolic groups is also recursively enumerable (see, for instance, the proof of Theorem III.Γ.3.2 in [10]). (1) and (2) of Theorem D follow from the next theorem.

Largeness and virtual first Betti number. Parts
Theorem 9.2. There is a recursive sequence of finite presentations for torsion-free, hyperbolic groups Γ n such that: (1) for each n P N, vb 1 pΓ n q ą 0 ô vb 1 pΓ n q " 8 ô Γ n is large ; and (2) the set of natural numbers tn P N | Γ n is largeu is recursively enumerable but not recursive. In particular, for any 1 ď d ď 8, there is no algorithm that determines whether or not a given torsion-free hyperbolic group Γ has vb 1 pΓq ě d; likewise, there is no algorithm that determines whether or not a given torsion-free hyperbolic group is large.
Proof. Let G n be the sequence of fundamental groups of the square complexes produced by Corollary 7.8; note that as the fundamental groups of aspherical spaces, the G n are torsion-free. Let N n ă Γ n be the pair of groups obtained by applying the algorithm of Theorem 9.1 to G n , with H a fixed torsion-free, non-elementary hyperbolic group with Property (T); torsion-free uniform lattices in Sppn, 1q provide explicit examples.
We have the following chain of implications. vb 1 pG n q ą 0 ñ Γ n is large ñ vb 1 pΓ n q " 8 ñ vb 1 pΓ n q ą 0 The first implication follows from part (1) of Corollary 7.8, and the other implications are trivial.
To prove (1) and (2), it therefore suffices to show that vb 1 pΓ n q ą 0 implies that vb 1 pG n q ą 0. Suppose, therefore, that K ă Γ n is a subgroup of finite index that admits a surjection f : K Ñ Z. Property (T) is inherited by quotients and subgroups of finite index, so the abelianization of N n XK is finite. Therefore, f pN n XKq " 1 and so K{pKXN n q surjects Z. But K{pK X N n q has finite index in G n , so vb 1 pG n q ą 0 as required.
9.2. Linear representations. In this section we make use of known examples of torsion-free, non-elementary hyperbolic groups that admit no infinite linear representation to establish parts (3) and (4) of Theorem D. As M. Kapovich showed in [22,Theorem 8.1], the existence of such examples can be proved using the work of Corlette [15] and Gromov-Schoen [18] on (archimedean and non-archimedean) superrigidity for lattices in Sppn, 1q. ). There exists a torsion-free, non-elementary hyperbolic group H with the property that, for any field k, every finitedimensional representation of G over k has finite image.
Proof. The statement of this theorem is the same as [22,Theorem 8.1], with the additional stipulation that the group H is torsion-free. Following Kapovich, we start with a uniform lattice Γ in the isometry group of quaternionic hyperbolic space. By Selberg's Lemma, we may assume that Γ is torsion free. We then take H (which is G in Kapovich's notation) to be any infinite small-cancellation quotient of Γ. As Kapovich explains, the group H then has no infinite linear representations over any field.
In fact, for a suitable choice of small-cancellation quotient, any torsion in H is the image of torsion in Γ. (For instance, this follows from [29, Lemma 6.3], which even deals with the relatively hyperbolic setting.) Such a choice of H is therefore torsion-free.
Combining this with the Belegradek-Osin version of the Rips construction gives parts (3) and (4) of Theorem D.
Theorem 9.4. Fix any infinite field k. There is a sequence of torsionfree hyperbolic groups Γ n with the property that: (1) for any n P N, Γ n has a finite-dimensional representation over k with infinite image if and only if Γ n has a finite-dimensional representation over some field with infinite image; and (2) the set of n P N such that Γ n has a finite-dimensional representation over k is recursively enumerable but not recursive.
Proof. Let X n be the sequence of square complexes output by Corollary 7.8 and let G n " π 1 X n . Then, for any infinite field k, G n has a finitedimensional representation over k with infinite image if and only if G n is large; furthermore, the set of such natural numbers n is recursively enumerable but not recursive. Let H be the torsion-free, non-elementary hyperbolic group of Theorem 9.3, which has the property that every linear representation of H, over any field k, is finite. For each n, let Γ n be the torsion-free hyperbolic group that is the output of the algorithm of Theorem 9.1 with input G n and H.
The result now follows from the claim that, for any field k, Γ n has a finite-dimensional representation over k with infinite image if and only if G n does. Indeed, if G n has such a representation then Γ n clearly does. Conversely, suppose that f : Γ n Ñ GLpn, kq has infinite image. If N is the kernel of the map Γ n Ñ G n then, because N is a quotient of H, it follows that f pN q is finite. Because f pΓ n q is residually finite, there exists a proper subgroup K of finite index in f pΓ n q such that K X f pN q " 1. Then L " f´1pKq is a subgroup of finite index in Γ n with an infinite representation f | L over k, and f | L pL X N q " 1. Therefore, f | L factors through the restriction to L of the map Γ n Ñ G n . It follows that G n has a subgroup of finite index with an infinite representation over k, and this can be induced to a representation of G n . 9.3. Profinite undecidability in the hyperbolic case. We finish with the following conjecture.
Conjecture 9.5. There is no algorithm to determine whether or not a given hyperbolic group Γ has p Γ -1.
Since the triviality problem is solvable for hyperbolic groups, the above conjecture is false if every non-trivial hyperbolic group Γ has p Γ fl 1. In fact, I. Kapovich and Wise proved that p Γ fl 1 for every nontrivial (torsion-free) hyperbolic group Γ if and only if every (torsionfree) hyperbolic group is residually finite [21]. Conjecture 9.5 therefore implies the well known conjecture that there exists a hyperbolic group that is not residually finite [7,Question 1.15].
In fact, our final theorem shows that the two conjectures are equivalent (even in the torsion-free case).
Theorem 9.6. The following statements are equivalent.
(1) Every non-trivial (torsion-free) hyperbolic group has a proper subgroup of finite index. (2) There is an algorithm that, given a finite presentation of a (torsion-free) hyperbolic group, will determine whether or not the profinite completion of that group is trivial.
Proof. There is an algorithm that can decide if a given hyperbolic group is trivial, and if (1) holds then (2) reduces to checking if the given group is trivial. For the converse, suppose that there exists a nontrivial hyperbolic group H 0 with p H 0 " 1. Clearly H 0 is non-elementary. Let G n be a sequence of groups that witnesses the undecidability in Theorem B, let Γ n be the sequence of hyperbolic groups obtained by applying Theorem 9.1 to G n with H " H 0 , and note that p H " 1 implies p Γ np G n . Finally, it is a feature of Theorem 9.1 that if H 0 is torsion-free then so are the groups Γ n .