betaFeedback

WorksComputer Science

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

Abstract

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

Introduction

Reed–Solomon codes are obtained by evaluating polynomials of bounded degree over a finite field [1]. Their minimum distance meets the Singleton bound. Goppa extended this construction to algebraic curves by replacing polynomials with Riemann–Roch spaces [2]. This gave algebraic geometry codes, whose parameters reflect both the genus and the rational points of the curve. A standard account appears in [3 Ch. 2].

Write Fs\mathbb{F}_s for a finite field with ss elements. A linear [n,k,d]s[n,k,d]_s code is a kk-dimensional subspace of Fsn\mathbb{F}_s^n with minimum Hamming distance dd. Its rate is k/nk/n. The Singleton bound is d≤n−k+1d \le n-k+1, and a code attaining equality is called maximum distance separable (MDS). On a curve of genus gg, the usual designed-distance bound for an algebraic geometry code can be smaller than n−k+1n-k+1 by gg. To obtain an MDS code, one must rule out functions that vanish at too many evaluation points. Thus a large number of rational points alone does not ensure the MDS property.

MDS codes from curves of positive genus have been studied through divisor classes, point configurations, and code equivalence. Munuera proved the main conjecture for elliptic codes and for genus-two codes when the field size exceeds 83 [4 Thms. 1–2]. His Proposition 1 reduces the length problem to a condition on representatives of classes of sums of distinct evaluation points. He also studied length bounds for elliptic MDS codes [5]. The hyperelliptic case of the main conjecture, under hypotheses on the genus and field size, was treated independently by Chen [6] and de Boer [7]. Walker developed an approach through projective embeddings and proved the elliptic case by this method [8]. These upper-bound results explain the role of divisor classes. The present paper addresses existence with a specified length and dimension range.

Chuangqiang Hu is with Sun Yat-sen University, Guangzhou 510275, China (e-mail: [email protected]).

Guorui Ma is with the Shanghai Institute for Mathematics and Interdisciplinary Sciences (SIMIS) and the Research Institute of Intelligent Complex Systems, Fudan University, Shanghai 200433, China (e-mail: [email protected]). Guorui Ma is the corresponding author.

In arbitrary genus, Chen gave an MDS criterion and a counting construction [9 Thms. 4.2–4.3]. For a one-point divisor of degree m≥4gm \ge4g, the dimension is k=m−g+1k=m-g+1. The sufficient condition for length n>mn>m is

m(nm−g)<N,m\binom{n}{m-g}<N,

where N≤q+1+2gqN \le q+1+2g\sqrt{q} is the number of rational points in the projective image. For fixed gg and k/n→ρ∈(0,1)k/n \to\rho\in(0,1), put

H(ρ)=−ρlog⁡ρ−(1−ρ)log⁡(1−ρ)>0.H(\rho)=-\rho\log\rho-(1-\rho)\log(1-\rho)>0.

Here log denotes the natural logarithm. Stirling’s formula gives

log⁡(nm)m−g=nH(ρ)+o(n).\log\binom{n}{m}{m-g}=nH(\rho)+o(n).

Thus this sufficient condition can certify only n=O(log⁡q)n=O(\log q) at a fixed limiting rate. This observation concerns that counting condition; it is not an upper bound for all codes [9].

Marques, da Silva, and Tafazolian study complementary pairs on hyperelliptic curves [10]. Their Proposition 6 characterizes the MDS property of their length-2t2t, dimension-tt pairs by requiring reduced Mumford representatives of degree gg for classes associated with every tt-subset of the evaluation set. The present construction proves simultaneous avoidance for all such subset classes by placing them in a subgroup of the Jacobian. It imposes no complementarity or LCD condition.

Zhu, Chen, Peng, Zhang, and Zhao study MDS and NMDS constructions from maximal curves and genus-two curves with split Jacobian [11]. Their results impose determinant, evaluation-point, elliptic-cover, and subset-sum conditions, including k≡2(mod3)k \equiv2 \pmod3 in one specialization. For the Beelen–Montanucci branch, write q=a2hq=a^{2h}, where aa is a prime power and h≥3h \ge3 is odd, and put

s=ah−1−1a2−1.s=\frac{a^{h-1}-1}{a^2-1}.

Theorem 1 of [11] uses a curve of genus

(a−1)(ah+1+ah−a2)2\frac{(a-1)(a^{h+1}+a^h-a^2)}{2}

and a one-point divisor giving dimension s+3s+3. This genus varies with aa and hh; for example, h=3h=3 gives s=1s=1 and dimension 4, while the genus grows with aa. Their genus-two branch instead fixes the genus at two and assumes a split Jacobian, with sufficient conditions on the evaluation set. We do not claim to improve every length in [11]. Our contribution is a uniform existence theorem in every fixed genus, over all sufficiently large odd square fields, with g+1≤k≤n−gg+1 \le k \le n-g, full Riemann–Roch spaces, and eventual non-GRS codes. Table 1 records the scope of these comparisons.

ResultCurves and defining divisorsLength and dimension guarantee
Chen [9 Thm. 4.3]Arbitrary genus; one-point divisor.m(nm−g)<Nm\left(\frac{n}{m-g}\right)<N; at fixed rate, only n=O(log⁡q)n=O(\log q).
Zhu et al. [11 Thm. 1, Cor. 3]Beelen–Montanucci curves; one-point divisors.Determinant/evaluation conditions; dimension s+3s+3; genus varies with a,ha,h.
Zhu et al. [11 Thm. 4, Cors. 5–6, 11]Genus two with split Jacobian.Elliptic-cover and subset conditions; k≡2(mod3)k\equiv2\pmod{3} in Corollary 11; length depends on the point set.
Marques et al. [10 Prop. 6]Hyperelliptic curves; complementary pairs.Length 2t2t, dimension tt; reduced-degree MDS condition for every tt-subset.
Theorem 1, Corollary 2Hyperelliptic curves satisfying (1); general effective divisors.g+1≤k≤n−gg+1\leq k\leq n-g, n=q+1+Og(q1/4)n=\sqrt{q}+1+O_g(q^{1/4}).

Table 1. Scope of the closest MDS constructions.

The question considered here is the following. For every fixed g≥2g \ge2, can one obtain algebraic geometry codes over Fq\mathbb{F}_q with length asymptotic to q\sqrt{q} and with rate bounded away from zero and one? We require the full Riemann–Roch space of a divisor. This requirement excludes constructions obtained by selecting a proper subspace of that space. We allow general defining divisors, rather than requiring all poles to lie at one point.

Throughout, curves are smooth, projective, and geometrically irreducible; an affine equation denotes its smooth projective model. The construction assumes g≥2g \ge2.

The evaluation points are defined over Fr\mathbb{F}_r, and the defining divisor is defined over Fr2\mathbb{F}_{r^2}. Classes of sums of evaluation points lie in the subfield Jacobian. Corollary 7 reduces the MDS condition to finding a coset that avoids effective divisor classes of degree g−1g - 1. The main geometric step is Proposition 14. Its proof uses the intersection formula in Lemma 12 twice, through Lemma 13, to reduce the degree of a fixed point of a translated Frobenius involution by two and ultimately exclude all such effective classes.

Theorem 1. Let rr be an odd prime power, let g≥2g \ge2, and assume r≥(2g+2)2r \ge(2g + 2)^2. Let X/FrX/\mathbb{F}_r be a hyperelliptic curve of genus gg with an odd-degree affine model

y2=f(x),deg⁡f=2g+1,f∈Fr[x] square-free.(1)y^2=f(x),\qquad\deg f=2g+1,\qquad f\in\mathbb{F}_r[x]\ \text{square-free}. \tag*{(1)}

Set q=r2q=r^2, let n=∣X(Fr)∣n=|X(\mathbb{F}_r)|, and let DD be the sum of the points in X(Fr)X(\mathbb{F}_r). For every integer

g+1≤k≤n−g,(2)g+1\le k\le n-g, \tag*{(2)}

there is an effective Fq\mathbb{F}_q-rational divisor GG of degree k+g−1k+g-1, with support disjoint from DD, such that CL(D,G)C_L(D,G) is an [n,k,n−k+1]q[n,k,n-k+1]_q MDS code.

Proposition 17 below gives the additional non-equivalence assertion: if min⁡{k,n−k}≥3g+1\min\{k,n-k\}\ge3g+1, then the code is not monomially equivalent to a generalized Reed–Solomon code.

The theorem applies to each curve with the stated model. Existence of such curves in every genus gives the following consequence. In the asymptotic statements, the genus is fixed and qq tends to infinity through odd squares.

Corollary 2. Fix g≥2g\ge2 and 0<ρ<10<\rho<1. For every sufficiently large odd square qq, there are genus-gg MDS algebraic geometry codes, not monomially equivalent to generalized Reed–Solomon codes, with parameters

[n,⌊ρn⌋,n−⌊ρn⌋+1]q,(3)[n,\lfloor\rho n\rfloor,n-\lfloor\rho n\rfloor+1]_q, \tag*{(3)}

where nn satisfies

