### Andres Caicedo

Shared publicly -Maths moves at a faster pace these days... only eight days after the breakthrough of Croot, Lev, and Pach obtaining for the first time an exponentially strong upper bound on the cap set problem in (Z/4Z)^n, Jordan Ellenberg has adapted the argument to the original setting of (Z/3Z)^n; we now know that the smallest capset in this space has size between 2.2174^n and 2.756^n asymptotically. (I blogged about the cap set problem in one of my first blog posts way back in 2007: https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/ .) The argument looks like it will also extend to other finite fields than Z/3Z.

Like Dvir's argument solving the finite field Kakeya problem, it ends up being a very short (3 pages) application of the polynomial method. Basically, the point is that if A is a capset (avoiding 3-term progressions), and P(x) is some polynomial that vanishes outside of -A but is nonzero for many values of -A, then the polynomial P(x+y) vanishes on all of A x A except on the diagonal, where it has a lot of nonzeroes. But this forces the rank of the matrix P(x+y) for x,y in A to be large, which in turn forces the degree of P to be large. The usual linear algebra and dimension counting of the polynomial method then finishes off the proof.

The original problem of improving the bounds in Roth's theorem remains open (much as the Euclidean Kakeya problem does), but it at least gives hope that the current logarithmic-type upper bounds for Roth's theorem (based on Fourier methods) can be improved, given that the Fourier methods have finally been dethroned from their long-held title as claimants to the strongest quantitative bounds in the finite field setting.

Like Dvir's argument solving the finite field Kakeya problem, it ends up being a very short (3 pages) application of the polynomial method. Basically, the point is that if A is a capset (avoiding 3-term progressions), and P(x) is some polynomial that vanishes outside of -A but is nonzero for many values of -A, then the polynomial P(x+y) vanishes on all of A x A except on the diagonal, where it has a lot of nonzeroes. But this forces the rank of the matrix P(x+y) for x,y in A to be large, which in turn forces the degree of P to be large. The usual linear algebra and dimension counting of the polynomial method then finishes off the proof.

The original problem of improving the bounds in Roth's theorem remains open (much as the Euclidean Kakeya problem does), but it at least gives hope that the current logarithmic-type upper bounds for Roth's theorem (based on Fourier methods) can be improved, given that the Fourier methods have finally been dethroned from their long-held title as claimants to the strongest quantitative bounds in the finite field setting.

2

Add a comment...