2. Proof of Theorem 1·1

We first present a simple proof of the weaker bound $s(n) \gg n^{1+c_1}$ for some constant $c_1 \gt 0$ . We will be fairly brief since this is superseded by the results of [ Reference Pohoata and Zakharov17 ]. The idea is to choose a fixed skew corner-free set $S \subseteq (\mathbb{Z}/b\mathbb{Z})^2$ of size $|S| \gt b$ , for some positive integer b. That one can do so follows from the discussion at the end of the Section 1 since it is known that s(n) is not O(n) (see [ Reference Pratt18 , Proposition 4·16]). Given a positive integer n, choose $k = \lfloor \log_bn\rfloor$ and let $A \subseteq [n]^2$ consist of all points $(x,y) \in [b^k]^2$ such that $(x_j,y_j) \in S$ for all $j \in [k]$ , where $z_j$ denotes the j-th digit in the base-b representation of $z-1$ for $z \in [b^k]$ . It is straightforward to check that A is skew corner-free and that it has size $\Omega(n^{1+c_1})$ with $c_1 = \log_b|S|-1 \gt 0$ . We remark that this kind of product construction is analogous to the binary-ternary construction for sets free of three-term arithmetic progressions due to Erdős and Turán (see [ Reference Erdös and Turán3 ]).

We now turn to the main business of this section, which is to establish Theorem 1·1. Given a positive integer n, consider the box $B = [m]^d \subseteq \mathbb{Z}^d$ , where m,d are positive integers such that $(2m)^d \leq n$ . For positive integers r,t, consider the set

\[A_{r,t} = \{(x,y) \in B \times B \mid \lVert x\rVert^2 = r,\ \langle x,y\rangle = t\}.\]

We claim that $A_{r,t}$ is skew corner-free as a subset of $(\mathbb{Z}^d)^2$ . Indeed, suppose that it contains three points of the form (x,y), (x,y”), (x’,y’) with $y'' - y = x' - x$ . Since $\langle x,y\rangle = t = \langle x,y''\rangle$ , it follows that $\langle x,y''-y\rangle = 0$ , whence $\langle x,x'-x\rangle = 0$ . Hence, Pythagoras’ theorem implies that

