J Örg Br

Olivier Robert

ON ARTIN'S CONJECTURE: LINEAR SLICES OF DIAGONAL HYPERSURFACES

Keywords: Artin's conjecture, forms of higher degree MSC(2010):11E76, 11E95 (primary), 11D79 (secondary)

Artin's conjecture is established for all forms that can be realised as a diagonal form on an hyperplane.

Introduction

A famous conjecture of Emil Artin asserts that forms of degree k with integer coefficients in s variables have non-trivial zeros in all p-adic fields provided only that s > k 2 . Although the conjecture was disproved a long time ago (Terjanian [START_REF] Terjanian | Un contre-exemple à une conjecture d'Artin[END_REF][START_REF] Terjanian | Formes p-adiques anisotropes[END_REF]) and desperately fails in some sense, it is also not too far from the truth in certain other interpretations: given a degree k, there is a number p 0 (k) with the property that whenever the prime p exceeds p 0 (k) then all forms of degree k with integer coefficients in more than k 2 variables have non-trivial zeros in Q p (e.g. Ax and Kochen [START_REF] Ax | Diophantine problems over local fields[END_REF]), while for each prime p there are infinitely many degrees k and forms of this degree k in more than exp √ k variables that have no solution in Q p other than the trivial one (Arkhipov and Karatsuba [START_REF] Arkhipov | Local representation of zero by a form[END_REF], Brownawell [START_REF] Brownawell | On p-adic zeros of forms[END_REF], Lewis and Montgomery [START_REF] Lewis | On zeros of p-adic forms[END_REF], Wooley [START_REF] Wooley | Diophantine problems in many variables: the role of additive number theory[END_REF]).

At the time the conjecture was put forward, ca. 1930, it was known to hold when k = 1 (trivial) and k = 2 (Meyer [START_REF] Meyer | Mathematische Mittheilungen[END_REF]). Since then, only the case k = 3 was settled affirmatively (Demyanov [START_REF] Dem'yanov | On cubic forms in discretely normed fields[END_REF], Lewis [START_REF] Lewis | Cubic homogeneous polynomials over p-adic number fields[END_REF], Davenport [START_REF] Davenport | Cubic forms in thirty-two variables[END_REF]). For some other small degrees, the conjecture was confirmed except for a concrete list of small primes. For quintic forms, for example, p-adic solubility is guaranteed for all primes p ≥ 11 (Dumke [START_REF] Dumke | p-adic zeros of quintic forms[END_REF]). Certainly the conjecture was very influential in shaping the subject area, and remains a source of inspiration and inquiry.

One possible line of attack for the original question, or approximations thereof, begins with diagonalisation. Indeed, when interpreted on a suitable Q-vector space, a form with integer coefficients diagonalises. More precisely, whenever f ∈ Z[x 1 , . . . , x s ] is a form of degree k, there are a number r ≥ 0 and integers a j , b ij (1 ≤ j ≤ s + r, 1 ≤ i ≤ r) with the property that the equation f (x) = 0 is equivalent with the system of equations In this context, the equation f (x) = 0 is said to be equivalent with the system (1.1) if, for all field extensions K/Q the equation f (x) = 0 has solutions x ∈ K s \ {0} if and only if the system (1.1) admits solutions y ∈ K r+s \ {0}. In Section 2 we present a precise formulation of this transformation which, we believe, is part of the folklore, but seems hard to find in the existing literature. In particular, the solubility of f (x) = 0 over Q p can be discussed by considering (1.1). One obvious advantage is that the system (1.1) is amenable to treatment via the combinatorial theory of p-groups, as suggested by the work of Brüdern and Godinho [START_REF] Brüdern | On Artin's conjecture. I. Systems of diagonal forms[END_REF][START_REF] Brüdern | On Artin's conjecture. II. Pairs of additive forms[END_REF]. However, r is often very large, with negative consequences on the technical side of affairs. Also, the form f can be reshaped as (1.1) in many ways, with different values of r. Yet there is a smallest such number, say r(f ). This invariant measures how far f digresses from a diagonal form where one has r = 0. We believe that Artin's conjecture holds for all forms with small r. In fact, in an important paper, Davenport and Lewis [START_REF] Davenport | Homogeneous additive equations[END_REF] confirm the Artin conjecture for diagonal forms. Here we show that the conjecture is also true in the case r = 1. This is a consequence of our main result that we now announce in a more direct language.

Fix a degree k and a natural number s. Suppose that a j , b j are integers, and consider the pair of equations (1.2)

a 1 x k 1 + a 2 x k 2 + . . . + a s x k s = b 1 x 1 + b 2 x 2 + .
. . + b s x s = 0. Theorem. Let s ≥ k 2 + 2, and let p be a prime. Then there exists a solution (x 1 , . . . , x s ) ∈ Q s p \ {0} of the system (1.2). As an immediate corollary, we note that for a fixed prime p, one may allow the coeffients a j , b j in (1.2) to be p-adic integers, and still conclude as in the theorem. This follows by a routine approximation argument based on the compactness of Z p . If Artin's conjecture is known for a particular value of k, then that case of the theorem follows by substituting the linear equation in (1.2) into the other equation. Thus, for k ≤ 3 our result is trivial, but for k = 4 and many other even degrees Artin's conjecture fails ( [START_REF] Arkhipov | Local representation of zero by a form[END_REF][START_REF] Terjanian | Un contre-exemple à une conjecture d'Artin[END_REF]). Further, the observant reader will have already noticed that the case where k is odd is merely a special case of the main result in Knapp [START_REF] Knapp | Pairs of additive forms of odd degrees[END_REF]. The cases where k ≥ 4 is even are all new.

The condition on s in our theorem cannot be relaxed, at least when k + 1 is a prime p. In fact, in this case, the only p-adic solution of the equation [START_REF] Davenport | Homogeneous additive equations[END_REF], p. 454), and hence the pair of equations in k 2 + 1 variables given by (1.3) and x k 2 + x k 2 +1 = 0 has no non-trivial p-adic solution.

(1.3) k-1 j=0 p j k l=1 x k jk+l = 0 is x ν = 0 (1 ≤ ν ≤ k 2 ) (see
There is a large body of work on a generalisation of Artin's conjecture to systems of diagonal forms. These take the shape

(1.4) S j=1 a ij x ki j = 0 (1 ≤ i ≤ R)
in which S, R and k i are natural numbers, and a ij are integers. The conjecture asserts that in each p-adic field the equations (1.4) have a non-trivial solution provided that (1.5) S > k 2 1 + k 2 2 + . . . + k 2 R . Note that our theorem is the case R = 2, k 2 = 1, and that the system (1.1) is the case R = r + 1, k j = 1 for j ≥ 2. It is therefore not without interest to compare our result to others concerning the system (1.4). Davenport and Lewis [START_REF] Davenport | Simultaneous equations of additive type[END_REF] considered the important special case where the k i are all equal and were able to prove the conjecture when R = 2 and k 1 = k 2 is odd [START_REF] Davenport | Two additive equations[END_REF]. When k 1 = k 2 is even, Brüdern and Godinho [START_REF] Brüdern | On Artin's conjecture. II. Pairs of additive forms[END_REF] confirmed the conjecture for many k (see also Kränzlein [17]). Knapp [START_REF] Knapp | Pairs of additive forms of odd degrees[END_REF] then showed that the conjecture also holds when R = 2 and k 1 = k 2 are both odd, while Wooley [START_REF] Wooley | On simultaneous additive equations[END_REF] showed that when R = 2, k 1 = 2 and k 2 = 3 then S ≥ 11 suffices to ensure p-adic non-trivial solutions. For larger R little is known (see [START_REF] Brüdern | On Artin's conjecture. I. Systems of diagonal forms[END_REF][START_REF] Davenport | Simultaneous equations of additive type[END_REF][START_REF] Low | Simultaneous diagonal congruences[END_REF]). It is rather remarkable that Wooley [START_REF] Wooley | Artin's conjecture and systems of diagonal equations[END_REF] very recently found examples with R = 2 where the conjecture fails, though such failures have been familiar for large R (see [START_REF] Lewis | On zeros of p-adic forms[END_REF]). From the perspective taken here, our theorem adds to the small stock of examples where a conjecture of Artin's type has been verified for a class of forms of even degree.

Our proof of the theorem is largely combinatorial. In Section 3, we apply a simple contraction argument that will eliminate the linear equation. In this way we will obtain the theorem already for almost all k. Only those values of k that are small powers of 2, or that are of the form k = p -1, k = p(p -1) with p an odd prime will deny treatment by this first approach.

In subsequent sections we consider the cases k = p -1 and k = p(p -1). We begin with reducing the original problem to one on congruences, and to realise this, we establish our own variant of Hensel's lemma in Section 4. In many instances later in the argument, congruences will be solved by implicit and explicit uses of the Cauchy-Davenport theorem. The relevant combinatorial tools for this strategy are provided in Section 5. We develop an elementary inverse theory to make economies on the number of variables save in exceptional cases that can be explicitly described. In Section 6 we introduce a natural equivalence relation on the set of equations (1.2). Here we are motivated by the p-normalisation of Davenport and Lewis [START_REF] Davenport | Cubic equations of additive type[END_REF], but our approach is different. In a sense it is only the non-linear equation in (1.2) that is normalised.

In Sections 7 to 9, we handle the case k = p -1. From earlier work on related questions, one would foresee a reduction to a congruence modulo p for which a non-singular solution is then required. The work in Section 7 shows that this approach is only partially successful. There remains a case where all the solutions of the ambient congruence modulo p are singular. Fortunately, aided by the inverse theory from Section 5, the systems where this happens may be classified; these are the critical systems introduced at the end of Section 7. For the critical systems a direct application of a Hensel type lift is not possible. We bypass this difficulty by solving a congruence to a potentially very large power of p, and in doing so we invoke aid from variables in the given system where the coefficients are divisible by p. These are features in our argument that are absent from earlier work. For more details we refer to Sections 8 and 9.

In Sections 10 to 12 the case k = p(p -1) is considered. Apart from minor complications in detail, the treatment in this case is along more familiar lines, and in particular, we will always be able to reduce the problem to one on congruences modulo p 2 that admit non-singular solutions.

We are then left with the case where k is a power of the prime p = 2, discussed in Sections 13 to 17. This takes us into a third stream of ideas. Our work in Section 4 forces us to solve congruences modulo high powers of 2. Our strategy is to lift solutions, modulo 2 l , to solutions modulo 2 l+1 through the method of contractions, as introduced by Davenport and Lewis [START_REF] Davenport | Homogeneous additive equations[END_REF][START_REF] Davenport | Two additive equations[END_REF]. The details are rather subtle, and the development of their ideas that is required here is best described en cours. There is a curious feature concerning the case k = 4 where our main argument collapses. It so happens that for certain normalised forms of degree 4 the routine reduction to congruences leads one into a dead end. For an example where and why this happens, see (13.2). To salvage the situation, we turn to an equivalent system that is rather far from normalised but readily seen to admit 2-adic solutions. Perhaps this is a first glimpse of certain weaknesses in the traditional p-normalisation method.

It would be interesting to explore the limitations of the methods presented in this communication. One question is whether our approach yields when r > 1, and to what extent. Further, we propose to compute the invariant r(f ) for the forms f of degree 4 that Terjanian [START_REF] Terjanian | Un contre-exemple à une conjecture d'Artin[END_REF][START_REF] Terjanian | Formes p-adiques anisotropes[END_REF] used to rebut Artin's conjecture.

A diagonalisation method

In this section we briefly substantiate a remark made in the introduction, and show that a form with rational coefficients can always be realised as a diagonal form on a suitable linear subpace of Q t , when t is sufficiently large. This is only a special case of the following result.

Proposition. Let F be a field of characteristic 0, and let k, s ∈ N. Suppose that g ∈ F [X 1 , . . . , X s ] is a form of degree k. Then, there exist a number r with

0 ≤ r ≤ s(s + 1) . . . (s + k -1) k! , linear forms L j ∈ F [Y 1 , . . . , Y r+s ] (1 ≤ j ≤ r) and c j ∈ F (1 ≤ j ≤ r + s)
with the property that in any field extension E/F the equation g(x 1 , . . . , x s ) = 0 has a solution x ∈ E s \ {0} if and only if the system of equations

r+s j=1 c j y k j = 0, L j (y) = 0 (1 ≤ j ≤ r)
has a solution y ∈ E r+s \ {0}.

In the sequel, we shall suppose that F and k are as in the hypotheses in the Proposition.

For a proof of the proposition, let R = s(s + 1) . . . (s + k -1)/(k!). Then there are linear forms Λ j (X 1 , . . . , X s ) with coefficients in F , and

α j ∈ F such that (2.1) g(X 1 , . . . , X s ) = R j=1 α j Λ j (X 1 , . . . , X s ) k .
This is shown in Ellison [START_REF] Ellison | A 'Waring Problem' for homogeneous forms[END_REF], pp. 665-666, over the complex numbers, but the argument works over fields of characteristic zero. Now suppose that (x 1 , . . . , x s ) ∈ E s is a solution of g(x) = 0 with x = 0. We put y j = Λ j (x 1 , . . . , x s ). Then, the x i and y j solve the system of equations

(2.2) R j=1 α j y k j = 0, y j -Λ j (x 1 , . . . , x s ) = 0 (1 ≤ j ≤ R).
Conversely, suppose that a non-trivial solution in E of (2.2) is given. If this solution would have x i = 0 for all 1 ≤ i ≤ s, then a consideration of the linear subsystem

shows that also all y j would be 0 which is not the case. Hence, some of the variables x j must be non-zero, and from (2.1) we see that g(x) = 0. This completes the proof.

Contractions

Throughout the paper, we now suppose that p is a prime and that k ≥ 4. We may do so because for k = 1, 2, 3 the Artin conjecture is known to hold; recall the comments in Section 1. In this section, we apply a simple contraction argument to the pair of equations (1.2). In short, in this equation, we force that b 2l-1 x 2l-1 + b 2l x 2l = 0, parametrize the solutions of this linear relation, and substitute into the degree k equation. We are then left with a single equation of degree k in [s/2] variables. In many cases, this argument is of strength sufficient to conclude that (1.2) has non-trivial p-adic solutions.

Let Γ * (k, p) denote the smallest natural number t with the property that whenever c 1 , . . . , c t ∈ Z, then the equation

(3.1) c 1 x k 1 + c 2 x k 2 + • • • + c t x k t = 0 has a non-trivial solution x ∈ Q t p .
The following lemma makes the contraction argument precise.

Lemma 3.1. Suppose that s ≥ 2Γ * (k, p). Then the system (1.2) has a non-trivial solution in Q p . Proof. Within this proof, let Γ = Γ * (k, p). For 1 ≤ l ≤ Γ, define the integers u 2l-1 , u 2l by u 2l-1 = b 2l , u 2l = -b 2l-1 except when b 2l-1 = b 2l =
0 in which case we take u 2l-1 = u 2l = 1. Then in all cases, one at least of u 2l-1 , u 2l is non-zero. With y l ∈ Q p still to be determined, we now choose

(3.2) x 2l-1 = u 2l-1 y l , x 2l = u 2l y l (1 ≤ l ≤ Γ)
and then put x j = 0 for 2Γ < j ≤ s. Then

s j=1 b j x j = Γ l=1 y l (b 2l-1 u 2l-1 + b 2l u 2l ) = 0 and s j=1 a j x k j = Γ l=1 c l y k l in which c l = a 2l-1 u k 2l-1 + a 2l u k 2l ∈ Z. We choose a solution y ∈ Q Γ p {0} of c 1 y k 1 + • • • + c Γ y k Γ = 0. With this choice of y, the numbers x ∈ Q s p defined in (3.
2) are a non-trivial solution of (1.2). With Lemma 3.1 in hand, we wish to determine conditions on p that ensure

(3.3) Γ * (k, p) ≤ 1 2 k 2 + 1
, because in such circumstances the conclusion of the Theorem is implied at once.

The function Γ * (k, p) has been studied in detail by Dodson [START_REF] Dodson | Homogeneous additive congruences[END_REF]. We proceed by discussing the consequences of his work for 2-adic solubility. Next we suppose that k is even and write k = 2 τ k 0 with τ ≥ 1 and k 0 odd. Then by Dodson [START_REF] Dodson | Homogeneous additive congruences[END_REF], Lemma 4.6.1, one has

(3.4) Γ * (k, 2) ≤ k(2 τ +2 -1) τ + 2 + 1.
If k 0 = 1 and τ ≥ 6, one has

k(2 τ +2 -1) τ + 2 = 4k 2 -k τ + 2 < 1 2 k 2 , so that (3.4) implies (3.3). If k 0 ≥ 3 and τ ≥ 1, one finds that k(2 τ +2 -1) τ + 2 ≤ 4k2 τ τ + 2 = 4 (τ + 2)k 0 k 2 ≤ 4 9 k 2 .
Again, via (3.4), this confirms (3.3). We have now shown that for all k covered by the hypotheses in Lemma 3.2, the inequality (3.3) holds. The conclusion of Lemma 3.2 now follows from Lemma 3.1.

A similar argument applies when p is odd. In this context, put d = (k, p -1) and write (3.5) k = p τ dk 0 with p k 0 . Dodson [13, p. 165] denotes by γ * (k, p l ) the smallest positive integer t with the property that whenever c 1 , . . . , c t are integers coprime to p then the congruence

c 1 x k 1 + c 2 x k 2 + • • • + c t x k t ≡
0 mod p l has a solution with at least one of x 1 , . . . , x t coprime to p. Further progress will depend on the inequality

(3.6) Γ * (k, p) ≤ k γ * (k, p τ +1 ) -1 + 1 that is part of [
(3.7) γ * (δ, p) ≤ 1 2 (δ + 4) whenever δ | p -1, δ < 1
2 (p -1) and p ≥ 5, irrespective of the parity of δ. Lemma 3.3. Suppose that the even natural number δ satisfies the relations δ | p-1 and δ < 1 2 (p -1). Then γ * (δ, p) ≤ 1 2 δ + 1. Proof. The hypotheses imply that p ≥ 7. Now suppose that 2t > δ, and choose c 1 , . . . , c t coprime to p. Then, by a familiar result of Chowla, Mann and Straus [START_REF] Chowla | Some applications of the Cauchy-Davenport theorem[END_REF] (or [START_REF] Nathanson | Additive number theory. Inverse problems and the geometry of sumsets[END_REF]Theorem 2.8]), the set

R 0 = δ/2 j=1 c j x δ j : x j ∈ F p (1 ≤ j ≤ δ/2)
contains at least (δ -1) p-1 δ + 1 elements. Put R = R 0 {0}. By Lemma 2.11 of Nathanson [START_REF] Nathanson | Additive number theory. Inverse problems and the geometry of sumsets[END_REF], the set S = {c t x δ : x ∈ F p } is not an arithmetic progression in F p , and the theory of power residues shows that #S = p-1 δ + 1. Hence, for computing the size of the sumset R + S, Vosper's theorem [START_REF] Nathanson | Additive number theory. Inverse problems and the geometry of sumsets[END_REF]Theorem 2.7] combines with the Cauchy-Davenport theorem [22, Theorem 2.1], and we find that #(R + S) ≥ min(p, #R + #S). The lower bounds for the sizes of S and R show that

#R + #S ≥ (δ -1) p -1 δ + p -1 δ + 1 = p.
In particular, 0 ∈ R + S, and hence, there is a solution of c 1 x δ 1 + . . . c t x δ t ≡ 0 mod p with at least one of x 1 , . . . , x δ/2 not divisible by p. Lemma 3.4. Let k ≥ 4 be even, and let p be an odd prime with p k and p -1 = k. Then, whenever s ≥ k 2 + 2, the equations (1.2) have a non-trivial solution in Q p .

Proof. In (3.5), we have τ = 0. Note that γ * (k, p) = γ * (d, p) (see [12, (2.1.2)]). Thus, we may use upper bounds for γ * (d, p) in (3.6) to verify (3.3).

We divide into cases. First suppose that d is even and that d <

* (k, p) ≤ k 1 4 k + 1 2 + 1 ≤ 1 2 k 2 + 1 as desired.
We now consider d = p -1. By (3.5) and the hypothesis that p -1 = k, we have k = (p -1)k 0 with k 0 ≥ 2. Further, by [12, (2.3.2)], one has γ * (p -1, p) = p. By (3.6), this yields

Γ * (k, p) ≤ k(p -1) + 1 = k -1 0 k 2 + 1 ≤ 1 2 k 2 + 1.

This again confirms (3.3).

This leaves the case d = Proof. We again consider cases, depending on the size of d. If d = p -1, then [START_REF] Dodson | Homogeneous additive congruences[END_REF]Lemma 4.6.1] shows that

(3.9) Γ * (k, p) ≤ k(p τ +1 -1) τ + 1 + 1.
But now k = p τ (p -1)k 0 with τ ≥ 1. For τ ≥ 2 we note that

p τ +1 -1 τ + 1 ≤ 1 3 (p τ +1 -1) = 1 3 p τ (p -1) + p τ -1 ≤ 1 3 (k + p τ ) ≤ 1 3 k 1 + 1 p -1 ≤ 1 2 k.
Hence Γ * (k, p) ≤ 1 2 k 2 + 1. This gives (3.3). For τ = 1 the hypothesis in Lemma 3.5 implies k 0 ≥ 2, and then

p τ +1 -1 τ + 1 = 1 2 (p 2 -1) = 1 2 p(p -1) + p -1 = 1 2 k k 0 + p -1 = 1 2 k 1 k 0 + 1 pk 0 ≤ 1 2 • 4 3 • k k 0 ≤ 1 3 k,
which again implies (3.3) via (3.9). It remains to consider the range 2 ≤ d ≤ 1 2 (p -1). We put ν = γ * (d, p). By [13, Lemma 4.3.2], we have

(3.10) Γ * (k, p) ≤ k(ν τ +1 -1) min(ν, τ + 1) + 1.
First suppose that d < 1 2 (p -1). We begin by showing that in this case one has (3.11) ν

≤ 1 2 d + 3 2 and ν ≤ d.
In fact, the first of these inequalities is (3.7) when d is odd, while Lemma 3.3 asserts that ν ≤ 1 2 d+1 when d is even. In the latter case, the hypotheses that d ≥ 2 implies that

ν τ +1 -1 min(ν, τ + 1) ≤ 1 2 ν τ +1 ≤ 1 2 d 1 2 d + 3 2 τ . But d | (p -1) and d < 1 2 (p -1) so that d ≤ 1 3 (p -1). Therefore ν τ +1 -1 min(ν, τ + 1) ≤ d 2 p -1 6 + 3 2 τ ≤ 1 2 dp τ ≤ 1 2 k. Now (3.
ν τ +1 -1 min(ν, τ + 1) ≤ 1 2 (ν τ +1 -1) ≤ 1 2 (d + 1) p + 1 2 τ = dp τ 1 2 + 1 2d 1 2 + 1 2p τ ≤ 9 20 k.
Once again, (3.10) implies (3.3), and the lemma follows.

We summarise the results obtained so far. For odd k, the conclusion in our theorem is contained in Knapp [START_REF] Knapp | Pairs of additive forms of odd degrees[END_REF]. For even k, the theorem also follows from Lemmas 3.2, 3.4 and 3.5 except for the following situations:

(3.12) p = 2, k ∈ {4, 8, 16, 32}, p > 2, k = p -1 or k = p(p -1).

Reduction to congruences

In this section, we reduce the question concerning p-adic solubility to suitable congruences. This is achieved via an appropriate version of Hensel's lemma that we formulate as Lemma 4.1 below. Throughout this section, we suppose that

(4.1) k = p τ (p -1)
holds with some τ ∈ N 0 , and that k ≥ 4. Hence for p = 2, this implies τ ≥ 2. It is important to note that the cases listed in (3.12) are all of the form (4.1). We put

(
(4.3) a 1 x k 1 + a 2 x k 2 ≡ A mod p γ and b 1 x 1 + b 2 x 2 = B with (4.4) p b 1 a 2 x k-1 2 -b 2 a 1 x k-1 1 .
Then there are y 1 , y 2 ∈ Z p with (y 1 , y 2 ) = (0, 0) and

a 1 z k 1 + a 2 b k 1 x k 2 ≡ Ab k 1 mod p γ , z 1 + b 2 x 2 = B, and elimination of z 1 yields the congruence (4.8) a 1 (B -b 2 x 2 ) k + a 2 b k 1 x k 2 ≡ Ab k 1 mod p γ . Now consider the polynomial ϕ ∈ Z[t] defined by (4.9) ϕ(t) = a 1 (B -b 2 t) k + a 2 b k 1 t k -Ab k 1 . Its formal derivative is (4.10) ϕ (t) = k a 2 b k 1 t k-1 -a 1 b 2 (B -b 2 t) k-1
. By (4.8), one has ϕ(x 2 ) ≡ 0 mod p γ . Furthermore, by (4.10), we infer that

ϕ (x 2 ) k = a 2 b k 1 x k-1 2 -a 1 b 2 (B -b 2 x 2 ) k-1 = a 2 b k 1 x k-1 2 -a 1 b 2 (b 1 x 1 ) k-1 = b k-1 1 a 2 b 1 x k-1 2 -a 1 b 2 x k-1 1 ,
thus showing via (4.4) and (4.6) that p τ ϕ (x 2 ).

We now construct integers ξ l , starting with ξ γ = x 2 , that satisfy the relations (4.11) ϕ(ξ l ) ≡ 0 mod p l , ξ l+1 ≡ ξ l mod p l-τ for all l ≥ γ. To achieve this, suppose that ξ l is already determined and put ξ l+1 = ξ l + p l-τ h, with h ∈ Z at our disposal. Then, by Taylor's theorem,

ϕ(ξ l+1 ) = ϕ(ξ l ) + ϕ (ξ l )p l-τ h + k j=2 ϕ (j) (ξ l ) j! p j(l-τ ) h j .
An inspection of (4.10) reveals the k | ϕ (j) (ξ l ) for all j ≥ 1, and that ϕ (j) (ξ l )/j! is an integer. Further, taking into account the exact power of p that divides j! it easily follows that p l+1 divides ϕ (j) (ξ l )p j(l-τ ) /j! for all j ≥ 2 and all l ≥ γ. In particular, we now see that there is an integer d with (4.12)

ϕ(ξ l+1 ) = p l ϕ(ξ l ) p l + ϕ (ξ l ) p τ h + p l+1 d.
An appropriate choice of h in (4.12) gives ϕ(ξ l+1 ) ≡ 0 mod p l+1 while the recursive congruence in (4.11) arises from the construction. By (4.11), we also see that the sequence ξ l converges to a limit y 2 ∈ Z p , and one has ϕ(y 2 ) = 0 and y 2 ≡ x 2 mod p, so that (4.6) then gives y 2 ∈ Z × p . We now define

y 1 ∈ Q p by b 1 y 1 + b 2 y 2 = B. But p b 1 (by (4.6)), so that y 1 ∈ Z p . By (4.9), 0 = ϕ(y 2 ) = a 1 (B -b 2 y 2 ) k + a 2 b k 1 y k 2 -Ab k 1 = b k 1 a 1 y k 1 + a 2 y k 2 -A .
Proof. Put A = - s j=3 a j x k j , B = - s j=3 b j x j .
Then (4.14) becomes (4.15)

a 1 x k 1 + a 2 x k 2 ≡ A mod p γ , b 1 x 1 + b 2 x 2 ≡ B mod p,
while (4.4) implies that p cannot divide both a 1 x 1 b 2 and a 2 x 2 b 1 . On exchanging the roles of the indices 1 and 2 if necessary, we may assume henceforth that p b 1 a 2 x 2 . Let q = (b 1 ; b 2 ). Then p q, and the substitution z j = qx j takes (4.15) to (4.16)

a 1 z k 1 + a 2 z k 2 ≡ Aq k mod p γ , b 1 z 1 + b 2 z 2 ≡ B mod p
in which b j = b j /q. By (4.16) there is an integer c with b

1 z 1 + b 2 z 2 = B -pc. Since (b 1 ; b 2 ) = 1, there are u 1 , u 2 ∈ Z with b 1 u 1 + b 2 u 2 = c.
We take w j = z j + pu j . Then (4.17)

b 1 w 1 + b 2 w 2 = B while w k j = (z j + pu j ) k = z k j + kz k-1 j pu j + 1 2 k(k -1)z k-2 j
p 2 u 2 j + . . . For odd p, we see that w k j ≡ z k j mod p τ +1 , and recalling that γ = τ + 1, we get (4.18) a 1 w k 1 + a 2 w k 2 ≡ Aq k mod p γ . In the case where p = 2 one has γ = τ +2 and k = 2 τ . But then, binomial expansion shows that there is some v ∈ Z with

w k j = z k j + 2 τ +1 z k-1 j u j + 2 τ +1 (k -1)z k-2 j u 2 j + 2 τ +2 v. But k -1 is odd, and so, 2 | z k-1 j u j + (k -1)z k-2 j u 2
j , and w k j ≡ z k j mod 2 τ +2 . Again, we arrive at (4.18). We have now verified (4.17) and (4.18) in all cases.

We wish to apply Lemma 4.1, and therefore consider

b 1 a 2 w k-1 2 -b 2 a 1 w k-1 1 ≡ b 1 a 2 z k-1 2 -b 2 a 1 z k-1 1 ≡ q k-1 (b 1 a 2 x k-1 2 -b 2 a 1 x k-1 1 ) ≡ q k-2 (b 1 a 2 x k-1 2 -b 2 a 1 x k-1 1
) mod p.

By (4.4), we conclude that p b 1 a 2 w k-1 2 -b 2 a 1 x k-1 1
as required in Lemma 4.1. This now supplies y 1 , y 2 ∈ Z p , not both zero, with

a 1 y k 1 + a 2 y k 2 = Aq k , b 1 y 1 + b 2 y 2 = B. But q ∈ Z ×
p , so that the numbers y j defined by y j = qy j are still in Z p and satisfy a 1 y k 1 + a 2 y k 2 = A and b 1 y 1 + b 2 y 2 = B, as required.

Auxiliaries

For convenience of the reader, we state here Chowla's extension of the Cauchy-Davenport theorem, see [START_REF] Nathanson | Additive number theory. Inverse problems and the geometry of sumsets[END_REF] The following simple consequence is frequently used below. Lemma 5.2. Let q ≥ 2 be an integer. Let s ≥ q, and let c 1 , . . . , c s ∈ (Z/qZ) × . Then, there is a subset J of {1, 2, . . . , s} with 1 ∈ J and j∈J c j ≡ 0 mod q.

Proof. Let A j = {0, c j } for 2 ≤ j ≤ q. Then, recursive application of Lemma 5.1 implies that A 2 + A 3 + • • • + A q = Z/qZ. Hence there exists (ε j ) 2≤j≤q with ε j = 0 or 1 such that q j=2 c j ε j = -c 1 . We take J consisting of 1 and all j with ε j = 1 to confirm the conclusion of the lemma. Lemma 5.3. Let p ≥ 3 and k = p τ (p -1) with τ ≥ 0. Let a 1 , . . . , a p ∈ F × p . Then there is a solution of a 1 x k 1 + • • • + a p x k p = 0 in F p with x 1 = 1. Proof. Apply Lemma 5.2 with q = p and take x j = 1 for j ∈ J and x j = 0 otherwise. Lemma 5.4. Let k be as in Lemma 5.3. Suppose that a 1 , . . . , a p-1 ∈ F × p , and that

a 1 x k 1 + • • • + a p-1 x k p-1 = 0 has no non-trivial solution.
Then the a j are all equal.

Proof. Suppose that the a j are not all equal, and that a 1 = a 2 , say. Then a 1 +a 2 = 0 (otherwise, by choosing x 1 = x 2 = 1 and the other x j zero, we would have a nontrivial solution). Hence, by setting A j = {0, a j } for 1 ≤ j ≤ p -1, we have #(A 1 + A 2 ) ≥ 4, and repeated use of Lemma 5.1 yields

A 1 + A 2 + • • • + A p-2 = F p .
In particular, there exist ε j ∈ {0, 1} such that p-2 j=1 a j ε j + a p-1 = 0. We have constructed a non-trivial solution, which is a contradiction. Thus, the a j are all equal.

Lemma 5.5. Let p ≥ 3. Let a 1 , a 2 , a 3 ∈ F × p . Then, at least one of the sums a 1 +a 2 , a 1 + a 3 , a 2 + a 3 is non-zero. Moreover, two of these sums are non-zero except when, up to permutation, we have a 1 = a 2 = -a 3 .

Proof. Trivial. Proof. By Lemma 5.3, there exists a non-trivial solution to p j=1 a j x p-1 j = 0. Since c = 0, there exists y such that cy = -p j=1 b j x j . The solution (x 1 , . . . , x p , y) of the system is non-singular: indeed, since x 1 = 1, the Jacobian for the variables x 1 and y is non-zero. Proof. First notice that the equation p-1 j=1 a j x p-1 j = 0 has no non-trivial solution (otherwise, by following the lines of the proof of Lemma 5.6, we would have a non-singular solution to the system). The lemma now follows from Lemma 5.4. Lemma 5.8. Let p ≥ 5. Suppose that a 1 , . . . , a p+2 ∈ F × p , and that at least one of the b j ∈ F p is non-zero. Then there is a non-singular solution in F p of the equations p+2 j=1

a j x p-1 j = p+2 j=1 b j x j = 0.
This result is a trivial consequence of Lemma 5.9 below. Lemma 5.9. Let p ≥ 5. Suppose that a 1 , . . . , a p+1 ∈ F × p , and that at least one of the b j ∈ F p is non-zero. Suppose that

(5.1) p+1 j=1 a j x p-1 j = p+1 j=1 b j x j = 0
has no non-singular solution in F p . Then, after a permutation of indices, the matrix of coefficients is of the form

(5.2) a p -a a . . . a b 1 b 2 0 . . . 0 with a, a , b 1 , b 2 ∈ F × p . Proof.
Suppose that exactly t of the numbers b j are non-zero. Then, by renumbering indices, we may assume that b 1 • • • b t = 0, and b j = 0 for j > t.

We first consider the case where t ≥ 3. Then, on applying Lemma 5.5 to a 1 , . . . , a t , we may again rearrange indices to assume that a 1 + a 2 = 0. We now apply Lemma 5.3 to find x 3 , . . . , x p+1 with p+1 j=3

a j x p-1 j = -(a 1 + a 2 ). Let B = p+1 j=3 b j x j . Now choose x 1 ∈ F × p such that b 1 x 1 + B = 0, and then x 2 ∈ F × p with b 1 x 1 + b 2 x 2 + B = 0. This shows that (x 1 , . . . , x p+1
) is a solution of (5.1). For y ∈ F p , we put

z 1 = x 1 + b 2 y, z 2 = x 2 -b 1 y. Then, we have b 1 z 1 + b 2 z 2 + B = 0 irrespective of the values of y. Further, if y is chosen such that z 1 z 2 = 0, we conclude that (z 1 , z 2 , x 3 , . . . , x p+1
) is also a solution of (5.1). We claim that for some y the solution is non-singular mod p. To see this, consider the minor

∆ 1,2 (z 1 , z 2 ) = (p -1)a 1 z p-2 1 (p -1)a 2 z p-2 2 b 1 b 2
of the Jacobian corresponding to indices 1 and 2. Since z 1 z 2 = 0, one has

z 1 z 2 det ∆ 1,2 (z 1 , z 2 ) = (p -1)(a 1 b 2 z 2 -a 2 b 1 z 1 ) = (p -1) a 1 b 2 x 2 -a 2 b 1 x 1 -b 1 b 2 (a 1 + a 2 )y .
Since p ≥ 5, one can choose y such that z 1 z 2 det ∆ 1,2 (z 1 , z 2 ) = 0. This provides the desired non-singular solution.

Next we consider the case t = 2. If a 1 + a 2 = 0, the previous argument still applies, and again yields a non-singular solution of the system (5.1). This leaves the case where a 2 = -a 1 . If one can find a non-trivial solution of p+1 j=3 a j x p-1 j = 0, then take x 1 = x 2 = 0 to obtain a non-singular solution of (5.1) . Hence, by Lemma 5.4, all a j (3 ≤ j ≤ p + 1) are equal, which is (5.2). When t = 1, take x 1 = 0 and use Lemma 5.3.

Normalisation

We now turn to solutions of the system (1.2) in p-adic numbers, and begin with a variant of a normalisation introduced by Davenport and Lewis [START_REF] Davenport | Homogeneous additive equations[END_REF].

Suppose we are given a system of equations (1.2) with rational coefficients a j , b j . Another such system is said to be equivalent to the given one if it can be transformed into the given one by a finite succession of the following processes:

(i) substitutions (x 1 , . . . , x s ) → (c 1 x 1 , . . . , c s x s ), with all c j ∈ Q × , (ii) multiplication of one of the equations by a non-zero rational number, (iii) permutation of indices. This defines an equivalence relation, and if one system (1.2) has a non-trivial p-adic solution, then so have all equivalent systems.

Note that each equivalence class contains a system with integer coefficients. Further we remark that if a i b i = 0 holds for all 1 ≤ i ≤ s, then this is so for all equivalent systems.

A system (1.2) with integer coefficients is referred to as preconditioned (for p) if all its coefficient a j , b j are non-zero, and there exists a b i with p b i . A preconditioned system is said to be conditioned if for 1 ≤ j ≤ k, one has

(6.1) #{1 ≤ i ≤ s : p j a i } ≥ js/k.
Lemma 6.1. Fix natural numbers k and s. Suppose that for all conditioned systems (1.2) there exists non-trivial p-adic solutions. Then all systems (1.2) with rational coefficients have non-trivial p-adic solutions.

Proof. The proof is in two steps. We first show that a system (1.2) with rational coefficients and a i b i = 0 for all 1 ≤ i ≤ s has a non-trivial p-adic solution. According to a comment in the preamble of Lemma 6.1, this will follow from showing that such a system is equivalent to a conditioned system.

To see this, multiply the equations (1.2) with a suitable natural number to arrange that a i , b i are integers. Then define i by p i a i and write i = α i k + ν i with 0 ≤ ν i ≤ k -1. We apply the transformation x i → p -αi x i for all i. Then the new system has i = ν i . On multiplying the linear equation by a suitable integer, the new system can still be supposed to have integer coefficients. For this system, define (6.2)

υ j = #{1 ≤ i ≤ s : ν i = j}
and apply a permutation of indices such that the variables with ν i = 0 are numbered 1, 2, . . . , υ 0 , the variables with ν i = 1 are numbered υ 0 + 1, . . . , υ 0 + υ 1 , and so on. With x 0 = (x 1 , . . . , x υ0 ), x 1 = (x υ0+1 , . . . , x υ0+υ1 ) etc, we then have

(6.3) s i=1 a i x k i = f 0 (x 0 ) + pf 1 (x 1 ) + • • • + p k-1 f k-1 (x k-1 )
where

f j (x j ) = p -j νi=j a i x k i
has integer coefficients. Next apply the transformation x 0 → px 0 , followed by division of (6.3) by p. This transforms (1.2) into an equivalent system where (6.3) now becomes (6.4)

f 1 (x 1 ) + pf 2 (x 2 ) + • • • + p k-2 f k-1 (x k-1 ) + p k-1 f 0 (x 0 ).
Repetition of this argument shows that any cyclic permutation of the f j is possible. Note that this also permutes the υ j accordingly. By [8, Lemma 2], there is a cyclic permutation of the υ j with (6.5)

υ 0 + • • • + υ j ≥ (j + 1)s/k for 0 ≤ j ≤ k -1.
Hence, the new system satisfies (6.1). After multiplication by a suitable natural number, the linear equation will have integer coefficients, and on cancelling redundant factors p, one obtains a conditioned system equivalent to the original one.

In a second step, we apply a compactness argument of Davenport and Lewis. If the system (1.2) with integer coefficients has some a i or b i zero, then for all large n ∈ N, the numbers a i = a i + p n , b i = b i + p n are non-zero. Thus, the system (1.2) with a i , b i in place of a i , b i has a non-trivial p-adic solution z n . By homogeneity, we may suppose that z n ∈ Z s p \ pZ s p . Since Z s p is compact, the sequence (z n ) n contains a convergent subsequence. By the argument given in [START_REF] Davenport | Simultaneous equations of additive type[END_REF], page 573, its limit is a non-trivial solution of the given system.

The case k = p -1: a reduction step

We require some notation that we shall use throughout the next three sections. First and foremost, we suppose that k = p -1. Recall here also that we assumed that k ≥ 4 so that p ≥ 5. Further, let (1.2) be a system with non-zero integer coefficients and p k a i for all 1 ≤ i ≤ s. Then define the numbers ν i , µ i via

p νi a i , p µi b i .
The variable x i in (1.2) (or the index i) is said to be low when µ i < ν i , and high otherwise. The number min(µ i , ν i ) is called the level of the variable x i . We now mimic some of the analysis from the proof of Lemma 6.1. We define υ j by (6.2) and note that p k a i (1 ≤ i ≤ s) implies that υ j vanishes for j ≥ k. Hence, after a suitable permutation of the variables x i , the given form of degree k can be represented as in (6.3). In particular, the vectors x j and the forms f j are defined in our current context. Note that conditioned systems are covered by this set-up, and for these one has the additional inequality (6.5).

Lemma 7.1. Let (1.2) be a system with non-zero integer coefficients. Suppose that υ 0 ≥ k + 1, and that there is a low variable at level 0. Then the system has a non-trivial p-adic solution. In particular, a conditioned system with s ≥ k 2 + 2 and a low variable at level 0 has a non-trivial p-adic solution.

Proof. The variables x 1 , . . . , x υ0 are at level 0, and are high by definition. Hence, if x j is a low variable at level 0, then j > υ 0 and p b j . We take x i = 0 for i > υ 0 , except for one low variable x j . Then we apply Lemma 5.6 with x j in the role of y to obtain a non-singular solution of the pair of congruences

s i=1 a i x k i ≡ s i=1 b i x i ≡ 0 mod p.
Then, Lemma 4.2 yields the desired p-adic solution of (1.2). For conditioned systems, the inequality υ 0 ≥ k + 1 follows from (6.5).

Lemma 7.2. Let (1.2) be a system with non-zero integer coefficients. Suppose that υ 0 ≥ k + 3. Then there exists a non-trivial p-adic solution.

Proof. On cancelling redundant factors p from the linear equation, we may suppose that p b j for at least one j. If j > υ 0 , then x j is low and Lemma 7.1 yields a non-trivial p-adic solution. If j ≤ υ 0 , then Lemma 5.8 yields a non-singular solution of (7.1)

υ0 j=1 a j x k j ≡ υ0 j=1 b j x j ≡ 0 mod p.
We may take x j = 0 for j > υ 0 and apply Lemma 4.2 to find a non-trivial p-adic solution of (1.2).

Lemma 7.3. Let s ≥ k 2 + 2, and suppose that the system (1.2) is conditioned. Suppose further that for some j ∈ {1, . . . , k -1} one has υ j ≥ k + 1. Then there exists a non-trivial p-adic solution.

Proof. In view of Lemma 7.1, we may assume that no variable at level 0 is low.

Hence the variables at level 0 are exactly x 1 , . . . , x υ0 , and p | b m for all m > υ 0 .

Since the system is conditioned, there is i 0 ≤ υ 0 with p b i0 . We apply x i → px i for 0 ≤ i ≤ j -1. We then divide the degree k equation by p j , and the linear equation by p. The new system has integer coefficients, is equivalent with the given one, and the variables in x j are now at level 0. Also the variable x i0 is a low variable at level 0 in the new system. Hence, Lemma 7.1 yields a non-trivial p-adic solution.

We now summarise the impact of the above lemmata on conditioned systems.

Lemma 7.4. Suppose that s ≥ k 2 + 2, and that the system (1.2) is conditioned. If this system does not have a non-trivial p-adic solution, then

(7.2) s = k 2 + 2, υ 0 = k + 2, υ j = k (1 ≤ j ≤ k -1),
and for all 1 ≤ j ≤ k -1, the forms f j as defined in (6.3) satisfy

(7.3) f j (z 1 , . . . , z k ) ≡ c j (z k 1 + • • • + z k k ) mod p
for some integer c j with p c j .

Proof. Since the system is conditioned, but does not have a non-trivial p-adic solution, we deduce from Lemma 7.3 that υ j ≤ k for 1 ≤ j ≤ k -1, and from Lemma 7.2 that

υ 0 ≤ k + 2. But υ 0 + • • • + υ k-1 = s ≥ k 2 + 2
, and (7.2) follows. Now let j ∈ {1, . . . , k -1}. By Lemma 7.1, no variable at level 0 is low. Hence, the argument of proof of Lemma 7.3 shows that the given system is equivalent to one where the variables x i that originally had ν i = j are now at level 0, and the new system has an extra low variable at level 0. Lemma 5.7 is applicable to the new system, and in view of Lemma 4.2, we may conclude that the coefficients of f j are all equal, mod p. This gives (7.3).

From now on, we are reduced to consider conditioned systems where (7.2) holds. By Lemma 5.9, either there is a non-singular solution of the congruences (7.1), and then via Lemma 4.2 a non-trivial p-adic solution of (1.2), or there is a permutation of indices and integers a, a , b 1 , b 2 with p aa b 1 b 2 and (7.4)

a i b i 1≤i≤υ0 ≡ a -a a . . . a b 1 b 2 0 . . . 0 mod p.
Thus, we may suppose that the conditioned system satisfies both (7.2) and (7.4). We now multiply the degree k equation of the given system with b k 1 b k 2 . Note that this does not affect the numbers

ν j because b k 1 b k 2 ≡ 1 mod p. Since p is odd, the substitution x 1 = b 1 x 1 , x 2 = -b 2 x 2
takes the given system to an equivalent system where the new coefficients, say a j , b j again, satisfy b 1 = 1, b 2 = -1, while (7.4) still holds. Now choose an integer a with a a ≡ 1 mod p and multiply the degree k equation in (1.2) by a . In this way we arrange that (7.4) holds with a = 1. We compile this argument as the following result. Lemma 7.5. A conditioned system (1.2) with (7.2) and (7.4) is equivalent to a conditioned system satisfying b 1 = -b 2 = 1 and

(7.5) a i b i 1≤i≤υ0 ≡ a -a 1 . . . 1 1 -1 0 . . . 0 mod p.
It remains to solve conditioned systems of the shape introduced in Lemma 7.5. If in such a system one has a 1 = -a 2 , then x 1 = x 2 = 1 and x j = 0 (j ≥ 3) is a non-trivial rational solution. Hence we may suppose that a 1 + a 2 = 0.

We now refer to a conditioned system as critical if the following conditions are satisfied:

(i) a 1 + a 2 = 0, b 1 = -b 2 = 1,
(ii) the equations (7.2) hold, (iii) the congruences (7.5) hold, (iv) for 1 ≤ j ≤ k -1, the congruences (7.3) hold, (v) there is no low variable at level 0.

In this language, Lemmata 7.1, 7.4 and 7.5 may be summarised as follows.

Lemma 7.6. Suppose that s ≥ k 2 + 2 and that the conditioned system (1.2) does not have a non-trivial p-adic solution. Then, the system is equivalent to a critical system.

The case k = p -1: critical systems

In this and the next section, we show that any critical system (1.2) has non-trivial p-adic solutions. This is the most demanding part of our proof of the theorem. It will turn out that the variables x 1 , x 2 can be grouped together with a block of variables, all with the same value of ν j , to form a subsystem that is readily solved over Q p . However, the selection process for this block depends on the distribution of the numbers µ 3 , . . . , µ k 2 +2 in a delicate manner. For a critical system, the integers a 1 , a 2 are not divisible by p, but we have p | a 1 + a 2 and a 1 + a 2 = 0. Hence, there is θ ∈ N with p θ a 1 + a 2 . Throughout, we assume that a 1 , a 2 have these properties and define θ even if a 1 , a 2 are not related to a critical system. Lemma 8.1. Let a 1 , a 2 be as in the preceding paragraph, and let c, d be integers with p cd. Then for each l with 1 ≤ l < θ, there are integers x 1 , x 2 , c with c ≡ c mod p and

a 1 x k 1 + a 2 x k 2 = p l c , x 1 -x 2 = p l d. Proof. Since k = p -1,
we see that p k, and by Fermat's theorem, there is a natural number x with ka 1 dx k-1 ≡ c mod p. Now choose

x 2 = x, x 1 = x + p l d. Then a 1 x k 1 + a 2 x k 2 = a 1 (x + p l d) k + a 2
x k , and we have assumed that 2 ≤ l + 1 ≤ θ. Hence, l + 1 ≤ 2l, and it follows that

a 1 x k 1 + a 2 x k 2 ≡ (a 1 + a 2 )x k + ka 1 dx k-1 p l k ≡ cp l mod p l+1 , as required.
The next two lemmas are concerned with auxiliary systems that we shall meet recursively in the course of the argument.

c 1 ≡ c 2 ≡ • • • ≡ c k mod p.
Let 1 ≤ β < θ. Then, the system of equations

(8.2) a 1 x k 1 + a 2 x k 2 +p β (c 1 y k 1 + • • • + c k y k k ) +p β+1 ez k = 0, x 1 -x 2 +p β (d 1 y 1 + • • • + d k y k ) +p β f z = 0 has a non-trivial solution (x 1 , x 2 , y 1 , . . . , y k , z) ∈ Q k+3 p .
Proof. We apply Lemma 8.1 with l = β, d = 1 and c = -kc 1 . Lemma 8.1 then delivers numbers x 1 , x 2 ∈ Z that we insert in (8.2). A factor p β can now be cancelled from both equations in (8.2), and these equations now reduce to

(8.3) c +c 1 y k 1 + • • • + c k y k k +pez k = 0, 1 +d 1 y 1 + • • • + d k y k +f z = 0,
in which c is a certain integer with c ≡ -kc 1 mod p. Now note that

y 1 = y 2 = • • • = y k = 1 and a suitable z ∈ N solve the pair of congruences c + c 1 y k 1 + • • • + c k y k k + pez k ≡ 0 mod p, 1 + d 1 y 1 + • • • + d k y k + f z ≡ 0 mod p,
and the Jacobian determinant associated with y k and z at this solution is

k y k-1 k c k f -pez k-1 d k ≡ kc k f ≡ 0 mod p.
Consequently, Lemma 4.2 provides a solution of (8.3) in p-adic numbers in which y k = 0. This solution, together with the x 1 , x 2 chosen earlier, is a solution of (8.2). Lemma 8.3. Let a 1 , a 2 be as in the preamble of Lemma 8.1. Let c 1 , . . . , c k , d 1 , . . . , d k be integers with p c 1 d 1 and (8.1). Let 1 ≤ β < θ. Then, the system of equations

(8.4) a 1 x k 1 + a 2 x k 2 +p β (c 1 y k 1 + • • • + c k y k k ) = 0, x 1 -x 2 +p β (d 1 y 1 + • • • + d k y k ) = 0
c +c 1 y k 1 + c 2 y k 2 = 0, -d 1 +d 1 y 1 + p m d 2 y 2 = 0.
By construction, the pair

y 1 = 1, y 2 = u is a solution of the congruences c + c 1 y k 1 + c 2 y k 2 ≡ 0 mod p, -d 1 + d 1 y 1 + p m d 2 y 2 ≡ 0 mod p,
and the Jacobian determinant at this solution is k(c 1 p m d 2 -c 2 d 1 u k-1 ). By considering separately the cases m = 0 and m = 0, one observes that this determinant is not divisible by p. As in the proof of Lemma 8.2, a non-trivial solution of (8.5) in Q p is now supplied by Lemma 4.2, and this unfolds to such a solution of (8.4).

The next two results are consequences of the last two lemmata for critical systems.

Lemma 8.4. Suppose that (1.2) is a critical system, and that there is a low variable at level l with l < θ. Then the system (1.2) has a non-trivial p-adic solution.

Proof. Recall that critical systems have no low variables at level 0. Now consider all low variables and choose one, say x t , where the level β is the smallest among them. Then 1 ≤ β < θ. Further, the variables x β of f β (x β ) are all high, thanks to the minimality of β. We put all variables in (1.2) to 0 except x 1 , x 2 , x β and x t . With x β = (y 1 , . . . , y k ), x t = z and a t = p β+1 e, b t = p β f , we have e, f ∈ Z with p f , and the system (1.2) reduces to the system (8.2), with the conditions for application of Lemma 8.2 satisfied. This yields the desired solution of (1.2). Lemma 8.5. Suppose that (1.2) is a critical system that involves a variable x t with 1 ≤ ν t = µ t < θ. Then the system has a non-trivial p-adic solution.

Proof. The variable x t is at level β = ν t , and therefore occurs among the entries of x β = (y 1 , . . . , y k ), say. By symmetry, we may suppose that x t = y 1 . If any of the variables y 2 , . . . , y k were low, then Lemma 8.4 would supply the desired solution of (1.2), so we may suppose that y 2 , . . . , y k are all high. We take all x j in (1.2) as 0 except x 1 , x 2 and x β = (y 1 , . . . , y k ). Then (1.2) reduces to the system (8.4), with the conditions for applicability of Lemma 8.3 all met. This yields the desired solution of (1.2).

We now establish a result that complements Lemmas 8.4 and 8.5. The strategy is different from the above approach. In particular, we rely on the classical version of Hensel's Lemma, and contract the variables x 1 and x 2 suitably. Lemma 8.6. Suppose that (1.2) is a critical system. Write θ = υk + r with 0 ≤ r ≤ k -1. For all i ≥ 3 with ν i = r suppose that µ i > θ -υ holds. Then (1.2) has a non-trivial p-adic solution.

Proof. Recall that for a critical system the variables x i with i ≥ 3 and ν i = r are exactly those where rk + 2 < i ≤ rk + k + 2. For convenience, we put y = (x rk+3 , . . . , x rk+k+2 ) and then set all variables in (1.2) to 0 except x 1 , x 2 and y. Renaming coefficients, the system (1.2) then reduces to the pair of equations

a 1 x k 1 + a 2 x k 2 +p r (c 1 y k 1 + • • • + c k y k k ) = 0, x 1 -x 2 +p θ-υ+1 (d 1 y 1 + • • • + d k y k ) = 0
in which c i , d i denote integers with p c i and (8.1). We put y = p υ z. Then the system becomes (8.6)

a 1 x k 1 + a 2 x k 2 +p θ (c 1 z k 1 + • • • + c k z k k ) = 0, x 1 -x 2 +p θ+1 (d 1 z 1 + • • • + d k z k ) = 0,
and it now suffices to construct a non-trivial p-adic solution of this pair of equations.

Write a 1 + a 2 = p θ a . Then a ∈ Z with p a . By Lemma 5.3, we can choose integers z 1 , . . . , z k with

c 1 z k 1 + • • • + c k z k k ≡ -a mod p.
Not all of the z i can be divisible by p, and by symmetry, we may suppose that p z 1 . With these integers determined, put

(8.7) h = -p θ+1 (d 1 z 1 + • • • + d k z k ).
With a variable x ∈ Q p still at our disposal, we choose

x 2 = x, x 1 = x + h,
and substitute in (8.6). Then, the linear equation of (8.6) is satisfied irrespective of the value of x. Further, the first equation in (8.6) reduces to (8.8)

a 1 (x + h) k + a 2 x k -p θ c = 0
where according to our construction, the integer c = -(c

1 z k 1 + • • • + c k z k k ) satisfies c ≡ a mod p. However (8.9) a 1 (x + h) k + a 2 x k = p θ a x k + ka 1 x k-1 h + h 2 Q k (x, h)
where

Q k ∈ Z[x, h] is a certain polynomial. With h fixed via (8.7), it follows that ϕ(x) = p -θ a 1 (x + h) k + a 2 x k
is a polynomial with integer coefficients, and from (8.7) and (8.9) we see that ϕ(1) ≡ a mod p and ϕ (1) ≡ ka ≡ 0 mod p. Hence x = 1 is a solution of the congruence ϕ(x) -c ≡ 0 mod p. By Hensel's Lemma, there is a non-zero x ∈ Q p with ϕ(x) -c = 0, and this x also solves (8.8). This completes the proof of Lemma 8.6.

Lemma 8.7. The conclusion of Lemma 8.3 remains valid when β = θ.

Proof. We recast the system (8.4) that now takes the shape (8.10)

a 1 x k 1 + a 2 x k 2 +p θ (c 1 y k 1 + • • • + c k y k k ) = 0, x 1 -x 2 +p θ (d 1 y 1 + • • • + d k y k ) = 0,
in which c i , d i are certain integers with (8.1) and p c 1 , and not all the d i are divisible by p. From now on, we assume that c i ≡ 1 mod p holds for all 1 ≤ i ≤ k, and we may do so without loss of generality. To see this, choose c ∈ N with cc 1 ≡ 1 mod p, and multiply the top equation in (8.10) by c. Then, we still have p θ ca 1 + ca 2 , and (8.1) implies that cc j ≡ 1 mod p for all j, as required.

By symmetry, we may further suppose that

p d i (1 ≤ i ≤ i 0 ), p | d i (i 0 < i ≤ k)
holds with a suitable number i 0 ∈ {1, . . . , k}.

We now discuss the equations (8.10) by a blend of ideas now familiar from the proofs of Lemmas 8.4 and 8.6. Put a 1 + a 2 = p θ a , and write a ≡ -α mod p with 1 ≤ α ≤ p -1.

There will be four cases to consider.

(i) Suppose that α ≥ 2 and i 0 ≥ 2. Then we take x 1 = x 2 = 1 and y j = 0 (α < j ≤ k) in (8.10) which then reduces to (8.11) a

+ c 1 y k 1 + • • • + c α y k α = 0 d 1 y 1 + • • • + d α y α = 0.
But since α ≥ 2 and i 0 ≥ 2 hold simultaneously it is immediate that there exist integers z 1 , . . . , z α , all not divisible by p, with d 1 z 1 + • • • + d α z α ≡ 0 mod p. Since all c j are in the class 1 mod p, it follows that the congruences (8.12)

a + c 1 z k 1 + • • • + c α z k α ≡ 0 mod p d 1 z 1 + • • • + d α z α ≡ 0 mod p
hold simultaneously. But α < p, and hence, the numbers d i z i cannot all be equal, modulo p. Hence, we can choose 1 ≤ i < j ≤ α with d i z i ≡ d j z j mod p. Let ∆ i,j be the Jacobian determinant for z i , z j at this solution of (8.12). Then

z i z j ∆ ij = det kc i z k i kc j z k j d i z i d j z j ≡ k(d j z j -d i z i ) mod p,
so that the solution in (8.12) is non-singular. By Lemma 4.2, we infer that (8.11) has a non-trivial p-adic solution, as required.

(ii) Suppose that α = 1 and i 0 ≥ 2. First choose d ∈ N with a + ka 1 d ≡ -2 mod p. Note that this implies that p d. Now take x 2 = 1 and x 1 = 1 + dp θ in (8.10) as well as y 3 = • • • = y k = 0. Then, since we have

a 1 x k 1 + a 2 x k 2 = p θ (a + a 1 dk) + p 2θ E with some E ∈ Z, the equations (8.10) reduce to (8.13) a + a 1 dk + p θ E+ c 1 y k 1 + c 2 y k 2 = 0 d+ d 1 y 1 + d 2 y 2 = 0.
However, there are integers z 1 , z 2 with p z 1 z 2 and d 1 z 1 ≡ d mod p, d 2 z 2 ≡ -2d mod p. Then, according to our choice of d, the numbers z 1 , z 2 solve the congruences

(8.14) a + a 1 dk + p θ E+ c 1 z k 1 + c 2 z k 2 ≡ 0 mod p, d+ d 1 z 1 + d 2 z 2 ≡ 0 mod p.
Note that the Jacobian determinant at the solution z 1 , z 2 is not divisible by p. It follows from Lemma 4.2 that (8.13) has a non-trivial solution in Q p , as required.

(iii) Suppose that i 0 = 1 and α ≤ p -2. This is similar to case (i). Take x 1 = x 2 = 1 in (8.10) which then reduces to (8.15) a

+ c 1 y k 1 + • • • + c k y k k = 0, d 1 y 1 + • • • + d k y k = 0.
The integers z 1 = 0, z 2 = • • • = z α+1 = 1 and z j = 0 for j ≥ α + 2 provide a solution of the associated congruences

a + c 1 z k 1 + • • • + c k z k k ≡ 0 mod p, d 1 z 1 + • • • + d k z k ≡ 0 mod p.
Further, the Jacobian determinant with respect to z 1 , z 2 is not divisible by p (note here that z 1 = 0 and p | d 2 ). Once again via Lemma 4.2, this yields a non-trivial p-adic solution of (8.15). (iv) Suppose that i 0 = 1 and α = p -1. We choose d, x 1 and x 2 as in case (ii), and also put y 3 = • • • = y k = 0. We then again reduce to the system (8.13), but this time with p d 1 , p | d 2 . Choose z 1 with d 1 z 1 ≡ -d mod p. Then p z 1 . Also, take z 2 = 1. Then, by construction, (8.14) holds, with Jacobian determinant not divisible by p. As in case (ii), one is led to a non-trivial p-adic solution. This completes the proof.

We are ready to treat all critical systems with small θ. Lemma 8.8. A critical system with θ < k has non-trivial p-adic solutions.

Proof. Recall that θ ≥ 1, and hence that all variables x i with ν i = θ are those where (8.16) θk

+ 3 ≤ i ≤ θk + k + 2.
First suppose that for all i in (8.16) one has µ i > θ. Then Lemma 8.6 yields the desired p-adic solution.

Next suppose that there is an i as in (8.16) where µ i < θ. Then x i is a low variable at a level less than θ. In this case Lemma 8.4 provides a non-trivial p-adic solution.

In the cases not yet considered one has µ i ≥ θ for all i in (8.16), and µ i = θ for at least one of the i in (8.16). We now take all x j = 0 in the given critical system except for x 1 , x 2 and y = (x θk+3 , . . . , x θk+k+2 ). Renaming coefficients, the system then takes the shape (8.10) in which c i , d i are certain integers with (8.1) and p c 1 , and not all the d i are divisible by p. The desired p-adic solution is now provided by Lemma 8.7. 9. The case k = p -1: le coup de grâce

In this section we complete our analysis of critical systems by establishing the following complement to Lemma 8.8. Lemma 9.1. A critical system with θ ≥ k has non-trivial p-adic solutions.

Once this lemma is established, we conclude via Lemma 8.8 that all critical systems have non-trivial p-adic solutions. As mentioned earlier, it now follows via Lemma 7.6 that all conditioned systems have such solutions, and then via Lemma 6.1, this finally establishes the case k = p -1 of the theorem. Given a critical system with θ ≥ k, we open the endgame by re-grouping its variables into blocks (9.1)

y j = (x kj+3 , x kj+4 , . . . , x kj+k+2 ) (0 ≤ j ≤ k -1),
and may then present the system as

A(x 1 , x 2 , y 0 , . . . , y k-1 ) = k 2 +2 i=1 a i x k i , B(x 1 , x 2 , y 0 , . . . , y k-1 ) = k 2 +2 i=1 b i x i . (9.2)
Recalling that θ ≥ k ≥ 4, either Lemma 8.4 or Lemma 8.5 will solve the system A = B = 0 over Q p unless the inequalities

(9.3) µ i > ν i
hold for all i ≥ 3, as we henceforth assume. In this situation, we apply a transformation to the given system that we now introduce.

Let τ be a non-negative integer, and write τ = uk + with 0 ≤ ≤ k -1 and u ∈ Z. Then define the new forms (9.4)

A τ = A(x 1 , x 2 , p u+1 y 0 , . . . , p u+1 y , p u y +1 , . . . , p u y k-1 ) B τ = B(x 1 , x 2 , p u+1 y 0 , . . . , p u+1 y , p u y +1 , . . . , p u y k-1 ).

Hence the systems A τ = B τ = 0 are all equivalent with the given system, so that it suffices to find a non-trivial p-adic solution of one of them. With applications in mind, we write A τ and B τ with coefficients as

A τ (x) = k 2 +2 i=1 a (τ ) i x k i , B τ (x) = k 2 +2 i=1 b (τ ) i x i ,
and then introduce the numbers ν

(τ ) i , µ (τ ) i for i ≥ 3 via p ν (τ ) i a (τ ) i , p µ (τ ) i b (τ )
i . By (9.4), one has (9.5) ν

(τ ) i = ν i + k(u + 1), µ (τ ) i = µ i + u + 1 (3 ≤ i ≤ k + k + 2) ν (τ ) i = ν i + ku, µ (τ ) i = µ i + u (i ≥ k + k + 3).
In particular, it follows that ν

(τ ) 3 > µ (τ ) 3
holds for all large τ . Therefore, there is a well-defined smallest number t among those τ for which there exists an index i ≥ 3 with ν

(τ ) i ≥ µ (τ ) i .
There is a curious dichotomy in the argument at this point. We first consider the case t > θ -k. Let θ = υk + r, with 0 ≤ r < k. By the definition of t, we have ν

(θ-k) i < µ (θ-k) i
for all i. However, by (9.5), when x i belongs to y r (that is kr

+ 3 ≤ i ≤ kr + k + 2), one has ν i = r and ν (θ-k) i = ν i + υk = r + υk = θ, µ (θ-k) i = µ i + υ.
It follows that µ i + υ > θ for all i with x i in y r . Hence, by Lemma 8.6, the system A = B = 0 has a non-trivial p-adic solution.

It remains to consider the case where t ≤ θ -k. We put t = u k + . There is at least one index i with µ

(t) i ≤ ν (t)
i , and thanks to the minimality of t, the variable x i must belong to y . This follows from (9.5). Further, this argument also shows that all indices i with µ

(t) i ≤ ν (t) i belong to y , that is k + 3 ≤ i ≤ k + k + 2,
and we can define

β = min{µ (t) i : µ (t) i ≤ ν (t) i } = min{µ (t) i : k + 3 ≤ i ≤ k + k + 2}.
Note that in this interval for i we have ν

(t) i = +ku +k = t+k so that β ≤ t+k ≤ θ. First suppose that µ (t) i < ν (t)
i holds for at least one i, which is the case β < t + k. Then β < θ. Choose an i with µ

(t) i = β and k + 3 ≤ i ≤ k + k + 2.
By the minimality of t, we have µ

(t-1) i ≥ ν (t-1) i
. However, by (9.5),

ν (t) i = ν (t-1) i + k, µ (t) i = µ (t-1) i + 1 so that ν (t) i -k ≤ µ (t) i -1, which implies that t + k -β ≤ k -1. Put β = u k + .
Recalling that β < t + k in the case under consideration, we see that and are distinct. We now consider the system A t = B t = 0 in the variables x 1 , x 2 , y and x i , and put all other variables to 0. Then, by (9.5) we see that the system reduces to a pair of equations (8.2) if we put z = x i and y = (y 1 , . . . , y k ). Since β < θ, the conditions of Lemma 8.2 are all met, and that lemma provides the desired non-trivial p-adic solution.

Hence we are now reduced to the case β = t + k where one has ν

(t) i ≤ µ (t)
i for all x i in y , with equality for at least one i. Then, we again consider A t = B t = 0, this time in the variables x 1 , x 2 , y = (y 1 , . . . , y k ), with all other variables set to 0. The reduced system takes the shape (8.4), and when β = t + k < θ holds, all conditions in Lemma 8.3 are met. This lemma then supplies a non-trivial p-adic solution of A t = B t = 0. This leaves the case β = θ for consideration where we have to solve (8.4) with β = θ, subject to the conditions in Lemma 8.3. By Lemma 8.7, this system always has a non-trivial p-adic solution. The proof of Lemma 9.1 is complete.

Further preparations

With the case k = p -1 now settled to our satisfaction, we may concentrate on degrees of the form k = p τ (p -1) with τ ≥ 1. We wish to construct, via Lemma 4.2, a p-adic solution of a conditioned system A(x) = B(x) = 0 given by (4.13), and hence seek for a non-singular solution of the pair of congruences (10.1)

υ j=1 a j x k j ≡ 0 mod p γ , υ j=1 b j x j ≡ 0 mod p in which υ = υ 0 + υ 1 + • • • + υ γ-1 .
There is then a dichotomy in the argument; conditioned systems fall into two classes that call for separate treatment. Thus, we refer to a conditioned system as having type A when p | b i for all i > υ 0 , and to the remaining systems as having type B. Note that the discriminating property is whether or not the variables at level 0 are exactly those indexed by 1 ≤ j ≤ υ 0 .

Lemma 10.1. (a) A solution of the congruences (10.1) associated with a system of type A is non-singular whenever there is a pair i, j with 1 ≤ i, j ≤ υ 0 and p x j , p | x i , p b i . (b) A solution of the congruence (10.1) associated with a system of type B is nonsingular whenever there is a number j with 1 ≤ j ≤ υ 0 and p x j .

Proof. Consider the Jacobian matrix for the system (4.13). Its minor with respect to columns indexed by i, j is

ka i x k-1 i ka j x k-1 j b i b j .
In case (a), we take the distinguished indices i, j. In case (b), we choose i such that x i is low at level 0. The lemma is now immediate.

In the next two sections we dispose of the case where

(10.2) k = p(p -1), p odd.
Here, the pivotal step is encapsulated in the next lemma. It can be thought of as a version of Lemma 5.6 when the modulus is p 2 .

Lemma 10.2. Suppose that k is given by (10.2). Let 1 ≤ t ≤ u and u ≥ p 2 + 2. Further, let c 1 , . . . , c u , d 1 , . . . , d t denote integers not divisible by p. Then the pair of congruences

(10.3) c 1 x k 1 + • • • + c u x k u ≡ 0 mod p 2 , d 1 x 1 + • • • + d t x t ≡ 0 mod p has a non-singular solution in integers x 1 , . . . , x u .
Proof. When t = 1 or 2, apply Lemma 5.2 with q = p 2 to find a non-empty set J ⊂ {3, . . . , p 2 + 2} with j∈J c j ≡ 0 mod p 2 .

Then put x j = 1 for j ∈ J and x i = 0 for 1 ≤ i ≤ u, i ∈ J. This is a solution of (10.3), and for j ∈ J one finds that (10.4) det

c 1 x k-1 1 c j x k-1 j d 1 d j = -d 1 c j x k-1 j
is not divisible by p. Hence, this solution of (10.3) is non-singular.

We may now suppose that t ≥ 3. Then, by Lemma 5.5, we can rearrange indices 1, 2, 3 to ensure that p c 2 + c 3 . Then again by Lemma 5.2, there is a set I ⊂ {4, . . . , p 2 + 2} with

i∈I c i ≡ -c 2 -c 3 mod p 2 . Let D = - i∈I i≤t d i .
Now choose integers x 2 , x 3 with d 2 x 2 + d 3 x 3 ≡ D mod p and p x 2 x 3 . It is immediate that there are at least p -2 (and hence at least one) such pairs with 1 ≤ x i ≤ p -1. Then, choosing x i = 1 for i ∈ I and x l = 0 for l = 1 and 4 ≤ l ≤ u with l ∈ I, we have a solution of (10.3) and can use (10.4) with j = 3 to confirm that the solution is non-singular.

The case k = p(p -1): type A

In this section, we discuss systems of type A when k = p(p -1), p an odd prime, and s ≥ k 2 + 2. We shall show that in this situation, the congruences (10.1) have a non-singular solution. With this end in view, we take x j = 0 for all j > υ 0 + υ 1 and then recall that type A system have p | b j for all j > υ 0 . It will be convenient to put y j = x υ0+j and c j = a υ0+j /p for 1 ≤ j ≤ υ 1 . In this notation, the congruences (10.1) read (11.1)

a 1 x k 1 + • • • + a υ0 x k υ0 +p c 1 y k 1 + • • • + c υ1 y k υ1 ≡ 0 mod p 2 , b 1 x 1 + • • • + b υ0 x υ0 ≡ 0 mod p.
Since this pair of congruences is associated with a system of type A at least one of b j with 1 ≤ j ≤ υ 0 is not divisible by p. We may then suppose that p b 1 , say. Finally, since the system is conditioned, we have the inequalities (11.2)

υ 0 ≥ k + 1, υ 0 + υ 1 ≥ 2k + 1.
If υ 0 ≥ p 2 + 2, then Lemma 10.2 delivers a non-singular solution of (11.1) with y 1 = • • • = y υ1 = 0. Hence, from now on, we may suppose that υ 0 ≤ p 2 + 1. Then, by (11.2), (11.3)

υ 1 ≥ 2k -p 2 = p 2 -2p.
We take x 1 = 0, and note that υ 0 -1 ≥ k ≥ p + 3 for p ≥ 3. Hence, when p ≥ 5 and not all of b 2 , . . . , b υ0 are divisible by p, Lemma 5.8 yields numbers x 2 , . . . , x υ0 , not all divisible by p, with (11.4)

a 2 x k 2 + • • • + a υ0 x k υ0 ≡ 0 mod p, b 2 x 2 + • • • + b υ0 x υ0 ≡ 0 mod p.
When p = 3, then υ 0 ≥ 7, and a theorem of Olson [23, (1)] supplies a non-empty subset J ⊂ {2, . . . , υ 0 } with j∈J a j ≡ j∈J b j ≡ 0 mod p.

Again, this gives a solution of (11.4), with x j = 1 for j ∈ J, and x j = 0 for the remaining j. Finally, when all b j are divisible by p, then a non-trivial solution of (11.4) is provided by Lemma 5.3. We have now shown that for all p ≥ 3, the congruences (11.4) have a non-trivial solution, and with one such solution x 2 , . . . , x υ0 fixed, we define the integer c through the equation (11.5)

a 2 x k 2 + • • • + a υ0 x k υ0 = cp.
In this notation, the pair of congruences (11.1) reduces to the single congruence

c + c 1 y k 1 + • • • + c υ1 y k υ1 ≡ 0 mod p. By (11.
3), we have υ 1 ≥ p, and hence, by Lemma 5.3, this congruence has a solution whenever p c, while in the case where p | c, we may take

y 1 = • • • = y υ1 = 0.
We have now found a solution of the congruences (11.1) with x 1 = 0 and p x j for some j ∈ {2, . . . , υ 0 }. In view of Lemma 10.1, it follows that all conditioned systems of type A and degree p(p -1) have a non-trivial p-adic solution.

12. The case k = p(p -1): type B

In this section we complete the discussion of the case k = p(p -1) by considering systems of type B. As in the previous section, we take x j = 0 for all j > υ 0 + υ 1 , define c j and y j as in Section 11 and also put d j = b j+υ0 (1 ≤ j ≤ υ 1 ). Then the congruences (10.1) reduce to (12.1)

a 1 x k 1 + • • • + a υ0 x k υ0 +p c 1 y k 1 + • • • + c υ1 y k υ1 ≡ 0 mod p 2 , b 1 x 1 + • • • + b υ0 x υ0 + d 1 y 1 + • • • + d υ1 y υ1 ≡ 0 mod p.
We shall show that this pair has a solution with one of x 1 , . . . , x υ0 not divisible by p. This is then also a solution of (10.1) with this property, and from Lemma 10.1 (b), we may then conclude that systems of this type have non-trivial solutions in Q p . Our method of solving (12.1) follows the pattern of Section 11 as close as is possible. Thus, when υ 0 ≥ p 2 + 2, Lemma 10.2 yields a non-trivial solution of (12.1) with y 1 = • • • = y υ1 = 0 provided that the b j are not all divisible by p. In the contrary case where all b j are divisible by p, we find a non-trivial solution of

a 1 x k 1 + • • • + a υ0
x k υ0 ≡ 0 mod p 2 from Lemma 5.2 with q = p 2 , and again we may take

y 1 = • • • = y υ1 = 0.
Hence, we are again reduced to the case υ 0 ≤ p 2 + 1, and we may then suppose that (11.2) and (11.3) hold. We now deal with this situation in an ad hoc manner when p ≥ 5, and only later refine the argument when p = 3. We begin as with systems of type A and choose a non-trivial solution of (11.4) and insert this into (12.1). Then, for a suitable c ∈ Z, the congruences (12.1) reduce to the pair

(12.2) c + c 1 y k 1 + • • • + c υ1 y k υ1 ≡ 0 mod p, d 1 y 1 + • • • + d υ1 y υ1 ≡ 0 mod p.
At this point, the treatment of systems of type A was simpler because then one would have p | d j for all 1 ≤ j ≤ υ 1 , in which case the linear congruence in (12.2) is automatically satisfied. We therefore proceed to remove the linear congruence by a contraction method similar to the one used in Section 3.

By symmetry, we may suppose that p d j for 1 ≤ j ≤ r, and p | d j for r < j ≤ υ 1 ; here 0 ≤ r ≤ υ 1 is chosen appropriately. If r = 1 or 2, we take y 1 = y 2 = 0 and want to solve c + c 3 y k 3 + • • • + c υ1 y k υ1 ≡ 0 mod p by Lemma 5.3. For this to be applicable we require that υ 1 -2 ≥ p-1 and p c. When p | c, take y 3 = • • • = y υ1 = 0. Hence, in view of (11.3), there is always a solution of c + c 3 y k 3 + • • • + c υ1 y k υ1 ≡ 0 mod p, and hence of (12.2), even when p = 3.

It remains to consider the situation where r ≥ 3. Then, by Lemma 5.5, we can rearrange indices 1, . . . , r such that p c 2i-1 + c 2i for 1 ≤ i ≤ (r -1)/2. Then choose y 2i-1 = d 2i z i , y 2i = -d 2i-1 z i , with z i ∈ Z at our disposal. When r is odd, we put y r = 0 and when r is even, we put y r-1 = y r = 0. The system (12.2) then reduces to the single congruence

(12.3) c + 1≤i≤(r-1)/2 (c 2i-1 + c 2i )z k i + r<j≤υ1 c j y k j ≡ 0 mod p.
The coefficients in this congruence are all not divisible by p. Further we may suppose that p c because in the case where p | c, a solution is provided by z i = y j = 0. By Lemma 5.3, there is a solution of (12.3) provided that the congruence involves at least p -1 variables. However, the number of variables in (12.3)

is υ 1 -r + r-1
2 , and r ≤ υ 1 . In particular, we see at least 1 2 (υ 1 -1) variables when r is odd, and at least υ1 2 -1 variables when r is even. By (11.3), we have

1 2 (υ 1 -1) ≥ υ 1 2 -1 ≥ 1 2 p 2 -p -1,
and since p is odd, we conclude that (12.3) contains at least (12.4) (12.3) has a solution. This solutions traces back to a solution of (12.2), and to a solution of (12.1) with one at least of x 1 , . . . , x υ0 not divisible by p, as required.

1 2 (p 2 -1) -p ≥ p -1 (p ≥ 5) variables, hence
When p = 3, the inequality (12.4) fails. Nonetheless, we can still apply the above argument whenever (12.3) contains at least 2 = p -1 variables, and when υ 1 ≥ 5, this is always the case. When υ 1 = 4, and r ≤ 3, we still have υ 1 -r + r-1 2 ≥ 2 variables. When υ 1 = 3, the cases r = 1 = 2 have been successfully dismissed in the initial phase of this discussion.

Recalling that we always have υ 1 ≥ 3 (from (11.3)), we infer that even when p = 3, we find a solution of (12.3), and hence of (12.1) with one at least of x 1 , . . . , x υ0 not divisible by 3, except when υ 1 = r is 3 or 4. Hence it now remains to consider the congruences (12.1) with k = 6, υ 1 = 3 or 4, p d 1 d 2 . . . d υ1 and υ 0 ≥ 13 -υ 1 . In these exceptional cases, there is again a solution of (12.1) with some x j not divisible by 3. This is a consequence of the following stronger lemma.

a i c j d l (1 ≤ i ≤ 9, 1 ≤ j ≤ 3, 1 ≤ l ≤ 3).
Then, there are integers x i , y j with (12.5)

a 1 x 6 1 + • • • + a 9 x 6 9 + 3(c 1 y 6 1 + c 2 y 6 2 + c 3 y 6 3 ) ≡ 0 mod 9, b 1 x 1 + • • • + b 9 x 9 + d 1 y 1 + d 2 y 2 + d 3 y 3 ≡ 0 mod 3,
and not all of x 1 , . . . , x 9 divisible by 3.

Note that once this is established, we have proved that the congruences (12.1) always have a solution with not all x i divisible by p. Hence, the discussion of type B systems will be complete, and when combined with the results of the previous section, this will also complete the proof of the theorem in the case k = p(p -1), p ≥ 3.

We now prove Lemma 12.1. First suppose that c 1 ≡ c 2 ≡ c 3 mod 3. Then, if we also have d 1 ≡ d 2 ≡ d 3 mod 3, we take y 1 = y 2 = -y 3 = z, with the integer z still at our disposal. If d 1 ≡ d 2 ≡ d 3 mod 3 does not hold, then we can arrange indices and suppose that d 1 ≡ d 2 ≡ -d 3 mod 3, and we take y 1 = y 2 = y 3 = z. The congruences (12.5) then reduce to (12.6)

a 1 x 6 1 + • • • + a 9 x 6 9 ≡ 0 mod 9, b 1 x 1 + • • • + b 9 x 9 +d 1 z ≡ 0 mod 3.
Similarly, when not all of c j lie in the same residue class mod 3, we may suppose that c 1 ≡ c 2 ≡ -c 3 mod 3. If d 1 ≡ d 3 mod 3, we take y 1 = y 3 = z, y 2 = 0 and insert in (12.5). We again reduce to (12.6), this time with 2d 1 in place of d 1 .

By symmetry, the same reduction is possible when d 2 ≡ d 3 mod 3. This leaves the case where d 1 ≡ d 2 ≡ -d 3 mod 3. But then we take y 1 = -y 3 = z, y 2 = 0, and argue as before.

Thus it remains to solve (12.6). By Lemma 5.2, there are integers x 1 , . . . , x 9 , not all divisible by 3, that solve the sextic congruence in (12.6). With x 1 , . . . , x 9 now chosen, the linear congruence fixes z. It is worth noting that we needed (12.6) with d 1 and 2d 1 in place of d 1 , both not divisible by 3.

This completes the discussion of the case k = p(p -1).

Powers of 2: introductory comment

We now turn to our final task and establish the theorem when

(13.1) k = 2 τ , τ ≥ 2, p = 2.
This will require several new ideas. Most importantly, we will have to rework our basic winning strategy, at least when k = 4. Thus far, we have followed a traditional path in attacking problems of the type considered in this paper. We began with a conditioned system and then showed that the associated congruences (4.14) possess a solution suitable for an application of Lemma 4.2 and Lemma 10.1. However, when k = 4, the strategy necessarily fails for certain systems. Consider the pair of equations in 18 = k 2 + 2 variables given by (13.2)

x 4 1 + • • • + x 4 15 + 8(y 4 1 + y 4 2 + y 4
3 ) = y 1 + y 2 + y 3 = 0. Although this system is certainly not conditioned, one may replace all its zero coefficients by 2 l , with l ≥ 4. This yields a family of conditioned systems of type B, with υ 0 = 15 and υ 3 = 3. Whatever the actual value of l may be, the associated congruences (10.1) are (13.3)

x 4 1 + • • • + x 4 15 + 8(y 4 1 + y 4 2 + y 4 3 ) ≡ 0 mod 16, y 1 + y 2 + y 3 ≡ 0 mod 2.
Here, the second congruence forces one or three of y 1 , y 2 , y 3 to be even, and in both cases it follows first that 8(y 4 1 + y 4 2 + y 4 3 ) ≡ 0 mod 16, and then that all x j must be even. In particular, the pair (13.3) does not have non-singular solutions. We will therefore have to develop a method that detects such seemingly hopeless examples, and then we still need to find 2-adic solutions in such cases.

Our main tool in this section is a contraction method. The basic ideas go back to Davenport and Lewis [START_REF] Davenport | Homogeneous additive equations[END_REF][START_REF] Davenport | Two additive equations[END_REF], as developed by Brüdern and Godinho [START_REF] Brüdern | On Artin's conjecture. II. Pairs of additive forms[END_REF]. We require a highly refined version of the methods in [START_REF] Brüdern | On Artin's conjecture. II. Pairs of additive forms[END_REF], but only in a 2-adic context.

We now explain in detail our contraction method, and we also develop a language capable of describing contractions in terms of a simple formalism. Again, this follows [START_REF] Davenport | Homogeneous additive equations[END_REF] in spirit, but considerable refinement will be required.

Let s ≥ 2, and suppose that a system A(x) = B(x) = 0 is given by (4.13). With an application of Lemma 10.1 in mind, we associate with (4.13) the pair of congruences (13.4)

s j=1 a j x k j ≡ 0 mod 2 τ +2 , s j=1 b j x j ≡ 0 mod 2.
A contraction of a given system A = B = 0 is a partition C 1 , C 2 , . . . , C t , Z of {1, . . . , s} with C j = ∅ for 1 ≤ j ≤ t. For new variables y 1 , . . . , y t , we then take x i = y j for all i ∈ C j , x i = 0 for all i ∈ Z and substitute accordingly in A(x) = B(x) = 0. We then obtain a new system, say A (y) = B (y) = 0, with (13.5)

A (y) = t j=1 c j y k j , B (y) = t j=1 d j y j ,
say. We refer to the system A = B = 0 as the system contracted from A = B = 0 relative to the partition C 1 , C 2 , . . . , C t , Z . We may take t = s, Z = ∅ and C j = {j} to see that A = B = 0 is contracted from itself. Further, if one contracts A = B = 0 to A = B = 0, say, then the new system A = B = 0 is also contracted from A = B = 0. We now focus on preconditioned systems A = B = 0 in s = k 2 + 2 variables, with k = 2 τ as before. If the system A = B = 0 in variables y 1 , . . . , y t is contracted from A = B = 0, and the contracted system is given by (13.5), we refer to the ν j defined by 2 νj c j as the niveau of the variable y j . We define the parity of y j as even when 2 | d j , and as odd when 2 d j .

Because a preconditioned system given by (4.13) is contracted from itself, niveau and parity of its variables are defined. In particular, its variables of niveau 0 are precisely those indexed by i, where 2 a i . For convenience, suppose that this is the set {1, . . . , υ 0 }.

If A = B = 0 is contracted from A = B = 0 relative to C 1 , C 2 , .
. . , C t , Z , then we refer to a variable y j in (13.5) as primary when C j ∩ {1, . . . , υ 0 } is non-empty. Variables that are not primary are secondary. The relevance of primary variables is illustrated by the following simple observation. Lemma 13.1. Let s ≥ k 2 + 2, k = 2 τ with τ ≥ 2, and let A = B = 0 be a preconditioned system given by (4.13). If a system A = B = 0 is contracted from A = B = 0 and contains a primary even variable at niveau τ + 2, then the congruences (10.1) (with p = 2) have a solution where one of the integers a i x i with 1 ≤ i ≤ υ 0 is odd. If, moreover, the contraction is relative to C 1 , C 2 , . . . , C t , Z and the set Z contains an index belonging to an odd variable, then the congruences (10.1) have a non-singular solution.

Proof. If y is the contracted primary even variable at niveau τ + 2, we take y = 1 and y j = 0 for all other variables in A = B = 0. Tracing this back to A(x), B(x), we obtain a solution of (10.1) (with p = 2), with all x i ∈ {0, 1}, and a l x l odd for at least one l ∈ {1, . . . , υ 0 }. When j ∈ Z belongs to an odd variable, the choice x j = 0 is forced, and the matrix

a j x k-1 j a l x k-1 l b j b l has determinant -b j a l ≡ 1 mod 2.
Hence, the solution of (10.1) is non-singular.

Later we shall construct the desired primary variable at niveau τ + 2 by nested contraction. The following conventions will help to describe the contraction process in an efficient manner. A secondary variable in a contracted system at niveau ν will be denoted S ν . If its parity is known, we write S ν,e when the variable is even, and S ν,o when it is odd. A primary variable will be denoted as P ν when its niveau is not lower that ν, and we write P ν,e , P ν,o when the parity is even, resp. odd. If the variable P ν is at exact niveau ν, then we signal this by writing P ν .

We are ready to describe the simplest contractions that we shall regularly apply. Given two variables P ν,e , these may be contracted to P ν+1,e . To see this, first consider the case where both variables are P ν,e . If the variables are x, y, and they occur in the system with terms ax k , bx, and a y k , b y, say, then the contraction z = x = y transfers this to (a + a )z k , (b + b )z. But b, b are even integers, and so is b + b . Further, 2 ν a, 2 ν a , and hence 2 ν+1 | a + a , as required. If one of the two P ν is already a variable of type P ν+1 , then we put the other variable to 0. This confirms the claim. This contraction process we abbreviate as (13.6) 2P ν,e → P ν+1,e .

Note that the same argument shows that a P ν,e and an S ν,e can be contracted to P ν+1,e , and we write this as (13.7) P ν,e , S ν,e → P ν+1,e .

More generally, if A is a set of variables in a contracted system, and there is a contraction to a set of variables B, then we denote this by A → B. For example, if a conditioned system with s = k 2 + 2 variables is given, then in the notation of Section 6 it contains υ 0 variables P 0 , and υ j variables S j (1 ≤ j ≤ k -1). In order to apply Lemma 13.1, we wish to show that (13.8)

υ 0 P 0 , υ 1 S 1 , . . . υ τ +1 S τ +1 → P τ +2,e .
In later sections we shall provide conditions under which (13.8) is indeed true. We now turn to the contraction of secondary variables, and begin by showing that (13.9) 3S ν,e → S ν+1,e , S ν,e ; 3S ν,o → S ν+1,e , S ν,o .

To see this, let π ∈ {e, o}, and suppose that x, y are two variables S ν,π . These will occur in the associated system with terms 2 ν ax k , bx and 2 ν a y k , b y. Here a, a are ≡ 1 mod 2 and b ≡ b mod 2. If a ≡ a mod 4, we contract the variables via x = y = z, and the contraction involves the terms 2 ν (a + a )z k , (b + b )z. But 2 a + a , so that z is an S ν+1,e . If three S ν,π are given, and they occur with 2 ν a j x k j in the corresponding system then the a j are ≡ 1 mod 2, and we can find two a j that are in the same residue class modulo 4. These contract to S ν+1,e , leaving one S ν,π unused.

One may repeatedly apply (13.9) to confirm that for n ∈ N and π ∈ {e, o} one has (13.10) (2n + 1)S ν,π → nS ν+1,e , S ν,π .

Finally, there is a parity-correcting contraction. For ν < µ, one obviously has

(13.11) S ν,o , S µ,o → S ν,e .
Similarly, for j ≥ 1, one has (13.12) P 0,e , P 0,o , S j,o → P 1,e .

Contraction principles

In this section, we elaborate on the simple examples of contractions presented in the previous section. This will reduce the complexity of the main argument that we present in sections 15 and 16 below. Lemma 14.1. Let l ≥ 1, and suppose that for some ν ≥ 1, a collection of 2 l variables of type P ν,e and S ν,e is given, with at least one of these primary. Then these variables may be contracted to one P ν+l,e .

Proof. Let n, m be non-negative integers with n + m = 2 l and n ≥ 1. The lemma asserts that (14.1) nP ν,e , mS ν,e → P ν+l,e .

We prove this by induction on l. For l = 1, the two possible cases n = 1 and n = 2 are (13.6) and (13.7). Now suppose that l > 1, and that n + m = 2 l with n ≥ 1. If m = 0, we can apply (13.6) repeatedly to confirm (14.1) via 2 l P ν,e → 2 l-1 P ν+1,e , and then apply the induction hypothesis that 2 l-1 of P ν+1,e will contract to P ν+l,e . If m ≥ 2 is even, we infer from (13.10) that mS ν,e → m 2 -1 S ν+1,e , 2S ν,e , and from m+n = 2 l we see that n is even, n ≥ 2. Hence, we can use (13.7) twice to conclude 2P ν,e , mS ν,e → 2P ν+1,e , 1 2 (m -2)S ν+1,e . Then, since n -2 is even, one may apply (13.6) repeatedly to see that (n -2)P ν,e → ( n 2 -1)P ν+1,e . When combined with the last display, we have shown that

(14.2) nP ν,e , mS ν,e → ( n 2 + 1)P ν+1,e , ( m 2 -1)S ν+1,e ,
and the desired conclusion (14.1) follows by applying the case l -1 of Lemma 14.1 to the right hand side of (14.2). When m is odd, we first apply (13.10) and then (13.7) to confirm that P ν,e , mS ν,e → P ν,e , S ν,e , 1 2 (m -1)S ν+1,e → P ν+1,e , 1 2 (m -1)S ν+1,e . This leaves n-1 variables P ν,e untouched, and since n is odd, repeated use of (13.6) yields (n -1)P ν,e → 1 2 (n -1)P ν+1,e . This shows nP ν,e , mS ν,e → 1 2 (n + 1)P ν+1,e , 1 2 (m -1)S ν+1,e . Again, appeal to the induction hypothesis completes the proof. Lemma 14.2. Let l ≥ 0, and suppose that 2 l+1 variables of type P ν,e , S ν,e , . . . , S ν+l,e are given, with at least 2 l of these of type P ν,e . Then a subset of these variables contract to one P ν+l+1,e .

Proof. Again, we induct on l. The case l = 0 is covered by Lemma 14.1. When l ≥ 1, we consider two cases. First suppose that the list of given variables contain an S ν+l,e . In this case, we choose 2 l P ν,e and apply Lemma 14.1, asserting 2 l P ν,e → P ν+l,e . Then by (13.7), the contraction P ν+l,e , S ν+l,e → P ν+l+1,e completes the proof in this case.

If there is no S ν+l,e among the variables, we can split the given variables into two disjoint sets of 2 l variables each, both containing at least 2 l-1 P ν,e . By induction hypothesis, the variables in each of the two sets contract to a P ν+l,e , so that we have 2P ν+l,e . Reference to (13.6) completes the induction.

We now develop the contraction principles announced in Lemmas 14.1 and 14.2 further, to include situations where the secondary variables may be odd. We shall be successful only under more restrictive hypotheses. Lemma 14.3. Let l ≥ 1, and suppose that for some ν ≥ 1, a collection of 2 l + 2 variables of types P ν,e , S ν,e and S ν,o is given, at least two of which are primary. Then, a subset of at most 2 l of these variables contract to one P ν+l,e .

Proof. The case l = 1 is covered by (13.6). Suppose then that l ≥ 2, and that 2 l + 2 = u + n + m where u is the number of P ν,e and where n and m is the number of S ν,e , S ν,o respectively. We apply (13.10) whenever n, m are at least 2, producing

n-1 2 + m-1 2
variables S ν+1,e , and leaving either one or two of S ν,e , S ν,o unused, depending on the parities of n and m. For those variables S ν,e that remained, we apply (13.7), P ν,e , S ν,e → P ν+1,e , and then contract remaining variables P ν,e , if any, in pairs via (13.6) to P ν+1,e . In this way, we will have at least one P ν+1,e (because if one S ν,e remained unused, the contraction P ν,e , S ν,e → P ν+1,e provided one, and otherwise P ν,e , P ν,e → P ν+1,e is applied at least once).

We now count how many variables remain unused at niveau ν. If there are two of S ν,o remaining, then by (13.10), m must be even, and hence 2 | u + n, and all variables P ν,e , S ν,e will have been contracted in pairs to niveau ν + 1. If there is only one S ν,o remaining, then m was odd, and so is u + n. But then, the P ν,e , S ν,e contract in pairs until one variable remains. Hence, in both cases, two variables will remain at niveau ν, while at niveau ν + 1 we have 2 l-1 variables of types P ν+1,e , S ν+1,e , one of which is primary. We may now apply Lemma 14.1 to complete the proof.

We now turn to an analogue of Lemma 14.2 in which the secondary variables may have both parities. To realise this, we require two additional variables, a phenomenon already familiar from a comparison of Lemmas 14.1 and 14.3. A more restrictive novelty is that the secondary variables are no longer allowed to invade niveau ν + l. In practice, this limits applicability to the range k ≥ 16. Lemma 14.4. Let l ≥ 1, and suppose that 2 l+1 + 2 variables of types P ν,e , S ν , . . . , S ν+l-1 are given, with at least 2 l of these primary. Then, a subset of these variables contract to one P ν+l+1,e .

Proof. The case l = 1 is the case l = 2 of Lemma 14.3, so that we may suppose that l ≥ 2.

The strategy is to contract odd variables to even ones at higher level, and then apply Lemma 14.2. For ν ≤ j ≤ ν + l -1, let m j denote the number of S j,o given, and let m = m ν + • • • + m ν+l-1 be the number of all odd variables. Further, let n be the number of all even variables given, including the primary ones. Then (14.3) m + n = 2 l+1 + 2.

We also write n ν for the number of even variables S ν,e and P ν,e . We begin by contracting S j,o in pairs to S j+1,e . For 0 ≤ m j ≤ 2, let r j = m j , and for m j ≥ 3, let r j ∈ {1, 2} be defined by m j ≡ r j mod 2. Then by (13.10), the available S j,o indeed contract in disjoint pairs to S j+1,e , leaving r j of S j,o unused in this process. Note that the new variables are all at niveau between ν + 1 and ν + l.

For r = 1 or 2, let

J r = {ν < j ≤ ν + l -1 : r j = r}.
Consider the situation where #J 2 ≥ 2. Then we choose a pair j 1 , j 2 ∈ J 2 with j 1 < j 2 , and apply (13.11) twice to generate 2S j1,e from the so far unused 2S j1,o , 2S j2,o . This process can be repeated until either all S j,o with j ∈ J 2 have contracted in disjoint pairs to even secondary variables at niveau between ν + 1 and ν + l -1, or this applies to all j ∈ J 2 , j = j 0 , for some specific j 0 ∈ J 2 , and 2S j0,o remain untouched. Consistent with these operations, we do not apply any contractions when #J 2 ≤ 1. Now examine the situation when #J 1 ≥ 2. Should J 2 have left 2S j0,o , then choose j 1 = j 2 ∈ J 1 , and first apply the contractions

S ji,o , S j0,o → S j i ,e (i = 1, 2)
where j i = min(j 0 , j i ), and where it is useful to note that j i = j 0 (i = 1, 2) thanks to the construction of J 1 , J 2 . This removes two elements j 1 , j 2 from J 1 , and as long as there are two elements j 3 < j 4 left in J 1 , we contract these via S j3,o , S j4,o → S j3,e . This last process we also apply in the case where the variables collected by J 2 have contracted completely. These contractions either contract all remaining odd variables, or there is exactly one S j,o , with some j ∈ J 1 , that remains uncontracted. If, however, J 1 = {j 1 }, then in the case where the process applied to J 2 left 2S j0,o unused, we apply (13.11) to yield an S j,e , leaving one S j0,o untouched. If #J 1 = 0, no further contractions are applied.

We have now completed our contractions from odd to even secondary variables. The variables have been contracted in disjoint pairs, and the new even variables are all at niveau between ν + 1 and ν + l. Furthermore, at most two variables S ν,o and at most two variables S j,o for exactly one value of j ∈ {ν + 1, . . . , ν + l -1} have not been involved in a contraction.

Let κ be the number of these exceptions, so that 0 ≤ κ ≤ 4. Further, since all contractions are in pairs, we have m ≡ κ mod 2, and the number of even variables that we have generated at niveaux ν + 1, . . . , ν + l equals (m -κ)/2. In addition, there are already n -n ν even original seed variables at these niveaux.

In the special case κ = 4, we contract the remaining odd variables in two pairs via S ν,o , S j,o → S ν,e (recall that j > ν) to 2S ν,e , adding two variables to those counted by n ν . We therefore put n ν (κ) = n ν for κ ≤ 3 but n ν (4) = n ν + 2.

We now contract the even variables at niveau ν, of which there are now n ν (κ), including at least 2 l primary ones. Here we begin by (13.10) and contract available S ν,e in pairs to S ν+1,e until there are at most two S ν,e left uncontracted. For these, we choose the same number of P ν,e (which is possible since l ≥ 2), and apply (13.7) to generate P ν+1,e . There are then only P ν,e left, and these can be contracted via (13.6) until at most one P ν,e is left aside. It transpires that this generates [n ν (κ)/2] new variables at niveau ν + 1, including at least 2 l-1 primary ones. On collecting together, at niveaux ν + 1, . . . , ν + l, we now have a total of T variables, where

T = [n ν (κ)/2] + (n -n ν ) + (m -κ)/2.
We show that for κ = 3 one has T ≥ 2 l . To see this, note that

T ≥ 1 2 n ν (κ) + m -κ -1 2
+ n -n ν , this lower bound being valid for all values of κ. When κ ≤ 3, we infer that (14.4)

T ≥ 1 2 (n + m) + 1 2 (n -n ν ) -1 2 (κ + 1) = 2 l + 1 2 (1 + n -n ν -κ). When κ ≤ 2, then from n -n ν ≥ 0 we see that 1 + n -n ν -κ ≥ -1, and hence, T ≥ 2 l -1 2 .
Since T is an integer, we conclude that T ≥ 2 l , as we claimed. When κ = 4, use n ν (4) = n ν + 2, and proceed as before to again conclude that T ≥ 2 l . This leaves the case κ = 3. Then, (14.4) yields T ≥ 2 l -1 + 1 2 (n -n ν ), and hence, whenever n > n ν ,we also conclude that T ≥ 2 l . In the exceptional situation where n = n ν , we deduce from (14.3) that n ν ≡ m ≡ κ mod 2, so that n ν is odd. In this case, the contraction of the variables at niveau ν will leave one P ν,e untouched, and since κ = 3, there is one S ν,o and one S j,o (for some j > ν) remaining as well. Hence, the contraction P ν,e , S ν,o , S j,o → P ν+1,e yields an extra variable at niveau ν + 1. But T = 2 l -1 in the current situation, and we again have 2 l variables in total.

We have now proved that the seed variables contract to 2 l even variables at niveaux scattered through ν + 2, . . . , ν + l, including 2 l-1 primary variables. Also, l ≥ 2 implies that we may apply Lemma 14.2 with ν + 1 in place of ν, and l -1 in place of l. This yields one P ν+l+1,e , as required.

Powers of 2 : systems of type A

The sole purpose of this section is to establish the following result.

Lemma 15.1. Let k = 2 τ with k ≥ 4, and let s = k 2 + 2. Let A = B = 0 be a conditioned system of type A, given by (4.13). Then, the associated congruences (13.4) have a non-singular solution.

Once this is established, it follows via Lemma 4.2 that systems satisfying the hypotheses of Lemma 15.1 have non-trivial 2-adic solutions.

We approach the claim in Lemma 15.1 through the second clause in Lemma 13.1. Because the system is of type A, one of the variables x 1 , x 2 , . . . , x υ0 must be odd, and by symmetry we may suppose that x 1 is odd. Put x 1 = 0. According to Lemma 13.1, it now suffices to show that the variables indexed by 2 ≤ j ≤ υ 0 +υ 1 +• • •+υ τ +1 contract to one P τ +2,e . Thus, since for systems of type A all secondary variables are even, we have to confirm that (15.1) (υ 0 -1) P 0 , υ 1 S 1,e , υ 2 S 2,e , . . . , υ τ +1 S τ +1,e → P τ +2,e .

We begin by contracting the available P 0 . For π ∈ {o, e}, one has 2 P 0,π → P 1,e . Hence we can form disjoint groups of two P 0 of the same parity until no further such pairing is possible. When υ 0 is even, this will leave exactly one P 0 unused, and produce 1 2 υ 0 -1 variables P ν,e . When υ 0 is odd, we may end up with two variables uncontracted, but at least 1 2 (υ 0 -3) variables P 1,e will be generated. Thus we always have at least (15.2) 1 2 (υ 0 -2) P 1,e . Further contractions will be applied relative to the size of υ 0 . We consider cases.

(i) Suppose that υ 0 ≥ 4k + 2. By (15.2), we have 2k of P 1,e at our disposal. By Lemma 14.2 with l = τ , we see that 2kP 1,e → P τ +2,e , completing the proof of (15.1) in this case.

(ii) Suppose that 2k + 2 ≤ υ 0 ≤ 4k + 1 and k ≥ 8. Then (15.2) provides k variables P 1,e . Further, by (6.5), one has

υ 0 + υ 1 + υ 2 + υ 3 + υ 4 ≥ 5k + 1,
and hence that υ 1 + υ 2 + υ 3 + υ 4 ≥ k. We may now apply Lemma 14.2 with l = τ and ν = 1 to contract the available P 1,e , S 1,e , S 2,e , S 3,e and S 4,e to one P τ +2,e , as required.

(iii) Suppose that k + 2 ≤ υ 0 ≤ 2k + 1 and k ≥ 8. Then (15.2) yields at least k/2 variables P 1,e . Since we have 8 | k, repeated use of (13.6) shows that (15.3)

1 2 k P 1,e → 1 4 k P 2,e → 1 8 k P 3,e . If υ 3 ≥ 3
8 k, then we can form 1 8 k disjoint groups containing one P 3,e and three S 3,e . By Lemma 14.1, each of these groups contracts to a P 5,e , so that in total we have 1 8 k variables P 5,e . By Lemma 14.2, these contract to one P τ +2,e , as required. Hence, we may suppose that υ 3 < 3 8 k. However, by (6.5), we have υ 0 + υ 1 + υ 2 + υ 3 ≥ 4k + 1, and in the current situation, this shows that υ 1 + υ 2 > 13 8 k. In this case, we only use the first step in (15.3), producing 1 4 k variables P 2,e . Then, by (13.10), we contract the available S 1,e in pairs to S 2,e until at most two S 1,e remain unused. This yields υ1-1 2 variables S 2,e . At niveau 2, we now have 1 4 k primary variables, and υ1-1 2 + υ 2 secondary ones. However, υ1-1

2 ≥ 1 2 υ 1 -1 so that υ 1 -1 2 + υ 2 ≥ 1 2 υ 1 + υ 2 -1 > 13 16 k -1.
Since the left hand side is an integer, it follows that υ1-1 2 + υ 2 ≥ 3 4 k, and hence, the variables at niveau 2 can be grouped into 1 4 k blocks with one P 2,e and three S 2,e , contracting to one P 4,e each (by Lemma 14.1 again). This yields a total of 1 4 k P 4,e , contracting to one P τ +2,e (by Lemma 14.2).

(iv) Suppose that υ 0 = k + 1. By (15.2), we construct 1 2 k -1 variables P 1,e . Note that for k = 4, just one P 1,e is provided. By (6.5), we have υ 0 + υ 1 ≥ 2k + 1, whence υ 1 ≥ k. We begin by contracting the available S 1,e in pairs to S 2,e until exactly 1 2 k of S 1,e are still uncontracted (when 2 | υ 1 ) or exactly 1 2 k -1 of S 1,e are uncontracted (when 2 υ 1 ). This generates 1 2 (υ 1 + 1 -k 2 ) variables S 2,e . We now use the uncontracted S 1,e and apply (13.7) to produce 1 2 k -1 variables P 2,e . At niveau 2, we then have

k 2 -1 P 2,e , 1 2 (υ 1 + 1 -k 2 ) + υ 2 S
2,e . However, by (6.5), one has υ 0 + υ 1 + υ 2 ≥ 3k + 1, whence υ 1 + υ 2 ≥ 2k, and

1 2 (υ 1 + 1 -k 2 ) + υ 2 ≥ υ 1 2 + υ 2 - k 4 ≥ 3 4 k.
Further, for k ≥ 4, one also has 1 2 k -1 ≥ 1 4 k, and consequently, at niveau 2, one can form 1 4 k disjoint groups with one P 2,e and three S 2,e . The argument given at the end of (iii) shows that this is enough to contract to one P τ +2,e .

(v) Suppose that k = 4 and 6 ≤ υ 0 ≤ 17. We start from (15.2). Then at niveau 1, we have υ 0 2 -1 variables P 1,e , υ 1 variables S 1,e .

Note that υ 0 ≥ 6 implies that at least two P 1,e are in play. Hence, we may begin by contracting available S 1,e in pairs to S 2,e ; leaving up to two S 1,e unused. These find a partner P 1,e to contract to a P 2,e . After these contractions, the remaining P 1,e contract in disjoint pairs to P 2,e . In total, this generates 1 2 [ 1 2 υ 0 ] -1 + υ 1 new variables at niveau 2, including at least one primary variable. Hence, at niveau 2, the number of variables is

1 2 [ 1 2 υ 0 ] -1 + υ 1 + υ 2 ≥ 1 2 [ 1 2 υ 0 ] -1 + υ 1 -1 2 + υ 2 ≥ 1 2 1 2 υ 0 -3 2 + υ 1 -1 2 + υ 2 = 1 4 υ 0 + 1 2 υ 1 + υ 2 -5 4 . (15.4)
However, by (6.5), we have υ 0 + υ 1 + υ 2 ≥ 14, so that there are at least three variables at niveau 2. If υ 3 ≥ 1, we may obtain a P 4,e by the obvious contractions P 2,e , S 2,e , S 3,e → P 3,e , S 3,e → P 4,e or 2P 2,e , , S 3,e → P 3,e , S 3,e → P 4,e while in the complementary case υ 3 = 0 one has υ 0 + υ 1 + υ 2 = 18, and (15.4) delivers four variables at niveau 2, including a primary one. Now Lemma 14.1 again yields a P 4,e .

Recall that by (6.5), a conditioned system with s = k 2 +2 has υ 0 ≥ k +1. Hence, the cases (i-v) exhaust all possible cases covered by Lemma 15.1, and in all cases we have confirmed (15.1). This completes the proof.

Powers of 2 : Systems of type B

The natural analogue of Lemma 15.1 for systems of type B will not hold true, at least when k = 4. This we have illustrated with the example in section 13. Nonetheless, we shall follow the pattern of the previous section as far as is possible. For systems of type B, Lemmas 14.3 and 14.4 will have to replace Lemmas 14.1 and 14.2 in our treatment of type A. We require Lemma 14.4 with l = τ + 2, and it is then blind for variables at niveau τ + 1. This causes extra difficulties, resulting in a separate treatment of k = 8 in some cases. Except when υ 0 is very large, the case k = 4 is so different from what follows that large parts of its discussion are postponed to the next section.

Throughout, let k = 2 τ with k ≥ 4 and s = k 2 + 2. We begin with a conditioned system A = B = 0 of type B, given by (4.13). By (6.5), this contains υ 0 variables at niveau 0 where υ 0 ≥ k + 1. We contract these in disjoint pairs with the same parity to P 1,e . When υ 0 is odd, this yields (υ 0 -1)/2 variables P 1,e . When υ 0 is even, then either one obtains υ 0 /2 of P 1,e , or only finds (υ 0 -2)/2 such contractions but then is left with a pair P 0,e , P 0,o of uncontracted variables at niveau 0. Hence, we find (16.1) [υ 0 /2] variables P 1,e or (16.2) 2 | υ 0 , 1 2 υ 0 -1 variables P 1,e , and P 0,e , P 0,o .

Lemma 16.1. Let k = 2 τ with k ≥ 4 and s ≥ k 2 + 2. Let A = B = 0 be a conditioned system of type B, given by (4.13). Suppose that υ 0 ≥ 4k. Then, its variables contract to one P τ +2,e .

Proof. If υ 0 ≥ 4k + 1, we apply (16.1) and (16.2) to generate 2k P 1,e . By Lemma 14.1, these variables contract to one P τ +2,e . This leaves the case υ 0 = 4k. Again, if we are able to generate 2k P 1,e , these contract to one P τ +2,e , as before. By (16.2), we are now reduced to the case where the variables at niveau 0 contract to 2k -1 of P 1,e , leaving a pair P 0,e , P 0,o . Since the system is of type B, there is a variable S j,o at some niveau j ≥ 1, and then the obvious contraction (13.12) produces another P 1,e . Hence, again we have 2k P 1,e and the proof is completed as before.

Lemma 16.2. Let k = 2 τ with k ≥ 8 and s ≥ k 2 + 2. Let A = B = 0 be a conditioned system of type B, given by (4.13). Then, its variables contract to one P τ +2,e .

Proof. For υ 0 ≥ 4k, this conclusion is part of Lemma 16.1. For υ 0 < 4k, we mimic the arguments used in the proof of Lemma 15.1, and proceed by considering cases.

(i) Suppose that 2k < υ 0 < 4k, and that k ≥ 16. Here, (16.1) and (16.2) guarantee at least k variables P 1,e . By (6.5), we have

υ 0 + • • • + υ 4 ≥ 5k + 1, whence υ 1 + υ 2 + υ 3 + υ 4 ≥ k + 2.
Consequently, for k = 2 τ with τ ≥ 4, Lemma 14.4 with ν = 1, l = τ is applicable and yields a P τ +2,e .

(ii) Suppose that 2k < υ 0 < 4k, and that k = 8. A highly refined version of the preceding argument still applies, as we shall now show. We have already pointed out that for k = 4, values of υ 0 slightly less than 4k = 16 cannot be approached by an argument of the type suggested by (i), and when k = 8, these difficulties reflect in the fine details that require attention below. We have 17 ≤ υ 0 ≤ 31, and the variables at niveau 0 contract to 1 2 (υ 0 -1) variables P 1,e . Note that these are at least 8. Hence, if we were able to show that (16.3) 1 2 (υ 0 -1) + υ 1 + υ 2 + υ 3 ≥ 18, then it would follow from Lemma 14.4 that the variables at niveau 1, 2 and 3 contract to one P 5,e , as is required to complete the proof. If it were the case that (16.4)

υ 0 + υ 1 + υ 2 + υ 3 ≥ 34, then 1 2 (υ 0 -1) + υ 1 + υ 2 + υ 3 ≥ 34 -υ 0 + 1 2 (υ 0 -1)
, and υ 0 ≤ 31 implies (16.3). However, by (6.5), we have υ 0 + υ 1 + υ 2 + υ 3 ≥ 33, and so, it remains to consider the case where (16.5)

υ 0 + υ 1 + υ 2 + υ 3 = 33. But then (16.6) 1 2 (υ 0 -1) + υ 1 + υ 2 + υ 3 = 33 -υ 0 + 1 2 (υ 0 -1)
, and for υ 0 ≤ 29, again (16.3) follows.

This leaves the case where υ 0 = 30 or 31, and where (16.5) holds. Then υ 1 +υ 2 + υ 3 = 2 or 3, and by (6.5), we also have υ 0 + υ 1 + υ 2 + υ 3 + υ 4 ≥ 5k + 2 = 42, so that υ 4 ≥ 9. If there is an even variable among the S 4 , we may apply crude contractions to conclude that eight of the 1 2 (υ 0 -1) variables P 1,e contract to one P 4,e by Lemma 14.1, and P 4,e , S 4,e → P 5,e completes the argument in this case. Hence we may suppose that there at least 9 S 4,o , and since there are 2 or 3 secondary variables in total at niveaux 1, 2 and 3, we may correct the parity of these variables via S j,o , S 4,o → S j,e , valid for j ≤ 3 by (13.11). After parity correction, we have 1 2 (υ 0 -1) of P 1,e , and 2 or 3 even secondary variables at niveaux not exceeding 3. The total number of all these variables is still given by (16.6), and is therefore 17, but now all variables are even, and Lemma 14.2 delivers a P 5,e , completing the argument in the case under consideration.

(iii) Suppose that k < υ 0 ≤ 2k. By (16.1) and ( 16.2), we obtain at least k/2 variables P 1,e from the variables at niveau 0. Then, by (13.6), one has the chain of contractions (16.7)

1 2 υ 1 + υ 2 ≤ 3 4 k + 2.
We now involve the variables at niveau 3. In its simplest form, the argument to follow will only work for k ≥ 16, as we now temporarily assume. Begin by contracting the S 2 in pairs to S 3 , disregarding parity. By (16.9) and (13.10), the yields a total of

υ 3 + 1 2 υ 2 -1 + 1 2 (υ 1 -1) ≥ υ 3 + 1 2 υ 2 -1 + 1 2 (υ 1 -1) -1 2 ≥ υ 3 + 1 2 υ 2 + 1 4 υ 1 -1 -
υ 3 + 1 2 υ 2 -1 + 1 2 (υ 1 -1) ≤ 3 8 k + 1 which in turn implies (16.12) υ 3 + 1 2 υ 2 + 1 4 υ 1 ≤ 3 8 k + 5 2 .
Further, on multiplying (16.8) and (16.10) with 1 2 , and adding the results with (16.12), we infer that

υ 1 + υ 2 + υ 3 ≤ 3 8 k + 5 2 + 1 2 3 4 k + 2 + 1 2 3 2 k + 1 = 3 2 k + 4.
However, by (6.5), we have υ 0 + υ 1 + υ 2 + υ 3 ≥ 4k + 1, and hence that (16.13)

υ 1 + υ 2 + υ 3 ≥ 2k + 1
which is a contradiction when k ≥ 16. This shows that we have exhausted all possible cases when k ≥ 16. This leaves the case k = 8 for further discussion. In view of (16.8) and (16.10), we may restrict attention to the case where υ 1 ≤ 13, 1 2 υ 1 + υ 2 ≤ 8. From (6.5), we see that υ 0 + υ 1 + υ 2 ≥ 25, whence υ 1 + υ 2 ≥ 9. We now argue as in (16.9), and contract the available S 1 in pairs to S 2 , disregarding parity. Let u 2 be the exact number of S 2 available after this process, including the S 2 counted by υ 2 . Then u 2 ≥ υ1 2 + υ 2 -1, and hence u 2 ≥ 4. First consider the case where among the S 2 there are at least three with the same parity. A pair of these contracts to an S 3,e . Following this contraction, we contract the remaining u 2 -2 variables S 2 in disjoint pairs to S 3 , without regarding parity. Then, as in (16.11), at niveau 3 we now have at least u 3 variables S 3 , where

u 3 ≥ υ 3 + 1 2 υ 2 + 1 4 υ 1 -3 2
including at least one S 3,e . By (16.13),

u 3 ≥ 17 -1 2 υ 2 -3 4 υ 1 -3 2 ≥ 13 -1 2 υ 1 -3 2 ≥ 5.
Hence, from (16.7), we see P 3,e , S 3,e , 4S 3 at niveau 3. If the five S 3 here include at least 3S 3,e , then Lemma 14.1 produces the desired P 5,e . In the contrary case, we have at least 3S 3,o , and we can select two of them to contract to an S 4,e . The desired P 5,e is then provided by P 3,e , S 3,e , S 4,e → P 4,e , S 4,e → P 5,e .

If we do not have three S 2 with the same parity, then the condition that u 2 ≥ 4 implies that u 2 = 4, with 2S 2,e , 2S 2,o . In this case, we apply (16.7) and start with 2P 2,e , followed by 2P 2,e , 2S 2,e → P 4,e (Lemma 14.1). However, u 2 = 4 implies In (13.2) we presented an example of a conditioned system with k = 4 and s = 18 where the associated congruences (13.3) do not admit a non-singular solution. Note that in this example there are three odd variables at niveau 3.

It turns out that this is typical for such examples. Anticipating this observation, we set out to show that in all other relevant cases, we can still follow the pattern of our work in sections 14-16. Thus, our leading parameter remains υ 0 , but we now closely monitor the variables at niveau 3. Throughout, we now restrict to the case k = 4, type B. Lemma 17.1. Let k = 4 and s ≥ 18. Let A = B = 0 be a conditioned system of type B, given by (4.13). Suppose that the system includes a variable S 3,e . Then its variables contract to one P 4,e .

Proof. It will suffice to contract the variables at niveaux 0, 1 and 2 to one P 3,e because then the contraction P 3,e , S 3,e → P 4,e establishes the lemma.

If υ 0 ≥ 9, then (16.1) produces 4P 1,e . If υ 0 = 8 we apply (16.2) to produce 3P 1,e , P 0,e , P 0,o . However, since the system is of type B, there is a variable S j,o , for some 1 ≤ j ≤ 3. Now P 0,e , P 0,o , S j,o → P 1,e , so that again we have 4P 1,e . Hence, by (13.6), whenever υ 0 ≥ 8, we may contract via 4P 1,e → 2P 2,e → P 3,e .

We are left with the case where υ 0 ≤ 7. However, by (6.5), we now have (17.1)

υ 0 ≥ 5, υ 0 + υ 1 ≥ 9, υ 0 + υ 1 + υ 2 ≥ 14.
Hence, by (16.1), we get 2P Hence, we now suppose that there are υ 2 odd variables at niveau 2. We now apply S 1,o , S 2,o → S 1,e whenever necessary to construct two variables S 1,e from the variables initially at niveaux 1 and 2. Then 2P 1,e , 2S 1,e → P 3,e is a consequence of Lemma 14.1. This completes the proof.

From now on, we may suppose that the variables at niveau 3, if any, are all odd. If there are at most two such variables, then we conclude as follows.

Lemma 17.2. Let k = 4 and s ≥ 18. Let A = B = 0 be a conditioned system of type B, given by (4.13). Suppose that υ 3 ≤ 2. Then its variables contract to one P 4,e .

Proof. In view of Lemma 17.1, we may suppose that all variables at niveau 3 are odd. Further, by Lemma 16.1, it suffices to study the situation where υ 0 ≤ 15. Also, we have the inequalities (17.1) at our disposal. We now divide into cases.

(i) 14 ≤ υ 0 ≤ 15. We shall see that a preliminary contraction always yields 7P 1,e , and one S j,e for some 1 ≤ j ≤ 3. Once this is established, Lemma 14.2 produces the desired P 4,e .

If υ 0 = 15, then 7P 1,e flow from (16.1), and s ≥ 18 yields at least three secondary variables. Since υ 3 ≤ 2, not all of these can be at niveau 3. Further, if one of these is even, then we have already reached our goal. Hence, the secondary variables can be assumed to be all odd. If there is an S i,o and an S j,o with 1 ≤ i < j ≤ 3, then S i,o , S j,o → S i,e yields the desired even variable. Otherwise, we must have 3S i,o for some i = 1 or 2. But then (13.9) yields one S i+1,e , completing the argument in this case.

If υ 0 = 14, we recall that the system is of type B, so that (16.1) or (16.2) and (13.12) produce 7P 1,e , leaving three secondary variables unused. As in the case υ 0 = 15, one contracts two of the unused variables to an even secondary variable, and then proceeds as before.

(ii) υ 0 = 13. Here (16.1) yields 6P 1,e . If υ 1 + υ 2 ≥ 4, it suffices to apply Lemma 14.4 to create a P 4,e . However, υ 1 + υ 2 ≤ 3 together with s ≥ 18 and υ 3 ≤ 2 implies that υ 1 + υ 2 = 3, υ 3 = 2. Since the two variables at niveau 3 are both odd, we may use (13.11) to correct the parity of two of the variables counted by υ 1 + υ 2 to become even. But then we have 6P 1,e , and two even secondary variables at niveau not exceeding 2. By Lemma 14.2, this yields P 4,e .

(iii) υ 0 = 12. Here, we first use (16.1) and (16.2) to generate 5 (sic!) P 1,e . If υ 1 + υ 2 ≥ 5, Lemma 14.4 creates a P 4,e . Thus, we may suppose that υ 1 + υ 2 ≤ 4, and again, this implies s = 18, υ 3 = 2, υ 1 + υ 2 = 4.

The variables counted by υ 3 are odd, and we use this to construct a sixth P 1,e via (13.12). Hence, we now have 6P 1,e and υ 1 + υ 2 = 4, so that Lemma 14.4 again yields a P 4,e .

(iv) 8 ≤ υ 0 ≤ 11. From υ 3 ≤ 2 we have υ 0 + υ 1 + υ 2 ≥ 16. Further, if υ 0 is odd, we apply (16.1) to generate [υ 0 /2] ≥ 4 variables P 1,e , and we also have [υ 0 /2] + υ 1 + υ 2 ≥ 10.

We may therefore apply Lemma 14.4 to generate a P 4,e .

If υ 0 is even, then we apply (16.2) together with (13.12) to generate υ 0 /2 ≥ 4 of P 1,e . Note that this is possible since the system is of type B. However, the contractions may involve one secondary variable. After this process, at niveaux 1 and 2 we see 1 2 υ 0 + υ 1 + υ 2 -1 ≥ 10 variables in total. Hence Lemma 14.4 is applicable, yielding a P 4,e .

(v) υ 0 = 7. By (16.1) we get 3P 1,e . Hence, if υ 1 ≥ 7, Lemma 14.3 provides a P 4,e via 3P 1,e , 7S 1 → P 4,e . Hence, we may suppose that 2 ≤ υ 1 ≤ 6. Now υ 3 ≤ 2 implies υ 2 ≥ 3. We split into subcases, relating to the available S 2 .

(α) Suppose that there are 3S 2,e . Then 2P 1,e → P 2,e , and Lemma 14.1 supplies P 2,e , 3S 2,e → P 4,e , as required.

(β) Suppose that there are 3S 2,o . We contract these to one S 3,e , leaving one S 2,o uncontracted. This variable we use in S 1,o , S 2,o → S 1,e if necessary to ensure that there is an S 1,e available. Now Lemma 14.1 and (13.7) give (17.2) 3P 1,e , S 1,e , S 3,e → P 3,e , S 3,e → P 4,e .

(γ) Suppose that the system is not covered by (α) and (β). Then, there are at most two variables S 2,o , and at most two S 2,e , and so, 3 ≤ υ 2 ≤ 4 and υ 1 ≥ 5.

If there are 2S 2,e , then there is also a least one S 2,o , and as in case (β), this odd variable can be used to ensure one S 1,e . But then we complete the argument via (17.3) 3P 1,e , S 1,e , 2S 2,e → 2P 2,e , 2S 2,e → P 4,e .

This leaves the case υ 2 = 3, with S 2,e , 2S 2,o for discussion. Now υ 1 ≥ 6. The more frequent parity of the variables at niveau 1 occurs at least three times, and two of them contract to a second S 2,e . This leaves four variables at niveau 1, and by using one of the S 2,o if necessary, we can ensure that we have an S 1,e available. We can now complete the argument via (17.3).

(vi) υ 0 = 6. This is similar to case (v), but there are certain details that require attention. We begin with (16.1) and (16.2), providing 2P 1,e , P 0,o , P 0,e or 3P 1,e . If υ 1 ≥ 8, then Lemma 14.3 again yields a P 4,e . If υ 1 = 7 and there is a variable S j,o with j ≥ 2, then use (13.12), so that we have 3P 1,e available. Again Lemma 14.3 yields a P 4,e . Otherwise, all variables at niveaux 2 and 3 are even, and υ 1 = 7 implies υ 2 ≥ 3, providing 3S 2,e , and 2P 1,e → P 2,e . In this case P 2,e , 3S 2,e → P 4,e yields the desired conclusion. Hence, we are reduced to the case where 3 ≤ υ 1 ≤ 6, υ 2 ≥ 4.

We now follow the argument given in case (v).

(α) Suppose that there are 3S 2,e . Here, as above (17.4) 2P 1,e , 3S 2,e → P 2,e , 3S 2,e → P 4,e .

completes the argument.

(β) Suppose that there are 3S 2,o . These contract to S 3,e , S 2,o , and the remaining S 2,o can be used in (13.12) to ensure that we have 3P 1,e .

If there is an S 1,e , then (17.2) yields a P 4,e .

In the alternative case, we have at least 3S (γ) If the system is not covered by (α) or (β), we see from υ 2 ≥ 4 that we must have υ 2 = 4 with 2S 2,o , 2S 2,e . But now υ 1 = 6, and as in case (v), one then may construct an S 2,e from the variables at niveau 1. One P 4,e now comes from (17.4). In the alternative case, υ 1 ≥ 4 yields at least 3S 1,o , and these contract to S 2,e . Now (17.5) completes the argument.

(γ) If the system is not covered by (α) or (β), then υ 2 = 4, with 2S 2,e , 2S It is perhaps of interest to inspect the role of the variables at niveau 3 in the proof of Lemma 17.2. While these are essential in the case where υ 0 = 15, in the case υ 0 ≤ 12 it is only required that there are at most two such variables, their parity is irrelevant, and they are not used in the contractions.

Since we treat type B, a variable P 4,e gives a non-singular solution of the congruences (13.4) by Lemmas 10.1 and 13.1, and hence, the given system has a 2-adic non-trivial solution by Lemma 4.2 in the cases covered by Lemmas 17.1 and 17.2. Therefore it only remains to discuss conditioned systems with s ≥ 18, and υ 3 ≥ 3 where all variables at niveau 3 are odd.

Cycling home

We now embark on our final task. In order to complete the proof of the Theorem when k = 4, it remains to show that a conditioned system with k = 4, s ≥ 18 and υ 3 ≥ 3 with all variables at niveau 3 odd, has non-trivial 2-adic solutions. Note that (13.3) is such a system, forcing us to waive the strategy followed in section 17.

Instead, we apply a "cycling trick", inspired by the proof of Lemma 6.1. Suppose that A = B = 0 is a conditioned system satisfying the conditions described in the previous paragraph. Then, by (6.5), we have υ 0 ≥ 5, υ 0 + υ 1 ≥ 9, υ 0 + υ 1 + υ 2 ≥ 14, and υ 3 ≥ 3 by hypothesis. Let x 0 , . . . , x 3 be as in (6.3). The system A(x) = B(x) = 0 is equivalent with the system (18.1) 1 8 A(2x 0 , 2x 1 , 2x 2 , x 3 ) = B(2x 0 , 2x 1 , 2x 2 , x 3 ) = 0, and observe that 1 8 A(2x 0 , 2x 1 , 2x 2 , x 3 ) is a form with integer coefficients. We put y j = x j-1 (1 ≤ j ≤ 3), and y 0 = x 3 . Then, in the language introduced in section 13, the variables y j are now at niveau j. Also, all variables y 0 are odd, thanks to our overall hypothesis. Further, the variables y 1 , y 2 , y 3 are all even, by construction.

Note that the system (18.1) is not conditioned. However, all its coefficients are still non-zero, and we have υ 3 variables P 0,o , and υ j-1 variables S j,e (1 ≤ j ≤ 3). We now argue as follows. We first use 3 P 0,o → P 1,e , P 0,o .

If υ 0 ≥ 7, then P 1,e , 7S 1,e → P 4,e is provided by Lemma 14.1. If υ 0 = 5 or 6, then υ 0 + υ 1 ≥ 9 implies υ 1 ≥ 3. We first contract two of the υ 0 S 1,e to one S 2,e , leaving an S 1,e behind, and then P 1,e , S 1,e , 3S 2,e → P 2,e , 3S 2,e → P 4,e .

Hence, in all cases, the variables in the system (18.1) contract to P 4,e , leaving a P 0,o untouched.

As in the proof of Lemma 13.1, this amounts to choosing y 1 = y 2 = 1, y 3 = 0 in y 0 , and an inspection of the proof of Lemma 13.1 shows that we have found a non-singular solution to the congruences (13.4) associated with (18.1). Consequently, the system (18.1) has non-trivial 2-adic solutions by Lemma 4.2, and so has the original system A = B = 0. This establishes the theorem when k = 4.

b

  ij y j = 0 (1 ≤ i ≤ r).

Lemma 3 . 5 .

 35 Let k ≥ 6 be even, and let p be an odd prime with p | k. If k = p(p-1) and s ≥ k 2 + 2, then the equations (1.2) have a non-trivial p-adic solution.

(4. 5 ) a 1 y k 1 + a 2 y k 2 = 2 and b 2 a 1 x k- 1 1b 1 a 2 x 2 .

 512212 A and b 1 y 1 + b 2 y 2 = B. In the sequel, we refer to solutions of (4.3) that satisfy (4.4) as non-singular. Proof. By (4.4) the prime p cannot divide b 1 a 2 x k-1 simultaneously. By symmetry in the indices 1 and 2, we may therefore suppose that (4.6) p Now multiply the congruence in (4.3) with b k 1 , and put z 1 = b 1 x 1 . Then (4.3) transforms into (4.7)

Lemma 5 . 1 .

 51 , Theorem 2.1]. Let q ≥ 1 be an integer. Let A , B ⊂ Z/qZ, and suppose that 0 ∈ B and B \ {0} ⊂ (Z/qZ) × . Let A + B denote the set of all sums a + b with a ∈ A and b ∈ B. Then #(A + B) ≥ min(#A + #B -1, q).

Lemma 5 . 6 .

 56 Let p ≥ 3. Let a 1 , . . . , a p , c ∈ F × p , and let b 1 , . . . , b p ∈ F p . Then there is a non-singular solution in F p of the pair of equations p j=1 a j x p-1 j = cy + p j=1 b j x j = 0.

Lemma 5 . 7 .b

 57 Let p ≥ 3. Let a 1 , . . . , a p-1 ∈ F × p , and let b 1 , . . . , b p ∈ F p with b p = 0. j x j = 0 has no non-singular solution in F p . Then the a j are all equal.

Lemma 8 . 2 .

 82 Let a 1 , a 2 as in the preamble of Lemma 8.1. Let c 1 , . . . , c k , d 1 , . . . , d k , e, f be integers where p c 1 f , and where (8.1)

  has a non-trivial p-adic solution.Proof. Write d 2 = p m d 2 with p d 2 . Put u = 1 -p m , so that u = 0 when p d 2 , and u ≡ 1 mod p otherwise. Then apply Lemma 8.1 with c = -c 1 -u k c 2 , d = -d 1 and l = β. Note that p cd as required. This lemma provides integers x 1 , x 2 , c with c ≡ c mod p. If we take y 3 = y 4 = • • • = y k = 0 in (8.4) and cancel a factor p β , this system now reduces to(8.5)

Lemma 12 . 1 .

 121 Let a 1 , . . . , a 9 , b 1 , . . . , b 9 , c 1 , c 2 , c 3 , d 1 , d 2 , d 3 denote integers, and suppose that 3

(

  vii) υ 0 = 5. Here (16.1) yields 2P 1,e . If υ 1 ≥ 8 then Lemma 14.3 gives a P 4,e . Hence, we are reduced to the case where 4 ≤ υ 1 ≤ 7, υ 2 ≥ 4. (α) If there are 3S 2,e , we use (17.4) to get P 4,e . (β) If there are 3S 2,o , transform theses to S 2,o , S 3,e . Should there be 2S 1,e , then 2P 1,e , 2S 1,e , S 3,e → P 3,e , S 3,e → P 4,e .

  First suppose that k is odd. Then by Dodson [13, Lemma 4.2.2], we have Γ * (k, 2) = k + 1. Hence (3.3) holds.

Lemma 3.2. Let k ≥ 5, but not one of the numbers 8, 16, 32. If s ≥ k 2 + 2, then the equations (1.2) have a non-trivial 2-adic solution.

Proof.

  Let p be a prime, and suppose that k is linked with τ via (4.1). Let a 1 , a 2 , b 1 , b 2 , A, B and x 1 , x 2 denote integers satisfying

	4.2)	γ = τ + 1 except when p = 2 where γ = τ + 2.
	Lemma 4.1.

  This completes the proof of the lemma.

	Let a 1 , . . . , a s , b 1 , . . . , b s be integers, and consider the forms
		s		s
	(4.13)	A(x 1 , . . . , x s ) =	a j x k j ,	B(x 1 , . . . , x s ) =	b j x j .
		j=1		j=1
	Lemma 4.2. Let s ≥ 2, and suppose that x ∈ Z s satisfies the congruences
	(4.14)	A(x) ≡ 0 mod p γ ,	B(x) ≡ 0 mod p
	and (4.4). Then there are y 1 , y 2 ∈ Z p with (y 1 , y 2 ) = (0, 0) and
		A(y 1 , y 2 , x 3 , . . . , x s ) = B(y 1 , y 2 , x 3 , . . . , x s ) = 0.

  S 1 → P τ +2,e , completing the proof of the lemma in this case. Thus, from now on, we may suppose that

		1 2 k P 1,e → 1 4 k P 2,e → 1 8 k P 3,e
	and we recall that 8 | k.
	We now consider the secondary variables. If υ 1 ≥ 3 2 k + 2, then we apply Lemma
	14.3 in the form
	1 2 k P 1,e , 3 2 k + 2 (16.8) υ 1 ≤ 3 2 k + 1.
	Here we contract the available S 1 in pairs to S 2 , disregarding parity of the resulting
	S 2 . By (13.10), we obtain 1 2 (υ 1 -1) new S 2 . Hence, in total, at niveau 2 there
	are
	(16.9)	υ 2 + 1 2 (υ 1 -1) ≥ 1 2 υ 1 + υ 2 -1
	secondary variables now available. Note that 8 | k implies 1 4 k ≥ 2, and hence, whenever υ 2 + 1 2 (υ 1 -1) ≥ 3 4 k + 2, we can apply Lemma 14.3 in the form
		1 4 k P 2,e , 3 4 k + 2 S 2 → P τ +2,e ,
	to finish the proof in this case. Consequently, we may now suppose that
		υ 2 + 1 2 (υ 1 -1) ≤ 3 4 k + 1,
	and by (16.9) this implies that
	(16.10)

  . Once again, provided that there are at least 3 8 k + 2 of S 3 available, we can use (16.7) and Lemma 14.3 in the form 1 8 k P 3,e , 3 8 k + 2 S 3 → P τ +2,e , to complete the proof of the lemma in the current case. Note that at this point we need that 1 8 k ≥ 2, which requires us to restrict to k ≥ 16. But then, we are reduced to the case where

	(16.11)	1 2
	variables S 3

  By Lemmas 13.1, 10.1 and 4.2, it follows that systems of type B considered in Lemmas 16.1 and 16.2 have non-trivial solutions in Q 2 . This completes the proof of our theorem when k = 2 τ , k ≥ 8. 17. Systems of type B when k = 4

	1 2 υ 1 + υ 2 ≤ 5. But then, by (16.13),
	υ

3 ≥ 17 -υ 1 -υ 2 ≥ 7, so that we can find a pair of S 3 of the same parity contracting to an S 4,e . The argument is now completed with P 4,e , S 4,e → P 5,e .

  1,e . If υ 1 ≥ 4, the desired P 3,e is implied by Lemma 14.3. Hence, in view of (17.1), we may now suppose that 2 ≤ υ 1 ≤ 3 and υ 2 ≥ 4. If among the variables at niveau 2 there is an S 2,e , we may use 2P 1,e , S 2,e → P 2,e , S 2,e → P 3,e .

  1,o , providing an S 2,e . Now (17.5) 2P 1,e , S 2,e , S 3,e → P 2,e , S 2,e , S 3,e → P 4,e .

  2,o . We use the 2S 2,o to ensure 2S 1,e at niveau 1, and then 2P 1,e , 2S 1,e , 2S 2,e → 2P 2,e , 2S 2,e → P 4,e . The proof if Lemma 17.2 is now complete.

Acknowledgements

The authors are grateful to their home institutions for support on the occasion of mutual visits during the period where this paper was conceived. The first author acknowledges with gratitude support by Deutsche Forschungsgemeinschaft and Schweizer Nationalfond. Further, he thanks T. Wooley and V. Kala for discussions concerning the material in §2, and M. Kaesberg for comments on a draft version of this paper. Last but not least we wish to express our sincere gratitude to an anonymous referee who has read the manuscript with utmost care, drew our attention to reference [15] and made numerous suggestions that improved the presentation.