PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions

Zhihao Guan, Hengjia Wei

arXiv:2609.06441v1cs.ITmath.IT

TL;DR

Insertion and deletion errors disrupt symbol positions, and random Reed–Solomon codes approaching the half-Singleton bound require fields that grow linearly with code length. The paper extends probabilistic analysis to AG codes, showing that random codes from suitable curves approach the bound over linear, sublinear, and block-length-independent field sizes.

  • Problem

    Insertions and deletions disrupt symbol positions, and random Reed–Solomon codes approaching the half-Singleton bound require fields larger than the code length.

    Source: §I · p. 1

  • Method

    The paper extends probabilistic analysis of insdel codes to AG codes built from curves with many rational points.

    Source: A. Our Results · p. 2

  • Results

    Random AG codes approach the half-Singleton bound with high probability over linear-sized fields for fixed-genus curves, sublinear-sized fields for Hermitian curves, and fields independent of block length for tower families.

    Source: A. Our Results · p. 2

  • Takeaways & Limitations

    Structured linear codes can approach the half-Singleton bound even when alphabet size does not grow with block length.

    Source: A. Our Results · p. 2

Abstract

from arXiv · show

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-\varepsilon)n-2k$ insdel errors with high probability over linear-sized fields ($q=\Theta(n)$). (2) By utilizing Hermitian curves, we achieve this optimality over sublinear fields of size $q=\Theta(n^{2/3})$, breaking the linear field size barrier. (3) Using asymptotically optimal Garc\'{i}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/\varepsilon^2)}$, independent of $n$.

I. INTRODUCTION

Insertions and deletions destroy positional information, while Reed–Solomon approaches to the half-Singleton bound require fields larger than the code length. This paper extends probabilistic analysis to AG codes and shows how curves with many rational points support near-optimal codes over smaller fields.

A. Our Results

  • With probability tending to one, random AG codes approach the half-Singleton bound over linear-sized fields for fixed-genus curves, sublinear-sized fields for Hermitian curves, and fields independent of block length for tower families.The respective guarantees correct (1 − ε)n − 2k insdel errors; the tower result is for fixed rate and ε.Source: A. Our Results · p. 2

B. Our Approach and Related Work

  • An irreducible variety is HS-optimal if and only if it is an MDS variety, reducing the optimality question to determinant conditions on varieties.The approach targets the half-Singleton bound over fields smaller than those required by Reed–Solomon codes.Source: B. Our Approach and Related Work · p. 2
  • The probabilistic framework estimates rank-failure probabilities using rank certification and geometric estimates of rational points where generic determinants vanish.The framework applies to random linear codes whose generator-matrix columns are sampled from rational points of an MDS variety over a finite field.Source: B. Our Approach and Related Work · p. 2
  • Suitable AG-code generator matrices can be represented by sampling points from affine MDS curves, so curves with enough rational points yield linear-, sublinear-, and constant-size field regimes.The paper relates this application to prior AG-code work on list decoding and higher-order MDS codes, while focusing here on insdel errors.Source: B. Our Approach and Related Work · pp. 2–3

C. Organization

  • The paper develops code bounds and algebraic foundations, proves the variety characterization, builds a probabilistic framework, and applies it to three AG-curve families.The families are smooth complete fixed-genus curves, Hermitian curves, and the García–Stichtenoth tower.Source: C. Organization · p. 3

II. PRELIMINARIES

This section establishes the notation and basic linear-algebra conventions used throughout the paper.

  • For a positive integer n, [n] denotes {1,...,n}; N and N+ denote the nonnegative and positive integers, respectively.Source: §II · p. 3
  • Fq denotes a finite field with q elements, while F may be a finite or infinite field and F^n is an n-dimensional vector space over F.Source: §II · p. 3
  • For vectors and matrices, restricting to an index set selects the corresponding coordinates or columns; full row or column rank means rank equals the number of rows or columns.Source: §II · p. 3