q+1−2gq1/4≤n≤q+1+2gq1/4.(4)\sqrt{q}+1-2gq^{1/4}\le n\le\sqrt{q}+1+2gq^{1/4}. \tag*{(4)}

Writing k=⌊ρn⌋k=\lfloor\rho n\rfloor, we have

kn=ρ+O(n−1)⟶ρ,n=q+1+Og(q1/4).(5)\frac{k}{n}=\rho+O(n^{-1})\longrightarrow\rho,\qquad n=\sqrt{q}+1+O_g\left(q^{1/4}\right). \tag*{(5)}

The next consequence uses a fixed equation and gives an exact length.

Corollary 3. Fix g≥2g\ge2, 0<ρ<10<\rho<1, and a prime p≡−1(mod2g+1)p\equiv-1\pmod{2g+1}. For every sufficiently large positive odd integer mm, put q=p4mq=p^{4m}. On the curve

X:y2=1−x2g+1(6)X:y^2=1-x^{2g+1} \tag*{(6)}

there are MDS codes, not monomially equivalent to generalized Reed–Solomon codes, with parameters (3) and

n=q+2gq1/4+1.(7)n=\sqrt{q}+2gq^{1/4}+1. \tag*{(7)}

A recent preprint gives n≤q/2+o(q)n\le q/2+o(q) for fixed genus when both the dimension and the codimension grow faster than log⁡q\log q [12 Thm. 1]. That growth condition includes the families in Corollary 2. There remains a gap in order between that upper bound and the present existence lower bound. No upper bound of order q\sqrt{q}, or optimal leading constant, is proved here.

The proof has three parts. Section II expresses the MDS condition in the Jacobian and constructs effective representatives with the required support. Section III proves the hyperelliptic intersection formula and the coset statement. Section IV finds the required points, proves the main results, and checks the examples. Section V states the remaining questions.

Preliminaries

Divisors and Evaluation Codes

Let KK be a finite field and let X/KX/K be a curve of genus gg. A divisor on XX is a finite sum H=∑TmTTH=\sum_Tm_TT, where TT runs through closed points and mT∈Zm_T\in\mathbb{Z}. Its degree is ∑TmT[K(T):K]\sum_Tm_T[K(T):K], where K(T)K(T) is the residue field at TT. It is effective, written H≥0H\ge0, if every mTm_T is nonnegative. Its support supp⁡(H)\operatorname{supp}(H) is the set of points with nonzero coefficient. Equivalently, a KK-rational divisor is a divisor on the geometric curve invariant under the Galois group of an algebraic closure K‾\overline{K} over KK. It need not be a sum of points in X(K)X(K).

Write K(X)K(X) for the function field of XX. For h∈K(X)×h\in K(X)^\times, its principal divisor is (h)=∑TvT(h)T(h)=\sum_Tv_T(h)T, where vTv_T is the normalized order at TT. Two KK-rational divisors are linearly equivalent, written H∼H′H\sim H', if H−H′=(h)H-H'=(h) for such an hh. Set

L(H)={h∈K(X)×:(h)+H≥0}∪{0},ℓ(H)=dim⁡KL(H).(8)\mathcal{L}(H)=\{h\in K(X)^\times:(h)+H\ge0\}\cup\{0\}, \qquad \ell(H)=\dim_K\mathcal{L}(H). \tag*{(8)}

The complete linear system ∣H∣|H| consists of effective divisors linearly equivalent to HH. If KXK_X is a canonical divisor, Riemann–Roch gives

ℓ(H)=deg⁡H+1−g+ℓ(KX−H),deg⁡KX=2g−2.(9)\ell(H)=\deg H+1-g+\ell(K_X-H), \qquad \deg K_X=2g-2. \tag*{(9)}

In particular, ℓ(H)=0\ell(H)=0 if deg⁡H<0\deg H<0, and ℓ(H)=deg⁡H+1−g\ell(H)=\deg H+1-g if deg⁡H>2g−2\deg H>2g-2; see [3 Sec. 1.5].

Definition 1. Fix distinct P1,…,Pn∈X(K)P_1,\ldots,P_n\in X(K), and put D=P1+⋯+PnD=P_1+\cdots+P_n. If supp⁡(G)∩supp⁡(D)=∅\operatorname{supp}(G)\cap\operatorname{supp}(D)=\varnothing, every function in L(G)\mathcal{L}(G) is regular at every PiP_i. Define the evaluation map and the algebraic geometry code by

ev⁡D:L(G)⟶Kn,h⟼(h(P1),…,h(Pn)),(10)\operatorname{ev}_D:\mathcal{L}(G)\longrightarrow K^n, \qquad h\longmapsto\bigl(h(P_1),\ldots,h(P_n)\bigr), \tag*{(10)}
CL(D,G)=ev⁡D(L(G)).C_L(D,G)=\operatorname{ev}_D(\mathcal{L}(G)).

Its minimum distance is the smallest number of nonzero coordinates of a nonzero codeword.

The next standard criterion identifies the precise vanishing condition we must prove. The use of these vanishing spaces is classical; see [4 Sec. I] and [9 Thm. 4.2]. We retain the proof for general GG to make the subsequent sufficient condition self-contained.

Lemma 4. Suppose deg⁡G<n\deg G<n, and set k=ℓ(G)≥1k=\ell(G)\geq1. Then CL(D,G)C_L(D,G) has dimension kk and minimum distance at least n−deg⁡Gn-\deg G. It is MDS if and only if

ℓ(G−E)=0(11)\ell(G-E)=0 \tag*{(11)}

for every sum EE of kk distinct points among P1,…,PnP_1,\ldots,P_n.

Proof. The kernel of (10) is L(G−D)\mathcal{L}(G-D). Its degree is negative, so this space is zero. Thus evaluation is injective and its image has dimension kk.

Let h∈L(G)h\in\mathcal{L}(G) be nonzero, and let ZZ be the sum of the evaluation points at which hh vanishes. The support condition on GG implies h∈L(G−Z)h\in\mathcal{L}(G-Z). Consequently, deg⁡Z≤deg⁡G\deg Z\leq\deg G, since a divisor of negative degree has no nonzero section. The corresponding codeword has weight n−deg⁡Z≥n−deg⁡Gn-\deg Z\geq n-\deg G.

For a sum EE of kk distinct evaluation points, the kernel of evaluation on just those coordinates is L(G−E)\mathcal{L}(G-E). If (11) holds for all such EE, no nonzero codeword has kk zero coordinates. Its weight is therefore at least n−k+1n-k+1. The Singleton bound gives equality. Conversely, a nonzero element of L(G−E)\mathcal{L}(G-E) evaluates to a nonzero codeword, by injectivity, with at least kk zero coordinates. Its weight is at most n−kn-k, so the code is not MDS.

Effective Divisor Classes in the Jacobian

We now express (11) in a form that uses the subfield of definition of the evaluation points. Fix P0∈X(K)P_0\in X(K). Let J=Jac⁡(X)J=\operatorname{Jac}(X) be the Jacobian. Write [H][H] for the linear-equivalence class of a divisor HH. The group J(K)J(K) identifies with the degree-zero divisor classes represented over KK. More generally, Pic⁡d(X)(K)\operatorname{Pic}^{d}(X)(K) denotes the degree-dd line-bundle classes, and translation by dP0dP_0 identifies it with J(K)J(K). The existence of P0P_0 ensures that these rational classes have line-bundle, and hence divisor, representatives over KK; see [13 Part III, Sec. 1].

For an integer d≥0d\geq0, let X(d)X^{(d)} be the dd-th symmetric power of XX; let X(0)X^{(0)} be a point defined over KK. Its KK-points are effective KK-rational divisors of degree dd. Consider the Abel–Jacobi map

αd:X(d)⟶J,A⟼[A−dP0].(12)\alpha_d:X^{(d)}\longrightarrow J,\qquad A\longmapsto[A-dP_0]. \tag*{(12)}

Definition 2. Let WdW_d be the closed image of αd\alpha_d. Its set of KK-rational points is

Wd(K)={[A−dP0]:A≥0, deg⁡A=d, A defined over K}.(13)W_d(K)=\{[A-dP_0]: A\geq0,\ \deg A=d,\ A\text{ defined over }K\}. \tag*{(13)}

The standard construction and these maps are described in [13 Part III, Secs. 3–5]. Concretely, we must rule out the possibility that a class has an effective representative over K‾\overline{K} but not over KK. The class is represented by a line bundle LL of degree dd defined over KK. If LL has a nonzero section over K‾\overline{K}, then its section space is already nonzero over KK, because the dimension of this space does not change under field extension. Thus a nonzero section exists over KK, and its divisor is an effective KK-rational representative of the class.

On geometric points, the fibers of (12) are complete linear systems: for an effective divisor AA of degree dd,

αd−1([A−dP0])=∣A∣.(14)\alpha_d^{-1}([A-dP_0])=|A|. \tag*{(14)}

Indeed, αd(B)=αd(A)\alpha_d(B)=\alpha_d(A) if and only if B∼AB\sim A.

In particular, W0(K)={0}W_0(K)=\{0\}, and adding P0P_0 to an effective divisor gives

