Sumsets as unions of sumsets of subsets

Sumsets as unions of sumsets of subsets, Discrete Analysis 2017:14, 5 pp.

In May 2016 there was a remarkable development in additive combinatorics. First, Croot, Lev and Pach managed to use the so-called polynomial method to obtain an exponentially small upper bound for a problem closely related to the cap-set problem, a major open problem in the area. Then within a couple of weeks, Jordan Ellenberg and Dion Gijswijt independently saw how to adapt the Croot-Lev-Pach argument to solve the cap-set problem itself. This was reported on in several places, including a blog post on this website. Soon after that, Terence Tao found a beautiful way of expressing the argument in terms of a concept that came to be called slice rank, which clarified the previous proofs and led quickly to further results.

The theorem of Ellenberg and Gijswijt implies that there is a constant $c<1$ such that for every prime $p$ and every positive integer $n$, the largest subset of $\mathbb F_p^n$ that does not contain distinct elements $x,y,z$ such that $x+y=2z$ has density at most $c^n$. One of the further results, proved in [1,2] is the following statement. Let $(a_1,\dots,a_m), (b_1,\dots,b_m)$ and $(c_1,\dots,c_m)$ be three sequences of elements of $\mathbb F_p^n$ such that $a_i+b_i+c_i=0$ for every $i$ and such that there are no other triples $(i,j,k)$ with $a_i+b_j+c_k=0$. Then $m\leq(cp)^n$. Note that if $(a_1,\dots,a_m)$ is a list of the elements of a set $A$ in some order and we set $b_i=a_i$, $c_i=-2a_i$ for each $i$, then we recover the previous theorem. This generalization has applications to questions about the complexity of matrix multiplication.

In the present paper, Ellenberg proves a result that generalizes the results just mentioned and some others. Roughly, it states that a sumset $A+B$ of two subsets of $\mathbb F_p^n$ can be expressed as a union of two much more efficient sumsets. More precisely, if $A$ and $B$ are subsets of $\mathbb F_p^n$, then there are subsets $A'\subset A$ and $B'\subset B$ such that the sumset $A+B$ is equal to the union of the sumsets $A+B'$ and $A'+B$, and such that $A'$ and $B'$ both have density at most $c^n$, where this $c$ is essentially the same as the $c$ above.

To see why this implies the bound for the cap-set problem, let $A=B$ and suppose that $A$ does not contain three distinct elements $x,y,z$ with $x+z=2y$. Then for each $x\in A$ the element $2x$ belongs to $A+A$, and moreover can be expressed as an element of $A+A$ in exactly one way – as $x+x$. If $A'$ and $A''$ are subsets of $A$, then $(A+A')\cup(A''+A)=A+(A'\cup A'')$, and the intersection of this with $\{2x:x\in A\}$ is, by the remark we have just made, the set $\{2x':x'\in A'\cup A''\}$. But by Ellenberg’s result we can choose $A'$ and $A''$ of density at most $c^n$ such that it is also $\{2x':x'\in A\}$, from which it follows that $A'\cup A''=A$ and therefore that $A$ has density at most $2c^n$.

The proof of this result about sumsets is along similar lines to the proofs of the earlier results, but there is an extra ingredient in the form of a result of Meshulam about the structure of spaces of low-rank matrices.

[1] Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans, On cap sets and the group-theoretic approach to matrix multiplication, Discrete Analysis 2017:3, 27 pp.

[2] Robert Kleinberg, A nearly tight upper bound on tri-colored sum-free sets in characteristic 2, arXiv:1605.08416