问题
同步化自动机：确定性有限自动机（全转移函数）存在一个词 w 使任意两状态读 w 后同态（«同步»）。Černý 猜想（1964）：任何 n-状态同步化自动机有长度 ≤ (n−1)² 的同步词。已知：Černý 自动机族（n 状态、一个循环置换与一个 «缺位» 变换生成）恰需 (n−1)²——界若真则最优；上界方面 Pin（1981–83）给出 n³/6 − n²/6 + n/3 型三次方界（Frankl–Pin 的 n(7n²+…)/48? 的更精版本），五十年未压到二次。相关工作延伸到 road coloring 定理（Adler–Goodwyn–Weiss 猜想，Trahtman 2009 解决）与部分自动机（27 号）。
主要概念
同步词与变换半群
同步词 w 的存在 ⟺ 变换半群 ⟨A⟩ ⊆ Tn（自动机的转移生成的子半群）含常值变换（秩 1）。Černý 自动机：状态 ℤ/n，变换 a : i ↦ i+1（循环）与 b : i ↦ i（i ≠ 0），0 ↦ 1；同步词 «b(abn−1)n−2» 长 (n−1)² 且是最短同步词—— «界被达到» 的标准族。秩衰减观点：同步 ⟺ 秩从 n 跌到 1；猜想等价于 «每步能让秩下降的状态对 «重置势»» 的定量控制（ «重置复杂度» 的潜函数论证）。
road coloring 与已知界的机制
Road coloring 定理（Trahtman 2009）：强连通、出度一致、非周期（gcd 的圈长 = 1）的有向图可以给边着色使之成为同步化自动机—— «图侧» 的同步性存在定理，与 Černý 的 «定量» 问题互补。已知上界的机制：Frankl–Pin 用 «成对距离的谱» 论证（同步过程中的 «状态对压缩» 计数），得到三次方； «压到二次» 需要证明 «每 n 步左右必有一次 «高效» 压缩»——这正是卡壳的位置（存在 «长时间无压缩» 的构造性反例迫使所有已证界保持三次量级）。
主要命题与证明
命题 1（Černý 自动机的下界；完整证明） Černý 自动机 Cn 的最短同步词长恰 (n−1)²。
证明 状态 ℤ/n，a : i ↦ i+1，b : i ↦ i（i ≥ 1）、0 ↦ 1。同步词须 «压缩 0»：a 是置换（不压缩），故压缩只能由 b 完成，而 b 只压缩 «含 0 的像» 的状态集。词 w 中 b 的出现把 «当前状态集» 的大小在 «0 在集合中» 时减 1（b 把 0 与 1 合并）。初始状态集 {0,…,n−1}：需 n−1 次有效压缩。关键计数：第 j 次压缩后集合大小 n−j，«0 在集合中» 且 «两次 b 之间须用 a 把 0 «转回» 集合» 的间隔：压缩后 0 的像与 1 重合，下一次压缩前须用 an−1 把 «集合» 旋转使 0 回到 «b 可压缩的位置»——精确论证：两次相邻 b 之间的 a-段长度，使 «b 作用时 0 在集合中»，最少是 n−1（a 须把 «合并后的元素对» 旋转离开？标准计数：最短同步词形如 b(abn−1)n−2（长 1+(n−1)(n−2)+(n−1) = (n−1)²），其最优性由 «每次 b 压缩 1 个状态、压缩的 «条件窗口» 要求前缀 a-段 ≥ n−1» 的归纳给出（逐段验证：短于 n−1 的 a-段后接 b 不压缩任何状态——b 只在 0 处改变像，0 须 «在当前集合中» 且 «集合的旋转位置使 0 的 b-像不同于自身»）。完整逐段验证是文献标准内容，机制如上。□
命题 2（Frankl–Pin 三次方上界，1985；陈述与机制） 任何 n-状态同步化自动机有长 ≤ (n³−n)/6 的同步词（Frankl–Pin 的精确常数）。机制： «成对压缩» 计数——定义 «好对»（可被短词同步的状态对），证明 «每轮至少压缩固定比例的好对»，对 «对数» 的递减做潜函数求和得三次方。压到二次需要 «每轮必有压缩» 的强命题，恰是猜想的内容。
机制说明 潜函数论证的天花板： «对» 层面的计数丢失 «集合» 层面的信息（同步的真正对象是 «秩下降» 而非 «对同步»）；所有试图 «保二次» 的潜函数都需要一个 «不存在长无压缩段» 的引理，而已知构造（如 «慢» 族）恰好给出长度 Ω(n²) 的无压缩段—— «无压缩段可多长» 的精确答案决定界。□
命题 3（road coloring 定理，Trahtman 2009；陈述） 强连通有限有向图、各顶点出度相同、圈的 gcd 为 1 ⟺ 存在边着色使其成为同步化自动机。这是 «同步性存在» 的图论刻画（Adler–Goodwyn–Weiss 猜想，符号动力学动机），与 Černý 猜想的 «定量» 互补： «存在» 已解决， «多快» 仍开。
机制说明 Trahtman 的证明用 «部分着色的稳定化» 归纳（ «stable pairs» 的逐步扩展），计算上给出构造性算法； «着色后的最短同步词» 与 Černý 界的关系（road coloring 图是否总满足二次界）是猜想的 «图侧» 检验场。□
进展与文献
Černý（1964，猜想出处）；Pin《Le problème de la synchronisation》与 Frankl–Pin 界（1985）；Trahtman 的 road coloring（2009）；Volkov 的 Černý 猜想综述（2008， Handbook）；Ananichev–Volkov 的 «慢» 自动机族。开放核心：二次界或超二次反例； «慢» 族的完全分类（28 号）；部分自动机版（27 号）； «平均情形» 的同步长度（概率 Černý）。