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