Teorema de la esquina

El teorema de la esquina es un resultado probado en combinatoria aditiva que establece la presencia de alguna estructura ordenada (en el sentido aritmético) llamada esquina en conjuntos bidimensionales suficientemente grandes de cualquier densidad fija.

Para los números naturales, de hecho, estamos hablando de pertenecer a un conjunto de celdas suficientemente denso en una red bidimensional de dos extremos y un punto de ruptura de un ángulo recto con lados de la misma longitud paralelos a los ejes de coordenadas.

Redacción

El teorema se refiere a una red bidimensional y considera conjuntos de pares de números (coordenadas en un espacio bidimensional). Para los números naturales, llamemos esquina al triple de coordenadas. Diremos que un conjunto contiene alguna esquina si contiene los tres puntos de esta esquina. ${\ estilo de visualización x, y, d \ (d \ no = 0)}$ ${\ estilo de visualización \ {{(x, y), (x + d, y), (x, y + d)}\}}$

Para un subconjunto de un retículo bidimensional , definimos su densidad como , es decir, como la proporción de celdas que pertenecen al conjunto entre el retículo completo. $A\subconjunto \{{1,\dots,N}\}^{2}$ ${\displaystyle {\rho _{N}}(A)={\frac {|A|}{N^{2))))$

teorema de la esquina

Para any existe tal que si el conjunto tiene densidad , entonces contiene una esquina. $\delta$ ${\ estilo de visualización N = N (\ delta)}$ $A\subconjunto \{{1,\dots,N}\}^{2}$ ${\ estilo de visualización \ rho _ {N} (A) \ geq \ delta}$

Historial de mejora de resultados

El teorema de la esquina fue demostrado [1] [ 2] por Miklos Ajtai y Endre Szemeredy en 1974-1975 . En 1981, este resultado fue reprobado por Hillel Furstenberg utilizando los métodos de la teoría ergódica . También hay [3] una demostración de Jozsef Solymosi ( Hung. Jozsef Solymosi ), basada en el lema de quitar un triángulo de un gráfico .

Además del hecho de la existencia de , que es suficiente para que cualquier conjunto de densidad al cuadrado contenga una esquina, también es apropiado considerar el orden de crecimiento de la función , o, por el contrario, como la densidad máxima para un determinado , para que es posible un subconjunto sin esquinas. ${\ estilo de visualización N = N (\ delta)}$ $\delta$ ${\ estilo de visualización \ {1, \ puntos, N \}^ {2))$ ${\ estilo de visualización N (\ delta)}$ ${\ estilo de visualización \ delta (N)}$ $\delta$ $norte$

Si se denota como la densidad del subconjunto máximo del cuadrado que no contiene esquinas, entonces el teorema de la esquina principal es equivalente a la afirmación de que , y es apropiado considerar la cuestión más general de mejorar los límites superiores en . Esta pregunta fue planteada por primera vez [4] por William Timothy Gowers en 2001. ${\ estilo de visualización L (N)}$ ${\ estilo de visualización \ {1, \ puntos, N \}^ {2))$ ${\ estilo de visualización L (N) = o (1)}$ ${\ estilo de visualización L (N)}$

En 2002, Wu Ha Wang demostró [5] que , donde es la inversa de la tetración en base 2 en el mismo sentido que el logaritmo natural es la inversa del exponente . ${\displaystyle L(N)\leq {\frac {100}{(\log _{*}(N))^{1/4))))$ ${\ estilo de visualización \ registro _ {*}}$

En 2005–2006, Ilya Shkredov mejoró esta estimación [6] , primero a y luego [7] a , donde y son algunas constantes absolutas. $L(N)=O\left({\frac {1}{(\log \log \log N)^{C_{1))))\right)$ $L(N)=O\left({\frac {1}{(\log \log N)^{C_{2))))\right)$ $C_{1}$ $C_{2}$

Conexión con el teorema de Roth