\[r = \lVert x'\rVert^2 = \lVert x\rVert^2 + \lVert x'-x\rVert^2 = r + \lVert x'-x\rVert^2.\]

It follows that $\lVert x'-x\rVert = 0$ , that is, $x' = x$ , as desired. In order to transfer this example to the integer setting, we use the map

\[\varphi \colon \mathbb{Z}^d \to \mathbb{Z}, \quad (x_1, \ldots, x_d) \mapsto 1+\sum_{j=1}^{d}(2m)^{j-1}(x_j-1),\]

which, when restricted to B, becomes a Freiman isomorphism into [n]. Thus, $(\varphi \times \varphi)(A_{r,t})$ is a skew corner-free subset of $[n]^2$ of the same size as $A_{r,t}$ . Therefore, all that remains is to choose r,t so that $A_{r,t}$ is of the required size. But as r,t range over $[dm^2]$ , the sets $A_{r,t}$ form a partition of $B \times B$ . Hence, by the pigeonhole principle, there exists a choice of r,t such that

\[|A_{r,t}| \geq \frac{|B\times B|}{(dm^2)^2} = \frac{m^{2d}}{d^2m^4} = \frac{m^{2d-4}}{d^2}.\]

Finally, choosing $m = \lfloor \frac{1}{2}n^{1/d}\rfloor$ and $d = \lfloor (2\log_2n)^{1/2}\rfloor$ , it is not hard to check that we get

\[|A_{r,t}| \geq \frac{n^2}{2^{(4\sqrt{2}+o(1))\sqrt{\log_2n}}}.\]

Remark. Our construction draws inspiration from the classical Behrend construction of sets lacking three-term arithmetic progressions [ Reference Behrend2 ] (in particular, the projection of our set onto the first coordinate is precisely such a Behrend set). Additionally, it turns out to be quite similar in spirit to the construction of Pohoata and Zakharov [ Reference Pohoata and Zakharov17 , Theorem 1·1]. Their construction is based on (the affine version of) the Hermitian unital over $\mathbb{F}_{p^2}^2$ , which can be thought of as an analogue of a sphere in the finite field setting. By working directly in the integer setting, we take the advantage of being able to consider higher dimensional spheres, which results in superior bounds.

Remark. Both constructions described in this section can be easily modified so as to produce bi-skew corner-free sets of comparable size (for a precise definition, see [ Reference Pratt18 , Definition 4·17]). Indeed, for the first construction, one merely has to replace the set S with a suitable bi-skew corner-free set, e.g.

\[\{(0,0), (0,1), (2, 0), (2, 3), (3, 1), (3, 3), (3, 5), (4, 0)\} \subseteq (\mathbb{Z}/6\mathbb{Z})^2.\]

For the second construction, one can modify the definition of the set $A_{r,t}$ by requiring that the second point also lie on the sphere of radius $\sqrt{r}$ centred at the origin:

\[A_{r,t}' = \{(x,y) \in B \times B \mid \lVert x\rVert^2 = \lVert y\rVert^2 = r,\ \langle x,y\rangle = t\}.\]

To ensure that $A_{r,t}'$ is large, one first uses the pigeonhole principle to find a value of r such that $\sqrt{r}S^{d-1}$ contains at least ${m^d}/{dm^2} = {m^{d-2}}/{d}$ points of B. A further application of the pigeonhole principle then yields a set $A_{r,t}$ of size at least

\[\frac{(m^{d-2}/d)^2}{dm^2} = \frac{m^{2d-6}}{d^3},\]

which can then be optimised to give a bi-skew corner-free subset of $[n]^2$ of size at least

\[n^22^{-(4\sqrt{3}+o(1))\sqrt{\log_2n}}.\]

3. Proof of Theorem 1·2

We begin by giving a high-level overview of our approach. We use the density increment/iteration method that falls into the broad conceptual framework outlined in [ Reference Green8 , Section 4]. More precisely, our strategy is based on the approach of Heath-Brown [ Reference Heath-Brown10 ] and Szemerédi [ Reference Szemerédi24 ] to Roth’s theorem. The starting point is to write down a trilinear form that counts skew corners in a given set A. By performing standard manipulations, one can express this form in terms of the Fourier coefficients of A. An application of Hölder’s inequality then shows that this quantity is controlled by various $\mathbb{L}^p$ -norms associated to the Fourier transform of A. Thus, if the count of skew corners in A deviates from what we would expect for a random set of the same density, one of these norms must be large. From this, one can deduce either a large Fourier $\mathbb{L}^2$ -mass along characters oscillating in the horizontal or vertical direction. These alternatives are then shown to lead to density increments on either an arithmetic progression of rows or an arithmetic progression of columns. Since we are working in a two-dimensional setting, we need one additional averaging argument to obtain a density increment on a square substructure. The final density increment can then be iterated in the usual way to obtain the stated bound.

We now begin the argument proper. Let G be a finite abelian group. We define the trilinear form

\[\Lambda(f, g, h) := \mathbb{E}_{x,y,y',d\in G}f(x,y)g(x,y+d)h(x+d,y'),\]

where f,g,h are real-valued functions on $G^2$ . In particular, if $A \subseteq G^2$ , then $N^4\Lambda(1_A,1_A,1_A)$ is the number of skew corners in A. By employing the Fourier inversion formula and the fact that the Fourier transform diagonalises convolution, one can derive the Fourier representation of $\Lambda$ :

\begin{align*} {} {}\Lambda(f,g,h) &= \mathbb{E}_{x,d\in G}(g(x,\cdot) \circ f(x,\cdot))(d)S(h)(x+d)\\ {} {}&= \mathbb{E}_{x\in G}[S(h)\circ(g(x,\cdot)\circ f(x,\cdot))](x)\\ {} {}&= \mathbb{E}_{x\in G}\sum_{\gamma\in\widehat{G}}\widehat{S(h)\circ(g(x,\cdot)\circ f(x,\cdot))}(\gamma)\gamma(x)\\ {} {}&= \sum_{\gamma\in\widehat{G}}\widehat{S(h)}(\gamma)\mathbb{E}_{x\in G}\widehat{f(x,\cdot)}(\gamma)\overline{\widehat{g(x,\cdot)}(\gamma)}\gamma(x). {}\end{align*}

In particular, the triangle inequality implies that

\begin{equation*} {} {}|\Lambda(f,g,h)| \leq \sum_{\gamma\in\widehat{G}}|\widehat{S(h)}(\gamma)|\sigma(f,g)(\gamma), {}\end{equation*}

where we define

\[\sigma(f,g) \colon \widehat{G} \to \mathbb{R}, \quad \gamma \mapsto \mathbb{E}_{x\in G}|\widehat{f(x,\cdot)}(\gamma)||\widehat{g(x,\cdot)}(\gamma)|.\]

Thus, on applying applying Hölder’s inequality, we obtain that

(1) \begin{equation} {} {}|\Lambda(f,g,h)| \leq \lVert \widehat{S(h)}\rVert_p\lVert \sigma(f,g)\rVert_q {}\end{equation}

for all $1 \leq p,q \leq \infty$ such that ${1}/{p}+{1}/{q} = 1$ . It is also useful to note that, by the Cauchy–Schwarz inequality and Parseval’s identity, we have the following bound:

(2) \begin{equation} {} {}\lVert \sigma(f,g)\rVert_1 = \mathbb{E}_{x\in G}\sum_{\gamma\in\widehat{G}}|\widehat{f(x,\cdot)}(\gamma)||\widehat{g(x,\cdot)}(\gamma)| {} {}\leq \mathbb{E}_{x\in G}\lVert f(x,\cdot)\rVert_2\lVert g(x,\cdot)\rVert_2. {}\end{equation}

To motivate the main part of the argument, we first briefly discuss some of the core ideas in the finite field setting. The key observation is that we can use Fourier analysis to bound the number of skew corners in a given set from below. This is made precise by the following result, which we call a ‘generalised von Neumann theorem’, borrowing the terminology from [ Reference Green8 ]. Given a parameter $\eta \in [0,1]$ , we say that a subset of a finite abelian group is $\eta$ -uniform if all non-trivial Fourier coefficients of its indicator function are at most $\eta$ in absolute value.

Proposition 3·1 (Generalised von Neumann theorem). Let G be a finite abelian group and let $A \subseteq G^2$ be a subset of density $\alpha$ . Let $f_A = 1_A - \alpha1_{G^2}$ be the balanced function of A. Then

(3) \begin{equation} {} {} {}\Lambda(1_A,1_A,1_A) \geq \alpha^3 - \alpha\lVert \widehat{S(f_A)}\rVert_{\infty}. {} {}\end{equation}

In particular, if A is $\eta$ -uniform, then A contains at least $(\alpha^3-\alpha\eta)N^4$ skew corners.

Proof. Consider the decomposition

\[\Lambda(1_A,1_A,1_A) = \Lambda(1_A,1_A,f_A) + \alpha\Lambda(1_A,1_A,1_{G^2}).\]

By the Cauchy–Schwarz inequality, we have the following lower bound for the second term on the right-hand side:

\begin{equation*} {} {}\Lambda(1_A,1_A,1_{G^2}) = \mathbb{E}_{x,y,d\in G}1_A(x,y)1_A(x,y+d) = \mathbb{E}_{x\in G}S(1_A)(x)^2 \geq \Bigl(\mathbb{E}_{x\in G}S(1_A)(x)\Bigr)^2 = \alpha^2. {}\end{equation*}

On the other hand, by (1) with $p = \infty$ , $q = 1$ and (2), the first term can be upper bounded in magnitude as follows:

\begin{align*} {} {}|\Lambda(1_A,1_A,f_A)| &\leq \lVert \widehat{S(f_A)}\rVert_{\infty}\mathbb{E}_{x\in G}\lVert 1_A(x,\cdot)\rVert_2^2 = \lVert \widehat{S(f_A)}\rVert_{\infty}\mathbb{E}_{x\in G}S(1_A)(x) = \alpha \lVert \widehat{S(f_A)}\rVert_{\infty}, {}\end{align*}

so (3) follows. The second statement follows on observing that $\widehat{S(f_A)}(\gamma) = \widehat{f_A}(\gamma,1)$ for $\gamma \in \widehat{G}$ , where we naturally identify $\widehat{G^2}$ with $\widehat{G}^2$ .

Using Proposition 3·1 as a starting point, one can give an argument in the finite field setting in the same vein as for Meshulam’s theorem [ Reference Meshulam14 ]. Indeed, if $G = \mathbb{F}_2^n$ and $A \subseteq G^2$ is skew corner-free of density $\alpha$ , then one can easily verify that $\Lambda(1_A,1_A,1_A) \leq {\alpha}/{N}$ , where $N = 2^n$ . Thus, either $\alpha \leq \sqrt{{2}/{N}}$ or there exists $\gamma \in \widehat{G}\setminus\{1\}$ such that $|\widehat{S(f_A)}(\gamma)| \geq {\alpha^2}/{2}$ . The latter case leads to a density increment of $S(1_A)$ on a coset of a codimension-1 subspace $H \leqslant G$ , and an extra averaging argument produces a density increment of A on a coset of $H^2$ . This density increment can then be iterated to obtain a bound of the form $|A| \ll {4^n}/{n}$ . This is already better than the best known bound [ Reference Lacey and McClain13 ] for corner-free sets in this setting, and the argument is substantially simpler.

However, we do not have the luxury of working in the finite field setting, so we have to work a bit harder. To begin, we set up some notation that will be used throughout the remainder of this section. Let $A \subseteq [n]^2$ be a subset of density $\alpha$ . Set $N = 2n$ and view $[n]^2$ as a subset of the group $G^2$ , where $G = \mathbb{Z}/N\mathbb{Z}$ . Let $f_A = 1_A - \alpha1_{[n]^2}$ be the balanced function of A. Given $x \in G$ , we let $A_x := \{y \in G \mid (x,y) \in A\}$ be the slice of A at x.

In the above setting, the following result plays a role analogous to that of Proposition 3·1. For comparison, the corresponding result in the setting of three-term arithmetic progressions is roughly [ Reference Green6 , Proposition 2].

Proof. As in the proof of Proposition 3·1, we decompose

\begin{equation*} {} {}\Lambda(\widetilde{1_A}, 1_A, 1_A) = \Lambda(\widetilde{1_A}, 1_A, f_A) + \alpha\Lambda(\widetilde{1_A}, 1_A, 1_{[n]^2}). {}\end{equation*}

Since A is skew corner-free when viewed as a subset of $G^2$ , the left-hand side equals

\begin{align*} {} {}\frac{1}{N}\mathbb{E}_{x,y,y'\in G}\widetilde{1_A}(x,y)1_A(x,y)1_A(x,y') = \frac{1}{N}\mathbb{E}_{x\in G}\Bigl(\mathbb{E}_{y\in G}\widetilde{1_A}(x,y)\Bigr)\Bigl(\mathbb{E}_{y'\in G}1_A(x,y')\Bigr) = \frac{\alpha}{4N}. {}\end{align*}

To obtain a lower bound on the second term on the right-hand side, we write it as follows:

\begin{align*} {} {}\Lambda(\widetilde{1_A}, 1_A, 1_{[n]^2}) {} {}&= \frac{1}{2N^2}\sum_{x\in [n],\ A_x \neq \varnothing}\frac{|\{(y_1,y_2) \in A_x^2 \mid y_2-y_1 \in [n]-x \}|}{|A_x|}. {}\end{align*}

Since all pairs $(y_1, y_2) \in A_x^2$ such that either $1 \leq y_2 \leq y_1 \leq x$ or $x \lt y_1 \leq y_2 \leq n$ are counted in the numerator of the summand, we get that this quantity is at least

\begin{align*} {} {}\frac{1}{2N^2}\sum_{x\in [n],\ A_x\neq\varnothing}\frac{1}{|A_x|}\Biggl(\frac{|A_x \cap [1,x]|^2}{2}+\frac{|A_x \cap [x+1,n]|^2}{2}\Biggr) &\geq \frac{1}{2N^2}\sum_{x\in [n],\ A_x\neq\varnothing}\frac{1}{|A_x|}\cdot \frac{|A_x|^2}{4}\\ {} {}&= \frac{1}{8N^2}\sum_{x\in [n],\ A_x\neq\varnothing}|A_x|\\ {} {}&= \frac{\alpha}{32}, {}\end{align*}

where we made use of convexity in the first inequality. Hence, if (i) fails to hold, it follows by (1) with $p = 3$ , $q = {3}/{2}$ that

\[\lVert \widehat{S(f_A)}\rVert_3\lVert \sigma(\widetilde{1_A},1_A)\rVert_{3/2} \geq \frac{\alpha^2}{64},\]

so either (ii) or (iii) must hold.

In the following lemma we record two bounds based on Parseval’s identity that will be important for the success of the $\mathbb{L}^2$ density increment strategy.

Proof. To prove (i), observe that if $A_x \neq \varnothing$ , then

\[\lVert \widetilde{1_A}(x,\cdot)\rVert_2\lVert 1_A(x,\cdot)\rVert_2 = \frac{\lVert 1_A(x,\cdot)\rVert_2^2}{S(1_A)(x)} = 1,\]

whereas if $A_x = \varnothing$ , then the left-hand side trivially vanishes. The conclusion now follows from the estimate (2). Likewise, Parseval’s identity implies that

\[\sum_{\gamma\in\widehat{G}}|\widehat{S(f_A)}(\gamma)|^2 = \lVert S(f_A)\rVert_2^2 \leq \lVert S(1_A)\rVert_2^2 \leq \lVert S(1_A)\rVert_{\infty}\lVert S(1_A)\rVert_1 \leq \alpha,\]

which proves (ii).

We note in passing that, assuming the first alternative in Proposition 3·2 doesn’t hold, we could have instead used the estimate (1) with $p = \infty$ , $q = 1$ coupled with part (i) of Lemma 3·3 to obtain the existence of a character $\gamma \in \widehat{G} \setminus \{1\}$ such that $|\widehat{S(f_A)}(\gamma)| \geq {\alpha^2}/{64}$ . We could then carry on essentially in the same fashion as in Roth’s original argument [ Reference Roth20 ] to obtain a bound of the form $s(n) \ll {n^2}/{\log\log n}$ . However, as mentioned before, we pursue a different route, which leads to a better bound.

The following lemma is technical in nature and is a variant of [ Reference Green6 , Lemma 4]. It is a device that will be used to convert information about large Fourier $\mathbb{L}^p$ -mass into that about large Fourier $\mathbb{L}^2$ -mass, which in turn serves as input to the $\mathbb{L}^2$ density increment strategy.

Proof. Enumerate $\widehat{G}$ as $\{\gamma_1,\ldots,\gamma_N\}$ so that the sequence $(b_j)_{j\in [N]}$ defined by $b_j = |\phi(\gamma_j)|$ for $j \in [N]$ is non-increasing. Then note that for each $k \in [N]$ we have

\[kb_k \leq \sum_{j=1}^{k}b_j \leq \lVert\phi\rVert_1,\]

whence $b_k \leq k^{-1}\lVert\phi\rVert_1$ . Hence, for all $k \in [N]$ we get

\[\sum_{j=k+1}^{N}b_j^{3/2} \leq b_k^{1/2}\sum_{j=k+1}^{N}b_j \leq b_k^{1/2}\lVert\phi\rVert_1 \leq k^{-1/2}\lVert\phi\rVert_1^{3/2}.\]

In particular, taking $k = \min\Bigl\{\Bigl\lceil 4(\beta^{-1}\lVert\phi\rVert_1)^3\Bigr\rceil, N\Bigr\}$ , it follows that $\sum_{j=1}^{k}b_j^{3/2} \geq \frac{1}{2}\beta^{3/2}$ . Now if we had $b_j \leq 2^{-3}j^{-3/4}\beta$ for all $j \in [k]$ , then it would follow that

\[\sum_{j=1}^{k}b_j^{3/2} \leq 2^{-9/2}\beta^{3/2}\sum_{j=1}^{k}j^{-9/8} \lt 2^{-9/2}\beta^{3/2}\Biggl(1+\int_{1}^{\infty}x^{-9/8}\,dx\Biggr) \lt \frac{1}{2}\beta^{3/2},\]

which is absurd. Therefore, there must exist $m \in[k]$ such that $b_m \geq 2^{-3}m^{-3/4}\beta$ , whence

\[\sum_{j=1}^{m}b_j \geq mb_m \geq 2^{-3}m^{1/4}\beta.\]

Thus, we may take $\Gamma = \{\gamma_1, \ldots, \gamma_m\}$ , as desired.

Following [ Reference Henriot11 ], for a set of characters $\Gamma \subseteq \widehat{G}$ and a parameter $\nu \in (0,2]$ , we will say that $\Gamma$ is $\nu$ -annihilated by a non-empty set $X \subseteq G$ if $|\gamma(x)-1| \leq \nu$ for all $\gamma \in \Gamma$ and $x \in X$ . The following simple lemma is a variant of [ Reference Henriot11 , Lemma 12].

Proof. If $\gamma(x) = e(x\theta)$ for $\theta \in \mathbb{R}/\mathbb{Z}$ , then for all $x \in X$ we have $2|\sin(\pi x\theta)| = |1-e(x\theta)| \leq \nu$ , whence

\[\text{Re}\gamma(x) = \cos(2\pi x\theta) = 1-2\sin^2(\pi x\theta) \geq 1-\frac{\nu^2}{2}.\]

Therefore, we have

\[\text{Re}\widehat{\mu_X}(\gamma) = \mathbb{E}_{x\in X}\text{Re}\gamma(x) \geq 1-\frac{\nu^2}{2},\]

so the conclusion follows.

The following two propositions, whose names are partly inspired by [ Reference Henriot11 , Section 8], constitute the heart of the proof. In the first proposition, we obtain a density increment on a suitable set of rows as a consequence of the second alternative in Proposition 3·2.

Proposition 3·6 (Horizontal $\mathbb{L}^2$ density increment). Let $A \subseteq [n]^2$ be a subset of density $\alpha \gt 0$ such that $\lVert \sigma(\widetilde{1_A},1_A)\rVert_{3/2} \geq 2^6\alpha$ . Then there exists a non-empty set $\Gamma \subseteq \widehat{G}$ of size $|\Gamma| \ll \alpha^{-3}$ such that, for any set $P \subseteq G$ that 1-annihilates $\Gamma$ ,

\begin{equation*}\mathbb{E}_{x\in G}\max_{y\in G}\frac{|(A_x-y) \cap P|}{|P|} \geq 2|\Gamma|^{1/4}\alpha.\end{equation*}

Proof. By Lemma 3·4 applied with $\phi = \sigma(\widetilde{1_A},1_A)$ , $\beta = 2^6\alpha$ and part (i) of Lemma 3·3, we obtain a set $\Gamma \subseteq \widehat{G}$ of the required size such that

\[\sum_{\gamma \in \Gamma}\mathbb{E}_{x\in G}|\widehat{\widetilde{1_A}(x,\cdot)}(\gamma)||\widehat{1_A(x,\cdot)}(\gamma)| \geq 2^3|\Gamma|^{1/4}\alpha.\]

Hence, if $\Gamma$ is 1-annihilated by P, we obtain using Parseval’s identity and Lemma 3·5 that

\begin{align*} {} {}\mathbb{E}_{x\in G}\langle \widetilde{1_A}(x,\cdot) \circ \mu_P, 1_A(x,\cdot) \circ \mu_P\rangle &= \mathbb{E}_{x\in G}\sum_{\gamma\in\widehat{G}}|\widehat{\widetilde{1_A}(x,\cdot)}(\gamma)||\widehat{1_A(x,\cdot)}(\gamma)||\widehat{\mu_P}(\gamma)|^2\\ {} {}&\geq 2^{-2}\sum_{\gamma\in\Gamma}\mathbb{E}_{x\in G}|\widehat{\widetilde{1_A}(x,\cdot)}(\gamma)||\widehat{1_A(x,\cdot)}(\gamma)|\\ {} {}&\geq 2|\Gamma|^{1/4}\alpha. {}\end{align*}

On the other hand, this quantity can be upper bounded as follows:

\begin{align*} {} {}\mathbb{E}_{x\in G}\langle \widetilde{1_A}(x,\cdot) \circ \mu_P, 1_A(x,\cdot) \circ \mu_P\rangle &\leq \mathbb{E}_{x\in G}\lVert\widetilde{1_A}(x,\cdot) \circ \mu_P\rVert_1\lVert 1_A(x,\cdot) \circ \mu_P \rVert_{\infty}\\ {} {}&= \mathbb{E}_{x\in G}\lVert\widetilde{1_A}(x,\cdot)\rVert_1 \lVert \mu_P\rVert_1\lVert 1_A(x,\cdot) \circ \mu_P \rVert_{\infty}\\ {} {}&\leq \mathbb{E}_{x\in G}\lVert 1_A(x,\cdot) \circ \mu_P \rVert_{\infty}, {}\end{align*}

whence the desired conclusion follows.

The reason why we use the ‘locally normalised’ indicator function $\widetilde{1_A}$ instead of $1_A$ lies in the last part of the proof of Proposition 3·6. At that point, we have to upper bound the average additive energy of a vertical slice of A with P. Had we used $1_A$ instead of $\widetilde{1_A}$ , we would end up with a weighted average having the column densities of A as weights. Since these densities may vary a lot from column to column, this would not necessarily imply an adequate density increment. This is in contrast to the setting of Roth’s theorem, where all normalisations are of a ‘global’ nature and hence are purely a matter of taste.

The following proposition has the third alternative in Proposition 3·2 as a starting assumption and produces a density increment on a suitable set of columns.

Proposition 3·7 (Vertical $\mathbb{L}^2$ density increment). Let $A \subseteq [n]^2$ be a subset of density $\alpha \gt 0$ such that $\lVert \widehat{S(f_A)}\rVert_3 \geq 2^{-12}\alpha$ . Then there exists a non-empty set $\Gamma \subseteq \widehat{G}$ of size $|\Gamma| \ll \alpha^{-3}$ such that, for any set $P \subseteq [n]$ of diameter at most $2^{-30}|\Gamma|^{1/4}\alpha n$ that 1-annihilates $\Gamma$ ,

\begin{equation*} {} {} {}\max_{t\in G}\mathbb{E}_{x\in P}|A_{x+t}|/n \geq (1+2^{-27}|\Gamma|^{1/4})\alpha. {} {}\end{equation*}

Proof. We start by applying Lemma 3·4 with $\phi = |\widehat{S(f_A)}|^2$ , $\beta = 2^{-24}\alpha^2$ and part (ii) of Lemma 3·3 to obtain a set $\Gamma \subseteq \widehat{G}$ of the required size such that

\[\sum_{\gamma\in\Gamma}|\widehat{S(f_A)}(\gamma)|^2 \geq 2^{-27}|\Gamma|^{1/4}\alpha^2.\]

Thus, for any $P \subseteq [n]$ that 1-annihilates $\Gamma$ , we get using Parseval’s identity and Lemma 3·5 that

\[\lVert S(f_A) \circ \mu_P\rVert_2^2 = \sum_{\gamma\in\widehat{G}}|\widehat{S(f_A)}(\gamma)|^2|\widehat{\mu_P}(\gamma)|^2 \geq 2^{-2}\sum_{\gamma\in\Gamma}|\widehat{S(f_A)}|^2 \geq 2^{-29}|\Gamma|^{1/4}\alpha^2.\]

Next, we perform the usual passage from balanced to indicator functions. By expanding out inner products and using the adjoint property of convolution, one obtains that

\[\lVert S(f_A)\circ\mu_P\rVert_2^2 = \lVert S(1_A)\circ\mu_P\rVert_2^2 - \alpha\langle S(1_A)+S(f_A), S(1_{[n]^2})\circ(\mu_P\circ\mu_P) \rangle.\]

But note that we have the estimates

\[\lVert S(1_A)+S(f_A)\rVert_{\infty} \leq 1, \quad \lVert S(1_{[n]^2})\circ(\mu_P\circ\mu_P) - S(1_{[n]^2}) \rVert_1 \leq \frac{\mathrm{diam}(P)}{n},\]

where the second one holds because $S(1_{[n]^2})\circ(\mu_P\circ\mu_P)$ is ${1}/{2}$ on $(\mathrm{diam}(P), n-\mathrm{diam}(P)]$ , 0 outside $(\!-\mathrm{diam}(P),n+\mathrm{diam}(P)]$ and has values in $[0,{1}/{2}]$ everywhere. Hence, Hölder’s inequality implies that

\[|\langle S(1_A)+S(f_A), S(1_{[n]^2})\circ(\mu_P\circ\mu_P) - S(1_{[n]^2}) \rangle| \leq \frac{\mathrm{diam}(P)}{n}.\]

Since we have

\[\langle S(1_A)+S(f_A), S(1_{[n]^2})\rangle = \frac{\alpha}{8},\]

it follows that

\[\lVert S(1_A)\circ\mu_P\rVert_2^2 \geq \lVert S(f_A)\circ\mu_P\rVert_2^2 + \Bigl(\frac{\alpha}{8}-\frac{\mathrm{diam}(P)}{n}\Bigr)\alpha.\]

Hence, if $\mathrm{diam}(P) \leq 2^{-30}|\Gamma|^{1/4}\alpha n$ , we obtain that

\[\lVert S(1_A)\circ\mu_P\rVert_2^2 \geq \Bigl(\frac{1}{8}+2^{-30}|\Gamma|^{1/4}\Bigr)\alpha^2.\]

We now conclude similarly as in the proof of Proposition 3·6, by observing the upper bound

\[\lVert S(1_A) \circ \mu_P\rVert_2^2 \leq \lVert S(1_A)\circ \mu_P\rVert_1\lVert S(1_A)\circ \mu_P\rVert_{\infty} = \frac{1}{4}\alpha\lVert S(1_A)\circ \mu_P\rVert_{\infty}\]

and unfolding the definition of the difference convolution of $S(1_A)$ and $\mu_P$ .

To complete the density increment argument, we require the following well-known result (for a proof, see e.g. [ Reference Schmidt21 ]):

Lemma 3·8 has the following straightforward consequence, which will be used to furnish arithmetic progressions P as input to Propositions 3·6 and 3·7. In order for the final averaging argument to succeed, we also need to keep track of the span of these progressions, which is defined to be the product of the length and the common difference (this piece of terminology is not standard).

Proof. Let $\ell = \Bigl\lfloor \frac{1}{6}(2^{-30}\alpha n)^{\frac{1}{m+1}}\Bigr\rfloor$ and $Q = (6\ell)^m$ . Here, we are assuming that $\alpha n \geq 2^{30}6^{m+1}$ , which is certainly the case unless (i) holds. Thus, $\ell \geq 1$ and $\ell \gg \alpha n^{\frac{1}{m+1}}$ . Enumerating $\Gamma$ as $\{\gamma_1,\ldots,\gamma_m\}$ , where $\gamma_j(x) = e(x\theta_j)$ for $j \in [m]$ and $\theta_1, \ldots, \theta_m \in \mathbb{R}/\mathbb{Z}$ , Lemma 3·4 implies the existence of $q \in [Q]$ such that $\lVert q\theta_j\rVert_{\mathbb{R}/\mathbb{Z}} \leq {1}/{6\ell}$ for all $j \in [m]$ . Consequently, if we let P be the arithmetic progression $q \cdot [\ell]$ , it follows that $\lVert x\theta_j\rVert_{\mathbb{R}/\mathbb{Z}} \leq {1}/{6}$ for all $j \in [m]$ and $x \in P$ . Thus, $\Gamma$ is 1-annihilated by P and P has span $\ell q \leq 2^{-30}\alpha n$ , as desired.

Finally, we are ready to assemble all the pieces we have developed thus far into a single density increment result:

Proof. Assume that (i) doesn’t hold. In particular, we must be in one of the cases (ii) or (iii) of Proposition 3·2. If we are in case (ii), then we apply Proposition 3·6 together with Corollary 3·9. We obtain an arithmetic progression $P \subseteq [n]$ of length and span as in case (ii) of the present result such that

\begin{equation*} {} {}\mathbb{E}_{x\in G}\max_{y\in G}\frac{|(A_x-y) \cap P|}{|P|} \geq 2m^{1/4}\alpha, {}\end{equation*}

where $m \ll \alpha^{-3}$ is a positive integer. Hence, we may take

\[A' = \bigcup_{x\in [n]}[\{x\} \times ((A_x-y_x) \cap P)],\]

where for each $x \in [n]$ we choose $y_x \in G$ so as to maximise the quotient $|(A_x-y_x) \cap P|/|P|$ .

Now suppose that we are in case (iii) of Proposition 3·2. Then we apply Proposition 3·7 combined with Corollary 3·9. This yields an arithmetic progression $P \subseteq [n]$ of length and span as in case (iii) of the present result such that

\[\max_{t\in G}\mathbb{E}_{x\in P}|A_{x+t}|/n \geq (1+2^{-27}m^{1/4})\alpha,\]

where $m \ll \alpha^{-3}$ is a positive integer. But we may now take

\[A'' = \bigcup_{x\in P}(\{x\}\times A_{x+y}),\]

where $t \in G$ is chosen so as to maximise $\mathbb{E}_{x\in P}|A_{x+t}|/n$ . This concludes the proof.

In order to obtain a density increment that can be iterated, we have to make one last manoeuvre:

Proof. We only prove the first statement; the proof of the second statement is completely analogous. Partition $[\ell d]$ into d translates of P and then partition [n] into translates of $[\ell d]$ and an error set E of size less than $\ell d$ . Then $P \times E$ occupies at most $\ell^2 d$ elements of B, so $B \setminus (P\times E)$ has density at least $\beta - {\ell d}/{n}$ on $P \times [n]$ . The conclusion now follows by averaging.

By putting together Proposition 3·10 and Lemma 3·11 and using translation- and dilation-invariance of skew corner-free sets, we obtain the final form of our density increment result:

To establish Theorem 1·2, all that remains is to iterate Proposition 3·6. In analogy with the deduction of [ Reference Green6 , Theorem 1] from [ Reference Green6 , Proposition 7], we show by induction that for $n \gt 1$ , any skew corner-free subset of $[n]^2$ has density at most $C'(\log n)^{-c_2}$ , where $C' \gt 0$ is an absolute constant. To this end, we apply Proposition 3·12; if (i) holds, we are immediately done by taking $c_2 \leq \frac{1}{4}$ . Otherwise, there exist positive integers m, n’ as in (ii) and a skew corner-free subset of $[n']^2$ of density at least $(1+c'm^{1/4})\alpha$ . Here, we may assume that n is sufficiently large and

\[m \leq \frac{1}{4}(\log n)^{3/4}, \quad n' \geq n^{\frac{1}{m+1}}(\log n)^{-1/4} \gt 1.\]

Hence, by the induction hypothesis, we have

\[(1+c'm^{1/4})\alpha \leq C'(\log n')^{-c_2}.\]

Assuming for the sake of contradiction that $\alpha \gt C'(\log n)^{-c_2}$ , it follows that

(4) \begin{equation} {} {}(1+c'm^{1/4})\Bigl(\frac{\log n'}{\log n}\Bigr)^{c_2} \lt 1. {}\end{equation}

Now observe that for all $x \gt 0$ we have

\[\exp(3x^{1/3}) \gt \frac{(3x^{1/3})^3}{3!} \gt 4x,\]

so in particular $\log(4m) \leq 3m^{1/3}$ . Since the function $x \mapsto {\log x}/{x}$ is decreasing on the interval $[e,\infty)$ and $\log n \geq (4m)^{4/3} \gt e$ , it follows that

\[\frac{\log\log n}{4\log n} \leq \frac{\log(4m)}{3(4m)^{4/3}} \leq \frac{1}{4m}.\]

Therefore, we have

\[\frac{\log n'}{\log n} \geq \frac{1}{m+1} - \frac{\log\log n}{4\log n} \geq \frac{1}{4m},\]

so (4) implies that

\[1+c'm^{1/4} \lt (4m)^{c_2}.\]

If we take $c_2 \leq {1}/{5}$ say, the above fails for all $m \gt m_0$ , where $m_0 \geq 1$ is some constant depending on c’. The remaining range $m \leq m_0$ can now be dealt with by taking $c_2$ small enough so that $(4m_0)^{c_2} \lt 1+c'$ . We thus arrive at a contradiction, which concludes the proof.

4. Concluding remarks and open problems

The proofs of both Theorem 1·1 and Theorem 1·2 exhibit many parallels between the problem of estimating s(n) and that of determining the largest size of a subset of [n] lacking three-term arithmetic progressions. The latter problem is one of the cornerstones of additive combinatorics and has been a subject of intense study in the last seventy years. Recently, a huge breakthrough on this problem was made by Kelley and Meka [ Reference Kelley and Meka12 ], who proved upper bounds matching the shape of the well-known lower bound of Behrend [ Reference Behrend2 ]. This came as somewhat of a surprise since Kelley and Meka largely abandon the Fourier-analytic approach, relying instead on methods based in physical space. Thus, it is an interesting challenge to investigate the scope of these methods and explore potential applications to other related problems. In the very recent survey [ Reference Peluse15 ], some optimism has been expressed as to the possibility of applying Kelley–Meka techniques to improve bounds for corner-free sets. Given the apparently even larger similarity of skew corners to three-term arithmetic progressions, we think that a good intermediate step would be to investigate whether these techniques could be used to the improve bounds for the problem considered in this paper. Specifically, we ask the following question:

Question 4·1. Is it true that

\[s(n) \ll \frac{n^2}{\exp(c(\log n)^{\beta})}\]

for some constants $c, \beta \gt 0$ ?

There is another rather intriguing parallel with the study of corner-free sets which we think deserves more attention. As mentioned before, the usual notion of Fourier uniformity is not sufficient to get a handle on the count of corners in a given set. A concrete example explaining this phenomenon is given by [ Reference Green8 , example 5·3], which also appears in [ Reference Shkredov22 , Section 1]. In this example, a random set of $B \subseteq \mathbb{F}_2^n$ of density $\beta$ is taken and the product set $A = B^2 \subseteq (\mathbb{F}_2^n)^2$ is considered. Being the product of a random set with itself, A is a highly uniform set of density $\alpha = \beta^2$ . However, the count of corners in A is equal to the number of triples $(x,y,d)\in(\mathbb{F}_2^n)^3$ such that $x,y,x+d,y+d \in B$ , which is $\beta^4N^3 = \alpha^2N^3$ in expectation. This is significantly more than $\alpha^3N^3$ corners, what one would expect for a truly random subset of $(\mathbb{F}_2^n)^2$ of density $\alpha$ .

Taking a closer look at this example, it becomes clear that a similar reasoning applies to our problem: if $B \subseteq \mathbb{F}_2^n$ is random of density $\beta$ , then $A = B^2$ contains roughly $\beta^5N^4 = \alpha^{5/2}N^4$ skew corners, whereas a truly random subset of density $\alpha$ would contain more like $\alpha^3N^4$ skew corners. However, this apparent deficiency did not prevent us from using Fourier analysis to obtain bounds for skew corner-free sets. Indeed, we have shown in Proposition 3·1 that any uniform subset has roughly at least as many skew corners as a random set of the same density. In light of this, we do not find the example discussed in the previous paragraph as entirely satisfactory evidence as to the impossibility of applying Fourier analysis to the study corner-free sets. This motivates us to ask the following question:

Question 4·2. Do there exist Fourier uniform sets with significantly fewer than expected corners? More precisely, do there exist $\alpha, \delta \gt 0$ such that, for infinitely many N, there exists a set $A \subseteq (\mathbb{Z}/N\mathbb{Z})^2$ of density $\alpha+o(1)$ which is o(1)-uniform, but has at most $(\alpha^3 - \delta)N^3$ corners?

We believe that Question 4·2 should have an affirmative answer. However, showing the existence of such sets might not be a simple task. Indeed, comparing this to the situation for four-term arithmetic progressions, it has been known since the seminal work of Gowers [ Reference Gowers4 ] that there exist uniform sets with more than expected arithmetic progressions of length four. In spite of this, constructing such sets with fewer than expected 4-progressions turned out to be a non-trivial problem on its own (see [ Reference Gowers5 ]).