九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

范德瓦尔登数 W(3,5)

《组合设计中的 50 个公开问题》 · 问题 26 专题综述

题面三色情形的长 5 等差数列阈值 W(3,5) 是多少?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

W(3,5):[1,N] 的 3-染色必含单色 5-AP 的最小 N。已知精确值谱系(双色侧见 25 号):W(3,3)=27, W(3,4)=293(Rabung–Lotts 1979 计算、后经 SAT 复核)。W(3,5):下界约 1700(显式 3-染色)、上界约万级(一般范德瓦尔登上界的粗估)——整个 «多色谱系» 除极小值外都未确定,「可计算但算不动」是共同命运。与之并行的 «广义谱»(W(4,k)、W(r,k) 的高维、以及混合间隔 AP)把地图越拉越大。

主要概念

多色的组合爆炸

每个 «无单色 k-AP 的 r-染色» 的数目随 r 指数增长:SAT 实例的解空间膨胀使 «不可满足性证明»(确定 W)远难于 «构造上界»(找到好染色)。W(3,4)=293 的两段式证明(显式 292 染色+293 不可满足)已经吃满当年的算力;W(3,5) 的 293→1700+ 的跨度意味着分支因子暴涨数个量级。

上界的理论侧

多色范德瓦尔登的一般上界来自 Szemerédi 定理的定量版(Gowers 2001):W(r,k) ≤ 22r2k+O(r) 型 «塔式» 巨数——对具体 (3,5) 毫无用处;«实用» 上界来自手工/计算机的组合证明(«分支–定界» 对 AP 族)。理论与计算的断层在多色侧更陡。

主要命题与证明

命题 1(W(3,3)=27,完整证明的骨架) [1,26] 存在无单色 3-AP 的 3-染色;[1,27] 任意 3-染色必含。证明是 «中心对称对» 的逐案核对(25 号命题 1 的三色版):27 时的 «中心 14 + 13 对» 的强约束树。

说明 这是多色侧唯一 «手算可关闭» 的精确值;293 的关闭已是机器时代。□

命题 2(W(3,4)=293;陈述) Rabung–Lotts(1979)给出显式 292-染色与 293 的穷举证明;现代 SAT 复核确认。证明结构与 W(2,6) 同型:构造+对称约化+不可满足关闭。

说明 292-染色具有 «近周期» 结构(三色分段的准规律模式)——«好染色是准周期的» 的经验事实横贯整个谱系,但目前没有理论解释。□

命题 3(W(3,5) 的现状;陈述) 下界:显式 3-染色达到约 1700(文献中的构造纪录);上界:组合证明给 «万级» 粗界。二者之间的鸿沟没有理论工具能合拢——W(3,5) 是 SAT 引擎的 «下一个登月»(比 W(2,7) 更陡)。

说明 对比 25 号:双色侧有 Berlekamp 型代数下界机器,三色侧连 «好的代数构造» 都稀缺——多色下界构造本身就是开放方向。□

进展与文献

Rabung–Lotts 1979 的 W(3,4);SAT 时代的复核与纪录表(Kouril 系);Gowers 2001;Landman–Robertson《Ramsey Theory on the Integers》的系统整理。开放核心:W(3,5) 本体;W(4,4) 等并谱值;«准周期最优染色» 的理论化;与 29 号 Hales–Jewett 数的 «高维 AP» 联动。

← 返回问题 26