Wd−1(K)⊆Wd(K)(d≥1).(15)W_{d-1}(K)\subseteq W_d(K)\qquad(d\geq1). \tag*{(15)}

The effective classes in Pic⁡g−1(X)\operatorname{Pic}^{g-1}(X) form the theta divisor. Under the translation above, its inverse image in JJ is Wg−1W_{g-1} [13 Part III, Secs. 5–6]. We use this translated theta divisor throughout.

The following lemma isolates the implication from the geometric construction to the coding problem. This is the only place where the classes of sums of evaluation points are used.

Lemma 5. Assume XX, P0P_0, and P1,…,PnP_1,\ldots,P_n are defined over Fr⊆K\mathbb{F}_r\subseteq K. Let b∈J(K)b\in J(K) satisfy

(b+J(Fr))∩Wg−1(K)=∅.(16)(b+J(\mathbb{F}_r))\cap W_{g-1}(K)=\varnothing. \tag*{(16)}

For an integer 1≤k≤n1\leq k\leq n, let GG be a KK-rational divisor with

deg⁡G=k+g−1,[G−(k+g−1)P0]=b.(17)\deg G=k+g-1,\qquad[G-(k+g-1)P_0]=b. \tag*{(17)}

Then ℓ(G−E)=0\ell(G-E)=0 for every sum EE of kk distinct evaluation points.

Proof. For such an EE, put e=[E−kP0]∈J(Fr)e=[E-kP_0]\in J(\mathbb{F}_r). If ℓ(G−E)>0\ell(G-E)>0, choose 0≠h∈L(G−E)0\ne h\in L(G-E). Then A=(h)+G−EA=(h)+G-E is an effective KK-rational divisor of degree g−1g-1. Equations (17) and (13) give

[A−(g−1)P0]=b−e∈(b+J(Fr))∩Wg−1(K),[A-(g-1)P_0]=b-e\in(b+J(\mathbb{F}_r))\cap W_{g-1}(K),

contradicting (16). □

Effective Representatives with Disjoint Support

The coset argument produces a divisor class. Evaluation requires an actual divisor whose support avoids DD. The next elementary argument provides an effective representative without assuming that it is supported at rational points.

Lemma 6. Let ∣K∣=q|K|=q and assume n<qn<q. For every b∈J(K)b\in J(K) and k≥g+1k\ge g+1, there is an effective KK-rational divisor GG satisfying (17), with supp⁡(G)∩supp⁡(D)=∅\operatorname{supp}(G)\cap\operatorname{supp}(D)=\varnothing and ℓ(G)=k\ell(G)=k.

Proof. Set a=k+g−1≥2ga=k+g-1\ge2g. Represent bb by a KK-rational divisor BB of degree zero and put G0=B+aP0G_0=B+aP_0. Then deg⁡G0=a\deg G_0=a and [G0−aP0]=b[G_0-aP_0]=b. Since a>2g−2a>2g-2, Riemann–Roch gives ℓ(G0)=a+1−g=k\ell(G_0)=a+1-g=k. For each evaluation point RR, the divisor G0−RG_0-R has degree at least 2g−12g-1, so the same formula gives

ℓ(G0−R)=k−1.(18)\ell(G_0-R)=k-1. \tag*{(18)}

Thus each L(G0−R)L(G_0-R) is a proper subspace with qk−1q^{k-1} elements. Their union has at most nqk−1<qknq^{k-1}<q^k elements. Choose h∈L(G0)h\in L(G_0) outside this union. In particular h≠0h\ne0.

Set G=G0+(h)G=G_0+(h). It is effective because h∈L(G0)h\in L(G_0), and it has degree aa and the required class. At an evaluation point RR, let cRc_R be the coefficient of G0G_0. Membership in L(G0)L(G_0) gives vR(h)+cR≥0v_R(h)+c_R\ge0. Nonmembership in L(G0−R)L(G_0-R) gives vR(h)+cR<1v_R(h)+c_R<1. This integer is therefore zero, which is exactly the coefficient of RR in GG. Hence the supports are disjoint. Finally, linear equivalence gives ℓ(G)=ℓ(G0)=k\ell(G)=\ell(G_0)=k. □

Combining these two lemmas gives the following coset sufficient condition. It reduces the coding problem to geometric avoidance; the existence of the required coset is proved in Proposition 14.

Corollary 7. Assume that XX, P0P_0, and P1,…,PnP_1,\ldots,P_n are defined over Fr⊆K\mathbb{F}_r\subseteq K, where ∣K∣=q|K|=q and n<qn<q. Let b∈J(K)b\in J(K) satisfy (16). For every integer g+1≤k≤n−gg+1\le k\le n-g, there is an effective KK-rational divisor GG of degree k+g−1k+g-1, with support disjoint from DD, such that CL(D,G)C_L(D,G) is an [n,k,n−k+1]K[n,k,n-k+1]_K MDS code.

Proof. Lemma 6 gives an effective KK-rational divisor GG satisfying (17), with support disjoint from DD and ℓ(G)=k\ell(G)=k. Lemma 5 gives ℓ(G−E)=0\ell(G-E)=0 for every sum EE of kk distinct evaluation points. Since deg⁡G=k+g−1<n\deg G=k+g-1<n, Lemma 4 proves the MDS property. □

Hyperelliptic Curves and the Coset Construction

The goal of this section is to construct a Jacobian coset disjoint from the translated theta divisor. More precisely, we seek b∈J(Fr2)b\in J(\mathbb{F}_{r^2}) satisfying (b+J(Fr))∩Wg−1(Fr2)=∅(b+J(\mathbb{F}_r))\cap W_{g-1}(\mathbb{F}_{r^2})=\varnothing. We first use the hyperelliptic involution to prove an intersection formula for Wd(K)W_d(K), and then combine it with Frobenius and fixed-point descent to obtain the required coset.

Divisors of Small Degree

Let g≥2g\ge2, let KK be a finite field of odd characteristic, and let X/KX/K be the smooth projective model of y2=f(x)y^2=f(x), where f∈K[x]f\in K[x] is square-free and deg⁡f=2g+1\deg f=2g+1. The degree-two map x:X→P1x:X\to\mathbb{P}^1 to the projective line is branched at the 2g+12g+1 roots of ff and at infinity. The Hurwitz formula gives genus gg. The point above infinity is unique, is KK-rational, and will be denoted by P0P_0. The hyperelliptic involution is ι(x,y)=(x,−y)\iota(x,y)=(x,-y), extended to XX. For every finite geometric point PP, the divisor of x−x(P)x-x(P) gives

P+ι(P)∼2P0.(19)P+\iota(P)\sim2P_0. \tag*{(19)}

At a branch point the zero has multiplicity two. The same equivalence is immediate for P=P0P=P_0. These are the fibers of the map xx.

Apply ι\iota to each point of a divisor. For an effective KK-rational divisor AA of degree dd, relation (19) gives A+ι(A)∼2dP0A+\iota(A)\sim2dP_0. The equivalence is defined over KK, either by multiplying the functions for the points in Galois orbits or by pulling back a divisor on P1\mathbb{P}^1. Consequently,

−[A−dP0]=[ι(A)−dP0],−Wd(K)=Wd(K).(20)-[A-dP_0]=[\iota(A)-dP_0],\qquad-W_d(K)=W_d(K). \tag*{(20)}

To control intersections of translates of WdW_d, we first prove a structural fact about Riemann–Roch spaces of divisors of degree at most gg. Its consequence concerning hyperelliptic fibers is used below.

Lemma 8. Let FF be an effective KK-rational divisor with deg⁡F≤g\deg F\le g. If ℓ(F)≥2\ell(F)\ge2, then L(F)⊆K(x)L(F)\subseteq K(x).

Proof. Since FF is effective, constants belong to L(F)L(F). Choose a nonconstant h∈L(F)h\in L(F), and let e=deg⁡(h)∞e=\deg(h)_\infty, where (h)∞(h)_\infty is its pole divisor. The associated map h:X→P1h:X\to\mathbb{P}^1 has degree ee, and 1≤e≤deg⁡F≤g1\le e\le\deg F\le g.

Suppose h∉K(x)h\notin K(x). The extension K(X)/K(x)K(X)/K(x) has degree two, so K(x,h)=K(X)K(x,h)=K(X). Thus (x,h)(x,h) is birational onto an integral curve CC in P1×P1\mathbb{P}^1\times\mathbb{P}^1. Its two projection degrees are 22 and ee. A curve with these projection degrees has arithmetic genus

pa(C)=(2−1)(e−1)=e−1.p_a(C)=(2-1)(e-1)=e-1.

For completeness, put S=P1×P1S=\mathbb{P}^1\times\mathbb{P}^1 and write OS(a,b)\mathcal{O}_S(a,b) for the tensor product of the pullbacks of the degree-aa and degree-bb line bundles from the two factors. Write χ\chi for the alternating sum of cohomology dimensions. The exact sequence

0⟶OS(−e,−2)⟶OS⟶OC⟶00\longrightarrow\mathcal{O}_S(-e,-2)\longrightarrow\mathcal{O}_S\longrightarrow\mathcal{O}_C\longrightarrow0

