El teorema de Van der Waerden del es un teorema de la rama de las matemáticas llamadas la teoría de Ramsey. El teorema está sobre la estructura básica de los números enteros que se nombra para el holandés B. van der Waerden del matemático.

El teorema de Van der Waerden indica que para cualquier número entero positivo dado el r y el k, allí es un cierto N del número tales que si los números enteros {1, 2,…, N } son coloreado, cada uno con uno de diversos colores del r, después allí son por lo menos números enteros del k en la progresión aritmética todo el mismo color. El menos tal N es el V ( r,   del número de Van der Waerden; k ).

Por ejemplo, cuando el r = 2, usted tiene dos colores, decir el rojo y el azul. V (2, 3) es más grandes de 8, porque usted puede colorear los números enteros de {1,…, 8} como esto:

1 2 3 4 5 6 7 8 B R R B B R R B

y ningunos tres números enteros del mismo color forman una progresión aritmética. Pero usted no puede agregar un noveno número entero al extremo sin crear tal progresión.

Es un problema abierto para determinar los valores del V ( r, k ) para la mayoría de los valores del r y del k . La prueba del teorema proporciona solamente un límite superior. Para el caso del r =2 y del k = 3, por ejemplo, la discusión dada abajo demuestra que es suficiente colorear los números enteros {1,…, 325} con dos colores para garantizar que habrá una progresión aritmética solo-coloreada de la longitud 3. Pero de hecho, el límite de 325 está muy flojamente; el número required mínimo de números enteros es solamente 9. Cualquier colorante de los números enteros {1,…, 9} tendrá tres números enteros uniformemente espaciados de un color.

Para el r = 3 y el k = 3, el límite dado por el teorema es 7 (2·3⁷  +  1) (2·3^{7·(2·37  +  1)}  +  1), o aproximadamente 4.22·10¹⁴⁶¹⁶. Pero realmente, usted no necesita que muchos números enteros para garantizar una progresión solo-coloreada de la longitud 3; usted solamente necesidad 27. (Y es posible colorear {1,…, 26} con tres colores de modo que haya progresión aritmética ninguno-coloreada de la longitud 3; por ejemplo, RRYYRRYBYBBRBRRYRYYBRBBYBY.)

Cualquier persona que puede reducir el límite superior general a cualquier función “razonable” puede ganar un premio grande del efectivo. El Ronald Graham ha ofrecido un premio US$ 1000 para demostrar el < del V (2, k ); 2 ^{k 2}. El registro en curso es debido al Timothy Gowers, que establece $V\; del$

l (r, k) \ leq 2^ {2^ {r^ {2^ {2^ {k + 9}}}}},

primero estableciendo 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 previamente más conocido era debido al Saharon Shelah y procedido vía primero probar un resultado para el teorema de Hales-Jewett, que es otra consolidación del teorema de Van der Waerden.

El límite más bajo más conocido para el $V\; (2,\; k)$ es ese $V\; (2,\; k)\; >\; 2^k/k^\; \backslash \; epsilon$ para todo el ε positivo.

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

La prueba siguiente es debido al Ron Graham y B.

Probaremos el caso especial mencionado anteriormente, ese V (2, 3) el ≤ 325. Dejar el c ( n ) sea un colorante de los números enteros {1,…, 325}. Encontraremos tres elementos de {1,…, 325} en la progresión aritmética que sean el mismo color.

La divisoria {1,…, 325} en los 65 bloques {1,…, 5}, {6,…, 10},… {321,…, 325}, así cada bloque está de la forma { b ·5 + 1,…, b ·5 + 5} para un cierto b adentro {0,…, 64}. Puesto que cada número entero se colorea rojo o azul, cada bloque se colorea en una de 32 maneras diferentes. Por el principio de casillero, hay dos bloques entre los primeros 33 bloques que se colorean idénticamente. Es decir, hay dos números enteros del b ₁ y b ₂, ambos adentro {0,…, 32}, tales que c ( b ₁· del

l ; 5 + k ) = c ( b ₂· 5 + k )