El teorema de la esquina puede considerarse un análogo bidimensional del teorema de Roth (un caso especial del teorema de Szemeredi para progresiones de longitud ), porque en la formulación del problema es la igualdad de los dos "lados" de una esquina rectangular que es importante, al igual que en la definición de una progresión aritmética , la igualdad de dos diferencias entre números vecinos es importante. $3$

Teorema de Roth (1953)

Para cualquiera existe tal que si el conjunto tiene una densidad , entonces contiene una progresión aritmética, es decir, un triple de números para algunos y . $\delta$ ${\ estilo de visualización N = N (\ delta)}$ $A\subconjunto \{{1,\dots,N}\}$ ${\frac {|A|}{N}}>\delta$ ${\displaystyle \{anuncio,a,a+d\))$ $a$ $d\not=0$

El teorema de Roth se puede deducir del teorema de la esquina como consecuencia directa.

Prueba

Para probar lo contrario, supongamos que el teorema de la esquina es cierto y el teorema de Roth no es cierto, es decir, existe cierta densidad tal que para cualquiera puede encontrar un subconjunto de tal densidad que no contenga una progresión aritmética, pero una densidad similar cubrir un cuadrado de tamaño arbitrario sin formación de esquinas no existe. Necesitamos, partiendo de esto, llegar a una contradicción. $\delta>0$ $norte$ $A\subconjunto \{1,\puntos,N\}$

Considere tal conjunto para uno arbitrario y construya a partir de él un subconjunto bidimensional del cuadrado de tamaño , que será un contraejemplo para el teorema de la esquina, es decir, tendrá una densidad conocida distinta de cero y no debe contener esquinas. . $norte$ $A\subconjunto \{1,\puntos,N\}$ ${\ estilo de visualización (| A |> \ delta N)}$ $2N$

Tal conjunto será un conjunto de la forma , es decir, una secuencia de líneas que representan desplazamientos sucesivos del conjunto . Si hubiera una esquina en tal conjunto, entonces esto significaría que el conjunto tenía una progresión aritmética de longitud , porque está construido de tal manera que, si , entonces y , y luego, además de la esquina, contiene un triple que asigna la progresión aritmética a una línea específica. $X=\{(a+(i-1),i):i\in {1,\dots,N},a\in A\}$ $A$ $A$ $3$ $X$ ${\ estilo de visualización (x, y + d) \ en X}$ ${\ estilo de visualización (xd, y) \ en X}$ ${\ estilo de visualización (xd, y), (x, y), (x + d, y)}$

Sin embargo, nuestra suposición inicial era que no existen tales progresiones. Así que no hay esquinas. Ahora considere la densidad al cuadrado . Como solo hay turnos y todos están incluidos en el conjunto por completo, la densidad es igual a . $A$ $X$ $X$ ${\ estilo de visualización \ {1, \ puntos, 2N\}^{2))$ $norte$ ${\frac {N|A|}{(2N)^{2}}}>{\frac {\delta N^{2}}{4N^{2}}}={\frac {\delta {cuatro}}$

Entonces, hemos aprendido cómo construir un conjunto de densidad que no contenga esquinas en un cuadrado de cualquier tamaño. Sin embargo, esto contradice nuestra suposición original de que el teorema de la esquina es cierto. ${\frac{\delta}{4}}$

Generalización para grupos

Además de las esquinas visualmente representables en la red , se pueden considerar "esquinas" generalizadas de la forma , donde y es algún grupo con la operación . ${\ estilo de visualización \ {1, \ puntos, N \}^ {2))$ ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\))$ ${\ estilo de visualización x, y, d \ en G}$ $GRAMO$ $\circ$

Por espacio ${\displaystyle {\mathbb {Z} }_{2}^{n))$

Ben Green en 2005 consideró [8] [9] [10] la cuestión de las esquinas en el grupo , es decir, no para el conjunto de números naturales. y para el conjunto de secuencias de bits (que consisten en ceros y unos) de longitud , para las cuales se usa bit a bit exclusivo o en lugar de suma . ${\displaystyle {\mathbb {Z} }_{2}^{n))$ $norte$

