Teorema de Van der Waerden

Teorema de la teoría de Ramsey

El teorema de Van der Waerden es un teorema de la rama de las matemáticas llamada teoría de Ramsey . El teorema de Van der Waerden establece que para cualquier número entero positivo r y k , existe algún número N tal que si los números enteros {1, 2, ..., N } están coloreados, cada uno con uno de r colores diferentes, entonces hay al menos k números enteros en progresión aritmética cuyos elementos sean del mismo color. El menor N es el número de Van der Waerden W ( r ,  k ), que lleva el nombre del matemático holandés BL van der Waerden . ^[1]

Esto fue conjeturado por Pierre Joseph Henry Baudet en 1921. Waerden se enteró en 1926 y publicó su prueba en 1927, titulada Beweis einer Baudetschen Vermutung [Prueba de la conjetura de Baudet] . ^{[2] [3] [4]}

Ejemplo

Por ejemplo, cuando r = 2, tienes dos colores, digamos rojo y azul . W (2, 3) es mayor que 8, porque puedes colorear los números enteros de {1, ..., 8} así:

y no hay tres números enteros del mismo color que formen una progresión aritmética . Pero no se puede sumar un noveno número entero al final sin crear dicha progresión. Si sumas un 9 rojo , entonces los 3 , 6 y 9 rojos están en progresión aritmética. Alternativamente, si agrega un 9 azul , entonces el 1 , 5 y 9 azules están en progresión aritmética.

De hecho, no hay forma de colorear del 1 al 9 sin crear dicha progresión (se puede demostrar considerando ejemplos). Por tanto, W (2, 3) es 9.

problema abierto

Es un problema abierto determinar los valores de W ( r , k ) para la mayoría de los valores de r y k . La demostración del teorema proporciona sólo un límite superior. Para el caso de r = 2 y k = 3, por ejemplo, el argumento dado a continuación muestra que es suficiente colorear los números enteros {1,..., 325} con dos colores para garantizar que habrá una aritmética de un solo color. progresión de longitud 3. Pero, de hecho, el límite de 325 es muy flojo; el número mínimo requerido de números enteros es solo 9. Cualquier coloración de los números enteros {1,..., 9} tendrá tres números enteros espaciados uniformemente de un color.

Para r = 3 y k = 3, la cota dada por el teorema es 7(2·3 ⁷  + 1)(2·3 ^{7·(2·3 7  + 1)}  + 1), o aproximadamente 4,22·10 ¹⁴⁶¹⁶ . Pero en realidad, no necesitas tantos números enteros para garantizar una progresión de un solo color de longitud 3; solo necesitas 27. (Y es posible colorear {1, ..., 26} con tres colores para que no haya una progresión aritmética de un solo color de longitud 3; por ejemplo:

Un problema abierto es el intento de reducir el límite superior general a cualquier función "razonable". Ronald Graham ofreció un premio de 1.000 dólares estadounidenses por mostrar W (2, k ) < 2 ^{k 2} . ^[5] Además, ofreció un premio de 250 dólares estadounidenses por una prueba de su conjetura que involucrara números de van der Waerden fuera de la diagonal más generales , afirmando W (2; 3, k ) ≤ k ^O(1) , mientras mencionaba evidencia numérica. sugiere W (2; 3, k ) = k ^{2 + o(1)} . Ben Green refutó esta última conjetura y demostró contraejemplos superpolinomiales para W (2; 3, k ) < k ^r para cualquier r . ^[6] El mejor límite superior conocido actualmente se debe a Timothy Gowers , ^[7] quien establece

${\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}},}$

estableciendo primero un resultado similar para el teorema de Szemerédi , que es una versión más sólida del teorema de Van der Waerden. El límite anteriormente más conocido se debió a Saharon Shelah y se realizó probando primero un resultado para el teorema de Hales-Jewett , que es otro fortalecimiento del teorema de Van der Waerden.

