On the Maximal Length of MDS Elliptic Codes

摘要

The determination of the maximal length of maximum distance separable (MDS) codes arising from elliptic curves is a central problem in coding theory. For an elliptic curve $E$ over $\mathbb{F}_q$, let $\operatorname{MEC}(k,q)$ denote the maximal length of a $q$-ary MDS elliptic code of dimension $k$. It was recently shown that $\operatorname{MEC}(k,q)\le\frac{q+1}{2}+\sqrt{q}$ for $q\ge289$ and $3\le k\le(q+1-2\sqrt{q})/10$, with equality for odd $k$ when $q$ is an odd square. This paper investigates the remaining open cases, namely even dimension $k$, non-square $q$ and fields of characteristic $2$, and provides a complete resolution of the tightness question for the two natural parity regimes of $q+1+\lfloor 2\sqrt{q}\rfloor$. We prove that if the support of $G$ (used to define the code) consists of $\mathbb{F}_q$-rational points, the bound decreases to $\frac{q+1}{2}+\sqrt{q}-1$ for even $k$. Without this restriction, we construct MDS codes attaining $\frac{q+1}{2}+\sqrt{q}$ for even $k$. More generally, we establish $\operatorname{MEC}(k,q)=\frac{q+1+\lfloor2\sqrt{q}\rfloor}{2}$ when $q+1+\lfloor2\sqrt{q}\rfloor$ is even, and $\operatorname{MEC}(k,q)=\frac{q+\lfloor2\sqrt{q}\rfloor}{2}$ when it is odd.

核心问题与主要方法

核心问题

Determine the maximal length of MDS elliptic codes for given dimension k over \mathbb{F}_q, especially the unresolved even-k, non-square-q, and characteristic-2 cases.

场景：Algebraic geometry codes from elliptic curves over finite fields; evaluation set D\subseteq E(\mathbb{F}_q), divisor G with degree k, and MDS criterion via sumset structure on E(\mathbb{F}_q).

主要方法

Reduces the MDS property for elliptic AG codes to a sumset exclusion condition: sum(G) not in Sigma_k(D) inside the finite abelian group E(F_q). Uses index-2 subgroup and coset structure of E(F_q) to characterize when length N/2 can or cannot be MDS, especially for even k. Shows that if D has size N/2 and G is supported only on F_q-rational points, then even-dimensional codes hit a sumset obstruction, forcing non-MDS behavior at the previous upper-bound length. Circumvents the obstruction by allowing G to include a higher-degree place, with a degree-3 place R satisfying sum([R])=O, enabling constructions at length N/2. Combines Hasse-Weil/Waterhouse existence of elliptic curves with parity of q+1+floor(2sqrt(q)) to convert curve-level N/2 bounds into exact formulas for MEC(k,q).

关键贡献与后续阅读

关键贡献

Determines exact MEC(k,q) values in the stated range for both parity regimes of q+1+floor(2sqrt(q)), resolving even-k, non-square-q, and characteristic-2 cases. Separates restricted-support and unrestricted-support behavior for the divisor G, proving a one-symbol loss under F_q-rational support for even k and recovering the upper bound when higher-degree places are allowed. Introduces an explicit construction of MDS elliptic codes using a degree-3 place in the support of G, addressing the obstruction that appears for even-dimensional codes with rational support. Provides characteristic-2 consequences via the same parity framework, including exact maximal lengths for binary-field regimes covered by the assumptions. Connects finite abelian group sumset results, index-2 cosets, elliptic curve rational point counts, and AG-code Riemann-Roch setup into a unified maximal-length analysis.

研究启发

Do the proofs of Theorems 15, 18, 23, 29, and 31 have any hidden exceptional cases beyond the stated q and k range? How constructive are the degree-3 place constructions for implementation over arbitrary finite fields, especially outside the explicit examples? Can the higher-degree-place technique extend to dimensions k outside 3 <= k <= (q+1-2sqrt(q))/10 or to higher-genus AG codes?

限制与不确定性

Impact may be specialized to algebraic geometry code theory rather than broad information theory. Results apply within the stated parameter range for k and q, so generality is limited. Assessment relies on structured analysis only, not independent verification of proofs.

参考文献

21 条

