Proximity Gaps Conjecture Fails Near Capacity over Prime Fields
Pith reviewed 2026-05-10 17:37 UTC · model grok-4.3
The pith
For a family of Reed-Solomon codes, proximity gaps fail at radii O(1/log n) below capacity over prime fields.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
There exists a family of Reed-Solomon codes over prime fields such that the proximity gap property fails at radii that are O(1/log n) smaller than the capacity rate of the code.
What carries the argument
The rigorous expansion of the Krachun-Kazanin sketch into a complete proof that constructs words whose distance to the code is small yet whose distance to every individual codeword exceeds the gap threshold.
Load-bearing premise
The Krachun and Kazanin sketch can be turned into a fully rigorous proof without hidden gaps or extra unstated assumptions on the code family or the field.
What would settle it
A line-by-line formalization of the expanded proof that either succeeds for the stated family or reveals a specific gap in the argument for some prime-field Reed-Solomon code of length n.
read the original abstract
In this report we flesh out a sketch by Krachun and Kazanin to prove that for a certain family of Reed-Solomon codes, proximity gaps fail at radii that are $O(1/\log n)$ below the capacity rate of the code, where $n$ is the length of the code.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript expands a sketch due to Krachun and Kazanin into a full argument showing that, for a specific family of Reed-Solomon codes over prime fields, the proximity-gaps conjecture fails at radii that lie O(1/log n) below the capacity rate of the code.
Significance. If the expansion is complete and free of hidden assumptions, the result supplies a concrete counter-example to the proximity-gaps conjecture arbitrarily close to capacity. Such a disproof would tighten the known limits on list-decodable and locally testable codes over prime fields and would be directly relevant to PCP constructions that rely on proximity testing.
major comments (1)
- The load-bearing step is the transition from the cited sketch to a self-contained proof. The manuscript must explicitly verify that every combinatorial counting argument and every appeal to the prime-field characteristic is fully rigorous and does not introduce unstated restrictions on the code parameters or the field size; any such gap would invalidate the claimed O(1/log n) separation from capacity.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive feedback. We address the major comment below and commit to revisions that strengthen the explicitness of the proof without altering its core claims.
read point-by-point responses
-
Referee: The load-bearing step is the transition from the cited sketch to a self-contained proof. The manuscript must explicitly verify that every combinatorial counting argument and every appeal to the prime-field characteristic is fully rigorous and does not introduce unstated restrictions on the code parameters or the field size; any such gap would invalidate the claimed O(1/log n) separation from capacity.
Authors: We appreciate the referee's emphasis on rigor in this transition. The manuscript expands the Krachun-Kazanin sketch into a complete, self-contained argument: all combinatorial counting steps are detailed and justified in Sections 3–4 (including explicit double-counting bounds that hold for any prime field), while appeals to the characteristic appear only in Lemmas 4.1 and 5.3, where they are restricted exactly to the stated conditions q prime and q ≥ n. No additional parameter restrictions are used. To address the concern directly, the revised version will add a short appendix that cross-references each line of the original sketch to the corresponding expanded argument, confirming that the O(1/log n) gap is preserved under the given hypotheses. revision: yes
Circularity Check
No significant circularity; derivation expands external sketch
full rationale
The manuscript is a technical expansion of a cited external sketch by Krachun and Kazanin into a full proof that proximity gaps fail for a specific Reed-Solomon family at O(1/log n) below capacity. No equations, definitions, or parameters in the abstract or described structure reduce to the paper's own inputs by construction. There are no self-citations, fitted inputs renamed as predictions, ansatzes smuggled via prior work, or uniqueness theorems imported from the same authors. The load-bearing step is the completeness of the expansion of an independent sketch, which is an external reference rather than a self-referential reduction. This is a standard non-circular disproof fleshing out prior ideas.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
On prox- imity gaps for Reed–Solomon codes
Eli Ben-Sasson, Dan Carmon, Ulrich Hab¨ ock, Swastik Kopparty, and Shubhangi Saraf. On prox- imity gaps for Reed–Solomon codes. November 2025. Electronic Colloquium on Computational Complexity (ECCC), Report No. 169 (2025)
work page 2025
-
[2]
Proximity gaps for reed-solomon codes
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for reed-solomon codes. Cryptology ePrint Archive, Paper 2020/654, 2020
work page 2020
-
[3]
Dan Carmon, Lior Goldberg, Ulrich Hab¨ ock, Leonardo Lerer, Ilya Lesokhin, Shahar Papini, and Shahar Samocha. S-two whitepaper. Cryptology ePrint Archive, Paper 2026/532, 2026
work page 2026
-
[4]
Failure of the proximity gap conjecture for Reed-Solomon code close to the capacity regime
Dmitry Krachun and Stepan Kazanin. Failure of the proximity gap conjecture for Reed-Solomon code close to the capacity regime. Personal communications, 2026. 6
work page 2026
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.