Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

Neehar Verma; Camilla Hollanti; Razane Tajeddine

Source-linked AI summary

Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

Neehar Verma, Camilla Hollanti, Razane Tajeddine

arXiv:2609.05017v1Sep 4, 2026cs.ITcs.DSmath.CO

TL;DR

Linear codes for insertion and deletion errors face alignment challenges and a half-Singleton rate limitation, motivating structured constructions with strong insdel guarantees. This paper develops a general random-puncturing framework for evaluation codes, simplifies prior analysis, and applies it to Reed–Muller, Reed–Solomon, and algebraic geometry codes. It obtains constant-field randomized structured families approaching the half-Singleton bound while improving the Reed–Solomon additive-gap dependence.

Problem
The paper addresses whether structured linear codes can achieve strong insertion/deletion guarantees despite linearity's insdel rate constraint.
Method
It analyzes random puncturings of evaluation codes through the evaluation domain size and the maximum zero count of nonzero functions.
Results
Randomized families of structured linear codes over constant-sized fields approach the half-Singleton bound.
Takeaways & Limitations
The framework applies directly to algebraic geometry codes and improves the Reed–Solomon additive-gap dependence from 2^O(1/ε^2) to 2^O(1/ε).

Abstract

from arXiv · show

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 $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. 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.

I. Introduction

Insdel errors disrupt coordinate alignment and message length, making them harder to handle than substitutions or erasures. The introduction frames the challenge of achieving strong insdel guarantees with linear, structured codes, whose rate is constrained by the half-Singleton bound.

Insdel errors destroy alignment between transmitted and received coordinates and may change the transmitted message length.
Constant-sized alphabets admit explicit codes correcting a δ-fraction of insdel errors at rate 1−δ−ε.
Linearity is constrained for insdel correction: a linear code correcting one deletion has rate at most 1/2, unlike nonlinear codes with rate 1.
Linearity remains desirable because generator matrices provide compact representation and encoding, supporting algebraic families such as Reed–Solomon and algebraic geometry codes.
The half-Singleton bound asks whether structured linear codes can approach the universal insdel limit, especially over constant-sized fields.

A. Reed–Solomon codes

Reed–Solomon codes offer strong algebraic structure and efficient algorithms, but their insdel performance depends on the field size and remains less understood in higher dimensions. Prior random-code analyses use algebraic conditions tied to common subsequences, while efficient decoding near the half-Singleton bound remains open for general dimensions.

An [n,k]q Reed–Solomon code evaluates degree-bounded polynomials at n distinct field elements.
Reed–Solomon codes are MDS in the Hamming metric and have efficient algebraic encoding and decoding algorithms.
Two-dimensional Reed–Solomon codes can achieve the half-Singleton bound, correcting n−3 insdel errors.
Random Reed–Solomon codes approach the half-Singleton bound over linear-sized fields, extending interest beyond the well-understood two-dimensional regime.
Prior insdel proofs reduce the problem to algebraic conditions involving possible common subsequences and require structural LCS analysis plus specialized exposure procedures.
An existing efficient general decoder is not efficient close to the half-Singleton bound and corrects t errors only when tk=O(n), leaving general-dimensional efficient decoding open.

B. Our results

The paper develops a general random-puncturing framework for evaluation codes, then applies it to Reed–Muller, Reed–Solomon, and algebraic geometry codes. These applications yield new constant-fraction guarantees, improved Reed–Solomon dependence on ε, and structured constant-field families approaching the half-Singleton bound.

General framework: The framework controls edit distance using the evaluation-domain size and the maximum number of zeros of a nonzero function.A row-exposure argument bounds rank failures through fresh evaluation points and zero counts, making the bad event exponentially unlikely.
General framework: The proof uses a union bound over subsequence pairs after reducing edit distance to longest common subsequences, avoiding the previous proof’s involved LCS analysis.The same argument therefore applies to a broader class of evaluation codes.
Reed–Muller codes: For first-order binary Reed–Muller codes, random ordered length-n puncturings correct every fixed δ < 0.0376 with probability 1 − 2^-Ω(n).This applies to the full first-order RM code rather than specially chosen subcodes.
Reed–Solomon codes: For Reed–Solomon codes, the framework recovers the linear-field-size result and improves the additive-gap dependence from 2^O(1/ε^2) to 2^O(1/ε).The improvement follows because the Reed–Solomon zero parameter is Z = k−1.
Algebraic geometry codes: For every δ, ε > 0, randomized puncturings of algebraic geometry codes over a field size independent of block length approach the half-Singleton bound.Asymptotically good towers provide unbounded rational evaluation points over a fixed field, while the AG application uses Z = deg(G).
Algebraic geometry codes: The framework directly transfers the Reed–Solomon-to-algebraic-geometry transition from list decoding to insertion and deletion errors.The paper does not use the cited list-decoding results; it establishes the transition through its own general theorem.

