corners theorem

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

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

What follows is a sketch of Solymosi's argument.

Suppose $A\backslash subset\backslash \{1,\backslash ldots,N\backslash \}^2$ is corner-free. Construct an auxiliary tripartite graph $G$ with parts $X=\backslash \{x\_1,\backslash ldots,x\_N\backslash \}$, $Y=\backslash \{y\_1,\backslash ldots,y\_N\backslash \}$, and $Z=\backslash \{z\_1,\backslash ldots,z\_\{2N\}\backslash \}$, 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.

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

:$\backslash frac\{N^2\}\{2^\{(c\_1+o(1))\backslash sqrt\{\backslash log\_2\; N\}\}\}\backslash le\; r\_\{\backslash angle\}(N)\backslash le\; \backslash frac\{N^2\}\{(\backslash log\backslash log\; N)^\{c\_2\}\},$

where $c\_1\backslash approx\; 1.822$ and $c\_2\backslash approx\; 0.0137$. The lower bound is due to Green,{{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 }} building on the work of Linial and Shraibman.{{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 }} The upper bound is due to Shkredov.{{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 }}

A corner in $\backslash mathbb\{Z\}^d$ is a set of points of the form $\backslash \{a\backslash \}\backslash cup\backslash \{a+he\_i:1\backslash le\; i\backslash le\; d\backslash \}$, where $e\_1,\backslash ldots,e\_d$ is the standard basis of $\backslash mathbb\{R\}^d$, and $h\backslash ne\; 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{{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 }} and Nagle, Rödl, Schacht and Skokan.{{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}}

The multidimensional Szemerédi theorem states that for any fixed finite subset $S\backslash subseteq\backslash mathbb\{Z\}^d$, and for every $\backslash varepsilon>0$, there exists a positive integer $N(S,\backslash varepsilon)$ such that for any $N\backslash ge\; N(S,\backslash varepsilon)$, any subset $A\backslash subseteq\backslash \{1,\backslash ldots,N\backslash \}^d$ with size at least $\backslash varepsilon\; N^d$ contains a subset of the form $a\backslash cdot\; S+h$. This theorem follows from the multidimensional corners theorem by a simple projection argument.{{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 }} In particular, Roth's theorem on arithmetic progressions follows directly from the ordinary corners theorem.

{{Reflist|colwidth=30em}}

• [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

Category:Ramsey theory

Category:Additive combinatorics

Category:Theorems in combinatorics

Category:20th century in mathematics