A. Codes and the Half-Singleton Bound

This section sets out the insdel distance and half-Singleton benchmarks, then gives rank-based conditions for certifying codes that meet or approach those benchmarks.

A. Codes and the Half-Singleton Bound

B. Algebraic Preliminaries

The section reviews varieties and generic non-vanishing, then introduces formal power series and specialization tools used in the probabilistic analysis.

B. Algebraic Preliminaries

  • An affine variety is the common zero set of an ideal; its vanishing ideal is radical, and irreducibility is equivalent to that ideal being prime.Source: B. Algebraic Preliminaries · p. 5
  • On an irreducible variety, a polynomial is generically non-vanishing exactly when it is nonzero as an element of the coordinate ring.Source: B. Algebraic Preliminaries · p. 5
  • Products of irreducible varieties remain irreducible, and a polynomial non-vanishing generically on a product can be specialized while controlling degree in one variable group.The specialized polynomial remains generically non-vanishing when the chosen point avoids the stated exceptional polynomial.Source: B. Algebraic Preliminaries · p. 6
  • Formal power series locally parameterize an irreducible variety so generic non-vanishing can be tested after substitution; separate variable tuples extend this test to product varieties.Source: B. Algebraic Preliminaries · p. 6

III. MDS VARIETIES AND HALF-SINGLETON OPTIMALITY

An irreducible variety is HS-optimal if and only if it is MDS, linking generic code optimality under the Singleton and half-Singleton bounds.

III. MDS VARIETIES AND HALF-SINGLETON OPTIMALITY

  • An irreducible variety is HS-optimal if and only if it is MDS, so generic points generate codes optimal under both the Singleton and half-Singleton bounds.Source: §III · p. 6

A. Half-Singleton Optimality on Varieties

The section characterizes half-Singleton optimality geometrically: an irreducible variety is HS-optimal exactly when it is MDS. It also connects the all-one codeword condition to whether the variety lies in an affine hyperplane.

A. Half-Singleton Optimality on Varieties

  • An MDS variety is one whose generic column matrices generate MDS codes for every n >= k.The section relates this property to generic full row rank and avoidance of hyperplanes through the origin.Source: A. Half-Singleton Optimality on… · p. 6
  • For generic columns from an irreducible MDS variety, the generated code contains the all-one word exactly when the variety lies in an affine hyperplane.The variety's containment in a hyperplane through the origin instead characterizes failure of full row rank.Source: A. Half-Singleton Optimality on… · p. 6
  • An irreducible variety is MDS if and only if it is HS-optimal, characterizing when generic columns attain the half-Singleton bound.The proof reduces the converse to nonvanishing verification determinants.Source: A. Half-Singleton Optimality on… · p. 7
  • The proof transfers generic nonvanishing through formal power series, univariate monomials, and verification determinants on the variety.The reductions establish the determinant conditions needed for the MDS-to-HS-optimal direction.Source: A. Half-Singleton Optimality on… · p. 7

B. Reduction to Power Series

The reduction represents geometric properties using tuples of formal power series and tests them through determinant conditions. MDS tuples satisfy the HS-optimal conditions, enabling the transfer back to varieties.

B. Reduction to Power Series

  • A tuple of power series is MDS exactly when its component series are linearly independent.The associated evaluation matrix places each series' values at the variables z1 through zn in a row.Source: B. Reduction to Power Series · p. 7
  • The HS-optimal definition requires nonzero verification determinants for subsequence pairs with fewer than k shared indices, with separate cases depending on whether 1 lies in the tuple's span.When 1 is in the span, the tuple can be transformed to include the constant series 1.Source: B. Reduction to Power Series · pp. 7–8
  • Every MDS tuple of power series is HS-optimal.Linear dependence would force the corresponding verification matrices to have zero determinant.Source: B. Reduction to Power Series · p. 8
  • The reduction transfers determinant nonvanishing from power series to generic points on an irreducible MDS variety, proving that the variety is HS-optimal.The proof also connects membership of 1 in the series span to containment of the variety in an affine hyperplane.Source: B. Reduction to Power Series · p. 8

