Teorema de Van der Waerden
El teorema de Van der Waerden es un teorema en 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, luego hay al menos k enteros en progresión aritmética cuyos elementos son del mismo color. El menor N es el número de Van der Waerden W(r, k), llamado así por el matemático holandés BL van der Waerden.
Ejemplo
Por ejemplo, cuando r = 2, tiene dos colores, digamos red y azul. W(2, 3) es mayor que 8, porque puedes colorear los números enteros desde {1,..., 8} así:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| B | R | R | B | B | R | R | B |
y no hay tres enteros del mismo color que formen una progresión aritmética. Pero no puede agregar un noveno entero al final sin crear tal progresión. Si agrega un rojo 9, entonces el rojo 3, 6 y 9 están en progresión aritmética. Alternativamente, si agrega un azul 9, entonces el azul 1, 5 y 9 están en progresión aritmética.
De hecho, no hay forma de colorear del 1 al 9 sin crear tal progresión (se puede probar considerando ejemplos). Por lo 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 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 enteros es solo 9. Cualquier coloración de los enteros {1,..., 9} tendrá tres enteros espaciados uniformemente de un color.
Para r = 3 y k = 3, el límite dado por el teorema es 7(2·37 + 1)(2·37·(2·37 + 1) + 1), o aproximadamente 4,22·1014616. Pero en realidad, no necesita 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:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| R | R | G | G | R | R | G | B | G | B | B | R | B | R | R | G | R | G | G | B | R | B | B | G | B | G |
Un problema abierto es el intento de reducir el límite superior general a cualquier valor 'razonable' función. Ronald Graham ofreció un premio de US$1000 por mostrar W(2, k) < 2k2. Además, ofreció un premio de 250 dólares estadounidenses por una prueba de su conjetura que involucre números de van der Waerden fuera de la diagonal más generales, declarando W(2; 3, k) ≤ kO(1), mientras que mencionar evidencia numérica sugiere W(2; 3, k) = k2 + o(1). Ben Green refutó esta última conjetura y demostró contraejemplos superpolinómicos para W(2; 3, k) < kr para cualquier r. El mejor límite superior conocido actualmente se debe a Timothy Gowers, quien establece
- W()r,k)≤ ≤ 22r22k+9,{displaystyle W(r,k)leq 2^{2^{2^{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 procedió a probar 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 W()2,k){displaystyle W(2,k)} es eso para todo positivo ε ε {displaystyle varepsilon } tenemos 2^{k}/k^{varepsilon }}" xmlns="http://www.w3.org/1998/Math/MathML">W()2,k)■2k/kε ε {displaystyle W(2,k)} {k}/k^{varepsilon }2^{k}/k^{varepsilon }" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/045045535ed2655006f05a36e645307bd33a4e92" style="vertical-align: -0.838ex; width:16.374ex; height:3.176ex;"/>, para todo lo suficientemente grande k{displaystyle k}.
Demostración del teorema de Van der Waerden (en un caso especial)
La siguiente prueba se debe a Ron Graham y B.L. Rothschild. Khinchin da una prueba bastante simple del teorema sin estimar W(r, k).
Prueba en el caso de W(2, 3)
| b | c()n): color de enteros | ||||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 |
| R | R | B | R | B | |
| 1 | 6 | 7 | 8 | 9 | 10 |
| B | R | R | B | R | |
| ... | ... | ||||
| 64 | 321 | 322 | 323 | 324 | 325 |
| R | B | R | B | R | |
Probaremos el caso especial mencionado anteriormente, que W(2, 3) ≤ 325. Sea c(n) un coloración de los enteros {1,..., 325}. Encontraremos tres elementos de {1,..., 325} en progresión aritmética que son del mismo color.
Dividir {1,..., 325} en los 65 bloques {1,..., 5}, {6,..., 10},... {321,..., 325}, por tanto, cada bloque tiene la forma {5b + 1,..., 5b + 5} para alguna b en {0,..., 64}. Dado que cada número entero tiene un color rojo o azul, cada bloque tiene un color de una de 32 maneras diferentes. Por el principio del casillero, hay dos bloques entre los primeros 33 bloques que tienen el mismo color. Es decir, hay dos enteros b1 y b2, ambos en {0,..., 32}, tal que
- c(5b1 + k) c(5b2 + k)
para todo k en {1,..., 5}. Entre los tres enteros 5b1 + 1, 5b1 + 2, 5b1 + 3, debe haber al menos dos que sean del mismo color. (El principio del casillero nuevamente). Llame a estos 5b1 + a1 y 5b1 + a2, donde ai están en {1,2,3} y a1 < a2. Supongamos (sin pérdida de generalidad) que estos dos números enteros son ambos rojo. (Si ambos son azul, simplemente intercambie 'rojo' y & #39;azul' en lo que sigue).
Sea a3 = 2a2 − a 1. Si 5b1 + a3 es rojo, entonces hemos encontrado nuestra progresión aritmética: 5b1 + ai son todos rojo.
De lo contrario, 5b1 + a3 es azul. Dado que a3 ≤ 5, 5b1 + a3 está en el bloque b1, y dado que el bloque b2 tiene el mismo color, 5 b2 + a3 también es azul.
Ahora sea b3 = 2b2 − b1. Entonces b3 ≤ 64. Considere el número entero 5b3 + a3, que debe ser ≤ 325. ¿De qué color es?
Si es rojo, entonces 5b1 + a 1, 5b2 + a2, y 5b 3 + a3 forman una progresión aritmética red. Pero si es azul, entonces 5b1 + a3, 5b2 + a3, y 5b3 + a3 forman una progresión aritmética blue. De cualquier manera, hemos terminado.
Prueba en el caso de W(3, 3)
| b | c()n): color de enteros | ||||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | ... | m |
| G | R | R | ... | B | |
| 1 | m + 1 | m + 2 | m + 3 | ... | 2m |
| B | R | G | ... | R | |
| ... | ... | ||||
| g | g + 1 | g + 2 | g + 3 | ... | ()g + 1)m |
| B | R | B | ... | G | |
Se puede avanzar un argumento similar para mostrar que W(3, 3) ≤ 7(2·37+1)(2·37 ·(2·37+1)+1). Se empieza dividiendo los enteros en 2·37·(2·37 + 1) + 1 grupos de 7(2·37 + 1) enteros cada uno; de los primeros 37·(2·37 + 1) + 1 grupos, dos deben tener el mismo color.
Divida cada uno de estos dos grupos en 2·37+1 subgrupos de 7 enteros cada uno; de los primeros 37 + 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 red; esto implica una progresión red o un elemento de un color diferente, digamos blue, en el mismo subgrupo.
Dado que tenemos dos subgrupos de colores idénticos, hay un tercer subgrupo, aún en el mismo grupo que contiene un elemento que, si es rojo o blue, completaría un red o blue progresión, por una construcción análoga a la de W(2, 3). Supongamos que este elemento es verde. Dado que hay un grupo que tiene el mismo color, debe contener copias del rojo, azul, y elementos verde que hemos identificado; ahora podemos encontrar un par de elementos red, un par de elementos blue y un par de elementos verde que 'enfocan' en el mismo entero, de modo que sea del color que sea, debe completar una progresión.
Prueba en caso general
La demostración de W(2, 3) depende esencialmente de probar que W(32, 2) ≤ 33. Dividimos los enteros {1,...,325} en 65 'bloques', cada uno de los cuales se puede colorear de 32 maneras diferentes, y luego mostrar que dos bloques de los primeros 33 deben ser del mismo color, y hay un bloque coloreado de manera opuesta. De manera similar, la demostración de W(3, 3) depende de demostrar que
- W()37()2⋅ ⋅ 37+1),2)≤ ≤ 37()2⋅ ⋅ 37+1)+1.{displaystyle W(3^{7(2cdot 3^{7}+1)},2)leq 3^{7(2cdot 3^{7}+1)}+1.}
Por una doble inducción sobre el número de colores y la longitud de la progresión, el teorema se demuestra en general.
Prueba
Una progresión aritmética (AP) D-dimensional consta de números de la forma:
- a+i1s1+i2s2+⋯ ⋯ +iDsD{displaystyle a+i_{1}s_{1}+i_{2}s_{2}+cdots #
donde a es el punto base, el s's son tamaños de paso positivos y i's van de 0 a L − 1. Un AP d-dimensional es homogéneo para algunos colores cuando es todos del mismo color.
Una progresión aritmética D-dimensional con beneficios son todos los números de la forma anterior, pero donde se agrega parte del "límite" de la progresión aritmética, es decir, algunos de los índices i's pueden ser iguales a L. Los lados que agrega son aquellos en los que el primer k i's son iguales a L, y el resto i' s son menores que L.
Los límites de un D-dimensional AP con beneficios son estas progresiones aritméticas adicionales de dimensión d− − 1,d− − 2,d− − 3,d− − 4{displaystyle d-1,d-2,d-3,d-4}, hasta 0. La progresión aritmética 0dimensional es el único punto en valor índice ()L,L,L,L,...... ,L){displaystyle (L,L,L,L,ldotsL)}. A D-dimensional AP con beneficios homogénea cuando cada uno de los límites son individualmente homogéneos, pero diferentes límites no tienen que necesariamente tener el mismo color.
A continuación, defina la cantidad MinN(L, D, N) a ser el menor entero para que cualquier asignación de N colores a un intervalo de longitud MinN o más contiene necesariamente una progresión aritmética D-dimensional con ventajas.
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 inducciones, como sigue:
Lemma 1—Assume MinN es conocido por una longitud dada L para todas las dimensiones de progresiones aritméticas con beneficios hasta D. Esta fórmula da un límite MinN cuando aumenta la dimensión a D+ 1:
Deja M=MinN ()L,D,n){displaystyle M=operatorname {MinN} (L,D,n)}, entonces
- MinN ()L,D+1,n)≤ ≤ M⋅ ⋅ MinN ()L,1,nM){displaystyle operatorname {MinN} (L,D+1,n)leq Mcdot operatorname {MinN} (L,1,n^{M})}
Primero, si tienes un n-coloración del intervalo 1...I, usted puede definir un bloque para colorear de k- bloques de tamaño. Simplemente considere cada secuencia de k colores en cada k bloque para definir un color único. Llama esto. k-blocking an n-colorante. k- bloqueando un n coloración de la longitud l produce un nk coloración de la longitud lk.
Así que dado un n-coloración de un intervalo I de tamaño M⋅ ⋅ MinN ()L,1,nM)){displaystyle Mcdot operatorname {MinN} (L,1,n^{M})} Puedes M-...bloquearlo en un nM coloración de la longitud MinN ()L,1,nM){displaystyle operatorname {MinN} (L,1,n^{M}}. Pero eso significa, por definición MinN, que usted puede encontrar una secuencia aritmética de 1 dimensión (con beneficios) de longitud L en la coloración del bloque, que es una secuencia de bloques igualmente espaciados, que son todos el mismo color del bloque, es decir, tienes un montón de bloques de longitud M en la secuencia original, que son igualmente espaciadas, que tienen exactamente la misma secuencia de colores dentro.
Ahora, por la definición de M, puedes encontrar un d- secuencia aritmética dimensional con beneficios en cualquiera de estos bloques, y ya que todos los bloques tienen la misma secuencia de colores, la misma d-dimensional AP con beneficios aparece en todos los bloques, sólo traduciéndolo de bloque a bloque. Esta es la definición de un d+ 1 progresión aritmética dimensional, por lo que tiene una homogeneidad d+ 1 AP dimensional. El nuevo parámetro stride sD+ 1 se define como la distancia entre los bloques.
Pero necesitas beneficios. Los límites que obtienes ahora son todos los límites antiguos, además de sus traducciones en bloques de colores idénticos, porque iD+1 siempre es menos que L. El único límite que no es así es el punto 0-dimensional cuando i1=i2=⋯ ⋯ =iD+1=L{displaystyle i_{1}=i_{2}=cdots =i_{D+1}=L}. Este es un solo punto, y es automáticamente homogéneo.
Lemma 2—Assume MinN es conocido por un valor de L y todas las dimensiones posibles D. Entonces puedes atar a MinN por longitud L+ 1.
- MinN ()L+1,1,n)≤ ≤ 2MinN ()L,n,n){displaystyle operatorname {MinN} (L+1,n)leq 2operatorname {MinN} (L,n,n)}
Dado un n-coloración de un intervalo de tamaño MinN(L,n,n), por definición, se puede encontrar una secuencia aritmética con beneficios de la dimensión n de longitud L. Pero ahora, el número de límites "beneficios" es igual al número de colores, por lo que uno de los límites homogéneos, dicen de la dimensión k, tiene que tener el mismo color que otro de los límites de beneficio homogéneo, decir el de la dimensión p.k. Esto permite una longitud L+ 1 secuencia aritmética (de la dimensión 1) a construir, a lo largo de una línea dentro de la k- frontera dimensional que termina justo en el p-limitación dimensional, e incluyendo el punto terminal en el p- límites dimensionales. En fórmulas:
si
- a+Ls1+Ls2+⋯ ⋯ +LsD− − k{displaystyle a+Ls_{1}+Ls_{2}+cdots # tiene el mismo color que
- a+Ls1+Ls2+⋯ ⋯ +LsD− − p{displaystyle a+Ls_{1}+Ls_{2}+cdots #
entonces
- a+L⋅ ⋅ ()s1+⋯ ⋯ +sD− − k)+u⋅ ⋅ ()sD− − k+1+⋯ ⋯ +sp){displaystyle a+Lcdot (s_{1}+cdots +s_{D-k})+ucdot (s_{D-k+1}+cdots +s_{p}}} tienen el mismo color
- u=0,1,2,⋯ ⋯ ,L− − 1,L{displaystyle u=0,1,2,cdotsL-1,L} i.e. u hace una secuencia de longitud L+1.
Esto construye una secuencia de la dimensión 1, y los "beneficios" son automáticos, sólo agregue en otro punto de cualquier color. Para incluir este punto límite, hay que hacer el intervalo más largo por el valor máximo posible de la zancada, que es ciertamente menos que el tamaño del intervalo. Así que duplicar el tamaño del intervalo definitivamente funcionará, y esta es la razón para el factor de dos. Esto completa la inducción en L.
Caso base: MinN(1,d,n) = 1, es decir, si desea una longitud de 1 d-secuencia aritmética homogénea, con o sin beneficios, no tienes nada que hacer. Así que esto forma 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 sigue del caso base y los pasos de inducción.