El mejor límite inferior conocido actualmente es que para todos los positivos tenemos , para todos lo suficientemente grande . ^[8] ${\displaystyle W(2,k)}$ ${\displaystyle \varepsilon }$ ${\displaystyle W(2,k)>2^{k}/k^{\varepsilon }}$ ${\displaystyle k}$

Prueba del teorema de Van der Waerden (en un caso especial)

La siguiente prueba se debe a Ron Graham , BL Rothschild y Joel Spencer . ^[9] Khinchin ^[10] ofrece una prueba bastante simple del teorema sin estimar W ( r ,  k ).

Prueba en el caso de W (2, 3)

Probaremos el caso especial mencionado anteriormente, que W (2, 3) ≤ 325. Sea c ( n ) una coloración de los números enteros {1, ..., 325}. Encontraremos tres elementos de {1,..., 325} en progresión aritmética que son del mismo color.

Divida {1, ..., 325} en los 65 bloques {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, así cada bloque es de la forma {5 b + 1, ..., 5 b + 5} para algún b en {0, ..., 64}. Dado que cada número entero está coloreado de rojo o azul , cada bloque se colorea de una de 32 maneras diferentes. Según el principio del casillero , hay dos bloques entre los primeros 33 bloques que tienen colores idénticos. Es decir, hay dos números enteros b ₁ y b ₂ , ambos en {0,...,32}, tales que

c (5 segundo ₁ + k ) = c (5 segundo ₂ + k )

para todo k en {1, ..., 5}. Entre los tres números enteros 5 b ₁ + 1, 5 b ₁ + 2, 5 b ₁ + 3, debe haber al menos dos que sean del mismo color. (El principio del casillero nuevamente.) Llame a estos 5 b ₁ + a ₁ y 5 b ₁ + a ₂ , donde a i _están en {1,2,3} y a ₁ < a ₂ . Supongamos (sin pérdida de generalidad) que estos dos números enteros son rojos . (Si ambos son azules , simplemente intercambie ' rojo ' y ' azul ' en lo que sigue).

Sea a ₃ = 2 a ₂  −  a ₁ . Si 5 b ₁ + a ₃ es rojo , entonces hemos encontrado nuestra progresión aritmética: 5 b ₁  +  a _i son todos rojos .

De lo contrario, 5 b ₁ + a ₃ es azul . Dado que a ₃ ≤ 5, 5 b ₁ + a ₃ está en el bloque b ₁ , y dado que el bloque b ₂ tiene el mismo color, 5 b ₂ + a ₃ también es azul .

Ahora sea b ₃ = 2 b ₂  −  b ₁ . Entonces b ₃ ≤ 64. Considere el número entero 5 b ₃ + a ₃ , que debe ser ≤ 325. ¿De qué color es?

Si es rojo , entonces 5 b ₁ + a ₁ , 5 b ₂ + a ₂ y 5 b ₃ + a ₃ forman una progresión aritmética roja . Pero si es azul , entonces 5 b ₁ + a ₃ , 5 b ₂ + a ₃ y 5 b ₃ + a ₃ forman una progresión aritmética azul . De cualquier manera, hemos terminado.

Prueba en el caso de W (3, 3)

Se puede presentar un argumento similar para demostrar que W (3, 3) ≤ 7(2·3 ⁷ +1)(2·3 ^{7·(2·3 7 +1)} +1). Se comienza dividiendo los números enteros en 2·3 ^{7·(2·3 7  + 1)}  + 1 grupos de 7(2·3 ⁷  + 1) enteros cada uno; de los primeros 3 ^{7·(2·3 7  + 1)}  + 1 grupos, dos deben tener el mismo color.

Divida cada uno de estos dos grupos en 2·3 ⁷ +1 subgrupos de 7 números enteros cada uno; de los primeros 3 ⁷  + 1 subgrupos de cada grupo, dos de los subgrupos deben tener el mismo color. Dentro de cada uno de estos subgrupos idénticos, dos de los primeros cuatro números enteros deben ser del mismo color, digamos rojo ; esto implica una progresión roja o un elemento de un color diferente, digamos azul , en el mismo subgrupo.

Como tenemos dos subgrupos de colores idénticos, hay un tercer subgrupo, todavía en el mismo grupo, que contiene un elemento que, si es rojo o azul , completaría una progresión roja o azul , mediante una construcción análoga a la de W ( 2, 3). Supongamos que este elemento es verde . Dado que hay un grupo que tiene colores idénticos, debe contener copias de los elementos rojo , azul y verde que hemos identificado; ahora podemos encontrar un par de elementos rojos , un par de elementos azules y un par de elementos verdes que se 'centran' en un mismo número entero, de modo que sea del color que sea, debe completar una progresión.

Prueba en caso general.

La prueba de W (2, 3) depende esencialmente de demostrar que W (32, 2) ≤ 33. Dividimos los números enteros {1,...,325} en 65 'bloques', cada uno de los cuales puede colorearse en 32 de diferentes maneras, y luego muestra que dos bloques de los primeros 33 deben ser del mismo color, y hay un bloque de color opuesto. De manera similar, la prueba para W (3, 3) depende de demostrar que

${\displaystyle W(3^{7(2\cdot 3^{7}+1)},2)\leq 3^{7(2\cdot 3^{7}+1)}+1.}$

Mediante una doble inducción sobre el número de colores y la longitud de la progresión, se demuestra el teorema en general.

Prueba

Una progresión aritmética (AP) D-dimensional consta de números de la forma:

${\displaystyle a+i_{1}s_{1}+i_{2}s_{2}+\cdots +i_{D}s_{D}}$

donde a es el punto base, las s son tamaños de paso positivos y las i van de 0 a L  − 1 . Un AP d -dimensional es homogéneo para algunos colores cuando todos son del mismo color.

Una progresión aritmética de dimensión D con beneficios son todos los números de la forma anterior, pero donde se agrega algo del "límite" de la progresión aritmética, es decir, algunos de los índices i pueden ser iguales a L. Los lados que viras son aquellos en los que las primeras k i son iguales a L y las i restantes son menores que L .

Los límites de un AP de dimensión D con beneficios son estas progresiones aritméticas adicionales de dimensión , hasta 0. La progresión aritmética de dimensión 0 es el único punto en el valor del índice . Un AP D -dimensional con beneficios es homogéneo cuando cada uno de los límites es individualmente homogéneo, pero diferentes límites no tienen por qué tener necesariamente el mismo color. ${\displaystyle d-1,d-2,d-3,d-4}$ ${\displaystyle (L,L,L,L,\ldots ,L)}$

A continuación, defina la cantidad MinN( L , D , N ) como el mínimo entero, de modo que cualquier asignación de N colores a un intervalo de longitud MinN o más contenga necesariamente una progresión aritmética homogénea de D dimensiones con beneficios.

El objetivo es limitar el tamaño de MinN . Tenga en cuenta que MinN( L ,1, N ) es un límite superior para el número de Van der Waerden. Hay dos pasos de inducción, como sigue:

Lema 1  :  Supongamos que MinN se conoce para longitudes determinadas L para todas las dimensiones de progresiones aritméticas con beneficios hasta D. Esta fórmula da un límite a MinN cuando aumenta la dimensión a D  + 1 :

deja , entonces ${\displaystyle M=\operatorname {MinN} (L,D,n)}$

${\displaystyle \operatorname {MinN} (L,D+1,n)\leq M\cdot \operatorname {MinN} (L,1,n^{M})}$

Prueba

Primero, si tiene una coloración n del intervalo 1... I , puede definir una coloración de bloque de bloques de tamaño k . Simplemente considere cada secuencia de k colores en cada k bloque para definir un color único. Llame a esto k -bloqueo una n -coloración. k -bloquear una n coloración de longitud l produce una n ^k coloración de longitud l/ k .

Entonces, dada una coloración n de un intervalo I de tamaño, puede bloquearlo M en una coloración n ^M de longitud . Pero eso significa, según la definición de MinN , que puedes encontrar una secuencia aritmética unidimensional (con beneficios) de longitud L en el color del bloque, que es una secuencia de bloques igualmente espaciados, que son todos del mismo color de bloque. es decir, tienes un montón de bloques de longitud M en la secuencia original, que están igualmente espaciados y que tienen exactamente la misma secuencia de colores en su interior. ${\displaystyle M\cdot \operatorname {MinN} (L,1,n^{M}))}$ ${\displaystyle \operatorname {MinN} (L,1,n^{M})}$

