Sumsets as unions of sumsets of subsets

- Department of Mathematics, UW-Madison
- More about Jordan S. Ellenberg

*Discrete Analysis*, September. https://doi.org/10.19086/da.2103.

### Editorial introduction

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 Fnp that does not contain distinct elements x,y,z such that x+y=2z has density at most cn. One of the further results, proved in [1,2] is the following statement. Let (a1,…,am),(b1,…,bm) and (c1,…,cm) be three sequences of elements of Fnp such that ai+bi+ci=0 for every i and such that there are no other triples (i,j,k) with ai+bj+ck=0. Then m≤(cp)n. Note that if (a1,…,am) is a list of the elements of a set A in some order and we set bi=ai, ci=−2ai 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 Fnp can be expressed as a union of two much more efficient sumsets. More precisely, if A and B are subsets of Fnp, then there are subsets A′⊂A and B′⊂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 cn, 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∈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′)∪(A″+A)=A+(A′∪A″), and the intersection of this with {2x:x∈A} is, by the remark we have just made, the set {2x′:x′∈A′∪A″}. But by Ellenberg’s result we can choose A′ and A″ of density at most cn such that it is also {2x′:x′∈A}, from which it follows that A′∪A″=A and therefore that A has density at most 2cn.

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