TRANSLATION INVARIANT EQUATIONS AND THE METHOD OF SANDERS THOMAS F. BLOOM Abstract. We extend the recent improvement of Roth’s theorem on three term arithmeticprogressionsbySanderstoobtainsimilarresultsfortheproblemoflocat- ing non-trivial solutions to translation invariant linear equations in many variables 2 in both Z/NZ and F [t]. q 1 0 2 n 1. Introduction a J This paper concerns solutions to a linear equation in s ≥ 3 variables, 0 3 (1.1) c x +···+c x = 0 c (cid:54)= 0, 1 1 s s i ] working inside some fixed ring R, and we restrict our attention to those equations T N with coefficients satisfying c +···+c = 0. These are often referred to as translation 1 s h. invariant systems, since it follows that if (x1,...,xs) ∈ Rs is a solution then so is (x + x,...,x + x) for any x ∈ R. Following Ruzsa [16] we define the genus of an t 1 s a equation of the shape (1.1) to be the largest number m with the property that there m (cid:80) is a partition of {1,...,s} into m disjoint nonempty sets T where c = 0. Note [ j i∈Tj i that the genus is well defined and positive, as a consequence of translation invariance. 2 v Given an equation (1.1) of genus m and a finite set A one obtains |A|m solutions 0 x ∈ As by setting x = x whenever i,i(cid:48) ∈ T . We call such solutions trivial, and seek i i(cid:48) j 1 an upper bound on the size of sets which contain only trivial solutions to (1.1). In this 1 1 paperwegeneralisearecentresultofSanderswhichgivesthebestknownboundinthe 7. case with s = 3 and R = Z/NZ to obtain quantitative results of comparable quality 0 for any s ≥ 3 in circumstances where R is either Z/NZ or the polynomial ring F [t]. q 1 Despite the analogies between these rings having been well-explored throughout most 1 : of number theory, the problems of additive combinatorics have been little studied in v i the F [t] setting, and we hope that this paper will encourage others to obtain further X q results of this nature in polynomial rings. We also wish to promote the philosophy r a thatF [t]isausefulmodelcaseforsuchproblems, actingasa‘halfwayhouse’between q the currently popular finite field model case FN and Z/NZ; technically simpler than p the latter but capturing more of the interesting behaviour of the integer case than the former. The problem of finding large sets with no non-trivial solutions to (1.1) may be posed in any ring (or indeed any module), but since the work of Roth (see [14, 15]) it has received most attention in the integers Z, or rather finite truncations {1,...,N} that may conveniently be viewed as the cyclic group Z/NZ. In the special case Date: January 31, 2012. The author is supported by an EPSRC doctoral training grant. 1 2 THOMAS F. BLOOM s = 3 and (c ,c ,c ) = (1,−2,1) this is equivalent to finding a three term arithmetic 1 2 3 progression a,a+d,a+2d, with non-trivial solutions satisfying d (cid:54)= 0. If s ≥ 3 and c ∈ (Z/NZ)s is such that (1.1) has genus m ≥ 1 then we define r(N) = r (N) to be s,c the cardinality of the largest subset of Z/NZ which contains no non-trivial solutions to (1.1). Roth showed that r(N) (cid:28) N/loglogN. This was improved for s = 3 by s,c Heath-Brown [8] and Szemerédi [20] to r(N) (cid:28) N/logcN for some absolute constant c > 0, the value of which was subsequently improved by Bourgain (see [2, 3]), first to c = 1/2 − o(1) and then to c = 2/3 − o(1). Sanders further improved this to c = 3/4−o(1) in [17] before the recent breakthrough result of [18], (loglogN)5 (1.2) r(N) (cid:28) N . logN All of the results mentioned above were obtained only for the special case of three term progressions when c = (1,−2,1), but it is straightforward to generalise their methods for any translation invariant equation of the form (1.1) with s = 3. We expect that as the number of variables s increases non-trivial solutions to (1.1) should become easier to find, and hence we should obtain improved bounds for r(N). The first result of this paper confirms this expectation, generalising the result of Sanders to handle arbitrary s ≥ 3. Theorem 1.1. Let s ≥ 3, and suppose c ∈ Zs is such that the equation (1.1) has genus m ≥ 1. Then (cid:18)(loglogN)5(cid:19)s−2 r (N) (cid:28) N . s,c s,c logN We remark that the implicit constant in Theorem 1.1 in fact depends only on (cid:96) = max |c |. In [16] Ruzsa showed that if the equation (1.1) has genus m then 1≤i≤s i r(N) (cid:28) N1/m, which is far superior to Theorem 1.1 whenever m ≥ 2. The power of the methods used to obtain the bounds listed above, which originated in Roth [14], is that they give a non-trivial result in the most difficult case m = 1. When s ≥ 6, recent work of Schoen and Shkredov [19], building on other work of Sanders, shows that for some absolute positive constants C and c we have the near-optimal bound r(N) (cid:28) N exp(−ClogcN). Theorem 1.1, however, gives the sharpest known bounds for s = 4 and s = 5. By partial summation we obtain the following corollary. Corollary 1.1. If A ⊂ N satisfies (cid:80) a−1 = ∞ then A contains infinitely many a∈A non-trivial solutions to every translation invariant equation of the form (1.1) having s ≥ 4 variables. For comparison, a conjecture of Erd˝os asserts that if (cid:80) a−1 = ∞ then A must a∈A contain infinitely many arithmetic progressions of length k for any k ∈ N. In the case k = 3, this would follow were Corollary 1.1 to hold with s = 3, which would in turn follow if one could improve the (loglogN)5 factor in Theorem 1.1 to (loglogN)−2, for example. Another popular setting for the problem of finding solutions to the equation (1.1) is FN, an N-dimensional vector space over the finite field F . Here we have coefficients p p TRANSLATION INVARIANT EQUATIONS AND THE METHOD OF SANDERS 3 c ∈ F and we define r (N) to be the cardinality of the largest subset of FN that i p s,c p contains only trivial solutions to the equation (1.1). The best known bounds here are superior to those in Z/NZ. Thus, for example, the simple method of Meshulam [13] yields r(N) (cid:28) pN/N, a conclusion comparable to r(N) (cid:28) N/logN in the integer case. Furthermore, Bateman and Katz [1] have recently improved this upper bound to show that for some absolute constant (cid:15) > 0, one has r(N) (cid:28) pN/N1+(cid:15). The investigation of such problems in FN has recently become popular since it is p often conceptually easier to prove results in FN, taking advantage of the vector space p structure, and then ‘translate’ the methods to the more difficult case Z/NZ (see [7] for a comprehensive discussion of this technique). One setting that has received comparatively little attention is F [t], the ring of q polynomials over a finite field; as in the case of Z it is more convenient to deal with finite truncations of this infinite ring, so we shall work in the additive subgroup of polynomials with degree strictly less than N, which we shall denote by G . There are N many well-known analogies between number theory in Z and in F [t], and theorems q in one often have a natural counterpart in the other. We should expect, in particular, some result analogous to (1.2) to hold for solutions to the equation (1.1) where c ∈ F [t]s. Perhapspartofthereasonwhythisproblemhasbeenlargelyoverlookedisthat q G is additively isomorphic to FN, since both are N-dimensional vector spaces over N q F . Henceintheclassicalcase, withs = 3andc = (1,−2,1), thestrongboundsofthe q FN settingareavailable. Ingeneral, suchboundsareavailablewheneverc ∈ Fs, where q p p is the characteristic of F . In the F [t] setting, however, this restricts all coefficients q q to have degree zero, and hence trivial size under the usual valuation |a| = qdega. Viewed in this way it is less surprising that we can obtain such impressive bounds with such a strong restriction on the coefficients of our linear equation. Note in particular that such issues of triviality do not arise in the Z/NZ case, since s ≥ 3 and translation invariance forces at least one of the coefficients of the equation (1.1) to have non-trivial size. When s ≥ 3 and c ∈ F [t]s, denote by r(N) the size of the largest subset of G q N which contains no non-trivial solutions to the equation (1.1). The sharpest bound for r(N) currently available in the case where c ∈ Fs is due to Liu and Spencer [11] who q showed that r(N) (cid:28) qN/Ns−2. The second result of this paper adapts the method of Sanders to give a comparable bound even when the coefficients c have large degree. i As above, this result gives a bound which improves as s increases. Theorem 1.2. Let s ≥ 3, and suppose c ∈ F [t]s is such that the equation (1.1) has q genus m ≥ 1. Then (cid:18)(logN)4(cid:19)s−2 r (N) (cid:28) qN , s,c s,(cid:96) N where (cid:96) = max(degc ). i Note here that the implicit constant depends only on the highest degree of the coefficients c . It also depends on q, the size of the constant field. Throughout this i paper, this will be considered fixed as will s and c, and all constants may depend on these. 4 THOMAS F. BLOOM It is not difficult to get some kind of quantitative bound for r(N) even when the coefficients have large degree, and indeed the original method of Roth can be adapted withalittleefforttoobtainr(N) (cid:28) qN/logN. Theorem1.2goesbeyondthistoshow that we can obtain a quantitative bound comparable to the best known in Z/NZ. Indeed, in F [t] we are able to do slightly better (by a factor of logN) than the q analogue of (1.2). This improvement is a consequence of the vector space structure of F [t] which we are able to exploit even when the coefficients have large degree. q We remark that the methods of [16] are easily adapted to the F [t] setting to give q r(N) (cid:28) qN/m whenever (1.1) has genus m, a conclusion sharper than that of Theorem 1.2 whenever m ≥ 2. The strength of Theorem 1.2 is that it applies when m = 1, which appears to be the most difficult case. Since this paper was originally written, we have been made aware of recent similar results by Liu and Zhao [12]. By adapting the methods of [2] and [3] to the F [t] q setting they show, under the same hypotheses as Theorem 1.2, that (cid:18)(logN)2(cid:19)2(4ss−−29)2 r (N) (cid:28) qN . s,c s,(cid:96) N This is weaker than Theorem 1.2 for all s ≥ 3, as it does not use the new techniques introduced in [18]. We note, however, that the mechanisms they use to translate ideas from the Z/NZ setting of [2] and [3] to F [t] are very similar to those introduced in q this paper. In particular, they also give the proper analogue of Bohr sets in the F [t] q setting. The main ideas and techniques used to establish Theorems 1.1 and 1.2 are those of theoriginalargumentin[18],butweareabletomakemanytechnicalsimplificationsin F [t], largely thanks to the fact the analogue of ‘Bohr sets’ are closed under addition. q Indeed, we hope that this paper may also serve as an exposition of the methods in [18], for in F [t] the fundamental ideas are less obscured by technical difficulties. We q further hope that this paper will indicate how to translate many results of additive combinatorics to an analogous result in F [t], which we believe to be a technically q simpler model for such results. In recent years there has been a focus on obtaining such results in FN and then p translating the methods used so as to obtain a result in Z/NZ. We believe that the translation from FN to F [t] and thence to Z/NZ is simpler to perform and more p q intuitive. We are confident that this new method will stimulate further progress in other problems of additive combinatorics. Thus, for example, the approach taken in this paper is to first establish Theorem 1.2, the F [t] case, and then sketch how to adapt the proof to obtain Theorem 1.1, the q Z/NZ case. In Section 2 we explain the notation used in the rest of the paper and prove two useful lemmas. Sections 3 and 4 provide the two tools used in the approach of Sanders [18], namely a combinatorial transformation of sets inspired by the work of Katz and Koester [9] and an application of the useful probabilistic theorem due to Croot and Sisask [5]. Section 5 combines these tools in the ‘density increment’ strategy so as to conclude the proof of Theorem 1.2. Section 6 then sketches a proof of Theorem 1.1. Here we are brief, since the proofs are the same as those for Theorem 1.2 except for routine technical changes. TRANSLATION INVARIANT EQUATIONS AND THE METHOD OF SANDERS 5 2. Notation and preliminaries Throughout the rest of this paper, let N be some fixed large integer and F be q the finite field with q elements. We shall write G = G = {x ∈ F [t] : degx < N}, N q and note in particular that G is an N-dimensional vector space over F . We will q frequently use the expectation notation E 1 (cid:88) f(x) = f(x). |X| x∈X x∈X Unless denoted otherwise, all expectations are taken over G. By a convenient abuse of notation, we use the same letter for the set and its characteristic function. When considering C ⊂ G, we use µ to denote the measure induced by C, so that C |G| µ (x) = C(x) C |C| and for A ⊂ G, |A∩C| µ (A) = (cid:104)µ ,A(cid:105) = . C C |C| For notational convenience we will also use β to denote µ . Given a subspace B ⊂ G B we will denote subsets of B by capital Roman letters, and their density within B by the corresponding lower case Greek letter, so that β(A) = α, for example. We draw special attention to our novel notation for the balanced function of a subset A ⊂ B, defined by  1−α if x ∈ A,   A(x) := (A−αB)(x) = −α if x ∈ B\A, and  0 otherwise, so that E A(x) = 0. For any functions f,g : G → C we define x∈B E (cid:104)f,g(cid:105) = f(x)g(x), µX x∈X and similarly, for any 1 ≤ p < ∞, (cid:18)E (cid:19)1/p (cid:107)f(cid:107) = |f(x)|p and (cid:107)f(cid:107) = sup|f(x)|. p(µX) ∞(µX) x∈X x∈X Where the measure is omitted these expectations should be taken over G. There is an analogue of Fourier analysis in the F [t] setting. If x = (cid:80) a ti ∈ F ((1/t)) then q i 0 then there is a subset ∆˜ ⊂ ∆ (D) such that |∆˜| (cid:28) η−2log(1/δ) and η ∆ (D) ⊂ {−1,0,1}|∆˜| ·∆˜. η We now use this to convert the fact that we have large Fourier coefficients over a large spectrum into a more useful density increment property. The idea goes back to the work of Heath-Brown [8] and Szemerédi [20], and was developed into the following form by Sanders [17]. Lemma 2.3. For any Bohr set B ⊂ G and η > 0 if A,D ⊂ B satisfy (cid:88) |A(cid:98)(γ)|2 ≥ να2µ (B) G γ∈∆η(D) then there is a Bohr set B(cid:48) ⊂ B with rk(B(cid:48)) ≤ rk(B)+O(η−2log(1/δ)) and β(B(cid:48)) ≥ exp(−Cη−2log(1/δ)) such that (cid:107)A∗β(cid:48)(cid:107) ≥ α(1+ν). ∞ Proof. Let B(cid:98) ⊂ G(cid:98) be the dual group of B viewed as an additive group. It is easy to check that for any γ ∈ G(cid:98) there is some γ(cid:48) ∈ B(cid:98) such that γ(x) = γ(cid:48)(x) for all x ∈ B. Let ∆(cid:48) = B(cid:98) ∩ ∆ (D). Renormalising the Fourier transform, we see that ∆(cid:48) is the η η-spectrum at B for D. Let ∆˜ ⊂ ∆(cid:48) be the set given by Lemma 2.2, and refine the Bohr set B by setting B(cid:48) = {x ∈ B : deg{xγ} < −1 for all γ ∈ ∆˜}. It follows that rk(B(cid:48)) ≤ rk(B)+|∆˜| ≤ rk(B)+O(η−2log(1/δ)), and hence β(B(cid:48)) ≥ exp(−Cη−2log(1/δ)). Furthermore, for all γ ∈ ∆ (D) we have η β(cid:98)(cid:48)(γ) = Ex∈B(cid:48)e(xγ) = 1. By Parseval’s identity and the initial hypothesis (cid:88) (cid:88) (cid:107)A∗β(cid:48)(cid:107)2 = |A(cid:98)(γ)|2|β(cid:98)(cid:48)(γ)|2 ≥ |A(cid:98)(γ)|2 ≥ να2µ (B). 2 G γ∈G(cid:98) γ∈∆η(D) Furthermore, note that B∗β(cid:48)(y) = E B(y−x) = B(y), and hence (cid:104)B∗β(cid:48),B∗β(cid:48)(cid:105) = x∈B(cid:48) µ (B). Similarly, G E E (cid:104)A∗β(cid:48),B ∗β(cid:48)(cid:105) = µ (B) A(y −x) = αµ (B). G G x∈By∈B(cid:48) TRANSLATION INVARIANT EQUATIONS AND THE METHOD OF SANDERS 9 In particular, (cid:107)A∗β(cid:48)(cid:107)2 = (cid:107)A∗β(cid:48)(cid:107)2 +α2(cid:104)B ∗β(cid:48),B ∗β(cid:48)(cid:105)−2α(cid:104)A∗β(cid:48),B ∗β(cid:48)(cid:105) 2 2 = (cid:107)A∗β(cid:48)(cid:107)2 −α2µ (B). 2 G It follows that (cid:107)A∗β(cid:48)(cid:107)2 ≥ α2(1+ν)µ (B). Combining Ho¨lder’s inequality with the 2 G equality (cid:107)A∗β(cid:48)(cid:107) = αµ (B) gives (cid:107)A∗β(cid:48)(cid:107) ≥ α(1+ν) as required. (cid:3) 1 G ∞ We make one final remark on the values of the densities α of the various A ⊂ G we consider, where these A will be sets with no non-trivial solutions to the equation (1.1). Recall that we may assume α ≤ r(N) (cid:28) 1/logN by adapting the method of Roth. In particular, for sufficiently large N, we will assume that α < 1/e2, so that log(1/α) > 2. Making this assumption avoids some notational awkwardness. 3. A combinatorial transformation We begin with a generalisation of one of the two main tools in the method of Sanders, a combinatorial transformation. This has its origins in the work of Katz and Koester [9], though a similar transformation known as the Dyson e-transform has been a useful tool in additive combinatorics since [6]. The idea is to find, given subsets A ,...,A of a Bohr set B, corresponding 1 k+1 L,S ,...,S ⊂ B such that L is dense inside B, the S are not too sparse and 1 k i L∗S ∗···∗S ≤ α−2A ∗A ∗···∗A . 1 k 1 1 2 k+1 Since solutions to (1.1) are counted by (cid:104)(c ·A)∗···∗(c ·A),c ·A(cid:105) to find many 1 s−1 s solutions to (1.1) in A it then suffices to find a lower bound for (cid:104)L∗···∗S ,c ·A(cid:105). s−2 s The large density of L may then be efficiently exploited using the recent probabilistic method of Croot and Sisask, as we shall do in the next section. When we cannot find such sets we find a strong density increment and jump to the final stage of the proof. We first give a simplified proof of Lemma 4.2 from [18], taking advantage of the fact that our Bohr sets are subspaces in order to streamline the proof. We also observe that the proof gives a slightly stronger statement than is recorded in [18]. We then applythistechnicallemmaiterativelytoconstructsetsL,S ,...,S asabovetoprove 1 k the main theorem of this section. This is a generalisation of Proposition 4.1 from [18], taking advantage of the large number of convolutions to run a more efficient iterative procedure. Lemma 3.1. If B is a Bohr set and K,T,L,S ⊂ B then either (1) there exists a Bohr set B(cid:48) ⊂ B with rank at most rk(B)+O(λκ−1log(1/τ)), density β(B(cid:48)) ≥ exp(−Cλκ−1log(1/τ)) such that, for some x ∈ B, β(cid:48)(K + x) ≥ κ/32λ, or (2) there are L(cid:48),S(cid:48) ⊂ B with β(L(cid:48)) ≥ λ+κ/2 and β(S(cid:48)) ≥ τσ/2 such that, for all x ∈ G, L(cid:48) ∗S(cid:48)(x) ≤ L∗S(x)+K ∗T(x). Proof. For an arbitrary x ∈ B, let L = L ∪ (K + x) and S = S ∩ (T − x). By x x construction, L ∗S ≤ L∗S +(K +x)∗S ≤ L∗S +K ∗T. x x x x 10 THOMAS F. BLOOM Furthermore, we have β(L ) = λ+κ−β(L∩(K +x)) = λ+κ−L∗(−K)(x) x and β(S ) = (−S)∗T(x). Hence if |Sym (−S,T)| > |Sym (L,−K)| then we are x τσ/2 κ/2 inthesecondcasebytakingL(cid:48) = L andS(cid:48) = S forsomex ∈ Sym (−S,T)\Sym (L,−K). x x τσ/2 κ/2 Note that E β(Sym (−S,T))σ +στ/2 ≥ (−S)∗T(x) = στ, τσ/2 x∈B so that β(Sym (−S,T)) ≥ τ/2. Hence either we are in the second case of the τσ/2 theorem, or we may assume that D = Sym (−L,K) has density at least τ/4, say. κ/2 We have (cid:104)(−L)∗K,D(cid:105) ≥ κδ/2. β Note that (cid:104)(−L)∗B,D(cid:105) = λδ. β We may assume that λ < 1/4, say, or else the conclusion is trivial. Hence, by the triangle inequality, |(cid:104)(−L)∗K,D(cid:105) | ≥ κδ(1/2−λ) ≥ κδ/4. β Taking the Fourier transform of the left hand side we see that (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)(cid:88) (cid:91) (cid:12) (cid:12) (−L)(γ)K(cid:98)(γ)D(cid:98)(γ)(cid:12) ≥ κδµ (B)2/4. G (cid:12) (cid:12) (cid:12) (cid:12) γ∈G(cid:98) The Cauchy-Schwarz inequality combined with Parseval’s identity then gives (cid:88) |K(cid:98)(γ)|2|D(cid:98)(γ)|2 ≥ κ2δ2µ (B)3/16λ. G γ∈G(cid:98) Furthermore, if we let η2 = κ/32λ then by Parseval’s identity again we have (cid:88) |K(cid:98)(γ)|2|D(cid:98)(γ)|2 ≤ κ2δ2µ (B)3/32λ. G γ∈/∆η(D) Using the trivial upper bound |D(cid:98)(γ)| ≤ δµ (B) it follows that G (cid:88) |K(cid:98)(γ)|2 ≥ κ2µ (B)/32λ. G γ∈∆η(D) Applying Lemma 2.3, we have a Bohr set B(cid:48) ⊂ B with rank and size as required and β(cid:48)(K +x) ≥ κ/32λ for some x ∈ X. (cid:3) We now apply Lemma 3.1 iteratively to prove the main theorem of this section. Theorem 3.1. Let B be a Bohr set and suppose A ⊂ B with density α and 1 1 A ,...,A ⊂ B all with density at least α. Then either 2 k+1 (1) there exists a Bohr set B(cid:48) ⊂ B with rank rk(B(cid:48)) ≤ rk(B)+O(α−1/klog(1/α)), 1 density β(B(cid:48)) ≥ exp(−Cα−1/klog(1/α)) and, for some x ∈ B, we have β(cid:48)(A + 1 1 x) ≥ 2α , or 1

Translation invariant equations and the method of Sanders

Similar Translation invariant equations and the method of Sanders