Proving reliability limits for algebraic geometry codes in error correction
On Proximity Gaps for One-Point Algebraic Geometric Codes
Information Theory
Summary
Decoding error-correcting codes is like fixing mistakes in a message. This work studies a class of codes called algebraic geometry (AG) codes, which are more complex than simpler Reed-Solomon codes. The authors prove new guarantees about when these codes can reliably identify errors under certain conditions, even for very long codes over fixed finite fields. They also find examples showing limits to these guarantees, meaning that for some error levels, reliable error correction cannot be assured.
What this means in practice
- •For error correction engineers: Use soundness bounds to design AG code decoders that reliably detect errors in long codes over fixed-size fields beyond previous length limits.
- •For cryptography system builders: Apply the proven correlated agreement properties to verify soundness in interactive proof protocols using AG codes for scalable secure computations.
A theory result. No direct application yet.
Authors
Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu
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 $ρ=m/n$ and fix $ρ\in(0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\varepsilon<1$, we prove correlated agreement with multiplicative slack $\varepsilon$ and soundness $O(\ell(\ell+1)/(\varepsilon q))$ whenever $e\le(1-\varepsilon)(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ρ-η)n$, with soundness $O(\ell n/(η^3q))$ for $0<η<1-\sqrtρ$. 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 $σ<1$, with positive limiting rate and relative error radius.