范德瓦尔登数 W(2,7) · 公开问题 25

问题

范德瓦尔登数 W(r,k)：把 [1,N] r-染色，必含长 k 的单色等差数列的最小 N。范德瓦尔登定理（1927）保证存在。双色长 7：W(2,7)。已知精确值：W(2,3)=9, W(2,4)=35, W(2,5)=178, W(2,6)=1132（Kouril 2008）。W(2,7) 的下界 ~3703（显式 2-染色）与 «上界数十万» 之间是纯算力鸿沟——它是 «可计算但算不动» 家族的头名。更深处，一般 W(2,k) 的增长指数常数（介于 2^k 型下界与 2^k² 型上界之间，Graham 的百年之争）同样悬置。

主要概念

精确值的攻坚引擎

每个 «N 无单色 k-AP 的 2-染色» 是一个 SAT/CSP 实例：变量 x_i ∈ {0,1}，子句 «每个 k-AP 不同色»。W(2,6)=1132 的证明结构：①构造 1131 的显式染色（机器找到的 «almost-periodic» 模式）；②证明 1132 的不可满足——用对称性剪枝（«平移–反射» 群作用压缩搜索树）＋加权单位传播。SAT 工具链（冲突驱动学习）是 2000 年代以来的引擎，W(2,7) 需要把搜索空间再压数十个量级。

渐近线的两条桅杆

下界（构造侧）：Berlekamp 的代数构造给 W(2,k) > k·2^k−1 型；上界（Szemerédi 定理的定量版，Gowers 2001）：W(2,k) ≤ 2^{2^k+O(1)} 型 «双塔»——«指数常数» 的两端相差整整一层塔，而 «真实底数是否为 2»（即 W(2,k) ≈ 2^k+o(k)）完全未知。

主要命题与证明

命题 1（W(2,3)=9，核对骨架）　任给 [1,9] 的 2-染色必含单色 3-AP，且 [1,8] 存在不含单色 3-AP 的染色。

说明　下例：[1,8] 的染色 00101101 逐条核对全部 3-AP（1,2,3 起步的六条连续 AP 与三条跨度 2、两条跨度 3 的 AP）均双色。上界的关闭是有限核对：过中心 5 的四条 AP (1,5,9),(2,5,8),(3,5,7),(4,5,6) 与跨度 1–3 的其余 AP 联立——设 1 红：若 9 红 ⟹ 5 蓝 ⟹ (2,5,8),(3,5,7),(4,5,6) 各强迫 «至多一红»；再入 (1,2,3) 与 (7,8,9) 的两端约束，逐支核对（范德瓦尔登 1927 年原始手算的规模）每个分支都逼出 «某点须两色» 的矛盾；1、9 异色的分支同法。现代表述可用 SAT 一分钟复核，手工树约两百余节点。□

命题 2（Berlekamp 下界，1968；陈述＋机制）　对素数 p，存在 [1, p²−1]（或 (p+1) 相关区间）的 2-染色无单色 p 长 AP：用 𝔽_p 的二次剩余特征染色 𝔽_p² 的 «斜率» 结构。它给出 W(2,k) ≥ 约 2^k 型下界的 «代数构造» 样板。

机制　有限域 AP 的 «斜率» 分解：染色 «点 (x,x²) 的投影»，任何 p-AP 必跨 «两条二次曲线»，由 «二次型在直线上取值零点数 ≤ 2» 的代数事实保证双色性。□

命题 3（W(2,6)=1132 的计算证明结构，Kouril–Manders 2008/09；陈述）　①显式 1131-染色（由 «分层构造» + 局部搜索）；②1132 不可满足：把 «无单色 6-AP» 的染色约束化为加权 SAT，用 «对称约化»（剔除平移等价）与冲突驱动求解器在大规模集群上关闭搜索树。这是 SAT 引擎在拉姆齐型数上的旗舰战绩。

说明　W(2,7) 的难点不是方法缺失而是规模：搜索空间随 N 指数、对称约化的增益递减——«算法改进 × 算力 × 新剪枝» 的三维缺口。□

进展与文献

范德瓦尔登 1927；Berlekamp 1968 的构造下界；Rabung–Lotts 的早期精确值；Kouril–Manders 2008/09 的 W(2,6)；Gowers 2001 的 Szemerédi 定量上界；Shkredov 的现代改进。开放核心：W(2,7)（下界 3703 与数百上万上界之间）；W(2,k) 的渐近底数；«模周期» 构造是否渐近最优。