II. Notation and preliminaries

This section fixes finite-field notation and defines linear codes through their length, dimension, and minimum distance. It also recalls the Singleton bound and maximum distance separable codes.

The paper writes F_q for the finite field with q elements and [n] = {1, …, n}.
An [n, k, d]_q linear code is a subspace of F_q^n with length n, dimension k, and minimum Hamming distance d.
The Singleton bound states d ≤ n − k + 1; codes meeting it are called maximum distance separable codes.

A. Preliminaries on insertion/deletion errors

The preliminaries relate edit distance to longest common subsequences and establish the linear-code half-Singleton limitation. They then reformulate insdel correction as an LCS condition.

The edit distance is the minimum number of insertions and deletions needed to transform one string into another.
The longest common subsequence is a subsequence shared by two strings with maximal length.
For strings s and s′, d_edit(s, s′) = |s| + |s′| − 2LCS(s, s′).This identity allows the paper to move between edit-distance and LCS formulations.
An [n, k] linear code cannot correct more than n − 2k + 1 insertion/deletion errors.
A code corrects a δ-fraction of insdel errors exactly when every pair of distinct codewords has LCS at most n − δn − 1.

B. Algebraic preliminaries

The algebraic preliminaries introduce curves, function fields, divisors, Riemann–Roch spaces, and algebraic geometry codes. They also recall an asymptotically good tower whose rational-point density reaches the Drinfeld–Vlăduţ bound.

A curve X over F_q has a function field F_q(X), and its rational points correspond one-to-one with rational places.
For a function f, the valuation v_P records the multiplicity of a zero or pole at a place P.
The Riemann–Roch space L(G) is a finite-dimensional F_q-vector space, and every nonzero f ∈ L(G) has at most deg(G) zeros counted with multiplicity.
An algebraic geometry code evaluates functions in L(G) at distinct rational points whose set is disjoint from the support of G.
The Garcia–Stichtenoth tower satisfies |P_q(Y_m)|/g_m → √q − 1 and attains the Drinfeld–Vlăduţ bound, giving an asymptotically good code family.

III. Randomly punctured evaluation codes for insertions/deletions

The section develops a general framework for controlling the edit distance of random puncturings of evaluation codes using the evaluation domain size and a bound on zeros of nonzero functions. A V-matrix rank condition connects long common subsequences to decoding failure, while row-exposure arguments bound rank deficiency.

The framework applies to finite-dimensional function spaces containing the constant function, including Reed–Solomon, algebraic geometry, Reed–Muller, and monomial Cartesian codes.
A Schwartz–Zippel-type parameter Z bounds the number of evaluation-domain zeros of every nonzero function in the underlying space.
A common subsequence of length ℓ yields a V-matrix with a nonzero kernel vector, so decoding failure implies that the matrix lacks full column rank.
The probability of rank deficiency is bounded by exposing rows sequentially and applying the zero bound to newly exposed variables, followed by a union bound.
Each V-matrix row exposes a fresh variable, and agreement rows can be moved first without destroying this property.

IV. Specializing to specific families of evaluation codes

The framework is instantiated for Reed–Muller, Reed–Solomon, and algebraic geometry codes. These applications include guarantees over growing fields and structured code families over constant-sized fields approaching the half-Singleton bound.

The framework yields results for Reed–Muller codes, Reed–Solomon codes, and algebraic geometry codes from asymptotically good function-field towers.
First-order binary Reed–Muller codes admit random puncturings correcting a constant fraction of insdel errors.
Random Reed–Solomon codes recover the linear field-size requirement while improving the dependence on the additive gap ε.
Algebraic geometry codes from the GS tower give structured randomized families over constant-sized fields approaching the half-Singleton bound.

A. Reed–Muller codes

