Corners theorem

A corner is a subset of ${\displaystyle \mathbb {Z} ^{2}}$ of the form ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$, where ${\displaystyle x,y,h\in \mathbb {Z} }$ and ${\displaystyle h>0}$.

If ${\displaystyle A}$ is a subset of the ${\displaystyle N\times N}$ grid ${\displaystyle \{1,\ldots ,N\}\times \{1,\ldots ,N\}}$ that contains no corner, then the size of ${\displaystyle A}$ is ${\displaystyle o(N^{2})}$. In other words, for any ${\displaystyle \varepsilon }$, there is a ${\displaystyle N_{0}}$ such that for any ${\displaystyle N\geq N_{0}}$, any corner-free subset ${\displaystyle A}$ of ${\displaystyle \{1,\ldots ,N\}\times \{1,\ldots ,N\}}$ is smaller than ${\displaystyle \varepsilon N^{2}}$.

We would first like to replace the condition ${\displaystyle h>0}$ with ${\displaystyle h\neq 0}$. To achieve this, we consider the set${\displaystyle A+A\subset \{1,\ldots ,2N\}\times \{1,\ldots ,2N\}}$. By the pigeonhole principle, there exists a point ${\displaystyle c\in A+A}$ such that it can be represented as ${\displaystyle c=a+b}$ for at least ${\displaystyle {\frac {|A|^{2}}{(2N)^{2}}}}$ pairs ${\displaystyle a,b\in A}$. We choose this point ${\displaystyle c}$ and construct a new set ${\displaystyle A':=A\cap (c-A)}$. Observe that ${\displaystyle |A'|\geq {\frac {|A|^{2}}{(2N)^{2}}}}$, as the size of ${\displaystyle A'}$ is the number of ways of writing ${\displaystyle c=a+b}$. Further observe that it suffices to show that ${\displaystyle |A'|=o(N^{2})}$. Note that ${\displaystyle A'}$ is a subset of ${\displaystyle A}$, so it has no corner, i.e., no subset of the form ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ for ${\displaystyle h>0}$. But ${\displaystyle A'}$ is also a subset of ${\displaystyle c-A}$, so it also has no anticorner, i.e., no subset of the form ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ with ${\displaystyle h<0}$. Hence, ${\displaystyle A'}$ has no subset of the form ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ for ${\displaystyle h\neq 0}$, which is the condition we sought.

To show ${\displaystyle |A'|=o(N^{2})}$, we construct an auxiliary tripartite graph ${\displaystyle G}$. The first part has vertex set ${\displaystyle U=\{u_{1},\ldots ,u_{N}\}}$, where the vertices correspond to the ${\displaystyle N}$ vertical lines ${\displaystyle x=i}$. The second part has vertex set ${\displaystyle V=\{v_{1},\ldots ,v_{N}\}}$, where the vertices correspond to the ${\displaystyle N}$ horizontal lines ${\displaystyle y=j}$. The third part has vertex set ${\displaystyle W=\{w_{1},\ldots ,w_{2N}\},}$, where the vertices correspond to the ${\displaystyle 2N}$ slanted lines ${\displaystyle y=-x+k}$ with slope ${\displaystyle -1}$. We draw an edge between two vertices if the corresponding lines intersect at a point in ${\displaystyle A'}$.

Let us now think about the triangles in the auxiliary graph ${\displaystyle G}$. Note that for each point ${\displaystyle x\in A'}$, the vertices of ${\displaystyle G}$ corresponding to the horizontal, vertical, and slanted lines passing through ${\displaystyle x}$ form a triangle in ${\displaystyle G}$. A case check reveals that if ${\displaystyle G}$ contained any other triangle, then there would be a corner or anticorner, so ${\displaystyle G}$ does not contain any other triangle. With this characterization of all the triangles in ${\displaystyle G}$, observe that each edge of ${\displaystyle G}$ (corresponding to an intersection of lines at some point ${\displaystyle x\in A'}$) is contained in exactly one triangle (namely the triangle with vertices corresponding to the three lines passing through ${\displaystyle x\in A'}$). It is a well-known corollary of the triangle removal lemma that a graph on ${\displaystyle n}$ vertices in which each edge is in a unique triangle has ${\displaystyle o(n^{2})}$ edges. Hence, ${\displaystyle G}$ has ${\displaystyle o(N^{2})}$ edges. But note that we can count the edges of ${\displaystyle G}$ exactly by just counting all the intersections at points in ${\displaystyle A'}$ – there are ${\displaystyle 3|A'|}$ such intersections. Hence, ${\displaystyle 3|A|'=|E(G)|=o(N^{2})}$, from which ${\displaystyle |A'|=o(N^{2})}$. This completes the proof.

We have ${\displaystyle A\subseteq \{1,2,\ldots ,N\}}$ that does not contain any 3-term arithmetic progression. Define the following set

${\displaystyle B=\{(x,y)\in \{1,2,\ldots ,2N\}\times \{1,2,\ldots ,2N\}|x-y\in A\}}$.

For each ${\displaystyle a\in A}$, there are at least ${\displaystyle N}$ pairs ${\displaystyle (x,y)\in \{1,2,\ldots ,2N\}\times \{1,2,\ldots ,2N\}}$ such that ${\displaystyle x-y=a}$. For different ${\displaystyle a_{1},a_{2}\in A}$, these corresponding pairs are clearly different. Hence, ${\displaystyle |B|\geq N|A|}$.

Say for a contradiction that ${\displaystyle B}$ contains a corner ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$. Then ${\displaystyle A}$ contains the elements ${\displaystyle x-(y+h),x-y,(x+h)-y}$, which form a 3-term arithmetic progression − a contradiction. Hence, ${\displaystyle B}$ is corner-free, so by the corners theorem, ${\displaystyle |B|=o(N^{2})}$.

Putting everything together, we have ${\displaystyle A\leq |B|/N=o(N^{2})/N=o(N)}$, which is what we set out to prove.