Three-color van der Waerden numbers grow super-exponentially

Resumen Técnico: Los números de van der Waerden de tres colores crecen de forma superexponencial

Planteamiento del Problema
El artículo aborda la tasa de crecimiento de los números de van der Waerden, denotados como $w(k; r)$. Este número se define como el entero mínimo $N$ tal que toda $r$-coloración del conjunto $\{1, 2, \dots, N\}$ contiene una progresión aritmética monocromática de longitud $k$. Si bien la existencia de estos números está garantizada por el teorema de van der Waerden, su crecimiento asintótico preciso sigue siendo un problema fundamental abierto.

Históricamente, el crecimiento de $w(k; r)$ ha sido objeto de intensa especulación. Para un $r$ fijo, Erdős conjeturó que $w(k; 2)$ crece de forma superexponencial (es decir, $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$). Por el contrario, otras conjeturas sugerían un crecimiento exponencial lineal, específicamente $\lim_{k \to \infty} w(k; r)^{1/k} = r$. Antes de este trabajo, los mejores límites inferiores conocidos para $w(k; r)$ se habían derivado en gran medida del Lema de la Localidad de Lovász o de construcciones algebraicas específicas, arrojando cotas de la forma $w(k; r) \geq r^{k-1}/(4k)$ o, para un $r \geq 5$ fijo, cotas de la forma $(3r/3)^{(1-o(1))k}$. Los autores señalan que, si bien un resultado previo de Hunter [20] refutó la conjetura exponencial lineal para $r \geq 5$, el caso para $r=3$ (y el comportamiento general para valores pequeños de $r$ fijo) permanecía sin resolver.

Metodología
Los autores desarrollan una novedosa construcción probabilística para establecer límites inferiores para $w(k; r)$. La metodología se basa en tres componentes primarios:

1. Conjuntos Libres de Progresiones Densos en Grupos Cíclicos:
   Los autores construyen subconjuntos muy densos de grupos cíclicos $\mathbb{Z}_N$ que no contienen progresiones aritmáticas de $k$ términos (k-APs). Utilizan una extensión de la construcción de Erdős-Turán (conjuntos de enteros sin un dígito igual a $p-1$ en base $p$) adaptada a grupos cíclicos. Crucialmente, demuestran la existencia de "conjuntos de impacto" (Lema 2.8) que son dispersos (densidad $\leq \epsilon$) pero que intersectan cada k-AP en un grupo cíclico con una fracción constante de sus elementos. Esto se logra seleccionando clases de congruencia aleatorias módulo un conjunto de primos.

2. Consecuencias del Lema de la Localidad de Lovász (LLL):
   El artículo emplea la versión simétrica del Lema de la Localidad de Lovász para demostrar la existencia de coloraciones donde ninguna clase de color contiene una fracción "grande" de cualquier k-AP. Específicamente, el Corolario 3.3 establece que para grupos de orden $N$ sin factores primos pequeños, se pueden asignar subconjuntos de colores a los vértices de tal manera que ningún k-AP sea monocromático o casi monocromático.

3. Construcciones de Producto Desplazado Aleatorio:
   La innovación técnica central es una refinada construcción de "producto desplazado aleatorio" (Lemmas 4.2 y 4.3). A diferencia de las coloraciones de producto estándar que multiplican el número de colores, este método permite a los autores combinar coloraciones de grupos más pequeños en un grupo más grande mientras mantiene el número de colores fijo (o aumentándolos de manera controlada).

• Mecanismo: Dado una coloración $c_1$ de $H_1$ y $c_2$ de $H_2$, la construcción define una coloración en $H_1 \times H_2$ desplazando independientemente las fibras de la proyección sobre $H_2$ y permutando los colores basándose en el color del elemento base en $H_1$.
• Proceso Iterativo: Los autores iteran esta construcción. En cada paso, combinan una coloración de un grupo $Z_{n_{j-1}}$ con una coloración de un grupo cíclico de orden primo $Z_{q_j}$. La construcción aumenta el tamaño del grupo por un factor exponencial en $k$, mientras incurre en una pérdida "doble exponencial" en el parámetro de densidad de la clase de color "buena". Al equilibrar cuidadosamente estos parámetros, el proceso puede iterarse aproximadamente $(\log^* k)/2$ veces.

Contribuciones Clave y Resultados

• Crecimiento Superexponencial para Tres Colores:
  El resultado principal (Teorema 1) demuestra que para $k$ suficientemente grande, el número de van der Waerden de tres colores satisface:
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  Esto establece que $w(k; 3)$ crece más rápido que cualquier función exponencial de $k$, refutando así la conjetura de que $\lim_{k \to \infty} w(k; r)^{1/k} = r$ para $r \geq 3$.

• Límites Inferiores para Muchos Colores:
  El Teorema 2 proporciona un límite inferior para el régimen donde el número de colores $r$ es grande en relación con $k$ (específicamente $r \geq (\log k)^{3/\epsilon}$):
  $$w(k; r) \geq r^{(1-\epsilon)k \log k}$$
  Esto mejora los límites previos en el régimen de "muchos colores".

• Resolución del Problema de Erdős-Graham:
  Los autores abordan el número de van der Waerden canónico $H(k)$, definido como el entero mínimo $N$ tal que toda coloración de $[N]$ contiene una $k$-AP monocromática o arcoíris. Erdős y Graham conjeturaron si $H(k)^{1/k}/k \to \infty$. Utilizando su límite inferior mejorado para $w(k; k-1)$, los autores demuestran (Teorema 3) que:
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  Esto confirma que $H(k)$ crece de forma superexponencial, resolviendo el problema abierto planteado por Erdős y Graham.

Significado
El artículo afirma que el crecimiento de los números de van der Waerden para tres o más colores es superexponencial, un resultado que altera fundamentalmente la comprensión de estos números combinatorios. La importancia radica en:

1. Refutación de la Conjetura Exponencial Lineal: Demuestra definitivamente que $w(k; r)$ no se comporta como $r^k$ para $r \geq 3$.
2. Avance Metodológico: La introducción de la construcción de "producto desplazado aleatorio" permite iterar argumentos probabilísticos mientras se mantiene un número fijo de colores, una técnica que los autores señalan es más eficiente que las versiones anteriores utilizadas para $r \geq 5$.
3. Teoría Ramsey Canónica: Los resultados proporcionan una resolución sólida al problema de Erdős-Graham respecto a los números de van der Waerden canónicos, mostrando que incluso cuando se permiten progresiones arcoíris, el $N$ requerido es vastamente mayor que los límites inferiores establecidos previamente.

Los autores señalan que, si bien sus técnicas son generales, la aplicación específica aquí se centra en establecer estos límites inferiores. Sugieren que estas construcciones pueden ser aplicables para obtener nuevos límites para otros números de Ramsey aritméticos, un tema que pretenden explorar en una nota complementaria. El artículo no pretende determinar la tasa de crecimiento exacta ni proporcionar límites superiores, sino que establece un límite inferior significativamente más fuerte de lo conocido anteriormente.