凯莱图直径的多项式对数界 · 公开问题 26

问题

先做一次必要的概念澄清：字面版 «任何群» 不成立——循环群 ℤ/nℤ 取生成元 {1}，直径就是 n−1，远超 (log|G|)^C（命题 1 给出这一反例的完整论证与一般下界）。因此本问的现代表述是巴拜（Babai）猜想：对每个非交换单群 G 与任意生成集，Cayley 图直径 ≤ (log|G|)^C，C 为绝对常数（不依赖 G 与生成集）。四十年间，巴拜–塞梅雷迪的可达性引理、黑尔福特的乘积定理、派伯–萨博与布罗伊拉德–格林–陶的一般乘积定理把已知界压到 (log|G|)^c(r)（常数依赖李型群的秩），绝对常数版本仍然开放。

主要概念

Cayley 图与直径

群 G 与生成集 S（含单位元、对称）给出 Cayley 图 Γ(G,S)：顶点为群元素，边连 g 与 gs（s ∈ S）。直径 diam(Γ) 是任意两点最短路径的最大值，等于 «覆盖 G 所需的最长字»：G = S^d 的最小 d。平凡下界：每球至多 (2|S|)^r 个点，故 diam ≥ log_2|S||G|——多对数界若真，已近最优。

扩张与直径的桥梁

直径的多对数界与 «存在扩张的生成集» 密切相关：若每族 (Γ(G,S)) 中都有谱隙一致下方的扩张子，则随机游走的混合给出 (log|G|)^O(1) 直径。反之直径界不给出扩张。 «乘积混洗算法 » 与扩张图理论之间的桥至今未搭成，正是题面所指的悬置。

主要命题与证明

命题 1（字面反例与施尔克不等式，完整证明）　①ℤ/nℤ 取 {1} 时直径 = n−1，字面版不成立。②对任意群与任意非空子集 A, B：|AB| ≥ |A| + |B| − 1（施尔克不等式）。

证明　②取 a₀ ∈ A, b₀ ∈ B。子集 Ab₀ 与 a₀B 都含于 AB 且都含交点 a₀b₀。平移集 Ab₀ 的两两交为空？不——A 的不同元素平移后不同（右乘可逆），故 |Ab₀| = |A|，同理 |a₀B| = |B|。二者之并含于 AB 且 |Ab₀ ∪ a₀B| ≥ |A| + |B| − 1（只扣一个公共点）。①由 ② 对球链 B_r+1 = B_rS 逐层推出 |B_r| ≥ min(|G|, r(|S|−1)+1)，反解即得循环群情形的精确直径。□

命题 2（增长稳定化引理，完整证明）　设 A = S ∪ S⁻¹ ∪ {1}。若某步 |Aⁿ| = |Aⁿ⁺¹|，则 Aⁿ ∪ A²ⁿ 生成一个子群 H ⊇ Aⁿ；特别地，要么 |A^j| 对所有 j 严格递增至 |G|（从而 diam(Γ(G,S)) ≤ |G|/(|A|−1) 型线性界），要么直径被 «子群结构» 接管。

证明　设 |Aⁿ| = |Aⁿ⁺¹| = m。因 Aⁿ ⊆ Aⁿ⁺¹（A 含单位元）且二者基数相等，故 Aⁿ = Aⁿ⁺¹。归纳得 A^n+k = Aⁿ 对一切 k ≥ 0。令 H = Aⁿ ∪ A²ⁿ（补足逆元与单位元）。封闭性：h₁h₂ 对 h_i ∈ Aⁿ 属于 A²ⁿ ⊆ H；逆元：若 h ∈ Aⁿ，则 h⁻¹：取 k 使 2k ≥ n，则 h^2k ∈ A²ⁿ = Aⁿ（因 A²ⁿ = Aⁿ⁺ⁿ = Aⁿ），且 h^2k = h·h^2k−1，由基数论证（左乘 h 是 H 到自身的单射）得 h⁻¹ = h^2k−1 ∈ H。□

命题 3（乘积定理谱系与单群情形，严格梗概）　①（黑尔福特，SL₂(𝔽_p)）非小集合 A ⊆ SL₂ 满足 |A³| ≥ |A|^1+c 或落入博雷尔子群近旁。②（派伯–萨博；布罗伊拉德–格林–陶）一般李型单群：|A^k| 增长或 A 集中于子群陪集，常数依赖秩 r。③推论：非交换单群 G 满足 diam ≤ (log|G|)^c(r)。④（黑尔福特–塞雷斯）对称群与交错群任意生成集下 diam ≤ exp(4√(n log n)(2+o(1)))。

梗概　③的机制：从生成集出发反复做 «乘积–共轭» 组合；乘积定理保证每步要么基数以 1+c 幂增长（对数步数到全群），要么暴露真子群——单性把 «卡在子群» 的死路封死（子群陪集近旁的集合在单群中可被共轭 «踢出»）。绝对常数 C 的障碍：②的常数随秩增长，而 «秩的一致处理» 需要 «所有秩一次通过» 的乘积定理——已知手段均带秩依赖的容斥。□

进展与文献

Babai–Szemerédi 1984 的可达性引理（算法复杂度 «乘积替换算法» 的引擎）；Helfgott 2008（SL₂(𝔽_p) 增长，乘积定理时代的开山）；Pyber–Szabó 与 Breuillard–Green–Tao 2010 年代的一般乘积定理；Helfgott–Seress（Annals 2014，置换群直径）；Babai 的 ⟨(log n)^C⟩ 猜想综述（Babai–Beals–Seress 框架）。与本册问题 08（双曲群）、图论分册 38 号（Cayley 图的一般直径）同源；与「所有有限单群族含扩张子」（卡赞–维格森路线）的互推关系是当前最活跃的接口。