Ahora, según la definición de M , puedes encontrar una secuencia aritmética d- dimensional con beneficios en cualquiera de estos bloques, y dado que todos los bloques tienen la misma secuencia de colores, el mismo AP d -dimensional con beneficios aparece en todos de los bloques, simplemente traduciéndolo de bloque en bloque. Esta es la definición de una progresión aritmética d  + 1 dimensión, por lo que tienes un AP homogéneo d  + 1 dimensión. El nuevo parámetro de zancada s _{D  + 1} se define como la distancia entre los bloques.

Pero necesitas beneficios. Los límites que obtienes ahora son todos límites antiguos, además de sus traducciones a bloques del mismo color, porque i _D+1 siempre es menor que L . El único límite que no es así es el punto de dimensión 0 cuando . Se trata de un único punto y es automáticamente homogéneo. ${\displaystyle i_{1}=i_{2}=\cdots =i_{D+1}=L}$

Lema 2  :  Supongamos que MinN se conoce para un valor de L y todas las dimensiones posibles D. Luego puedes vincular MinN para la longitud L  + 1 .

${\displaystyle \operatorname {MinN} (L+1,1,n)\leq 2\operatorname {MinN} (L,n,n)}$

Prueba

Dada una n -coloración de un intervalo de tamaño MinN( L , n , n ) , por definición, puede encontrar una secuencia aritmética con beneficios de dimensión n de longitud L . Pero ahora, el número de límites de "beneficio" es igual al número de colores, por lo que uno de los límites homogéneos, digamos de dimensión k , tiene que tener el mismo color que otro de los límites de beneficio homogéneos, digamos el de dimensión pag  <  k . Esto permite construir una secuencia aritmética de longitud L  + 1 (de dimensión 1), yendo a lo largo de una línea dentro del límite k -dimensional que termina justo en el límite p -dimensional, e incluyendo el punto terminal en el límite p -dimensional . En fórmulas:

si

${\displaystyle a+Ls_{1}+Ls_{2}+\cdots +Ls_{D-k}}$tiene el mismo color que

${\displaystyle a+Ls_{1}+Ls_{2}+\cdots +Ls_{D-p}}$

entonces

${\displaystyle a+L\cdot (s_{1}+\cdots +s_{D-k})+u\cdot (s_{D-k+1}+\cdots +s_{p})}$tener el mismo color

${\displaystyle u=0,1,2,\cdots ,L-1,L}$es decir, u forma una secuencia de longitud L +1.

Esto construye una secuencia de dimensión 1, y los "beneficios" son automáticos, simplemente agregue otro punto de cualquier color. Para incluir este punto límite, hay que alargar el intervalo en el valor máximo posible de la zancada, que ciertamente es menor que el tamaño del intervalo. Por lo tanto, duplicar el tamaño del intervalo definitivamente funcionará, y esta es la razón del factor dos. Esto completa la inducción en L.

Caso base: MinN(1, d , n ) = 1 , es decir, si desea una secuencia aritmética d -dimensional homogénea de longitud 1, con o sin beneficios, no tiene nada que hacer. Entonces esto forma la base de la inducción. El teorema de Van der Waerden en sí es la afirmación de que MinN( L ,1, N ) es finito, y se deduce del caso base y de los pasos de inducción. ^[11]

Teoría ergódica

Furstenberg y Weiss demostraron una forma equivalente del teorema en 1978, utilizando la teoría ergódica. ^[12]

Teorema de recurrencia múltiple de Birkhoff  (Furstenberg y Weiss, 1978)  :  si es un espacio métrico compacto y hay homeomorfismos que conmutan, entonces y una secuencia creciente , tal que ${\textstyle X}$ ${\textstyle T_{1},\dots ,T_{N}:X\to X}$ ${\textstyle \exists x\in X}$ ${\textstyle n_{1}<n_{2}<\cdots }$