Teorema (Greene, 2005)

Para cualquier , existe tal que si el conjunto tiene una densidad , entonces contiene una esquina de la forma , donde , y la suma se hace módulo 2 . $\delta$ ${\ estilo de visualización n = n (\ delta)}$ ${\displaystyle A\subconjunto {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n))$ ${\frac{|A|}{2^{2n}}}\geq\delta$ ${\ estilo de visualización \ {(x, y), (x + d, y), (x, y + d) \))$ ${\displaystyle x,y,d\in {\mathbb {Z} }_{2}^{n))$

Esquema general de prueba para

{\displaystyle {\mathbb {Z} }_{2}^{n))

Indicadores de uniformidad

La prueba utiliza dos indicadores de la uniformidad de la distribución de conjuntos: uno para subconjuntos "unidimensionales" y otro para subconjuntos "bidimensionales" , donde ${\displaystyle E\subconjunto {\mathbb {Z} }_{2}^{n))$ $A\subconjunto E_{1}\times E_{2}$ ${\displaystyle E_{1},E_{2}\subconjunto {\mathbb {Z} }_{2}^{n))$

Como indicador de uniformidad para conjuntos unidimensionales, se usa una transformada de Fourier especialmente adaptada, donde las raíces de la unidad se usan como coeficientes , y se usa un análogo del producto escalar de la forma en lugar de la multiplicación . Si , entonces un valor pequeño en cierto sentido significa que el conjunto está cerca de algún conjunto distribuido aleatoriamente de la misma densidad, lo que significa que hay más subconjuntos estructurados en él que en muchos otros. Si para algunos , entonces se dice que el conjunto es -uniforme. ${\overline {x}}\cdot {\overline {y}}=\sum \limits _{i=1}^{n}{x_{i}y_{i}}{\pmod {2} }$ ${\widehat {E}}(\xi )=\sum \limits _{x\in E}{e^{-(x\cdot \xi )\pi i}}=\sum \limits_{ x\in E}{(-1)^{x\cdot \xi }}$ ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )))$ $mi$ $\max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}<2^{n}\alpha$ $\alfa$ $mi$ $\alfa$

Para un conjunto, tiene sentido considerar la función de equilibrio , donde es la densidad del conjunto, y la expresión entre corchetes significa el indicador de pertenencia al conjunto. Para la función de equilibrio se determina la denominada norma rectangular . Si el valor de esta norma es lo suficientemente pequeño en algún sentido, entonces esto también significa cercanía a un conjunto aleatorio. Si , entonces el conjunto se llama -uniforme con respecto a la norma rectangular. $A\subconjunto E_{1}\times E_{2}\subconjunto {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}$ ${f_{A}}(x,y)=[(x,y)\en A]-\rho [(x,y)\en E_{1}\times E_{2}]$ $\rho =\rho (A)={\frac {|A|}{|E_{1}||E_{2}|}}$ $\lVert {f_{A}}\rVert ^{4}=\sum \limits _{x_{1},y_{1},x_{2},y_{2}}{{f_{A} }(x_{1},y_{1}){f_{A}}(x_{1},y_{2}),{f_{A}}(x_{2},y_{1}),{f_ {A}}(x_{2},y_{2})}$ $A$ $\lVert {f_{A}}\rVert ^{4}<\alpha |E_{1}|^{2}|E_{2}|^{2}$ $A$ $\alfa$

Descripción del algoritmo

La demostración se hace por contradicción, es decir, se supone inicialmente que el conjunto tiene densidad y no contiene esquinas. La demostración es un algoritmo de transición secuencial de un conjunto a su subconjunto contenido en el producto de espacios de menor dimensión y mayor densidad allí. Además, se realiza la transición según el mismo esquema de este subconjunto a su propio subconjunto, y así sucesivamente, hasta encontrar una progresión aritmética en el siguiente subconjunto (que, obviamente, se pertenecerá a sí mismo ). Detener el algoritmo en algún punto está garantizado por el hecho de que la densidad del conjunto no puede exceder uno, y la transición del conjunto de densidad a su subconjunto de densidad (en un espacio más estrecho) , de modo que a través de la reducción del subconjunto, el algoritmo completa su trabajo. $A$ $\delta$ $A$ $A$ $\delta$ ${\ estilo de visualización \ delta +2^{-32}\delta ^{24}}$ ${\ estilo de visualización 2 ^ {32} \ delta ^ {-24}}$

