在以太坊社區的“鄰近性獎”（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 的認真校對和有益建議。
