Strong bounds for skew-corner-free sets

Strong bounds for skew-corner-free sets, Discrete Analysis 2025:20, 27 pp.

Roth’s theorem on arithmetic progressions, proved in 1953, is a central result that has driven many developments in additive combinatorics. It states that for every $\delta>0$ there exists a positive integer $N$ such that every subset of $\{1,2,\dots,N\}$ of size at least $\delta N$ contains an arithmetic progression of length 3. Roth’s argument showed that a bound $\delta\geq C/\log\log N$ suffices for the conclusion to hold. After a long sequence of improvements, the bound $C/\log\log N$ was eventually reduced to a bound of the form $\exp(-c(\log N)^{1/12})$ by Kelley and Meka (subsequently refined to $\exp(-c(\log N)^{1/9})$ by Bloom and Sisask). This matches the form of the best known lower bound of $\exp(-c(\log N)^{1/2})$ that comes from a construction of Behrend in 1946 (which has been slightly improved since, but still with this form of bound).

In 1974, Ajtai and Szemerédi proved a generalization of Roth’s theorem that has come to be known as the corners theorem. A corner in $\mathbb Z^2$ is a set of the form $\{(x,y),(x+d,y),(x,y+d)\}$ for some $d>0$. Ajtai and Szemerédi proved that for every $\delta>0$ there exists $N$ such that every subset $A$ of $\{1,2,\dots,N\}^2$ of size at least $\delta N^2$ contains a corner. It is an easy exercise to prove that the corners theorem implies Roth’s theorem (qualitatively speaking): the key observation is that if $A$ is a set of integers with no arithmetic progression of length 3, then $\{(x,y):x-y\in A\}$ is a subset of $\mathbb Z^2$ with no corner. However, good quantitative estimates for the corners theorem have proved hard to come by. The initial argument of Ajtai and Szemerédi used Szemerédi’s theorem (the generalization of Roth’s theorem to longer arithmetic progressions) at each step of an iteration, which yields log-star-type bounds even if the best-known bounds for Szemerédi’s theorem are used. Later it was noted by Solymosi that a proof of Roth’s theorem by Ruzsa and Szemerédi, which used Szemerédi’s regularity lemma, could be modified to yield a proof of the corners theorem, but this proof also gave log-star-type bounds. Then in 2005, Shkredov obtained the first “reasonable” estimate – a bound of the form $O((\log\log N)^{-c})$.

There matters stood still for a long time, but recently attention turned to a problem that is slightly easier, but still not wholly easy. A skew corner is defined to be a subset of $\mathbb Z^2$ of the form $\{(x,y),(x,y+d),(x+d,y')\}$. That is, it is a corner that has been sheared in a vertical direction. Whereas a corner can be viewed as a sequence of six integers that satisfy three equations, a skew corner is a sequence of six integers that satisfy only two equations, which makes them easier to handle. In 2024, Beker found a clever modification of Behrend’s construction that gives a lower bound of the form $\exp(-c(\log N)^{1/2})$ for the density of a skew-corner-free subset of $\{1,2,\dots,N\}^2$, as well as a Fourier argument (modelled on a proof of Roth’s theorem by Heath-Brown and Szemerédi) that yielded an upper bound of the form $O((\log N)^{-c})$.

The main result of this paper is to improve the upper bound to a Kelley-Meka-type bound: the particular bound obtained is $\exp(-C(\log N)^{1/12})$. This is achieved by means of a suitable modification of the proof of Kelley and Meka. A similar bound was obtained independently by Luka Milićević.

After this paper appeared on arXiv, the authors, together with Yang Liu and Mehtaab Sawhney, wrote a 75-page paper that obtained a Kelley-Meka-type bound for the corners theorem itself – their bound was $\exp(-C(\log N)^{1/600})$, which they did not try to optimize. Thus, we finally have upper and lower bounds for the corners theorem that are of a similar shape.