$${\displaystyle \lim _{j}d(T_{i}^{n_{j}}x,x)=0,\quad \forall i\in 1:N}$$

La demostración del teorema anterior es delicada y se remite al lector a ella. ^[12] Con este teorema de recurrencia, el teorema de van der Waerden se puede demostrar en el estilo teórico ergódico.

Teorema  (van der Waerden, 1927)  :  si se divide en un número finito de subconjuntos , entonces uno de ellos contiene infinitas progresiones aritméticas de longitud arbitrariamente larga. ${\textstyle \mathbb {Z} }$ ${\textstyle S_{1},\dots ,S_{n}}$ ${\textstyle S_{k}}$

$${\displaystyle \forall N,N',\;\exists |a|\geq N',\exists r\geq 1:\{a+ir\}_{i\in 1:N}\subset S_{k}}$$

Prueba

Basta demostrar que para cada longitud existe al menos una partición que contiene al menos una progresión aritmética de longitud . ${\textstyle N}$ ${\textstyle N}$

Una vez probado esto, podemos cortar esa progresión aritmética en conjuntos únicos y repetir el proceso para crear otra progresión aritmética, de modo que una de las particiones contenga infinitas progresiones aritméticas de longitud . ${\textstyle N}$ ${\textstyle N}$

Una vez probado esto, podemos repetir este proceso para encontrar que existe al menos una partición que contiene infinitas progresiones de longitud , para infinitas , y esa es la partición que queremos. ${\textstyle N}$ ${\textstyle N}$

Considere el espacio de estados , con métrica compacta ${\textstyle \Omega :=(1:N)^{\mathbb {Z} }}$

$${\displaystyle d((x_{n}),(y_{n}))=\max\{2^{-|n|}:x_{n}\neq y_{n}\}}$$

En otras palabras, sea el índice más cercano a donde difieren, y luego su distancia es . (De hecho, este es un ultramétrico). ${\textstyle n}$ ${\textstyle 0}$ ${\textstyle x,y}$ ${\textstyle 1/2^{|n|}}$

Dado que cada número entero cae exactamente en una de las particiones , podemos codificar la partición en una secuencia . Cada uno es el nombre de la partición en la que se encuentra. En otras palabras, podemos dibujar los conjuntos horizontalmente y conectar los puntos en la secuencia . ${\textstyle S_{1},\dots ,S_{n}}$ ${\textstyle (z_{n})_{n}}$ ${\textstyle z_{n}}$ ${\textstyle n}$ ${\textstyle S_{1},\dots ,S_{n}}$ ${\textstyle (z_{n})_{n}}$

Sea el mapa el mapa de desplazamiento: ${\textstyle T:\Omega \to \Omega }$

$${\displaystyle T((x_{n})_{n})=(x_{n+1})_{n}}$$

y luego, sea el cierre de todos los turnos de la secuencia : ${\textstyle (z_{n})_{n}}$ ${\textstyle X}$

$${\displaystyle X:=cl(\{T^{n}z:n\in \mathbb {Z} \})}$$

Según el teorema de recurrencia múltiple de Birkhoff, existe alguna secuencia y un número entero tal que ${\textstyle x\in X}$ ${\textstyle n\geq 1}$

$${\displaystyle d(T^{n}x,x)<1/4,\quad d(T^{2n}x,x)<1/4,\quad \cdots ,\quad d(T^{Nn}x,x)<1/4}$$

Dado que es el cierre de desplazamientos de y es continuo, existe un desplazamiento tal que simultáneamente está muy cerca de y está muy cerca de y así sucesivamente: ${\textstyle X}$ ${\textstyle z}$ ${\textstyle T}$ ${\textstyle T^{m}z}$ ${\textstyle x}$ ${\textstyle T^{m}z}$ ${\textstyle T^{n}x}$ ${\textstyle T^{n+m}z}$

