{'fraction_non_alphanumeric': 0.0542995444191344, 'fraction_numerical': 0.01714123006833713, 'mean_word_length': 3.4975028812908184, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Detecting large groups

Let G be a finitely presented group, and let p be a prime. Then G is 'large' (respectively, 'p-large') if some normal subgroup with finite index (respectively, index a power of p) admits a non-abelian free quotient. This paper provides a variety of new methods for detecting whether G is large or p-large. These relate to the group's profinite and pro-p completions, to its first L2-Betti number and to the existence of certain finite index subgroups with 'rapid descent'. The paper draws on new topological and geometric techniques, together with a result on error-correcting codes.


Introduction
A group is known as large if one of its finite index subgroups has a free nonabelian quotient. Large groups have many interesting properties, for example, super-exponential subgroup growth and infinite virtual first Betti number. It is therefore useful to be able to detect them in practice. In this paper, we will show how one may deduce that a finitely presented group is large using an array of different structures: its profinite and pro-p completions, its first L 2 -Betti number and the 'homology growth' of its finite index subgroups.
The detection of large groups was the aim of [4], where the author gave a characterisation of large finitely presented groups in terms of the existence of a sequence of finite index subgroups satisfying certain conditions. In this paper, we start by deducing the following consequence. In the above result, the term 'isomorphic' can be taken to mean 'isomorphic as groups', since any group isomorphism between profinite completionsĜ andK is automatically continuous. We do not require that the isomorphismĜ →K be induced by a homomorphism G → K.
One can also define a group to be p-large, for some prime p, if it contains a normal subgroup with index a power of p that has a free non-abelian quotient. In a similar spirit to Theorem 1.1, we will prove the following. Theorem 1.2. Let G and K be finitely presented (discrete) groups that have isomorphic pro-p completions for some prime p. Then G is p-large if and only if K is p-large.
A sample application of Theorem 1.2 is to weakly parafree groups, which are defined in terms of the lower central series, as follows. Denote the ith term of the lower central series of a group by γ i ( ). A group is weakly parafree if there is some non-trivial free group F with the 'same' lower central series as G. This means that there is an isomorphism F/γ i (F ) → G/γ i (G), for each positive integer i, and that these isomorphisms are compatible with each other in the obvious way. A group is known as parafree if it is weakly parafree and residually nilpotent. Many interesting examples of parafree groups are given in [1] and their properties are investigated in [2]. A consequence of Theorem 1.2 is the following result. Theorem 1.3. Let G be a finitely presented, weakly parafree group with b 1 (G) > 1. Then G is large.
Here, b 1 (G) denotes the first Betti number of G. This has the following corollary. There are also applications of Theorem 1.2 to low-dimensional topology, including the following. Recall that two closed 3-manifolds M 1 and M 2 are topologically Z p -cobordant if there is a topological 4-manifold X such that ∂X = M 1 ∪ M 2 , and such that the inclusion of each M i into X induces isomorphisms of homology groups with mod p coefficients. Thus, Theorem 1.5 represents an unexpected link between two very different areas of low-dimensional topology: the theory of finite covers of 3-manifolds, and 4-dimensional topology. We will investigate this connection further in a forthcoming paper [9].
One of the goals of this paper is also to relate largeness to L 2 -Betti numbers.
The first L 2 -Betti number is defined in [13] for any finitely presented group G and is denoted here by b (2) 1 (G). Theorem 1.6. Let G be a finitely presented (discrete) group that is virtually residually p-finite for some prime p, and such that b This gives new examples of large groups. By applying results of Shalom from [15], we obtain the following. Corollary 1.7. Let G be a finitely presented, non-amenable, discrete subgroup of SO(n, 1) or SU(n, 1), with n ≥ 2 and with critical exponent strictly less than 2.
Then G is large.
This is a consequence of Theorem 1.6 because Shalom showed that such a group G has b (2) 1 (G) > 0 (Theorem 1.5 in [15]). And since it is finitely generated and linear over a field of characteristic zero, it is virtually residually p-finite, for all but finitely many primes p (Proposition 9 in Window 7 of [11] [3]) to Lie groups other than SO(3, 1). Theorem 1.8. Let G be a finitely generated, discrete subgroup of SO(3, 1) that is neither virtually abelian nor cocompact. Then G is large. Theorem 1.6 is proved using two results. The first is due to Lück (Theorem 0.1 of [12]). It relates b (2) 1 (G) to the ordinary first Betti number b 1 (G i ) of finite index normal subgroups G i . Theorem 1.9. (Lück [12]) Let G be a finitely presented group, and let {G i } be a nested sequence of finite index normal subgroups such that G i = 1. Then exists and equals b This theorem is concerned with the growth rate of b 1 (G i ) for finite index subgroups G i . Recent work of the author has instead focused on the growth rate of homology with coefficients modulo some prime. Let us fix some terminology.
Let F p be the field of order a prime p. For a group G, let d p (G) be the dimension of the homology group H 1 (G; F p ).
The second result forming the basis for Theorem 1.6 is the following, which is a consequence of the results of the author in [4]. Theorem 1.10. Let G be a finitely presented group with a surjective homomorphism φ: G → Z. Let G i = φ −1 (iZ), and let p be a prime. Then 2. this limit is positive if and only if d p (G i ) is unbounded; 3. if the limit is positive, then G is large.
Thus, fast growth of d p (G i ) as a function of the index [G : G i ] appears to be a strong and useful property. We say that a nested sequence of finite index subgroups strictly positive. A notable situation where this arises is the following, which was the main result of [5].
Theorem 1.11. Let G be a lattice in PSL(2, C) satisfying one of the following: 1. G contains a non-trivial torsion element, or 2. G is arithmetic.
Then G contains a strictly nested sequence of finite index subgroups {G i } with linear growth of mod p homology, for some prime p.
It seems very likely that these lattices are large. But it remains unclear whether the conclusion of the theorem is strong enough to imply this. However, the following theorem provides an affirmative answer when {G i } is the derived p-series for G. Recall that this is a sequence of finite index subgroups {D Theorem 1.12. Let G be a finitely presented group, and let p be a prime.
Suppose that the derived p-series for G has linear growth of mod p homology.
This has implications for other series of finite index subgroups of G, for example the lower central p-series, which is defined as follows. The first term The remaining terms are defined recursively, setting γ Corollary 1.13. Let G be a finitely presented group, and let p be a prime.
Suppose that the lower central p-series for G has linear growth of mod p homology.
Then G is p-large.
The reason that 1.12 implies 1.13 is as follows. Each term D j (G) for all sufficiently large j. This is because the lower central p-series of the finite p-group G/D (p) i (G) terminates in the identity element, since this is true for any finite p-group. Moreover, we have the inequality . This is an application of Lemma 3.3 in this paper, using the fact that γ i (G) and has index a power of p. Thus, the assumption that the lower central p-series of G has linear growth of mod p homology implies that the same is true of the derived p-series. Theorem 1.12 then implies that G is p-large, as required. It is clear from this proof that versions of Corollary 1.13 apply to other series of subgroups, for example, the dimension subgroups modulo Z p . Theorem 1.12 is a consequence of a more general result, which we now describe. An abelian p-series for a group G is a sequence of finite index subgroups Thus, we say that an abelian p-series In Sections 4-7, we will prove the following theorems.
Theorem 1.14. Let G be a finitely presented group, and let p be a prime. Then the following are equivalent: 1. G is large; 2. some finite index subgroup of G has an abelian p-series with rapid descent. Theorem 1.15. Let G be a finitely presented group, and let p be a prime. Then the following are equivalent: 1. G is p-large; 2. G has an abelian p-series with rapid descent.
These theorems represent a significant improvement upon the results in [4], and can be viewed as the strongest theorems in this paper. They are interesting for two reasons. Firstly, (2) in each theorem does not obviously imply that G has a finite index subgroup with positive b 1 , although this is of course a consequence of the theorems. Secondly, the proof of these results involves some genuinely new techniques. As in [4] and [6], topological and geometric methods play a central role. But in this paper, some basic ideas from the theory of error-correcting codes are also used. In particular, we apply a generalisation of the so-called 'Plotkin bound' [14].
Acknowledgement. I would like to thank Yehuda Shalom for pointing out Corollary 1.7 to me.

Profinite completions and weakly parafree groups
Our goal in this section is to prove Theorems 1.1 -1.5. Our starting point is the following result, which is one of the main theorems in [4].
Theorem 2.1. Let G be a finitely presented group. Then the following are equivalent: 1. G is large; 2. there exists a sequence G 1 ≥ G 2 ≥ . . . of finite index subgroups of G, each normal in G 1 , such that Here, d( ) denotes the rank of a group, which is the minimal size of a generating set. 1. There is an induced bijection (also denoted φ) between the set of finite index subgroups of G and the set of finite index subgroups of K.

If
4. If G i ⊂ G j are finite index subgroups of G, and G i is normal in G, then the We can now prove the following. LetG i be the intersection of the conjugates of G i . Proposition 2.3 (1) gives finite index subgroups φ(G i ) and φ(G i ) of K, which we denote by K i andK i respectively. By 2.3 (2),K i is normal in K. By 2.3 (3),K i is contained in K i . By

(2) and (4), there is an isomorphism
and where the following hold: index a power of p, admits a surjective homomorphism φ onto a non-abelian free group F . Define the following subgroups of F recursively. Set F 1 = F , and let Then it is trivial to check that the conditions of (2) hold.
(2) ⇒ (1): By Theorem 2.1 and Remark 2.2, some G i admits a surjective homomorphism φ onto a non-abelian free group F . By assumption, G i is subnormal in G and has index a power of p. SetG i to be the intersection of the conjugates of G i . ThenG i is normal in G and also has index a power of p. The restriction of φ toG i is a surjective homomorphism onto a finite index subgroup of F , which is therefore free non-abelian. Thus, G is p-large.
Theorem 1.2. Let G and K be finitely presented (discrete) groups that have isomorphic pro-p completions for some prime p. Then G is p-large if and only if Proof. This is very similar to the proof of Theorem 1.1. Suppose that G is p-large.
It therefore has a sequence of subgroups G i where the conclusions of Theorem 2.5 hold. Using Remark 2.4, K also has such a sequence of subgroups. Thus, by Our aim now is to prove Theorem 1.3.
As stated in the Introduction, this has the following corollary.
Corollary 1.4. Any finitely presented, parafree group is either large or infinite cyclic.
Proof. Any parafree group G with b 1 (G) ≤ 1 is infinite cyclic. Theorem 1.3 is a consequence of a stronger result concerning weakly p-parafree groups, which we now define. A group G is weakly p-parafree, for some prime p, if there is some non-trivial free group F such that G/γ i ( ) denotes the lower central p-series of a group. Proposition 2.6. A weakly parafree group is weakly p-parafree for each prime p.
Proof. By assumption, there is an isomorphism between G/γ i (G) and F/γ i (F ) for some non-trivial free group F . This induces an isomorphism between the lower central p-series of G/γ i (G) and F/γ i (F ). Hence, . Similarly, the righthand side is isomorphic to F/γ (p) i (F ). Thus, we obtain an isomorphism between G/γ (p) i (G) and F/γ Note that, when defining the weakly p-parafree group G, we do not make the assumption that the isomorphisms G/γ This means that the following diagram commutes, for each i ≥ 2: Here, the horizontal arrows are the given isomorphisms and the vertical maps are the obvious quotient homomorphisms. However, we can assume this, with no loss, as the following lemma implies.
Lemma 2.7. Let G and K be finitely generated groups. Suppose that, for each . Then there is a collection of such isomorphisms that are compatible.
Proof. For each j ≤ i, θ i restricts to an isomorphism between γ occurs infinitely often. Take this to be the given isomorphism , and only consider those θ i for which θ i,2 = φ 2 . Among these, some θ i,3 occurs infinitely often. Define this to be φ 3 , and so on. Then the φ i form the required compatible collection of isomorphisms.
The above lemma is elementary and well-known, as is the following result.
They are included for the sake of completeness.
Lemma 2.8. Let G and K be finitely generated groups, and let p be a prime.
Then the following are equivalent: 1. the pro-p completions of G and K are isomorphic; i (G). The claim follows immediately.
(2) ⇒ (1): The pro-p completionĜ (p) can be expressed as the inverse limit of . This is because the kernel of any homomorphism of G onto a finite p-group contains γ According to Lemma 2.7, these isomorphisms can be chosen compatibly. This implies there is an isomorphism between the inverse limits: Thus,Ĝ (p) andK (p) are isomorphic.
Setting K to be a free group in Lemma 2.8 gives the following characterisation of weakly p-parafree groups in terms of pro-p completions.
Corollary 2.9. Let G be a finitely generated (discrete) group and let p be a prime.
Then G is weakly p-parafree if and only if its pro-p completion is isomorphic to the pro-p completion of a non-trivial free group.
Thus, Theorem 1.3 is a consequence of the following.
Theorem 2.10. Let G be a finitely presented group that is weakly p-parafree for Proof. The assumption that G is weakly p-parafree implies that the pro-p completion of G is isomorphic to the pro-p completion of a free group F , by Corollary 2.9. Since d p (G) > 1, F is a non-abelian free group. In particular, it is p-large.
Thus, by Theorem 1.2, G is p-large.
We close this section with a topological application of Theorem 1.2. Theorem 1.5. If two closed 3-manifolds M 1 and M 2 are topologically Z pcobordant, for some prime p, then This is an immediate consequence of Theorem 1.2 and the following result.
Theorem 2.11. If two closed 3-manifolds are topologically Z p -cobordant, then the pro-p completions of their fundamental groups are isomorphic.
We will prove this theorem in a forthcoming paper [9], where we will develop further connections between 3-manifolds, 4-manifolds, and the pro-p completions of their fundamental groups.

Homology growth in cyclic covers
The goal of this section is to prove the following result and then Theorem 1.6. Theorem 1.10. Let G be a finitely presented group with a surjective homomor- 3. if the limit is positive, then G is large.
We will need the following lemma.
for any i, j ∈ N. Then Claim. Suppose that f (m) > 2k, for some positive m ∈ N. Then lim inf i f (i)/i > 0.
The claim now follows by noting that if i = nm + r, for 0 ≤ r < m, then Proof of Theorem 1.10. We claim that there is a non-negative integer k such that, for all i, j ≥ 1, This and Lemma 3.1 will then imply (1) and (2).
Let K be a finite connected 2-complex with fundamental group G. We may find a map F : K → S 1 so that F * : π 1 (K) → π 1 (S 1 ) is φ: G → Z. Let b be a point in S 1 . Then, after a small homotopy, we may assume that F −1 (b) is a finite graph Γ, that a regular neighbourhood of Γ is a copy of Γ × I and that the restriction of F to this neighbourhood is projection onto the I factor, followed by inclusion of I into S 1 . Let K be the result of cutting K along Γ. Let K i be the i-fold cover of K corresponding to G i . Then K i can be obtained from i copies of K glued together in a circular fashion. Cut K i along one of the copies of Γ in K i , and let K i be the result. The Mayer-Vietoris sequence (applied to the decomposition of K i into K i and Γ × I) gives the following inequalities: Similarly, since the disjoint union of K i and K j is obtained by cutting K i+j along a copy of Γ, we have Since d p (K i ) = d p (G i ), the claim now follows, letting k = 2d p (Γ) + 2|Γ|.
Conclusion (3) is a consequence of the following result (Theorem 1.2 of [4]), Theorem 3.2. Let G be a finitely presented group and suppose that, for each Then, K i admits a surjective homomorphism onto a non-abelian free group, for all sufficiently large i.
To prove Theorem 1.6, we need one more fact, which is well known. It appears as Proposition 3.7 in [5], for example. Lemma 3.3. Let G be a finitely generated group and let K be a normal subgroup with index a power of a prime p. Then We can now prove Theorem 1.6.
Theorem 1.6. Let G be a finitely presented (discrete) group, that is virtually residually p-finite, for some prime p, and such that b Proof. Since G is virtually residually p-finite, it has a finite index normal subgroup G 1 that is residually p-finite. Thus, G 1 contains a nested sequence of normal subgroups G i , each with index a power of p, such that i G i = 1. By the multi- 1 (G 1 ), which is positive. Hence, by relabelling the G i , we may assume that b 1 (G 1 ) > 0.
Let φ: G 1 → Z be a surjective homomorphism, and let K i = φ −1 (p i Z).
We claim that lim inf i d p (K i )/[G : K i ] is positive. Consider the subgroups G i ∩ K i . Each is a finite index normal subgroup of G 1 and their intersection is the identity. Hence, by Theorem 1.9, and so has order a power of p. Hence, by Lemma 3.3, Therefore, lim inf i d p (K i )/[G : K i ] is positive, as claimed.
In particular, d p (K i ) is unbounded. Thus, by Theorem 1.10, G is large.

Cocycle size and Property (τ )
Most of the remainder of the paper is devoted to the proof of Theorems 1.14 and 1.15.
Theorem 1.14. Let G be a finitely presented group and let p be a prime. Then the following are equivalent: 1. G is large; 2. some finite index subgroup of G has an abelian p-series with rapid descent.
Theorem 1.15. Let G be a finitely presented group, and let p be a prime. Then the following are equivalent: 1. G is p-large; 2. G has an abelian p-series with rapid descent.
The difficult direction in each of these theorems is (2) ⇒ (1). For this, one needs a method for proving that a finitely presented group is large or p-large.
Various techniques have been developed with this aim. The one we will use deals with the 'relative size' of cocycles on 2-complexes.
Let K be a connected finite 2-complex with fundamental group G. Let K i be the covering space corresponding to a finite index subgroup G i . The key to our approach is to consider cellular 1-cocycles on K i representing non-trivial elements of H 1 (K i ; F p ).
For a cellular 1-dimensional cocycle c on K i , let its support supp(c) be those 1-cells with non-zero evaluation under c. For an element α ∈ H 1 (K i ; F p ), consider the following quantity, which was defined in [6]. The relative size of α is relsize(α) = min{|supp(c)| : c is a cellular cocycle representing α} Number of 1-cells of K i .
The following result was proved in [6] and is central to our approach. growth of mod p homology for some prime p. Then one of the following must hold: (i) π 1 (K i ) is p-large for infinitely many i, or (ii) there is some ǫ > 0 such that the relative size of any non-trivial class in This is a slightly modified version of Theorem 6.1 of [6]. In that result, it is not explicitly stated that π 1 (K i ) is p-large for infinitely many i, merely that π 1 (K) is large. But the proof does indeed give a normal subgroup of π 1 (K i ) with index a power of p that has a free non-abelian quotient.
In this section, we will relate the relative size of cocycles to Property (τ ).
While not directly needed in the remainder of the paper, this is a potentially important link.
We now recall the definition of Property (τ ). Let G be a group with a finite generating set S. Let {G i } be a collection of finite index subgroups of G. Let X i = X(G/G i ; S) be the Schreier coset graph of G/G i with respect to the generating set S.
Here, V (X i ) denotes the vertex set of X i , and for a subset A of V (X i ), ∂A denotes the set of edges with one endpoint in A and one not in A. To appreciate the significance of this conjecture, note the following theorem, which appears as Corollary 7.4 in [8]. Theorem.
[8] The Lubotzky-Sarnak conjecture and the Geometrisation Conjecture together imply that any arithmetic lattice in PSL(2, C) is large.
Thus, it is important to develop new methods for showing that a group does not have Property (τ ). The following result, which is the main theorem in this section, may be a useful tool. In the proof of this theorem, we will need the following construction, which will also be important later in the paper. Let K be a finite connected 2-complex with some 0-cell as a basepoint b. Let c be a cocycle on K representing a nontrivial element of H 1 (K; F p ) and let (K,b) be a (based) covering space of (K, b).
Since we are assuming that the relative size of α i tends to zero, and since the other terms on the right-hand side of the above formula depend only on K, we deduce that h(X i ) → 0. Hence, G does not have Property (τ ) with respect to {G i }.

Cocycles in covering spaces
Our aim over the next few chapters is to prove (2) ⇒ (1) of Theorems 1.14 and 1.15, and thereby establish that the group G in these theorems is large or p-large as appropriate. The proof will be topological, and so we consider a finite connected 2-complex K with fundamental group G. We are assuming that G has a finite index subgroup G 1 with a rapidly descending p-series G i . (In the proof of Theorem 1.15, take G 1 to be G.) Let K i be the corresponding covering spaces of K. Theorem 4.1 gives a criterion for establishing that G 1 is p-large, in terms of the existence of 1-cocycles on K i with relative size tending to zero. We therefore, in this section, investigate how 1-cocycles on a 2-complex can be used to construct 1-cocycles in covering spaces (with potentially smaller relative size). If U is a set of 1-cocycles on a cell complex K, we define its support supp(U ) to be the union of the supports of the cocycles in U . Our main result is the following.
Theorem 5.1. Let K be a finite connected 2-complex with r 2-cells. Let U be a collection of cocycles on K that represent linearly independent elements of H 1 (K; F p ). Let u = |U |. Let q:K → K be a finite regular cover such that π 1 (K)/π 1 (K) is an elementary abelian p-group with rank n. Then there is a col-lectionŨ of cocycles onK representing linearly independent elements of H 1 (K; F p ) such that The point behind Theorem 5.1 is that it provides not just a lower bound on the dimension of H 1 (K; F p ) but also gives information about certain cocycles oñ K representing this cohomology.
We now embark on the proof of Theorem 5.1. Consider the following subspaces of H 1 (K; F p ): 1. the space spanned by the elements of U ; 2. the classes that have trivial evaluation on all elements of π 1 (K).
Let V 1 and V 2 be these two subspaces. Then the dimensions of V 1 and V 2 are u and n respectively.
Pick a complementary subspace for V 1 ∩ V 2 in V 2 , and let C be a set of cocycles on K that represents a basis for this subspace. Note that |C| ≥ n − u.
Note also that, by construction, C ∪U forms a linearly independent set of elements For each c 1 ∈ U and c 2 ∈ C, we will show how to construct a cochain oñ K, which we denote c 1 ∧ c 2 . These cochains will play a vital role in the proof of We now define c 1 ∧ c 2 . Since the edges ofK are oriented, it suffices to assign an integer (c 1 ∧ c 2 )(e) modulo p to each edge e. We define this to be where the product is multiplication in F p .
It may be helpful to consider the case where K is the wedge of 3 circles labelled x, y and z, where p = 2 and where π 1 (K) is the second term in the derived 2series for π 1 (K). Let c 1 and c 2 be the cochains supported on the x-labelled and y-labelled edges of K, respectively. Then the following is a diagram ofK, and the edges in the support of c 1 ∧ c 2 are shown in bold.
x z y b Figure 2.
We denote by U ∧ C the space of cochains onK spanned by elements where c 1 ∈ U and c 2 ∈ C. Let Z 1 (K) denote the space of 1-cocycles onK with mod p coefficients. We will establish the following.
Claim 5.2. The dimension of U ∧ C is |U | |C|, which is at least u(n − u).
Claim 5.3. The subspace Z 1 (K) ∩ U ∧ C of cocycles in U ∧ C has codimension at most r (the number of 2-cells of K).
Claim 5.4. The map from Z 1 (K) ∩ U ∧ C into H 1 (K; F p ) is an injection.
Thus, settingŨ to be a basis for Z 1 (K) ∩ U ∧ C will establish Theorem 5.1.
where equality is in F p .
Proof. Each letter in the word g corresponds to an edge e, say, in the first part of the loop [g, h]. The inverse of this letter appears in g −1 , where the loop runs over the edge e ′ . Between the vertices i(e) and i(e ′ ) is a word w conjugate to h. We claim that c 2 (i(e ′ )) − c 2 (i(e)) = c 2 (h). Pick a path from the basepointb ofK to i(e). Then c 2 (i(e)) is the evaluation under c 2 of the projection of this path to K. If we extend this path using the word w, we obtain a path fromb to i(e ′ ). Thus, the difference between c 2 (i(e ′ )) and c 2 (i(e)) is the evaluation of c 2 on the projection of w. The parts of g and g −1 in w project to the same edges in K, but with reverse orientations. Hence, c 2 (i(e ′ )) − c 2 (i(e)) equals c 2 (h), as required. Therefore, the evaluation of the loop [g, h] along the edges in g and g −1 Similarly, along the edges in h and h −1 , it is c 1 (h)c 2 (g).
Let C 1 (K) and B 1 (K) be the space of 1-cochains onK, with mod p coefficients, and the subspace of coboundaries.
Proof. Since U ∪ C forms a linearly independent set of classes in H 1 (K; F p ), there are loops ℓ i in K, based at the basepoint of K, where i ∈ U ∪ C, such that, for all Let i ∈ U and j ∈ C. Then, by Lemma 5.5, for any c 1 ∈ U and c 2 ∈ C, Since every element of B 1 (K) has trivial evaluation on any loop inK, we deduce the lemma.
Lemma 5.6 implies Claim 5.2. It also implies that the restriction of the Thus, it is an injection on any subspace of U ∧ C . This gives Claim 5.4. We now verify Claim 5.3.
Lemma 5.7. Let ℓ and ℓ ′ be the boundary loops of two 2-cells ofK that differ by a covering transformation ofK. Then, Proof. Let g be a path in the 1-skeleton ofK from the basepoint of ℓ to the basepoint of ℓ ′ . Thus, the loop gℓg −1 runs from the basepoint of ℓ to the basepoint of ℓ ′ , then goes around ℓ ′ and then returns to the basepoint of ℓ. Since g and ℓ project to loops in K based at the same point, Lemma 5.5 gives that This is zero because ℓ is the boundary of a 2-cell and so has zero evaluation under the cocycles c 1 and c 2 . So, . This is proved as follows. Pick a basis for V 1 + V 2 so that it contains a basis for V 1 ∩ V 2 , a basis for V 1 and a basis for Remark 5.9. The cochains c 1 ∧ c 2 we have considered in this section are, in fact, special cases of a much more general construction. In [7], a more general class of cochain was used to provide new lower bounds on the homology growth and subgroup growth of certain groups. These more general cochains had a certain integer ℓ, known as their level, assigned to them. The cochains c 1 ∧ c 2 are those with level one.

The subspace reduction theorem
Let E be a finite set, and let F E p be the vector space over F p consisting of functions E → F p . The support of an element φ of F E p is The support of a subspace W of F E p is The main example we will consider is where E is the set of 1-cells in a finite 2-complex K (with some given orientations). Then F E p is just C 1 (K), the space of 1-cochains on K. Recall that our goal is to find cocycles representing non-trivial elements of H 1 (K; F p ) and with small relative size. The following result, which is the main theorem of this chapter, will be the tool we use. Theorem 6.1. Let V be a subspace of F E p with dimension v, and let w be a positive integer strictly less v. Then, V contains a subspace W with dimension w such that In our case, V will be a subspace of C 1 (K) spanned by v cocycles, representing linearly independent elements of H 1 (K; F p ). We will use Theorem 6.1 to pass to a set of w cocycles (where w is a fixed integer less than v) spanning a subspace W with support which is smaller than the support of V by a definite factor, independent of v.
We now embark on the proof of Theorem 6.1. The following lemma gives a formula relating the support of a subspace to the support of each of its elements.
Proof. Focus on an element e ∈ E in the support of W . Then, there is a ψ in W such that ψ(e) = 0. Decompose W as a direct sum ψ ⊕ W ′ . Then we may express W as a union of translates of W ′ , as follows: Now, for any element φ ′ ∈ W ′ , iψ(e) + φ ′ (e) = 0 for exactly one value of i between 0 and p−1. Denote the indicator function of an element φ in F E p by I φ : E → {0, 1}. This is defined as follows: Then, Summing this over all e in the support of W gives φ∈W |supp(φ)| = (p − 1)p dim(W )−1 |supp(W )|, as required.
Theorem 6.3. Let V be a non-zero subspace of F E p with dimension v. Then there is a codimension one subspace W of V such that Proof. Note that the theorem holds trivially if v = 1. We therefore assume v ≥ 2.
There are (p v − 1)/(p − 1) codimension one subspaces W of V . Summing the formula of Lemma 6.2 over each of these gives: It is instructive to consider the case w = 1 in Theorem 6.1. This states that in any subspace V of F E p with dimension v > 1, there is an element with at most non-zero co-ordinates. This is a theorem in the theory of error-correcting codes, known as the 'Plotkin bound' [14]. For, a linear code is just a subspace of F E p , and the Hamming distance of such a code is the minimal number of non-zero co-ordinates in any non-zero element of the subspace. Thus, Theorem 6.1 can be viewed as a generalisation of the Plotkin bound, giving information not just about elements of V but whole subspaces. It is probably well-known to experts on error-correcting codes.
The proof is as follows. Suppose that φ: G 1 → F is a surjective homomorphism from a finite index subgroup of G onto a non-abelian free group F . For the proof of Theorem 1.15, assume in addition that G 1 is normal in G and has index a power of p. Let {F i } be the derived p-series of F , and let G i = φ −1 (F i ). Since {F i } is an abelian p-series for F with rapid descent, {G i } is therefore an abelian p-series with rapid descent, as required.
So, suppose that some finite index subgroup G 1 of G has an abelian p-series {G i } with rapid descent. In the proof of 1.15, take G 1 to be G. We will show that G 1 is p-large, which will establish the theorems. Since d p (G i /G i+1 ) ≤ d p (G i ), the rapid descent of {G i } implies that it has linear growth of mod p homology.
Let K be a connected finite 2-complex with fundamental group G. Let K i be the finite-sheeted covering space corresponding to the subgroup G i . Recall from Section 4 the definition of the relative size of an element of H 1 (K i ; F p ), and the following result.
Theorem 4.1. Let K be a finite connected 2-complex, and let {K i → K} be a collection of finite-sheeted covering spaces. Suppose that {π 1 (K i )} has linear growth of mod p homology for some prime p. Then one of the following must hold: (i) π 1 (K i ) is p-large for infinitely many i, or (ii) there is some ǫ > 0 such that the relative size of any non-trivial class in H 1 (K i ; F p ) is at least ǫ, for all i.
Thus, our plan is to prove that (ii) of Theorem 5.1 does not hold, and therefore deduce that G 1 is p-large. We will keep track of a set U i of cellular 1-dimensional cocycles on K i that represent linearly independent elements of H 1 (K i ; F p ). The cardinality |U i | will be some fixed positive integer u independent of i. (The precise size of u will depend on data from the group G and the series {G i }.) Our aim is to ensure that |supp(U i )| Number of 1-cells of K i → 0.
( †) In particular, the relative size of any element of U i tends to zero, which means that (ii) does not hold.
We establish ( †) using the following method. Let q i : K i+1 → K i be the covering map. We will find a set of cocycles U + i+1 on K i+1 representing linearly independent elements of H 1 (K i+1 ; F p ), with the following properties: Note that the inequality in (II) is strict.
Let E denote the set of 1-cells of K i+1 with given orientation. Then C 1 (K i+1 ) is isomorphic to F E p , the vector space of functions E → F p . Let V be the subspace of C 1 (K i+1 ) spanned by U + i+1 , and let w = u. We apply Theorem 6.1 to V .
Theorem 6.1. Let V be a subspace of F E p with dimension v, and let w be a positive integer strictly less v. Then, V contains a subspace W with dimension w such that Let U i+1 be a basis for the subspace W given by Theorem 6.1. Note that the factor (p w+1 − p)/(p w+1 − 1) is strictly less than 1, and is dependent only on the fixed integers u and p. Now, |q −1 i (supp(U i ))| is obtained from |supp(U i )| by scaling by the degree of the cover q i . The same relation holds between the number of 1-cells in K i+1 and the number of 1-cells in K i . Thus, ( †) follows.
The key, then, is to construct the cocycles U + i+1 with properties (I) and (II). For this, we use Theorem 5.1 (setting K = K i , U = U i andK = K i+1 ) Theorem 5.1. Let K be a finite connected 2-complex with r 2-cells. Let U be a collection of cocycles on K that represent linearly independent elements of H 1 (K; F p ). Let u = |U |. Let q:K → K be a finite regular cover such that π 1 (K)/π 1 (K) is an elementary abelian p-group with rank n. Then there is a collectionŨ of cocycles onK representing linearly independent elements of H 1 (K; F p ) such that 1. supp(Ũ ) ⊂ q −1 (supp(U )); 2. |Ũ | ≥ (n − u)u − r.
We define U + i+1 to be the setŨ provided by this theorem. Condition (1) of the theorem is just (I) above. We need to ensure that Condition (II) holds. Thus, we require (n − u)u − r > u.
We will ensure that this holds by using the hypothesis that G i has rapid descent and by a suitable choice of u.
Let X|R be a finite presentation for G. Let λ be Since {G i } is rapidly descending, λ is positive. Let u be 4|R| λ , which is a positive integer. Now pick a sufficiently large integer j, such that, for This proves (2) ⇒ (1) of Theorems 1.14 and 1.15.