{{Short description|Statement in arithmetic combinatorics}} thumb In arithmetic combinatorics, the '''corners theorem''' states that for every <math>\varepsilon>0</math>, for large enough <math>N</math>, any set of at least <math>\varepsilon N^2</math> points in the <math>N\times N</math> grid <math>\{1,\ldots,N\}^2</math> contains a corner, i.e., a triple of points of the form <math>\{(x,y), (x+h,y), (x,y+h)\}</math> with <math>h\ne 0</math>. It was first proved by Miklós Ajtai and Endre Szemerédi in 1974 using Szemerédi's theorem.<ref name="szemeredi-ajtai">{{cite journal | last1=Ajtai | first1=Miklós | last2=Szemerédi | first2=Endre | author-link1=Miklós Ajtai | author-link2=Endre Szemerédi| title=Sets of lattice points that form no squares | journal=Stud. Sci. Math. Hungar. | volume=9 | pages=9–11 | year=1974 | mr=0369299}}.</ref> In 2003, József Solymosi gave a short proof using the triangle removal lemma.<ref name=solymosi>{{cite book | first=József | last=Solymosi | author-link = József Solymosi | chapter=Note on a generalization of Roth's theorem | title=Discrete and computational geometry | mr=2038505 | isbn=3-540-00371-1 | publisher=Springer-Verlag | location=Berlin | series=Algorithms and Combinatorics | volume=25 | pages=825–827 | year=2003 | doi=10.1007/978-3-642-55566-4_39 | editor1-first=Boris | editor1-last=Aronov | editor2-first=Saugata | editor2-last=Basu | editor3-first=János | editor3-last=Pach | editor4-first=Micha | editor4-last=Sharir| display-editors = 3 }}</ref>
==Statement== Define a corner to be a subset of <math>\mathbb{Z}^2</math> of the form <math>\{(x,y), (x+h,y), (x,y+h)\}</math>, where <math>x,y,h\in \mathbb{Z}</math> and <math>h\ne 0</math>. For every <math>\varepsilon>0</math>, there exists a positive integer <math>N(\varepsilon)</math> such that for any <math>N\ge N(\varepsilon)</math>, any subset <math>A\subseteq\{1,\ldots,N\}^2</math> with size at least <math>\varepsilon N^2</math> contains a corner.
The condition <math>h\ne 0</math> can be relaxed to <math>h>0</math> by showing that if <math>A</math> is dense, then it has some dense subset that is centrally symmetric.
==Proof overview== What follows is a sketch of Solymosi's argument.
Suppose <math>A\subset\{1,\ldots,N\}^2</math> is corner-free. Construct an auxiliary tripartite graph <math>G</math> with parts <math>X=\{x_1,\ldots,x_N\}</math>, <math>Y=\{y_1,\ldots,y_N\}</math>, and <math>Z=\{z_1,\ldots,z_{2N}\}</math>, where <math>x_i</math> corresponds to the line <math>x=i</math>, <math>y_j</math> corresponds to the line <math>y=j</math>, and <math>z_k</math> corresponds to the line <math>x+y=k</math>. Connect two vertices if the intersection of their corresponding lines lies in <math>A</math>.
Note that a triangle in <math>G</math> corresponds to a corner in <math>A</math>, except in the trivial case where the lines corresponding to the vertices of the triangle concur at a point in <math>A</math>. It follows that every edge of <math>G</math> is in exactly one triangle, so by the triangle removal lemma, <math>G</math> has <math>o(|V(G)|^2)</math> edges, so <math>|A|=o(N^2)</math>, as desired.
==Quantitative bounds== Let <math>r_{\angle}(N)</math> be the size of the largest subset of <math>[N]^2</math> which contains no corner. The best known bounds are :<math>\frac{N^2}{2^{(c_1+o(1))\sqrt{\log_2 N}}}\le r_{\angle}(N)\le \frac{N^2}{(\log\log N)^{c_2}},</math> where <math>c_1=2\sqrt{2\log_2\frac{4}{3}}\approx 1.822</math> and <math>c_2=\frac{1}{73}\approx 0.0137</math>. The lower bound is due to Green,<ref>{{cite journal | last=Green | first=Ben | author-link=Ben Green (mathematician) | title=Lower Bounds for Corner-Free Sets | year = 2021 | journal=New Zealand Journal of Mathematics | volume=51 | pages=1–2 | doi=10.53733/86 | arxiv=2102.11702 }}</ref> building on the work of Linial and Shraibman.<ref>{{cite journal | last1=Linial | first1=Nati |last2=Shraibman | first2=Adi | author-link1=Nati Linial | title=Larger Corner-Free Sets from Better NOF Exactly-N Protocols | journal=Discrete Analysis | year=2021 | volume=2021 | doi=10.19086/da.28933 | arxiv=2102.00421 | s2cid=231740736 }}</ref> The upper bound is due to Shkredov.<ref>{{cite journal | last=Shkredov | first= I.D. | title=On a Generalization of Szemerédi's Theorem | journal=Proceedings of the London Mathematical Society | volume=93 | year=2006 | issue=3 | pages=723–760 | doi=10.1017/S0024611506015991 | arxiv= math/0503639 | s2cid= 55252774 }}</ref>
==Multidimensional extension== A corner in <math>\mathbb{Z}^d</math> is a set of points of the form <math>\{a\}\cup\{a+he_i:1\le i\le d\}</math>, where <math>e_1,\ldots,e_d</math> is the standard basis of <math>\mathbb{R}^d</math>, and <math>h\ne 0</math>. 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<ref name=gowers>{{cite journal | last=Gowers | first=Timothy | author-link=Timothy Gowers | title=Hypergraph regularity and the multidimensional Szemerédi theorem | journal=Annals of Mathematics | volume=166 | year=2007 | issue=3 | pages=897–946 | doi=10.4007/annals.2007.166.897 | mr=2373376| arxiv=0710.3032 | s2cid=56118006 }}</ref> and Nagle, Rödl, Schacht and Skokan.<ref>{{Cite journal|last1=Rodl|first1=V.|last2=Nagle|first2=B.|last3=Skokan|first3=J.|last4=Schacht|first4=M.|last5=Kohayakawa|first5=Y.|date=2005-05-26|title=From The Cover: The hypergraph regularity method and its applications|journal=Proceedings of the National Academy of Sciences|volume=102|issue=23|pages=8109–8113|doi=10.1073/pnas.0502771102|pmid=15919821|pmc=1149431|issn=0027-8424|bibcode=2005PNAS..102.8109R|doi-access=free}}</ref>
===Multidimensional Szemerédi's Theorem=== The multidimensional Szemerédi theorem states that for any fixed finite subset <math>S\subseteq\mathbb{Z}^d</math>, and for every <math>\varepsilon>0</math>, there exists a positive integer <math>N(S,\varepsilon)</math> such that for any <math>N\ge N(S,\varepsilon)</math>, any subset <math>A\subseteq\{1,\ldots,N\}^d</math> with size at least <math>\varepsilon N^d</math> contains a subset of the form <math>a\cdot S+h</math>. This theorem follows from the multidimensional corners theorem by a simple projection argument.<ref name=gowers>{{cite journal | last=Gowers | first=Timothy | author-link=Timothy Gowers | title=Hypergraph regularity and the multidimensional Szemerédi theorem | journal=Annals of Mathematics | volume=166 | year=2007 | issue=3 | pages=897–946 | doi=10.4007/annals.2007.166.897 | mr=2373376| arxiv=0710.3032 | s2cid=56118006 }}</ref> In particular, Roth's theorem on arithmetic progressions follows directly from the ordinary corners theorem.
==References== {{Reflist|colwidth=30em}}
==External links== *[http://michaelnielsen.org/polymath1/index.php?title=Ajtai-Szemer%C3%A9di%27s_proof_of_the_corners_theorem Proof of the corners theorem] on polymath.
Category:1974 introductions Category:1974 in science <!-- first proof --> <!-- Category:2003 in mathematics --><!-- shorter proof --> Category:Ramsey theory Category:Additive combinatorics Category:Theorems in combinatorics Category:20th century in mathematics