结果族 122：Quantitative trace-reconstruction bounds with a uniform decoder · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
朋友通过一条总会随机吞字的信道给你发一句 0/1 暗号,你收到许多条残缺版本,要在所有 @@M@@2^n@@ 个候选原句里认出唯一正确的那句。这篇论文只回答”信息够不够”的问题:到底要攒多少条残缺暗号才够?结论:固定吞字概率时,拟多项式条就够——注意这是纯样本数结论,不谈怎么算得快。
关键词卡片
@@M@@p@@,删除概率 @@M@@q=1-p@@。@@M@@2^{(\log n)^k}@@ 量级,远小于任何 @@M@@2^{n^{\varepsilon}}@@。看个具体例子
旧纪录是 @@M@@\exp(\tilde O(n^{1/5}))@@ 条,本文压到 @@M@@\exp(O((\log n)^3(1+\log\log(2n))^6))@@ 条。
公式卡 @@M@@n=2^{500}@@ 时,所需轨迹数的对数:旧界 @@M@@\approx n^{1/5}=2^{100}\approx10^{30}@@,新界 @@M@@\lesssim(\log n)^3(1+\log\log n)^6\approx4\times10^{12}@@(未计常数)——指数上砍掉十几个数量级。另外,若删除概率很小(@@M@@q\le n^{-\varepsilon}@@),多项式条轨迹就够;同样结论也适用于一般符号表的串(保留符号被精确观察时),重构成功概率至少 @@M@@2/3@@。
为什么值得关心
它与同日两篇姊妹作合力,把轨迹重构的样本复杂度从”亚指数时代”推进到”拟多项式时代”。但要读清:本定理只保证”条数够”,不给出快速算法,也不断言这个量级最优。
暂无形式化证明(AI 结果待核验)
第一级台阶
导读里”总会随机吞字的信道暗号”可以翻译成半数学语言：对象是一串未知的 0/1 符号；操作是每一位独立地以同一概率存活，存活者按原顺序拼成一条残句。要问的只有一件事：攒多少条残句，才能在所有可能的原句里认出唯一正确的那句——条数之外的问题（比如算得快不快）一概不问。
第二级台阶
用本科术语精确化：残句称为删除轨迹，单个比特存活概率记作 p；样本复杂度指最坏情形下——对每一个候选原串都单独要求至少 2/3 重构成功率——所需的最少轨迹条数；拟多项式指 exp((log n)^k) 一类量级。论文的检验器叫探针：在指定的一列位置读出比特，乘上带指数衰减的相位权重后求和，得到一个能给候选串打分的线性统计量。
第三级台阶
定理的陈述策略是”区分即足够”：对任意两个不同候选串，构造一个探针使其期望分数之差可检测，再对全部候选对手取联合界。假设各有用场：原句长度与存活概率已知，检验容差与相位参数才有依据；逐串成立的最坏情形标准，排除了”平均而言易重构”的侥幸。结论用上述术语说：固定 p 时 exp(O(p^{-1}(log n)^3(1+log log n)^6)) 条轨迹足够；删除概率不超过 n^{-ε} 时降为多项式条。且这仅是样本数结论——既不给出高效算法，也不断言量级最优，这两点论文都明言在界外。
论文把最坏情形轨迹重构（trace reconstruction）的样本上界改进为 @@M@@\exp(O(p^{-1}(\log n)^3(1+\log\log(2n))^6))@@：固定保留概率 @@M@@p@@ 时拟多项式条轨迹足够，删除概率 @@M@@\le n^{-\varepsilon}@@ 时多项式条足够；这是纯样本复杂度结果，不声称高效算法，也不断言最优。
删除信道的轨迹重构中，样本上界长期停留在亚指数：HMPW 的 @@M@@\exp(\tilde O(\sqrt n))@@、De–O’Donnell–Servedio 与 Nazarov–Peres 的 @@M@@\exp(O(n^{1/3}))@@、Chase 的 @@M@@\exp(O(n^{1/5}\log^5 n))@@。2026 年 BVW 用非局部低阶统计量与多尺度传播首次给出拟多项式界 @@M@@\exp(p^{-7/3}(\log_2 n)^{c_0})@@，但未给高效解码。作者核对 BVW 证明的具体处方发现：按其第 8 节的深度界与配对检验参数，固定 @@M@@p@@ 时已证估计隐含 @@M@@\log@@ 幂至少 @@M@@(7/3)\log_{1.1}3>26@@。受 BVW”以 Fourier 乘积检验相位关系”的思想启发，本文给出完全不同的归纳证明，把可证量级推进到显式指数；作者言明这是相对 BVW 已证估计的改进，非对其方法一切优化的断言。
定理：对整数 @@M@@n\ge2@@、@@M@@0<p\le1@@，对每个输入串以至少 @@M@@2/3@@ 概率成功的最坏情形二元串重构，至多需要 @@M@@\exp(O(p^{-1}(\log n)^3(1+\log\log(2n))^6))@@ 条独立轨迹。更细地，记 @@M@@q=1-p@@、@@M@@\mathcal X=1+\log n/(1+\log(1/q))@@，则所需样本预算的对数不超过 @@M@@O(p^{-1}(\log n)\mathcal X^2(1+\log\mathcal X)^6)@@。固定 @@M@@\varepsilon>0@@ 且 @@M@@0\le q\le n^{-\varepsilon}@@ 时多项式条轨迹足够。同样的渐近界也适用于一般符号表的串（假设保留符号被精确观察）。摘要强调：这些界只关于样本复杂度（sample complexity），不断言高效算法，也不证明匹配的最优下界。
只需构造检验区分任意两个候选串 @@M@@x,y@@，再对全部 @@M@@<2^n@@ 个对手取联合界。先给两串垫上等长的已知零块，使首错位 @@M@@d\ge n/2@@。核心对象是”最末锚点数组”：一个 @@M@@k@@ 阶探针（probe）在严格递增位置上取比特谓词与若干”精确边”（强制相邻间隔恰为 1），并可携带低层”掩码”因子——形如 @@M@@K(g)\prod_s e^{i\beta_s g_s}@@ 的相位乘积，受指数衰减模长与”谱紧”表示（可写成紧频率方块上复测度的 Fourier 积分）双重约束，即标题中的 spectrally compact masks。令 @@M@@s_x(m)@@ 为所有限制末位 @@M@@i_k=d+m@@ 的探针权重之和，差多项式 @@M@@H(z)=\sum_m(s_x(m)-s_y(m))z^m@@ 没有负幂项。第 @@M@@j@@ 层归纳目标是找到探针使 @@M@@|H(e^{-a_j+i\theta})|\ge e^{-B_j/f(\theta/a_j)}@@（@@M@@f(u)=e^{u^2/20}@@），且阶与块数每层至多乘 4。
奠基用”避周期词”：由 Fine–Wilf 周期现象，公共前缀片段的两个单比特延拓中至少一个无短周期；取 @@M@@2P_0@@ 长全精确边的模式，其在两串中的出现结尾按周期分离，得 @@M@@H(z)=1-\eta z^u+\text{尾项}@@，在正实轴上量级可观，再用次调和 Poisson 不等式把信号搬到圆弧上。归纳步是”加权相位检验”：经高斯–多项式掩码把数组变为非负，在频率网格上寻找至多 4 个频率（其和近零）使两边 Fourier 值乘积之差显著——证明依赖 Cauchy 核权重下顶点覆盖（vertex cover）权重的组合下界，与四元乘积逐步控制相位差的 telescoping 论证。随后”洗牌合并”把乘积展开、按全部位置的弱序分类，合并为阶至多 @@M@@4k@@ 的单个新探针；”中心 Fourier 展开”与”径向紧化”把高斯掩码乘积折回带可许层掩码的元组统计量，误差指数级小。停止条件为 @@M@@a_jn\le0.001@@：此时展开全部掩码并选定一组频率，得纯乘积探针，使每条松边的参数 @@M@@z^*@@ 满足 @@M@@\kappa(z^*)=(1-|z^*|^2)/|1-z^*|^2\ge c_0q@@；再经带状解析插值（Hadamard 三线定理）推到 @@M@@\kappa@@ 更大的边界线，使全部参数落入圆心 @@M@@q@@、半径 @@M@@p@@ 的”迹圆盘”。条件于源比特存活，二项计数给出检验统计量期望差至少 @@M@@\exp(-O(p^{-1}\ell_*8^b(b+1)^6))@@；Hoeffding 不等式加联合界完成区分，换算即得定理指数。
主结果暂无形式化证明，OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。本文与同日的”统一拟多项式时间”篇界的形式一致：后者把同类分离强化为对半定矩松弛的命题并造出解码器；下界篇则证明固定删除概率需要 @@M@@n^{\Omega(\log\log n)}@@ 条轨迹。上下界的对数之间仍隔着头对数幂，最优样本复杂度仍是公开问题。
问 1：证明中最关键、也最脆弱的一步在哪里？
答：归纳步的”加权相位检验→洗牌合并”。它靠 Cauchy 核权重下顶点覆盖权重的组合下界，找到至多 4 个频率（其和近零）使两侧 Fourier 值乘积之差显著，再用四元乘积的 telescoping 论证逐步控制相位差，最后把乘积按全部位置的弱序分类，合并成阶至多 4k 的单个新探针。每层阶数与块数至多乘 4，任何一层常数失控，末端的期望差 exp(−O(p^{-1}ℓ*8^b(b+1)^6)) 就撑不起样本换算。
问 2：为什么一般字母表的结论要求”保留符号被精确观察”？
答：探针里的比特谓词以”读到什么就是什么”为前提；若信道还掺替换噪声，谓词期望会系统性偏移，奠基步的避周期词论证与相位权重都会失准。论文未讨论含替换错误的信道。
问 3：相对 2026 年 BVW 的拟多项式界，真正的新意是什么？
答：BVW 首创拟多项式量级，但指数中的 log 幂未被显式控制——作者按其第 8 节的深度界与配对参数核算，已证估计隐含 log 幂至少 26。本文改用”最末锚点数组＋谱紧掩码”的全新归纳证明，把指数写成显式的 O(p^{-1}(log n)^3(1+log log n)^6)，并明确声明只是相对 BVW 已证估计的改进，不评其方法的一切潜在优化。
问 4：AI 生成证明最可能在哪里出错？
答：多层归纳的常数耦合。奠基步 Fine–Wilf 周期引理的参数（2P₀ 长全精确边模式）、次调和 Poisson 不等式的常数 e^{u²/20}、停止条件 a_j n≤0.001 处的 κ(z*)≥c₀q、Hadamard 三线插值，这些量要在 b≈log log n 层归纳后严丝合缝地折进 8^b(b+1)^6，再与 Hoeffding 集中及 2^n 个对手的联合界相容。机器证明最易在这种层层相乘的簿记里丢掉一个因子。
问 5：只证样本数、不给算法，是回避难点吗？
答：区分性统计量要同时知道两个候选串才能打分，天然不构成解码器；摘要明确”不断言高效重构算法”。把此类分离升级为可执行算法是同日姊妹篇（统一解码器篇）的任务，两文边界清晰。
问 6：这个界离最优有多远，谁会用它？
答：同族下界篇证明固定删除概率需要 n^{Ω(log log n)} 条轨迹，故拟多项式量级已接近必要；但上下界的对数之间仍隔若干 log 幂，最优样本复杂度是公开问题（论文自承”optimal complexity open”）。直接受众是删除信道编码与 DNA 存储理论社区。
总评
这是把最坏情形轨迹重构的样本上界写成显式拟多项式指数的扎实一步，与姊妹篇合力闭合”样本—算法”叙事；最大风险在于未形式化，且全文依赖多层归纳的常数咬合，任一层失准都会牵动主定理。