para todo el k adentro {1,…, 5}. Entre los tres números enteros del b ₁·5 + 1, b ₁·5 + 2, b ₁·5 + 3, allí deben ser por lo menos dos que son el mismo color. (El principio de casillero otra vez.) Llamar este el b ₁·5 + un ₁ y b ₁·5 + un ₂, donde está el un i del _{de adentro {1.3} y un < de 1; un 2. Suponer (sin la pérdida de generalidad) que estos dos números enteros son ambos rojos. (Si son ambo azules, apenas intercambio “rojo” y “azul” en qué sigue.)}

Dejar el un ₃ = 2· un ₂  −   un ₁. Si b ₁·5 + un ₃ es rojos, después hemos encontrado nuestra progresión aritmética: b ₁·5  +  el un i es todo del _{de rojo.}

Si no, b ₁·5 + un ₃ es azules. Desde un ≤ 5, b ₁ de ₃·5 + un ₃ está en el bloque del b ₁, y puesto que el bloque del b ₂ se colorea idénticamente, el b ₂·5 + un ₃ es también azul.

Ahora dejar el b ₃ = 2· b ₂ - b ₁. Entonces ≤ 64 del b ₃. Considerar el b ₃ del número entero·5 + un ₃, que debe ser el ≤ 325. ¿Qué color es él?

Si es rojo, entonces el b ₁·5 + un ₁, b ₂·5 + un ₂, y b ₃·5 + una forma de ₃ una progresión aritmética roja. Pero si es azul, entonces b ₁·5 + un ₃, b ₂·5 + un ₃, y b ₃·5 + una forma de ₃ una progresión aritmética azul. Cualquier manera, nos hacen.

Una discusión similar se puede avanzar para demostrar ese V (3, 3) el ≤ 7 (2·3⁷+1) (2·3^7·(2·37+1)+1). Uno comienza dividiendo los números enteros en 2·3^{7·(2·37  +  1)}  +  1 grupo de 7 (2·3⁷  +  1) números enteros por cada uno; del primer 3^{7·(2·37  +  1)}  +  1 grupo, dos se debe colorear idénticamente.

Dividir a estos dos grupos en 2·subgrupos 3⁷+1 de 7 números enteros por cada uno; del primer 3⁷  +  1 los subgrupos en cada grupo, dos de los subgrupos se deben colorear idénticamente. Dentro de cada uno de estos subgrupos idénticos, dos de los primeros cuatro números enteros deben ser el mismo color, dicen rojo; esto implica o una progresión roja o un elemento de un diverso color, dice el azul, en el mismo subgrupo.

Puesto que tenemos dos subgrupos idéntico-coloreados, hay un tercer subgrupo, aún en el mismo grupo que contiene un elemento que, si rojo o azul, terminaría una progresión roja o azul, al lado de una construcción análoga a la que está para el V (2, 3). Suponer que este elemento es amarillo. Puesto que hay un grupo que se colorea idénticamente, debe contener las copias de los elementos rojos, azules, y amarillos que hemos identificado; podemos ahora encontrar un par de elementos rojos, un par de elementos azules, y un par de elementos amarillos que “centrarse” en el mismo número entero, de modo que cualquier color es, debe terminar una progresión.

Debe ser observado que la prueba para el V (2, 3) depende esencialmente de probar ese V (32, 2) el ≤ 65. Dividimos los números enteros {1,…, 325} en 65 “bloques”, que se pueden colorear en 32 maneras diferentes, y después demostramos que dos bloques deben ser el mismo color. Semejantemente, la prueba para el V (3, 3) depende de probar eso $V\; del$

l (3^ {7 (2 \ cdot3^7+1)}, 2) \ leq 2 \ cdot3^ {7 (2 \ cdot3^7+1)} +1.

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