Three-color van der Waerden numbers grow super-exponentially

技术摘要：三色范德瓦尔登数呈超指数级增长

问题陈述
本文研究了范德瓦尔登数 $w(k; r)$ 的增长率。该数被定义为：对于集合 $\{1, 2, \dots, N\}$ 的任何 $r$-着色，都包含一个单色的长度为 $k$ 的等差数列，其中 $N$ 为满足此条件的最小整数。虽然范德瓦尔登定理保证了这些数的存在性，但其精确的渐近增长率仍是一个基础性的开放问题。

从历史上看，$w(k; r)$ 的增长一直是激烈推测的主题。对于固定的 $r$，埃尔德什（Erdős）曾猜想 $w(k; 2)$ 是超指数增长的（即 $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$）。相反，其他猜想则建议了线性指数增长，具体为 $\lim_{k \to \infty} w(k; r)^{1/k} = r$。在此项工作之前，已知的 $w(k; r)$ 最优下界主要源于洛瓦兹局部引理（Lovász Local Lemma）或特定的代数构造，产生的界限形式为 $w(k; r) \geq r^{k-1}/(4k)$，或者对于固定的 $r \geq 5$，形式为 $(3r/3)^{(1-o(1))k}$。作者指出，尽管 Hunter [20] 的前人研究通过证明 $r \geq 5$ 时线性指数猜想不成立，但针对 $r=3$ 的情况（以及对于较小固定 $r$ 的一般行为）仍未得到解决。

方法论
作者开发了一种新型概率构造来建立 $w(k; r)$ 的下界。该方法依赖于三个主要组成部分：

1. 循环群中的稠密无等差数列集：
   作者构造了循环群 $\mathbb{Z}_N$ 中非常稠密的、不包含 $k$-项等差数列（k-APs）的子集。他们利用了埃尔德什-图兰（Erdős-Turán）构造（即在 $p$ 进制下不含数字 $p-1$ 的整数集合）的扩展，并将其应用于循环群。至关重要的是，他们证明了“命中集”（Hitting sets，引理 2.8）的存在，这些集合是稀疏的（密度 $\leq \epsilon$），但能与循环群中的每一个 $k$-AP 相交，且交集占其元素的常数比例。这是通过选择模一组素数的随机同余类来实现的。

2. 洛瓦兹局部引理（LLL）的后果：
   本文采用对称版本的洛瓦兹局部引理，以证明存在某种着色方案，使得没有任何一个颜色类包含任何 $k$-AP 的“大”比例。具体而言，推论 3.3 确立了对于阶数不含小素因子的群 $N$，可以将颜色子集分配给顶点，使得没有任何 $k$-AP 是单色的或近乎单色的。

3. 随机平移乘积构造：
   核心技术创新是精炼的“随机平移乘积”构造（引理 4.2 和 4.3）。不同于通过乘积增加颜色数量的标准乘积着色法，这种方法允许作者在保持颜色数量固定（或受控增加）的情况下，将较小群的着色组合进一个更大的群中。

   • 机制： 给定 $H_1$ 的着色 $c_1$ 和 $H_2$ 的着色 $c_2$，该构造通过独立地平移投影到 $H_2$ 的纤维，并基于基元素在 $H_1$ 中的颜色进行颜色置换，从而定义 $H_1 \times H_2$ 上的着色。
   • 迭代过程： 作者迭代了这一构造。在每一步中，他们将一个群 $Z_{n_{j-1}}$ 的着色与一个素数阶循环群 $Z_{q_j}$ 的着理结合起来。该构造使群的大小以关于 $k$ 的指数倍数增加，同时导致“好”颜色类的密度出现“双指数”损失。通过仔细平衡这些参数，该过程可以迭代大约 $(\log^* k)/2$ 次。

主要贡献与结果

• 三色的超指数增长：
  主要结果（定理 1）证明了对于足够大的 $k$，三色范德瓦尔登数满足：
  $$w(k; 3) > 2^{k(\log^* k)/4}$$
  这确立了 $w(k; 3)$ 的增长速度快于任何 $k$ 的指数函数，从而反驳了对于 $r \geq 3$ 时 $\lim_{k \to \infty} w(k; r)^{1/k} = r$ 的猜想。

• 多色的下界：
  定理 2 提供了当颜色数 $r$ 相对于 $k$ 较大时（具体为 $r \geq (\log k)^{3/\epsilon}$）的下界：
  $$w(k; r) \geq r^{(1-\epsilon)k \log k}$$
  这改进了在“多颜色”情形下的既有界限。

• 解决埃尔德什-格雷厄姆问题：
  作者探讨了正则范德瓦尔登数 $H(k)$，其定义为：任何对 $[N]$ 的着色都包含一个单色或彩虹（rainbow）$k$-AP 的最小 $N$。埃尔德什和格雷厄姆曾猜想 $H(k)^{1/k}/k \to \infty$。利用他们对 $w(k; k-1)$ 改进后的下界，作者证明（定理 3）了：
  $$H(k) \geq k^{(1-o(1))k \log k}$$
  这证实了 $H(k)$ 是超指数增长的，从而解决了埃尔德什和格雷厄姆提出的开放问题。

意义
本文声称，对于三种或更多颜色，范德瓦尔登数的增长是超指数级的，这一结果从根本上改变了对这些组合数的理解。其意义在于：

1. 反驳了线性指数猜想： 它明确表明对于 $r \geq 3$，$w(k; r)$ 的行为并不像 $r^k$ 那样。
2. 方法论的进步： “随机平移乘积”构造的引入，使得在保持固定颜色数量的同时迭代概率论证成为可能，作者指出这种技术比以往用于 $r \geq 5$ 的版本更为高效。
3. 正则 Ramsey 理论： 这些结果为正则范德瓦尔登数（canonical van der Waerden number）提供了强有力的解决，表明即使允许存在彩虹等差数列，所需的 $N$ 也远大于此前建立的下界。

作者指出，虽然他们的技术具有通用性，但本文的具体应用侧重于建立这些下界。他们建议，这些构造可能适用于获取其他算术 Ramsey 数的新界限，这是他们打算在随附笔记中探讨的主题。本文并不声称要确定精确的增长率或提供上界，而是建立了一个显著强于以往已知的下界。