CS Paper Radar

A Uniform Upper Bound on the Length of MDS Codes from Genus-Two Curves

Haojie Chen

cs.IT math.AGmath.NT ·submitted 2026-10-29 04:56 UTC · v1
theory

Abstract

We study the maximal length of MDS algebraic geometry codes from genus-two curves over finite fields. Let $C_\mathcal{ L}(D,G)$ be such a code over $\mathbb F_q$, with length $n$ and dimension $k$. Assume that $3\leq k\leq n-3$. We prove that $n<(2q+10\sqrt q+16)/3$. This bound holds for every prime power $q$ and for both parities of $k$. It gives a uniform upper bound of $2q/3+O(\sqrt q)$ for the maximal length. The explicit bound is strictly smaller than $q+1$ when $q\geq125$.

Closest papers

Nearest neighbours by meaning across the whole index.

Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus

cs.IT ·2026-10-29 ·Haojie Chen, Chuangqiang Hu, Guorui Ma
theory similarity 0.85
Abstract

We study the length of maximum distance separable algebraic geometry codes from curves of arbitrary positive genus. For fixed genus, we prove that the asymptotic ratio of the length to the field size is at most $1/2$ when both the dimension and the codimension grow faster than the logarithm of the field size. We also give explicit bounds under logarithmic dimension conditions. The bounds hold in every characteristic and are uniform in the curve and the evaluation set. The proof combines character sums on the Jacobian with an estimate for sums of distinct points.

0.43

MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves

cs.IT math.AG ·2026-11-01 ·Chuangqiang Hu, Guorui Ma
similarity 0.77
Abstract · 10 pages, 2 figures

For every fixed genus $g\geq2$ and every $0<ρ<1$, we construct maximum distance separable (MDS) algebraic geometry codes over $\F_q$ for all sufficiently large odd squares $q$. Their parameters are $\bigl[n,\lfloorρn\rfloor,n-\lfloorρn\rfloor+1\bigr]_q$ with $n=\sqrt q+1+O_g(q^{1/4})$. The codes use full Riemann--Roch spaces on genus-$g$ hyperelliptic curves. They are not monomially equivalent to generalized Reed--Solomon (GRS) codes when $q$ is sufficiently large. An infinite subfamily has exact length $n=\sqrt q+2gq^{1/4}+1$.

0.09

On the maximum length of cyclic MDS codes

cs.IT ·2026-10-21 ·Gaojun Luo, Xiwang Cao, Shitao Li, Yang Li
theoryhot direction similarity 0.77
Abstract

We study the maximum length of nontrivial simple-root cyclic maximum distance separable (MDS) codes over ${\mathbb F}_q$. We prove $n\le q+1$ if $\gcd(n,q^2-1)>2$, or if the dimension is even and $\gcd(n,q^2-1)>1$. The bound also holds for all lengths whose prime factors lie in $\{2,3,5,7\}$. We obtain further cases involving primes $\ell\ge11$ with $(\ell-1)/2$ prime, under conditions on the exponents and the characteristic. The proofs combine Fourier supports, locality bounds and field descent with arithmetic restrictions on multiplicative orders and prime-adic valuations.

0.22

Geometric Obstructions and Sharp Genus Dependence in LCD Scalings

cs.IT math.AG ·2026-11-03 ·Rahim Rahmati-Asghar
theory similarity 0.74
Abstract · All comments are welcome

We study the least pole order of a rational function whose nonzero evaluations scale a prescribed code to a Euclidean LCD code. A residue-one differential yields an obstruction for odd-dimensional one-point AG codes in characteristic two: for $C=C_L(D,aQ)$ with $0\le a<n$ and odd dimension, the threshold is at least $n+2g-a-1$. The obstruction uses alternating Gram matrices and does not require the scaled code to be self-orthogonal. For the dimension-three codes $C_L(D,(r+1)Q)$ on Hermitian curves over $\F_{r^2}$, $r=2^e\ge4$, we obtain \[ n+2g-r-2\leτ_D(C;Q)\le n+2g-3. \] Consequently the leading genus contribution is asymptotically sharp even in dimension three. On the elliptic curve $y^2+y=x^3$ over $\F_4$, we prove the exact dimension-three threshold $6$ by an explicit multiplier. For repetition codes on the Hermitian family, the threshold equals the general interpolation bound $n+2g-1$. The upper bounds use information sets and hold for $q>3k$, and for $q>2k$ in characteristic two.

0.07

