问题
[k]N = {1,…,k}N 是 k 字母、N 维的离散立方。组合线(combinatorial line):选一部分坐标 «固定»、其余坐标 «联动»——联动坐标同时取 1,2,…,k(可加 «通配» 变换)。Hales–Jewett 数 HJ(k,r):最小 N 使 [k]N 的任意 r-染色含单色组合线。Hales–Jewett 定理(1963)保证存在;它是拉姆齐理论的 «最抽象主干»——范德瓦尔登定理是它取 «数字和» 后的影子。已知小值:HJ(2,n)(tic-tac-toe 族)、HJ(3,2) 等已算;HJ(3,3) 及以上完全开。Polymath 曾攻 HJ(2,6) 等相关数;«HJ 数的增长» 是与 Graham 数比肩的 « tower» 之谜。
主要概念
组合线 vs 几何线
几何直线(tic-tac-toe 的线)只是组合线的特例:组合线允许 «联动坐标的任意重排»(如坐标集 {1,3} 联动且 x1=4−x3 型 «反向联动»)。«反向» 使组合线族比几何线族大得多——这正是 HJ 数 «巨大» 的原因:染色要躲的线太多。HJ 定理的 Shell–鸽笼归纳证明给出 «tower 级» 上界;Shelah 的 «space derandomization» 与 Polymath 的改进把它压到 «towers of towers» 级——但真实增长率(是否 «仅» tower)未知。
与范德瓦尔登的关系
映射 ω(词) = Σ(字母−1)k坐标 把组合线映成(广义)等差数列的 «数字进位» 影子:HJ(k,r) 的上界给出 W(r,k) 的上界(反向不成立)——范德瓦尔登定理的 «组合母体»。
主要命题与证明
命题 1(Hales–Jewett 定理的鸽笼归纳骨架,完整推导) HJ(k,r) ≤ r-层 tower(归纳定义:HJ(k,r) ≤ k-tower of HJ(k−1,r)-型递归)。
推导 对 k 归纳。k=2:HJ(2,r) = «tic-tac-toe»:由 «对角线» 论证 HJ(2,r) ≤ r·2r 型(Graham–Rothschild 的精细版)。归纳步:设 M = HJ(k−1,rk)(用 «色数幂» 换 «字母减一»)。把 [k]N 按 «最后若干坐标» 切成 k 层片:每个 «切片» 是 [k−1]M 的拷贝。给每个 «切片-位置» 记 «该位置在 k 个层片上的色向量» ∈ [r]k——共 rk 种,由归纳假设存在 «色向量单色» 的组合线(在切片坐标上);该 «切片级组合线» 联动位置上,k 个层片的色向量逐一 «横向» 展开:要么 «横向» 已单色(得真正的单色组合线),要么 «横向» 色向量相同 ⟹ 在 «层片方向» 上联动得单色线。两条 «出口» 必居其一(鸽笼的 «同为或全异» 分叉)。□
命题 2(HJ(2,n) 与 tic-tac-toe;陈述) k=2 的组合线退化为 «两点联动对»,其谱系(«n 维 tic-tac-toe» 数)由 Polymath 的 Hales–Jewett 项目对小值部分标定;k=3、r=2 的首值(3×3 棋盘的全对角线版)亦已算出。它们是 «HJ 谱» 仅有的已标定区域——每往上一格都是新的计算工程。
说明 已标定值的证明结构与拉姆齐型数一致:显式染色(下界)+约束传播关闭(上界);组合线族比几何线族大得多(«反向联动» 线),使约束传播更快但搜索空间更胖。□
命题 3(Shelah 的上界改进,1988;陈述) Shelah 的 «空间去随机化» 把 Hales–Jewett 的原始 tower 上界压到 «少一层 tower»;Polymath(2010s)进一步给出 HJ(k,r) 的显式(但仍 tower 级)界。下界侧只有 «低维构造»,真实增长率完全未知。
说明 «tower 是否必要» 是本问题的深层形态:组合线族太大,目前没有 «多项式型» 下界构造与 «次 tower» 上界的会合迹象。□
进展与文献
Hales–Jewett 1963;Shelah 1988;Graham–Rothschild–Spencer《Ramsey Theory》的 HJ 章;Polymath 的 HJ 项目公开记录;Tao 的博客级推导(广为引用的教本)。开放核心:HJ(3,3);«次 tower» 上界的存在性;HJ 数与 «多维范德瓦尔登»(Gallai 定理)的定量关系。