The Reed–Muller instantiations provide insdel guarantees for general q-ary codes and constant-fraction guarantees for first-order binary codes, under explicit parameter regimes. The binary result follows from a random-puncturing distance bound combined with the general theorem.

General q-ary Reed–Muller codes: With probability at least 1 − 2^−n, random ordered puncturings correct at least (1 − ε)n − 2k + 1 insdel errors.
General q-ary Reed–Muller codes: For q-ary Reed–Muller codes, nonzero degree-r polynomials vanish on at most Z = r q^(m−1) evaluation points.
General q-ary Reed–Muller codes: The resulting q-ary Reed–Muller families use fields of size q = O(n^(1/m)) but are constrained to a low-rate regime.
First-order binary Reed–Muller codes: For first-order binary Reed–Muller codes, m = o(n), and random ordered length-n puncturings have minimum distance close to n/2 with probability 1 − 2^−Ω(μ^2 n).
First-order binary Reed–Muller codes: For every δ ∈ (0, δ′), where δ′ ≈ 0.0376, the binary puncturings correct at least ⌊δn⌋ insdel errors with probability at least 1 − 2^−Ω(n).

B. Reed–Solomon codes

The Reed–Solomon specialization applies the general theorem to low-degree univariate polynomials, whose nonzero members have at most k − 1 zeros. Random evaluation points then yield high-probability insdel correction approaching the half-Singleton regime.

An [n, k]q Reed–Solomon code evaluates polynomials of degree less than k at n distinct points of Fq and has minimum distance d = n − k + 1.
For Reed–Solomon codes, the zero bound is Z = k − 1 by the Schwartz–Zippel argument.
With ℓ = 2k − 1 + ⌊εn⌋, random distinct evaluation points produce the relevant decoding guarantee with probability at least 1 − 2^−n.
The resulting random Reed–Solomon code corrects at least (1 − ε)n − 2k + 1 insdel errors.
The Reed–Solomon result is also a special case of the broader framework with m = 1 and r = k − 1, eliminating the rate constraints in that corollary.

C. Algebraic geometry codes

The paper applies its general random-evaluation framework to algebraic geometry codes from an asymptotically optimal function-field tower, obtaining randomized structured linear codes over constant-sized fields that approach the half-Singleton bound.

Main result: The main result gives a randomized family of linear AG codes that achieves the half-Singleton bound over constant-sized fields.The framework is instantiated with structured codes rather than unrestricted random linear codes.
Construction: The construction uses AG codes from an asymptotically optimal tower of function fields, with evaluation points sampled uniformly from distinct rational points.The codes are defined using the Riemann–Roch space L(G) on the tower curves.
Proof framework: The proof applies the general theorem with X = P_q(Y_m) \ {P_∞}, function space L(G), and zero bound Z = deg(G).The divisor and Riemann–Roch dimension are selected so that ℓ(G) = k.
Error correction: With probability at least 1 − 2^-n, the resulting [n, k = Rn] AG code corrects at least (1 − ε)n − 2k + 1 insdel errors.The guarantee follows from the random choice of evaluation points.
Parameters: The field size is q = p^2 = 2^O(1/ε + log(1/R)), making the alphabet size independent of the block length.The parameters assume ε ∈ (0, 1) and R ∈ (0, 1/2).

V. Conclusions and future work

The conclusions emphasize a general framework for random puncturings, new Reed–Muller and Reed–Solomon consequences, and AG-code constructions over constant-sized fields. They also identify explicit constructions, efficient decoding, restricted-field settings, and list decoding as directions for future work.

Contributions: The paper presents a simple framework for analyzing random evaluation codes against insdel errors.The framework controls random puncturings through the evaluation-code viewpoint.
Reed–Muller codes: For first-order binary Reed–Muller codes, random puncturings achieve a constant-fraction insdel guarantee for the full code.This differs from results restricted to insdel-robust subcodes.
Algebraic geometry codes: Applying the same theorem to AG codes yields randomized families of structured linear codes over constant-sized fields approaching the half-Singleton bound.This extends the framework beyond Reed–Muller and Reed–Solomon instantiations.
Future work: Future work includes explicit constructions with efficient decoding, extensions to fixed or restricted field sizes, list-decodable codes, and generalized evaluation codes.The paper specifically notes that explicit constructions and accompanying efficient decoding algorithms remain open.