C. Reduction of Power Series to Univariate Monomials

The proof reduces MDS power series to univariate monomials by selecting independent leading terms and using weighted substitutions. It then handles standard and strict verification determinants through corresponding monomial cases.

C. Reduction of Power Series to Univariate Monomials

  • Independent leading terms allow a change of basis that makes each series' leading monomial distinct, reducing the problem to monomials.A weighted substitution maps multivariate series to univariate ones while preserving those leading terms.Source: C. Reduction of Power Series to… · pp. 8–9
  • It suffices to establish HS-optimality for tuples (1, t^e1, ..., t^e(k-1)) and (t^e1, ..., t^ek) with distinct positive exponents.These are the base cases for the standard and strict cases, respectively.Source: C. Reduction of Power Series to… · p. 8
  • Positive integer weights can preserve the selected leading monomials under substitution of each variable by a power of t.The weights are chosen so the leading exponents remain ordered and later monomials have greater weight.Source: C. Reduction of Power Series to… · p. 9
  • The standard-case determinants are nonzero by the first monomial assumption, and the strict case follows from the strict monomial case or a leading determinant of the first type.When constant terms vanish, the lowest-degree coefficient is the strict verification determinant; otherwise, row subtraction isolates a standard verification determinant.Source: C. Reduction of Power Series to… · p. 9

D. Monomial Codes

Generic Reed-Solomon codes and more general monomial codes satisfy the required half-Singleton determinant conditions. This establishes the base cases used to extend optimality beyond Reed-Solomon constructions.

D. Monomial Codes

  • A generic Reed-Solomon code is HS-optimal, and its generic evaluation variables can be specialized to distinct finite-field elements.The generic code is defined over the fraction field of a polynomial ring in algebraically independent evaluation variables.Source: D. Monomial Codes · p. 10
  • Monomial codes are HS-optimal when e1 = 0 and strict HS-optimal when e1 > 0.The generators are distinct monomials with increasing exponents.Source: D. Monomial Codes · p. 10
  • The monomial determinant proof uses induction on k, deleting positions from subsequences to reduce to a smaller verification determinant.The resulting determinant is nonzero by the induction hypothesis, establishing the standard case; the strict case follows similarly.Source: D. Monomial Codes · p. 10

IV. PROBABILISTIC ANALYSIS OF RANDOM CODES ON MDS VARIETIES

The section moves from generic-point results to finite-field constructions, where evaluation points must be rational. It sets up random sampling from rational points and distinguishes varieties contained in an affine hyperplane from those that are not.

IV. Probabilistic Analysis of Random Codes on MDS Varieties

  • Generic points over an infinite field do not provide a practical finite-field construction, motivating a focus on rational points over Fq.The section identifies finite-field rational points as the sampling domain for practical codes.Source: §IV · p. 11
  • The goal is to preserve optimal performance asymptotically with high probability by sampling generator-matrix columns uniformly from rational points.The framework treats the affine-hyperplane case by normalizing the hyperplane to {x1 = 1}; the strict case has no such normalization.Source: §IV · p. 11
  • The analysis distinguishes the standard case, where the variety lies in an affine hyperplane, from the strict case, where it does not.In the standard case, an invertible coordinate change preserves rank conditions while normalizing the hyperplane.Source: §IV · p. 11

A. Probabilistic Analysis of Random Codes

The section bounds failure probabilities for randomly sampled codes on MDS varieties by analyzing rank failures across pairs of subsequences. For affine curves, Bezout-based estimates yield a specialization, including a sharper case when the curve degree is below k + τ.