and χ(OS(a,b))=(a+1)(b+1)\chi(\mathcal{O}_S(a,b))=(a+1)(b+1) give this formula (with the factors interchanged if necessary). The normalization of CC is XX, and normalization can only decrease arithmetic genus. Hence g≤e−1g\le e-1, contradicting e≤ge\le g.

It follows that h∈K(x)h\in K(x), as required. □

Corollary 9. Let FF be an effective KK-rational divisor with deg⁡F≤g\deg F \leq g. If ℓ(F)≥2\ell(F) \geq2, then F−2P0F - 2P_0 is linearly equivalent over KK to an effective divisor.

Proof. Choose a nonconstant h∈L(F)h \in L(F). Lemma 8 gives h∈K(x)h \in K(x). Let TT be its pole divisor on P1\mathbb{P}^1, and set s=deg⁡T≥1s = \deg T \geq1. Then (h)∞=x∗T∼2sP0(h)_\infty= x^*T \sim2sP_0. Since (h)∞≤F(h)_\infty\leq F, we have

F−2P0∼F−(h)∞+2(s−1)P0≥0,F - 2P_0 \sim F - (h)_\infty+ 2(s - 1)P_0 \geq0,

as required. All the divisors and equivalences used here are defined over KK.

Frobenius and the Required Coset

Assume now that XX is defined over Fr\mathbb{F}_r and K=Fr2K = \mathbb{F}_{r^2}. Let σ\sigma be the rr-power Frobenius endomorphism, acting on XX and on JJ. On KK-points it has square equal to the identity, and its fixed subgroup on J(K)J(K) is J(Fr)J(\mathbb{F}_r). Since P0P_0 is rational over Fr\mathbb{F}_r, we have σ(Wd(K))=Wd(K)\sigma(W_d(K)) = W_d(K).

Since σ\sigma and ι\iota commute, ισ\iota\sigma is an involution on X(K)X(K).

Definition 3. A point P∈X(K)P \in X(K) is called an ισ\iota\sigma-fixed point if ι(σ(P))=P\iota(\sigma(P)) = P, or equivalently σ(P)=ι(P)\sigma(P) = \iota(P).

Let P,QP,Q be two such points with finite distinct xx-coordinates, so that

σ(P)=ι(P),σ(Q)=ι(Q).(21)\sigma(P) = \iota(P), \qquad\sigma(Q) = \iota(Q). \tag*{(21)}

Put

u=[P−P0],v=[Q−P0],δ=u+v.(22)u = [P - P_0], \qquad v = [Q - P_0], \qquad\delta= u + v. \tag*{(22)}

We first record the relations between these divisor classes and then construct the required coset as a set of fixed points.

Lemma 10. With this notation, u≠vu \ne v, δ≠0\delta\ne0, and

σ(u)=−u,σ(v)=−v,σ(δ)=−δ.(23)\sigma(u) = -u, \qquad\sigma(v) = -v, \qquad\sigma(\delta) = -\delta. \tag*{(23)}

Proof. Since P0P_0 is defined over Fr\mathbb{F}_r, equations (19) and (21) give

σ(u)=[ι(P)−P0]=−[P−P0]=−u.\sigma(u) = [\iota(P) - P_0] = -[P - P_0] = -u.

The same computation gives σ(v)=−v\sigma(v) = -v. Adding these two identities gives σ(δ)=−δ\sigma(\delta) = -\delta.

Suppose δ=0\delta= 0. Then P+Q∼2P0P + Q \sim2P_0, so some nonconstant h∈K(X)h \in K(X) has divisor

(h)=P+Q−2P0.(h) = P + Q - 2P_0.

Thus 11 and hh are linearly independent elements of L(2P0)L(2P_0). Since 2≤g2 \leq g, Lemma 8 gives h∈K(x)h \in K(x). The divisor of poles of a function in K(x)K(x) pulls back under the degree-two map xx. Hence hh has no finite pole on P1\mathbb{P}^1, and its pole at infinity has order at most one. It follows that h=ax+bh = ax + b with a≠0a \ne0. Every point in its zero divisor on XX has the same xx-coordinate −b/a-b/a. This contradicts x(P)≠x(Q)x(P) \ne x(Q), so δ≠0\delta\ne0.

If u=vu = v, then P∼QP \sim Q. Since P≠QP \ne Q, a function with divisor P−QP - Q would give a degree-one map from XX to P1\mathbb{P}^1. Such a map identifies their function fields and would force XX to have genus zero. This contradicts g≥2g \geq2. Thus u≠vu \ne v.

Define

τ:J(K)⟶J(K),τ(z)=σ(z)−δ.(24)\begin{aligned} \tau&: J(K) \longrightarrow J(K),\\ \tau(z) &= \sigma(z) - \delta. \tag*{(24)} \end{aligned}

For z∈J(K)z \in J(K), one has σ2(z)=z\sigma^2(z) = z, since K=Fr2K = \mathbb{F}_{r^2}. Lemma 10 gives σ(δ)=−δ\sigma(\delta) = -\delta. Therefore

τ2(z)=σ(σ(z)−δ)−δ=σ2(z)−σ(δ)−δ=z+δ−δ=z.\begin{aligned} \tau^2(z) &= \sigma(\sigma(z) - \delta) - \delta\\ &= \sigma^2(z) - \sigma(\delta) - \delta\\ &= z + \delta- \delta= z. \end{aligned}

Thus τ\tau is an involution.

We next identify the required coset with the fixed points of an involution.

Proposition 11. For δ\delta as in (22), there is b∈J(K)b \in J(K) with σ(b)−b=δ\sigma(b) - b = \delta. The fixed points of the involution τ\tau in (24) are exactly b+J(Fr)b + J(\mathbb{F}_r).

Proof. The geometric points of the kernel of σ−1\sigma- 1 form the finite group J(Fr)J(\mathbb{F}_r). Since the differential of Frobenius is zero, the differential of σ−1\sigma- 1 is −1-1, so its kernel is finite and reduced. Thus σ−1\sigma- 1 is an isogeny and is surjective on geometric points [13 Part I, Prop. 7.1]. Choose b∈J(Fr2)b \in J(\mathbb{F}_{r^2}) satisfying

σ(b)−b=δ.(25)\sigma(b) - b = \delta. \tag*{(25)}

Applying σ\sigma and adding the resulting identity to (25) gives σ2(b)−b=σ(δ)+δ=0\sigma^2(b) - b = \sigma(\delta) + \delta= 0, so b∈J(K)b \in J(K).

Finally, (25) shows that τ(z)=z\tau(z) = z exactly when σ(z−b)=z−b\sigma(z - b) = z - b, that is, when z−b∈J(Fr)z - b \in J(\mathbb{F}_r). Hence the fixed points are b+J(Fr)b + J(\mathbb{F}_r).

Intersection Formula and Fixed-Point Descent

The next formula reduces an intersection involving degree dd to two translates involving degree d−1d - 1. Its genus-two case, d=1d = 1, appears in [14 Prop. 4.5]. In the proof of their Theorem 4.8, Frobenius permutes four theta translates, and a rational point would have to lie in their common intersection. We use the same general principle that a fixed point in exchanged sets lies in their intersection. The formula below allows this principle to reduce the degree by two in arbitrary genus.

Lemma 12. Let U,V∈X(K)U,V \in X(K) be distinct, and set u=[U−P0]u = [U - P_0], v=[V−P0]v = [V - P_0]. For 1≤d≤g−11 \leq d \leq g - 1,

Wd(K)∩(Wd(K)+u−v)=(u+Wd−1(K))∪(−v+Wd−1(K)).(26)W_d(K) \cap(W_d(K) + u - v) = (u + W_{d-1}(K)) \mathbin{\cup} (-v + W_{d-1}(K)). \tag*{(26)}

Proof. Let zz belong to the left side. By (13), there are effective KK-rational divisors A,BA,B of degree dd such that

z=[A−dP0],z−(u−v)=[B−dP0].z = [A - dP_0], \qquad z - (u - v) = [B - dP_0].

Subtracting these identities gives A+V∼B+UA + V \sim B + U. If AA contains UU, the divisor A−UA - U is effective of degree d−1d - 1, and z∈u+Wd−1(K)z \in u + W_{d-1}(K).

Suppose instead that AA does not contain UU. Since U≠VU \ne V, the divisor A+VA + V has coefficient zero at UU, whereas B+UB + U has a positive coefficient there. These are distinct effective divisors in the same complete linear system. Their linear equivalence gives a nonconstant h∈K(X)h \in K(X) with (h)=B+U−(A+V)(h) = B + U - (A + V), so h∈L(A+V)h \in L(A + V) and ℓ(A+V)≥2\ell(A + V) \geq2. As deg⁡(A+V)=d+1≤g\deg(A + V) = d + 1 \leq g, Corollary 9 gives an effective KK-rational divisor EE of degree d−1d - 1 with A+V∼2P0+EA + V \sim2P_0 + E. It follows that

z+v=[A+V−(d+1)P0]=[E−(d−1)P0],z + v = [A + V - (d + 1)P_0] = [E - (d - 1)P_0],

