Corners theorem: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 17:21, 8 December 2024

In arithmetic combinatorics, the corners theorem states that for every $\varepsilon >0$ , for large enough $N$ , any set of at least $\varepsilon N^{2}$ points in the $N\times N$ grid $\{1,\ldots ,N\}^{2}$ contains a corner, i.e., a triple of points of the form $\{(x,y),(x+h,y),(x,y+h)\}$ with $h\neq 0$ . 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

Define a corner to be a subset of $\mathbb {Z} ^{2}$ of the form $\{(x,y),(x+h,y),(x,y+h)\}$ , where $x,y,h\in \mathbb {Z}$ and $h\neq 0$ . For every $\varepsilon >0$ , there exists a positive integer $N(\varepsilon )$ such that for any $N\geq N(\varepsilon )$ , any subset $A\subseteq \{1,\ldots ,N\}^{2}$ with size at least $\varepsilon N^{2}$ contains a corner.

The condition $h\neq 0$ can be relaxed to $h>0$ by showing that if $A$ is dense, then it has some dense subset that is centrally symmetric.

Proof overview

What follows is a sketch of Solymosi's argument.

Suppose $A\subset \{1,\ldots ,N\}^{2}$ is corner-free. Construct an auxiliary tripartite graph $G$ with parts $X=\{x_{1},\ldots ,x_{N}\}$ , $Y=\{y_{1},\ldots ,y_{N}\}$ , and $Z=\{z_{1},\ldots ,z_{2N}\}$ , where $x_{i}$ corresponds to the line $x=i$ , $y_{j}$ corresponds to the line $y=j$ , and $z_{k}$ corresponds to the line $x+y=k$ . Connect two vertices if the intersection of their corresponding lines lies in $A$ .

Note that a triangle in $G$ corresponds to a corner in $A$ , except in the trivial case where the lines corresponding to the vertices of the triangle concur at a point in $A$ . It follows that every edge of $G$ is in exactly one triangle, so by the triangle removal lemma, $G$ has $o(|V(G)|^{2})$ edges, so $|A|=o(N^{2})$ , as desired.

Quantitative bounds

Let $r_{\angle }(N)$ be the size of the largest subset of $[N]^{2}$ which contains no corner. The best known bounds are

{\frac {N^{2}}{2^{(c_{1}+o(1)){\sqrt {\log _{2}N}}}}}\leq r_{\angle }(N)\leq {\frac {N^{2}}{(\log \log N)^{c_{2}}}},

where $c_{1}\approx 1.822$ and $c_{2}\approx 0.0137$ . 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

A corner in $\mathbb {Z} ^{d}$ is a set of points of the form $\{a\}\cup \{a+he_{i}:1\leq i\leq d\}$ , where $e_{1},\ldots ,e_{d}$ is the standard basis of $\mathbb {R} ^{d}$ , and $h\neq 0$ . 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

The multidimensional Szemerédi theorem states that for any fixed finite subset $S\subseteq \mathbb {Z} ^{d}$ , and for every $\varepsilon >0$ , there exists a positive integer $N(S,\varepsilon )$ such that for any $N\geq N(S,\varepsilon )$ , any subset $A\subseteq \{1,\ldots ,N\}^{d}$ with size at least $\varepsilon N^{d}$ contains a subset of the form $a\cdot S+h$ . 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

^ 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. Vol. 25. Berlin: Springer-Verlag. pp. 825–827. doi:10.1007/978-3-642-55566-4_39. ISBN 3-540-00371-1. MR 2038505.
^ Green, Ben (2021). "Lower Bounds for Corner-Free Sets". New Zealand Journal of Mathematics. 51: 1–2. arXiv:2102.11702. doi:10.53733/86.
^ 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.
^ 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.
^ ^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.
^ 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.

External links

Proof of the corners theorem on polymath.

