WorksComputer Science
MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves
Abstract
For every fixed genus and every , we construct maximum distance separable (MDS) algebraic geometry codes over \F_q for all sufficiently large odd squares . Their parameters are with . The codes use full Riemann–Roch spaces on genus- hyperelliptic curves. They are not monomially equivalent to generalized Reed–Solomon (GRS) codes when is sufficiently large. An infinite subfamily has exact length .
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 for a finite field with elements. A linear code is a -dimensional subspace of with minimum Hamming distance . Its rate is . The Singleton bound is , and a code attaining equality is called maximum distance separable (MDS). On a curve of genus , the usual designed-distance bound for an algebraic geometry code can be smaller than by . 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 , the dimension is . The sufficient condition for length is
where is the number of rational points in the projective image. For fixed and , put
Here log denotes the natural logarithm. Stirling’s formula gives
Thus this sufficient condition can certify only 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-, dimension- pairs by requiring reduced Mumford representatives of degree for classes associated with every -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 in one specialization. For the Beelen–Montanucci branch, write , where is a prime power and is odd, and put
Theorem 1 of [11] uses a curve of genus
and a one-point divisor giving dimension . This genus varies with and ; for example, gives and dimension 4, while the genus grows with . 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 , full Riemann–Roch spaces, and eventual non-GRS codes. Table 1 records the scope of these comparisons.
| Result | Curves and defining divisors | Length and dimension guarantee |
| Chen [9 Thm. 4.3] | Arbitrary genus; one-point divisor. | ; at fixed rate, only . |
| Zhu et al. [11 Thm. 1, Cor. 3] | Beelen–Montanucci curves; one-point divisors. | Determinant/evaluation conditions; dimension ; genus varies with . |
| Zhu et al. [11 Thm. 4, Cors. 5–6, 11] | Genus two with split Jacobian. | Elliptic-cover and subset conditions; in Corollary 11; length depends on the point set. |
| Marques et al. [10 Prop. 6] | Hyperelliptic curves; complementary pairs. | Length , dimension ; reduced-degree MDS condition for every -subset. |
| Theorem 1, Corollary 2 | Hyperelliptic curves satisfying (1); general effective divisors. | , . |
Table 1. Scope of the closest MDS constructions.
The question considered here is the following. For every fixed , can one obtain algebraic geometry codes over with length asymptotic to 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 .
The evaluation points are defined over , and the defining divisor is defined over . 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 . 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 be an odd prime power, let , and assume . Let be a hyperelliptic curve of genus with an odd-degree affine model
Set , let , and let be the sum of the points in . For every integer
there is an effective -rational divisor of degree , with support disjoint from , such that is an MDS code.
Proposition 17 below gives the additional non-equivalence assertion: if , 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 tends to infinity through odd squares.
Corollary 2. Fix and . For every sufficiently large odd square , there are genus- MDS algebraic geometry codes, not monomially equivalent to generalized Reed–Solomon codes, with parameters
where satisfies
Writing , we have
The next consequence uses a fixed equation and gives an exact length.
Corollary 3. Fix , , and a prime . For every sufficiently large positive odd integer , put . On the curve
there are MDS codes, not monomially equivalent to generalized Reed–Solomon codes, with parameters (3) and
A recent preprint gives for fixed genus when both the dimension and the codimension grow faster than [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 , 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 be a finite field and let be a curve of genus . A divisor on is a finite sum , where runs through closed points and . Its degree is , where is the residue field at . It is effective, written , if every is nonnegative. Its support is the set of points with nonzero coefficient. Equivalently, a -rational divisor is a divisor on the geometric curve invariant under the Galois group of an algebraic closure over . It need not be a sum of points in .
Write for the function field of . For , its principal divisor is , where is the normalized order at . Two -rational divisors are linearly equivalent, written , if for such an . Set
The complete linear system consists of effective divisors linearly equivalent to . If is a canonical divisor, Riemann–Roch gives
In particular, if , and if ; see [3 Sec. 1.5].
Definition 1. Fix distinct , and put . If , every function in is regular at every . Define the evaluation map and the algebraic geometry code by
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 to make the subsequent sufficient condition self-contained.
Lemma 4. Suppose , and set . Then has dimension and minimum distance at least . It is MDS if and only if
for every sum of distinct points among .
Proof. The kernel of (10) is . Its degree is negative, so this space is zero. Thus evaluation is injective and its image has dimension .
Let be nonzero, and let be the sum of the evaluation points at which vanishes. The support condition on implies . Consequently, , since a divisor of negative degree has no nonzero section. The corresponding codeword has weight .
For a sum of distinct evaluation points, the kernel of evaluation on just those coordinates is . If (11) holds for all such , no nonzero codeword has zero coordinates. Its weight is therefore at least . The Singleton bound gives equality. Conversely, a nonzero element of evaluates to a nonzero codeword, by injectivity, with at least zero coordinates. Its weight is at most , 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 . Let be the Jacobian. Write for the linear-equivalence class of a divisor . The group identifies with the degree-zero divisor classes represented over . More generally, denotes the degree- line-bundle classes, and translation by identifies it with . The existence of ensures that these rational classes have line-bundle, and hence divisor, representatives over ; see [13 Part III, Sec. 1].
For an integer , let be the -th symmetric power of ; let be a point defined over . Its -points are effective -rational divisors of degree . Consider the Abel–Jacobi map
Definition 2. Let be the closed image of . Its set of -rational points is
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 but not over . The class is represented by a line bundle of degree defined over . If has a nonzero section over , then its section space is already nonzero over , because the dimension of this space does not change under field extension. Thus a nonzero section exists over , and its divisor is an effective -rational representative of the class.
On geometric points, the fibers of (12) are complete linear systems: for an effective divisor of degree ,
Indeed, if and only if .
In particular, , and adding to an effective divisor gives
The effective classes in form the theta divisor. Under the translation above, its inverse image in is [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 , , and are defined over . Let satisfy
For an integer , let be a -rational divisor with
Then for every sum of distinct evaluation points.
Proof. For such an , put . If , choose . Then is an effective -rational divisor of degree . Equations (17) and (13) give
contradicting (16). □
Effective Representatives with Disjoint Support
The coset argument produces a divisor class. Evaluation requires an actual divisor whose support avoids . The next elementary argument provides an effective representative without assuming that it is supported at rational points.
Lemma 6. Let and assume . For every and , there is an effective -rational divisor satisfying (17), with and .
Proof. Set . Represent by a -rational divisor of degree zero and put . Then and . Since , Riemann–Roch gives . For each evaluation point , the divisor has degree at least , so the same formula gives
Thus each is a proper subspace with elements. Their union has at most elements. Choose outside this union. In particular .
Set . It is effective because , and it has degree and the required class. At an evaluation point , let be the coefficient of . Membership in gives . Nonmembership in gives . This integer is therefore zero, which is exactly the coefficient of in . Hence the supports are disjoint. Finally, linear equivalence gives . □
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 , , and are defined over , where and . Let satisfy (16). For every integer , there is an effective -rational divisor of degree , with support disjoint from , such that is an MDS code.
Proof. Lemma 6 gives an effective -rational divisor satisfying (17), with support disjoint from and . Lemma 5 gives for every sum of distinct evaluation points. Since , 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 satisfying . We first use the hyperelliptic involution to prove an intersection formula for , and then combine it with Frobenius and fixed-point descent to obtain the required coset.
Divisors of Small Degree
Let , let be a finite field of odd characteristic, and let be the smooth projective model of , where is square-free and . The degree-two map to the projective line is branched at the roots of and at infinity. The Hurwitz formula gives genus . The point above infinity is unique, is -rational, and will be denoted by . The hyperelliptic involution is , extended to . For every finite geometric point , the divisor of gives
At a branch point the zero has multiplicity two. The same equivalence is immediate for . These are the fibers of the map .
Apply to each point of a divisor. For an effective -rational divisor of degree , relation (19) gives . The equivalence is defined over , either by multiplying the functions for the points in Galois orbits or by pulling back a divisor on . Consequently,
To control intersections of translates of , we first prove a structural fact about Riemann–Roch spaces of divisors of degree at most . Its consequence concerning hyperelliptic fibers is used below.
Lemma 8. Let be an effective -rational divisor with . If , then .
Proof. Since is effective, constants belong to . Choose a nonconstant , and let , where is its pole divisor. The associated map has degree , and .
Suppose . The extension has degree two, so . Thus is birational onto an integral curve in . Its two projection degrees are and . A curve with these projection degrees has arithmetic genus
For completeness, put and write for the tensor product of the pullbacks of the degree- and degree- line bundles from the two factors. Write for the alternating sum of cohomology dimensions. The exact sequence
and give this formula (with the factors interchanged if necessary). The normalization of is , and normalization can only decrease arithmetic genus. Hence , contradicting .
It follows that , as required. □
Corollary 9. Let be an effective -rational divisor with . If , then is linearly equivalent over to an effective divisor.
Proof. Choose a nonconstant . Lemma 8 gives . Let be its pole divisor on , and set . Then . Since , we have
as required. All the divisors and equivalences used here are defined over .
Frobenius and the Required Coset
Assume now that is defined over and . Let be the -power Frobenius endomorphism, acting on and on . On -points it has square equal to the identity, and its fixed subgroup on is . Since is rational over , we have .
Since and commute, is an involution on .
Definition 3. A point is called an -fixed point if , or equivalently .
Let be two such points with finite distinct -coordinates, so that
Put
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, , , and
Proof. Since is defined over , equations (19) and (21) give
The same computation gives . Adding these two identities gives .
Suppose . Then , so some nonconstant has divisor
Thus and are linearly independent elements of . Since , Lemma 8 gives . The divisor of poles of a function in pulls back under the degree-two map . Hence has no finite pole on , and its pole at infinity has order at most one. It follows that with . Every point in its zero divisor on has the same -coordinate . This contradicts , so .
If , then . Since , a function with divisor would give a degree-one map from to . Such a map identifies their function fields and would force to have genus zero. This contradicts . Thus .
Define
For , one has , since . Lemma 10 gives . Therefore
Thus is an involution.
We next identify the required coset with the fixed points of an involution.
Proposition 11. For as in (22), there is with . The fixed points of the involution in (24) are exactly .
Proof. The geometric points of the kernel of form the finite group . Since the differential of Frobenius is zero, the differential of is , so its kernel is finite and reduced. Thus is an isogeny and is surjective on geometric points [13 Part I, Prop. 7.1]. Choose satisfying
Applying and adding the resulting identity to (25) gives , so .
Finally, (25) shows that exactly when , that is, when . Hence the fixed points are .
Intersection Formula and Fixed-Point Descent
The next formula reduces an intersection involving degree to two translates involving degree . Its genus-two case, , 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 be distinct, and set , . For ,
Proof. Let belong to the left side. By (13), there are effective -rational divisors of degree such that
Subtracting these identities gives . If contains , the divisor is effective of degree , and .
Suppose instead that does not contain . Since , the divisor has coefficient zero at , whereas has a positive coefficient there. These are distinct effective divisors in the same complete linear system. Their linear equivalence gives a nonconstant with , so and . As , Corollary 9 gives an effective -rational divisor of degree with . It follows that
so . This proves one inclusion.
For the reverse inclusion, let . Then , and subtracting gives . Similarly, (19) gives . Subtracting now gives . Both sets on the right of (26) therefore lie in the intersection.
Lemma 13. For , write . Then
Moreover, for , one has .
Proof. We use the intersection formula twice.
Suppose and is fixed. Then belongs to , because this set is stable under . Therefore
Apply Lemma 12 with and . The distinct -coordinates ensure . Their divisor classes are and , so
For every , direct substitution in (24) gives
Since permutes , 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 . A point in the intersection in (27) satisfies
Apply Lemma 12 to , , and degree . This degree lies between and . The resulting union is
Subtracting gives
These two sets are again exchanged by . Indeed, for ,
Here we again use and . Since is fixed and belongs to the union in (29), the same membership argument forces to belong to both sets. In particular, , as required.
Proposition 14. Let be -fixed points with finite distinct -coordinates. Then there is such that
Proof of Proposition 14. Take from (22). Proposition 11 gives such that the fixed points of are exactly .
We prove by induction on that no point of is fixed. For , a fixed point would give , hence , a contradiction. For , Lemma 13 gives , since . For , a fixed would satisfy by the same lemma, contrary to the induction hypothesis. Therefore for every , proving (30).
Proofs of the Main Results
Proof of Theorem 1
The geometric construction only requires two values of for which 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 , and there are at least two distinct for which is a nonsquare in .
Proof. The Weil bound [3 Sec. 5.2] states
Put . Then , so
where has been used for the last inequality.
Let be the quadratic character, equal to zero at zero, one at nonzero squares, and minus one at nonsquares. Write for the number of roots of in , for , and for the number of nonsquare values. Counting the affine points, and then adding , gives
Thus (31) already implies ; no separate character-sum theorem is needed. Since ,
Now . The last expression is at least , 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 . Lemma 15 gives distinct with nonsquare. Each has a square root in , since its quadratic polynomial is irreducible over and splits over its quadratic extension. The nontrivial automorphism of interchanges the roots, so . Hence the points and satisfy (21). Proposition 14 gives satisfying (30); taking gives (16).
Lemma 15 also gives . By (2), and . Corollary 7 therefore applies with this and . It gives an effective -rational divisor of degree , with support disjoint from , such that is an MDS code. Since , this proves the stated parameters and support condition.
Non-equivalence to GRS Codes
This subsection concerns only code equivalence under the hypothesis . It is independent of the MDS construction and is not used to establish the MDS property.
Definition 4. Two length- linear codes over 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 and , a generalized Reed–Solomon (GRS) code of dimension is
Definition 5. For , put . The Schur square of a linear code is
Its dimension is invariant under monomial equivalence. Indeed, a permutation acts on the square by the same permutation, and coordinate multipliers act by the nonzero multipliers .
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 . We first state the standard multiplication theorem needed for those divisors.
Lemma 16. Let be a smooth projective geometrically irreducible curve of genus , and let be a -rational divisor of degree at least . Then the map
is surjective.
Proof. Over an algebraic closure , this is the standard multiplication theorem for line bundles of degree at least [15 Thm. 6]. Global sections commute with field extension for these line bundles. Hence tensoring the displayed map with gives that surjective map. Its cokernel therefore becomes zero after tensoring with . Faithful flatness of the field extension implies that the cokernel over was already zero.
The next proposition distinguishes the resulting codes from GRS codes at every fixed limiting rate, including rate . The shortening step ensures that evaluation remains injective after squaring.
Proposition 17. Let have genus , and let be the sum of distinct -rational points. Let be a -rational divisor with support disjoint from , and suppose that is an MDS code of dimension with
Then 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 , up to nonzero coordinate multipliers, as
where is defined over and has support disjoint from . One obtains by choosing a differential with a simple pole at every evaluation point [3 Lem. 2.2.9]; its residues give the coordinate multipliers. Since , this degree is less than . Replacing by that evaluation code if necessary, we may assume .
Put and choose any sum of distinct points in . The code shortened on these coordinates consists of the codewords that are zero there, followed by deletion of those coordinates. Since avoids , it is exactly
Its dimension is . This follows either from the MDS property or from Riemann–Roch, since, on putting , we have
Write . The assumption gives
Lemma 16 therefore gives
and the last degree inequality makes the evaluation map on injective. Riemann–Roch yields
Shortening a GRS code on coordinates gives a GRS code of length and dimension . Indeed, the polynomial being evaluated must be divisible by the product of the corresponding linear factors. Factoring out that product gives the new nonzero coordinate multipliers. Products of polynomials of degree less than span all polynomials of degree at most . Thus the Schur square of this shortened GRS code has dimension
because . This differs from (34) by . Monomial equivalence would preserve the dimension of the Schur square after the corresponding shortening. This contradiction proves the proposition.
In particular, for fixed and , the condition holds for all sufficiently large . 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 . Since , choose distinct and put
This is square-free of degree . The finite branch points and give rational points fixed by . All other rational points occur in pairs. Therefore is even.
With , the lower Weil bound gives
Substituting into (31) gives (4), and dividing it by proves for fixed .
For a fixed , both and tend to infinity linearly with . Hence they are at least for all sufficiently large . Theorem 1 gives the MDS parameters, and Proposition 17 gives non-equivalence to GRS codes. Finally, and (4) prove (5).
Remark. Put and
If , then the lower Weil bound gives . Hence satisfies . This is an explicit sufficient bound for both the MDS and the non-GRS assertions in Corollary 2.
Corollary 18. Fix . For every odd square with , there are genus- MDS algebraic geometry codes with parameters , where is even and satisfies (4). If , 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 .
Proof of Corollary 3
A curve of genus over is called maximal if it has rational points.
Lemma 19. Fix and a prime . The curve in (6) is maximal over . Moreover, for every positive odd integer and ,
Proof. Put . The congruence on gives . In particular, is odd and does not divide , so is square-free. Over , take the Hermitian curve with affine equation . The formulas
satisfy . They define a nonconstant rational map to . This map extends to a finite surjective morphism between the smooth projective models over . Since the Hermitian curve is maximal, the covered curve is maximal over that field [16 Sec. 1].
The Frobenius eigenvalues of over have modulus and sum by maximality. Equality in the triangle inequality forces every . Since is odd,
which is (35). □
Proof of Corollary 3. Put and , so that . The congruence gives and . Thus is square-free and . Lemma 19 gives the point count (35).
Formula (35) gives through odd . For fixed , both and are therefore at least for all sufficiently large odd , so (2) holds. Theorem 1 gives (3), and Proposition 17 gives non-equivalence to GRS codes. Finally, and 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 , , and . Then and . The polynomial is square-free. In the notation of (32), direct calculation gives and , whence
For example, in , and is a nonsquare. Thus the two points required in the proof can be chosen above and . The range (2) is . Taking gives an code, with a defining divisor of degree 21.
Example 21. Take , , and
Its five distinct roots and are rational. Here and , so and . Corollary 18 with gives an code, with a defining divisor of degree 28.
Example 22. Take , , and in Corollary 3. The congruence holds. We have , , and
Taking gives , and , so the dimension condition holds already at . Thus we obtain an 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 coordinates. The strict difference proves non-equivalence to GRS codes; it is not a numerical assumption about a chosen generator matrix.
| Original | Shortened | GRS square | |
| 35 | 33 | ||
| 49 | 47 | ||
| 240 | 237 |
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
Let with . Since 3 is a nonsquare in , this is a quadratic field, and . Keep and the evaluation divisor consisting of all 58 points in . Set
Here , so these points satisfy (21). Define
The congruence and the square-freeness of define an effective divisor of degree two by , . Its Mumford class is .
Here is an exact certificate for (25). Put
Polynomial multiplication and division over give
where . The three factors on the last right-hand side are square-free and pairwise coprime. At , the numerator is nonzero, and at it vanishes. Its other zeros are precisely . Its pole at has order six. Consequently,
Since , this proves
Proposition 14 therefore applies to this specified class . To choose the effective representative for , put
The poles of are the two points in and a pole of order one at . Thus and its pole at has order 19. We check that is nonzero at every finite evaluation point. For , : its -coefficient is , and . If with , the -coefficient of
would give . The exact identity
leaves only or . At the numerator is 23, whereas is a nonsquare in . Neither case gives a zero at an evaluation point. Hence
is effective of degree 21 and avoids , including . Moreover,
The code is therefore by Corollary 7.
For completeness, a basis of is
The pole orders at are the distinct integers , so these functions are independent. Riemann–Roch gives , proving that the list is a basis of the full space. Dividing the list by gives a basis of .
Order the finite points of lexicographically using representatives , and put . An explicit generator matrix is specified by
The last column has entry 1 in row 20 and zero elsewhere. This follows by taking values at : 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 . A complexity theorem requires analyzing each step.
Proposition 17 proves non-equivalence to GRS codes when . 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]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]V. D. Goppa, “Codes on algebraic curves,” Dokl. Akad. Nauk SSSR, vol. 259, no. 6, pp. 1289–1290, 1981 (in Russian).
- [3]H. Stichtenoth, Algebraic Function Fields, 2nd ed. Berlin, Germany: Springer, 2009, doi: 10.1007/978-3-540-76878-4.DOI
- [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]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]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]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]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]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]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]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]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]J. S. Milne, Abelian Varieties, ver. 2.00, 2008. [Online]. Available: https://www.jmilne.org/math/CourseNotes/AV.pdf
- [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]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]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