结果族 099：The sharp exponential scale of edit-distance distortion · 学科：Convex and metric geometry · 验证状态：暂无形式化证明，请以社区核验为准
把”廉价平移”编进一棵家谱树：每层配一批互不相同的素数当周期，叶子放二进制单词。整层一起挪一格很便宜（删一行、插一行），但想单独挪动一个”家族成员”，素数互不整除的算术保证藏不住——任何对齐方式都会暴露位移。这棵树每深一层，词长只按平方增长，失真却按幂次往上翻。两条互相独立的树构造，都把 @@M@@\ell_1@@ 失真逼到指数级。
关键词卡片
@@M@@\ell_1@@ 距离拆成割之和，再用傅里叶展开与 Parseval 分析平均位移。@@M@@d@@，都有一组公共长度的二进制词。看个具体例子
“数字版定理”：深度 @@M@@k@@ 的树给出失真 @@M@@\ge(k/4)^k@@（构造一）或 @@M@@\ge(\gamma k)^k/@@常数（构造二），而词长对数只有 @@M@@O(k^2\log k)@@；取 @@M@@k\approx a\sqrt{\log d/\log\log d}@@ 平衡两式，词长不超过 @@M@@d@@、失真达到 @@M@@\exp(\Omega(\sqrt{\log d\log\log d}))@@。附录还独立证明了对单一指定长度的常数失真二元转换（因子 804），不过主下界并不需要它。
为什么值得关心
与姊妹篇的一致上嵌入定理合并，@@M@@\log E_\Sigma(d)@@ 的阶被钉死在 @@M@@\sqrt{\log d\log\log d}@@——编辑距离的 @@M@@\ell_1@@ 失真问题就此定阶。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的家谱树把”廉价平移”组织起来：每层配一批互不相同的素数当周期，叶子放二进制词。整层一起挪一格是廉价动作——删一行、插一行；单独挪动一个”家族成员”却藏不住，素数互不整除的算术保证任何对齐方式都会暴露位移。对象是”一棵带素数周期的树＋叶上的词”，操作是”对比廉价的整体平移与昂贵的单独位移”。
第二级台阶
用本科术语定形。带标签行指由若干两两不相交字母表的块按固定顺序拼成的行，标签记录子指标而非行指标，专门对付任意对齐；周期按素数嵌套，一个子节点的周期等于父节点周期乘一个新素数，状态群是各周期剩余类的直积；分析侧把 ℓ1 距离分解为割的非负组合，再用 Parseval 恒等式把平均位移写成傅里叶系数的加权和。失真仍是嵌入后两个方向拉伸比之积。
第三级台阶
二元下界定理的陈述：对每个足够大的 d，存在公共长度 n≤d 的有限二进制词集，其编辑距离度量嵌入 ℓ1 的失真至少 exp(c√(log d·log log d))。两条独立路线都在树深 k 处给出 k log k 阶的失真对数与 k²log k 阶的词长对数，平衡后覆盖每个大 d 而非某个子序列——这是”等长见证、全量覆盖”的关键假设兑现处。证明的门槛在傅里叶侧：逃过廉价行移检测的特征必须激活至少 k^k 片叶，其权重被单叶代价压垮。与姊妹篇的一致上嵌入定理合并，log E_Σ(d) 的阶被钉死在 √(log d·log log d)；附录另有一个主定理并不需要的定长二元转换（因子 804）。
本文用两条互相独立的”树构造”证明：对每个足够大的 @@M@@d@@ 都存在长度不超过 @@M@@d@@ 的等长二进制词有限集，其编辑距离度量嵌入 @@M@@\ell_1@@ 的失真至少 @@M@@\exp(c\sqrt{\log d\,\log\log d})@@，与姊妹篇上界合并即得一致的两面指数阶。
编辑距离 @@M@@\ED(x,y)@@ 是把一个词改成另一个词所需插入、删除、替换的最少次数。插入或删除会改变其后所有符号的位置，因此一个很长的区间能以极小的编辑代价整体平移——”保持顺序”与”廉价平移”之间的张力正是嵌入问题的症结。下界方向此前最好的结果是 Krauthgamer–Rabani（2009）的 @@M@@\Omega(\log d)@@，与 Ostrovsky–Rabani（2007）的上界 @@M@@\exp(O(\sqrt{\log n\log\log n}))@@ 之间隔着巨大空隙；方法上，Khot–Naor 的布尔噪声敏感度与 Krauthgamer–Rabani 的比特翻转—循环移位影响不等式是本文割（cut）与平移论证的前身。本文补齐下界：用树把”廉价平移”与”任何对齐都藏不住的位移”组织在一起。
二元下界定理：存在绝对常数 @@M@@c>0@@ 与 @@M@@d_0@@，使得对每个 @@M@@d\ge d_0@@，都存在整数 @@M@@n\le d@@ 与有限集 @@M@@\mathcal W\subseteq\{0,1\}^n@@（@@M@@|\mathcal W|\ge2@@），其 @@M@@\ell_1@@ 失真 @@M@@c_1(\mathcal W,\ED)\ge\exp(c\sqrt{\log d\,\log\log d})@@；见证词全部等长。在树深 @@M@@k@@ 处，每个构造给出 @@M@@k\log k@@ 阶的失真对数与 @@M@@k^2\log k@@ 阶的词长对数，两个尺度平衡后覆盖每个足够大的 @@M@@d@@，而不只是某个子序列。附录还独立证明了对单一指定长度 @@M@@M@@ 的常数失真二元转换（块宽 @@M@@M^2@@、绝对因子 @@M@@804@@），但主下界并不需要它。推论：与姊妹篇的一致上嵌入定理合并，得 @@M@@\log E_\Sigma(d)=\Theta(\sqrt{\log d\,\log\log d})@@，常数对一切至少二元的有限字母表一致。
两条路线共享四件工具。最关键的是”带标签行”对齐引理：每行由来自若干两两不相交字母表的块按固定顺序拼成，叶标签保持的是子指标而非行指标。于是未分裂的源行因子词分离而损失符号；分裂的源行在两个相邻匹配之间于目标侧留下一整段不匹配区间，且不同源行所亏欠的区间互不重叠——”任意两行都分离”由此确定性地升级为”整词分离”，全程不假设行边界对齐。其余三件是 @@M@@\ell_1@@ 距离的割分解、Erdős 式中心二项系数的素数供给引理、以及前缀 110 的短定界符二元码（宽 @@M@@O(k\log k)@@，失真只损常数倍宽度）。
构造一是嵌套周期的有限树。深度 @@M@@k@@ 的满 @@M@@m@@ 叉树（@@M@@m=20k@@）每层分配 @@M@@[k^4,k^5]@@ 内的互异素数，周期嵌套 @@M@@Q_{vi}=Q_v\,p_{j,i}@@，状态群为 @@M@@A=\prod_u\mathbb Z/Q_u@@。行推进向量 @@M@@u_v=\sum_i w_{vi}@@ 廉价：平移后两个行表共享 @@M@@T-s@@ 行，删 @@M@@s@@ 行插 @@M@@s@@ 行即可；而 @@M@@w_v=R_vu_v@@（周期恰为 @@M@@Q_v@@）在任意状态都分离——若某对行的相对位移在超过一半的子处归零，则须有 @@M@@m/2@@ 个互异素数整除 @@M@@|a'-a|<T@@，与素数大小矛盾。分析侧先把 @@M@@\ell_1@@ 距离化为割的非负组合，用 Parseval 得平均位移的傅里叶恒等式；在某节点活跃但活跃子少于 @@M@@k@@ 个的特征，其 @@M@@\chi(u_v)@@ 是低阶单位根，一段廉价行移的平均就能检测它；逃过所有检测的特征必须在每个活跃节点有至少 @@M@@k@@ 个活跃子，从而激活至少 @@M@@k^k@@ 片叶，其总权重被单叶代价压至 @@M@@M/(2k^k)@@。合起来得根方向平均位移 @@M@@\le C_1Mk^{-k}@@，与逐点分离 @@M@@4^{-k}M/D@@ 相除得失真 @@M@@D\ge C_1^{-1}(k/4)^k@@。
构造二是圆相位树：叶记录量化的圆（circle）相位，内部节点的子分成 @@M@@16k@@ 组，每组配 @@M@@[k^2,k^3]@@ 内的素数并随机取剩余类，系数设计保证各组算术隔离。核心是”好位移”（good shift）的递归定义与概率论证：对每个固定合格位移，随机数据以至少 @@M@@9/10@@ 的概率使其在节点处好——对每个行剩余类至少 @@M@@m/64@@ 个子好；只需对根半转 @@M@@t=1/2@@ 取一次随机实现，任意基相位下的分离 @@M@@\gamma^kN@@（@@M@@\gamma=1/128@@）由对齐引理确定性地导出。分析侧的环面检测不等式设三道关卡：微旋转检测过大的整数频率和；有理行移检测失败的素同余；两关都过时，可除性迫使每个非零频率和继续穿过至少 @@M@@k@@ 个子，最终激活至少 @@M@@k^k@@ 片叶，被单叶平均以系数 @@M@@2k^{-k}@@ 压制，得 @@M@@D\ge(\gamma k)^k/(2C'B)@@。两条路线都取 @@M@@k\approx a\sqrt{\log d/\log\log d}@@，使词长不超过 @@M@@d@@ 而失真达到目标指数。
本文主结果暂无形式化证明。两条下界路线自足且互不依赖，也不依赖姊妹篇；上界直接引用圆构造姊妹稿的一致上嵌入定理，二者拼成一致双侧界，与主文构造形成第三条独立印证。按 OpenAI 官方声明，未经形式化的结果可能存在问题，请以社区核验为准。
问 1：证明里最要害、最脆弱的一步是什么？
答：带标签行对齐引理与傅里叶逃逸分析的焊点。前者把”任意两行分离”升级为”整词分离”——未分裂的源行因子词分离而损失符号，分裂的源行留下互不重叠的不匹配区间，全程不假设行边界对齐；后者断言逃过廉价行移检测的特征必须激活至少 k^k 片叶、权重被单叶代价压至 k^{-k} 量级。任一端松动，(k/4)^k 的失真即不成立。
问 2：为什么造两棵树，一棵不够吗？
| 答：机制冗余。有限树的分离论证在有限群上是确定性的（互异素数整除 | a′−a | <T 的计数矛盾）；圆相位树只对根半转这个固定位移做一次概率论证（好位移概率至少 9/10），再用对齐引理确定性地导出一切基相位的分离。两棵树的素数区间与检测关卡都不同，一条有漏洞另一条独立成立。 |
问 3：与 Khot–Naor、Krauthgamer–Rabani 相比新意何在？
答：前辈方法是布尔噪声敏感度与”比特翻转—循环移位”影响不等式，本文继承为割分解加平移的傅里叶估计，新组织是树：每层把廉价行移与藏不住的位移嵌套一次，深度 k 即得 k log k 阶失真对数。结果上从 Ω(log d) 跃到与 Ostrovsky–Rabani 上界同阶的指数。
问 4：等长见证与”每个大 d”为什么值得强调？
答：此前下界见证常落在长度的子序列上；”对每个 d≥d₀ 都有单一公共长度的二进制见证”才能与上界在同一个定义 E_Σ(d) 的域上比较，写下 log E_Σ(d)=Θ(√(log d·log log d)) 的一致结论，常数对一切至少二元字母表一致。这靠平衡 k≈a√(log d/log log d) 与定界符码宽度控制实现。
问 5：AI 生成、暂无形式化的证明最可能错在哪？
答：密集算术簿记：素数供给引理、m/2 个互异素数整除小于 T 的数的计数、傅里叶权重 M/(2k^k) 的积累、圆树随机系数的 9/10 概率。常数滑位则指数阶悄然改变；与圆构造、主文构造三线互证是现有唯一系统性检验，无形式化兜底。
问 6：附录的 804 因子转换定理主定理不用，为何要证？
答：独立价值与对比：对单一指定长度 M 的词给出块宽 M²、绝对因子 804 的二元转换，与 Bhattacharya 等人的对数宽度、按词长和归一的保证形成对照，也回答”能否常数失真”这一自然问题。主下界只需宽度 O(k log k)、损失温和增长的短定界符码。
问 7：谁会用到它？
答：度量嵌入与算法理论研究者：与姊妹篇合并后是编辑距离 ℓ1 失真的定阶定理，给”用割/线性规划技术处理编辑距离”的精度极限盖章；等长二进制见证也方便直接挪用做其他度量（如局部敏感哈希下界）的硬核。
总评
两条独立树构造把多年停在 Ω(log d) 的下界推到与上界同阶，是结果族 099 收口的关键一环。最大风险是无形式化下的多层算术簿记与对齐引理的适用边界，引用时宜注明”阶已定、常数未定”。