Teorema de las esquinas

En combinatoria aritmética , el teorema de las esquinas establece que para cada${\displaystyle \varepsilon >0}$, para lo suficientemente grande${\displaystyle N}$cualquier conjunto de al menos${\displaystyle \varepsilon N^{2}}$puntos en el${\displaystyle N\times N}$red${\displaystyle \{1,\ldots ,N\}^{2}}$contiene una esquina, es decir, una terna de puntos de la forma${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$con${\displaystyle h\neq 0}$. Fue demostrado por primera vez por Miklós Ajtai y Endre Szemerédi en 1974 utilizando el teorema de Szemerédi . ^{[ 1 ]} En 2003, József Solymosi dio una breve prueba utilizando el lema de eliminación de triángulos . ^{[ 2 ]}

Definir una esquina como un subconjunto de${\displaystyle \mathbb {Z} ^{2}}$de la forma${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$, dónde${\displaystyle x,y,h\in \mathbb {Z} }$y${\displaystyle h\neq 0}$. Por cada${\displaystyle \varepsilon >0}$Existe un número entero positivo.${\ Displaystyle N (\ varepsilon)}$de tal manera que para cualquier${\displaystyle N\geq N(\varepsilon)}$cualquier subconjunto${\displaystyle A\subseteq \{1,\ldots ,N\}^{2}}$con tamaño al menos${\displaystyle \varepsilon N^{2}}$contiene una esquina.

La condición${\displaystyle h\neq 0}$puede relajarse${\displaystyle h>0}$demostrando que si${\displaystyle A}$Si es denso, entonces tiene algún subconjunto denso que es simétrico respecto al centro.

A continuación se presenta un esbozo del argumento de Solymosi.

Suponer${\displaystyle A\subset \{1,\ldots ,N\}^{2}}$no tiene vértices. Construya un grafo tripartito auxiliar.${\displaystyle G}$con piezas${\displaystyle X=\{x_{1},\ldots ,x_{N}\}}$,${\displaystyle Y=\{y_{1},\ldots,y_{N}\}}$, y${\displaystyle Z=\{z_{1},\ldots,z_{2N}\}}$, dónde${\displaystyle x_{i}}$corresponde a la línea${\displaystyle x=i}$,${\displaystyle y_{j}}$corresponde a la línea${\displaystyle y=j}$, y${\displaystyle z_{k}}$corresponde a la línea${\displaystyle x+y=k}$. Conecta dos vértices si la intersección de sus líneas correspondientes se encuentra en${\displaystyle A}$.

Tenga en cuenta que un triángulo en${\displaystyle G}$corresponde a una esquina en${\displaystyle A}$, excepto en el caso trivial en el que las líneas correspondientes a los vértices del triángulo coinciden en un punto en${\displaystyle A}$. De ello se deduce que cada borde de${\displaystyle G}$está en exactamente un triángulo, por lo que por el lema de eliminación de triángulos ,${\displaystyle G}$tiene${\displaystyle o(|V(G)|^{2})}$bordes, por lo tanto${\displaystyle |A|=o(N^{2})}$, según se desee.

Dejar${\displaystyle r_{\angle }(N)}$sea ​​el tamaño del subconjunto más grande de${\displaystyle [N]^{2}}$que no contiene ninguna esquina. Los límites mejor conocidos son

${\displaystyle {\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}}}},}$

dónde${\displaystyle c_{1}=2{\sqrt {2\log _{2}{\frac {4}{3}}}}\approx 1.822}$y${\displaystyle c_{2}={\frac {1}{73}}\approx 0.0137}$. El límite inferior se debe a Green, ^{[ 3 ]} basándose en el trabajo de Linial y Shraibman. ^{[ 4 ]} El límite superior se debe a Shkredov. ^{[ 5 ]}

Una esquina en${\displaystyle \mathbb {Z} ^{d}}$es un conjunto de puntos de la forma${\displaystyle \{a\}\cup \{a+he_{i}:1\leq i\leq d\}}$, dónde${\displaystyle e_{1},\ldots ,e_{d}}$es la base estándar de${\displaystyle \mathbb {R} ^{d}}$, y${\displaystyle h\neq 0}$La extensión natural del teorema de las esquinas a este contexto puede demostrarse utilizando el lema de eliminación de hipergrafos , siguiendo el espíritu de la demostración de Solymosi. El lema de eliminación de hipergrafos fue demostrado independientemente por Gowers ^{[ 6 ]} y Nagle, Rödl, Schacht y Skokan ^{[ 7 ] .}

• Demostración del teorema de las esquinas en Polymath.