so z∈−v+Wd−1(K)z \in-v + W_{d-1}(K). This proves one inclusion.

For the reverse inclusion, let w=[E−(d−1)P0]∈Wd−1(K)w = [E - (d - 1)P_0] \in W_{d-1}(K). Then u+w=[U+E−dP0]∈Wd(K)u + w = [U + E - dP_0] \in W_d(K), and subtracting u−vu - v gives v+w∈Wd(K)v + w \in W_d(K). Similarly, (19) gives −v+w=[ι(V)+E−dP0]∈Wd(K)-v + w = [\iota(V) + E - dP_0] \in W_d(K). Subtracting u−vu - v now gives −u+w=[ι(U)+E−dP0]∈Wd(K)-u + w = [\iota(U) + E - dP_0] \in W_d(K). Both sets on the right of (26) therefore lie in the intersection.

Lemma 13. For 1≤d≤g−11 \le d \le g - 1, write Wd(K)τ={z∈Wd(K):τ(z)=z}W_d(K)^\tau= \{z \in W_d(K) : \tau(z) = z\}. Then

Wd(K)τ⊆(−u+Wd−1(K))∩(−v+Wd−1(K)).(27)W_d(K)^\tau\subseteq(-u + W_{d-1}(K)) \cap(-v + W_{d-1}(K)). \tag*{(27)}

Moreover, for 2≤d≤g−12 \le d \le g - 1, one has Wd(K)τ⊆Wd−2(K)W_d(K)^\tau\subseteq W_{d-2}(K).

Proof. We use the intersection formula twice.

Suppose 1≤d≤g−11 \le d \le g - 1 and z∈Wd(K)z \in W_d(K) is fixed. Then σ(z)=z+δ\sigma(z) = z + \delta belongs to Wd(K)W_d(K), because this set is stable under σ\sigma. Therefore

z∈Wd(K)∩(Wd(K)−δ).z \in W_d(K) \cap(W_d(K) - \delta).

Apply Lemma 12 with U=ι(P)U = \iota(P) and V=QV = Q. The distinct xx-coordinates ensure U≠VU \ne V. Their divisor classes are −u-u and vv, so

Wd(K)∩(Wd(K)−δ)=(−u+Wd−1(K))∪(−v+Wd−1(K)).(28)\begin{aligned} W_d(K) \cap(W_d(K) - \delta) &= (-u + W_{d-1}(K)) \\ &\quad\cup(-v + W_{d-1}(K)). \tag*{(28)} \end{aligned}

For every w∈Wd−1(K)w \in W_{d-1}(K), direct substitution in (24) gives

τ(−u+w)=−v+σ(w),τ(−v+w)=−u+σ(w).\begin{aligned} \tau(-u + w) &= -v + \sigma(w),\\ \tau(-v + w) &= -u + \sigma(w). \end{aligned}

Since σ\sigma permutes Wd−1(K)W_{d-1}(K), τ\tau interchanges the two sets on the right of (28). A fixed point in their union must belong to their intersection, which proves (27).

Now assume 2≤d≤g−12 \le d \le g - 1. A point zz in the intersection in (27) satisfies

z+u∈Wd−1(K)∩(Wd−1(K)+u−v).z + u \in W_{d-1}(K) \cap(W_{d-1}(K) + u - v).

Apply Lemma 12 to U=PU = P, V=QV = Q, and degree d−1d - 1. This degree lies between 11 and g−2g - 2. The resulting union is

(u+Wd−2(K))∪(−v+Wd−2(K)).(u + W_{d-2}(K)) \cup(-v + W_{d-2}(K)).

Subtracting uu gives

(−u+Wd−1(K))∩(−v+Wd−1(K))=Wd−2(K)∪(Wd−2(K)−δ).(29)\begin{aligned} (-u + W_{d-1}(K)) \cap(-v + W_{d-1}(K)) &= W_{d-2}(K) \cup(W_{d-2}(K) - \delta). \tag*{(29)} \end{aligned}

These two sets are again exchanged by τ\tau. Indeed, for w∈Wd−2(K)w \in W_{d-2}(K),

τ(w)=σ(w)−δ,τ(w−δ)=σ(w)−σ(δ)−δ=σ(w).\begin{aligned} \tau(w) &= \sigma(w) - \delta,\\ \tau(w - \delta) &= \sigma(w) - \sigma(\delta) - \delta\\ &= \sigma(w). \end{aligned}

Here we again use σ(δ)=−δ\sigma(\delta) = -\delta and σ(Wd−2(K))=Wd−2(K)\sigma(W_{d-2}(K)) = W_{d-2}(K). Since zz is fixed and belongs to the union in (29), the same membership argument forces zz to belong to both sets. In particular, z∈Wd−2(K)z \in W_{d-2}(K), as required.

Proposition 14. Let P,Q∈X(K)P, Q \in X(K) be ισ\iota\sigma-fixed points with finite distinct xx-coordinates. Then there is b∈J(K)b \in J(K) such that

(b+J(Fr))∩Wd(K)=∅(0≤d≤g−1).(30)(b + J(\mathbb{F}_r)) \cap W_d(K) = \varnothing\qquad(0 \le d \le g - 1). \tag*{(30)}

Proof of Proposition 14. Take u,v,δu, v, \delta from (22). Proposition 11 gives b∈J(K)b \in J(K) such that the fixed points of τ\tau are exactly b+J(Fr)b + J(\mathbb{F}_r).

We prove by induction on dd that no point of Wd(K)W_d(K) is fixed. For d=0d = 0, a fixed point would give τ(0)=0\tau(0) = 0, hence δ=0\delta= 0, a contradiction. For d=1d = 1, Lemma 13 gives W1(K)τ⊆{−u}∩{−v}=∅W_1(K)^\tau\subseteq\{-u\} \cap\{-v\} = \varnothing, since u≠vu \ne v. For 2≤d≤g−12 \le d \le g - 1, a fixed z∈Wd(K)z \in W_d(K) would satisfy z∈Wd−2(K)z \in W_{d-2}(K) by the same lemma, contrary to the induction hypothesis. Therefore (b+J(Fr))∩Wd(K)=∅(b + J(\mathbb{F}_r)) \cap W_d(K) = \varnothing for every 0≤d≤g−10 \le d \le g - 1, proving (30).

Proofs of the Main Results

Proof of Theorem 1

The geometric construction only requires two values of xx for which f(x)f(x) is a nonsquare in the subfield. The Weil bound gives these values uniformly under the numerical hypothesis of Theorem 1. It also supplies the inequality needed to choose the effective representative.

Lemma 15. Under the hypotheses of Theorem 1, one has n<q=r2n < q = r^2, and there are at least two distinct a∈Fra \in\mathbb{F}_r for which f(a)f(a) is a nonsquare in Fr\mathbb{F}_r.

Proof. The Weil bound [3 Sec. 5.2] states

r+1−2gr≤n≤r+1+2gr.(31)r + 1 - 2g\sqrt{r} \le n \le r + 1 + 2g\sqrt{r}. \tag*{(31)}

Put t=r≥2g+2t = \sqrt{r} \ge2g + 2. Then 2gt≤t2−2t=r−2t2gt \le t^2 - 2t = r - 2t, so

n≤2r+1−2t<2r<r2,n \le2r + 1 - 2t < 2r < r^2,

where r≥36r \ge36 has been used for the last inequality.

Let χ:Fr→{−1,0,1}\chi: \mathbb{F}_r \to\{-1, 0, 1\} be the quadratic character, equal to zero at zero, one at nonzero squares, and minus one at nonsquares. Write BB for the number of roots of ff in Fr\mathbb{F}_r, SS for ∑a∈Frχ(f(a))\sum_{a \in\mathbb{F}_r} \chi(f(a)), and MM for the number of nonsquare values. Counting the affine points, and then adding P0P_0, gives

n=r+1+S,S=r−B−2M.(32)n = r + 1 + S, \qquad S = r - B - 2M. \tag*{(32)}

Thus (31) already implies ∣S∣≤2gr|S| \le2g\sqrt{r}; no separate character-sum theorem is needed. Since B≤2g+1B \le2g + 1,

M≥r−(2g+1)−2gr2=t(t−2g)−(2g+1)2.(33)M \ge\frac{r - (2g + 1) - 2g\sqrt{r}}{2} = \frac{t(t - 2g) - (2g + 1)}{2}. \tag*{(33)}

Now t(t−2g)≥2t≥4g+4t(t - 2g) \ge2t \ge4g + 4. The last expression is at least (2g+3)/2>1(2g + 3)/2 > 1, proving the claim.

All parts of the construction are now available. We first find the coset and then apply the sufficient condition in Corollary 7.

