结果族 099：The sharp exponential scale of edit-distance distortion · 学科：Convex and metric geometry · 验证状态：暂无形式化证明，请以社区核验为准
一个朴素现象里藏着大学问：把单词 ABCD 循环挪一格变成 BCDA，只需 2 次编辑——删掉首字母、再接到尾部——可单词里每个字母的位置都变了。”词很长、挪动很便宜”这一反差，被本文组织成对 @@M@@\ell_1@@ 嵌入的系统性障碍：词记录圆上的相位，便宜的子群平移与昂贵的”半转”必须被任何嵌入区别对待，从而逼出指数失真。
关键词卡片
@@M@@\mathbb{R}/\mathbb Z@@ 上的一个点，标记子词被循环挪到了哪里。@@M@@\ell_1@@ 距离的基本构件，任何 @@M@@\ell_1@@ 距离都能拆成割的非负组合。看个具体例子
下界的”数字版”：两条独立构造都给出长度 @@M@@\le d@@ 的等长二进制词，@@M@@\ell_1@@ 失真至少 @@M@@\exp(c\sqrt{\log d\log\log d})@@；其中第二个构造失真至少 @@M@@m^{m/4}@@，而词长对数仅 @@M@@O(m^2\log m)@@——失真涨得远比词长快。配套的二元编码定理还能把大字母表的词逐符号换成二进制，宽度只按对数增长而不破坏指数阶。
为什么值得关心
它与姊妹篇的上界构造在指数阶上互相锁定：多条彼此独立的路线到达同一个数字，是这一结果族最结实的交叉印证。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读抓住的朴素现象是：把 ABCD 循环挪成 BCDA 只花两次编辑——删首字母、接尾部——尽管每个字母的位置都变了。”词很长、挪动很便宜”这组反差在这里被组织成可计算的障碍：让词记录圆上的相位，便宜的子群平移与昂贵的整体半转形成一张对照表，任何忠实嵌入都必须把两者区别对待。
第二级台阶
用本科术语定形。相位即圆周 R/Z 上的点，标记子词被循环挪到的位置；割度量是两点”是否被分开”的 0-1 距离，ℓ1 的任何有限距离都可分解为割的非负组合；在此基础上做有限傅里叶展开，就把”嵌入如何对待平移”变成关于频率的算术问题。失真仍指嵌入后拉伸与压缩之比。
第三级台阶
定理的语境：状态给有根树的叶子分配网格相位，内部节点的词列出带独立标签的子词行。三类相位变化被对比——子群内平移只挪行表、单叶位移代价与叶的比重成比例、全体叶子的半转则必须昂贵；半转的昂贵性要经”带标签行”引理控制任意对齐后才能立住。结论有两条独立构造给出公共长度不超过 d 的二进制词，ℓ1 失真至少 exp(Ω(√(log d·log log d)))（第二条给出量化版 m^{m/4}）。配套的二元编码定理把大字母表按对数宽度转移到二进制；上界侧把 Ostrovsky–Rabani 的重叠子串方法发展成完备直方图嵌入，覆盖一切有穷字母表、一切长度至多 d 的词（含空词），与下界在同一指数阶碰头。
本文为编辑距离嵌入 @@M@@\ell_1@@ 的失真下界 @@M@@\exp(\Omega(\sqrt{\log d\,\log\log d}))@@ 提供两个互相独立的”有限圆”构造（均为二进制等长词），并把 Ostrovsky–Rabani 上界方法发展成完备的直方图嵌入，上下两面在指数阶上互相锁定。
编辑距离 @@M@@\ED(x,y)@@ 计算把一个词改成另一个词所需插入、删除、替换的最少次数；把 @@M@@\Sigma^{\le d}@@ 嵌入 @@M@@\ell_1@@ 的最小失真记为 @@M@@E_\Sigma(d)@@。此前的格局是：Ostrovsky–Rabani（2007）的上界为 @@M@@\exp(C\sqrt{\log m\,\log\log m})@@，而最好的下界（Krauthgamer–Rabani 2009）只有 @@M@@\Omega(\log d)@@。本文的切入点是一个朴素却深刻的现象：插入或删除会改变整个后缀的位置，可把一个词循环平移一格只需两次编辑——删掉首字母再插到尾部。词”很长”而平移”很便宜”，这一反差可以被组织成对 @@M@@\ell_1@@ 嵌入的系统性障碍。
主定理：存在绝对常数 @@M@@c,C>0@@ 与 @@M@@d_0@@，对每个 @@M@@d\ge d_0@@、每个至少二元的有穷字母表 @@M@@\Sigma@@，都有 @@M@@\exp(c\sqrt{\log d\,\log\log d})\le E_\Sigma(d)\le\exp(C\sqrt{\log d\,\log\log d})@@。文章的两条下界路线各自给出一组公共长度 @@M@@\le d@@ 的二进制词见证下界；上界则由一个确定性有穷维映射实现。此外还有两项独立贡献：两个直接的二元编码定理——对大小为 @@M@@A@@ 的字母表给出宽度 @@M@@O(\log(2A))@@ 的码字替换，在所有等长词上同时具有绝对失真；以及一个完备的有穷直方图嵌入，把 Ostrovsky–Rabani 的重叠子串方法在同样的指数阶上对一切有穷字母表、一切长度至多 @@M@@d@@ 的词（含空词）完整实现。
下界的核心对象是”相位”（phase），即圆 @@M@@\mathbb R/\mathbb Z@@ 上的点。状态给有限根树（rooted tree）的每片叶子分配一个等距网格相位；叶子上放一段二元模式，记录圆上平移的半圆；内部节点的词列出各子词并给每个子词独立标签，长词在平移后的相位处重复这些行。三类相位变化被对比：指定子群内的平移只挪动行表，代价低廉；只移动一片叶子，代价不超过该叶所占比重乘位移的两倍；而所有叶子同时半转（half-turn）必须昂贵。证明半转昂贵要控制任意对齐（alignment），行标签正是工具：源行若整行匹配在单个目标行内，就继承子词的分离；若跨进多个目标行，就留下长长的无匹配区间，且不同源行所亏欠的区间互不重叠——”带标签行”引理把逐行分离放大为对任意匹配的下界。
分析侧把 @@M@@\ell_1@@ 距离在有限相位空间上分解为割（cut）的非负组合，再做有限傅里叶展开。关键算术事实是：在廉价子群上平均后仍能探测半转的特征，其全部叶频的绝对值之和必然很大——否则互异素数周期会迫使非零频率沿树”分叉”穿过太多叶子。加权单叶位移恰好控制这些大频率的质量，共同的分析引理是加权有限圆不等式 @@M@@\Delta_F(w)\le 2\E_{u\in H}\Delta_F(u)+\frac1B\sum_i\sum_a\frac Ma\Delta_F((a/M)e_i)@@。两个构造各自验证前提：第一个把子按素数分组、包含每个素数的全部剩余类，让一个非零相位沿树下降，用”分母重置”防止分母因子失控；第二个每个素数独占一个子，该素数的平移作用于除自己外的所有子，”被排除的坐标”迫使大多数平移坐标归零，失真至少 @@M@@m^{m/4}@@ 而词长对数仅 @@M@@O(m^2\log m)@@。最后用宽度对数的二元替换把大字母表转移到二进制，等长性质保证见证词公共长度。
上界构造把词分块，在每个二进制尺度列出重叠窗口，用随机划分（由割表示实现 @@M@@\Pr[\pi(u)=\pi(v)]=e^{-\alpha\rho(u,v)}@@）划分短词的像并记录计数直方图（histogram），对所有划分取直和得到确定性映射。相距远的块总在某个尺度让所有交叉窗口对都远，直方图支撑常不相交，给出下界；一次”移动”只挪动一个符号，大多数窗口可恒等配对，给出扩张上界。递归在幂长度上证明后，再在实际窗口长度上给出经由任意最长公共子序列与经由移动的两条扩张估计，最后以新符号 @@M@@\ast@@ 补齐，覆盖全部更短的词与空词。
本文主结果暂无形式化证明。两条下界路线彼此独立，且与同族姊妹篇（标记行构造、树构造）互不依赖，多条独立路线给出同一指数阶，构成交叉印证；直方图嵌入上界亦被姊妹篇直接引用为配套定理。按 OpenAI 官方声明，未经形式化的结果可能存在问题，请以社区核验为准。
问 1：下界证明里最要害、最脆弱的一步是什么？
答：证明”半转昂贵”。它要对任意对齐立住：带标签行引理处理两条逃逸路线——源行整行落进单个目标行时继承子词分离；跨进多个目标行时留下长段不匹配区间，且不同源行亏欠的区间互不重叠。行标签一旦泄漏（不同槽意外匹配），区间不再不相交，逐行分离就放大不成对齐下界。这一环是构造与分析的焊点。
问 2：为什么给两个互相独立的构造？
答：素数安排不同：第一个把子按素数分组、包含每个素数的全部剩余类，靠”分母重置”防止因子失控；第二个每个素数独占一个子，用”被排除的坐标”迫使多数平移坐标归零，给出量化版失真 m^{m/4}（词长对数仅 O(m²log m)）。二者互为冗余，一条有隐患另一条仍撑住下界。
问 3：与姊妹篇及 Ostrovsky–Rabani 相比新意是什么？
答：下界机制独立于标记行构造与树构造姊妹稿，多条独立路线抵达同一指数，是本族最结实的交叉印证。上界不止引用：把 Ostrovsky–Rabani 的重叠子串方法发展成完备直方图嵌入，补齐一切有穷字母表、一切长度至多 d 的词（含空词）与确定性有限维映射，被姊妹篇直接引作配套定理。
问 4：加权有限圆不等式挡住什么麻烦？
答：它把半转位移控制在”廉价子群平均＋单叶预算”内，算术核心是：能在廉价子群平均后仍探测半转的特征，其叶频绝对值之和必大——否则互异素数周期迫使非零频率沿树分叉穿过太多叶子。两个构造各自验证这条前提，缺一即断。
问 5：AI 生成、暂无形式化的证明最可能错在哪？
答：有限群上的傅里叶与素数周期簿记：分母重置处因子是否真的不累积、被排除坐标归零的计数、直方图嵌入随机划分的配对概率 e^{-αρ(u,v)} 与直和装配常数。无形式化，姊妹篇同指数互证是现有唯一系统性检验。
问 6：二元编码定理的”对数宽度、绝对失真”为何重要？
答：它解决归约瓶颈：大小 A 的字母表逐符号换成宽度 O(log(2A)) 的二进制块，且在所有等长词上同时绝对失真。大字母表的下界见证无须重造，等长性保证见证词仍为公共长度，与”字母再多不更容易”配套。
问 7：直方图嵌入的完备性体现在哪，谁用得上？
答：覆盖任意有穷字母表、一切长度至多 d 的词与空词，输出确定性有限维映射，不再是存在性陈述。上游是本族姊妹篇的上界引用；做编辑距离草图、近邻搜索的人可当显式黑盒，虽然指数失真只够常数因子近似。
总评
用”圆上相位”把平移之廉与半转之贵拧成下界机器，并以完备直方图嵌入补齐上界，是本族自足性最高的一篇。最大风险在傅里叶与素数簿记密集且无形式化，交叉印证之外仍需独立核验。