Roth’s Theorem

Graph Theory and Additive Combinatorics 6 Roth’s theorem In Chapter 3.3, we proved Roth’s theorem using Szemerédi regularity lemma via the triangle removal lemma. In this chapter, we will be instead be studying Roth’s original proof of Roth’s Theorem using Fourier analysis. First, let us recall the statement of Roth’s Theorem. Let r3 ([ N ]) denote the maximum size of a 3-AP-free subset of [ N ]. Then Roth’s theorem states that r3 ([ N ]) = o ( N ). One of the drawbacks of using Szemerédi regularity which shows an upper bound that is something like logN∗ N . Roth’s Fourier analytic proof would instead give us an upper bound of something like N log log N , which is a much more reasonable bound. Remark 6.1. The current best upper bound known is r3 ([ N ]) ≤ √ N (log N )1−o(1) and the best lower bound known is r3 ( N ) ≥ Ne−O( log N ) due to the Behrend construction. There is some evidence that seem to suggest that the lower bound is closer to truth, but closing the gap is still an open problem. 6.1 Roth’s theorem in finite fields We will begin by examining a finite field analogue to Roth’s Theorem. Finite field models are a good sandbox for testing methods before applying to general integer cases; in particular, it is a good starting point because a lot of technicalities go away. Let r3 (F3n ) denote the maximum size of 3 AP-free subset of F3n . Note that given x, y, z in F3n , the following are equivalent: • x, y, z for a 3 term arithmetic progression • x − 2y + z = 0 • x+y+z = 0 • x, y, z form a line Sanders (2011) Bloom (2016) • for all i, the ith coordinate of x, y, z are all distinct or all equal. We will state and prove a version of Roth’s theorem in the finite field model. The proof is in the same spirit as the general Roth’s theorem, but is slightly easier. This is relevant to the game of SET, which can be thought of as finding 3 APs in F43 . Meshulam (1995) Theorem 6.2. r3 (F3n )  =O 3n n  The proof using triangle removal lemma copies verbatim so we can get r3 (F3n ) = o (3n ) but the above theorem gives a better dependence. We comment briefly on the history of this problem. In 2004, Edel found that r3 (F3n ) ≥ 2.21n . It was open for a long time whether r3 (F3n ) = (3 − o (1))n . Recently, a surprising breakthrough showed that r3 (F3n ) ≤ 2.76n . We had an energy increment argument during the proof of Szemerédi Regularity lemma. The strategy for Roth’s theorem is a variant of energy increment. Instead, we will consider density increment. Given A ⊂ F3n , we employ the follow strategy. 1. If A is pseudorandom (which we will see is equivalent to it being Fourier uniform, which roughly translates to all its Fourier coefficients are small) then there is a counting lemma which will show that A has lots of 3-AP. 2. If A is not pseudorandom, then we will show that A has a large Fourier coefficient. Then we can find a codimension 1 affine subspace (i.e. hyperplane) where density of A will increase. Now we consider A restricted to this hyperplane, and repeat the previous steps. 3. Each time we repeat, we obtain a density increment. Since density is bounded above by 1, this gives us a bounded number of steps. Next, we recall some Fourier analytic ideas that will be important in our proof. In F3n , we consider the Fourier characters γr : F3n → C, indexed by r ∈ F3n , which are defined to be γr ( x ) = ω r· x where ω = e2πi/3 and r · x = r1 x1 + · · · + rn xn . We define a Fourier transform. For f : F3n → C, the Fourier transform is given by fb : F3n → C where fb(r ) = E f ( x )ω −r· x = h f , γr i. n x ∈F3 Effectively, the fourier transform is the inner product of f and the Fourier characters. Edel (2004) Croot, Lev, Pach (2016) Ellenberg and Gijswijt (2016) Remark 6.3. We use the following convention on normalization: in a finite group, for a physical space we will use average measure but in frequency we will always use sum measure. We note some key properties of the Fourier transform. Proposition 6.4. • fb(0) = E f • (Plancheral/Parseval) Ex∈F3n f ( x ) g( x ) = ∑r∈Fn fb(r ) gb(r ). 3 • (Inversion) f ( x ) = ∑r∈Fn fb(r )ω r· x 3 • (Convolution) Define ( f ∗ g)( x ) = Ey f (y) g( x − y). Then we claim that [ f ∗ g( x ) = fb( x ) gb( x ). To prove these properties notice that Fourier characters form an orthonormal basis. Indeed, we can check  1 if r = s, hγr , γs i = E γr ( x )γs ( x ) = E ω −(r−s)· x = 0 otherwise. x x If we think of Fourier transform as a unitary change of basis, inversion and Parseval’s follows immediately. To see the formula for convolution, note that E( f ∗ g ) ω = E f (y) g( x − y)ω −r(y+(x−y)) = E f ( x )ω −r· x E g( x )ω −s· x . r·x s r x,y x The following key identity relates Fourier transform with 3-APs. Proposition 6.5. If f , g, h : F3n → C, then E f ( x ) g( x + y)h( x + 2y) = x,y ∑ fb(r) gb(−2r)bh(r). r We will give two proofs of this proposition, with the second being more conceptual. First proof. We expand the LHS using the formula for Fourier inversion. ! ! ! LHS = E ∑ fb(r1 )ω r1 · x ∑ gb(r2 )ωr2 ·(x+y) ∑ bh(r3 )ωr3 ·(x+2y) x,y = ∑ r1 r1 ,r2 ,r3 r2 fb(r1 ) gb(r2 )b h (r3 ) E ω x r3 x ·(r1 +r2 +r3 ) Eω y·(r2 +2r3 ) y = ∑ fb(r ) gb(−2r )b h (r ) r The last equality follows because  1 if r + r + r = 0, 2 3 1 x ·(r1 +r2 +r3 ) ω = E 0 otherwise x and Eω y·(r2 +2r3 ) y =  1 if r2 + 2r3 = 0, 0 otherwise. Second proof. In this proof, we think of the LHS as a convolution. E x,y,z:x +y+z=0 f ( x ) g(y)h(z) = ( f ∗ g ∗ h)(0) = ∑ f\ ∗ g ∗ h (r ) r = ∑ fb(r ) gb(r )b h (r ) r In particular, note that if we take f , g, h = 1 A where A ⊂ F3n , then 3−2n #{( x, y, z) ∈ A3 : x + y + z = 0} = ∑ b1 A (r)3 . (6.1) r Remark 6.6. If A = − A then this gives the same formula that counts closed walks of length 3 in Cayley graphs. In particular, {b 1 A (r ) = r } correspond eigenvalues of Cayley( G, A). Lemma 6.7 (Counting Lemma). If A ⊂ F3n with | A| = α3n , let Λ3 ( A) = Ex,y 1 A ( x )1 A ( x + y)1 A ( x + 2y). Then, Λ3 ( A) − α3 ≤ α max 1c A (r ) . r 6 =0 Proof. By Proposition 6.5, Λ3 ( A ) = ∑ 1cA (r)3 = α3 + ∑ 1cA (r)3 . r r 6 =0 Therefore, Λ3 ( A ) − α3 ≤ ∑ 1c A (r ) 3 r 6 =0 c ≤ max 1c A (r ) · ∑ 1 A (r ) r 6 =0 2 r 2 = max 1c A (r ) · E1 A r 6 =0 (Parseval) = α max 1c A (r ) . r 6 =0 Proof of Theorem 6.2. Let N = 3n , the number of elements in F3n . Step 1. If the set is 3-AP free, then there is a large Fourier coefficient. Lemma 6.8. If A is 3-AP-free and N ≥ 2α−2 , then there is r 6= 0 such that 2 1c A (r ) ≥ α /2. Proof. By counting lemma and the fact that Λ3 ( A) = | A| α = , 2 N N α α3 3 α max 1c ≥ . A (r ) ≥ α − N 2 r 6 =0 Step 2. Large Fourier coefficient implies density increment on a hyperplane. Lemma 6.9. If 1c A (r ) ≥ δ for some r 6 = 0, then A has density at least α+ δ 2 when restricted to some hyperplane. Proof. We have −r · x 1c A (r ) = E n 1 A ( x ) w x ∈F3 = 1 ( α0 + α1 w + α2 w2 ) 3 where α0 , α1 , α2 are densities of A on the cosets of r ⊥ . Notice that α = α0 +α31 +α2 . By triangle inequality, 3δ ≤ α0 + α1 w + α2 w2 = ( α0 − α ) + ( α1 − α ) w + ( α2 − α ) w2 2 ≤ ∑ |α j − α| j =0 2 ≤ ∑ (|α j − α| + (α j − α)). j =0 (This final step is a trick that will be useful in the next section.) Note that every term in the last summation is non-negative. Consequently, δ there exists j such that δ ≤ |α j − α| + (α j − α). Then, α j ≥ α + . 2 Step 3 : Iterate density increment. So far, we have that if A is 3-AP-free and N ≥ 2α−2 , then A has density at least α + α2 /4 on some hyperplane. Let our initial density be α0 = α. At the i-th step, we restrict A to some hyperplane, so that the restriction of A inside the smaller space has density αi ≥ αi−1 + α2i−1 /4. Let Ni = 3n−i . We can continue at step i as long as Ni ≥ 2αi−2 . We note that the first index i1 such that αi1 ≥ 2α0 satisfies i1 ≤ 2 4 α + 1. This is because αi+1 ≥ α + i α4 . Similar calculations shows that if i` is the first index such that αi` ≥ 2` α0 then i` ≤ 2 4 8 4 1 + m + · · · + `−1 + ` ≤ + log2 . α α α α 2 α Suppose the process terminates after m steps with density αm . Then we find that the size of the subspace in the last step is given by 2 −2 3n−m < 2α− m ≤ 2α . So     8 1 2 =O n ≤ + log3 2 α α α  n | A| = α = O(1/n). Equivalently, | A| = αN = O 3n as N desired. Thus Remark 6.10. This proof is much more difficult in integers, because there is no subspace to pass down to. A natural question is whether this technique can be generalized to bound 4-AP counts. In the regularity-based proof of Roth’s theorem, we saw that the graph removal lemma was not sufficient, and we actually needed hypergraph regularity and a hypergraph removal lemma to govern 4-AP counts. Similarly, while the counting lemma developed here shows that Fourier coefficients control 3-AP counts, they do not in fact control 4-AP counts. For example, consider the set A = { x ∈ F5n : x · x = 0}. One can show that the nonzero Fourier coefficients corresponding to A are all small. However, one can also show that A has the wrong number of 4-APs, thus implying that Fourier coefficients cannot control 4-AP counts. The field of higher-order Fourier analysis, namely quadratic Fourier analysis, was developed by Gowers specifically to extend this proof of Roth’s Theorem to prove Szemeredi’s Theorem for larger APs. An example of quadratic Fourier analysis is given by the following theorem. Gowers (1998) Theorem 6.11 (Inverse theorem for quadratic Fourier analysis). For all δ > 0, there exists a constant c(δ) > 0 such that if A ⊂ F5n has density α, and |Λ4 ( A) − α4 | > δ, then there exists a non-zero quadratic polynomial f ( x1 , . . . , xn ) over F5 satisfying |Ex∈F5n 1 A ( x )ω f (x) | ≥ c(δ). 6.2 Roth’s proof of Roth’s theorem in the integers In Section 6.1 we saw the proof of Roth’s theorem in the finite field setting, specifically for the set F3n . We will now extend this analysis to prove the following bound, which will imply Roth’s theorem in the integers: Theorem 6.12.  r3 ([ N ]) = O . N log log N  Roth (1953) The subsequent proof of this bound is the original one given by Roth himself. Recall that the proof of Roth’s theorem in finite fields had the following 3 steps: 1. Show that a 3-AP-free set admits a large Fourier coefficient. 2. Deduce that there must exist a subspace with a density increment. 3. Iterate the density increment to upper bound the size of a 3-AP free set. The proof of Roth’s theorem on the integers will follow the same 3 steps. However, the execution will be quite different. The main difference lies in step 2, where there is no obvious notion of a subspace of [ N ]. Previously we defined Fourier analysis in terms of the group F3n . There is a general theory of Fourier analysis on Abelian groups b also referred to which relates a group G to its set of characters G, as its dual group. For now, however, we work with the group Z. b = R/Z. The Fourier Transform of a The dual group of Z is Z function f : Z → C is given by the function fb : R/Z → C satisfying fb(θ ) = ∑ f ( x )e(− xθ ), x ∈Z where e(t) = e2πit . This is commonly referred to as the Fourier series of f . As they were in F3n , the following identities are also true in Z. Their proofs are the same. • fb(0) = ∑ x∈Z f ( x ) • (Plancherel/Parseval) ∑ x∈Z f ( x ) g( x ) = R1 • (Inversion) f ( x ) = 0 fb(θ )e( xθ )dθ R1 0 fb(θ ) gb(θ )dθ • Define Λ( f , g, h) = ∑ x,y∈Z f ( x ) g( x + y)h( x + 2y). Then Λ( f , g, h) = Z 1 0 fb(θ ) gb(−2θ )b h(θ )dθ. In the finite field setting, we defined a counting lemma, which showed that if two functions had similar Fourier transforms, then they had a similar number of 3-APs. We can define an analogue to the counting lemma in Z as well. Theorem 6.13 (Counting Lemma). Let f , g : Z → C such that ∑n∈Z | f (n)|2 , ∑n∈Z | g(n)|2 ≤ M. Define Λ3 ( f ) = Λ( f , f , f ). Then |Λ3 ( f ) − Λ3 ( g)| ≤ 3M f[ −g ∞ . Proof. We can rewrite Λ3 ( f ) − Λ3 ( g) = Λ( f − g, f , f ) + Λ( g, f − g, f ) + Λ( g, g, f − g). We want to show that each of these terms is small when f − g has small Fourier coefficients. We know that |Λ( f − g, f , f )| = Z 1 0 (\ f − g)(θ ) fb(−2θ ) fb(θ )dθ −g ≤ f[ ≤ f[ −g Z 1 ∞ 0 1 Z ∞ fb(−2θ ) fb(θ )dθ 0 | fb(−2θ )|2 dθ (triangle inequality) 1/2 Z 1 0 | fb(θ )|2 dθ 1/2 (Cauchy-Schwarz) −g ≤ f[ ∞ ≤ M f[ −g ∑ ! | f ( x )|2 (Plancherel) x ∈Z ∞ . Bounding the other two terms is identical. We can now proceed with proving Roth’s Theorem. Proof of Theorem 6.12. We follow the same 3 steps as in the finite field setting. Step 1: 3-AP free sets induce a large Fourier coefficient Lemma 6.14. Let A ⊂ [ N ] be a 3-AP free set, | A| = αN, N ≥ 5/α2 . Then there exists θ ∈ R satisfying N ∑ (1 A − α)(n)e(θn) ≥ n =1 α2 N 10 Proof. Since A has no 3-AP, the quantity 1 A ( x )1 A ( x + y)1 A ( x + 2y) is nonzero only for trivial APs, i.e. when y = 0. Thus Λ3 (1 A ) = | A| = αN. Now consider Λ3 (1[ N ] ). This counts the number of 3-APs in [ N ]. We can form a 3-AP by choosing the first and third elements from [ N ], assuming they are the same parity. Therefore Λ3 (1[ N ] ) ≥ N 2 /2. Now, we apply the counting lemma to f = 1 A , g = α1[ N ] Remark 6.15. The spirit of this whole proof is the theme of structure versus pseudorandomness, an idea we also saw in our discussion graph regularity. If A is “pseudorandom”, then we wish to show that A has small Fourier coefficients. But that would indicate that f and g have similar Fourier coefficients, implying that A has many 3-AP counts, which is a contradiction. Thus A cannot be pseudorandom, it must have some structure. Applying Theorem 6.13 yields (where we use the notation f ∧ = fb) α3 N 2 − αN ≤ 3αN (1 A − α1[ N ] )∧ 2 ∞ and thus (1 A − α1[ N ] )∧ ∞ 1 3 2 2α N − αN 3αN 1 1 = α2 N − 6 3 1 ≥ α2 N, 10 ≥ where in the last inequality we used the fact that N ≥ 5/α2 . Therefore there exists some θ with N ∑ (1 A − α)(n)e(θn) n =1 = (1 A − α1[ N ] )∧ (θ ) ≥ 1 2 α N, 10 as desired. Step 2: A large Fourier coefficient produces a density increment. In the finite field setting our Fourier coefficients corresponded to hyperplanes. We were then able to show that there was a coset of a hyperplane with large density. Now, however, θ is a real number. There is no concept of a hyperplane in [ N ], so how can we chop up [ N ] in order to use the density increment? On each coset of the hyperplane each character was exactly constant. This motivates us to partition [ N ] into sub-progressions such that the character x 7→ e( xθ ) is roughly constant on each subprogression. As a simple example, assume that θ is a rational a/b for some fairly small b. Then x 7→ e( xθ ) is constant on arithmetic progressions with common difference b. Thus we could partition [ N ] into arithmetic progressions with common difference b. Before formalizing this idea, we require the following classical lemma from Dirichlet. Lemma 6.16. Let θ ∈ R and 0 < δ < 1. Then there exists a positive integer d ≤ 1/δ such that kdθ kR/Z ≤ δ (here, k·kR/Z is defined as the distance to the nearest integer). j k Proof. Pigeonhole principle. Let m = 1δ . Consider the m + 1 numbers 0, θ, · · · , mθ. By the pigeonhole principle, there exist i, j such that the fractional parts of iθ and jθ differ by at most δ. Setting d = |i − j| gives us kdθ kR/Z ≤ δ, as desired. The next lemma formalizes our previous intuition for partitioning [ N ] into subprogressions such that the map x 7→ e( xθ ) is roughly constant on each progression. Lemma 6.17. Let 0 < η < 1 and θ ∈ R. Suppose N > Cη −6 (for some universal constant C). Then one can partition [ N ] into sub-APs Pi , each with length N 1/3 ≤ | Pi | ≤ 2N 1/3 , such that supx,y∈ Pi |e( xθ ) − e(yθ )| < η for all i. 4πN 1/3 η (4π )6 we Proof. By Lemma 6.16, there exists an integer d ≤ Cη −6 , η . 4πN 1/3 such that Since N > for C = get that kdθ kR/N ≤ √ d < N. Therefore we can partition [ N ] into APs with common difference d, each with lengths between N 1/3 and 2N 1/3 . Then inside each sub-AP P, we have that sup |e( xθ ) − e(yθ )| ≤ | P||e(dθ ) − 1| ≤ 2N 1/3 · 2π kdθ kR/Z ≤ η, x,y∈ P where we get the inequality |e(dθ ) − 1| ≤ 2π kdθ kR/Z from the fact that the length of a chord is at most the length of the corresponding arc. We can now apply this lemma to obtain a density increment. Lemma 6.18. Let A ⊂ [ N ] be 3-AP-free, with | A| = αN and N > Cα−12 . Then there exists a sub-AP P ⊂ [ N ] with | P| ≥ N 1/3 and | A ∩ P| ≥ (α + α2 /40)| P|. Proof. By Lemma 6.14, there exists θ satisfying | ∑ xN=1 (1 A − α)( x )e( xθ )| ≥ α2 N/10. Next, apply Lemma 6.17 with η = α2 /20 to obtain a partition P1 , . . . , Pk of [ N ] satisfying N 1/3 ≤ | Pi | ≤ 2N 1/3 . We then get that α2 N≤ 10 k N ∑ (1 A − α)(x)e(xθ ) x =1 ≤ ∑ ∑ (1 A − α)(x)e(xθ ) i =1 x ∈ Pi For x, y ∈ Pi , |e( xθ ) − e(yθ )| ≤ α2 /20. Therefore we have that ∑ (1 A − α)(x)e(xθ ) ≤ x ∈ Pi ∑ (1 A − α)(x) + x ∈ Pi α2 | P |. 20 i Altogether, k α2 N≤∑ 10 i =1 α2 ∑ (1 A − α)(x) + 20 | Pi | x∈P i k = ∑ ∑ (1 A − α)(x) i =1 x ∈ Pi + α2 N 20 ! . Thus k α2 N≤∑ 20 i =1 and hence ∑ (1 A − α)(x) x ∈ Pi k α2 k | Pi | ≤ ∑ | A ∩ Pi | − α| Pi | . ∑ 20 i=1 i =1 We want to show that there exists some Pi such that A has a density increment when restricted to Pi . Naively bounding the RHS of the previous sum does not guarantee a density increment, so we use the following trick k α2 k | Pi | ≤ ∑ | A ∩ Pi | − α| Pi | ∑ 20 i=1 i =1 k = ∑
| A ∩ Pi | − α| Pi | + | A ∩ Pi | − α| Pi | . i =1 Thus there exists an i such that α2 | P | ≤ | A ∩ Pi | − α| Pi | + | A ∩ Pi | − α| Pi |. 20 i Since the quantity | x | + x is always strictly greater than 0, this i must satisfy | A ∩ Pi | − α| Pi | ≥ 0, and thus we have α2 | P | ≤ 2(| A ∩ Pi | − α| Pi |), 20 i which yields α2 )| P |. 40 i Thus we have found a subprogression with a density increment, as desired. | A ∩ Pi | ≥ (α + Step 3: Iterate the density increment. Step 3 is very similar to the finite field case. Let our initial density be α0 = α, and the density after each iteration be αi . We have that αi+1 ≥ αi + α2i /40, and that αi ≤ 1. We double α (i.e. reach T such that α T ≥ 2α0 ) after at most 40/α + 1 steps. We double α again (i.e. go from 2α0 to 4α0 ) after at most 20/α + 1 steps. In general, the kth doubling requires at most 2k40 −1 α steps. There are at most log2 (1/α ) + 1 doublings, as α must remain less than 1. Therefore the total number of iterations must be O(1/α). Lemma 6.18 shows that we can pass to a sub-AP and increment the density whenever Ni > Cα−12 . Therefore if the process terminates at step i, we must have Ni ≤ Cαi−12 ≤ Cα−12 . Each iteration reduces the size of our set by at most a cube root, so i O(1/α) N ≤ Ni3 ≤ (Cα−12 )3 = ee O(1/α) . Therefore α = O(1/ log log N ) and | A| = αN = O( N/ log log N ), as desired. Remark 6.19. This is the same proof in spirit as last time. A theme in additive combinatorics is that the finite field model is a nice playground for most techniques. Let us compare this proof strategy in both F3n and [ N ]. We saw that r3 (F3n ) = O( N/ log N ). However, the bound for [ N ] is O( N/ log log N ), which is weaker by a log factor. Where does this stem from? Well, in the density increment step for F3n , we were able to pass down to a subset which had size a constant factor of the original one. However, in [ N ], each iteration gives us a subprogression which has size equal to the cube root of the previous subspace. This poses a natural question—is it possible to pass down to subsprogressions of [ N ] which look more like subspaces? It turns out that this is indeed possible. For a subset S ⊂ F3n , we can write its orthogonal complement as US = { x ∈ F3n : x · s = 0 for all s ∈ S}. In [ N ], the analogous concept is known as a Bohr set, an idea developed by Bourgain to transfer the proof in Section 6.1 to Z. This requires us to work in Z/NZ. For some subset S ⊂ Z/NZ, we can define its Bohr set as Bohr(S, e) = { x ∈ Z/NZ : sx N Bourgain, 1999 ≤ e for all s ∈ S}. This provides a more natural analogy to subspaces, and is the basis for modern improvements on bounds to Roth’s Theorem. We will study Bohr sets in relation to Freiman’s Theorem in Chapter 7. 6.3 The polynomial method proof of Roth’s theorem in the finite field model Currently, the best known bound for Roth’s Theorem in F3n is the following: Theorem 6.20. r3 (F3n ) = O(2.76n ). This bound improves upon the O(3n /n1+e ) bound (for some e > 0) proved earlier by Bateman and Katz. Bateman and Katz used Fourier-analytic methods to prove their bound, and until very recently, it was open whether the upper bound could be improved to a power-saving one (one of the form O(cn ) for c < 3), closer to the lower bound given by Edel of 2.21n . Croot–Lev–Pach gave a similar bound for 3-APs over (Z/4Z)n , proving that the maximum size of a set in (Z/4Z)n with no 4-APs is Ellenberg and Gijswijt (2017) Bateman and Katz (2012) Edel (2004) O(3.61n ). They used a variant of the polynomial method, and their proof was made easier by the fact that there are elements of order 2. Ellenberg and Gijswijt used the Croot–Lev–Pach method, as it is often referred to in the literature, to prove the bound for F3n . We will use a formulation that appears on Tao’s blog. Let A ⊆ F3n be 3-AP-free (this is sometimes known as a cap set in the literature). Then we have the identity δ0 ( x + y + z) = ∑ δa (x)δa (y)δa (z) (6.2) a∈ A for x, y, z ∈ A, where δa is the Dirac delta function, defined as follows:  1 if x = a, δa ( x ) := 0 if x 6= a. Note that (6.2) holds because x + y + z = 0 if and only if z − y = y − x in F3n , meaning that x, y, z form an arithmetic progression, which is only possible if x = y = z = a for some a ∈ F3n . We will show that the left-hand side of (6.2) is “low-rank" and the right-hand side is “high-rank" in a sense we explain below. Recall from linear algebra the classical notion of rank: given a function F : A × A → F, for a field F, we say F is rank 1 if it is nonzero and can be written in the form F ( x, y) = f ( x ) g(y) for some functions f , g : A → F. In general, we define rank F to be the minimum number of rank 1 functions required to write F as a linear combination of rank 1 functions. We can view F as a matrix. How should we define the rank of a function F : A × A × A → F? We might try to extend the above notion by defining such a function F to be rank 1 if F ( x, y, z) = f ( x ) g(y)h(z), known as tensor rank, but this is not quite what we want. Instead, we say that F has slice-rank 1 if it is nonzero and it can be written in one of the forms f ( x ) g(y, z), f (y) g( x, z), or f (z) g( x, y). In general, we say the slice-rank of F is the minimum number of slice-rank 1 functions required to write F as a linear combination. For higher powers of A, we generalize this definition accordingly. What is the rank of a diagonal function? Recall from linear algebra that the rank of a diagonal matrix is the number of nonzero entries. A similar result holds true for the slice-rank. Lemma 6.21. If F : A × A × A → F equals F ( x, y, z) = ∑ ca δa (x)δa (y)δa (z), a∈ A then slice-rank F = |{ a ∈ A : c a 6= 0}|. Croot, Lev, and Pach (2017) Tao (2016) Here the coefficients c a correspond to diagonal entries. Proof. It is clear that slice-rank F ≤ |{ a ∈ A : c a 6= 0}|, as we can write F as a sum of slice-rank 1 functions by F ( x, y, z) = ∑ c a δa ( x )(δa (y)δa (z)). a∈ A c a 6 =0 For the other direction, assume that all diagonal entries are nonzero; if c a = 0 for some a, then we can remove a from A without increasing the slice-rank. Now suppose slice-rank F < | A|. So we can write F ( x, y, z) = f 1 ( x ) g1 (y, z) + · · · + f ` ( x ) g` (y, z) + f `+1 (y) g`+1 ( x, z) + · · · + f m (y) gm ( x, z) + f m+1 (z) gm+1 ( x, y) + · · · + f | A|−1 (z) g| A|−1 ( x, y). Claim 6.22. There exists h : A → F3 with | supp h| > m such that ∑ h(z) f i (z) = 0 (6.3) z∈ A for all i = m + 1, . . . , | A| − 1. Here supp h is the set {z ∈ A : h(z) 6= 0}. Proof. In the vector space of functions A → F3 , the set of h satisfying (6.3) for all i = m + 1, . . . , | A| − 1 is a subspace of dimension greater than m. Furthermore, we claim that every subspace of dimension m + 1 has a vector whose support has size at least m + 1. For a subspace X of dimension m + 1, suppose we write m + 1 vectors forming a basis of X in an | A| × (m + 1) matrix Y. Then, this matrix has rank m + 1, so there must be some non-vanishing minor of order m + 1; that is, we can delete some rows of Y to get an (m + 1) × (m + 1) matrix with nonzero determinant. If the column of this matrix are the vectors v1 through vm+1 , then these vectors generate all of F3m+1 . In particular, some linear combination of v1 , v2 , . . . , vm+1 is equal to the vector of all ones, which has support m + 1. So, taking that linear combination of the original vectors (the columns of Y) gives a vector of support at least m + 1. Pick the h from the claim. We find ∑ F ( x, y, z)h(z) = z∈ A ∑ ∑ ca δa (x)δa (y)δa (z)h(z) = ∑ ca h(a)δa (x)δa (y), a∈ A z∈ A a∈ A but also ∑ z∈ A F ( x, y, z)h(z) = f 1 ( x ) ge1 (y) + · · · + f ` ( x ) g] ` (y) f + f `+1 (y) gg m ( x ), `+1 ( x ) + · · · + f m ( y ) g where gei (y) = ∑z∈ A gi (y, z)h(z) for 1 ≤ i ≤ `, and gei ( x ) = ∑z∈ A gi ( x, z)h(z) for ` + 1 ≤ i ≤ m. Thus ∑ ca h(a)δa (x)δa (y) = a∈ A f 1 ( x ) ge1 (y) + · · · + f ` ( x ) g` (y) f + f `+1 (y) gg m ( x ). `+1 ( x ) + · · · + f m ( y ) g Note the left-hand side has more than m diagonal entries (namely the a where h( a) 6= 0), but the left-hand side has rank at most m, which is a contradiction as we have reduced to the 2-dimensional case. Using induction, we can easily generalize (from 3 variables) to any finite number of variables, the proof of which we omit. We have thus proved that the slice-rank of the right hand side of (6.2) is | A|, and is therefore “high-rank.” We now show that the left hand side has “low-rank.” Lemma 6.23. Define F : A × A × A → F3 as follows: F ( x + y + z) := δ0 ( x + y + z). Then slice-rank F ≤ 3M, where ∑ M := a,b,c≥0 a+b+c=n b+2c≤2n/3 n! . a!b!c! Proof. In F3 , one has δ0 ( x ) = 1 − x2 . Applying this coordinate-wise, n δ0 ( x + y + z) = ∏ (1 − ( x i + y i + z i )2 ), (6.4) i =1 where the xi are the coordinates of x ∈ F3n , and so on. If we expand the right-hand side, we obtain a polynomial in 3n variables with degree 2n. We find a sum of monomials, each of the form j i j k x11 · · · xnin y11 · · · ynn z11 · · · zknn , where i1 , i2 , . . . , in , j1 , . . . , jn , k1 , . . . , k n ∈ {0, 1, 2}. Group these monomials. For each term, by the pigeonhole principle, at least one of i1 + · · · + in , j1 + · · · + jn , k1 + · · · + k n is at most 2n/3. We can write (6.4) as a sum of monomials, which we write explicitly as n ∏ (1 − ( x i + y i + z i )2 ) = i =1 ∑ i1 ,i2 ,...,in j1 ,j2 ,...,jn k1 ,k2 ,...,k n i j j k ci1 ,...,in ,j1 ,...,jn ,k1 ,...,kn x11 · · · xnin y11 · · · ynn z11 · · · zknn (6.5) where ci1 ,...,in ,j1 ,...,jn ,k1 ,...,kn is a coefficient in F3 . Then, we can group terms to write (6.5) as a sum of slice-rank 1 functions in the following way: n ∏ (1 − ( x i + y i + z i )2 ) = i =1 ∑ i i1 +···+in ≤ 2n 3 + x11 · · · xnin f i1 ,...,in (y, z) ∑ y11 · · · ynn g j1 ,...,jn ( x, z) ∑ z11 · · · zknn hk1 ,...,kn ( x, y), j1 +···+ jn ≤ 2n 3 + k1 +···+k n ≤ 2n 3 j j k where f i1 ,...,in (y, z) = ∑ j1 ,j2 ,...,jn k1 ,k2 ,...,k n j j k ci1 ,...,in ,j1 ,...,jn ,k1 ,...,kn y11 · · · ynn z11 · · · zknn , and g j1 ,...,jn ( x, z) and hk1 ,...,kn ( x, y) are similar except missing some terms to avoid overcounting. So, each monomial with degree at most 2n/3 contributes to the slice-rank 3 times, and the number of such monomials is at most M. Thus the slice-rank is at most 3M. We would like to estimate M. If we let 0 ≤ x ≤ 1, we see that Mx2n/3 ≤ (1 + x + x2 )n if we expand the right-hand side. Explicitly, Mx2n/3 ≤ ∑ a,b,c≥0 a+b+c=n b+2c≤2n/3 x b+2c n! ≤ (1 + x + x 2 ) n . a!b!c! So (1 + x + x 2 ) n ≤ (2.76)n , 0< x <1 x2n/3 M ≤ inf where we plug in x = 0.6. When this proof came out, people were shocked; this was basically a four-page paper, and demonstrated the power of algebraic methods. However, these methods seem more fragile compared to the Fourier-analytic methods we used last time. It is an open problem to extend this technique to prove a power-saving upper-bound for the size of a 4-AP-free subset of F5n (in the above arguments, we can replace F3 with any other finite field, so the choice of field does not really matter). It is also open to extend the polynomial method to corner-free sets in F2n × F2n , where corners are sets of the form {( x, y), ( x + d, y), ( x, y + d)}, or to the integers. Alternatively, we could Stirling’s formula, which would give the same bound. 6.4 Roth’s theorem with popular differences After giving a new method for 3-APs in F3n that gave a much better bound than Fourier analysis, we will now give a different proof that gives a much worse bound, but has strong consequences. This theorem involves a “popular common difference." Theorem 6.24. For all e > 0, there exists n0 = n0 (e) such that for n ≥ n0 and every A ⊆ F3n with | A| = α3n , there exists y 6= 0 such that Green (2005) |{ x : x, x + y, x + 2y ∈ A}| ≥ (α3 − e)3n . Here y is the popular common difference; this theorem obtains a lower bound on the number of 3-APs with common difference y in A. Note that α3 3n is roughly the expected number of 3-APs with common difference y if A is a random subset of F3n with size α3n . The theorem states we can find some y such that the number of 3-APs with common difference y is close to what we expect in a random set, and suggests that it is not true that the number of 3-APs is at least what we would expect in a random set. Green showed that the theorem is true with n0 = tow((1/e)O(1) ). This bound was improved by Fox–Pham to n0 = tow(O(log 1e )), using the regularity method. They showed that this bound is tight; this is an instance in which the regularity method gives the right bounds, which is interesting. This is the bound we will show. Lemma 6.25 (Bounded increments). Let α, e > 0. If α0 , α1 , . . . ∈ [0, 1] such that α0 ≥ α, then there exists k ≤ dlog2 1e e such that 2αk − αk+1 ≥ α3 − e. Proof. Otherwise, α1 ≥ 2α0 − α3 + e ≥ α3 + e. Similarly α2 ≥ 2α1 − α3 + e ≥ α3 + 2e. If we continue this process, we find αk ≥ α3 + 2k−1 e for all 1 ≤ k ≤ dlog2 1e e+1. Thus αk > 1 if k = dlog2 1e e + 1, which is a contradiction. Let f : F3n → C, and let U ≤ F3n ; this notation means that U is a subspace of F3n . Let f U ( x ) be the average of f ( x ) on the U-coset that x is in. The lemma below is related to an arithmetic analog of the regularity lemma. Lemma 6.26. For all e > 0, there exists m = tow(O(log 1e )) such that for all f : F3n → [0, 1], there exist subspaces W ≤ U ≤ F3n with codim W ≤ m such that e k f\ − f W k∞ ≤ ⊥ |U | and 2k f U k33 − k f W k33 ≥ (E f )3 − e. Fox and Pham (2019+) 2 Proof. Let e0 := 1 and ek+1 := e3−1/ek for integers k ≥ 0. Using the 2 recursion, we find that the recursion says ek−+21 = e−2 32/ek , so that ek−+21 ≤ 22 e −2 k for sufficiently large k. Let Rk := {r ∈ F3n : | fˆ(r )| ≥ ek }. Then | Rk | ≤ ek−2 , since by Parseval’s identity, ∑r | fˆ(r )|2 = E[ f 2 ] ≤ 1. 3 3 Now define Uk := R⊥ k and αk : = k f Uk k3 . Note αk ≥ (E f ) by convexity. So by the previous lemma, there exists k = O(log 1e ) such that 2αk − αk+1 ≥ (E f )3 − e. For this choice of k, let m := ek−+21 . With some computation we find m = tow(O(log 1e )). It is not too hard to check that   fˆ(r ) if r ∈ W ⊥ , c f W (r ) = 0 if r ∈ / W⊥. \ So k f − f Uk+1 k∞ ≤ maxr∈/ Rk+1 | fˆ(r )| ≤ ek+1 ≤ 3−| Rk | e ≤ e/|Uk⊥ |. So if we take W = Uk+1 and U = Uk , we are done, as codim Uk+1 ≤ | Rk+1 | ≤ m. With a regularity lemma comes a counting lemma, which is left as an exercise (it is fairly easy to prove). Define Λ3 ( f ; U ) = Ex∈F3n ,y∈U f ( x ) f ( x + y) f ( x + 2y). Lemma 6.27 (Counting lemma). Let f , g : F3n → [0, 1] and U ≤ F3n . Then |Λ3 ( f ; U ) − Λ3 ( g; U )| ≤ 3|U ⊥ | · k f[ − gk∞ . Lemma 6.28. Let f : F3n → [0, 1], with subspaces W ≤ U ≤ F3n . Then Λ3 ( f W ; U ) ≥ 2k f U k33 − k f W k33 . Proof. We use Schur’s inequality: a3 + b3 + c3 + 3abc ≥ a2 (b + c) + b2 ( a + c) + c2 ( a + b) for a, b, c ≥ 0. We find Λ( fW ; U ) = E ≥ ≥ ≥ f W ( x ) f W (y) f W (z) x,y,z form a 3-AP in the same U-coset 3 2Ex, y in same U-coset f W ( x )2 f W (y) − E f W 2 3 2E f W fU − E fW 3 , 2E f U3 − E f W where the first inequality follows from Schur’s inequality and the last follows from convexity. Theorem 6.29. For all e > 0, there exists m = tow(O(log 1e )) such that if f : F3n → [0, 1], then there exists U ≤ F3n with codimension at most m such that Λ3 ( f ; U ) ≥ (E f )3 − e. Note if n is large enough, then |U | is large enough, so there exists a nonzero “common difference" y. Proof. Choose U, W as in the regularity lemma. Then Λ3 ( f ; U ) ≥ Λ3 ( f W ; U ) − 3e ≥ 2k f U k33 − k f W k33 − 3e ≥ (E f )3 − 4e. The corresponding statement for popular differences is true in Z as well. Theorem 6.30. For all e > 0, there exists N0 = N0 (e) such that if N > N0 and A ⊆ [ N ] with | A| = αN, then there exists y > 0 such that Green (2005) |{ x : x, x + y, x + 2y ∈ A}| ≥ (α3 − e) N. A similar statement also holds for 4-APs in Z: Theorem 6.31. For all e > 0, there exists N0 = N0 (e) such that if N > N0 and A ⊆ [ N ] with | A| = αN, then there exists y > 0 such that Green and Tao (2010) |{ x : x, x + y, x + 2y, x + 3y ∈ A}| ≥ (α4 − e) N. Remark 6.32. Surprisingly, the corresponding statement for 5-APs (or longer) in Z is false. Bergelson, Host, and Kra (2005) with appendix by Ruzsa