Three-color van der Waerden numbers grow super-exponentially

Resumo Técnico: Os números de van der Waerden de três cores crescem super-exponencialmente

Enunciado do Problema
O artigo aborda a taxa de crescimento dos números de van der Waerden, denotados por $w(k; r)$. Este número é definido como o menor inteiro $N$ tal que toda coloração de $r$ cores do conjunto $\{1, 2, \dots, N\}$ contém uma progressão aritmética monocromática de comprimento $k$. Embora a existência desses números seja garantida pelo teorema de van der Waerden, seu crescimento assintótico preciso permanece um problema fundamental em aberto.

Historicamente, o crescimento de $w(k; r)$ tem sido objeto de intensa especulação. Para um $r$ fixo, conjecturou Erdős que $w(k; 2)$ cresce super-exponencialmente (ou seja, $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$). Inversamente, outras conjecturas sugeriam crescimento exponencial linear, especificamente $\lim_{k \to \infty} w(k; r)^{1/k} = r$. Antes deste trabalho, os melhores limites inferiores conhecidos para $w(k; r)$ foram derivados majoritariamente do Lema do Locais de Lovász ou de construções algébricas específicas, produzindo limites da forma $w(k; r) \geq r^{k-1}/(4k)$ ou, para um $r \geq 5$ fixo, limites da forma $(3r/3)^{(1-o(1))k}$. Os autores observam que, embora um resultado anterior de Hunter [20] tenha refutado a conjectura exponencial linear para $r \geq 5$, o caso para $r=3$ (e o comportamento geral para pequenos $r$ fixos) permanecia não resolvido.

Metodologia
Os autores desenvolvem uma construção probabilística inovadora para estabelecer limites inferiores para $w(k; r)$. A metodologia baseia-se em três componentes primários:

1. Conjuntos Densos Livres de Progressões em Grupos Cíclicos:
   Os autores constroem subconjuntos muito densos de grupos cíclicos $\mathbb{Z}_N$ que não contêm progressões aritméticas de $k$ termos (k-APs). Eles utilizam uma extensão da construção de Erdős-Turán (conjuntos de inteiros sem um dígito igual a $p-1$ na base $p$) adaptada para grupos cíclicos. Crucialmente, eles provam a existência de "conjuntos de impacto" (Lema 2.8) que são esparsos (densidade $\leq \epsilon$), mas que interceptam cada k-AP em um grupo com uma fração constante de seus elementos. Isso é alcançado selecionando classes de congruência aleatórias módulo um conjunto de primos.

2. Consequências do Lema do Locais de Lovász (LLL):
   O artigo emprega a versão simétrica do Lema do Locais de Lovász para demonstrar a existência de colorações onde nenhuma classe de cor contém uma fração "grande" de qualquer k-AP. Especificamente, o Corolário 3.3 estabelece que, para grupos de ordem $N$ sem pequenos fatores primos, é possível atribuir subconjuntos de cores aos vértices de tal forma que nenhuma k-AP seja monocromática ou quase monocromática.

3. Construções de Produtos Deslocados Aleatórios:
   A principal inovação técnica é uma construção refinada de "produto deslocado aleatório" (Lemmas 4.2 e 4.3). Diferente das colorações de produtos padrão que multiplicam o número de cores, este método permite que os autores combinem colorações de grupos menores em um grupo maior enquanto mantêm o número de cores fixo (ou aumentando-as de maneira controlada).

• Mecanismo: Dado uma coloração $c_1$ de $H_1$ e $c_2$ de $H_2$, a construção define uma coloração em $H_1 \times H_2$ deslocando independentemente as fibras da projeção sobre $H_2$ e permutando as cores com base na cor do elemento base em $H_1$.
• Processo Iterativo: Os autores iteram esta construção. Em cada etapa, eles combinam uma coloração de um grupo $Z_{n_{j-1}}$ com uma coloração de um grupo cíclico de ordem prima $Z_{q_j}$. A construção aumenta o tamanho do grupo por um fator exponencial em $k$, enquanto incorre em uma perda "duplo-exponencial" no parâmetro de densidade da classe de cor "boa". Ao equilibrar cuidadosamente esses parâmetros, o processo pode ser iterado aproximadamente $(\log^* k)/2$ vezes.

Principais Contribuições e Resultados

• Crescimento Super-exponencial para Três Cores:
  O resultado principal (Teorema 1) prova que, para $k$ suficientemente grande, o número de van der Waerden de três cores satisfaz:
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  Isso estabelece que $w(k; 3)$ cresce mais rápido do que qualquer função exponencial de $k$, refutando assim a conjectura de que $\lim_{k \to \infty} w(k; r)^{1/k} = r$ para $r \geq 3$.

• Limites Inferiores para Muitas Cores:
  O Teorema 2 fornece um limite inferior para o regime onde o número de cores $r$ é grande em relação a $k$ (especificamente $r \geq (\log k)^{3/\epsilon}$):
  $$w(k, r) \geq r^{(1-\epsilon)k \log k}$$
  Isso melhora os limites anteriores no regime de "muitas cores".

• Resolução do Problema de Erdős-Graham:
  Os autores abordam o número de van der Waerden canônico $H(k)$, definido como o menor $N$ tal que toda coloração de $[N]$ contém uma $k$-AP monocromática ou arco-íris (rainbow). Erdős e Graham conjecturaram se $H(k)^{1/k}/k \to \infty$. Usando seu limite inferior melhorado para $w(k; k-1)$, os autores provam (Teorema 3) que:
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  Isso confirma que $H(k)$ cresce super-exponencialmente, resolvendo o problema em aberto proposto por Erdős e Graham.

Significado
O artigo afirma que o crescimento dos números de van der Waerden para três ou mais cores é super-exponencial, um resultado que altera fundamentalmente a compreensão desses números combinatórios. O significado reside em:

1. Refutação da Conjectura Exponencial Linear: Ele demonstra definitivamente que $w(k; r)$ não se comporta como $r^k$ para $r \geq 3$.
2. Avanço Metodológico: A introdução da construção de "produto deslocado aleatório" permite a iteração de argumentos probabilísticos enquanto mantém um número fixo de cores, uma técnica que os autores notam ser mais eficiente do que as versões anteriores usadas para $r \geq 5$.
3. Teoria de Ramsey Canônica: Os resultados fornecem uma resolução forte para o problema de Erdős-Graham relativo aos números de van der Waerden canônicos, mostrando que mesmo permitindo progressões arco-íris, o $N$ necessário é vastamente maior do que os limites inferiores estabelecidos anteriormente.

Os autores observam que, embora suas técnicas sejam gerais, a aplicação específica aqui foca em estabelecer estes limites inferiores. Eles sugerem que estas construções podem ser aplicáveis para obter novos limites para outros números de Ramsey aritméticos, um tópico que pretendem explorar em uma nota complementar. O artigo não pretende determinar a taxa de crescimento exata ou fornecer limites superiores, mas estabelece um limite inferior significativamente mais forte do que o conhecido anteriormente.