Corners theorem

In mathematics, the corners theorem is a result in arithmetic combinatorics proved by Miklós Ajtai and Endre Szemerédi. It states that for every ${\displaystyle \varepsilon >0}$, for large enough ${\displaystyle N}$, any set of at least ${\displaystyle \varepsilon N^{2}}$ points in the ${\displaystyle N\times N}$ grid ${\displaystyle \{1,\ldots ,N\}\times \{1,\ldots ,N\}}$ contains a corner, i.e., a triple of points of the form ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$. Later, Solymosi (2003) gave a simpler proof, based on the triangle removal lemma. The corners theorem implies Roth's theorem.

This figure shows a ${\displaystyle 6\times 6}$ grid and a subset with ${\displaystyle {\frac {1}{2}}}$ of the points marked with red. This selection of points contains a total of 2 corners, which are marked in green and blue, respectively.

Statement and proof of the corners theorem

Definition

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}$.

Formal statement of corners theorem

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}}$.

Proof

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.

A proof of Roth's theorem from the corners theorem

Roth's theorem is the special case of Szemerédi's theorem for arithmetic progressions of length 3.

Roth's theorem. If ${\displaystyle A\subseteq \{1,2,\ldots ,N\}}$ contains no 3-term arithmetic progression, then ${\displaystyle |A|=o(N)}$

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.

References

• Ajtai, Miklós; Szemerédi, Endre (1974). "Sets of lattice points that form no squares". Stud. Sci. Math. Hungar. 9: 9–11. MR 0369299.
• Solymosi, József (2003). "Note on a generalization of Roth's theorem". In Aronov, Boris; Basu, Saugata; Pach, János; et al. (eds.). Discrete and computational geometry. Algorithms and Combinatorics. 25. Berlin: Springer-Verlag. pp. 825–827. doi:10.1007/978-3-642-55566-4_39. ISBN 3-540-00371-1. MR 2038505.CS1 maint: ref=harv (link)

External links

• Proof of the corners theorem on polymath.