Demostración del teorema de van der Waerden

Question

El Teorema de van der Waerden afirma que dados cualesquiera números naturales $k$ y $r$ existe un número natural $W=W(k,r)$ tal que si el conjunto $\{1,2\cdots W\}$ se divide en $r$ (también llamados colores) entonces existe un $k$ -progresión aritmética en una clase.

Intento demostrar el teorema según el esquema dado aquí .

He entendido las pruebas para $W(3,2) \le 325$ y $W(3, 3) \le 7(2·3^7+1)(2·3^{7·(2·3^7+1)}+1)$ y en líneas similares han elaborado una prueba para $W(3,4)\le 9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)(2.4^{9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)}+1)$ .

Lo que quiero hacer es demostrar el teorema en general en líneas similares. El principal problema es para mí en cuanto a lo que será el límite superior para empezar y luego cómo lidiar con la notación engorroso.

Entiendo que pedirle a alguien que pruebe el resultado completo no es apropiado aquí, pero si pueden darme alguna ayuda se lo agradeceré enormemente.

Gracias.

Answer 1

Como ya tienes una prueba para $W(3,4)$ y dices que has leído el libro de GRS, voy a omitir cualquier discusión sobre cómo funciona realmente la prueba, y sólo me centraré en la parte que dices que te falta, que es la inducción. En realidad se trata de una triple inducción, primero sobre el número de colores $c$ para una longitud de progresión fija $n$ , entonces en la longitud de la progresión $n$

A continuación, para un determinado $(c, n)$ se encuentra por inducción, para cada par $i$ , una estructura que contiene un único "objetivo $^i$ " entero que necesariamente completaría una progresión si es cualquiera de $i$ diferentes colores. Una vez que $i=c$ hemos terminado.

Los casos base son que $W(2, c) = c+1$ y $W(n, 1) = 1$ aún más fácil.

Ahora queremos encontrar un límite para $W(n, c)$ . Podemos suponer $n>2$ , $c>1$ y sabemos que algunos $W(n', c')$ para todos los pares $(n', c') < (n, c)$ lo que significa que, o bien $n'<n$ o ( $n'=n$ y $c'<c$ ).

No he editado lo siguiente con mucho cuidado, y lo he escrito más bien a destiempo, por lo que puede haber muchos errores, sobre todo de bulto. Pero creo que la idea es sólida y está bien documentada. Estaré encantado de recibir comentarios y correcciones.

Considere un bloque $B_1$ de $b_1 = 2W(n-1, c)-1$ elementos; podemos estar seguros de que la primera mitad de este bloque (elementos $1\ldots W(n-1,c)$ ) contiene una longitud $(n-1)$ progresión monocromática de algún color $\chi_1$ . Si la progresión es $x_1, x_2, \ldots x_{n-1}$ entonces $B_1$ también contiene un "elemento objetivo" $2x_{n-1} - x_{n-2}$ . Si este elemento es de color $\chi_1$ hemos terminado, por lo que asumimos que es algún otro color.

Consideremos ahora un superbloque $B_2$ que consiste en $b_2 = 2W(n-1, c^{b_1})-1$ bloques de tamaño $b_1$ . (Tengo $W(n-1, c^{b_1}$ ) por la hipótesis de inducción). Imaginaré que se trata de una secuencia de bloques cada uno de los cuales está coloreado con uno de $c^{b_1}$ colores. Puedo suponer que la primera mitad de esta secuencia (elementos $1\ldots W(n-1, c^{b_1})$ ) contiene una progresión de $n-1$ bloques de idéntico color. Cada uno de ellos contiene un "elemento de destino" que por el párrafo anterior no puede ser coloreado con color $\chi_1$ ; dicen que son todo color $\chi_2$ . Por la construcción es GRS, los propios elementos objetivo forman una progresión aritmética monocromática de longitud $n-1$ y apuntan a un "elemento objetivo²" que no puede ser de color $\chi_1$ o $\chi_2$ . Entonces digamos que el elemento objetivo² es el color $\chi_3$ .

Ahora vamos a saltar al paso de la inducción. Tengo un super $^{d-1}$ -bloque compuesto por $b_{d+1} = 2W(n-1, c^{b_d})-1$ bloques de tamaño $b_d$ . Puedo suponer que la primera mitad de esta secuencia (elementos $1\ldots W(n-1, c^{b_d})$ ) contiene una progresión de $n-1$ bloques de idéntico color. Cada uno de ellos contiene un "objetivo $^{d-1}$ elemento" que no puede ser de color $\chi_1\ldots\chi_{d-1}$ y el $n-1$ objetivo $^{d-1}$ los elementos forman una progresión aritmética monocromática de algún color, digamos $\chi_d$ cuyo siguiente elemento se convierte, por tanto, en un "objetivo $^d$ elemento" que no puede ser de color $\chi_1\ldots\chi_d$ .

Basta con aplicar este paso de inducción $c$ veces, por lo que el bloque final es el super $^{c-1}$ -bloque compuesto por $b_c = 2W(n-1, c^{b_{c-1}})-1$ super $^{c-2}$ bloques de tamaño $b_{c-1}$

Esto es suficiente para demostrar que $W(n, c)$ existe realmente. Pero nos gustaría saber qué tamaño tiene. Tenemos $b_{d} = 2W(n-1, c^{b_{d-1}})-1$ y $W(n, c) = \prod_1^c{b_i}$ que da una recurrencia para un límite en el tamaño de $W$ . Tengo que volver al trabajo ahora, así que lo dejaré para ti.

Espero que esto contenga muchos errores, por lo que lo he convertido en un Wiki comunitario, e invito alegremente a todos a editar la respuesta sin consultarme.

Answer 2

Además de los dos parámetros $k$ y $r$ debe introducir otro parámetro $j$ correspondiente a la profundidad de sus grupos internos en la prueba.

Esto nos lleva a la siguiente definición (complicada pero inevitable) de una función $V(k,r,j)$ para $k\geq 2, r\geq 1, j \geq 0$ :

$$V(2,r,j)=2j+1 \ (j\geq 0)$$

$$V(k,r,0)=1 \ (k\geq 2,r \geq 1)$$

$$V(k,r,j+1)=V(k,r,j)V(k-1,r^{V(k,r,j)},r^{V(k,r,j)}) \ (k\geq 2,r \geq 1,j\geq 0)$$

Entonces tenemos por doble inducción en $j$ y $k$ :

TEOREMA. Cualquier intervalo entero de tamaño $V(k,r,j)$ , coloreado con $r$ colores, contiene un anidado $k-1$ -progresión de $k-1$ -procesos de $(k-1)$ -procesos ... (con profundidad $j$ ) donde cualquier progresión anidada $P$ se centra en algún número entero $x_P$ después de ella, y la siguiente progresión anidada está formada por $k-1$ traducciones regularmente espaciadas de $P \cup \lbrace x_P \rbrace$ .

Cuando tomamos $j=r$ en el teorema, hay $r+1$ puntos finales enfocados $x_P$ por lo que al menos dos de ellos deben tener el mismo color, por lo que hay un monocromático $k$ -progresión. Deducimos

COROLARIO. $W(k,r) \leq V(k,r,r)$ .

Puede comprobar como ejercicio que $$V(3, 3,3)= 7(2·3^7+1)(2·3^{7·(2·3^7+1)}+1)$$ y $$V(3,4,4)= 9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)(2.4^{9(2.4^9+1)(2.4^{9(2.4^9+1)}+1)}+1)$$