El siguiente subconjunto se considera no solo como , donde es algún subespacio, sino también más estrictamente, como , donde los conjuntos son conjuntos arbitrarios, pero que tienen pequeños coeficientes de Fourier. Formalmente, podemos estar de acuerdo en que , , $A_{i}\subconjunto A$ ${\displaystyle A_{i}\subconjunto W_{i}\times W_{i))$ ${\displaystyle W_{i}\subconjunto {\mathbb {Z} }_{2}^{n))$ ${\displaystyle A_{i}\subconjunto E_{1}^{(i)}\veces E_{2}^{(i)))$ ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}\subconjunto W_{i))$ $A_{0}=A$ ${\displaystyle W_{0}={\mathbb {Z} }_{2}^{n))$ ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n))$

Además, consideraremos un paso separado del algoritmo y denotaremos las densidades de los conjuntos como y . Estas densidades también importan en la demostración. $mi$ $\beta _{1}={\frac {E_{1}^{(i)}}{|W|}}$ $\beta _{2}={\frac {E_{2}^{(i)}}{|W|}}$

En los tres casos considerados a continuación, -la uniformidad de los conjuntos se entiende con respecto al espacio actual $\alfa$ $mi$ $Wisconsin$

En cada etapa separada del algoritmo, son posibles tres casos:

Caso 1

Los conjuntos y son -uniformes para algunos . El conjunto es uniforme para algunos . ${\displaystyle E_{1}^{(i)))$ ${\displaystyle E_{2}^{(i)))$ $\alpha_{1}$ ${\ estilo de visualización \ alfa _ {1} = \ alfa _ {1} (\ delta, \ beta _ {1}, \ beta _ {2})}$ $Ai}$ $\alpha_2$ ${\ estilo de visualización \ alfa _ {2} = \ alfa _ {2} (\ delta)}$

En este caso, la presencia de esquinas se puede probar literalmente, sin profundizar en los subconjuntos. Además, se puede probar que el conjunto contiene al menos esquinas. Esta es la mejor estimación en orden de crecimiento, ya que el número de esquinas, obviamente, no puede exceder (después de todo, la esquina está determinada por tres números, ). $A$ ${\frac {\delta ^{3}\beta _{1}\beta _{2}}{2}}|W|^{3}$ ${\ estilo de visualización | W | ^ {3}}$ ${\ estilo de visualización x, y, d \ en W}$

Caso 2

El conjunto no es uniforme por lo mismo que en el caso anterior. $A$ $\alpha_2$ $\alpha_2$

Tooda, resulta que es posible elegir subconjuntos de tal manera que su tamaño no sea mucho más pequeño que los tamaños (disminuye en la mayoría de los casos, donde es un polinomio ), y la densidad del conjunto excede significativamente su densidad entre ( excede por donde es un polinomio) $F_{1}\subconjunto E_{1}$ $F_{1}\subconjunto E_{2}$ ${\ estilo de visualización E_{1},E_{2))$ $p({\frac{1}{\delta )))$ $pags$ $A$ ${\displaystyle F_{1}\veces F_{2))$ ${\displaystyle E_{1}\times E_{2))$ ${\ estilo de visualización q (\ delta)}$ $q$

Caso 3

Uno de los conjuntos no es uniforme (por lo mismo que en el primer caso). ${\displaystyle E_{1}^{(i)},E_{2}^{(i)))$ $\alpha_{1}$ $\alpha_{1}$

Tenga en cuenta que este caso no puede surgir en el primer paso, ya que , y el espacio con respecto a sí mismo, por supuesto, siempre es -uniforme. ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n))$ ${\ estilo de visualización 0}$

