The polynomial that bounds the caps

Twenty cards with no set among them asks how large a cap can be — a set of points in $(\mathbb{Z}/3)^n$ with no three on a line, which is the same as no three distinct points adding to nought. The largest caps are known up to dimension six, and in general they grow like $\lambda^n$ for an unknown $\lambda$ at least about $2.22$. The question that essay leaves is whether $\lambda$ is less than $3$: whether a cap must be an exponentially small part of the space, or merely a part that shrinks like a power of the dimension.

For forty years the second was all anybody could prove. Roy Meshulam’s bound of 1995 showed a cap has at most about $2 \cdot 3^n/n$ points, by the Fourier-analytic method Klaus Roth had used on progressions in the integers, and fifteen years of effort by strong mathematicians improved the $n$ only to $n^{1.0001}$ or so. Then, in May 2016, Ernie Croot, Vsevolod Lev and Péter Pál Pach found an exponential bound for a closely related problem in $(\mathbb{Z}/4)^n$, Jordan Ellenberg and Dion Gijswijt adapted their idea to caps within days, and the result was this:

$$|A| \le 3\,M(n), \qquad M(n) = \#\{\text{monomials in } n \text{ variables, each exponent} \le 2, \text{ of total degree} \le 2n/3\},$$

which grows like $2.7551^n$. The proof fits on a page. Every step of it can be drawn, and none of it looks at the cap except to use the fact that it is one.

A table that is diagonal on a cap #

Start from what a cap is. For points $x$, $y$, $z$ of a set $A$, the sum $x + y + z$ is nought in two situations: when the three form a line, and when they are the same point, since $3x = 0$ modulo three. A cap has no lines, so on a cap $x + y + z = 0$ happens only when $x = y = z$.

Record that in a three-dimensional table indexed by $A \times A \times A$, with a one wherever $x + y + z = 0$ and a nought elsewhere.

Over the cap of four in the figure the table is diagonal: the four cells where all three indices agree are filled, and nothing else. Over four points containing a line it is not, because the line’s three points add to nought in all six orders. A diagonal table with nonzero entries on its diagonal is, in the right sense, as large as its side: it is a three-dimensional version of an identity matrix, and an identity matrix of size $|A|$ has rank $|A|$. The whole proof consists of showing that the table has another description that forces its rank to be small — so that $|A|$, being the rank, must be small too.

One polynomial that computes the table #

Over the integers mod 3, a number $c$ satisfies $1 - c^2 = 1$ if $c = 0$ and $1 - c^2 = 0$ otherwise, because $1^2 = 1$ and $2^2 = 4$ both leave remainder one on division by three. That is the indicator trick the count of solutions divisible by $p$ is built on, with $q - 1 = 2$. Multiplying over the coordinates gives a polynomial that is one exactly when a whole vector is nought:

$$F(x, y, z) = \prod_{i=1}^{n} \bigl(1 - (x_i + y_i + z_i)^2\bigr).$$

It is one when $x + y + z = 0$ and nought otherwise, so on $A \times A \times A$ it is the table. It has degree $2n$, since each factor has degree two, and that degree is the whole of what the proof will use: a polynomial that detects “nought” in every coordinate at once cannot help having degree twice the dimension, and the question is whether degree $2n$ spread across three sets of variables is small. And because $t^3 = t$ for every $t$ in the field, any exponent of three or more can be reduced, so every monomial in $F$ can be written with each variable raised to a power of at most two.

Expand the product. Each monomial is a product of powers of the $x_i$, the $y_i$ and the $z_i$, and it has an $x$-part, a $y$-part and a $z$-part — the degrees of the three kinds of variable in it — which add up to at most $2n$.

Three parts that cannot all be large #

Here is the one idea the proof needs, and it is a pigeonhole.

If three numbers add to at most $2n$, they cannot all be larger than $2n/3$. So every monomial of $F$ has at least one part of degree at most $2n/3$. Sort the monomials into three piles by that part — the ones whose $x$-part is small, then of the rest the ones whose $y$-part is small, then the ones whose $z$-part is small — and every monomial lands in a pile, as the triangle of dots shows for $n = 3$.

Now group the first pile by its $x$-part. Every monomial there is $x^a$ times something in $y$ and $z$, where $x^a$ is a monomial of degree at most $2n/3$ with exponents at most two. So the first pile is a sum

$$\sum_{a} x^a \, g_a(y, z)$$

over the allowed $x$-monomials $x^a$, and there are exactly $M(n)$ of those. The second pile is similarly a sum of at most $M(n)$ terms $y^b\, h_b(x, z)$, and the third of at most $M(n)$ terms $z^c\, k_c(x, y)$. So the table has been written as a sum of at most $3M(n)$ pieces, each of the form a function of one variable times a function of the other two.

Slice rank: why a diagonal table cannot be that cheap #