[1] S. Ball and M. Lavrauw (2018) Planar arcs . J. Combin. Theory Ser. A 160 , pp. 261–287 . External Links: ISSN 0097-3165,1096-0899 , Document , Link , MathReview (György Kiss) Cited by: §I .
[2] S. Ball and M. Lavrauw (2019) Arcs in finite projective spaces . EMS Surv. Math. Sci. 6 ( 1-2 ), pp. 133–172 . External Links: ISSN 2308-2151,2308-216X , Document , Link , MathReview (Yue Zhou) Cited by: §I .
[3] S. Ball (2012) On sets of vectors of a finite vector space in which every subset of basis size is a basis . J. Eur. Math. Soc. (JEMS) 14 ( 3 ), pp. 733–748 . External Links: ISSN 1435-9855,1435-9863 , Document , Link , MathReview (Gengsheng Zhang) Cited by: §I .
[4] J. M. Chao and H. Kaneta (1997) Classical arcs in PG ( r , q ) {\rm PG}(r,q) for 11 ≤ q ≤ 19 11\leq q\leq 19 . Vol. 174 , pp. 87–94 . Note: Combinatorics (Rome and Montesilvano, 1994) External Links: ISSN 0012-365X,1872-681X , Document , Link , MathReview Entry Cited by: §I .
[5] H. Chen and S. S.-T. Yau (1997) Contribution to Munuera’s problem on the main conjecture of geometric hyperelliptic MDS codes . IEEE Trans. Inform. Theory 43 ( 4 ), pp. 1349–1354 . External Links: ISSN 0018-9448,1557-9654 , Document , Link , MathReview Entry Cited by: §I .
[6] H. Chen (1994) On the main conjecture of geometric MDS codes . Internat. Math. Res. Notices ( 8 ), pp. 313 ff., approx. 6 pp.}, ISSN = 1073–7928,1687–0247, MRCLASS = 94B27 (11T71 14G15), MRNUMBER = 1289576, MRREVIEWER = Michael M. Dediu, DOI = 10.1155/S107379289400036X, URL = https://doi.org/10.1155/S107379289400036X, . Cited by: §I .
[7] D. Han and Y. Ren (2023) A tight upper bound for the maximal length of MDS elliptic codes . IEEE Trans. Inform. Theory 69 ( 2 ), pp. 819–822 . External Links: ISSN 0018-9448,1557-9654 , Document , Link , MathReview (Yan Liu) Cited by: TABLE I , §I , §I , § II-C , Lemma 10 , Remark 22 , Lemma 8 , Lemma 9 .
[8] D. Han and Y. Ren (2024) The maximal length of q q -ary MDS elliptic codes is close to q 2 \frac{q}{2} . Int. Math. Res. Not. IMRN ( 11 ), pp. 9036–9043 . External Links: ISSN 1073-7928,1687-0247 , Document , Link , MathReview (Juan Tena) Cited by: §I .
[9] J. W. P. Hirschfeld and G. Korchmáros (1996) On the embedding of an arc into a conic in a finite plane . Finite Fields Appl. 2 ( 3 ), pp. 274–292 . External Links: ISSN 1071-5797,1090-2465 , Document , Link , MathReview (Tamás Szőnyi) Cited by: §I .
[10] H. Kaneta and T. Maruta (1989) An elementary proof and an extension of Thas’ theorem on k k -arcs . Math. Proc. Cambridge Philos. Soc. 105 ( 3 ), pp. 459–462 . External Links: ISSN 0305-0041,1469-8064 , Document , Link , MathReview Entry Cited by: §I .
[11] J. Li, D. Wan, and J. Zhang (2015) On the minimum distance of elliptic curve codes . In 2015 IEEE International Symposium on Information Theory (ISIT) , Vol. , pp. 2391–2395 . External Links: Document Cited by: §I , §I , §I , Lemma 2 .
[12] X. Li, L. Ma, and C. Xing (2019) Optimal locally repairable codes via elliptic curves . IEEE Trans. Inform. Theory 65 ( 1 ), pp. 108–117 . External Links: ISSN 0018-9448,1557-9654 , Document , Link , MathReview (Hassan Khodaiemehr) Cited by: Lemma 5 .
[13] Y. Li, S. Zhu, and P. Li (2023) On MDS codes with Galois hulls of arbitrary dimensions . Cryptogr. Commun. 15 ( 3 ), pp. 565–587 . External Links: ISSN 1936-2447,1936-2455 , Document , Link , MathReview (Romar dela Cruz) Cited by: Lemma 34 .
[14] F. J. MacWilliams and N. J. A. Sloane (1977) The theory of error-correcting codes. I . North-Holland Mathematical Library , Vol. Vol. 16 , North-Holland Publishing Co., Amsterdam-New York-Oxford . External Links: ISBN 0-444-85009-0 , MathReview (Ian Blake) Cited by: §I .
[15] C. Munuera (1992) On the main conjecture on geometric MDS codes . IEEE Trans. Inform. Theory 38 ( 5 ), pp. 1573–1577 . External Links: ISSN 0018-9448,1557-9654 , Document , Link , MathReview (Francesco Fabris) Cited by: §I , §I , §I .
[16] H. Rück (1987) A note on elliptic curves over finite fields . Math. Comp. 49 ( 179 ), pp. 301–304 . External Links: ISSN 0025-5718,1088-6842 , Document , Link , MathReview (Joseph H. Silverman) Cited by: § II-B , Lemma 7 .
[17] J. H. Silverman (2009) The arithmetic of elliptic curves . Second edition , Graduate Texts in Mathematics , Vol. 106 , Springer, Dordrecht . External Links: ISBN 978-0-387-09493-9 , Document , Link , MathReview (Vasil \cprime Ī. Andrīĭchuk) Cited by: § II-A , Lemma 3 .
[18] H. Stichtenoth (2009) Algebraic function fields and codes . Second edition , Graduate Texts in Mathematics , Vol. 254 , Springer-Verlag, Berlin . External Links: ISBN 978-3-540-76877-7 , MathReview Entry Cited by: Lemma 4 .
[19] L. Storme and J. A. Thas (1993) M.D.S. codes and arcs in PG ( n , q ) {\rm PG}(n,q) with q q even: an improvement of the bounds of Bruen, Thas, and Blokhuis . J. Combin. Theory Ser. A 62 ( 1 ), pp. 139–154 . External Links: ISSN 0097-3165,1096-0899 , Document , Link , MathReview (J. W. P. Hirschfeld) Cited by: §I .
[20] J. L. Walker (1996) A new approach to the main conjecture on algebraic-geometric MDS codes . Vol. 9 , pp. 115–120 . Note: Second Upper Michigan Combinatorics Workshop on Designs, Codes and Geometries (Houghton, MI, 1994) External Links: ISSN 0925-1022,1573-7586 , Document , Link , MathReview Entry Cited by: §I , §I .
[21] W. C. Waterhouse (1969) Abelian varieties over finite fields . Ann. Sci. École Norm. Sup. (4) 2 , pp. 521–560 . External Links: ISSN 0012-9593 , Link , MathReview (M. J. Greenberg) Cited by: Lemma 6 .