Proof of Theorem 1. Let K=Fr2K = \mathbb{F}_{r^2}. Lemma 15 gives distinct a1,a2∈Fra_1, a_2 \in\mathbb{F}_r with f(ai)f(a_i) nonsquare. Each f(ai)f(a_i) has a square root yiy_i in KK, since its quadratic polynomial is irreducible over Fr\mathbb{F}_r and splits over its quadratic extension. The nontrivial automorphism of K/FrK/\mathbb{F}_r interchanges the roots, so yir=−yiy_i^r = -y_i. Hence the points P=(a1,y1)P = (a_1, y_1) and Q=(a2,y2)Q = (a_2, y_2) satisfy (21). Proposition 14 gives b∈J(K)b \in J(K) satisfying (30); taking d=g−1d=g-1 gives (16).

Lemma 15 also gives n<qn<q. By (2), k≥g+1k\ge g+1 and k+g−1≤n−1<nk+g-1\le n-1<n. Corollary 7 therefore applies with this bb and kk. It gives an effective KK-rational divisor GG of degree k+g−1k+g-1, with support disjoint from DD, such that CL(D,G)\mathcal{C}_L(D,G) is an [n,k,n−k+1]K[n,k,n-k+1]_K MDS code. Since K=FqK=\mathbb{F}_q, this proves the stated parameters and support condition.

Non-equivalence to GRS Codes

This subsection concerns only code equivalence under the hypothesis min⁡{k,n−k}≥3g+1\min\{k,n-k\}\ge3g+1. It is independent of the MDS construction and is not used to establish the MDS property.

Definition 4. Two length-nn linear codes over KK are monomially equivalent if one is obtained from the other by a permutation of coordinates and multiplication of each coordinate by a nonzero scalar. For distinct a1,…,an∈Ka_1,\ldots,a_n\in K and v1,…,vn∈K×v_1,\ldots,v_n\in K^\times, a generalized Reed–Solomon (GRS) code of dimension kk is

{(v1h(a1),…,vnh(an)):h∈K[x], deg⁡h<k}.\{(v_1h(a_1),\ldots,v_nh(a_n)):h\in K[x],\ \deg h<k\}.

Definition 5. For c,c′∈Knc,c'\in K^n, put c∗c′=(c1c1′,…,cncn′)c\ast c'=(c_1c'_1,\ldots,c_nc'_n). The Schur square of a linear code CC is

C∗2=span⁡K{c∗c′:c,c′∈C}.C^{\ast2}=\operatorname{span}_K\{c\ast c':c,c'\in C\}.

Its dimension is invariant under monomial equivalence. Indeed, a permutation acts on the square by the same permutation, and coordinate multipliers viv_i act by the nonzero multipliers vi2v_i^2.

Schur-square dimensions already distinguish AG codes in [9 Thm. 4.1]; see also [11 Lem. 8]. We use this established method with general defining divisors. Shortening will ensure injectivity after squaring, including at rate 1/21/2. We first state the standard multiplication theorem needed for those divisors.

Lemma 16. Let X/KX/K be a smooth projective geometrically irreducible curve of genus gg, and let HH be a KK-rational divisor of degree at least 2g+12g+1. Then the map

L(H)⊗KL(H)⟶L(2H),h1⊗h2⟼h1h2\mathcal{L}(H)\otimes_K\mathcal{L}(H)\longrightarrow\mathcal{L}(2H),\qquad h_1\otimes h_2\longmapsto h_1h_2

is surjective.

Proof. Over an algebraic closure K‾\overline{K}, this is the standard multiplication theorem for line bundles of degree at least 2g+12g+1 [15 Thm. 6]. Global sections commute with field extension for these line bundles. Hence tensoring the displayed map with K‾\overline{K} gives that surjective map. Its cokernel therefore becomes zero after tensoring with K‾\overline{K}. Faithful flatness of the field extension implies that the cokernel over KK was already zero.

The next proposition distinguishes the resulting codes from GRS codes at every fixed limiting rate, including rate 1/21/2. The shortening step ensures that evaluation remains injective after squaring.

Proposition 17. Let X/KX/K have genus g≥2g\ge2, and let DD be the sum of nn distinct KK-rational points. Let GG be a KK-rational divisor with support disjoint from DD, and suppose that C=CL(D,G)C=C_{\mathcal{L}}(D,G) is an MDS code of dimension kk with

deg⁡G=k+g−1<n,min⁡{k,n−k}≥3g+1.\deg G=k+g-1<n,\qquad\min\{k,n-k\}\ge3g+1.

Then CC is not monomially equivalent to a GRS code.

Proof. The dual of a GRS code is a GRS code, and taking duals preserves monomial equivalence. The duality theorem for AG codes [3 Thm. 2.2.8 and Prop. 2.2.10] expresses C⊥C^\perp, up to nonzero coordinate multipliers, as

CL(D,H0),deg⁡H0=n−k+g−1,C_{\mathcal{L}}(D,H_0),\qquad\deg H_0=n-k+g-1,

where H0H_0 is defined over KK and has support disjoint from DD. One obtains H0=D−G+(η)H_0=D-G+(\eta) by choosing a differential η\eta with a simple pole at every evaluation point [3 Lem. 2.2.9]; its residues give the coordinate multipliers. Since k≥3g+1k\ge3g+1, this degree is less than nn. Replacing CC by that evaluation code if necessary, we may assume k≤n/2k\le n/2.

Put t=2g−1t=2g-1 and choose any sum TT of tt distinct points in DD. The code shortened on these coordinates consists of the codewords that are zero there, followed by deletion of those coordinates. Since GG avoids DD, it is exactly

C′=CL(D−T,G−T).C'=C_{\mathcal{L}}(D-T,G-T).

Its dimension is k′=k−tk'=k-t. This follows either from the MDS property or from Riemann–Roch, since, on putting H=G−TH=G-T, we have

deg⁡H=k−g≥2g+1.\deg H=k-g\ge2g+1.

Write n′=n−tn'=n-t. The assumption 2k≤n2k\le n gives

2deg⁡H=2k−2g≤n−2g<n−2g+1=n′.2\deg H=2k-2g\le n-2g<n-2g+1=n'.

Lemma 16 therefore gives

