Dual and Covering Radii of Extended Algebraic Geometry Codes
Yunlong Zhu, Chang-An Zhao · 2025
Read Dual and Covering Radii of Extended Algebraic Geometry Codes by Yunlong Zhu, Chang-An Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21773.txt.
Introduction
Error-correcting codes protect data by adding structure, and algebraic geometry codes build that structure from curves. Yunlong Zhu and Chang-An Zhao study extended versions of these codes in this 2025 paper. Earlier work covered extended Reed-Solomon codes in depth, but the broader geometry codes with curves of genus one or more drew less attention. The authors fill that gap.
They work out the dual codes and smallest distances for extended geometry codes and a related family. For some curve genera, they show a code can reach a length once thought to need special curves, using the longest known curves. For small fields, that length is the largest known for its class. They also pin down how far a received word can stray while still being covered by the code. Only a short list of values is possible, and just two values when the genus is one.
Catalog record
| CREATOR | Yunlong Zhu, Chang-An Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-21773
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dual and Covering Radii of Extended Algebraic Geometry Codes Yunlong Zhu, Chang-An Zhao Abstract Many literatures consider the extended Reed-Solomon (RS) codes, including their dual codes and covering radii, but few focus on extended algebraic geometry (AG) codes of genus g ≥ 1 g\geq 1 . In this paper, we investigate extended AG codes and Roth-Lempel type AG codes, including their dual codes and minimum distances. Moreover, we show that for certain g g , the length of a g g -MDS code over a finite field 𝔽 q \mathbb{F}_{q} can attain q + 1 + 2 g q q+1+2g\sqrt{q} , which is achieved by an extended AG code from the maximal curves of genus g g . Notably, for some small finite fields, this length q + 1 + 2 g q q+1+2g\sqrt{q} is the largest among all known g g -MDS codes. Subsequently, we establish that the covering radius of an [ n , k ] [n,k] extended AG code has g + 2 g+2 possible values. For the case of g = 1 g=1 , we prove that this range reduces to two possible values when the length n n is sufficiently large, or when there exists an [ n , k + 1 ] [n,k+1] MDS elliptic code. 1 Introduction Let \mathbb{F}_{q} be a finite field with q elements. An [n,k] -linear code \mathcal{C} is a k -dimensional subspace of \mathbb{F}_{q}^{n} . For a non-zero vector {\bf v}=(v_{1},\ldots,v_{n})\in\mathbb{F}_{q}^{n} , the Hamming weight wt({\bf v}) is defined as the number of non-zero positions in {\bf v} , i.e., {\rm wt}({\bf v}):=\#\{i\mid v_{i}\neq 0,1\leq i\leq n\}. The distance between two vectors {\bf v} and {\bf u} is given by d({\bf v},{\bf u})={\rm wt}({\bf v-u}) and the minimum distance of \mathcal{C} is d:=\min\{d({\bf v},{\bf u})|{\bf v,u}\in\mathcal{C}\}. For an [n,k,d] -linear code \mathcal{C} , the well-known Singleton bound states that d+k\leq n+1. Linear codes achieving this equality are known as maximum distance separable (MDS) codes. The Singleton defect [ 1 ] of \mathcal{C} , denoted s(\mathcal{C}) , is defined as s(\mathcal{C})=n+1-k-d. A code \mathcal{C} is called \ell -MDS if s(\mathcal{C})=s(\mathcal{C}^{\perp})=\ell [ 2 ] . In particular, a 1 -MDS code, is also called a near-MDS (NMDS) code. A central problem in coding theory involves determining the maximum possible length of \ell -MDS codes. We recall the famous MDS conjecture proposed by Segre [ 3 ] : Conjecture 1.1 . Let \mathcal{C} be an [n,k] MDS code over \mathbb{F}_{q} . Then \displaystyle n\leq\begin{cases}q+2\ \text{\rm if $q$ is even and $k\in\{3,q-1\}$},\\ q+1\ \text{\rm otherwise}.\end{cases} While this conjecture remains open in general, partial results can be found, for example, in [ 4 , 5 , 6 ] . The covering radius \rho(\mathcal{C}) of a linear code \mathcal{C} is the smallest integer such that spheres of radius \rho(\mathcal{C}) centered at all codewords cover \mathbb{F}_{q}^{n} . This concept represents a fundamental parameter in coding theory [ 7 ] , with many further investigations in [ 8 , 9 , 10 , 11 , 12 , 13 ] . Vectors at distance \rho(\mathcal{C}) from \mathcal{C} are called deep holes. Notably, deep holes of MDS codes preserve the MDS property when appended to their generator matrices, as proven by Kaipa [ 14 ] and Wu et al. [ 15 ] . Both the minimum distance and the covering radius determination for general linear codes are NP-hard problems [ 16 , 17 ] . For algebraic geometric (AG) codes, the minimum distance satisfies d\geq d^{*} where d^{*} denotes the designed distance. However, bounds on the covering radii remain scarce; we refer the reader to [ 18 ] , [ 19 ] for some results. When n\leq q , Zhuang et al. proposed that the Reed-Solomon (RS) codes over \mathbb{F}_{q} achieve a covering radius \rho=n-k [ 20 ] . Bartoli et al. demonstrated that there exist specific MDS elliptic codes with \rho=n-k-1 [ 21 ] . Zhang and Wan further showed that elliptic codes also have \rho=n-k-1 for sufficiently large n [ 8 ] . Nevertheless, the covering radii of general MDS codes remain largely undetermined [ 22 ] . Motivations and Contributions Extended AG codes from curves of genus g are observed to achieve the maximum length among all known g -MDS codes over small finite fields, as recorded in the MAGMA database [ 23 ] . This motivates investigating their maximality over arbitrary finite fields \mathbb{F}_{q} . While the existing literature primarily focuses on the genus 0 case, extended AG codes with g\geq 1 remain largely unexplored, to the best of our knowledge. For g=0 , extended RS codes are the well-known MDS codes with length n=q+1 . Under the MDS conjecture, these codes become maximal MDS codes when 4\leq k\leq q-2 . Zhang et al. investigated the covering radii of extended RS codes [ 22 ] , and showed that these codes have two possible values. Very recently, Wu et al. proposed improved results for extended RS codes [ 15 ] , while Wu et al. further determined the covering radii of non-standard extended RS codes [ 24 ] , including Roth-Lempel codes [ 25 ] . Additionally, Li et al. analyzed the covering radii of two extended twisted generalized RS codes [ 26 ] . Consequently, a natural problem arises for the case of g\geq 1 : can one determine the dual codes, minimum distances and covering radii of extended AG codes? Our main results are summarized as follows. 1. Utilizing the Weil differential, we explicitly determine the generator matrix of the dual codes for extended AG codes. By establishing an isomorphism between a function space and a differential space over \mathbb{F}_{q} via a canonical divisor of function fields, we propose a function-based generator matrix for the dual code of an extended AG code, which generalizes the result for standard AG codes. Subsequently, we explicitly derive the lower bound of the minimum distances for extended AG codes, and investigate the MDS property of extended AG codes. Furthermore, we consider three cases of AG codes, from the projective line, elliptic curves and Hermitian curves respectively. We then present the explicit dual code and minimum distances for these codes. 2. We explicitly determine dual code generators for Roth-Lempel type AG codes, providing both differential-based and function-based generator matrices. A sufficient condition for the minimum distance of these codes is established. For elliptic curves, we further establish a condition for Roth-Lempel-type elliptic codes to be NMDS. 3. We adapt covering radius bounds from [ 19 ] to extended AG codes. Furthermore, for elliptic curves, we prove that the covering radius of extended elliptic codes has two possible values when n is sufficiently large or when an [n,k+1] MDS elliptic code exists. Organization This paper is organized as follows. In Section II, we provide an essential overview of algebraic geometry codes, elliptic curves and covering radii. Section III details our main results on extended AG codes and Roth-Lempel type AG codes. In Section IV, we discuss the covering radius bounds for extended AG codes. Finally, Section V concludes the paper and discusses our future research directions. 2 Preliminaries In this section, we review fundamental definitions and concepts, including AG codes and covering radii for linear