CS Paper Radar

Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus

Haojie Chen, Chuangqiang Hu, Guorui Ma

cs.IT ·submitted 2026-10-29 06:10 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT math.AGmath.NT ·2026-10-29 ·Haojie Chen
theory similarity 0.85
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$.

0.17

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

cs.IT math.AG ·2026-11-01 ·Chuangqiang Hu, Guorui Ma
similarity 0.74
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 Length of Maximum Sum-Rank Distance Codes

cs.IT math.CO ·2026-10-16 ·Valentina Astore, Ferdinando Zullo
similarity 0.72
Abstract

The classical theory of arcs in finite projective spaces provides a powerful geometric framework for studying maximum distance separable (MDS) codes and their possible lengths. In this paper, we investigate how this perspective extends to maximum sum-rank distance (MSRD) codes, whose geometric description involves systems of linear sets rather than individual projective points. Our main goal is to understand how the block structure of an MSRD code constrains its length. In dimension three, we determine the possible intersection patterns of lines with the associated linear sets and obtain explicit formulas for their characters and the weight distribution of the corresponding codes. These results lead to new length bounds and show that the block structure comes at a cost: the presence of a block of rank at least two reduces the maximum possible total length by at least $q-1$, and sufficiently long MSRD codes must be classical, that is, MDS codes over $\mathbb F_{q^m}$. We also prove that three-dimensional one-weight MSRD codes do not exist. In arbitrary dimension, we interpret shortening geometrically as projection and establish a general projection bound that extends classical counting arguments for arcs. This yields restrictions depending explicitly on the block profile and, for full-length blocks, identifies parameter ranges in which linearized Reed--Solomon codes attain the maximum possible number of blocks. Finally, we construct an exceptional three-dimensional MSRD code over $\mathbb F_9$ with three blocks of length two and propose a sum-rank analogue of the MDS conjecture.

0.39

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

cs.IT ·2026-09-06 ·Zhihao Guan, Hengjia Wei
theory similarity 0.70
Abstract · 25 pages

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=Θ(n)$). (2) By utilizing Hermitian curves, we achieve this optimality over sublinear fields of size $q=Θ(n^{2/3})$, breaking the linear field size barrier. (3) Using asymptotically optimal Garcí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$.

0.40

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.70
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

A geometric approach to the density of rank-metric codes

cs.IT math.AG ·2026-09-18 ·Shamil Asgarli, Lian Duan, Nathan Kaplan, Kuan-Wen Lai
theory similarity 0.68
Abstract · 27 pages

We study the asymptotic density of $\mathbb{F}_q$-point-free linear sections of geometrically irreducible projective varieties over finite fields. We then apply these results to rank-metric codes via determinantal varieties. Our approach recovers the known cases in which the density tends to $0$ or $1$ and determines the limit in the cases where it was previously unknown. To compute these previously unknown limits, we extend the notion of quasireflexivity to higher-dimensional varieties and show that determinantal varieties satisfy this property. This allows us to invoke the Chebotarev density theorem for varieties over finite fields to obtain the desired estimate.

0.31

Geometric Obstructions and Sharp Genus Dependence in LCD Scalings

cs.IT math.AG ·2026-11-03 ·Rahim Rahmati-Asghar
theory similarity 0.67
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

Linear Complementary Pairs of MDS Codes from Elliptic Curves

cs.IT math.AGmath.NT ·2026-10-21 ·Adler Marques
hot direction similarity 0.67
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