Proof of a conjecture of Kleinberg-Sawin-Speyer

Proof of a conjecture of Kleinberg-Sawin-Speyer, Discrete Analysis 2018:13, 7 pp.

In the present paper the author constructs an $S_3$-symmetric probability distribution on $\{(a,b,c)\in\mathbb{Z}_{\geq 0}^3:a+b+c=p-1\}$ such that its marginal achieves the maximum entropy among all probability distributions on {0,1,…,p-1} with mean $(p-1)/3$. This proves a conjecture that appeared in the original preprint version of a paper of Kleinberg, Sawin and Speyer, which is being published in Discrete Analysis alongside the present paper.

Specifically, conditional on the existence of a probability distribution with the aforementioned properties, Kleinberg Sawin and Speyer established the existence of so-called tri-coloured sum-free sets in $(\mathbb{Z}/q\mathbb{Z})^n$ of size at least $\theta^{n-o(n)}$. A tri-coloured sum-free set in $(\mathbb{Z}/q\mathbb{Z})^n$ is a collection of triples $\{(a_i,b_i,c_i): a_i,b_i,c_i \in (\mathbb{Z}/q\mathbb{Z})^n\}$ such that $a_i+b_j+c_k=0$ if and only if $i=j=k$. A previous paper by Blasiak, Church, Cohn, Grochow, Naslund, Sawin and Umans, also published in Discrete Analysis, had given an upper bound of $3\theta_q^n$ on the size of such a set, where $\theta_q < q$ is a constant only depending on $q$. The upper bound of Blasiak et al., obtained using the breakthrough polynomial method of Croot-Lev-Pach and Ellenberg-Gijswijt, is therefore shown to be approximately sharp by the result in the present paper.

This matters for several reasons. First, it shows that this new polynomial method can lead to sharp bounds. In the original application to the cap set problem in $\mathbb{F}_3^n$, sharpness has not (yet) been established. Second, tri-coloured sum-free sets have connections to certain approaches to the fast matrix-multiplication problem, and to long-standing open problems in property testing. For example, Fox and Lovász used the Kleinberg-Sawin-Speyer result to prove that their polynomial bound for Green’s arithmetic triangle removal lemma, also obtained using a variant of the polynomial method, is essentially sharp. Moreover, Cohn, Kleinberg, Szegedy and Umans showed that it is impossible to achieve an exponent of $\omega=2$ for the matrix multiplication problem using sets satisfying the simultaneous triple-product property in the abelian groups $\mathbb{F}_p^n$.

The present paper therefore contributes a fundamental ingredient to a result that cements the power of the Croot-Lev-Pach polynomial method.