Strong Bounds for Skew-Corner-Free Sets

Abstract

Motivated by applications to matrix multiplication algorithms, Pratt asked (ITCS'24) how large a subset of $[n]\times [n]$ could be without containing a skew-corner: three points $(x,y),(x,y+h),(x+h,y^{\prime })$ with $h\ne 0$. We prove any skew corner-free set has size at most $\exp (-\hat{I}\text{c◯}({\log }^{1/12}n))\cdot n^2$, nearly matching the best known lower bound of $\exp (-O(\sqrt{\log n}))\cdot n^2$ by Beker (arXiv'24). Our techniques generalize those of Kelley and Meka's recent breakthrough on three-term arithmetic progression (FOCS'23), answering a question of Beker (arXiv'24). We note that a similar bound was obtained concurrently and independently by Milićević (arXiv'24).

27 pages, updated for publication in Discrete Analysis