Volume 15 (2019) Article 8 pp. 1-7 [Note]
Matrix Rigidity and the Croot-Lev-Pach Lemma
by
Revised: October 2, 2018
Published: October 15, 2019
Our main result is a similar non-rigidity theorem for any $q^n \times q^n$ matrix $M$ of the form $M(x,y) = f(x+y)$, where $f:\mathbb{F}_q^n \to \mathbb{F}_q$ is any function and $\mathbb{F}_q$ is a fixed finite field of $q$ elements ($n$ goes to infinity). The theorem follows almost immediately from a recent lemma of Croot, Lev and Pach (2017) which is also the main ingredient in the recent solution of the famous cap-set problem by Ellenberg and Gijswijt (2017).