El teorema de Van der Waerden es un resultado clásico de la teoría combinatoria de números sobre progresiones aritméticas monocromáticas en la coloración de números naturales . El teorema es un enunciado típico de la teoría de Ramsey , así como un precursor del teorema de Szemeredi , que marcó el comienzo de una gran rama de la combinatoria aditiva .
Notación A lo largo del artículo, la notación se utiliza para denotar un conjunto . Esta designación es bastante común en la literatura. |
El teorema tiene dos formulaciones equivalentes : finito e infinito [1] .
Redacción sin fin Para cualquier función y , existen tales que |
Una función generalmente se llama coloración de números naturales, sus valores son colores de números y una progresión es de un color (el teorema no especifica qué color tienen sus elementos).
La formulación finita es similar a la infinita, pero considera una coloración de un conjunto finito. Pertenece a O. Schreier [2] .
Redacción definitiva Para cualquier existe un número tal que para cualquier función existe tal que |
Los números de la formulación final se llaman números de van der Waerden . Para ellos, se estudian los límites inferior y superior.
La demostración del teorema fue publicada por B. L. van der Waerden en 1927.
Alexander Sofier en su ensayo histórico sobre la teoría de Ramsey escribe que Schur consideró el enunciado del teorema como una hipótesis cuando trabajaba en su teorema sobre la coloración de números (en 1916), pero la hipótesis no llegó a van der Waerden de Schur, pero fue inventado de forma independiente por Bode y van der Waerden aprendió la hipótesis de sus alumnos (Baudet ya había muerto en ese momento). La prueba fue inventada en la Universidad de Hamburgo y presentada al público en Berlín en el congreso de la Sociedad Matemática Alemana [3] .
Van der Waerden simplemente no se dio cuenta de cuán importante era el resultado que había probado: envió sus artículos sobre geometría algebraica a la revista más prestigiosa, Mathematische Annalen , y envió esta prueba a la revista "ininteligible" Nieuw Archief voor Wiskunde de la Sociedad Matemática Holandesa . .
Texto original (inglés)[ mostrarocultar] Van der Waerden simplemente no se dio cuenta de lo importante que era el resultado que demostró: envió sus artículos de geometría algebraica a la revista más prestigiosa, Mathematische Annalen , pero envió esta prueba a una revista "oscura", Nieuw Archief voor Wiskunde de la Sociedad Matemática Holandesa . .A su vez, Alexander Khinchin escribió que el resultado se obtuvo en Göttingen en el verano de 1928 pocos días antes de su llegada allí y que “un matemático local […] se encontró con la hipótesis en el curso de su trabajo científico” [4] .
La ambigüedad del origen de la hipótesis original es enfatizada por Ronald Graham en su libro sobre la teoría de Ramsey [5] , sin embargo, todas las fuentes coinciden en que en la formulación del problema que resolvió van der Waerden, había solo dos colores, y Se agregó el fortalecimiento de la afirmación a un número arbitrario de colores como herramienta de prueba.
En esta sección, la afirmación de que el teorema es verdadero para colores y longitudes de progresión se denota como .
El teorema se demuestra por inducción sobre . La base es obvia [7] . Al probar un paso de inducción, se suele decir por conveniencia que se supone que se prueba para todos , aunque formalmente, para probar cada enunciado individual , se utilizan un número finito de enunciados de la forma , pero con valores muy grandes de . suficiente
Para garantizar la presencia de una progresión de longitud de un color , se debe pasar de considerar un intervalo, cuya longitud garantiza la presencia de una progresión de longitud de un color , a intervalos cada vez más grandes, que garanticen la presencia de más y estructuras más complejas - los llamados abanicos . Para colorear, llamamos -fan a una familia de progresiones de longitud tal que:
Los ventiladores se pueden usar para probar el paso de inducción debido a dos propiedades obvias:
Por lo tanto, basta probar un paso de inducción sobre un parámetro para la declaración "cualquier coloración de un intervalo suficientemente grande contiene un abanico o una progresión de longitud ". Para esto debes:
Esto garantizará la presencia de varios abanicos idénticos espaciados a la misma distancia entre sí (una especie de progresión de abanicos). Si el color del elemento central del abanico difiere de los colores de sus progresiones [8] , entonces en tal construcción es posible seleccionar un abanico en diagonal (ver la imagen).
Durante la transición diagonal de la progresión de -fans a -fan, se pierde una gran cantidad de conexiones aritméticas y de color, en las que participan elementos que no están incluidos en el -fan. Si rastreamos estos elementos y su duplicación en progresiones subsiguientes desde -fans, -fans, etc., entonces se verá que las progresiones de un color que emanan de cualquier -fan son en realidad diagonales de progresiones multidimensionales de un color de dimensión desde a , dependiendo del "momento" de aparición del color durante la inducción. Por lo tanto, algunos autores presentan la prueba en términos de encontrar la combinación apropiada de progresiones multidimensionales [9] .
Para el teorema de van der Waerden, se han estudiado muchas generalizaciones para varios aspectos de la formulación del enunciado. Se pueden combinar diferentes tipos de generalizaciones en una declaración.
En esta sección, solo se dan formulaciones interminables de declaraciones generalizadas, aunque para la mayoría de ellas hay análogos finitos construidos de acuerdo con el mismo principio que para el teorema principal.
La condición de que los números formen una progresión aritmética significa el cumplimiento de las igualdades
Una forma de generalizar es sustituir estas condiciones por otras que también sean lineales.
Pregunta ¿ Para qué sistemas de ecuaciones lineales (incluidas las ecuaciones individuales) sigue siendo cierto el enunciado del teorema de van der Waerden cuando la condición de que los elementos de la configuración requerida forman una progresión se reemplaza por el hecho de que satisfacen el sistema dado? |
Además, los elementos de progresión se pueden representar como . Si percibimos las diferencias como funciones fijas de , entonces esto lleva a una generalización polinomial.
Versión polinomial Sean polinomios con coeficientes enteros tales que . Entonces para cualquiera y hay colorantes tales que |
Los abanicos también se pueden usar para probar la versión polinómica, pero con las correspondientes diferencias polinómicas. Por ejemplo, al probar la presencia de un par monocromático en una coloración arbitraria, un paso intermedio es probar la existencia de números tales que tengan colores diferentes y sean cuadrados [11] .
Por dimensiónAl generalizar el teorema a espacios multidimensionales, en lugar de progresiones, se consideran imágenes homotéticas de un conjunto finito de puntos (una progresión aritmética corresponde a una imagen homotética de un hipercubo discreto ).
Versión multidimensional [12] Para cualquier número natural , hay conjuntos y colorantes tales que |
El teorema de Hales-Jewett ofrece una generalización más amplia, puramente combinatoria y multidimensional. Por comodidad, puede entenderse como un teorema de coloración , pero en él no se utilizan en absoluto operaciones con números, es decir, el conjunto puede sustituirse por cualquier otro del mismo tamaño. Aquí, la dimensión del espacio actúa como un parámetro variable (“suficientemente grande”) , por lo que el teorema de Hales-Jewett tiene solo una formulación finita.
Definición A un conjunto de líneas combinatorias en la diagonal de cualquier subcubo no trivial se le llama, es decir, al conjunto de todos los vectores, donde algunas de las coordenadas pueden ser fijas, y el resto (número distinto de cero) son siempre iguales y corren a través de todos los valores . Teorema de Hales-Jewett [13] Para any existe un número tal que para any en cualquier color existe una línea combinatoria monocromática. |
La demostración del teorema de Hales-Jewett se basa en la misma inducción mediante ventiladores. Para un vector , se considera una partición de coordenadas . En una hipercoloración , donde el hipercolor del vector es una combinación de colores de todos los puntos de la forma , para un tamaño suficientemente grande es posible, por la suposición inductiva (c ), encontrar una línea combinatoria, donde todos los elementos excepto uno serán del mismo color. Para colorear , esto significará la presencia de tal "línea" de subespacios de dimensión de colores idénticos . Y para los grandes, se garantiza la presencia de una línea recta similar en cada uno de estos subespacios. Resulta "una línea recta de líneas rectas", cada una de las cuales tiene la misma continuación. Esta construcción es similar a la construcción de progresiones generalizadas a partir de la demostración del teorema de van der Waerden y puede usarse para construir ventiladores de la misma forma que [14] .
El teorema de van der Waerden se deriva del teorema de Hales-Jewett, ya que la transformación de a , correspondiente a la interpretación de las coordenadas como dígitos en el sistema numérico -ario , mapea líneas combinatorias en progresión aritmética [15] . El teorema multidimensional de van der Waerden se puede derivar de manera similar fijando cualquier numeración de elementos y considerando el teorema de Hales-Jewett para [16] .
El teorema multidimensional también se puede demostrar directamente, sin el teorema de Hales-Jewett. De hecho, si se demuestra para un subconjunto que contiene puntos afines independientes , entonces podemos aplicar la inducción de a con la ayuda de abanicos de los teoremas de van der Waerden, pero con una partición en bloques multidimensionales. Por lo tanto, basta con presentar una forma de pasar de un enunciado para a un enunciado para un conjunto de puntos independientes afines. Como ejemplo de esto , puedes tomar una esquina, es decir, puntos de la forma
La presencia de una esquina bidimensional en el hiperplano con la condición (que se garantiza para suficientemente grande ) significa la presencia de una esquina en la que todos los puntos, excepto el central, son del mismo color. Además, dividiendo los números en bloques multidimensionales y aplicándoles el mismo procedimiento, uno puede construir ventiladores arbitrariamente grandes a partir de esos rincones.
Un color (subconjuntos densos)
A partir de consideraciones empíricas, es natural suponer que la configuración deseada de números de un solo color en la mayoría de los casos tendrá el color más popular, porque cuantos más números de un color u otro, más configuraciones interesantes pueden surgir entre ellos.
Aunque plausible, esta afirmación no se deriva directamente del teorema de van der Waerden y es mucho más difícil de probar. Para formalizarlo, cabe señalar que en la coloración final el color más popular tiene una densidad superior positiva [17] . Por lo tanto, la suposición enunciada significa la presencia de una progresión en cualquier conjunto denso. Este teorema lleva el nombre de Endre Szemeredy , quien lo demostró por primera vez.
Teorema de Szemeredi Para cualquiera y un conjunto tal que , existen tales que . |
Por analogía con los números de van der Waerden, para la versión finita del teorema de Szémerédy, estudiamos cotas inferior y superior para , suficientes para el conjunto con la condición de contener siempre una progresión de longitud . Obtener dichas estimaciones en el caso es mucho más difícil que en el caso de .
Ideas de pruebaLos métodos para probar el teorema de Szemeredi son notablemente diferentes del teorema de van der Waerden tanto en tipo como en complejidad. Se conocen demostraciones combinatorias (usando el lema de regularidad de Szemeredi de la teoría general de grafos ), analíticas (usando los coeficientes de Fourier y las normas de Gowers generalizándolos ) y ergódicas.
Para probar las generalizaciones más amplias (con la adición de diferencias polinómicas y multidimensionalidad del espacio), los métodos de la teoría ergódica funcionan bien, pero no brindan estimaciones cuantitativas para las formulaciones finales [18] .
A una infinidad de coloresCon un número contable de colores, es decir, coloración , puede que no haya progresiones largas de un solo color [19] . Pero si consideramos configuraciones donde los colores de todos los elementos son diferentes como otro polo, también admisible, de estructura de color, entonces el teorema sigue siendo cierto.
Esta declaración se llama la versión canónica del teorema de van der Waerden.
versión canónica Para cualquier coloración y hay números tales que:
|
Erdős y Graham fueron los primeros en notar que la versión canónica se deriva del teorema de Szemeredi [20] . Posteriormente, esta idea se generalizó al caso multidimensional [21] . Sin embargo, el teorema de Szémeredy en sí mismo es difícil de probar, por lo que más tarde se encontró otra prueba elemental de la versión canónica a través de una versión multidimensional del teorema habitual de van der Waerden [22] .
Según la coloración , se puede construir una coloración del plano , donde el color del par está asociado a la progresión , es decir, corresponde a la división de la progresión por la igualdad de colores. Por ejemplo, los pares para los que las progresiones correspondientes están coloreadas (rojo, rojo, verde) y (azul, azul, amarillo) tendrán el mismo color en . Es importante que el número de colores sea finito .
Si no hay progresiones multicolores de longitud , entonces cualquier progresión tiene al menos dos elementos del mismo color. Por el teorema multidimensional de van der Waerden, hay una imagen homotética de un solo color en la coloración . Las progresiones correspondientes a los puntos de esta imagen se cortarán de tal manera que, al combinar estas igualdades, es posible mostrar la monocromaticidad de elementos de diferentes progresiones, y serán tantos que estos elementos forman su propia progresión. de longitud , completamente monocromática, que es requerida por la condición.
Condiciones aritméticas
a la estructura deseada |
Área de búsqueda | Espacio | ||
---|---|---|---|---|
unidimensional | Multidimensional | para la final | ||
Progresiones aritméticas | coloración definitiva | Teorema de Van der Waerden | ingenio, 1952 | Teorema de Hales-Jewett |
Colorear sin fin | Promel, Rodl, 1986 | El teorema tiene
única redacción final | ||
subconjunto denso | Teorema de Szemeredi
(incluido el teorema de Roth ) |
teorema de la esquina | conocido fuerte | |
Soluciones de ecuaciones lineales
o sistemas de ecuaciones |
coloración definitiva | Teorema de Rado | ||
Colorear sin fin | Lefman, 1986 | El teorema tiene
única redacción final | ||
subconjunto denso | algunos son conocidos | |||
significado de polinomios
en diferencias |
coloración definitiva | Walters, 2000 | ||
Colorear sin fin | Girao, 2020 | El teorema tiene
única redacción final | ||
subconjunto denso | Bergelson, Leibman, 1996 | |||
Demostrado por métodos separados
Teorema de Furstenberg-Sharkozy [25] y el teorema cuadrático de Roth [26] |