Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions
Abstract
In this paper, we study the performance of algebraic geometry (AG) codes against adversarial insertion-deletion (insdel) errors. The half-Singleton bound states that an [n,k]q linear code can correct at most n−2k+1 insdel errors. It was recently proven that random Reed-Solomon codes approach this bound. However, these constructions require the field size q to grow linearly with the code length n. We overcome this barrier by extending the probabilistic analysis of general linear insdel codes to AG codes. We demonstrate that curves with many rational points allow for nearly optimal codes over significantly smaller alphabets. We prove the following main asymptotic results: (1) For general smooth complete curves of fixed genus, random AG codes are nearly optimal, that is, they can correct (1−ε)n−2k insdel errors with high probability over linear-sized fields (q=Θ(n)). (2) By utilizing Hermitian curves, we achieve this optimality over sublinear fields of size q=Θ(n2/3), breaking the linear field size barrier. (3) Using asymptotically optimal García-Stichtenoth towers, we prove the existence of random AG codes that approach the half-Singleton bound with high probability over fields of size q=2OR(1/ε2), independent of n.
Related
- Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size
- On the Average List Size of VT Codes under Two Insertions or Two Deletions
- Easy detection of CRISPR/Cas9-Induced Insertions, Deletions, and Substitutions in Rice Genes OsMADS26, OsRAC1 and OsNRT1.1b using SYBR Green qPCR and Robust HRM analysis in R software
- Explicit and asymptotically good constructions of Algebraic Geometry codes in the sum-rank metric
- Algebraic Magnetism: X-products of attractors via 𝔽1-geometry
BibTeX
@misc{guan2026random,
title = {{Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions}},
author = {Zhihao Guan and Hengjia Wei},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06441},
eprint = {2609.06441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06441},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions
AU - Zhihao Guan
AU - Hengjia Wei
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06441
UR - https://arxiv.org/abs/2609.06441
AB - In this paper, we study the performance of algebraic geometry (AG) codes against adversarial insertion-deletion (insdel) errors. The half-Singleton bound states that an [n,k]_q linear code can correct at most n−2k+1 insdel errors. It was recently proven that random Reed-Solomon codes approach this bound. However, these constructions require the field size q to grow linearly with the code length n. We overcome this barrier by extending the probabilistic analysis of general linear insdel codes to AG codes. We demonstrate that curves with many rational points allow for nearly optimal codes over significantly smaller alphabets. We prove the following main asymptotic results: (1) For general smooth complete curves of fixed genus, random AG codes are nearly optimal, that is, they can correct (1−ε)n−2k insdel errors with high probability over linear-sized fields (q=Θ(n)). (2) By utilizing Hermitian curves, we achieve this optimality over sublinear fields of size q=Θ(n^2/3), breaking the linear field size barrier. (3) Using asymptotically optimal García-Stichtenoth towers, we prove the existence of random AG codes that approach the half-Singleton bound with high probability over fields of size q=2^O_R(1/ε^2), independent of n.
ER -