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, Solymosi (2003) gave a simpler proof, based on the triangle removal lemma. The corners theorem implies Roth's theorem.

This figure shows a grid and a subset with 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 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 horizontal 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 (corresponding to an intersection of lines at some point ) is contained in exactly one triangle (namely the triangle with vertices corresponding to the three lines passing through ). 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.

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)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.