El teorema de Van der Waerden es un teorema en la rama de las matemáticas llamado teoría de Ramsey . Van der Waerden teorema que para cualquier positivos dados enteros r y k , hay un cierto número N tal que si los enteros {1, 2, ..., N } son de color, cada uno con uno de r diferentes colores, entonces hay al menos k 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), llamado así por el matemático holandés BL van der Waerden . [1]
Ejemplo
Por ejemplo, cuando r = 2, tiene 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:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
B | R | R | B | B | R | R | B |
y no hay tres números 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 9 rojo , entonces el 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 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 demostración 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 enteros {1, ..., 325} con dos colores para garantizar que habrá una aritmética de un solo color. progresión de la longitud 3. Pero, de hecho, el límite de 325 está muy suelto; el número mínimo requerido de enteros es sólo 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 · 3 7 + 1) (2 · 3 7 · (2 · 3 7 + 1) + 1), o aproximadamente 4.22 · 10 14616 . 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 | dieciséis | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
R | R | GRAMO | GRAMO | R | R | GRAMO | B | GRAMO | B | B | R | B | R | R | GRAMO | R | GRAMO | GRAMO | B | R | B | B | GRAMO | B | GRAMO |
.)
Cualquiera que pueda reducir el límite superior general a cualquier función "razonable" puede ganar un gran premio en efectivo. Ronald Graham ha ofrecido un premio de US $ 1000 por mostrar W (2, k ) <2 k 2 . [2] El mejor límite superior conocido actualmente se debe a Timothy Gowers , [3] quien establece
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ó mediante la primera prueba 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 por es eso para todo positivo tenemos , para todo lo suficientemente grande . [4]
Prueba del teorema de Van der Waerden (en un caso especial)
La siguiente prueba se debe a Ron Graham y BL Rothschild. [5] Khinchin [6] da una demostración bastante simple del teorema sin estimar W ( r , k ).
Prueba en el caso de W (2, 3)
B | c ( n ): color de números 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 |
Demostraremos el caso especial mencionado anteriormente, que W (2, 3) ≤ 325. Sea c ( n ) una coloración de los 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 alguna b en {0, ..., 64}. Dado que cada número entero está coloreado de rojo o azul , cada bloque se colorea de una de las 32 formas diferentes. Según el principio del casillero , hay dos bloques entre los primeros 33 bloques que tienen el mismo color. Es decir, hay dos enteros b 1 y b 2 , ambos en {0, ..., 32}, de modo que
- c (5 b 1 + k ) = c (5 b 2 + k )
para todo k en {1, ..., 5}. Entre los tres números enteros 5 b 1 + 1, 5 b 1 + 2, 5 b 1 + 3, debe haber al menos dos que sean del mismo color. (El principio del casillero nuevamente.) Llame a estos 5 b 1 + a 1 y 5 b 1 + a 2 , donde a i están en {1,2,3} y a 1 < a 2 . Suponga (sin pérdida de generalidad) que estos dos números enteros son ambos rojos . (Si ambos son azules , simplemente intercambie ' rojo ' y ' azul ' en lo que sigue).
Sea a 3 = 2 a 2 - a 1 . Si 5 b 1 + a 3 es rojo , entonces hemos encontrado nuestra progresión aritmética: 5 b 1 + a i son todos rojos .
De lo contrario, 5 b 1 + a 3 es azul . Dado que a 3 ≤ 5, 5 b 1 + a 3 está en el bloque b 1 , y dado que el bloque b 2 tiene el mismo color, 5 b 2 + a 3 también es azul .
Ahora sea b 3 = 2 b 2 - b 1 . Entonces b 3 ≤ 64. Considere el número entero 5 b 3 + a 3 , que debe ser ≤ 325. ¿De qué color es?
Si es rojo , entonces 5 b 1 + a 1 , 5 b 2 + a 2 y 5 b 3 + a 3 forman una progresión aritmética roja . Pero si es azul , entonces 5 b 1 + a 3 , 5 b 2 + a 3 y 5 b 3 + a 3 forman una progresión aritmética azul . De cualquier manera, hemos terminado.
Prueba en el caso de W (3, 3)
B | c ( n ): color de números enteros | ||||
---|---|---|---|---|---|
0 | 1 | 2 | 3 | ... | metro |
GRAMO | R | R | ... | B | |
1 | m +1 | m +2 | m +3 | ... | 2m |
B | R | GRAMO | ... | R | |
... | ... | ||||
gramo | gm + 1 | gm + 2 | gm + 3 | ... | (g + 1) m |
B | R | B | ... | GRAMO |
Se puede avanzar un argumento similar para mostrar que W (3, 3) ≤ 7 (2 · 3 7 +1) (2 · 3 7 · (2 · 3 7 +1) +1). Uno comienza dividiendo los números enteros en 2 · 3 7 · (2 · 3 7 + 1) + 1 grupos de 7 (2 · 3 7 + 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 7 +1 subgrupos de 7 enteros cada uno; de los primeros 3 7 + 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.
Dado que tenemos dos subgrupos de idéntico color, 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 el mismo color, 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 'enfocan' en el mismo número entero, de modo que sea cual sea el color, debe completar una progresión.
Prueba en caso general
La prueba 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 puede colorearse en 32 de diferentes maneras, y luego muestre que dos bloques de los primeros 33 deben ser del mismo color, y hay un bloque coloreado de la manera opuesta. De manera similar, la prueba de W (3, 3) depende de probar que
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) de dimensión D consta de números de la forma:
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 algunos colores cuando todos son del mismo color.
Un D progresión aritmética dimensional con beneficios es todos los números de la forma anterior, pero donde se agrega en algunos de los "límites" de la progresión aritmética, es decir, algunos de los índices i 's puede ser igual a L . Los lados que añadir son aquellos en los que el primer k i 's son iguales a L , y los restantes i ' s son menos de 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 del í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 tienen por qué tener necesariamente el mismo color.
A continuación, defina la cantidad MinN (L, D, N) como el menor número 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 D- dimensional homogénea 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 Minn es conocido por un longitudes dadas L para todas las dimensiones de progresiones aritméticas con beneficios hasta D . Esta fórmula da un límite en MinN cuando aumenta la dimensión a D + 1 :
dejar , luego
Primero, si tiene un color n del intervalo 1 ... I , puede definir un color de bloque de bloques de tamaño k . Solo considere cada secuencia de k colores en cada k bloque para definir un color único. Llame a esto k -blocking an n -coloring. k -bloqueo y coloración n de longitud l produce una coloración n k de longitud l / k .
Entonces, dado un color n de un intervalo I de tamañopuedes M -Block en un n M coloración de longitud. Pero eso significa, según la definición de MinN , que puede 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, tiene 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.
Ahora, por la definición de M , 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 AP d- dimensional con beneficios aparece en todos de los bloques, simplemente traduciéndolo de un bloque a otro. Esta es la definición de una progresión aritmética d + 1 dimensional, por lo que tiene un AP d + 1 dimensional homogéneo . El nuevo parámetro de zancada s D + 1 se define como la distancia entre los bloques.
Pero necesitas beneficios. Los límites que recibe ahora son todos los límites de edad, además de sus traducciones en 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. Este es un solo punto y es automáticamente homogéneo.
Lema 2 - Supongamos Minn es conocido por un valor de L y todos los posibles dimensiones D . Luego, puede vincular MinN para la longitud L + 1 .
Dado un n -Coloreado de un intervalo de tamaño de Minnesota (L, N, N) , por definición, se puede encontrar una progresión aritmética con beneficios de dimensión n de longitud L . Pero ahora, el número de límites de "beneficios" es igual al número de colores, por lo que uno de los límites homogéneos, digamos de dimensión k , debe tener el mismo color que otro de los límites de beneficios homogéneos, digamos el de dimensión p
Si
- tiene el mismo color que
luego
- tener el mismo color
- es decir, u hace 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, uno tiene que alargar el intervalo en el valor máximo posible de la zancada, que ciertamente es menor que el tamaño del intervalo. Entonces, duplicar el tamaño del intervalo definitivamente funcionará, y esta es la razón del factor de dos. Esto completa la inducción de 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í 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. [5]
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 los 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
- ↑ van der Waerden, BL (1927). "Beweis einer Baudetschen Vermutung". Nieuw. Arco. Wisk. (en alemán). 15 : 212-216.
- ^ 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.
- ^ Gowers, Timothy (2001). "Una nueva prueba del teorema de Szemerédi" . Geom. Funct. Anal . 11 (3): 465–588. doi : 10.1007 / s00039-001-0332-9 .
- ^ 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". Estructura aleatoria. Algoritmos . 1 (3): 343–360. doi : 10.1002 / rsa.3240010307 .
- ^ a b Graham, RL ; Rothschild, BL (1974). "Una breve prueba del teorema de van der Waerden sobre progresiones aritméticas" . Proc. Amer. Matemáticas. Soc . 42 (2): 385–386. doi : 10.1090 / S0002-9939-1974-0329917-8 .
- ^ Khinchin (1998 , págs. 11-17, capítulo 1)
Referencias
- Khinchin, A. Ya. (1998), Three Pearls of Number Theory , Mineola, NY: Dover, págs. 11-17, ISBN 978-0-486-40026-6
enlaces externos
- O'Bryant, Kevin . "Teorema de van der Waerden" . MathWorld .
- O'Bryant, Kevin y Weisstein, Eric W. "Número de Van der Waerden" . MathWorld .