Source-linked AI summary
An extension of the order bound for AG codes
Iwan Duursma, Radoslav Kirov
TL;DR
Lower-bounding the minimum distance of algebraic geometric codes requires stronger tools than uniform designed-distance bounds. The paper extends the order bound through a partition-based theorem, improving Beelen and Duursma–Park bounds in an exhaustive study of two-point Suzuki-curve codes. The main development assumes positive Goppa designed minimum distance.
Problem
The paper addresses the need for stronger lower bounds on algebraic geometric code minimum distance beyond existing order bounds and uniform bounds.
Method
The paper extends the order-bound argument by using partitions and sequences of divisors associated with multiple points.
Results
For 63 codes, dDK = dDP + 6 and dDK = 62, matching the actual minimum distance; across another comparison, dDK improves dB and dDP by 0 to 3.
Takeaways & Limitations
The extension provides a stronger order bound than the compared Beelen and Duursma–Park bounds for the reported two-point Suzuki-curve codes.
Takeaways & Limitations
The main development restricts attention to codes with deg C > 0; the deg C ≤ 0 case requires a modification.
Abstract
from arXiv · showhide
The most successful method to obtain lower bounds for the minimum distance of an algebraic geometric code is the order bound, which generalizes the Feng-Rao bound. We provide a significant extension of the bound that improves the order bounds by Beelen and by Duursma and Park. We include an exhaustive numerical comparison of the different bounds for 10168 two-point codes on the Suzuki curve of genus g=124 over the field of 32 elements. Keywords: algebraic geometric code, order bound, Suzuki curve.
1 Introduction
The paper characterizes minimum distance through divisor classes and base-point-free divisors, covering both functional and differential algebraic geometric codes. This yields the Goppa designed distance as a basic lower bound.
- Code construction: Algebraic geometric codes are defined by evaluating functions or residues at n distinct rational points disjoint from the divisor G.The functional code uses αL, while the differential code uses αΩ and is dual to CL(D, G).
- Minimum-distance characterization: Minimum distance equals the smallest degree of an effective divisor A satisfying the corresponding Riemann–Roch space inequality.The same characterization is given for both CL(D, G) and CΩ(D, G), with C chosen according to the code.
- Minimum-distance characterization: For CL(D, G), a codeword supported in A exists exactly when L(G − D + A) differs from L(G − D).The analogous differential-code condition is expressed using L(K − G + A) and follows from the residue-space formulation.
- Baseline bound: The Goppa designed minimum distance is deg C, and the actual minimum distance is at least this value.Here C denotes the relevant designed-support divisor class.
2 Coset bounds
The coset-bound framework translates codeword supports into semigroup ideals and estimates their minimum degree through ordered divisor sequences. The paper restricts the main development to positive designed distance.
- Order-bound rationale: The bound combines separate estimates for codeword subsets rather than applying one uniform lower bound to every codeword.The minimum need only be checked for i from 0 through the genus g, using the Singleton-bound limitation on the possible improvement.
- Semigroup ideals: Codeword supports belong to semigroup ideals Γ∗(C) ⊆ Γ(C), allowing distance estimation through the minimum degree of an element in Γ∗(C).For deg C > 0, L(−C) = 0, so Γ∗(C) = Γ(C).
- Semigroup ideals: The order-bound argument uses ΓP(C) and its complement ΔP(C), defined by whether adding or removing P changes the relevant Riemann–Roch spaces.These sets encode the base-point conditions needed to classify divisor supports.
- Duursma–Park bound: The Duursma–Park bound gives deg A ≥ w for ΓP(C) whenever an ordered ΔP(C) sequence has successive divisors separated by at least P.The support of Aw − A1 must be disjoint from the support of A.
3 Order bounds
The paper generalizes order bounds by allowing sequences of points rather than repeatedly using one point. It compares the resulting Duursma–Park and Beelen bounds with weaker and classical specializations.
- General order bounds: A sequence of points {Qi} and cumulative divisors Ri transfers codeword supports into ΓQi(C + Ri) for both functional and differential code chains.This provides the input structure for repeated application of the coset-bound theorem.
- Duursma–Park bound: The Duursma–Park bound requires ordered divisors in ΔQi(C + Ri) whose successive differences are at least Qi and whose endpoint difference is supported in S.Under these conditions, the minimum distance is at least w.
- Beelen bound: The Beelen bound imposes the stricter condition Aj+1 − Aj ∈ {kQi : k > 0}, while its weaker version also requires A1 ∈ {kQi : k ≥ 0}.The simple order bound further specializes to Qi = P for all i.
- Classical specializations: For G = mP, the simple order bound reduces to the original Feng–Rao bound.The paper places this specialization within the hierarchy of increasingly general order bounds.
- Bound comparison: The general hierarchy is dB0 ≤ dB ≤ dABZ′ ≤ dDP and dABZ ≤ dABZ′.The ABZ order bound dABZ′ permits one exceptional successive difference and is always at least the ABZ floor bound.
4 Extension of the order bound
The paper extends the order-bound argument by partitioning divisor semigroups over multiple points and proves a stronger lower bound for supported divisors.
- The extension works with ΓS(C) and ∆S(C), formed by intersecting or combining the corresponding one-point semigroup sets over a finite point set S.
- For S = {P, Q}, combining bounds over C + iP + jQ yields a lower bound for divisors in Γ(C) ∩ ΓS.
- Theorem 4.2 gives deg A ≥ w when an ordered divisor sequence satisfies Ai − Pi ≥ Ai−1 and A avoids the support of Aw − A1.
- The proof derives the bound by repeatedly injecting spaces of functions, producing deg D′ ≥ lD′(Aw) ≥ lD′(A1 − P1) + w.
- The theorem requires constructing suitable sequences in ∆S(C), which the paper addresses through an effective computational procedure.
5 Efficient computation of the bounds
The authors turn the extended theorem into algorithms for coset and two-point code distances, using divisor-function tables and flow maximization.
- The function dP,Q encapsulates curve geometry and supports computation of two-point coset distances and code distances.
- For two-point divisors A = kP + aQ, Theorem 5.2 relates the degree bound deg(A) ≥ dP,Q(a) to membership in ΓQ.
- The function d is periodic modulo m when mP ∼ mQ, and dP,Q and dQ,P satisfy a symmetry relation that reduces computation.
- A weight-maximizing grid algorithm finds longest divisor sequences by storing the best path length for each degree and Q-coordinate.
- The implementation uses successive table updates, bounded degree ranges, and final-row or reverse-row maximization or minimization to obtain the bounds.
- The extended method first computes joint S-coset bounds, derives P- and Q-coset tables, and then applies the same minimizing flow method used for dDP to obtain dDK.
6 Tables for the Suzuki curve over F32
The numerical study evaluates the bounds on 10168 two-point Suzuki-curve codes and shows that the new dDK bound improves earlier order bounds, with exact agreement in a notable subset.
- The Suzuki curve over F32 has genus g = 124, and the study evaluates 10168 two-point codes.
- The comparison includes Goppa, base-point, floor-type, Beelen, ABZ, Duursma–Park, and dDK order bounds, each optimized over its applicable parameter space.
- The dDP bound improves dB for 236 codes, while dDK improves dDP for 1366 codes; the respective maximum improvements are 5 and 6.
- For 63 codes with dDK = dDP + 6, dDK = 62 agrees with the actual minimum distance realized by 62 points equivalent to 31P + 31Q.
- Across degree-specific optimal codes, dDK exceeds the corresponding dB and dDP maxima by between 0 and 3, depending on the degree.