问题
舒尔数 S(r)(本文取 «最大可染色» 口径):[1,S(r)] 存在 r-染色不含单色解 x+y=z(x,y 可相同),而 [1,S(r)+1] 强制出现。已知:S(1)=1, S(2)=4, S(3)=13, S(4)=44(Abbott–Hanson),S(5)=160(Heule 2017,SAT 求解器万核月余)。S(6):下界 536(显式 6-染色)与指数型上界之间——SAT 工具链是这一族的当代引擎,而 6-色的组合爆炸使 «下一个精确值» 的代价比 W(2,7) 更重。舒尔定理的一般上界与 «舒尔数与拉姆齐数的指数关系» 是理论侧的骨架。
主要概念
从费马到舒尔
舒尔 1916 年证明:对每个 r 存在 N 使 r-染色的 [1,N] 必含单色 x+y=z——动机是证明 «费马方程 xn+yn=zn 的 «素因子» 结构在模意义下的单色性»。证明机器:«r! 的倍数链» 递归——色类的 «和集» 论证给出 «有限 versions of 拉姆齐» 的第一个定理(先于拉姆齐 1930)。
SAT 时代的精确值
每个 «无单色和的 r-染色» 是 CSP 实例;S(5)=160 的证明是 «构造 159-染色 + 160 不可满足»:对称约化+冲突驱动学习+万核集群月余。经验规律(同 25、26 号):显式染色呈 «准周期» 结构,而不可满足证明的难度随色数指数膨胀。
主要命题与证明
命题 1(S(2)=4,完整证明) [1,4] 存在无单色和的 2-染色;[1,5] 的任何 2-染色必含单色 x+y=z。
证明 [1,4] 的染色:红 {1,4}、蓝 {2,3}。红类:1+1=2∉红、1+4=5 出界、4+4=8 出界 ✓;蓝类:2+2=4∉蓝、2+3=5 出界、3+3=6 出界 ✓。[1,5] 强制:设染色无单色和。1 与 2 异色(1+1=2)——设 1 红、2 蓝。2+2=4 ⟹ 4 红。1+4=5 ⟹ 5 蓝。考察 3:若 3 红,则 1+3=4 是 «红 红 红» 单色;若 3 蓝,则 2+3=5 是 «蓝 蓝 蓝» 单色——两支皆矛盾。□
命题 2(舒尔定理的一般上界,1916;陈述+机制) S(r) ≤ ⌊e r!⌋ 型(舒尔的原始递归:以 «色类的和链» 论证)。现代改进(Abbott–Hanson、Salehi 等)给出更细的递归界;下界侧 S(r) > 3r 型构造(指数)与上界 «阶乘» 之间的指数鸿沟是理论侧主缺口。
机制 舒尔的递归:r-染色取 «最大色类» C,其 «差集» 论证给出 (r−1)-色子结构——«递归掉一层色 ⟹ 规模乘一个因子»,累积成阶乘型上界。□
命题 3(S(5)=160 的计算证明结构,Heule 2017;陈述) 显式 159-染色+160 不可满足:把染色约束化为 SAT(每点变量、每 «和三元组» 子句),用立方体式分治(cube-and-conquer)在约 2 万核集群上运行月余关闭。这是 SAT 引擎在 «和型拉姆齐» 上的旗舰战绩。
说明 S(6) 的现状:下界 536 与 «阶乘型» 理论上界之间天堑;cube-and-conquer 的规模预估使 «万核» 变 «百万核» ——方法论的边际递减已经显现。□
进展与文献
Schur 1916;Abbott–Hanson–Toft 的经典界;Heule《Schur Number Five》(2017/18);SAT 与拉姆齐数的综合综述(Rado 数侧)。开放核心:S(6)(及 «SAT 时代» 的下一个精确值);舒尔数的指数常数;与拉姆齐数 R(3,…,3) 的 «指数关系» 精确化(S(r) 与 «图拉姆齐» 的已知连接是 «弱界»)。