Teorema de las esquinas

Esta figura muestra una cuadrícula y un subconjunto de los puntos marcados en rojo. Esta selección de puntos contiene un total de 2 esquinas, que están marcadas en verde y azul, respectivamente.${\displaystyle 6\times 6}$${\displaystyle {\frac {1}{2}}}$

En matemáticas, el teorema de las esquinas es un resultado de la combinatoria aritmética probada por Miklós Ajtai y Endre Szemerédi . Establece que para cada , para lo suficientemente grande , cualquier conjunto de al menos puntos en la cuadrícula contiene una esquina, es decir, un triple de puntos de la forma . Más tarde, Solymosi (2003) dio una demostración más simple, basada en el lema de eliminación de triángulos . El teorema de las esquinas implica el teorema de Roth . ${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle \varepsilon N^{2}}$${\displaystyle N\times N}$${\displaystyle \{1,\ldots ,N\}\times \{1,\ldots ,N\}}$${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$

Declaración y demostración del teorema de las esquinas

Definición

Una esquina es un subconjunto del formulario , donde y .${\displaystyle \mathbb {Z} ^{2}}$${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$${\displaystyle x,y,h\in \mathbb {Z} }$${\displaystyle h>0}$

Enunciado formal del teorema de las esquinas

Si es un subconjunto de la cuadrícula que no contiene esquinas, entonces el tamaño de es . En otras palabras, para cualquiera , existe tal que para cualquiera , cualquier subconjunto sin esquinas de es más pequeño que .${\displaystyle A}$${\displaystyle N\times N}$${\displaystyle \{1,\ldots ,N\}\times \{1,\ldots ,N\}}$${\displaystyle A}$${\displaystyle o(N^{2})}$${\displaystyle \varepsilon }$${\displaystyle N_{0}}$${\displaystyle N\geq N_{0}}$${\displaystyle A}$${\displaystyle \{1,\ldots ,N\}\times \{1,\ldots ,N\}}$${\displaystyle \varepsilon N^{2}}$

Prueba

Primero nos gustaría reemplazar la condición con . Para lograr esto, consideramos el conjunto . Según el principio del casillero , existe un punto tal que se puede representar como por al menos pares . Elegimos este punto y construimos un nuevo conjunto . Observe que , ya que el tamaño de es el número de formas de escritura . Observe además que basta con demostrarlo . Tenga en cuenta que es un subconjunto de , por lo que no tiene esquina, es decir, ningún subconjunto del formulario para . Pero también es un subconjunto de , por lo que tampoco tiene anticorner, es decir, ningún subconjunto de la forma con . Por eso,${\displaystyle h>0}$${\displaystyle h\neq 0}$${\displaystyle A+A\subset \{1,\ldots ,2N\}\times \{1,\ldots ,2N\}}$${\displaystyle c\in A+A}$${\displaystyle c=a+b}$${\displaystyle {\frac {|A|^{2}}{(2N)^{2}}}}$${\displaystyle a,b\in A}$${\displaystyle c}$${\displaystyle A':=A\cap (c-A)}$${\displaystyle |A'|\geq {\frac {|A|^{2}}{(2N)^{2}}}}$${\displaystyle A'}$${\displaystyle c=a+b}$${\displaystyle |A'|=o(N^{2})}$${\displaystyle A'}$${\displaystyle A}$${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$${\displaystyle h>0}$${\displaystyle A'}$${\displaystyle c-A}$${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$${\displaystyle h<0}$${\displaystyle A'}$no tiene ningún subconjunto del formulario para , que es la condición que buscamos.${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$${\displaystyle h\neq 0}$

Para mostrar , construimos un gráfico tripartito auxiliar . La primera parte tiene un conjunto de vértices , donde los vértices corresponden a las líneas verticales . La segunda parte tiene un conjunto de vértices , donde los vértices corresponden a las líneas horizontales . La tercera parte tiene conjunto de vértices , donde los vértices corresponden a las líneas inclinadas con pendiente . Dibujamos un borde entre dos vértices si las líneas correspondientes se cruzan en un punto en .${\displaystyle |A'|=o(N^{2})}$${\displaystyle G}$${\displaystyle U=\{u_{1},\ldots ,u_{N}\}}$${\displaystyle N}$${\displaystyle x=i}$${\displaystyle V=\{v_{1},\ldots ,v_{N}\}}$${\displaystyle N}$${\displaystyle y=j}$${\displaystyle W=\{w_{1},\ldots ,w_{2N}\}}$${\displaystyle 2N}$${\displaystyle y=-x+k}$${\displaystyle -1}$${\displaystyle A'}$

Pensemos ahora en los triángulos del gráfico auxiliar . Tenga en cuenta que para cada punto , los vértices correspondientes a las líneas horizontales, verticales e inclinadas que pasan forman un triángulo en . Una verificación de caso revela que si contiene cualquier otro triángulo, entonces habría una esquina o anticorner, por lo que no contiene ningún otro triángulo. Con esta caracterización de todos los triángulos en , observe que cada borde de (correspondiente a una intersección de líneas en algún punto ) está contenido exactamente en un triángulo (es decir, el triángulo con vértices correspondientes a las tres líneas que lo atraviesan ). Es un corolario bien conocido del lema de eliminación de triángulos.${\displaystyle G}$${\displaystyle x\in A'}$${\displaystyle G}$${\displaystyle x}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle x\in A'}$${\displaystyle x\in A'}$que un gráfico de vértices en el que cada borde está en un triángulo único tiene bordes. Por tanto, tiene aristas. Pero tenga en cuenta que podemos contar los bordes de exactamente simplemente contando todas las intersecciones en los puntos de , existen tales intersecciones. Por lo tanto, de la cual . Esto completa la prueba.${\displaystyle n}$${\displaystyle o(n^{2})}$${\displaystyle G}$${\displaystyle o(N^{2})}$${\displaystyle G}$${\displaystyle A'}$${\displaystyle 3|A'|}$${\displaystyle 3|A|'=|E(G)|=o(N^{2})}$${\displaystyle |A'|=o(N^{2})}$

Una prueba del teorema de Roth a partir del teorema de las esquinas

El teorema de Roth es el caso especial del teorema de Szemerédi para progresiones aritméticas de longitud 3.

Teorema de Roth. Si no contiene una progresión aritmética de 3 términos, entonces${\displaystyle A\subseteq \{1,2,\ldots ,N\}}$${\displaystyle |A|=o(N)}$

La prueba

Tenemos que no contiene ninguna progresión aritmética de 3 términos. Defina el siguiente conjunto${\displaystyle A\subseteq \{1,2,\ldots ,N\}}$

${\displaystyle B=\{(x,y)\in \{1,2,\ldots ,2N\}\times \{1,2,\ldots ,2N\}|x-y\in A\}}$.

Para cada uno , hay al menos pares tales que . Para diferentes , estos pares correspondientes son claramente diferentes. Por lo tanto, .${\displaystyle a\in A}$${\displaystyle N}$${\displaystyle (x,y)\in \{1,2,\ldots ,2N\}\times \{1,2,\ldots ,2N\}}$${\displaystyle x-y=a}$${\displaystyle a_{1},a_{2}\in A}$${\displaystyle |B|\geq N|A|}$

Digamos por una contradicción que contiene una esquina . Luego contiene los elementos , que forman una progresión aritmética de 3 términos: una contradicción. Por lo tanto, está libre de la esquina, así que por el teorema de esquinas, . ${\displaystyle B}$${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$${\displaystyle A}$${\displaystyle x-(y+h),x-y,(x+h)-y}$${\displaystyle B}$${\displaystyle |B|=o(N^{2})}$

Poniendo todo junto, tenemos , que es lo que nos propusimos demostrar.${\displaystyle |A|\leq |B|/N=o(N^{2})/N=o(N)}$

Referencias

• Ajtai, Miklós; Szemerédi, Endre (1974). "Conjuntos de puntos de celosía que no forman cuadrados". Semental. Sci. Matemáticas. Hungar . 9 : 9-11. Señor  0369299 .
• Solymosi, József (2003). "Nota sobre una generalización del teorema de Roth". En Aronov, Boris; Basu, Saugata; Pach, János; et al. (eds.). Geometría discreta y computacional . Algoritmos y Combinatoria. 25 . Berlín: Springer-Verlag. págs. 825–827. doi : 10.1007 / 978-3-642-55566-4_39 . ISBN 3-540-00371-1. Señor  2038505 .

enlaces externos

• Prueba del teorema de las esquinas en el erudito.