Teorema de las esquinas

En combinatoria aritmética, el teorema de las esquinas declara que para cada $\varepsilon >0$ , para $N$ suficientemente grande, cualquier conjunto con al menos $\varepsilon N^{2}$ puntos en el látice de $N\times N$ dado por $\{1,\ldots ,N\}^{2}$ contiene una esquina, es decir una terna de puntos de la forma $\{(x,y),(x+h,y),(x,y+h)\}$ con $h\neq 0$ . Fue probado primero por Miklós Ajtai y Endre Szemerédi en 1974 utilizando el Teorema de Szemerédi.^[1] En 2003, József Solymosi dio una prueba corta utilizando el lema de extracción del triángulo.^[2]

Enunciado

Definimos una esquina como un subconjunto de $\mathbb {Z} ^{2}$ de la forma $\{(x,y),(x+h,y),(x,y+h)\}$ , donde y $x,y,h\in \mathbb {Z}$ . Para cada $h\neq 0$ , existe un entero positivo $N(\varepsilon )$ tal que para cualquier $\varepsilon >0$ , cualquier $N\geq N(\varepsilon )$ , cualquier subconjunto $A\subseteq \{1,\ldots ,N\}^{2}$ con tamaño al menos $\varepsilon N^{2}$ contiene una esquina.

La condición $h\neq 0$ puede ser relajada a $h>0$ , mostrando que si $A$ es denso, entonces tiene algún subconjunto denso que es centralmente simétrico.

Visión general de la prueba

Lo que sigue es un esbozo del argumento de Solymosi.

Supongamos que $A\subset \{1,\ldots ,N\}^{2}$ es un conjunto libre de esquinas. Construir un grafo auxiliar tripartito $G$ con partes $X=\{x_{1},\ldots ,x_{N}\}$ , $Y=\{y_{1},\ldots ,y_{N}\}$ , y $Z=\{z_{1},\ldots ,z_{2N}\}$ , donde $x_{i}$ corresponde a la línea $x=i$ , $y_{j}$ corresponde a la línea $y=j$ , y $z_{k}$ corresponde a la línea $x+y=k$ . Conectamos dos vértices si la intersección de sus líneas correspondientes se encuentra en $A$ .

Notemos que un triángulo en $G$ corresponde a una esquina en $A$ , exceptuando el caso trivial donde las líneas que corresponden a los vértices del triángulo concur en un punto en $A$ . Sigue que cada arista de $G$ se encuentra en exactamente un triángulo, por lo tanto, por el lema de extracción del triángulo, $G$ tiene $o(|V(G)|^{2})$ aristas, así que $|A|=o(N^{2})$ , como deseábamos mostrar.

Cuotas cuantitativas

Sea $r_{\angle }(N)$ la medida del subconjunto más grande de $[N]^{2}$ tal que no contiene ninguna esquina. Las mejores cuotas conocidas son

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

donde $c_{1}\approx 1.822$ y $c_{2}\approx 0.0137$ . La cuota más baja fue demostrada por Green, construyendo a partir del trabajo de Linial y Shraibman^[3]. La cuota superior fue demostrada por Shkredov.^[4]

Extensión multidimensional

Una esquina en $\mathbb {Z} ^{d}$ es un conjunto de puntos de la forma $\{a\}\cup \{a+he_{i}:1\leq i\leq d\}$ , dónde $e_{1},\ldots ,e_{d}$ es la base estándar de $\mathbb {R} ^{d}$ , y $h\neq 0$ . La extensión natural del teorema de esquinas a esta situación general puede ser mostrada utilizando el lema de extracción de hipergrafo, en el espíritu de la prueba de Solymosi. El lema de extracción de hieprgrafo fue mostrado independientemente por Gowers^[5] y Nagle, Rödl, Schacht y Skokan^[6].

Teorema Multidimensional de Szemerédi

El teorema multidimensional de Szemerédi declara que para cualquier subconjunto finito fijo $S\subseteq \mathbb {Z} ^{d}$ , y para cada $\varepsilon >0$ , existe un entero positivo $N(S,\varepsilon )$ tal que para cualquier $N\geq N(S,\varepsilon )$ , cualquier subconjunto $A\subseteq \{1,\ldots ,N\}^{d}$ con tamaño al menos $\varepsilon N^{d}$ contiene un subconjunto de la forma $a\cdot S+h$ . Este teorema sigue del teorema de esquinas multidimensional mediante un argumento de proyección sencillo^[5]. En particular, el teorema de Roth sigue directamente del teorema de esquinas normal.