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, for large enough, any set of at least points in the grid contains a corner, i.e., a triple of points of the form. Later, 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 of the form, where and.

Formal statement of corners theorem

If ' is a subset of the grid ' that contains no corner, then the size of ' is '. In other words, for any, there is a such that for any, any corner-free subset of is smaller than .

Proof

We would first like to replace the condition ' with. To achieve this, we consider the set'. By the pigeonhole principle, there exists a point ' such that it can be represented as ' for at least ' pairs '. We choose this point ' and construct a new set '. Observe that ', as the size of ' is the number of ways of writing '. Further observe that it suffices to show that '. Note that is a subset of, so it has no corner, i.e., no subset of the form for. But is also a subset of, so it also has no anticorner, i.e., no subset of the form with. Hence, has no subset of the form for, which is the condition we sought.
To show , we construct an auxiliary tripartite graph. The first part has vertex set, where the vertices correspond to the vertical lines. The second part has vertex set, where the vertices correspond to the vertical lines. The third part has vertex set, where the vertices correspond to the slanted lines with slope. We draw an edge between two vertices if the corresponding lines intersect at a point in.
Let us now think about the triangles in the auxiliary graph. Note that for each point, the vertices of corresponding to the horizontal, vertical, and slanted lines passing through form a triangle in. A case check reveals that if contained any other triangle, then there would be a corner or anticorner, so does not contain any other triangle. With this characterization of all the triangles in, observe that each edge of is contained in exactly one triangle. It is a well-known corollary of the triangle removal lemma that a graph on vertices in which each edge is in a unique triangle has edges. Hence, has edges. But note that we can count the edges of exactly by just counting all the intersections at points in – there are such intersections. Hence,, from which. 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 contains no 3-term arithmetic progression, then

The proof

We have that does not contain any 3-term arithmetic progression. Define the following set
.
For each, there are at least pairs such that. For different, these corresponding pairs are clearly different. Hence,.
Say for a contradiction that contains a corner. Then contains the elements, which form a 3-term arithmetic progression − a contradiction. Hence, is corner-free, so by the corners theorem,.
Putting everything together, we have, which is what we set out to prove.