The growth rate of tri-colored sum-free sets

The growth rate of tri-colored sum-free sets, Discrete Analysis 2018:12, 10 pp.

This paper contributes to the remarkable collection of results that followed in the wake of the 2016 breakthrough by Ellenberg and Gijswijt on the cap set problem, which asks for the maximal size of a 3-term progression-free subset of $\mathbb{F}_3^n$. The polynomial method of Ellenberg and Gijswijt, who followed the lead of Croot, Lev, and Pach after whom the method is now named, showed for the first time that the size of such a set is bounded by a polynomial in the size of the ambient space. More specifically, they showed that a cap set in $\mathbb{F}_3^n$ can be of size at most $(2.756)^n$.

This paper considers a variant of the cap set problem, namely the question of how large a tri-coloured sum-free subset of $\mathbb{F}_3^n$ can be. By a tri-coloured sum-free subset we mean a collection of triples $(a_i,b_i,c_i)$ in $(\mathbb{F}_3^n)^3$ such that $a_i+b_j+c_k=0$ if and only if $i=j=k$. Note that a cap set $A\subseteq \mathbb{F}_3^n$ gives rise to a tri-coloured sum-free set, namely the collection of triples $\{(a,a,a): a\in A\}$.

It is therefore not entirely surprising that the Croot-Lev-Pach polynomial method can be used to show that if $q$ is a prime power, then a tri-coloured sum-free set in $\mathbb{F}_q^n$ can have size at most $3\theta^n$, where $\theta$ is the solution to an explicit optimisation problem. This is one of the results appearing in the paper “On cap sets and the group-theoretic approach to matrix multiplication”, by Blasiak, Church, Cohn, Grochow, Naslund, Sawin, and Umans, which Discrete Analysis published earlier this year.

In the present paper the authors show this bound to be tight to within a subexponential factor. The lower bound is based on a construction of an $S_3$-symmetric probability distribution on $\{(a,b,c)\in\mathbb{Z}_{\geq 0}^3:a+b+c=n\}$ such that its marginal achieves the maximum entropy among all probability distributions on $\{0,1,…,n\}$ with mean $n/3$. In answer to a conjecture which was posed in the original preprint version of this article, the existence of such a distribution was established by Pebody, whose article is being published in Discrete Analysis alongside the present paper.

The question of whether the Croot-Lev-Pach polynomial method also yields a tight bound for the cap set problem remains open.