Paper 2026/782

Failure of proximity gaps close to capacity

Abstract

We give a simple counterexample which shows that, for Reed--Solomon codes over multiplicative subgroups of prime fields, proximity gaps do not hold near capacity, at least not as conjectured by Ben-Sasson, et al., in BCIKS20. For relative distance $\theta = 1-\rho-\eta$, where $\rho$ is the rate of the code, and positive $\eta = \Theta_\rho(1/\log n)$, where $n$ is the length of the code, we construct an affine line that is not entirely $\theta$-close to the code but still contains $2^{\Omega_\rho(1/\eta)}$ such points. The same construction gives a slightly stronger list-decoding lower bound. The proof uses a new additive-combinatorics lemma on sums of roots of unity.

Note: added acknowledgments