[szemeredi-ajtai-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..

[solymosi-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: 1–2. 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.

[gowers-6] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
+{{Short description|Statement in arithmetic combinatorics}}
-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 <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\}\times\{1,\ldots,N\}</math> contains a corner, i.e., a triple of points of the form <math>\{(x,y), (x+h,y), (x,y+h)\}</math>. Later, {{harvtxt|Solymosi|2003}} gave a simpler proof, based on the [[triangle removal lemma]]. The corners theorem implies [[Szemerédi's theorem|Roth's theorem]].
+[[File:Иллюстрация_уголков.png|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 and proof of the corners theorem ==
+==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.
-=== Definition ===
-A '''corner''' is 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>0</math>.
+==Proof overview==
-=== Formal statement of corners theorem ===
+What follows is a sketch of Solymosi's argument.
-If ''<math>A</math>'' is a subset of the <math>N\times N</math> grid ''<math>\{1,\ldots,N\}\times\{1,\ldots,N\}</math>'' that contains no corner, then the size of ''<math>A</math>'' is ''<math>o(N^2)</math>''. In other words, for any <math>\varepsilon</math>, there is a <math>N_0</math> such that for any <math>N\geq N_0</math>, any corner-free subset <math>A</math> of <math>\{1,\ldots,N\}\times\{1,\ldots,N\}</math> is smaller than ''<math>\varepsilon N^2</math>''.
+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>.
-=== Proof ===
-We would first like to replace the condition ''<math>h>0</math>'' with <math>h\neq 0</math>. To achieve this, we consider the set''<math>A+A\subset \{1,\ldots,2N\}\times \{1,\ldots,2N\}</math>''. By the [[Pigeonhole principle|pigeonhole principle]], there exists a point ''<math>c\in A+A</math>'' such that it can be represented as ''<math>c=a+b</math>'' for at least ''<math>\frac{|A|^2}{(2N)^2}</math>'' pairs ''<math>a,b\in A</math>''. We choose this point ''<math>c</math>'' and construct a new set ''<math>A':=A \cap (c-A)</math>''. Observe that ''<math>|A'|\ge \frac{|A|^2}{(2N)^2}</math>'', as the size of ''<math>A'</math>'' is the number of ways of writing ''<math>c=a+b</math>''. Further observe that it suffices to show that ''<math>|A'| = o(N^2)</math>''. Note that <math>A'</math> is a subset of <math>A</math>, so it has no corner, i.e., no subset of the form <math>\{(x,y), (x+h,y), (x,y+h)\}</math> for <math>h>0</math>. But <math>A'</math> is also a subset of <math>c-A</math>, so it also has no anticorner, i.e., no subset of the form <math>\{(x,y), (x+h,y), (x,y+h)\}</math> with h<0. Hence, <math>A'</math> has no subset of the form <math>\{(x,y), (x+h,y), (x,y+h)\}</math> for <math>h\ne 0</math>, which is the condition we sought.
-To show ''<math>|A'|= o(N^2)</math>'', we construct an auxiliary tripartite graph <math>G</math>. The first part has vertex set <math>U=\{u_1,\ldots,u_N\}</math>, where the vertices correspond to the <math>N</math> vertical lines <math>x=i</math>. The second part has vertex set <math>V=\{v_1,\ldots,v_N\}</math>, where the vertices correspond to the <math>N</math> vertical lines <math>y=j</math>. The third part has vertex set <math>W=\{w_1,\ldots,w_{2N}\},</math>, where the vertices correspond to the <math>2N</math> slanted lines <math>y=-x+k</math> with slope <math>-1</math>. We draw an edge between two vertices if the corresponding lines intersect at a point 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 us now think about the triangles in the auxiliary graph <math>G</math>. Note that for each point <math>x\in A'</math>, the vertices of <math>G</math> corresponding to the horizontal, vertical, and slanted lines passing through <math>x</math> form a triangle in <math>G</math>. A case check reveals that if <math>G</math> contained any other triangle, then there would be a corner or anticorner, so <math>G</math> does not contain any other triangle. With this characterization of all the triangles in <math>G</math>, observe that each edge of <math>G</math> (corresponding to an intersection of lines at some point <math>x\in A'</math>) is contained in exactly one triangle (namely the triangle with vertices corresponding to the three lines passing through <math>x\in A'</math>). It is a well-known corollary of the [[graph removal lemma|triangle removal lemma]] that a graph on <math>n</math> vertices in which each edge is in a unique triangle has <math>o(n^2)</math> edges. Hence, <math>G</math> has <math>o(N^2)</math> edges. But note that we can count the edges of <math>G</math> exactly by just counting all the intersections at points in <math>A'</math> – there are <math>3|A'|</math> such intersections. Hence, <math>3|A|'=|E(G)|=o(N^2)</math>, from which <math>|A'|=o(N^2)</math>. This completes the proof.
+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\approx 1.822</math> and <math>c_2\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 proof of Roth's theorem from the corners theorem ==
+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>
-Roth's theorem is the special case of [[Szemerédi's theorem]] for arithmetic progressions of length 3.
-<blockquote>'''Roth's theorem.''' If <math>A\subseteq\{1,2,\ldots, N\}</math> contains no 3-term arithmetic progression, then <math>|A|=o(N)</math>
-</blockquote>
+===Multidimensional Szemerédi's Theorem===
-=== The proof ===
+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.
-We have <math>A\subseteq\{1,2,\ldots, N\}</math> that does not contain any 3-term arithmetic progression. Define <math>B=\{(x,y)\in \{1,2,\ldots, 2N\}\times \{1,2,\ldots, 2N\}|x-y\in A\}</math>. Note that for each <math>a\in A</math>, there are at least <math>N</math> pairs <math>(x,y)\in \{1,2,\ldots, 2N\}\times \{1,2,\ldots, 2N\}</math> such that <math>x-y=a</math>. For different <math>a_1, a_2\in A</math>, these corresponding pairs are clearly different. Hence, <math>|B|\geq N|A|</math>.
-Say for a contradiction that <math>B</math> contains a corner <math>\{(x,y), (x+h,y), (x,y+h)\}</math>. Then <math>A</math> contains the elements <math>x-(y+h), x-y, (x+h)-y</math>, which form a 3-term arithmetic progression − a contradiction. Hence, <math>B</math> is corner-free, so by the corners theorem, <math>|B|=o(N^2)</math>.
-Putting everything together, we have <math>A\leq |B|/N=o(N^2)/N=o(N)</math>, which is what we set out to prove.
-<br />
 ==References==
+{{Reflist|colwidth=30em}}
-* {{cite journal | last1=Ajtai | first1=Miklós | last2=Szemerédi | first2=Endre | title=Sets of lattice points that form no squares | journal=Stud. Sci. Math. Hungar. | volume=9 | pages=9-11 | year=1974 | mr=0369299}}
-* {{cite book | first=József | last=Solymosi | authorlink = 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=harv}}
 ==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]]