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 𝔽q with designed distance n−m, write ρ=m/n and fix ρ∈(0,1). For polynomial curves of degree at most ℓ and any 0<ε<1, we prove correlated agreement with multiplicative slack ε and soundness O(ℓ(ℓ+1)/(ε q)) whenever e≤(1−ε)(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≤ q. We also establish mutual correlated agreement up to radius (1−√ρ−η)n, with soundness O(ℓ n/(η3q)) for 0<η<1−√ρ. 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.
Related
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
- Proximity Gaps for Gabidulin Codes and Applications
- Best proximity point results of operator type condensing mappings via measure of noncompactness and application to an infinite system of differential equations in c0 and ℓ1
- Explicit and asymptotically good constructions of Algebraic Geometry codes in the sum-rank metric
BibTeX
@misc{li2026proximity,
title = {{On Proximity Gaps for One-Point Algebraic Geometric Codes}},
author = {Songsong Li and Chaoping Xing and Chen Yuan and Ruiqi Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39256},
eprint = {2610.39256},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39256},
}
RIS
TY - UNPB
TI - On Proximity Gaps for One-Point Algebraic Geometric Codes
AU - Songsong Li
AU - Chaoping Xing
AU - Chen Yuan
AU - Ruiqi Zhu
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39256
UR - https://arxiv.org/abs/2610.39256
AB - 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 𝔽_q with designed distance n−m, write ρ=m/n and fix ρ∈(0,1). For polynomial curves of degree at most ℓ and any 0<ε<1, we prove correlated agreement with multiplicative slack ε and soundness O(ℓ(ℓ+1)/(ε q)) whenever e≤(1−ε)(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≤ q. We also establish mutual correlated agreement up to radius (1−√ρ−η)n, with soundness O(ℓ n/(η^3q)) for 0<η<1−√ρ. 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.
ER -