In arithmetic combinatorics, the corners theorem 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 with . It was first proved by Miklós Ajtai and Endre Szemerédi in 1974 using Szemerédi's theorem.[1] In 2003, József Solymosi gave a short proof using the triangle removal lemma.[2]

Statement

edit

Define a corner to be a subset of   of the form  , where   and  . For every  , there exists a positive integer   such that for any  , any subset   with size at least   contains a corner.

The condition   can be relaxed to   by showing that if   is dense, then it has some dense subset that is centrally symmetric.

Proof overview

edit

What follows is a sketch of Solymosi's argument.

Suppose   is corner-free. Construct an auxiliary tripartite graph   with parts  ,  , and  , where   corresponds to the line  ,   corresponds to the line  , and   corresponds to the line  . Connect two vertices if the intersection of their corresponding lines lies in  .

Note that a triangle in   corresponds to a corner in  , except in the trivial case where the lines corresponding to the vertices of the triangle concur at a point in  . It follows that every edge of   is in exactly one triangle, so by the triangle removal lemma,   has   edges, so  , as desired.

Quantitative bounds

edit

Let   be the size of the largest subset of   which contains no corner. The best known bounds are

 

where   and  . The lower bound is due to Green,[3] building on the work of Linial and Shraibman.[4] The upper bound is due to Shkredov.[5]

Multidimensional extension

edit

A corner in   is a set of points of the form  , where   is the standard basis of  , and  . The natural extension of the corners theorem to this setting can be shown using the hypergraph removal lemma, in the spirit of Solymosi's proof. The hypergraph removal lemma was shown independently by Gowers[6] and Nagle, Rödl, Schacht and Skokan.[7]

Multidimensional Szemerédi's Theorem

edit

The multidimensional Szemerédi theorem states that for any fixed finite subset  , and for every  , there exists a positive integer   such that for any  , any subset   with size at least   contains a subset of the form  . This theorem follows from the multidimensional corners theorem by a simple projection argument.[6] In particular, Roth's theorem on arithmetic progressions follows directly from the ordinary corners theorem.

References

edit
  1. ^ Ajtai, Miklós; Szemerédi, Endre (1974). "Sets of lattice points that form no squares". Stud. Sci. Math. Hungar. 9: 9–11. MR 0369299..
  2. ^ 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.
  3. ^ Green, Ben (2021). "Lower Bounds for Corner-Free Sets". New Zealand Journal of Mathematics. 51. arXiv:2102.11702. doi:10.53733/86.
  4. ^ Linial, Nati; Shraibman, Adi (2021). "Larger Corner-Free Sets from Better NOF Exactly-N Protocols". Discrete Analysis. 2021. arXiv:2102.00421. doi:10.19086/da.28933. S2CID 231740736.
  5. ^ Shkredov, I.D. (2006). "On a Generalization of Szemerédi's Theorem". Proceedings of the London Mathematical Society. 93 (3): 723–760. arXiv:math/0503639. doi:10.1017/S0024611506015991. S2CID 55252774.
  6. ^ a b Gowers, Timothy (2007). "Hypergraph regularity and the multidimensional Szemerédi theorem". Annals of Mathematics. 166 (3): 897–946. arXiv:0710.3032. doi:10.4007/annals.2007.166.897. MR 2373376. S2CID 56118006.
  7. ^ Rodl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (2005-05-26). "From The Cover: The hypergraph regularity method and its applications". Proceedings of the National Academy of Sciences. 102 (23): 8109–8113. Bibcode:2005PNAS..102.8109R. doi:10.1073/pnas.0502771102. ISSN 0027-8424. PMC 1149431. PMID 15919821.
edit