A. Probabilistic Analysis of Random Codes

  • For fixed subsequences with intersection size below k, Lemma IV.2 bounds failure of full row rank in the verification matrix.The lemma applies to lengths ℓ between ℓ′ − τ and ℓ′; its displayed bound is not present in the supplied passage.Source: A. Probabilistic Analysis of Random… · p. 11
  • Theorem IV.3 gives a success-probability bound for ε-relaxed HS-optimality by combining failure estimates across subsequence pairs.The proof applies a union bound to the failure events and derives the stated success bound.Source: A. Probabilistic Analysis of Random… · pp. 11–12
  • The failure analysis separates pairs with small, intermediate, and large intersections, using rank-failure probabilities for the large-intersection case.For the large-intersection case, failure of the intersection rank implies that a sampled k × (k + τ) submatrix is singular.Source: A. Probabilistic Analysis of Random… · p. 12
  • For affine curves of degree d, the corollary specializes the general theorem using curve-specific estimates based on Bezout’s theorem.Bezout’s theorem bounds the number of zeros of a generically non-vanishing polynomial on the curve.Source: A. Probabilistic Analysis of Random… · pp. 12–13
  • When d < k + τ, the rank-failure probability p_{k+τ}(S) is zero, giving the sharper case in the affine-curve corollary.The corollary states a probability bound for ε-relaxed HS-optimality, with a separate bound when d < k + τ.Source: A. Probabilistic Analysis of Random… · p. 13

B. Chain Decomposition and Rank Certification

This section develops and analyzes a chain-based rank-certification method for pairs of increasing subsequences, using generic determinant non-vanishing and sequential exposure to bound certification failures. It then uses monotonicity of output sequences to limit the number included in the final union bound.

B. Chain Decomposition and Rank Certification

  • For a fixed failed-test sequence, fresh disjoint chains yield conditional failure bounds through Pq(X, 2); a union bound over sequences and pairs (I, J) gives Lemma IV.2’s probability estimate.The bound counts rational points of X where specialization can fail, adapting the chain-replacement strategy of [26] to codes from points on an MDS variety.Source: B. Chain Decomposition and Rank… · p. 13
  • Lemma IV.10 [26] partitions at least (1−ε0)ℓ positions into mutually disjoint chains, each of size at most 1/ε0.The chains are ordered so reserve-bank chains can replace primary-queue chains without being smaller.Source: B. Chain Decomposition and Rank… · p. 14
  • A reserve bank chosen from the last chains has total size in [r/ε0, (r + 1)/ε0] and contains at least r chains for possible replacements.The remaining chains still provide enough positions for the h verification columns.Source: B. Chain Decomposition and Rank… · p. 14
  • The procedure tests chains by specializing their variables and checking generic non-vanishing; successful tests advance toward full row rank, while failures trigger replacement from a reserve bank [26].It terminates with either a full-row-rank certificate or a sequence of r failed-test indices.Source: B. Chain Decomposition and Rank… · pp. 15–16
  • The relevant determinant is generically non-vanishing on X and has degree at most 2 in each column variable Gi.Generic non-vanishing follows from HS-optimality, and the degree bound follows because each generator column occurs at most twice.Source: B. Chain Decomposition and Rank… · p. 16
  • Replacing a chain preserves generic non-vanishing because the old and new determinants differ only by relabeling variables and possibly a column permutation, up to sign.The argument covers Type II chains with matching or opposite orientations and the case where the old chain is Type I.Source: B. Chain Decomposition and Rank… · p. 17
  • At each step, conditioning on previously exposed points leaves the current chain's points uniform among at least |S| − n remaining points, while the determinant has degree at most 2 in each variable.The chain exposes at most 1/ε0 + 1 points; a union bound controls failure of generic non-vanishing across their successive specializations.Source: B. Chain Decomposition and Rank… · pp. 17–18
  • If the matrix does not have full row rank, Algorithm 1 outputs a sequence (i1, ..., ir) in {0, ..., h − 1}^r; every output sequence satisfies i1 ≤ ... ≤ ir.Source: B. Chain Decomposition and Rank… · p. 18

