# Corners theorem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Corners_theorem
> Markdown URL: https://mediated.wiki/source/Corners_theorem.md
> Source: https://en.wikipedia.org/wiki/Corners_theorem
> Source revision: 1356804313
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Statement in arithmetic combinatorics}}
thumb
In [arithmetic combinatorics](/source/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](/source/Mikl%C3%B3s_Ajtai) and [Endre Szemerédi](/source/Endre_Szemer%C3%A9di) in 1974 using [Szemerédi's theorem](/source/Szemer%C3%A9di'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](/source/J%C3%B3zsef_Solymosi) gave a short proof using the [triangle removal lemma](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/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

---
Adapted from the Wikipedia article [Corners theorem](https://en.wikipedia.org/wiki/Corners_theorem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Corners_theorem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.