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 un 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 son del mismo color. El menor de tales N es el número de Van der Waerden W ( r ,  k ), llamado así por el 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} de esta manera:

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

De hecho, no hay forma de colorear los números del 1 al 9 sin crear una progresión de este tipo (se puede demostrar considerando ejemplos). Por lo tanto, W (2, 3) es 9.

Problema abierto

Determinar los valores de W ( r , k ) para la mayoría de los valores de r y k es un problema abierto . La prueba del teorema proporciona solo 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 progresión aritmética de un solo color de longitud 3. Pero, de hecho, el límite de 325 es muy flexible; 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 de un color espaciados uniformemente.

Para r = 3 y k = 3, el límite dado 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 de modo 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 1000 dólares estadounidenses por demostrar que 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 que W (2; 3, k ) ≤ k ^O(1) , mientras que mencionó evidencia numérica que sugiere que W (2; 3, k ) = k ^{2 + o(1)} . Ben Green refutó esta última conjetura y demostró contraejemplos superpolinómicos de 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 fuerte del teorema de Van der Waerden. El límite más conocido anteriormente se debía a Saharon Shelah y procedía mediante la demostración primero de 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 para es que para todos los positivos tenemos , para todos los suficientemente grandes . ^[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] da una prueba bastante simple del teorema sin estimar W ( r ,  k ).

Prueba en el caso deYo(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 sean del mismo color.

Divida {1, ..., 325} en los 65 bloques {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, por lo que cada bloque tiene la forma {5 b + 1, ..., 5 b + 5} para algún b en {0, ..., 64}. Como cada entero está coloreado de rojo o azul , cada bloque está coloreado de una de 32 formas diferentes. Por el principio del palomar , hay dos bloques entre los primeros 33 bloques que están coloreados de manera idéntica. Es decir, hay dos enteros b ₁ y b ₂ , ambos en {0, ..., 32}, tales que

c ( 5b1 + k ) = c ( _5b2 + k )_​

para todo k en {1, ..., 5}. Entre los tres enteros 5 b ₁ + 1, 5 b ₁ + 2, 5 b ₁ + 3, debe haber al menos dos que sean del mismo color. (El principio del palomar de nuevo.) Llamemos a estos 5 b ₁ + a ₁ y 5 b ₁ + a ₂ , donde los a _i están en {1,2,3} y a ₁ < a ₂ . Supongamos (sin pérdida de generalidad) que estos dos enteros son ambos rojos . (Si ambos son azules , simplemente intercambiemos ' 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 . Como a ₃ ≤ 5, 5 b ₁ + a ₃ está en el bloque b ₁ y, como 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 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 deYo(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) números 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 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 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.

Puesto que tenemos dos subgrupos de colores idénticos, hay un tercer subgrupo, todavía en el mismo grupo que contiene un elemento que, si fuera 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 . Puesto 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 "concentren" en el mismo entero, de modo que, sea cual sea su color, 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 de 32 maneras diferentes, y luego demostramos que dos bloques de los primeros 33 deben ser del mismo color, y hay un bloque coloreado de manera opuesta. De manera similar, la prueba de 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.}$

Por una doble inducción sobre el número de colores y la longitud de la progresión, el teorema queda demostrado en general.

Prueba

Una progresión aritmética (PA) de dimensión D 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 varían de 0 a L  − 1. Un AP d -dimensional es homogéneo para alguna coloración cuando todo es 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 agregan algunos de los "límites" de la progresión aritmética, es decir, algunos de los índices i pueden ser iguales a L. Los lados que se agregan son aquellos donde los primeros k i son iguales a L y los i restantes son menores que L.

Los límites de un AP D -dimensional con beneficios son estas progresiones aritméticas adicionales de dimensión , hasta 0. La progresión aritmética de dimensión 0 es el punto único en el valor de índice . Un AP D -dimensional con beneficios es homogéneo cuando cada uno de los límites es individualmente homogéneo, pero los diferentes límites no necesariamente tienen que tener 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 menor entero de modo que cualquier asignación de N colores a un intervalo de longitud MinN o más necesariamente contenga una progresión aritmética homogénea de dimensión D con beneficios.

El objetivo es limitar el tamaño de MinN . Nótese 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 se indica a continuación:

Lema 1  :  Supongamos que MinN es conocido para longitudes dadas L para todas las dimensiones de progresiones aritméticas con beneficios hasta D. Esta fórmula proporciona un límite para MinN cuando se 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

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

Entonces, dada una coloración n de un intervalo I de tamaño, puedes convertirlo en M bloques para obtener una coloración n ^M de longitud . Pero eso significa, por la definición de MinN , que puedes encontrar una secuencia aritmética unidimensional (con beneficios) de longitud L en la coloración de bloques, 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, 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 bien, según la definición de M , se puede 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 PA d -dimensional con beneficios aparece en todos los bloques, simplemente trasladándolo de un bloque a otro. Esta es la definición de una progresión aritmética d  +1 dimensional, por lo que se tiene un PA homogéneo d  +1 dimensional. 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, más sus traducciones en bloques de colores idénticos, 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 . Este es un único punto y es automáticamente homogéneo. ${\displaystyle i_{1}=i_{2}=\cdots =i_{D+1}=L}$

Lema 2  :  Supongamos que MinN es conocido para un valor de L y todas las dimensiones posibles D. Entonces, se puede acotar MinN para la longitud L  + 1 .

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

Prueba

Dado un coloreado n de un intervalo de tamaño MinN( L , n , n ) , por definición, se puede encontrar una secuencia aritmética con beneficios de dimensión n y 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, por ejemplo de dimensión k , tiene que tener el mismo color que otro de los límites de beneficio homogéneos, por ejemplo, el de dimensión p  <  k . Esto permite construir una secuencia aritmética de longitud L  + 1 (de dimensión 1), siguiendo 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})}$tienen 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, solo hay que añadir otro punto del color que sea. Para incluir este punto límite, hay que hacer que el intervalo sea más largo en el valor máximo posible de la zancada, que es ciertamente 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 se desea una secuencia aritmética homogénea de dimensión d y longitud 1, con o sin beneficios, no hay nada que hacer. Por lo tanto, esto constituye la base de la inducción. El teorema de Van der Waerden en sí mismo 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 son 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 prueba del teorema anterior es delicada y se remite al lector a ella. ^[12] Con este teorema de recurrencia, el teorema de van der Waerden puede demostrarse 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 arbitraria. ${\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 que esto se demuestra, podemos cortar esa progresión aritmética en conjuntos singleton y repetir el proceso para crear otra progresión aritmética, y así una de las particiones contiene infinitas progresiones aritméticas de longitud . ${\textstyle N}$ ${\textstyle N}$

Una vez demostrado 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}$