$${\displaystyle d(x,T^{m}z)<1/4,\quad d(T^{n}x,T^{m+n}z)<1/4,\quad \cdots ,\quad d(T^{Nn}x,T^{m+Nn}z)<1/4}$$

Por la desigualdad del triángulo, todos los pares del conjunto están cerca uno del otro: ${\textstyle \{T^{m}z,T^{m+n}z,\dots ,T^{m+Nn}z\}}$

$${\displaystyle d(T^{m+in}z,T^{m+jn}z)<3/4\quad \forall i,j\in 0:N}$$

lo que implica , es decir, que la secuencia aritmética está en la partición . ${\textstyle z_{m}=z_{m+n}=\dots =z_{m+Nn}}$ ${\textstyle m,m+n,\dots ,m+Nn}$ ${\textstyle S_{z_{m}}}$

Ver también

• Números de Van der Waerden para todos los valores conocidos de W ( n , r ) y los límites más conocidos para valores desconocidos.
• Juego de Van der Waerden : un juego en el que el jugador elige números enteros del conjunto 1, 2, ..., N e intenta recopilar una progresión aritmética de longitud n .
• Teorema de Hales-Jewett
• teorema de rado
• Teorema de Szemerédi
• Bartel Leendert van der Waerden

Notas

1. van der Waerden, BL (1927). "Beweis einer Baudetschen Vermutung". Nuevo. Arco. Wisk. (en alemán). 15 : 212–216.
2. L, van der WAERDEN B. (1927). "Beweis einer Baudetschen Vermutung". Nieuw Arch. Wiskunde . 15 : 212–216.
3. Soifer, Alexander (2015), Soifer, Alexander (ed.), "¿De quién fue la conjetura que demostró Van der Waerden?", El erudito y el Estado: en busca de Van der Waerden , Basilea: Springer, págs. doi :10.1007/978-3-0348-0712-8_38, ISBN 978-3-0348-0712-8, recuperado el 17 de enero de 2024
4. L, van der WAERDEN B. (1971). "Cómo se encontró la prueba de la conjetura de Baudet". Estudios en Matemática Pura . Reimpreso en el capítulo 33 de "El libro para colorear de matemáticas".
5. Graham, Ron (2007). "Algunos de mis problemas favoritos en la teoría de Ramsey". ENTEROS: Revista electrónica de teoría combinatoria de números . 7 (2): #A15.
6. Klarreich, Erica (2021). "Matemático arroja estructura y desorden a un problema centenario". Revista Quanta .
7. Gowers, Timoteo (2001). "Una nueva prueba del teorema de Szemerédi". Análisis Geométrico y Funcional . 11 (3): 465–588. doi :10.1007/s00039-001-0332-9. S2CID  124324198.
8. Szabó, Zoltán (1990). "Una aplicación del lema local de Lovász: un nuevo límite inferior para el número de van der Waerden". Algoritmos y estructuras aleatorias . 1 (3): 343–360. doi :10.1002/rsa.3240010307.
9. Graham, Ronald; Rothschild, Bruce; Spencer, Joel (1990). Teoría de Ramsey . Wiley . ISBN 0471500461.
10. Khinchin (1998, págs. 11-17, capítulo 1)
11. Graham, RL ; Rothschild, BL (1974). "Una breve prueba del teorema de van der Waerden sobre progresiones aritméticas". Actas de la Sociedad Matemática Estadounidense . 42 (2): 385–386. doi : 10.1090/S0002-9939-1974-0329917-8 .
12. Petersen, Karl E. (1983). "Capitulo 2.". Teoría ergódica. Estudios de Cambridge en Matemáticas Avanzadas. Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-0-521-38997-6.

Referencias

• Khinchin, A. Ya. (1998), Tres perlas de la teoría de números, Mineola, Nueva York: Dover, págs. 11-17, ISBN 978-0-486-40026-6(segunda edición publicada originalmente en ruso en 1948)

enlaces externos

• O'Bryant, Kevin. "Teorema de van der Waerden". MundoMatemático .
• O'Bryant, Kevin y Weisstein, Eric W. "Número de Van der Waerden". MundoMatemático .