Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size
Abstract
We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap ε from 2O(1/ε2) to 2O(1/ε). Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.
Related
- Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions
- Explicit and asymptotically good constructions of Algebraic Geometry codes in the sum-rank metric
- Hyper-derivative Algebraic Geometry Codes via Local Expansions
- MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves
- Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus
BibTeX
@misc{verma2026algebraic,
title = {{Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size}},
author = {Neehar Verma and Camilla Hollanti and Razane Tajeddine},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05017},
eprint = {2609.05017},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05017},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size
AU - Neehar Verma
AU - Camilla Hollanti
AU - Razane Tajeddine
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05017
UR - https://arxiv.org/abs/2609.05017
AB - We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap ε from 2^O(1/ε^2) to 2^O(1/ε). Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.
ER -