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 $\varepsilon >0$, for large enough $N$, any set of at least $\varepsilon N^{2}$ points in the $N\times N$ grid $\{1,\ldots ,N\}\times \{1,\ldots ,N\}$ contains a corner, i.e., a triple of points of the form $\{(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.

Statement and proof of the corners theorem

Definition

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

Formal statement of corners theorem

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

Proof

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

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

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

The proof

We have $A\subseteq \{1,2,\ldots ,N\}$ that does not contain any 3-term arithmetic progression. Define $B=\{(x,y)\in \{1,2,\ldots ,2N\}\times \{1,2,\ldots ,2N\}|x-y\in A\}$. Note that for each $a\in A$, there are at least $N$ pairs $(x,y)\in \{1,2,\ldots ,2N\}\times \{1,2,\ldots ,2N\}$ such that $x-y=a$. For different $a_{1},a_{2}\in A$, these corresponding pairs are clearly different. Hence, $|B|\geq N|A|$.

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

Putting everything together, we have $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. Vol. 25. Berlin: Springer-Verlag. pp. 825–827. doi:10.1007/978-3-642-55566-4_39. ISBN 3-540-00371-1. MR 2038505. {{cite book}}: Invalid |ref=harv (help)

External links

• Proof of the corners theorem on polymath.