Número de Van der Waerden
El teorema de Van der Waerden establece que para cualquier entero positivo r y k existe un entero positivo N tal que si los enteros {1, 2, ..., N } están coloreados, cada uno con uno de r colores diferentes, entonces hay en menos k enteros en progresión aritmética todos del mismo color. El N más pequeño es el número de van der Waerden W ( r , k ).
Hay dos casos en los que el número de van der Waerden W ( r , k ) es fácil de calcular: primero, cuando el número de colores r es igual a 1, se tiene W (1, k ) = k para cualquier entero k , ya que un color produce solo coloraciones triviales RRRRR...RRR (para el color único indicado como R). Segundo, cuando la longitud k de la progresión aritmética forzada es 2, se tiene W ( r , 2) = r+ 1, ya que uno puede construir una coloración que evite progresiones aritméticas de longitud 2 usando cada color como máximo una vez, pero usar cualquier color dos veces crea una progresión aritmética de longitud 2. (Por ejemplo, para r = 3, la coloración más larga que evita una progresión aritmética de longitud 2 es RGB). Solo hay otros siete números de van der Waerden que se conocen con exactitud. La siguiente tabla proporciona valores y límites exactos para los valores de W ( r , k ); los valores se toman de Rabung y Lotts excepto donde se indique lo contrario. [1]
A veces también se escribe w (r; k 1 , k 2 , ..., k r ) para indicar el número más pequeño w tal que cualquier coloración de los enteros {1, 2, ..., w } con r colores contiene un progresión de longitud k i de color i , para algunos i . Estos números se denominan números de van der Waerden fuera de la diagonal . Así W ( r , k ) = w (r; k , k , ..., k). La siguiente es una lista de algunos números de van der Waerden conocidos:
Los números de Van der Waerden son recursivos primitivos , como lo demuestra Shelah ; [21] de hecho, probó que están (como máximo) en el quinto nivel de la jerarquía de Grzegorczyk .
