结果族 122：Quantitative trace-reconstruction bounds with a uniform decoder · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
上界说”攒够这么多份残缺复印件,原句就认得出来”;这篇反其道而行,证明”再少就一定认不出来”。像给商品补上价格的下半截:不管你多聪明、计算机多快、算多久,样本少于这个数,任何方案都注定失败。
关键词卡片
@@M@@q@@,固定在 @@M@@(0,1)@@ 内。看个具体例子
公式卡 固定 @@M@@q=1/2@@,精确重构 @@M@@n@@ 比特串至少要 @@M@@n^{c\log\log n}@@ 条轨迹(常数 @@M@@c@@ 可取 @@M@@0.3@@):@@M@@n=2^{100}\Rightarrow@@ 至少 @@M@@n^{1.3}@@ 条;@@M@@n=2^{10000}\Rightarrow@@ 至少 @@M@@n^{2.6}@@ 条。
指数 @@M@@c\log\log n@@ 随 @@M@@n@@ 无限上涨,所以任何固定的多项式 @@M@@n^C@@ 迟早不够用——”固定删除概率下多项式样本够用”的猜想被正式否定。而且这不只是样本问题:论文还证明两条孪生串的单条轨迹分布之差衰减得比任何多项式都快。
为什么值得关心
它划死了信息本身的底线:即使计算时间不限、成功概率只需任意固定的正值,样本不够就是不够。与上界两篇合看,真相被夹在”拟多项式”附近,只剩对数幂的缺口。
暂无形式化证明(AI 结果待核验)
第一级台阶
导读把这篇比作”给商品补上价格的下半截”，先翻译一下：对象仍是那条 0/1 原句和它的残缺复印件，操作仍是每位独立地以概率 q 被吞掉。但这回问的不是”攒多少份才够”，而是”少于多少份必定不够”——无论后面接多聪明的算法、算多久。核心手段是精心造出一对”孪生原句”，让信道对它们吐出几乎相同的复印件分布。
第二级台阶
用本科术语说：一条残件由删除概率为 q 的删除信道生成；两个候选串的轨迹分布之差用总变差（TV）度量，TV 接近 0 意味着任何统计检验都无法可靠分辨二者；孪生串取互补的 Prouhet–Thue–Morse 型带符号模式，其一切低阶统计近乎一致。样本数下界指最坏情形标准下——对每个串都要求以固定概率 s 重构成功——所需的最少轨迹条数。
第三级台阶
定理在这样的语境下陈述：固定 q∈(0,1) 与任意固定成功概率 s>0，计算资源完全放开，结论是所需轨迹数仍至少 n^{c·log log n}（常数 c<1/(4 log 2)）；一般地当 q³ log n→∞ 时下界为 n^{c·log(q³ log n)}。各假设的分工：q 固定挡住了低删除率体制——那里多项式样本确实可能够，与本文不矛盾；计算不限、成功概率只需固定正值，把结论做成纯信息论底线。用 TV 的语言说结论：孪生串的 m 条独立轨迹的联合分布之差被 Hellinger 张量化压住，必须 m 达到上述量级才能分开——这正是”多项式样本猜想被否定”的含义。
论文证明：对每个固定删除概率 @@M@@q\in(0,1)@@，即使计算不限、成功概率只需固定正值，精确重构任意 @@M@@n@@ 长二进制词需要 @@M@@n^{\Omega(\log\log n)}@@ 条轨迹，否定”多项式样本足够”的猜想；一般地当 @@M@@q^3\log n\to\infty@@ 时下界为 @@M@@n^{c\log(q^3\log n)}@@。
轨迹重构（trace reconstruction）的下界长期大幅落后于上界。Batu–Kannan–Khanna–McGregor（2004）提出问题时勾勒了固定删除概率下线性样本的障碍；McGregor–Price–Vorotnikova 分析零背景中单个 1 的位移；Holden–Lyons 证明 @@M@@\Omega(n^{5/4}/\sqrt{\log n})@@，Chase 改进到 @@M@@\Omega(n^{3/2}/\log^7 n)@@——都停留在多项式量级。上界侧 BVW（2026）已给出拟多项式样本界，”固定删除概率下多项式条轨迹是否足够”成为核心悬案。本文给出否定回答：任何固定 @@M@@q@@ 都超多项式。定理二更证明：固定 @@M@@q@@ 时两个不同 @@M@@n@@ 长词的轨迹律的最小总变差（total variation）衰减快于任何多项式。
以 @@M@@T_{q,s}(n)@@ 记以概率至少 @@M@@s@@ 重构每个 @@M@@x\in\{0,1\}^n@@ 所需的最小轨迹数（估计器可随机、计算不限）。定理一（定量样本下界）：固定 @@M@@s\in(0,1]@@ 与 @@M@@0<c<1/(4\log2)@@，沿一切 @@M@@n\to\infty@@、@@M@@q\in(0,1)@@ 且 @@M@@q^3\log n\to\infty@@ 的实例列，最终有 @@M@@T_{q,s}(n)\ge n^{c\log(q^3\log n)}@@（对数均为自然对数）。固定 @@M@@q@@ 时 @@M@@\log(q^3\log n)\asymp\log\log n@@，即 @@M@@n^{\Omega(\log\log n)}@@。定理二（单轨迹超多项式不可区分）：对每个固定 @@M@@q\in(0,1)@@ 与每个 @@M@@A>0@@，有 @@M@@n^A\min_{x\ne y}\mathrm{TV}(\mathcal D_q(x),\mathcal D_q(y))\to0@@，且同一信道下 @@M@@T_{q,s}(n)/n^A\to\infty@@。
先做信道归约：工作删除率取 @@M@@\delta=\min(q,1/2)@@，令 @@M@@H_{\rm del}=\delta^3\log n@@；在 @@M@@\delta@@ 处证明的不可区分性上界，经对存活比特再删除即传递到请求信道 @@M@@q@@。证明是跨约 @@M@@D\approx(1-\zeta)\log H_{\rm del}/(B\log2)@@ 个尺度的归纳：目标长度按 @@M@@N_{i-1}=N_i^{a_0(b_i)}@@ 自 @@M@@n@@ 向下收缩，得分指数 @@M@@d_i@@ 每块增长 @@M@@(b_i-1)/4-0.05@@（前 @@M@@5\cdot2^B@@ 个深度 2 预备块把种子指数从 2.20 抬到所需强度）。归纳不变量（level invariant）同时维护：一对等长词 @@M@@x_i,y_i@@ 与辅助律 @@M@@\mu_i,\nu_i@@，使某个马尔可夫核把辅助律投影到真轨迹律且 TV 误差每级不超过 @@M@@(i+1)\Delta@@；似然得分 @@M@@d\nu/d\mu-1@@ 的 @@M@@L^{r_i}@@ 范数平方不超过 @@M@@N_i^{-d_i}@@；以及 @@M@@x_i@@ 连缀 @@M@@k@@ 次与 @@M@@k+1@@ 次的轨迹律有共同质量至少 @@M@@\omega@@。
构造机制是”在多个尺度上隐藏位置差异”。基石是精确共同质量：同一词连缀 @@M@@k@@ 与 @@M@@k+1@@ 次后的轨迹律共享质量 @@M@@\omega@@；把这样一对游程放在中央段两侧、以公平比特选朝向，联合轨迹律便含质量 @@M@@\omega^2@@ 的乘积分量，其上朝向仍公平，许多独立对留下中央段位置的二项不确定性；边际化朝向后恰好还原两侧轨迹律之积，故把固定词各段的独立真迹连缀就能精确复原其轨迹律——这就是”辅助观察近似真迹”的来源。两词的中央段取互补的 Prouhet–Thue–Morse 型带符号模式，其生成多项式在 @@M@@1@@ 处高阶为零，与宽二项偏移卷积后极小（与 HMPW 的二进符号递归同源）。系数沿嵌套段树展开后，互补词的根类型为 @@M@@\pm1@@，相减消去一切偶根项；奇根项若不含”单活跃孩子”，就被迫包含 @@M@@2^b@@ 片叶的完全二叉子树，带来 @@M@@2^b@@ 个旧得分因子、保住衰减 @@M@@N^{-d}@@，而兄弟组的共享位移加独立位移再摊开后代位置，额外贡献 @@M@@N^{-(b-1)/4}@@ 的衰减。收尾用 Hellinger 张量化：@@M@@\mathrm{TV}(\mathrm{Tr}(x)^{\otimes m},\mathrm{Tr}(y)^{\otimes m})\le\sqrt{mN^{-d}}+2mE@@，要它小于常数必须 @@M@@m\ge n^{c\log(q^3\log n)}@@；经转移与按长度填充即得两个定理。归纳还须核查：种子对随 @@M@@q@@ 减小一致有效、块数增长时常数不越过尺度裕度、一切条件化与失败布局的损失计入不变量误差。强迫二叉子树与位移摊开的技术细节论文展开极长，此处从略。
主结果无 Lean 形式化证明，OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。与族内上界两篇的关系：BVW 型拟多项式上界的对数是 @@M@@\log n@@ 的固定幂，本下界在固定信道下的对数量级为 @@M@@(\log n)(\log\log n)@@，两侧仍有缺口。多项式可能性被否定后，姊妹篇的拟多项式样本上界与”统一拟多项式时间”篇的解码器便是当前最佳答案；低删除率 @@M@@q\le n^{-1/3-\varepsilon}@@ 下的多项式时间重构落在本文体制 @@M@@q^3\log n\to\infty@@ 之外，并不矛盾。
问 1：证明中最关键、也最脆弱的一步在哪里？
答：多尺度归纳的”层级不变量”维护。归纳同时要求：某马尔可夫核把辅助分布投影到真轨迹律且每级 TV 误差不超过 (i+1)Δ；似然得分的 L^{r_i} 范数平方不超过 N_i^{-d_i}。支撑它的是”强迫二叉子树”论证——互补词系数相减消去偶根项后，奇根项若不含单活跃孩子就被迫含 2^b 片叶的完全子树，才保住得分衰减。这条组合引理稍有漏洞，全链的 N^{-d} 衰减即告失守。
问 2：为什么必须固定删除概率 q？小 q 时结论如何？
答：定理的一般体制是 q³ log n→∞；当 q≤n^{-1/3-ε} 时多项式样本重构并不与本下界矛盾——论文明确这一体制豁免。低删除率下位移方差小、单轨迹信息多，孪生串的隐藏机制失效，论文未在该体制给出超多项式下界。
问 3：为什么”计算不限”也救不了？
答：论证是纯信息论的。单条轨迹分布的 TV 已超多项式地小（定理二：n^A·minTV→0 对一切 A 成立），m 条独立轨迹联合律的 TV 由 Hellinger 张量化界住：TV≤√(mN^{-d})+2mE。要它达到常数必须 m≥n^{c log(q³ log n)}，与估计器的聪明程度无关——随机化、无限时间都在 TV 面前平等。
问 4：与此前下界（Holden–Lyons、Chase 的多项式量级）相比，真正新意是什么？
答：此前下界停在 Ω(n^{3/2}/log⁷ n)，靠的是单一构造对的直接计算；本文首次跨到超多项式，靠三件新武器：同一词连缀 k 与 k+1 次的轨迹律有精确共同质量 ω（辅助观察可复原真迹）、互补 PTM 模式的高阶零点、以及跨 D≈log(q³ log n) 个尺度的归纳收缩。它正面否定了”固定 q 下多项式样本足够”的猜想。
问 5：AI 生成证明最可能在哪里出错？
答：跨尺度簿记。目标长度按 N_{i-1}=N_i^{a₀(bᵢ)} 收缩、得分指数每块增长 (bᵢ-1)/4-0.05，同时要核查种子对随 q 一致有效、块数增长不越过尺度裕度、条件化损失全部计入不变量误差——block 与 coefficients 等节的组合分支极多。机器证明最易在某条失败布局的漏计上翻车，而这类错误恰好最难抽查。
问 6：谁会用这个结果？
答：它给 DNA 数据存储与删除信道编码定了不可绕过的采样预算底线；与同族两篇上界合看，真相被夹在拟多项式附近、仅剩对数幂缺口。平均情形重构与容错重构的下界，论文未涉及。
总评
这是轨迹重构下界首次从多项式跃到超多项式、信息论底线被定量钉死的一步；最大风险在未形式化，且全靠跨尺度组合归纳的严密簿记，任何一条漏计的失败布局都可能悄悄击穿不变量。