Recent advances in the polynomial method

This page is an attempt to collect links to and brief summaries of all the papers, blog posts, etc., that relate to the recent advances in the polynomial method which began with the paper of Croot, Lev, and Pach in May 2016. Any corrections or suggestions for other material that should be included are encouraged via email to tb634@cam.ac.uk.

Brief summaries of the papers are included to help navigation. Any errors are entirely my own, and any confusion should be immediately correctable by following the links and consulting the papers themselves.

Definitions

The cap set problem asks for bounds on the largest cap set, i.e. a set \( A\subset \mathbb{F}_3^n\) such that the only solutions to \( a+b+c = 0 \) are the trivial ones with \( a=b=c\). This has a natural generalisation to any finite abelian group \( H\), though in general we need to consider the translation invariant equation \( a+b=2c\).

An alternative generalisation is to a tri-coloured sum-free set, which are three (possibly distinct) sets \(A,B,C\subset H\) together with a perfect matching \( M\subset A\times B\times C\) such that \( a+b+c=0\) if and only if \((a,b,c)\in M\). A cap set is the case with \(A=B=C\) and \( M\) the diagonal matching. When bounding the size of the tri-coloured sum-free set, we mean to bound the size of the matching, \(\lvert M\rvert\).

A \(k\)-sunflower is a collection of \(k\) sets such that the intersection of any two sets is the same. A family of sets is \(k\)-sunflower free if it contains no \(k\)-sunflower. The strong sunflower conjecture states that if \(\lvert A\rvert\leq m\) for all \(A\in \mathcal{F}\) and \( \mathcal{F}\) is \(k\)-sunflower free then \( \lvert \mathcal{F}\rvert < C_k^m\). The weak sunflower conjecture states that if \( A\subset \{1,\ldots,n\}\) for all \(A\in\mathcal{F}\) then there exists \(c<2\) such that \(\lvert \mathcal{F}\rvert < c^n\). The case \(k=3\) is the first non-trivial case, and often when dependence on \(k\) is omitted it is this case that is meant. The weak sunflower conjecture for \(k=3\) follows from the Ellenberg-Gijswijt bound and work of Alon-Shpilka-Umans (see this paper).

Papers

On cap sets and the group-theoretic approach to matrix multiplication -- Blasiak-Church-Cohn-Grochow-Naslund-Sawin-Umans -- PDF.

This paper generalises the results on the cap set problem to deal with tri-coloured sum-free sets in any abelian group of bounded exponent, say \(m\), showing that \(\lvert M\rvert \ll \lvert H\rvert^{1-\epsilon/m}\) for some absolute constant \(\epsilon >0\) (see also the paper by Petrov below). The authors then use this to rule out one possible approach to improving the exponent of matrix multiplication, namely using the simultaneous triple product property (STPP) for abelian groups of bounded exponent.

The polynomial method and application to tri-coloured sum-free sets appear in Section 4; Sections 2-3 discuss the STPP property and relationship to matrix multiplication and tri-coloured sum-free sets.

Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small -- Croot-Lev-Pach -- PDF.

The paper that began it all, in which the authors show that any \(A\subset (\mathbb{Z}/4\mathbb{Z})^n\) free of three-term arithmetic progressions has size \(\lvert A\rvert < 4^{cn}\), for some \(c\approx 0.926\). The key ideas that began the recent surge of the polynomial method are contained in Lemma 1 and its proof.

A remark on sumsets in \(\mathbb{F}_q^n\) -- Ellenberg -- PDF.

A note in which Ellenberg uses the polynomial method to show that, for any \( S\subset \mathbb{F}_q^n\), there is a set \( S'\subset S\) of size at most \( c_q^n\) for some \( c_q < q \) such that \( S'+S=S+S \), from which the cap set bounds immediately follow. This is also discussed in a blog post.

On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression -- Ellenberg-Gijswijt -- PDF.

A few days after the Croot-Lev-Pach paper, Ellenberg and Gijswijt independently realised how to use the new method to obtain exponential upper bounds for subsets of \(\mathbb{F}_3^n\) without three-term arithmetic progressions. This (3 page!) self-contained paper gives the proof, showing that such \(A\) must satisfy \(\lvert A\rvert < 2.756^n\). For good measure they also generalise to any three variable translation invariant equation over \(\mathbb{F}_q^n\) for any \(q\), with similar strength bounds.

A tight bound for Green's arithmetic triangle removal lemma in vector spaces -- Fox-Lovasz -- PDF.

This paper shows that if \(X,Y,Z \subset \mathbb{F}_p^n\) has fewer than \( (\epsilon/3)^{C_p}p^{2n}\) solutions to \( x+y+z=0\) then we can remove \( \epsilon p^n\) elements from \( X\cup Y\cup Z\) so that no solution remains. Furthermore, the constant \( C_p\) is explicitly given and this bound is tight in its dependence on \( \epsilon\). By contrast, the previous best-known dependence on \(\epsilon\) was of tower type! This paper applies the result of Kleinberg-Sawin-Speyer below to obtain the sharp constants, though the existence of some polynomial bound follows from the earlier cap set work and a simple product trick.

A nearly tight upper bound on tri-colored sum-free sets in characteristic 2 -- Kleinberg -- PDF.

This paper proves that, in \(\mathbb{F}_2^n\), a tri-coloured sum-free set has size \( \lvert M\rvert \leq 6\binom{n}{\lfloor n/3\rfloor} \). It further shows this upper bound is almost tight, constructing such sets of size at least \(\binom{n}{\lfloor n/3\rfloor}c^{-\sqrt{n}}\) for some absolute constant \(c>0\).

The growth rate of tri-colored sum-free sets -- Kleinberg-Sawin-Speyer -- PDF.

This paper shows that all tri-coloured sum-free sets in \( \mathbb{F}_p^n\) have size at most \( C_p^n\), where \( C_p\) is some explicitly defined constant \( < p\). Furthermore, this constant is sharp, and the paper also constructs tri-coloured sum-free sets with size at least \( C_p^{n}\cdot c_p^{-\sqrt{n}}\).

Sárközy's theorem in function fields -- Green -- PDF.

This paper uses the polynomial method to give a short proof that if \(k\geq 2\) and \( A\subset \mathbb{F}_q[t]_{\deg < n}\) contains no distinct \(p,q\in A\) such that \(p-q=b^k\) then \( \lvert A\rvert \ll q^{(1-c_{k,q})n}\), where the constant \( c_{k,q}\) is quite explicit. This is a function field analogue of Sárközy's theorem which concerns a similar situation in the integers, where the bounds are much weaker.

Upper bounds for sunflower-free sets -- Naslund-Sawin -- PDF.

To write.

A distribution on triples with maximum entropy marginal -- Norin -- PDF.

To write.

Proof of a conjecture of Kleinberg-Sawin-Speyer -- Pebody -- PDF.

To write.

Many zero divisors in a group ring imply bounds on progression-free subsets -- Petrov -- PDF.

To write.

Blog posts

All of the links below are to blog posts on mathematical blogs by mathematicians reporting on the polynomial method and its applications. I won't attempt to make (necessarily largely arbitrary) distinctions between reporting, exposition, and new material. They are grouped alphabetically by author for your own exploration. In particular, there are often interesting ideas and suggestions in the comment sections.

Bienvenu