Three-color van der Waerden numbers grow super-exponentially

Sintesi Tecnica: I numeri di van der Waerden a tre colori crescono in modo super-esponenziale

Enunciato del Problema
Il saggio affronta il tasso di crescita dei numeri di van der Waerden, denotati con $w(k; r)$. Questo numero è definito come il minimo intero $N$ tale che ogni colorazione con $r$ colori dell'insieme $\{1, 2, \dots, N\}$ contenga una progressione aritmetica monocromatica di lunghezza $k$. Sebbene l'esistenza di questi numeri sia garantita dal teorema di van der Waerden, la loro precisa crescita asintotica rimane un problema fondamentale aperto.

Storicamente, la crescita di $w(k; r)$ è stata oggetto di intense speculazioni. Per un $r$ fissato, Erdős ipotizzò che $w(k; 2)$ cresca in modo super-esponenziale (ovvero $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$). Al contrario, altre congetture suggerivano una crescita esponenziale lineare, specificamente $\lim_{k \to \infty} w(k; r)^{1/k} = r$. Prima di questo lavoro, i migliori limiti inferiori noti per $w(k; r)$ erano stati derivati principalmente dal Lemma di Lovász Local o da specifiche costruzioni algebriche, fornendo limiti della forma $w(k; r) \geq r^{k-1}/(4k)$ o, per un $r \geq 5$ fisso, limiti della forma $(3r/3)^{(1-o(1))k}$. Gli autori osservano che, sebbene un risultato precedente di Hunter [20] abbia smentito la congettura dell'esponenziale lineare per $r \geq 5$, il caso per $r=3$ (e il comportamento generale per piccoli $r$ fissi) rimaneva irrisolto.

Metodologia
Gli autori sviluppano una nuova costruzione probabilistica per stabilire limiti inferiori per $w(k; r)$. La metodologia si basa su tre componenti primarie:

1. Insiemi densi privi di progressioni in gruppi ciclici:
   Gli autori costruiscono sottoinsiemi molto densi di gruppi ciclici $\mathbb{Z}_N$ che non contengono progressioni aritmetiche di lunghezza $k$ ($k$-AP). Utilizzano un'estensione della costruzione di Erdős-Turán (insiemi di interi con nessuna cifra uguale a $p-1$ in base $p$) adattata ai gruppi ciclici. Fondamentalmente, dimostrano l'esistenza di "insiemi di impatto" (Lemma 2.8) che sono sparsi (densità $\leq \epsilon$) ma intersecano ogni $k$-AP in un gruppo ciclico con una frazione costante dei suoi elementi. Ciò si ottiene selezionando classi di congruenza casuali modulo un insieme di numeri primi.

2. Conseguenze del Lemma di Lovász Local (LLL):
   Il saggio impiega la versione simmetrica del Lemma di Lovász Local per dimostrare l'esistenza di colorazioni in cui nessuna classe di colore contiene una "grande" frazione di qualsiasi $k$-AP. Nello specifico, il Corollario 3.3 stabilisce che per gruppi di ordine $N$ senza piccoli fattori primi, è possibile assegnare sottoinsiemi di colori ai vertici in modo che nessuna $k$-AP sia monocromatica o quasi monocromatica.

3. Costruzioni di prodotti traslati casuali:
   L'innovazione tecnica centrale è una raffinata costruzione di "prodotto traslato casuale" (Lemmi 4.2 e 4.3). A differenza delle standard colorazioni a prodotto che moltiplicano il numero di colori, questo metodo permette agli autori di combinare le colorazioni di gruppi più piccoli in un gruppo più grande mantenendo il numero di colori fisso (o aumentandoli in modo controllato).

   • Meccanismo: Dato una colorazione $c_1$ di $H_1$ e $c_2$ di $H_2$, la costruzione definisce una colorazione su $H_1 \times H_2$ traslando indipendentemente le fibre della proiezione su $H_2$ e permutando i colori in base al colore dell'elemento di base in $H_1$.
   • Processo iterativo: Gli autori iterano questa costruzione. In ogni passaggio, combinano una colorazione di un gruppo $Z_{n_{j-1}}$ con una colorazione di un gruppo ciclico di ordine primo $Z_{q_j}$. La costruzione aumenta la dimensione del gruppo di un fattore esponenziale in $k$, subendo al contempo una perdita "doppia esponenziale" nel parametro di densità della classe di colore "buona". Bilanciando attentamente questi parametri, il processo può essere iterato circa $(\log^* k)/2$ volte.

Contributi Chiave e Risultati

• Crescita super-esponenziale per tre colori:
  Il risultato primario (Teorema 1) dimostra che per $k$ sufficientemente grande, il numero di van der Waerden a tre colori soddisfa:
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  Ciò stabilisce che $w(k; 3)$ cresce più velocemente di qualsiasi funzione esponenziale di $k$, smentendo la congettura che $\lim_{k \to \infty} w(k; r)^{1/k} = r$ per $r \geq 3$.

• Limiti inferiori per molti colori:
  Il Teorema 2 fornisce un limite inferiore per il regime in cui il numero di colori $r$ è grande rispetto a $k$ (specificamente $r \geq (\log k)^{3/\epsilon}$):
  $$w(k; r) \geq r^{(1-\epsilon)k \log k}$$
  Questo migliora i precedenti limiti nel regime di "molti colori".

• Risoluzione del Problema di Erdős-Graham:
  Gli autori affrontano il numero di van der Waerden canonico $H(k)$, definito come il minimo $N$ tale che ogni colorazione di $[N]$ contenga una $k$-AP monocromatica o arcobaleno. Erdős e Graham hanno ipotizzato se $H(k)^{1/k}/k \to \infty$. Utilizzando il loro migliorato limite inferiore su $w(k; k-1)$, gli autori dimostrano (Teorema 3) che:
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  Ciò conferma che $H(k)$ cresce in modo super-esponenziale, risolvendo il problema aperto posto da Erdős e Graham.

Significatività
Il saggio afferma che la crescita dei numeri di van der Waerden per tre o più colori è super-esponenziale, un risultato che altera fondamentalmente la comprensione di questi numeri combinatori. La significatività risiede in:

1. Smentita della congettura dell'esponenziale lineare: Dimostra definitivamente che $w(k; r)$ non si comporta come $r^k$ per $r \geq 3$.
2. Avanzamento metodologico: L'introduzione della costruzione di "prodotto traslato casuale" permette di iterare argomenti probabilistici mantenendo un numero fisso di colori, una tecnica che gli autori notano essere più efficiente rispetto alle versioni precedenti usate per $r \geq 5$.
3. Teoria Ramsey Canonica: I risultati forniscono una risoluzione forte al problema di Erdős-Graham riguardante i numeri di van der Waerden canonici, mostrando che anche quando si ammettono progressioni arcobaleno, l' $N$ richiesto è vastamente più grande dei limiti inferiori precedentemente stabiliti.

Gli autori notano che, sebbene le loro tecniche siano generali, l'applicazione specifica qui si concentra sull'établire questi limiti inferiori. Suggeriscono che queste costruzioni possano essere applicabili per ottenere nuovi limiti per altri numeri Ramsey aritmetici, un argomento che intendono esplorare in una nota complementare. Il saggio non pretende di determinare il tasso di crescita esatto o di fornire limiti superiori, ma stabilisce un limite inferiore significativamente più forte di quanto precedentemente noto.