On Proximity Gaps for One-Point Algebraic Geometric Codes

Abstract

Proximity gaps and correlated agreement underpin the soundness of interactive oracle proofs. We establish these properties for general one-point algebraic geometry (AG) codes, extending corresponding results for Reed-Solomon codes. For codes of length $n$ over ${\mathbb{F}}_q$ with designed distance $n-m$, write $\rho =m/n$ and fix $\rho \in (0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\epsilon <1$, we prove correlated agreement with multiplicative slack $\epsilon$ and soundness $O(\ell (\ell +1)/(\epsilon q))$ whenever $e\le (1-\epsilon )(n-m)/2$, with no additional genus penalty. This gives asymptotically good AG code families from Garcia--Stichtenoth tower of unbounded length over a fixed field with soundness bounds independent of $n$, beyond the RS restriction $n\le q$. We also establish mutual correlated agreement up to radius $(1-\sqrt{\rho }-\eta )n$, with soundness $O(\ell n/({\eta }^{3}q))$ for $0<\eta <1-\sqrt{\rho }$. Our half designed distance proof combines auxiliary divisors, simultaneous Berlekamp-Welch interpolation, and error-incidence counting to obtain a common polynomial representation without a Polishchuk-Spielman divisibility lemma. Finally, two counterexamples on the Garcia-Stichtenoth tower show limitations beyond half the minimum distance, at radii below the Johnson bound and with positive slack. The first requires a positive constant soundness lower bound independent of $q$ and $n$, precluding a uniform $O(1/q)$ guarantee throughout the Johnson regime. The second fixes the field and lets the relative gap above half distance tend to zero while ruling out correlated agreement for every soundness parameter $\sigma <1$, with positive limiting rate and relative error radius.

arXiv comment43 pages