Consideremos el espacio de estados , con métrica compacta. En otras palabras, sea el índice más cercano a donde difieren, y entonces su distancia es . (De hecho, se trata de una ultramétrica). ${\textstyle \Omega :=(1:N)^{\mathbb {Z} }}$ $${\displaystyle d((x_{n}),(y_{n}))=\max\{2^{-|n|}:x_{n}\neq y_{n}\}}$$ ${\textstyle n}$ ${\textstyle 0}$ ${\textstyle x,y}$ ${\textstyle 1/2^{|n|}}$

Como cada número entero cae en exactamente una de las particiones , podemos codificar la partición en una secuencia . Cada uno es el nombre de la partición en la que cae. 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 desplazamientos: y luego, sea el cierre de todos los desplazamientos de la secuencia : Por el teorema de recurrencia múltiple de Birkhoff, existe alguna secuencia , y un entero , tales que ${\textstyle T:\Omega \to \Omega }$ $${\displaystyle T((x_{n})_{n})=(x_{n+1})_{n}}$$ ${\textstyle (z_{n})_{n}}$ ${\textstyle X}$
$${\displaystyle X:=cl(\{T^{n}z:n\in \mathbb {Z} \})}$$ ${\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}$$

Como es el cierre de los desplazamientos de , y es continua, 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 triangular, todos los pares del conjunto están cerca uno del otro: lo que implica , es decir que la secuencia aritmética está en la partición . ${\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}$$ ${\textstyle z_{m}=z_{m+n}=\dots =z_{m+Nn}}$ ${\textstyle m,m+n,\dots ,m+Nn}$ ${\textstyle S_{z_{m}}}$

Véase también

• Números de Van der Waerden para todos los valores conocidos de W ( n , r ) y los límites mejor 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 recolectar 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, consultado 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 de Matemática Pura . Reimpreso en el Capítulo 33 de "El libro para colorear matemático".
5. Graham, Ron (2007). "Algunos de mis problemas favoritos en la teoría de Ramsey". INTEGERS: La revista electrónica de teoría de números combinatorios . 7 (2): #A15.
6. Klarreich, Erica (2021). "Un matemático arroja estructura y desorden a un problema centenario". Revista Quanta .
7. Gowers, Timothy (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 demostración del teorema de van der Waerden sobre progresiones aritméticas". Actas de la American Mathematical Society . 42 (2): 385–386. doi : 10.1090/S0002-9939-1974-0329917-8 .
12. Petersen, Karl E. (1983). "Capítulo 2". Teoría ergódica. Cambridge Studies in Advanced Mathematics. Cambridge: Cambridge University Press. ISBN 978-0-521-38997-6.

Referencias

• Khinchin, A. Ya. (1998), Tres perlas de la teoría de números, Mineola, NY: 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 .