V. APPLICATION TO AG CODES

The section realizes AG codes as codes generated by points on affine MDS curves, then applies probabilistic bounds to obtain half-Singleton-optimality results. It gives guarantees for fixed-genus, Hermitian, and Garceda-Stichtenoth curve families in distinct field-size regimes.

AG-code construction

  • The image of ψ is an irreducible MDS affine curve Y of degree d; for distinct P_i in X(Fq) excluding P, ψ(P_i)^T are generator-matrix columns, and ψ preserves uniform sampling without replacement on eligible subsets.Source: §V · p. 19
  • For n ≥ 2k, a generic tuple of evaluation points gives an HS-optimal code under the stated construction assumptions.The section also restricts to one-point divisors, which it says suffice for the families used in its results.Source: §V · p. 19

Random AG codes on curves

  • The random-code theorem applies when the genus is at most τ and the evaluation-point set has more than n elements, among its stated conditions.It gives ε-relaxed HS-optimality with a probability bound for uniformly sampled evaluation points.Source: §V · p. 19

Fixed-genus curves

  • For a smooth complete genus-g curve X over Fq, CL(X,P,D), with D=(k+g−1)P and S=X(Fq)\{P}, has rate R and is ε-relaxed HS-optimal with probability at least 1−2^-n when P is sampled uniformly without replacement from S.Source: §V · p. 20

Reed-Solomon example

  • On the projective line, the construction specializes to random punctured Reed-Solomon codes that are ε-relaxed HS-optimal with high probability for q = Θ(n).The paper notes that this result was also proved in [26].Source: §V · p. 20

a) Sublinear Fields via Hermitian Curves

  • For Hermitian curves with q = Θ(n^{2/3}), random AG codes of rate below (1 − ε)/2 approach the half-Singleton bound with probability tending to 1.The theorem states ε-relaxed HS-optimality with probability at least 1 − 2^-n.Source: §V · pp. 20–21

b) Constant Field Sizes: The Garceda-Stichtenoth Tower

  • Over fixed fields Fp², an infinite family of random AG codes of rate R is ε-relaxed HS-optimal with probability at least 1 − 2^-n_t for sufficiently large lengths n_t.The chosen p satisfies p = 2^{O_R(1/ε²)}, so the field size is independent of n_t.Source: §V · pp. 21–22

APPENDIX A LEMMA II.5

The appendices establish a shortening property for strict HS-optimal codes, a polynomial specialization lemma, and a curve embedding used to construct an MDS curve while preserving rational-point sampling.

APPENDIX A LEMMA II.5

  • Shortening a HS-optimal code yields a strict HS-optimal code with parameters reflected by dI(C′) ≥ 2((n−1)−2(k−1)+1).The proof also rules out 1n−1 ∈ C′.Source: Appendix A · p. 22

APPENDIX B LEMMA II.12

  • From f generically non-vanishing on X × Y, a coefficient polynomial g is generically non-vanishing on X, has degree at most degx(f), and certifies generic non-vanishing of f(x, y) on Y wherever g(x) ≠ 0.The proof obtains g by substituting formal power series for the y-coordinates and selecting a nonzero coefficient.Source: Appendix B · p. 23

APPENDIX C DETAILS OF PROVING LEMMA V.3

  • For deg(D) ≥ 2g + 1, the linear-system map embeds X; in the proof of Lemma V.3, its image has degree d and is irreducible and nondegenerate.The image of P is a point at infinity.Source: Appendix C · p. 24
  • The affine lift Y preserves degree and is an MDS curve, while ψ bijectively maps rational-point subsets onto Y and preserves uniform sampling without replacement.The affine image is obtained from the curve away from P.Source: Appendix C · p. 24
Loading 2609.06441v1…