A piece of the form $f(x)\, g(y, z)$ is called a slice, and the smallest number of slices adding up to a table is its slice rank. The polynomial has just shown that the slice rank of the cap’s table is at most $3M(n)$. The last step, in Terence Tao’s formulation of the argument a few weeks after it appeared, is that a diagonal table with nonzero entries on its diagonal has slice rank exactly equal to its side.

For two-dimensional tables this is the familiar statement that the rank of a matrix — the fewest pieces $f(x)\, g(y)$ that add up to it — is the size of an identity matrix. In three dimensions the proof takes one more step. Suppose the diagonal table were a sum of fewer than $|A|$ slices. The $x$-slices use some functions $f_1(x), f_2(x), \dots$, fewer of them than $|A|$, so there is a function $v$ on $A$ that is orthogonal to all of them and is nonzero at more points of $A$ than there are $y$- and $z$-slices together — a dimension count on the functions on $A$ provides one. Summing the table against $v$ in the $x$ variable kills every $x$-slice and leaves a two-dimensional table in $y$ and $z$: diagonal, with $v$’s values on the diagonal, so of rank equal to the number of points where $v$ is nonzero. But it is written with only the $y$- and $z$-slices, fewer pieces than that rank, which is impossible.

Put the two together. The cap’s table is diagonal with ones on its diagonal, so its slice rank is $|A|$. It is also computed by a polynomial that splits into at most $3M(n)$ slices. So

$$|A| \le 3\,M(n).$$

That is the whole proof, and the only thing in it that depends on the dimension is $M(n)$.

The argument run by hand in one and two dimensions #

It is worth running the proof where every term can be written out, because it shows both how it works and how weak it is in small cases.

In one dimension the polynomial is $F = 1 - (x + y + z)^2$. Expanded modulo three, where $-2 \equiv 1$, it is

$$F = 1 - x^2 - y^2 - z^2 + xy + yz + zx.$$

The degree bound is $2n/3 = \tfrac23$, so a part counts as small only if its degree is nought. Every term has at least one variable missing — the constant has all three missing, $x^2$ is missing $y$ and $z$, $xy$ is missing $z$ — so every term has a small part, and the piles are: terms with no $x$, which are $1 - y^2 - z^2 + yz$, a slice with the constant function $1$ in $x$; terms with an $x$ but no $y$, which are $-x^2 + zx$, a slice with the constant $1$ in $y$; and the one term with both, $xy$, which has no $z$. Three slices, each using the single allowed monomial $1$, so $M(1) = 1$ and the bound is $|A| \le 3$. The truth is two. The argument has done its job and wasted a point.

In two dimensions the allowed monomials are those of degree at most $\tfrac43$, which is $1$, $x_1$ and $x_2$, so $M(2) = 3$ and the bound is $9$ — the whole plane. It says nothing at all. It takes until dimension four for the bound to fall below the space ($45$ against $81$), and until the thirties for it to beat the Fourier bound. A method that proves the exponential theorem in a page proves nothing useful about any case a person could check by hand, which is the reverse of the usual relation between small cases and theorems, and part of why the idea took so long to be tried.

Counting the monomials #

$M(n)$ counts the vectors of exponents $(a_1, \dots, a_n)$ with each $a_i$ in $\{0, 1, 2\}$ and sum at most $2n/3$. All $3^n$ exponent vectors, sorted by their sum, make a bell curve centred on $n$.

The cut at $2n/3$ lies a third of the way from the centre towards the bottom of the range. Each exponent is $0$, $1$ or $2$ with average $1$, so the sum of $n$ of them concentrates around $n$ with a spread of about $\sqrt{2n/3}$ — the same concentration that makes a bell curve out of coin flips — and a cut a distance $n/3$ below the centre is about $\sqrt{n/6}$ spreads away. The share below it therefore falls exponentially — not the bell curve’s own rate, since a deviation proportional to $n$ is governed by the large deviations of the tail rather than by the bell, but exponentially all the same. At twelve variables the share is already $10.9\%$; at sixty it is about one part in 350.

The rate has a clean formula. Counting vectors with sum at most $2n/3$ is bounded by the standard trick of weighting each exponent by $t^{a}$ for a $t$ below one: $M(n) \le (1 + t + t^2)^n / t^{2n/3}$ for every $t$ in $(0, 1)$, and choosing the best $t$ gives

$$M(n)^{1/n} \to \min_{0 < t < 1} \frac{1 + t + t^2}{t^{2/3}} = 2.7551\ldots,$$

attained near $t = 0.593$. So the bound $3M(n)$ grows like $2.7551^n$, while the space grows like $3^n$.

Watching the bound fall behind #

In small dimensions the bound is useless. At $n = 4$ it gives $45$, more than twice the true $20$ and more than half the space; at $n = 6$ it gives $504$ against a true $112$. It overtakes Meshulam’s $3^n/n$ only past dimension thirty. By dimension sixty it is one part in 354 of the space, and by dimension six hundred it is about one part in $10^{23}$ — the power of an exponential rate, which no bound that shrinks like a power of $n$ can match however far it is pushed. Its virtue is entirely in the slope: on a logarithmic scale it is a line less steep than the space’s, so the gap between them grows without limit, and the cap’s share of the space, at most $3M(n)/3^n$, shrinks like $(2.7551/3)^n \approx 0.918^n$ — exponentially.

