在以太坊社区的“邻近性奖”（Proximity Prize）以及非正式地被称为“Proxember”的推动下，一系列精彩的论文开始质疑著名的里德-所罗门码邻近性间隙（Proximity Gaps for Reed–Solomon Codes ）中提出的“直至容量上限”的列表解码猜想。Diamond -Angus率先发难，随后Crites-Stewart也发表了论文，所有这些论文都指向同一个结论：认为里德-所罗门码可以一直解码到(1-ρ) ( 1 - ρ )的这种说法存在严重问题。
本文并非旨在证明任何新结论，其唯一目的是提供一个小型、完全可复现的数值示例，使现有理论更加具体。秉承 Crites-Stewart 的方法，我选取了一个简单的 Reed-Solomon 编码，并严格选择介于平凡插值阈值和经典 Elias 界限所定义的 Elias 列表解码容量之间的参数，结果表明列表大小已经膨胀到数十个码字。他们的工作对超过此界限的列表大小爆炸现象进行了更具建设性和通用性的处理；而我在这里只是在一个屏幕大小的微型示例中实例化了同样的现象，您可以使用几行 Python 代码复现该示例。
“达到容量上限”列表解码猜想
在深入探讨具体数字之前，值得一提的是大家一直在讨论的一个猜想。
我们使用定义在有限域\mathbb{F}_q F q上的长度为n n 、维度为k k的 Reed-Solomon (RS) 码。码率\rho = \frac{k}{n} ρ = k n ，
每个码字都是对某个大小为n n的评估集上的k次多项式的评估。
一个码C \subseteq \mathbb{F}_q^n C ⊆ F n q被称为(\delta, L) ( δ , L )列表可解码的，如果对于每个接收到的字y \in \mathbb{F}_q^n y ∈ F n q ，以y为中心、半径为\delta n δ n的汉明球最多包含L L个码字：
这里δ是容许错误率， L是列表大小。经典唯一解码对应于 (L = 1)的情况。
“达到容量上限”列表解码猜想（如《里德-所罗门码的邻近间隙》一书中所述）可以非正式地表述如下：
对于任意速率0 < ρ < 1和任意η > 0 ，速率为ρ的每个 Reed-Solomon 码都是 ( δ , poly (1/η)) ( δ , poly ( 1 / η ) )列表可解码的。
δ ≤ 1 - ρ - η。δ ≤ 1 − ρ − η 。
用文字表达：
- 速率为ρ的编码有1 - ρ的误差“容错空间”。
- 该猜想断言，RS 码可以有效地从几乎相同数量的错误中（直到一个很小的松弛\eta η ）进行列表解码，而列表大小只有多项式限制。
- 这就是为什么人们将其总结为“RS 码在容量范围内是列表可解码的”，其中隐含地将“容量”视为1-\rho 1 − ρ线。
这个猜想之所以如此诱人，是因为它符合一个非常简单的启发式：如果你将数据压缩一个因子ρ ，那么从逻辑上讲，你应该能够承受高达1 - ρ的噪声。Proxember 的整个推论在于，一旦你将这种普遍认知与Elias 列表解码容量（曲线ρ = 1 - H_q(δ) ρ = 1 - Hq ( δ ) ）进行比较，你就会发现这个“直至容量上限”的猜想实际上要求过高，列表的大小必然会呈爆炸式增长。
克里特-斯图尔特在第 3.1 节中做了什么
Crites–Stewart 的出发点是 Elias 的经典列表解码容量定理（例如，如 Guruswami–Rudra–Sudan 所述）：
令q ≥ 2，0 ≤ δ < 1 - 1 / q ，并令η > 0。对于所有足够大的块长度n ：
- 如果\rho \le 1 - H_q(\delta) - \eta ρ ≤ 1 − H q ( δ ) − η ，则存在一个(\delta, O(1/\eta)) ( δ , O ( 1 / η ) )列表可解码码。
- 如果ρ ≥ 1 - H_q(δ) + η ，则每个( δ , L ) ( δ , L )列表可解码码都有
L \ge q^{\Omega(\eta n)}。L ≥ q Ω ( η n ) 。具体来说，列表解码容量是曲线\rho = 1 - H_q(\delta) ρ = 1 − H q ( δ ) ，其中H_q(\delta) H q ( δ )是q q元熵函数。
第 3.1 节主要做了三件事：
量化\delta δ和H_q(\delta) H q ( δ )之间的差距。
它们证明了一个简单但至关重要的不等式\delta < H_q(\delta) \le \delta + \frac{1}{\log_2 q}δ < H q ( δ ) ≤ δ + 1 log 2 q对于所有0 < δ ≤ 1 - 1/q ， 0 < δ ≤ 1 - 1 / q ，并证明该上界本质上是紧的。直观地说，这意味着：容忍δ比例误差的熵成本略大于δ ，开销至多为1 / log₂q 1 / log₂问：
利用这一点可以排除“高达 $1-\rho$”列表解码的可能性。
一个非常常见的启发式方法是，速率为ρ的编码应该在大约 ρ 的范围内可列表解码。δ ≈ 1 - ρδ ≈ 1 − ρ对于小列表，分数误差——即，容量非正式地被视为直线δ = 1 - ρ δ = 1 − ρ 。Crites-Stewart 指出，一旦你记住H_q(δ) > δ H q ( δ ) > δ ，这与 Elias 容量定理不相容：
- 小列表的真实信息论极限是\rho \le 1 - H_q(\delta).ρ ≤ 1 − H q ( δ ) 。
- 如果你坚持列表可解码性一直到δ ≤ 1 - ρ - η ，其中η > 0， η > 0 ，那么在感兴趣的参数范围内，你最终必然会进入该区域。\rho \ge 1 - H_q(\delta) + \eta',ρ ≥ 1 − H q ( δ ) + η ′ ,Elias 保证列表规模呈指数级增长。
换句话说，“里德-所罗门至容量”的说法（将“容量”解释为1-\rho 1 − ρ ）只是要求参数高于实际的列表解码容量曲线。
- 小列表的真实信息论极限是
简而言之，第 3.1 节并没有引入新的容量定理；相反，它：
- 回想起经典的 Elias 列表解码容量界限，
- 明确指出这一界限如何与“高达 $1-\rho$”的观点相矛盾，
帖子后面的数值玩具示例只是微观参数中同一现象的一个具体实例，遵循了第 3.1 节的讨论精神（当然，Crites-Stewart 的处理方式更一般、更具建设性）。
数值示例：Trivial 爆炸与 Elias 爆炸
现在让我们看看，当我们把具体的参数代入一个简单的 Reed-Solomon 代码并进行暴力列表解码时会发生什么。本节的重点在于区分导致列表大小爆炸的两种不同原因：
- 一个基于维度的简单原因（当我们允许的错误太多而约束太少时），以及
- Elias/容量原因（即使我们仍然有“足够”的约束，熵计算也会强制使用大型列表）。
我们的实验将严格介于这两个阈值之间：
设置
我们与以下机构合作：
- 域大小q = 13 q = 13 （所以我们覆盖了\mathbb{F}_{13} F 13 ），
- 块长度n = 12 n = 12 ，
- 维度k = 5 ，因此速率为\rho = \frac{k}{n} = \frac{5}{12} \approx 0.4167,ρ = k n = 5 12 ≈ 0.4167 ，
- 误差率δ = 0.5，δ = 0.5 ，即解码半径为t = \delta n = 6 t = δ n = 6 个错误。
对于实验的每次试验，我们：
- 在\mathbb{F}_{13} F 13上随机抽取一个次数< k < k 的多项式。
- 在乘法序12 12域上对其进行评估，得到长度为 12 12 的RS 码字c c 。
- 对c c的6 个坐标进行破坏（均匀随机选择并更改为随机非零错误），得到接收字y y 。
- 运行暴力列表解码器，返回所有与y y的汉明距离不超过6 6的 RS 码字c' c ′ 。
列表解码器内部计算一致性阈值
并且保持所有码字在至少6个位置上与y y一致，即距离\le 6 ≤ 6 。
绕道而行：微不足道的爆炸阈值
Reed-Solomon码的列表大小会呈指数级增长，这有一个非常简单的“维度计数”原因。如果我们允许的错误数量足够多，使得一致数(1-δ)n ( 1 - δ ) n至多为kk ，那么我们对次数<k < k的多项式最多有kk个约束。
形式上，平凡爆炸机制是
在这个政权下：
- 你可以选择(1-δ)n ( 1 − δ ) n个坐标和值，
- 总有一些阶数小于k的多项式插值它们，
- 因此，你可以期望仅通过线性代数就能在解码球中几乎免费地获得大量的码字。
对于我们这段简短的代码：
- n = 12 n = 12 ，
- k = 5 k = 5 ，
- 因此，平凡爆炸阈值是t_{\text{triv}} = n - k = 12 - 5 = 7 \quad\text{错误},t triv = n − k = 12 − 5 = 7错误，等价地\delta_{\text{triv}} = \frac{7}{12} \approx 0.5833.δ triv = 7 12 ≈ 0.5833。
如果我们从7个或更多错误中解码，那么我们观察到的任何列表爆炸都可以合理地归咎于这种简单的机制。
我们的实验地点
在我们的实验中，我们对以下内容进行解码
我们有：
- 协议：(1-δ)n = 0.5 · 12 = 6,( 1 − δ ) n = 0.5 × 12 = 6 ，
- 满足6 > k = 5。6 > k = 5。
所以，我们严格低于微不足道的阈值：
- (1-δ)n > k ( 1 − δ ) n > k ,
- 等价地， t = 6 < t_{\text{triv}} = 7 t = 6 < t triv = 7 。
这意味着：
我们在t = 6时看到的任何列表大小的膨胀都不能用简单的“我们最多有k个约束，所以插值会产生很多码字”的论点来解释。
如果列表在这里激增，那一定是出于更微妙的、信息论方面的原因。
这个“更微妙的原因”恰恰是 Elias 列表解码能力的极限。
高于 Elias 容量阈值
对于字母表大小q = 13和错误率δ = 0.5 ，我们计算q元熵。
因此，在此δ处的列表解码容量为
我们的价格是
所以我们的产能远远超过负荷：
对 Elias 式计数论证进行标准改进，可以得到所有中心y \in \mathbb{F}_{13}^{12} y ∈ F 12 13的平均列表大小的清晰下界：
对于我们的参数：
- n(\rho + H_q(\delta) - 1) \approx 12 \cdot 0.171302 \approx 2.0556 n ( ρ + H q ( δ ) − 1 ) ≈ 12 ⋅ 0.171302 ≈ 2.0556 ，因此q^{n(\rho + H_q(\delta) - 1)} = 13^{2.0556} \approx 195,q n ( ρ + H q ( δ ) − 1 ) = 13 2.0556 ≈ 195 ，
- 和\sqrt{8 n \delta (1-\delta)}= \sqrt{8 \cdot 12 \cdot 0.5 \cdot 0.5}= \sqrt{24} \approx 4.90.√ 8 n δ ( 1 − δ ) = √ 8 × 12 × 0.5 × 0.5 = √ 24 ≈ 4.90。
综合起来，
因此，平均而言，以随机词y y为中心，半径为6 6的汉明球包含至少约40 40 个里德-所罗门码字——而这还不是在我们达到平凡阈值t_{\text{triv}} = 7错误之前。
在我们的实际实验中，我们只对形如“RS 码字+ + 6 个随机错误”的y y进行采样，观察到列表大小在40 40到55 55之间，平均约为48 48。这恰好高于理论下限\approx 40 ≈ 40 ，正如你所预期的那样：我们看到了列表大小爆炸的有限大小的具体表现，而在这个范围内，简单的(1-\delta)n \le k ( 1 − δ ) n ≤ k论证不再适用。
实验结果
经过 20 多次独立实验（随机码字、随机 6 稀疏错误、半径为 6 的暴力列表解码），我们得到：
Field size q = 13n = 12, k = 5, rate rho = 0.416667delta = 0.500000(1 - delta)*n = 6.000 vs k = 5-> (1 - delta)*n > k (OUT of the trivial interpolation regime)H_q(delta) ≈ 0.7546351 - H_q(delta) ≈ 0.245365 (capacity rate at this delta)rho - (1 - H_q(delta)) ≈ 0.171302 (above capacity)eta = rho + H_q(delta) - 1 ≈ 0.171302Refined Elias-style counting bound:E_y[|B(y, δn) ∩ C|] ≥ q^{n(ρ + H_q(δ) - 1)} / sqrt(8 n δ (1-δ))For these parameters that is ≥ 194.91 / 4.90 ≈ 39.79Random corrupted codewords and their list sizes:trial 0: s = 6, distance ≤ 6, list size = 47trial 1: s = 6, distance ≤ 6, list size = 48trial 2: s = 6, distance ≤ 6, list size = 45trial 3: s = 6, distance ≤ 6, list size = 49trial 4: s = 6, distance ≤ 6, list size = 53trial 5: s = 6, distance ≤ 6, list size = 46trial 6: s = 6, distance ≤ 6, list size = 42trial 7: s = 6, distance ≤ 6, list size = 47trial 8: s = 6, distance ≤ 6, list size = 50trial 9: s = 6, distance ≤ 6, list size = 53trial 10: s = 6, distance ≤ 6, list size = 50trial 11: s = 6, distance ≤ 6, list size = 47trial 12: s = 6, distance ≤ 6, list size = 52trial 13: s = 6, distance ≤ 6, list size = 43trial 14: s = 6, distance ≤ 6, list size = 46trial 15: s = 6, distance ≤ 6, list size = 49trial 16: s = 6, distance ≤ 6, list size = 48trial 17: s = 6, distance ≤ 6, list size = 49trial 18: s = 6, distance ≤ 6, list size = 55trial 19: s = 6, distance ≤ 6, list size = 48Observed list sizes: [47, 48, 45, 49, 53, 46, 42, 47, 50, 53, 50, 47, 52, 43, 46, 49, 48, 49, 55, 48]max list size = 55avg list size = 48.35结论
这个小小的 RS 玩具示例只是一个健全性检验：在介于平凡插值阈值和 Elias 界限之间的参数下，一个汉明球已经包含数十个码字，正如 Elias 分析所预测的那样，并且与任何“高达 $1-\rho$”的说法相矛盾。
我使用的代码如下：
https://github.com/asanso/ca/blob/50b6cfb4c3986a7695aa91401963b0ccf60eb986/elias-bound-toy.py
如果你想加入数值模拟大军，可以调整参数，进行更大规模的实验，看看你的数据点是否支持“埃利亚斯下方没有爆炸”的说法，或者反驳这种说法。
致谢
我非常感谢Giacomo Fenzi 的多次有益讨论，他耐心地调试我的玩具实验，并一直督促我将“等等，这个列表真的要爆炸了吗？”这个问题转化为可复现且（希望）可读的内容；同时，我也要感谢Alistair Stewart 、 George Kadianakis和Benedikt Wagner 的认真校对和有益建议。