Near-MDS codes of lengths q+6 and q+7 from conics in PG(2,q), q odd

cs.IT math.CO ·2026-08-18 ·Sinan Donmez, Atilla Akpinar, Rumi Melih Pelen
similarity 0.73
Abstract · 18 pages, 2 figures

Near maximum distance separable (NMDS) codes of dimension 3 and length n over the finite field with q elements are equivalent to (n,3)-arcs in PG(2,q). For every odd prime power q we construct, by adding five suitable points to a conic of PG(2,q), a family of [q+6,3,q+3] NMDS codes and determine their weight distributions completely; three distinct weight enumerators occur, governed by two explicit quadratic-character conditions on the parameters. For every odd prime power q, no code of our family is monomially equivalent to a code of the recent [q+6,3,q+3] NMDS family of Fan, Wang and Xu, even where the weight enumerators of the two families coincide: the separating invariant is a triple of geometric data attached to the underlying arc. Extending the configuration by a sixth point on a distinguished external line, we further obtain [q+7,3,q+4] NMDS codes, together with their weight distributions, for every odd prime power q >= 11 (admissible parameters exist for no q <= 9); the existence proof combines exact and Weil-type character sum estimates with a finite computer verification. Our proofs are purely geometric and rest on a simple counting identity for the trisecant lines of a point set obtained by extending a conic. All the codes constructed are optimal locally recoverable codes with locality 2.

0.32

On Proximity Gaps for One-Point Algebraic Geometric Codes

cs.IT ·2026-10-29 ·Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu
theory similarity 0.72
Abstract · 43 pages

Proximity gaps and correlated agreement underpin the soundness of interactive oracle proofs. We establish these properties for general one-point algebraic geometry (AG) codes, extending corresponding results for Reed-Solomon codes. For codes of length $n$ over $\mathbb F_q$ with designed distance $n-m$, write $ρ=m/n$ and fix $ρ\in(0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\varepsilon<1$, we prove correlated agreement with multiplicative slack $\varepsilon$ and soundness $O(\ell(\ell+1)/(\varepsilon q))$ whenever $e\le(1-\varepsilon)(n-m)/2$, with no additional genus penalty. This gives asymptotically good AG code families from Garcia--Stichtenoth tower of unbounded length over a fixed field with soundness bounds independent of $n$, beyond the RS restriction $n\le q$. We also establish mutual correlated agreement up to radius $(1-\sqrtρ-η)n$, with soundness $O(\ell n/(η^3q))$ for $0<η<1-\sqrtρ$. Our half designed distance proof combines auxiliary divisors, simultaneous Berlekamp-Welch interpolation, and error-incidence counting to obtain a common polynomial representation without a Polishchuk-Spielman divisibility lemma. Finally, two counterexamples on the Garcia-Stichtenoth tower show limitations beyond half the minimum distance, at radii below the Johnson bound and with positive slack. The first requires a positive constant soundness lower bound independent of $q$ and $n$, precluding a uniform $O(1/q)$ guarantee throughout the Johnson regime. The second fixes the field and lets the relative gap above half distance tend to zero while ruling out correlated agreement for every soundness parameter $σ<1$, with positive limiting rate and relative error radius.

0.22

On the MDS conjecture in even characteristic

cs.IT math.CO ·2026-10-20 ·Bocong Chen, Jing Huang
theoryhot direction similarity 0.72
Abstract · 34 pages

We prove that every nontrivial linear $[n,k]$ maximum distance separable (MDS) code over a finite field $\F_q$ of characteristic two satisfies $n\le q+1$, except in dimensions $k=3$ and $k=q-1$, where $n\le q+2$. This resolves the linear MDS conjecture in even characteristic.

0.24

Linear Complementary Pairs of MDS Codes from Elliptic Curves

cs.IT math.AGmath.NT ·2026-10-21 ·Adler Marques
hot direction similarity 0.70
Abstract · 14 pages

In this paper, we investigate the Linear Complementary Pairs (LCPs) of Maximum Distance Separable (MDS) codes that arise from elliptic curves. We establish geometric conditions for LCPs of elliptic codes and prove that they cannot consist entirely of MDS codes when evaluated over all rational points of the curve. To address this, we construct LCPs of MDS elliptic codes by restricting evaluation divisors to subgroup cosets. We apply this method to obtain explicit infinite families of LCPs of MDS codes over Mordell and supersingular elliptic curves, including large-length constructions over quadratic extensions.

0.37