defect 定理的定量版 · 公开问题 20

问题

defect 定理（词组合学的基础工具，Lothaire 系）：若 n 个非空词 «不满足任何非平凡恒等关系» 的程度足够（精确表述：词集 X 是 «码» 的缺陷版本——若 X 不是码，则 X 的词可由 «至多 n−1 个词» 的码生成，n = |X|）。定量版问： «独立»（自由）因子个数与 «被生成词的长度» 之间的精确界——多少个独立因子能 «覆盖» 多长的词？Fine–Wilf 型的精细边值对特殊词类已知（ «最优常数» 版本），一般词类的精确常数（如 Fine–Wilf 界的最优性已证，但 «双变量推广» 未完）仍在打磨。

主要概念

码、defect 与独立性

词集 X 是码若 X* 中每个词的 X-分解唯一。defect 定理：|X| = n 且 X 非码 ⟹ 存在码 Y，|Y| ≤ n−1，X ⊆ Y*。机制：非码 ⟹ 有 «碰撞» u₁⋯u_k = v₁⋯v_ℓ（两种分解）；碰撞的 «最短公共超词» 的 «基础词» 把 X 的 «耦合对» 合并，每合并一次减少一个独立度。定量版的直觉： «n 个词生成了 «太长» 的自由词 ⟹ 它们必须有缺陷»—— «太长» 的阈值由 Fine–Wilf 定理给出。

Fine–Wilf 定理与双变量推广

Fine–Wilf（1965）：两个周期 p, q 的词若长 ≥ p+q−gcd(p,q) 且 «两个周期一致»，则同时具有周期 gcd(p,q)。界是最优的（存在长 p+q−gcd−1 的 «伪一致» 词）。双变量推广： «两个词 u, v 的 «交换关系» uv = vu 与 «幂关系» 的联合边值»—— «u^mvⁿ = vⁿu^m 型部分一致 ⟹ 完全一致» 的阈值问题，已知部分层（ «Lyndon–Schützenberger 定理»：⟨u,v ⟩ 非码 ⟺ u,v 是同一词的幂），一般 «部分一致» 的最优阈值开放。

主要命题与证明

命题 1（Lyndon–Schützenberger 二词定理；完整证明）　非空词 u, v：uv = vu ⟺ 存在词 t 与 a,b ≥ 0 使 u = t^a, v = t^b。等价地，⟨u,v ⟩ 非码 ⟺ 二词交换。

证明　（⟸）显然。（⟹）对 |u|+|v| 归纳。uv = vu：不妨 |u| ≤ |v|。比较 uv 与 vu 的前 |u| 位：u = v 的前 |u| 位（若 |u| ≤ |v|：等式右边 vu 的前 |u| 位是 v 的前 |u| 位）⟹ u 是 v 的前缀。写 v = uw。代入：uwu = uuw ⟹ 消去首 u（自由独异点左消去）：wu = uw。|w|+|u| < |u|+|v|，归纳得 w = t^c, u = t^a ⟹ v = uw = t^a+c。□

命题 2（Fine–Wilf 定理及最优性；完整证明）　词 w 有周期 p 与 q（即 w(i) = w(i+p) 对一切合法 i），且 |w| ≥ p+q−gcd(p,q)，则 w 有周期 gcd(p,q)。界最优：存在长 p+q−gcd(p,q)−1 的双周期词无 gcd 周期。

证明　（机制）设 d = gcd(p,q)。由 w(i) = w(i+p) = w(i+q) 及其 «传递闭包»：w(i) = w(i+ap+bq) 对一切 «路径留在 |w| 内» 的组合。Bézout：ap+bq 遍历 d 的倍数；«路径» 的连通性论证：位置 i 与 i+d 之间可构造 «步长 ±p, ±q» 的路径（整数组合 i′−i = ap+bq = kd，且可选取路径使中间位置都在 [i−(min p,q), i+…] 的 «窗口» 内——窗口宽度条件正是 |w| ≥ p+q−d 的作用：任何 i,i+d ≤ |w| 时，存在先加 q 减 p（或反）的 «蛇形» 路径不越界（这是证明的技术核，原文给出蛇形构造）。最优性：取 p, q 互素，词 = «两条失配周期线的最短公共延长»（显式构造：长 p+q−1 的词 w(i) = i mod p 与 i mod q 的 «兼容延长»），验证无周期 gcd = 1 的 «常值性»。□

命题 3（defect 定理与定量开放层；陈述）　（i）defect 定理：非码的 n 词集可由 ≤ n−1 词的码生成（Lothaire 系，证明用 «碰撞合并» 的归纳）。（ii）定量层的已知： «n 词自由 ⟹ 它们的 «积» 不超过某长度» 型的双变量阈值（ «部分 Fine–Wilf»）对特殊结构（幂关系、交换关系）已知最优；一般 «k 个词的部分一致 ⟹ 完全独立» 的最优常数开放。（iii）与 15 号（模式可避）、48 号（自动性）的接口：defect 定理是 «词的代数独立性» 的唯一通用工具，其定量缺口传导到依赖它的所有领域。

现状说明　 «部分一致» 的困难：Fine–Wilf 的 «单变量» 蛇形路径在双变量（两个不同的 «错位» 词）情形没有已知的类似物；已知的最优常数都是 «逐对» 的（ «u^m 与 vⁿ 的部分一致阈值»）， «联合» 阈值的结构未明。□

进展与文献

Lothaire《Combinatorics on Words》的 defect 章节；Fine–Wilf（1965）；Lyndon–Schützenberger《The equation a^M = b^Nc^P in a free semigroup》（1962）；Shur 与 Karhumäki 的词组合学综述。开放核心：双变量及一般 «部分一致» 的最优阈值；defect 定理的 «最优缺陷» 版本（每次合并减 1 是否最优）；与码论（17 号）的定量接口。