Proof of a Conjecture of Kleinberg-Sawin-Speyer

Abstract

In Ellenberg and Gijswijt's groundbreaking work, the authors show that a subset of ${\mathbb{Z}}_3^n$ with no arithmetic progression of length 3 must be of size at most $2.755^n$ (no prior upper bound was known of $(3-\epsilon {)}^n)$), and provide for any prime $p$ a value ${\lambda }_p<p$ such that any subset of ${\mathbb{Z}}_p^n$ with no arithmetic progression of length 3 must be of size at most ${\lambda }_p^n$. Blasiak et al showed that the same bounds apply to tri-coloured sum-free sets, which are triples $\{(a_i,b_i,c_i):a_i,b_i,c_i\in {\mathbb{Z}}_p^n\}$ with $a_i+b_j+c_k=0$ if and only if $i=j=k$. Building on this work, Kleinberg, Sawin and Speyer gave a description of a value ${\mu }_p$ such that no tri-coloured sum-free sets of size $e^{{\mu }_{p}n}$ exist in ${\mathbb{Z}}_p^n$, but for any $\epsilon >0$, such sets of size $e^{({\mu }_p-\epsilon )n}$ exist for all sufficiently large $n$. The value of ${\mu }_p$ was left open, but a conjecture was stated which would imply that $e^{{\mu }_p}={\lambda }_p$, i.e. the Ellenberg-Gijswijt bound is correct for the sum-free set problem. The purpose of this note is to close that gap. The conjecture of Kleinberg, Sawin and Speyer is true, and the Ellenberg-Gijswijt bound is the correct exponent for the sum-free set problem.

Published in Discrete Analysis

References in corpus (3)

• Progression-free sets in Z_4^n are exponentially small
• On cap sets and the group-theoretic approach to matrix multiplication
• The Growth Rate of Tri-Colored Sum-Free Sets

Cited by in corpus (4)

• On cap sets and the group-theoretic approach to matrix multiplication
• The Growth Rate of Tri-Colored Sum-Free Sets
• A lower bound for the $k$-multicolored sum-free problem in ${\mathbb{Z}}_m^n$
• Universal points in the asymptotic spectrum of tensors