The approach to the limit is slow — the $n$-th root is still $2.745$ at a thousand variables — because $M(n)$ carries a factor that is a power of $n$ in front of its exponential, and a power of $n$ affects the $n$-th root only through a correction of order $\log n / n$. Every value is below the limit, since the optimised weighting bound is an upper bound at every $n$.

Why forty years of Fourier analysis missed it #

The polynomial argument is strange in two ways, and both are the reason it was surprising.

It never uses the cap’s size to find structure. The Fourier method Meshulam used works by density increment: a large cap must correlate with some hyperplane, so pass to a slice where it is denser and repeat. Each step gains a little, the gains add up to a factor of $n$, and nobody could make them compound. The polynomial method gains nothing step by step. It writes down one object that knows the cap is a cap — the diagonal table — and compares two counts of its size, one from the diagonal and one from the degrees.

And it bounds the wrong thing, on purpose. The slice rank of the table is at most $3M(n)$ whatever the set $A$ is; the argument’s only use of the cap is to make the table diagonal. That is why it is so short, and also why it cannot be sharp: it does not see which points are in the cap beyond the absence of lines. It is the same move Dvir made for Kakeya sets in 2008 — find a polynomial of low degree that vanishes where the set is, and show that low degree is incompatible with the set’s size — and Cauchy–Davenport’s polynomial proof is its oldest ancestor. The method had been available for a decade. What nobody had seen was that a three-variable table could be split by degree into slices.

What else fell to the same page #

The argument was generalised within weeks, and each generalisation is the same three moves with a different table.

For any prime $p$, a set in $(\mathbb{Z}/p)^n$ with no three-term progression has at most $c_p^{\,n}$ points for a constant $c_p < p$ — the same proof, with $1 - c^{p-1}$ as the indicator and the degree cut at $(p-1)n/3$. The problem Croot, Lev and Pach solved first, progressions in $(\mathbb{Z}/4)^n$, needed a slightly different indicator because $\mathbb{Z}/4$ is not a field. Eric Naslund and William Sawin used the method in 2017 to bound sunflower-free families of subsets — collections in which no three sets have pairwise intersections all equal — settling an exponential form of a question Paul Erdős and Endre Szemerédi had asked in 1978. And the slice-rank lemma itself became a tool in the study of matrix multiplication, where the rank of three-dimensional tables is exactly what decides how fast two matrices can be multiplied.

What did not fall is the original question for the integers. A set of whole numbers up to $N$ with no three-term progression can be far larger than any power $N^{c}$ with $c < 1$ — Felix Behrend built ones of size $N^{1 - o(1)}$ in 1946 — so no polynomial bound of this shape can hold there, and the progressions in the integers needed quite different ideas. The finite-field version was easier because the space has so much linear structure that degree can be counted.

What the pictures cannot show #

The slice-rank lemma. The figures show a diagonal table over a cap of four and a pigeonhole over the degrees; they do not show that a diagonal table cannot be written with fewer slices than its side. That lemma is proved by induction, not drawn, and it is the step on which the whole bound rests.

Any cap near the bound. The bound is not sharp and the figures do not suggest otherwise: the largest caps known sit far below it in every dimension drawn, and the true growth rate is somewhere between about $2.22$ and $2.7551$.

The limit. The rate figure reaches three thousand variables and $2.752$; the limit $2.7551$ is the minimum of a one-variable function, computed rather than seen.

That the argument is a proof at all. The simplex figure shows that every split of a degree has a small part, for one value of $n$; the monomial histogram counts the small monomials for one value of $n$. Neither shows the chain of reasoning that joins them — that the table equals the polynomial on the cap, that the polynomial splits into slices, that slices bound the rank. Each figure is a check of one link, not of the chain.

Still open: whether 2.7551 can be beaten #

The bound is best possible for a looser problem, and that is the strongest evidence that a new idea is needed to improve it. A tri-coloured sum-free set is a collection of triples $(x_i, y_i, z_i)$ with $x_i + y_j + z_k = 0$ exactly when $i = j = k$ — the diagonal condition without requiring the three coordinates to come from one set. The slice-rank argument bounds these by $3M(n)$ just as well, and Robert Kleinberg, William Sawin and David Speyer, with a construction completed by Sergey Norin and by Luke Pebody, showed in 2018 that tri-coloured sum-free sets of size $2.7551^n$ really exist. So any argument that works equally for tri-coloured sets can never prove a better bound for caps.

Whether caps themselves grow at a rate below $2.7551$ is not known, and nor is the rate. The best constructions give about $2.2202^n$, found in 2023 with the help of a computer search over structured caps in modest dimensions. A proof that caps are much smaller than tri-coloured sets would have to use the fact that $x$, $y$ and $z$ come from the same set — the one thing the polynomial argument deliberately forgets.