En este caso se utiliza el crecimiento del conjunto c del paso anterior, es decir, si el conjunto tiene una densidad entre , entonces la existencia de algún subespacio y algunos desplazamientos de los conjuntos , tal que al pasar a sus (desplazamientos) intersecciones con este subespacio, los nuevos conjuntos unidimensionales resultan ser -uniformes para preseleccionados arbitrariamente y la densidad del nuevo conjunto bidimensional resulta ser no menor que . $Ai}$ ${\ estilo de visualización \ delta _ {0} + \ tau}$ ${\displaystyle E_{1}^{(i)}\veces E_{2}^{(i)))$ ${\displaystyle W_{i+1}\subconjunto W_{i))$ $E_{1}^{(i)},E_{2}^{(i)},A$ $\sigma$ $\sigma$ $\delta _{0}+{\frac {\tau}{4}}$

Como aquí, puede elegir , y como el aumento en el conjunto proporcionado en el paso anterior del algoritmo. Por lo tanto, solo reducimos ligeramente (cuatro veces) la tasa de aumento en la densidad del conjunto durante el curso del algoritmo, pero en cada paso aseguramos la uniformidad de los conjuntos , y esto nos permite afirmar que los casos 1 y 2 agotar todos los casos posibles. $\sigma$ $\alpha_{1}$ $\tau$ $A$ $\alpha_{1}$ ${\displaystyle E_{1}^{(i)},E_{2}^{(i)))$

Para grupos abelianos arbitrarios

Ilya Shkredov en 2009 demostró ser una generalización para los grupos abelianos. [once]

Teorema

Hay una constante absoluta tal que si es un grupo abeliano , entonces se sigue de la presencia en la esquina $c>0$ $(G,\circ )$ $A\subconjunto G\veces G$ ${\displaystyle |A|\geq {\frac {|G|^{2}}{({\log \log {|G|}})^{c))))$ $A$ ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\))$

Notas

↑ M. Ajtai, E. Szemeredi: Conjuntos de puntos de celosía que no forman cuadrados, Studia Sci. Matemáticas. hungaro , 9 (1974), 9-11 (enlace no disponible)
↑ Prueba del teorema de las esquinas . Archivado el 30 de agosto de 2012 en Wayback Machine en polymath .
↑ J. Solymosi: Nota sobre una generalización del teorema de Roth, Algorithms Combin. , 25 , 2003, Springer, Berlín, 825-827
↑ Una nueva demostración del teorema de Szemeridi . Consultado el 5 de julio de 2017. Archivado desde el original el 23 de enero de 2018. (indefinido)
↑ Vu V. H, Sobre una cuestión de Gowers . Consultado el 5 de julio de 2017. Archivado desde el original el 9 de enero de 2018. (indefinido)
↑ I. D. Shkredov, Sobre un problema de Gowers . Consultado el 5 de julio de 2017. Archivado desde el original el 9 de enero de 2018. (indefinido)
↑ ID Shkredov, Sobre una generalización del teorema de Szemeredi (preimpresión) . Consultado el 5 de julio de 2017. Archivado desde el original el 9 de enero de 2018. (indefinido)
↑ Ben Green, "Modelos de campo finito en combinatoria aditiva" . Consultado el 5 de julio de 2017. Archivado desde el original el 13 de junio de 2017. (indefinido)
↑ Ben Green, "Modelos de campos finitos en combinatoria aritmética" (preimpresión) . Consultado el 5 de julio de 2017. Archivado desde el original el 9 de enero de 2018. (indefinido)
↑ I. D. Shkredov, Teorema de Szemeredy y problemas sobre progresiones aritméticas . Archivado el 24 de julio de 2018 en Wayback Machine , págs. 147-159 .
↑ I. D. Shkredov, Sobre un análogo bidimensional del teorema de Szemeredi en grupos abelianos . Consultado el 5 de julio de 2017. Archivado desde el original el 9 de enero de 2018. (indefinido)