(C′)∗2=CL(D−T,2H),(C')^{\ast2}=C_{\mathcal{L}}(D-T,2H),

and the last degree inequality makes the evaluation map on L(2H)\mathcal{L}(2H) injective. Riemann–Roch yields

dim⁡K(C′)∗2=2deg⁡H+1−g=2k′+g−1.(34)\dim_K(C')^{\ast2}=2\deg H+1-g=2k'+g-1. \tag*{(34)}

Shortening a GRS code on t<kt<k coordinates gives a GRS code of length n′n' and dimension k′k'. Indeed, the polynomial being evaluated must be divisible by the product of the tt corresponding linear factors. Factoring out that product gives the new nonzero coordinate multipliers. Products of polynomials of degree less than k′k' span all polynomials of degree at most 2k′−22k'-2. Thus the Schur square of this shortened GRS code has dimension

min⁡{n′,2k′−1}=2k′−1,\min\{n',2k'-1\}=2k'-1,

because 2k′−1=2k−4g+1<n′2k'-1=2k-4g+1<n'. This differs from (34) by g>0g>0. Monomial equivalence would preserve the dimension of the Schur square after the corresponding shortening. This contradiction proves the proposition.

In particular, for fixed gg and k/n→ρ∈(0,1)k/n\to\rho\in(0,1), the condition min⁡{k,n−k}≥3g+1\min\{k,n-k\}\ge3g+1 holds for all sufficiently large nn. This proves the non-GRS assertions in the asymptotic corollaries without excluding half-rate codes.

Proof of Corollary 2

Proof of Corollary 2. We may assume that r=q≥(2g+2)2r=\sqrt{q}\ge(2g+2)^2. Since r>2g+1r>2g+1, choose distinct c1,…,c2g+1∈Frc_1,\ldots,c_{2g+1}\in\mathbb{F}_r and put

f(x)=∏i=12g+1(x−ci).f(x)=\prod_{i=1}^{2g+1}(x-c_i).

This is square-free of degree 2g+12g+1. The finite branch points and P0P_0 give 2g+22g+2 rational points fixed by ι\iota. All other rational points occur in pairs. Therefore n=∣X(Fr)∣n=|X(\mathbb{F}_r)| is even.

With t=r≥2g+2t=\sqrt{r}\ge2g+2, the lower Weil bound gives

n≥t(t−2g)+1≥2t+1≥4g+5>2g+2.n\ge t(t-2g)+1\ge2t+1\ge4g+5>2g+2.

Substituting r=qr=\sqrt{q} into (31) gives (4), and dividing it by q\sqrt{q} proves n/q→1n/\sqrt{q}\to1 for fixed gg.

For a fixed 0<ρ<10<\rho<1, both ⌊ρn⌋\lfloor\rho n\rfloor and n−⌊ρn⌋n-\lfloor\rho n\rfloor tend to infinity linearly with nn. Hence they are at least 3g+13g+1 for all sufficiently large qq. Theorem 1 gives the MDS parameters, and Proposition 17 gives non-equivalence to GRS codes. Finally, k=⌊ρn⌋k=\lfloor\rho n\rfloor and (4) prove (5).

Remark. Put cρ=min⁡{ρ,1−ρ}c_\rho=\min\{\rho,1-\rho\} and

Rg,ρ=max⁡{2g+2,(3g+1)cρ−1−12}.R_{g,\rho}=\max\left\{2g+2,\frac{(3g+1)c_\rho^{-1}-1}{2}\right\}.

If q≥Rg,ρ4q\ge R_{g,\rho}^{4}, then the lower Weil bound gives n≥2q1/4+1≥(3g+1)cρ−1n\ge2q^{1/4}+1\ge(3g+1)c_\rho^{-1}. Hence k=⌊ρn⌋k=\lfloor\rho n\rfloor satisfies min⁡{k,n−k}≥3g+1\min\{k,n-k\}\ge3g+1. This is an explicit sufficient bound for both the MDS and the non-GRS assertions in Corollary 2.

Corollary 18. Fix g≥2g\ge2. For every odd square qq with q≥(2g+2)2\sqrt{q}\ge(2g+2)^2, there are genus-gg MDS algebraic geometry codes with parameters [n,n/2,n/2+1]q[n,n/2,n/2+1]_q, where nn is even and satisfies (4). If n≥6g+2n\ge6g+2, these codes are not monomially equivalent to GRS codes.

This follows from the parity and dimension checks in the proof of Corollary 2 and Theorem 1. The non-equivalence assertion follows from k=n−k=n/2≥3g+1k=n-k=n/2\ge3g+1.

Proof of Corollary 3

A curve of genus gg over Fs2\mathbb{F}_{s^2} is called maximal if it has s2+1+2gss^2+1+2gs rational points.

Lemma 19. Fix g≥2g\ge2 and a prime p≡−1(mod2(2g+1))p\equiv-1\pmod{2(2g+1)}. The curve XX in (6) is maximal over Fp2\mathbb{F}_{p^2}. Moreover, for every positive odd integer mm and r=p2mr=p^{2m},

∣X(Fr)∣=r+1+2gpm.(35)|X(\mathbb{F}_r)|=r+1+2gp^m. \tag*{(35)}

Proof. Put d=2g+1d=2g+1. The congruence on pp gives 2d∣p+12d\mid p+1. In particular, pp is odd and does not divide dd, so 1−xd1-x^d is square-free. Over Fp2\mathbb{F}_{p^2}, take the Hermitian curve with affine equation up+1+vp+1=1u^{p+1}+v^{p+1}=1. The formulas

x=u(p+1)/d,y=v(p+1)/2(36)x=u^{(p+1)/d},\qquad y=v^{(p+1)/2} \tag*{(36)}

satisfy y2=1−xdy^2=1-x^d. They define a nonconstant rational map to XX. This map extends to a finite surjective morphism between the smooth projective models over Fp2\mathbb{F}_{p^2}. Since the Hermitian curve is maximal, the covered curve XX is maximal over that field [16 Sec. 1].

The Frobenius eigenvalues α1,…,α2g\alpha_1,\ldots,\alpha_{2g} of XX over Fp2\mathbb{F}_{p^2} have modulus pp and sum −2gp-2gp by maximality. Equality in the triangle inequality forces every αi=−p\alpha_i=-p. Since mm is odd,

∣X(Fr)∣=r+1−∑i=12gαim=r+1−2g(−p)m=r+1+2gpm,\begin{aligned} |X(\mathbb{F}_r)|&=r+1-\sum_{i=1}^{2g}\alpha_i^m\\ &=r+1-2g(-p)^m\\ &=r+1+2gp^m, \end{aligned}

which is (35). □

Proof of Corollary 3. Put d=2g+1d=2g+1 and r=p2mr=p^{2m}, so that q=r2q=r^2. The congruence gives p≥4g+1p\ge4g+1 and p∤dp\nmid d. Thus 1−xd1-x^d is square-free and r≥(2g+2)2r\ge(2g+2)^2. Lemma 19 gives the point count (35).

Formula (35) gives n⟶∞n\longrightarrow\infty through odd mm. For fixed 0<ρ<10<\rho<1, both k=⌊ρn⌋k=\lfloor\rho n\rfloor and n−kn-k are therefore at least 3g+13g+1 for all sufficiently large odd mm, so (2) holds. Theorem 1 gives (3), and Proposition 17 gives non-equivalence to GRS codes. Finally, r=qr=\sqrt{q} and pm=q1/4p^m=q^{1/4} turn (35) into (7). □

Examples and the Scope of the Construction

We check the field sizes, point counts, and dimension conditions in three examples. These checks illustrate the general theorem, the half-rate consequence, and the exact family, respectively.

Example 20. Take g=2g=2, r=41r=41, and X:y2=1−x5X:y^2=1-x^5. Then q=1681q=1681 and r≥36r\ge36. The polynomial is square-free. In the notation of (32), direct calculation gives B=5B=5 and M=10M=10, whence

S=41−5−2⋅10=16,n=41+1+16=58.S=41-5-2\cdot10=16,\qquad n=41+1+16=58.

For example, f(6)=f(14)=15f(6)=f(14)=15 in F41\mathbb{F}_{41}, and 1515 is a nonsquare. Thus the two points required in the proof can be chosen above 66 and 1414. The range (2) is 3≤k≤563\le k\le56. Taking k=20k=20 gives an [58,20,39]1681[58,20,39]_{1681} code, with a defining divisor of degree 21.

Example 21. Take g=2g=2, r=41r=41, and

f(x)=x(x−1)(x−2)(x−3)(x−4).f(x)=x(x-1)(x-2)(x-3)(x-4).

Its five distinct roots and P0P_0 are rational. Here B=5B=5 and M=12M=12, so S=12S=12 and n=54n=54. Corollary 18 with k=27k=27 gives an [54,27,28]1681[54,27,28]_{1681} code, with a defining divisor of degree 28.

Example 22. Take g=3g=3, p=13p=13, and m=1m=1 in Corollary 3. The congruence 13≡−1(mod14)13\equiv-1\pmod{14} holds. We have r=169≥64r=169\ge64, q=28561q=28561, and

n=169+1+6⋅13=248.n=169+1+6\cdot13=248.

Taking ρ=1/2\rho=1/2 gives k=124k=124, and 4≤124≤2454\le124\le245, so the dimension condition holds already at m=1m=1. Thus we obtain an [248,124,125]28561[248,124,125]_{28561} code, with a defining divisor of degree 126.

All three examples also satisfy the hypothesis of Proposition 17. Table 2 gives the exact Schur-square dimensions after shortening on 2g−12g-1 coordinates. The strict difference proves non-equivalence to GRS codes; it is not a numerical assumption about a chosen generator matrix.

Original [n,k][n,k]Shortened [n′,k′][n',k']dim⁡(C′)∗2\dim(C')^{*2}GRS square
[58,20][58,20][55,17][55,17]3533
[54,27][54,27][51,24][51,24]4947
[248,124][248,124][243,119][243,119]240237

Table 2. Schur squares after shortening the three examples.

The point counts above verify the numerical inputs. The MDS conclusion follows from the geometric proof. We now specify a defining class, an effective divisor, and a generator matrix for the first example. This also separates a complete code construction from a check of its numerical parameters.

A Fully Specified Code over F1681\mathbb{F}_{1681}

Let K=F41(θ)K=\mathbb{F}_{41}(\theta) with θ2=3\theta^2=3. Since 3 is a nonsquare in F41\mathbb{F}_{41}, this is a quadratic field, and σ(θ)=−θ\sigma(\theta)=-\theta. Keep X:y2=f(x)=1−x5X:y^2=f(x)=1-x^5 and the evaluation divisor DD consisting of all 58 points in X(F41)X(\mathbb{F}_{41}). Set

P=(6,13θ),Q=(14,13θ).P=(6,13\theta),\qquad Q=(14,13\theta).

Here (13θ)2=15=f(6)=f(14)(13\theta)^2=15=f(6)=f(14), so these points satisfy (21). Define

uR(x)=x2+(35+21θ)x+23,u_R(x)=x^2+(35+21\theta)x+23,
vR(x)=(17+5θ)x+33+40θ.v_R(x)=(17+5\theta)x+33+40\theta.

The congruence vR2≡f(moduR)v_R^2\equiv f\pmod{u_R} and the square-freeness of uRu_R define an effective divisor RR of degree two by uR(x)=0u_R(x)=0, y=vR(x)y=v_R(x). Its Mumford class is b=[R−2P0]b=[R-2P_0].

Here is an exact certificate for (25). Put

uδ(x)=(x−6)(x−14),u_\delta(x)=(x-6)(x-14),
A(x)=x3+x2+33x+9,C=37θ.A(x)=x^3+x^2+33x+9,\qquad C=37\theta.

Polynomial multiplication and division over KK give

A−CvR≡0(moduR),A-Cv_R\equiv0\pmod{u_R},
A+Cσ(vR)≡0(modσ(uR)),A+C\sigma(v_R)\equiv0\pmod{\sigma(u_R)},
A2−C2f=uδuRσ(uR).A^2-C^2f=u_\delta u_R\sigma(u_R).

where C2=7C^2=7. The three factors on the last right-hand side are square-free and pairwise coprime. At P,QP,Q, the numerator A+CyA+Cy is nonzero, and at ι(P),ι(Q)\iota(P),\iota(Q) it vanishes. Its other zeros are precisely ι(R)+σ(R)\iota(R)+\sigma(R). Its pole at P0P_0 has order six. Consequently,

φ=A+CyA+Cy,(φ)=σ(R)+ι(R)−P−Q−2P0.\varphi=\frac{A+Cy}{\phantom{A+Cy}},\qquad(\varphi)=\sigma(R)+\iota(R)-P-Q-2P_0.

Since R+ι(R)∼4P0R+\iota(R)\sim4P_0, this proves

σ(b)−b=[P+Q−2P0]=δ.\sigma(b)-b=[P+Q-2P_0]=\delta.

Proposition 14 therefore applies to this specified class bb. To choose the effective representative for k=20k=20, put

ψ=y+vR(x)uR(x),G0=R+19P0,h=x9ψ+1.\psi=\frac{y+v_R(x)}{u_R(x)},\qquad G_0=R+19P_0,\qquad h=x^9\psi+1.

The poles of ψ\psi are the two points in RR and a pole of order one at P0P_0. Thus h∈L(G0)h\in L(G_0) and its pole at P0P_0 has order 19. We check that hh is nonzero at every finite evaluation point. For a∈F41a\in\mathbb{F}_{41}, uR(a)≠0u_R(a)\ne0: its θ\theta-coefficient is 21a21a, and uR(0)=23u_R(0)=23. If h(a,c)=0h(a,c)=0 with a,c∈F41a,c\in\mathbb{F}_{41}, the θ\theta-coefficient of

a9(c+vR(a))+uR(a)=0a^9(c+v_R(a))+u_R(a)=0

would give 5a10+40a9+21a=05a^{10}+40a^9+21a=0. The exact identity

gcd⁡(x41−x,5x10+40x9+21x)=x(x−15)\gcd(x^{41}-x,5x^{10}+40x^9+21x)=x(x-15)

leaves only a=0a=0 or a=15a=15. At a=0a=0 the numerator is 23, whereas f(15)=28f(15)=28 is a nonsquare in F41\mathbb{F}_{41}. Neither case gives a zero at an evaluation point. Hence

G=G0+(h)G=G_0+(h)

is effective of degree 21 and avoids DD, including P0P_0. Moreover,

[G−21P0]=[G0−21P0]=[R−2P0]=b.[G-21P_0]=[G_0-21P_0]=[R-2P_0]=b.

The code CL(D,G)C_L(D,G) is therefore [58,20,39]1681[58,20,39]_{1681} by Corollary 7.

For completeness, a basis of L(G0)L(G_0) is

1,x,…,x9,ψ,xψ,…,x9ψ.1,x,\ldots,x^9,\qquad\psi,x\psi,\ldots,x^9\psi.

The pole orders at P0P_0 are the distinct integers 0,1,…,190,1,\ldots,19, so these functions are independent. Riemann–Roch gives ℓ(G0)=20\ell(G_0)=20, proving that the list is a basis of the full space. Dividing the list by hh gives a basis of L(G)L(G).

Order the finite points Rj=(aj,cj)R_j=(a_j,c_j) of X(F41)X(\mathbb{F}_{41}) lexicographically using representatives 0,…,400,\ldots,40, and put R58=P0R_{58}=P_0. An explicit 20×5820\times58 generator matrix MM is specified by

Mi+1,j=ajih(Rj),(0≤i≤9, 1≤j≤57).M_{i+1,j}=\frac{a_j^i}{h(R_j)},\qquad(0\le i\le9,\ 1\le j\le57).
Mi+11,j=ajiψ(Rj)h(Rj).M_{i+11,j}=\frac{a_j^i\psi(R_j)}{h(R_j)}.

The last column has entry 1 in row 20 and zero elsewhere. This follows by taking values at P0P_0: h/(x9ψ)h/(x^9\psi) tends to 1, and all other basis elements have smaller pole order. Exact row reduction gives rank 20. Shortening on the first three columns gives rank 17 and Schur-square rank 35, agreeing with Table 2. These computations check the specified matrix; its MDS property follows from the divisor certificate and the coset proof.

Future Work

Extending the construction beyond hyperelliptic curves requires a new proof of the coset condition (16): Lemma 12 uses the degree-two map essentially.

The specified example shows how a Lang solution and a section give a generator matrix. A general algorithm must perform these steps uniformly: solve (25), represent its solution by a divisor, choose a section as in Lemma 6, and compute a basis of L(G)L(G). A complexity theorem requires analyzing each step.

Proposition 17 proves non-equivalence to GRS codes when min⁡{k,n−k}≥3g+1\min\{k,n-k\}\ge3g+1. Further equivalence questions concern different choices of the defining coset and comparisons with other non-GRS constructions, including [10, 11]. Determining the maximal attainable length and improving the leading constant of the present construction remain separate problems. The existence lower bound proved here supplies no matching upper bound.

Finally, the present argument does not give corresponding families in characteristic two, over nonsquare alphabet fields, or with a one-point defining divisor. These are questions for extending this construction, rather than claims that MDS constructions in those settings are unknown.

Acknowledgment

The authors acknowledge the assistance of ChatGPT 6 (OpenAI) in mathematical discussions and polishing the manuscript and correcting its grammar. Chuangqiang Hu was supported by the National Natural Science Foundation of China (No. 12441107).

References

References

  1. [1]I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” J. Soc. Industr. Appl. Math., vol. 8, no. 2, pp. 300–304, 1960, doi: 10.1137/0108018.DOI
  2. [2]V. D. Goppa, “Codes on algebraic curves,” Dokl. Akad. Nauk SSSR, vol. 259, no. 6, pp. 1289–1290, 1981 (in Russian).
  3. [3]H. Stichtenoth, Algebraic Function Fields, 2nd ed. Berlin, Germany: Springer, 2009, doi: 10.1007/978-3-540-76878-4.DOI
  4. [4]C. Munuera, “On the main conjecture on geometric MDS codes,” IEEE Trans. Inf. Theory, vol. 38, no. 5, pp. 1573–1577, 1992, doi: 10.1109/18.149510.DOI
  5. [5]C. Munuera, “On MDS elliptic codes,” Discrete Math., vol. 117, nos. 1–3, pp. 279–286, 1993, doi: 10.1016/0012-365X(93)90344-S.DOI
  6. [6]H. Chen, “On the main conjecture on geometric MDS codes,” Int. Math. Res. Not., vol. 1994, no. 8, pp. 313–318, 1994, doi: 10.1155/S107379289400036X.DOI
  7. [7]M. A. de Boer, “MDS codes from hyperelliptic curves,” in Arithmetic, Geometry and Coding Theory, R. Pellikaan, M. Perret, and S. G. Vlăduț, Eds. Berlin, Germany: Walter de Gruyter, 1996, pp. 23–34.
  8. [8]J. L. Walker, “A new approach to the main conjecture on algebraic-geometric MDS codes,” Des. Codes Cryptogr., vol. 9, no. 1, pp. 115–120, 1996, doi: 10.1007/BF00169780.DOI
  9. [9]H. Chen, “Many non-Reed–Solomon type MDS codes from arbitrary genus algebraic curves,” IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4856–4864, 2024, doi: 10.1109/TIT.2023.3348146. Preprint: arXiv:2208.05732v3, 2023.DOI
  10. [10]A. Marques, Y. da Silva, and S. Tafazolian, “Explicit LCP of MDS codes and LCD codes on hyperelliptic curves via Mumford representation,” arXiv:2607.16945v2, Oct. 2026.arxiv.org/abs/2607.16945
  11. [11]Y. Zhu, H. Chen, F. Peng, F. Zhang, and C.-A. Zhao, “New explicit constructions of MDS and NMDS algebraic geometry codes,” IEEE Trans. Inf. Theory, vol. 72, no. 9, pp. 6450–6465, 2026, doi: 10.1109/TIT.2026.3712030.DOI
  12. [12]H. Chen, C. Hu, and G. Ma, “Length bounds for MDS algebraic geometry codes of arbitrary positive genus,” arXiv:2610.39434v1, Oct. 2026.arxiv.org/abs/2610.39434
  13. [13]J. S. Milne, Abelian Varieties, ver. 2.00, 2008. [Online]. Available: https://www.jmilne.org/math/CourseNotes/AV.pdf
  14. [14]C. Arene, D. Kohel, and C. Ritzenthaler, “Complete addition laws on abelian varieties,” LMS J. Comput. Math., vol. 15, pp. 308–316, 2012, doi: 10.1112/S1461157012001027.DOI
  15. [15]D. Mumford, “Varieties defined by quadratic equations,” in Questions on Algebraic Varieties, C.I.M.E., III Ciclo, Varenna, 1969. Rome, Italy: Edizioni Cremonese, 1970, pp. 29–100.
  16. [16]A. Garcia, H. Stichtenoth, and C.-P. Xing, “On subfields of the Hermitian function field,” Compositio Math., vol. 120, no. 2, pp. 137–170, 2000, doi: 10.1023/A:1001736016924.DOI

Paper details

vlnc:W_d7asty6f
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 6

View statement
Looking for related papers…
Contents