The last few weeks have seen amazing results in additive combinatorics, where following a breakthrough by Croot, Lev and Pach, several longstanding open questions have been resolved using short simple proofs. I haven’t been following this progress, but fortunately Bobby Kleinberg gave an excellent talk yesterday in our reading group about some of these works, and their relations to TCS questions such as approaches for fast matrix multiplication. Since the proofs are short and these results also been extensively blogged about, what follows is mainly for my own benefit.
Among other things, Bobby showed the proof of the following result, that demonstrates much of those ideas:
Theorem: (Ellenberg and Gijswijt, building on Croot-Lev-Pach) There exists an absolute constant such that for every , if then contains a 3-term arithmetic progression.
To put this in perspective, up till a few weeks ago, the best bounds were of the form and were shown using fairly complicated proofs, and it was very reasonable to assume that a bound of the form is the best we can do. Indeed, an old construction of Behrend shows that this is the case in other groups such as the integers modulo some large or where is some large value depending on . The proof generalizes to for every constant prime (and for composite order cyclic groups as well).
The proof is extremely simple. It seems to me that it can be summarized to two observations:
- Due to the algebraic structure of the problem, one can “interpolate” in some sense a -a.p. free set with a polynomial of degree that is a half as small than you would expect otherwise.
- Due to concentration of measure phenomena in finite fields, this constant multiplicative factor makes a huge difference. There are values for which polynomials of degree make up all but an exponentially small fraction of the functions from to , while polynomials of degree only constitute an exponentially small fraction of these functions.
Let’s now show the proof. Assume towards a contradiction that satisfies ( can be some sufficiently small constant, will do) but there do not exist three distinct points that form a -a.p. (i.e., such that or, equivalently, ).
Let be the number of -variate monomials over where each variable has individual degree at most (higher degree can be ignored modulo ) and the total degree is at most . Note that there are possible monomials where each degree is at most two, and their degree ranges from to , where by concentration of measure most of them have degree roughly . Indeed, using the Chernoff bound we can see that if is a sufficiently small constant, we can pick some such that if then but (to get optimal results, one sets to be roughly and derives from this value).
Now, if we choose in that manner, then we can find a polynomial of degree at most that vanishes on but is non zero on at least points. Indeed, finding such a polynomial amounts to solving a set of linear equations in variables.1 Define the matrix such that . Since the assumption that implies that , the theorem follows immediately from the following two claims:
Claim 1: .
Claim 2: .
Claim 1 is fairly immediate. Since is -a.p. free, for every , is not in and hence is zeros on all the off diagonal elements. On the other hand, by the way we chose it, has at least nonzeroes on the diagonal.
For Claim 2, we expand as a polynomial of degree in the two variables and , and write where corresponds to the part of this polynomial where the degree in is at most and corresponds to the part where the degree in is larger and hence the degree in is at most . We claim that both and are at most . Indeed, we can write as for some coefficients and polynomials , where indexes the monomials in of degree at most . But this shows that is a sum of at most rank one matrices and hence . The same reasoning shows that thus completing the proof of Claim 2 and the theorem itself.
More formally, we can argue that the set of degree polynomials that vanish on has dimension at least and hence it contains a polynomial with at least this number of nonzero values.↩