# Low-Rank Representations Towards Classification Problem of Complex Networks

Murat Çelik<EMAIL_ADDRESS>Department of Computer Engineering,
Hacettepe UniversityAnkaraTurkey06800 ,  Ali Baran Taşdemir
<EMAIL_ADDRESS>Department of Computer Engineering,
Hacettepe UniversityAnkaraTurkey06800 and  Lale Özkahya
<EMAIL_ADDRESS>Department of Computer Engineering,
Hacettepe UniversityAnkaraTurkey06800

###### Abstract.

Complex networks representing social interactions, brain activities, molecular
structures have been studied widely to be able to understand and predict their
characteristics as graphs. Models and algorithms for these networks are used
in real-life applications, such as search engines, and recommender systems. In
general, such networks are modelled by constructing a low-dimensional
Euclidean embedding of the vertices of the network, where proximity of the
vertices in the Euclidean space hints the likelihood of an edge (link). In
this work, we study the performance of such low-rank representations of real-
life networks on a network classification problem.

Graph embeddings, graph representations, low-dimensional embedding, low-rank
representation.

††copyright: none

##  1\. Introduction

Complex networks representing social interactions, brain activities, molecular
structures have been studied widely to be able to understand and predict their
characteristics as graphs. Building good models for complex networks,
considering the role of social networks in understanding modern human
interaction, is very important (Barabási and Albert, 1999; Chakrabarti and
Faloutsos, 2006; Watts and Strogatz, 1998). In recent years, obtaining low-
dimensional embeddings of graph nodes in Euclidean space has been frequently
studied in machine learning applications,and in this way, thanks to the
geometry of the embedding, it has been tried to preserve the structural
properties of the graph (Hamilton et al., 2017). Specifically, the node
embedding method represents each node in the n-node graph as a vector of
$x\in\mathbb{R}^{k}$ and $k<<n$. In this way, the embedding method is used in
many subjects such as clustering, classification, link prediction, together
with machine learning (Hamilton et al., 2017). In this sense, the probability
of an edge/link between two nodes can be deduced from the geometric proximity
of the vectors representing them.

Two of these embedding methods that are widely used are TSVD (Truncated
Singular Value Decomposition) and PCA (Logistic Principal Component Analysis)
methods such as decomposition of the adjacency matrix of the given network (or
graph) (Ahmed et al., 2013). In recent years, the method of learning graph
embedding using deep neural networks has been frequently used (Cao et al.,
2016; Grover and Leskovec, 2016; Perozzi et al., 2014; Tang et al., 2015). The
question these methods are trying to solve is to get a given large networks to
be represented by matrices of smaller dimensions than the original, while
preserving its structural properties. One of the still unanswered questions is
how small of a matrix this representation can be done while preserving the
structural information of the network (Seshadhri et al., 2020; Chanpuriya et
al., 2020; Loukas, 2019; Garg et al., 2020). For example, the frequent
occurrence of triangles is an important characteristic in social networks such
as Facebook, and the extent to which this can be preserved by graph embedding
techniques such as TSVD and PCA has been researched (Seshadhri et al., 2020;
Chanpuriya et al., 2020), (Stolman et al., 2022), binary node classification
question, the class labels of the nodes were applied as graph characteristics.

The main contribution of this work is to examine the performance of the
commonly used TSVD and LPCA graph embedding techniques in the multiclass
classification problem of the original graph. The graph classification
question is a problem that has been studied in many different fields, and in
some cases it has difficulties such as trying to extract class information
without sufficient network information. Bonner et al. (Bonner et al., 2016)
developed a learning method for graph classification by using the topology
features of the network using deep neural networks. One of the comprehensive
studies in terms of the variety of random graph models was done by Rossi and
Ahmed (Rossi and Ahmed, 2019). In this study, 9 network classes with
distinctly different structures, including network groups constructed with
random network models, are included in the classification question. It has
been observed that the reconstructed networks to be represented at low
dimensions by graph embedding methods largely preserve their class properties.
As a result of the experiments, it was seen that the LPCA method gave better
performance than the TSVD method. It has been observed that random networks
need much larger sizes than real world networks in order to be successfully
represented.

Table 1. The average values for each network group of the attributes used in
the classification process.

Graph Classes | Number of Node | Number of Edge | Density | Max. Degree | Avg. Degree | Max. k-core |  | Avg. Clustering
---
Coefficient
Number of Triangles |  | Avg. Eigenvector
---
Centrality
Barabasi-Albert | 1000 | 35409 | 0.0709 | 278 | 71 | 40 | 0.127 | 767320 | 0.0247
Biological | 2715 | 27895 | 0.0098 | 339 | 20 | 37 | 0.256 | 272918 | 0.0096
Brain | 487 | 12561 | 0.2358 | 245 | 48 | 35 | 0.520 | 398615 | 0.0610
Chung-Lu | 5201 | 21437 | 0.0045 | 167 | 8 | 16 | 0.072 | 9449 | 0.0105
Economic | 2283 | 100090 | 0.1574 | 863 | 120 | 111 | 0.437 | 5518546 | 0.0255
Enzymes | 60 | 94 | 0.0948 | 6 | 4 | 3 | 0.287 | 21 | 0.0989
Erdos-Renyi | 1000 | 37583 | 0.0752 | 99 | 75 | 62 | 0.075 | 410869 | 0.0310
Facebook | 6314 | 231472 | 0.0138 | 987 | 76 | 64 | 0.258 | 1910524 | 0.0086
Retweet | 5586 | 6396 | 0.0005 | 1972 | 2 | 4 | 0.013 | 236 | 0.0055

##  2\. Method

In the classification process, different real network groups such as biology,
economy and social networks, as well as different network groups produced by
random methods, constitute the classes of the classification process. The
performance of TSVD and LPCA methods is compared to how much the
representation of the original networks given by the graph embedding methods
by the graphs in lower dimensions preserves the class feature.Classification
is done by using the graph features, which are known to play an important role
in graphs.

###  2.1. Graph Embedding Methods

#### TSVD :

TSVD (Truncated Singular Value Decomposition) is a spectral method that
approximates the adjacency matrix by using SVD (Singular Value Decomposition).
The TSVD method is used to reconstruct the adjacency matrix. For an adjacency
matrix $A\in\left\\{0,1\right\\}^{N\times N}$, let $Z\in\mathbb{R}^{N\times
k}$ be the orthonormal matrix. The columns of the orthonormal matrix $Z$
include the eigenvectors of the adjacency matrix corresponding to the k
largest magnitude eigenvalues. And we define $W$ as diagonal with entries
corresponding to the top k eigenvalues. Then we calculate TSVD embeddings by
$X=Zs(W)\sqrt{|W|}$ and $Y=Z\sqrt{|W|}$. The $s()$ function represents the
sign function. To compute the reconstructed adjacency matrix we compute
$\sigma(XY^{T})$ where $\sigma$ is a clipping function between 0 and 1.

#### LPCA :

We use another method based on the LPCA (Logistic PCA) to approximate the
adjacency matrix. With a logistic loss function, we are trying to minimize the
error between $\sigma(XY^{T})$ (approximation) and A (adjacency matrix). For a
given $A\in\left\\{0,1\right\\}^{N\times N}$, and $X,Y\in\mathbb{R}^{N\times
k}$, we use the loss function:

$L=\sum_{i=1}^{N}\sum_{j=1}^{N}-\log
l\left(\tilde{A}_{i,j}\left[XY^{T}\right]_{i,j}\right)$

where $l(x)=(1+e^{-x})^{-1}$ is logistic function and $\tilde{A}$ is the
shifted adjacency matrix with -1’s in place of 0’s ($\tilde{A}=2A-1$). We
initialize X and Y with random values between $\left[-1,1\right]$. And we find
X and Y embeddings that minimize the loss function by using SciPy (Jones et
al., 2001) implementation of the ”L-BFGS-B” (Byrd et al., 1995) algorithm with
100 iterations. And we reconstruct the approximated adjacency matrix by using
$\sigma(XY^{T})$.

In both of these graph embedding methods, the rank of operation is the $k$
value seen in the size of the obtained matrices.

###  2.2. Graph Attributes and Models

The features used are density, maximum degree, average degree, maximum k-core,
average clustering coefficient, total number of triangles, average eigenvector
centrality, which are also seen in Table 1. Below are the definitions of these
graph attributes. A graph is defined as $G=(V,E)$ with the node set $V$ and
the edge set $E$. The parameters $n=|V|$ and $m=|E|$ will represent the number
of elements of these sets. The number of neighboring nodes connected to each
node is the degree of that node, and the maximum, minimum and average (over
$n$) values defined on the graphs are among the attributes that play an
important role in areas such as coloring and matching problems. The value of
graph density, one of the most important graph parameters affecting the
algorithmic runtime, is calculated as $\frac{m}{{n\choose 2}}$. In this
context, if a graph contains $n^{2}$ edges, it means that it is dense, and
sparse otherwise.

A graph’s clustering coefficient measures the clustering tendency of the nodes
in the graph (Watts and Strogatz, 1998). Eigenvector centrality measures the
effect of one node on other nodes. The eigenvector centrality of a node is the
value of the digit corresponding to that node in the eigenvector of the
largest eigenvalue of the adjacency matrix. If a node has a high degree, that
node will have a high eigenvector centrality. Another important network
parameter is the $k$-core of the diagram (Sarıyüce et al., 2017; Liu and
Sarıyüce, 2019). The k-core of a graph is the number of nodes in the largest
possible subgraph that includes at least $k$ neighbors of each node in it.

###  2.3. Classification Process

Random Forest (RF), Stochastic Gradient Descent (SGD), K-Nearest Neighbor
(KNN) and Support Vector Machines (SVM) Classifiers are used as Machine
Learning model. In the training phase, F1 scores are obtained by stratified,
10-fold cross validation, and optimization study is carried out with the help
of these scores.F1 score is a statistical measure calculated by taking the
harmonic average of precision and recall values. These scores are observed as
0.87, 0.77, 0.86, and 0.89 for Random Forest (RF), Stochastic Gradient Descent
(SGD), K-Nearest Neighbor (KNN), and Support Vector Machines (SVM),
respectively. A second F1 score is obtained on the optimized models by
determining 20% of the training data set as the test data set. Support Vector
Machines (SVM) with an F1 score of 0.92 among the results are observed as the
most suitable model for classification. For this reason, the performances of
graph embedding methods are compared over the F1 score results obtained with
SVM in the following sections.

##  3\. Experimental Results

For the experiments, a total of 198 graphs from 9 different classes are
studied (Rossi and Ahmed, 2015). These network groups and their number of
elements: Biology Networks (bio, 30), Brain Networks (bn, 10), Economy
Networks (econ, 16), Retweet Networks (rt, 29), Facebook Networks (fb, 30),
Enzymes Networks ( enz, 30), Barabási–Albert Networks (ba, 13), Chung-Lu
Networks (cl, 24), Erdős–Rényi Networks (er, 16),the attributes of the
networks are given in Table-1 as the mean value. The last three of these
network groups have been created with the named random network models and are
used to represent different network structures.

Table 2. Average values of F1-scores found with the SVM classifier over all network groups when using different ranks of graph embedding methods. TSVD | LPCA
---|---
Rank | F1 Score | Rank | F1 Score
16 | 0.48 | 5 | 0.51
32 | 0.52 | 16 | 0.82
64 | 0.70 | 32 | 0.92
128 | 0.81 | 64 | 0.97

The main distinction between random network models is that the probability of
the edge added between two nodes differs according to the model. In the BA
model (Barabási and Albert, 1999), as a node is added at each step, each new
edge is determined in direct proportion to the degrees of pre-existing nodes.
In the ER model (Erdös and Rényi, 1959), the number of node pairs is
${n\choose 2}$, and each pair turns into an edge with a fixed probability $p$.
The CL model (Chung and Lu, 2002) generalizes the ER model to fit the
expectation of a given node degree (number of neighbors) distribution with
unequal edge probabilities.

###  3.1. Classification Accuracy

Since the SVM provides the highest F1 score during the training phase, the
values of this classifier are taken as a reference in terms of performance
during the testing phase. When the mean F1 score across all networks are
compared, the values seen in Table 2 are found to be 0.70 and 0.81 for TSVD
(for grade = 64 and 128), LPCA (for grade = 64 and 128) 0.92 and 0.97,
respectively. From this point of view, LPCA provides higher accuracy for the
same rank than TSVD.

Figure 1. Confusion matrix obtained by TSVD method and evaluating
classification accuracy over all network groups. Figure 2. Confusion matrix
obtained by LPCA method and evaluating classification accuracy over all
network groups.

When the confusion matrices seen in Figure 1 and 2 are compared, it is also
seen that the classification performance of LPCA is superior to TSVD. In
addition, classification performance is low in networks such as BA, CL. In
particular, the performance of the LPCA for the BA group is weaker than for
the other groups. In this sense, on the classification question, it is
concluded that these methods could not achieve the same success as for real-
life networks in random networks.

Table 3. Values of the (minimum) factorization dimension size obtained using
the LPCA method, providing successful classification with an F1 score of 92%
for the tested network groups.

Graph Classes | Number of Node | Average Degree | Rank
---|---|---|---
Biological | 2715 | 19.58 | 5
Enzymes | 60 | 3.47 | 5
Retweet | 5585 | 2.34 | 5
Brain | 487 | 47.50 | 16
Chung-Lu | 5201 | 7.96 | 16
Economic | 2283 | 120.02 | 16
Erdos-Renyi | 1000 | 75.17 | 32
Facebook | 6314 | 76.10 | 32
Barabasi-Albert | 1000 | 70.82 | 64

Table 3 lists the values of the (minimum) factorization dimension size
obtained using the LPCA method, which provides all networks in the group to be
classified with an F1 score of 92% for the network groups tested. Looking at
these values, it is observed that the LPCA method gives successful results in
graph embedding with a very small rank value for Biology, Enzymes and Retweet
networks. As seen in Table 1, these networks are networks with low density and
average degree. Generally, in random networks (BA, CL, ER), higher rank is
required to reach the same level of precision.

Calculation Time : For comparison purposes, one network each from the Economy
and BA random network group is selected and the computational speed of the
LPCA and TSVD methods is compared in Table 4. The computation time for TSVD is
found to be much shorter than for LPCA. It is predicted that this time spent
for LPCA will increase further if the number of iterations increases. The same
difference is seen for large networks other than the two example networks
given here, making TSVD preferable in terms of computation time.

Table 4. Comparison of the computation times (in seconds) of the two methods on econ-beause (n=0.5K, m=44K) and ba_1k_150k (n=1K, m=150K) networks, for purposes of example. | econ-beause | ba_1k_150k
---|---|---
Rank | TSVD | LPCA | TSVD | LPCA
16 | 0.40 | 3.54 | 1.75 | 15.98
32 | 0.44 | 3.86 | 1.65 | 14.33
64 | 0.36 | 2.60 | 1.70 | 15.19

##  4\. Conclusions

In this study, it is seen that the networks reconstructed to be represented at
low dimensions by graph embedding methods largely preserved their class
properties.On the other hand, in similar studies, it is seen that some
features, such as the triangle distribution, which are important in the
analysis of networks, are not sufficiently preserved by the methods presented
here. In this respect, the presented methods need improvement to preserve
different graph properties in the reconstruction process.

## References

  * (1)
  * Ahmed et al. (2013) Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander J Smola. 2013.  Distributed large-scale natural graph factorization. In _Proceedings of the 22nd international conference on World Wide Web_. 37–48.
  * Barabási and Albert (1999) Albert-László Barabási and Réka Albert. 1999.  Emergence of scaling in random networks.  _science_ 286, 5439 (1999), 509–512.
  * Bonner et al. (2016) Stephen Bonner, John Brennan, Georgios Theodoropoulos, Ibad Kureshi, and Andrew Stephen McGough. 2016\.  Deep topology classification: A new approach for massive graph classification. In _2016 IEEE International Conference on Big Data (Big Data)_. IEEE, 3290–3297.
  * Byrd et al. (1995) Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. 1995\.  A limited memory algorithm for bound constrained optimization.  _SIAM Journal on scientific computing_ 16, 5 (1995), 1190–1208.
  * Cao et al. (2016) Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2016.  Deep neural networks for learning graph representations. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 30.
  * Chakrabarti and Faloutsos (2006) Deepayan Chakrabarti and Christos Faloutsos. 2006.  Graph mining: Laws, generators, and algorithms.  _ACM computing surveys (CSUR)_ 38, 1 (2006), 2–es.
  * Chanpuriya et al. (2020) Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. 2020\.  Node embeddings and exact low-rank representations of complex networks.  _Advances in Neural Information Processing Systems_ 33 (2020), 13185–13198.
  * Chung and Lu (2002) Fan Chung and Linyuan Lu. 2002.  The average distances in random graphs with given expected degrees.  _Proceedings of the National Academy of Sciences_ 99, 25 (2002), 15879–15882.
  * Erdös and Rényi (1959) Paul Erdös and Alfréd Rényi. 1959.  On random graphs I.  _Publicationes Mathematicae (Debrecen)_ 6 (1959), 290–297.
  * Garg et al. (2020) Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. 2020\.  Generalization and representational limits of graph neural networks. In _International Conference on Machine Learning_. PMLR, 3419–3430.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks. In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_. 855–864.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * Jones et al. (2001) Eric Jones, Travis Oliphant, Pearu Peterson, et al. 2001\.  SciPy: Open source scientific tools for Python.  (2001).
  * Liu and Sarıyüce (2019) Penghang Liu and Ahmet Erdem Sarıyüce. 2019\.  Analysis of Core and Truss Decompositions on Real-World Networks.  _MLG workshop at Knowledge Discovery and Data Mining Conference, Anchorage, AK, USA_ (2019).
  * Loukas (2019) Andreas Loukas. 2019\.  What graph neural networks cannot learn: depth vs width.  _arXiv preprint arXiv:1907.03199_ (2019).
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. 701–710.
  * Rossi and Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed. 2015.  The Network Data Repository with Interactive Graph Analytics and Visualization. In _AAAI_.  http://networkrepository.com
  * Rossi and Ahmed (2019) Ryan A Rossi and Nesreen K Ahmed. 2019.  Complex networks are structurally distinguishable by domain.  _Social Network Analysis and Mining_ 9, 1 (2019), 51\.
  * Sarıyüce et al. (2017) Ahmet Erdem Sarıyüce, C Seshadhri, and Ali Pinar. 2017\.  Parallel local algorithms for core, truss, and nucleus decompositions.  _arXiv. org e-Print archive, https://arxiv. org/abs/1704.00386_ (2017).
  * Seshadhri et al. (2020) C Seshadhri, Aneesh Sharma, Andrew Stolman, and Ashish Goel. 2020.  The impossibility of low-rank representations for triangle-rich complex networks.  _Proceedings of the National Academy of Sciences_ 117, 11 (2020), 5631–5637.
  * Stolman et al. (2022) Andrew Stolman, Caleb Levy, C Seshadhri, and Aneesh Sharma. 2022\.  Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling.  _arXiv preprint arXiv:2201.08481_ (2022).
  * Tang et al. (2015) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015\.  Line: Large-scale information network embedding. In _Proceedings of the 24th international conference on world wide web_. 1067–1077.
  * Watts and Strogatz (1998) Duncan J Watts and Steven H Strogatz. 1998.  Collective dynamics of ‘small-world’networks.  _Nature_ 393, 6684 (1998), 440.


# Many Non-Reed-Solomon Type MDS Codes From Arbitrary Genus Algebraic Curves

Hao Chen Hao Chen is with the College of Information Science and
Technology/Cyber Security, Jinan University, Guangzhou, Guangdong Province,
510632, China<EMAIL_ADDRESS>The research of Hao Chen was supported by
NSFC Grant 62032009.

###### Abstract

It is always interesting and important to construct non-Reed-Solomon type MDS
codes in coding theory and finite geometries. In this paper, we prove that
there are non-Reed-Solomon type MDS codes from arbitrary genus algebraic
curves. It is proved that MDS algebraic geometry (AG) codes from higher genus
curves are not equivalent to MDS AG codes from lower genus curves. For genus
one case, we construct MDS AG codes of small consecutive lengths from elliptic
curves. New self-dual MDS AG codes over ${\bf F}_{{2^{s}}}$ from elliptic
curves are also constructed. These MDS AG codes are not equivalent to Reed-
Solomon codes, not equivalent to known MDS twisted Reed-Solomon codes and not
equivalent to Roth-Lempel MDS codes.

Hence many non-equivalent MDS AG codes, which are not equivalent to Reed-
Solomon codes and known MDS twisted-Reed-Solomon codes, can be obtained from
arbitrary genus algebraic curves. It is interesting open problem to construct
explicit longer MDS AG codes from maximal curves.

Index terms: MDS AG code, Reed-Solomon code, Twisted Reed-Solomon code, Self-
dual MDS code.

##  1 Introduction and Preliminaries

The Hamming weight $wt({\bf a})$ of a vector ${\bf a}\in{\bf F}_{q}^{n}$ is
the number of non-zero coordinate positions. The Hamming distance $d({\bf
a},{\bf b})$ between two vectors ${\bf a}$ and ${\bf b}$ is defined to be the
Hamming weight of $wt({\bf a}-{\bf b})$. For a code ${\bf C}\subset{\bf
F}_{q}^{n}$, its minimum Hamming distance

$d({\bf C})=\min_{{\bf a}\neq{\bf b}}\\{d({\bf a},{\bf b}),{\bf a}\in{\bf
C},{\bf b}\in{\bf C}\\}$

is the minimum of Hamming distances $d({\bf a},{\bf b})$ between any two
different codewords ${\bf a}$ and ${\bf b}$ in ${\bf C}$. For a linear code
${\bf C}\subset{\bf F}_{q}^{n}$, its minimum Hamming distance is its minimum
Hamming weight. For a linear $[n,k,d]_{q}$ code, the Singleton bound asserts
$d\leq n-k+1$. When equality holds, this code is an MDS code. We refer to [37,
48] for the theory of error-correcting codes. In [48, Page 317], the Chapter
11 ”MDS codes” is called ”one of the most fascinating chapters in all of
coding theory”.

The main conjecture of linear MDS codes proposed in [58] claims that the
length of a linear MDS code over ${\bf F}_{q}$ is at most $q+1$, except some
exceptional cases. In [3] the main conjecture was proved for linear MDS codes
over prime fields. Some classification results about general MDS codes over
small fields were given in [42]. An $(n,M=q^{n-d},d)_{q}$ code is called
almost MDS. A linear almost MDS code ${\bf C}$ satisfying that the dual ${\bf
C}^{\perp}$ is also almost MDS is called near MDS code. It is well-known that
AG codes from elliptic curves are near MDS codes. The main conjecture of near
MDS codes was proposed in [44]. For counting the number of MDS linear codes,
we refer to [29, 41].

We say that two codes ${\bf C}_{1}$ and ${\bf C}_{2}$ in ${\bf F}_{q}^{n}$ are
equivalent if ${\bf C}_{2}$ can be obtained from ${\bf C}_{1}$ by a
permutation of coordinates and the multiplication of a Hamming weight $n$
vector ${\bf v}=(v_{1},v_{2},\ldots,v_{n})\in{\bf F}_{q}^{n}$ on coordinates,
where $v_{i}\neq 0$ for $i=1,\ldots,n$. That is

${\bf C}_{2}=\\{{\bf c}=(c_{1},\ldots
c_{n}):(c_{1},\ldots,c_{n})=(v_{1}x_{1},\ldots,v_{n}x_{n}),{\bf x}\in
Perm({\bf C}_{1})\\},$

where $Perm({\bf C}_{1})$ is the code obtained from ${\bf C}_{1}$ by a
coordinate permutation. Equivalent codes have the same code length, the
dimension and the minimum Hamming distance.

Reed-Solomon codes proposed in the 1960 paper [55] are well-known MDS codes.
Let $P_{1},\ldots,P_{n}$ be $n\leq q$ distinct elements in ${\bf F}_{q}$. The
Reed-Solomon code $RS(n,k)$ is defined by

$RS(n,k)=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf F}_{q}[x],\deg(f)\leq k-1\\}.$

This is a $[n,k,n-k+1]_{q}$ linear MDS codes, because a degree $\deg(f)\leq
k-1$ polynomial has at most $k-1$ roots. These codes were called ”the greatest
codes of them all” in [32, Chapter 5]. Reed-Solomon codes are AG codes from
the genus zero curve. It should be mentioned that Reed-Solomon codes were
widely used in secret sharing, secure multiparty computation, see [59, 49, 13,
18, 20] and distributed storage systems, see [16].

MDS codes which are not equivalent to Reed-Solomon codes are called non-Reed-
Solomon type MDS codes. It is always interesting and important to construct
non-Reed-Solomon MDS codes in coding theory and finite geometries, we refer to
[56, 8, 10, 12]. One method used to distinguish MDS codes from Reed-Solomon
codes is the calculation of dimensions of their Schur squares, see [10, 12].
The componentwise product (star product) of $t$ vectors ${\bf
x}_{j}=(x_{j,1},\ldots,x_{j,n})\in{\bf F}_{q}^{n}$, $j=1,\ldots,t$, is ${\bf
x}_{1}\star\cdots\star{\bf x}_{t}=(x_{1,1}\cdots x_{t,1},\ldots,x_{1,n}\cdots
x_{t,n})\in{\bf F}_{q}^{n}$. The componentwise product of linear codes ${\bf
C}_{1},\ldots,{\bf C}_{t}$ in ${\bf F}_{q}^{n}$ is defined by

${\bf C}_{1}\star\cdots\star{\bf C}_{t}=\Sigma_{{\bf c}_{i}\in{\bf C}_{i}}{\bf
F}_{q}{\bf c}_{1}\star\cdots\star{\bf c}_{t}.$

When ${\bf C}_{1}={\bf C}_{2}={\bf C}$, the componentwise product ${\bf
C}\star{\bf C}$ is called the Schur square of the linear code ${\bf C}$. It is
clear that Schur squares of equivalent linear codes are equivalent. Hence the
dimension and the minimum Hamming distance of Schur squares are invariants of
two equivalent linear codes. The dimension of the Schur square of the Reed-
Solomon $[n,k,n-k+1]_{q}$, $2k\leq n\leq q+1$, is $2k-1$. Then any MDS
$[n,k,n-k+1]_{q}$ code ${\bf C}$ satisfying $\dim({\bf C}\star{\bf C})\geq
2k$, is a non-Reed-Solomon type MDS code, see [12].

The interest to construct non-Reed-Solomon type MDS codes comes from the
invention of the twisted Gabidulin codes in the rank-metric. Rank-metric codes
attaining the similar Singleton bound $|{\bf C}|\leq q^{n(n-d_{r}({\bf
C})+1)}$ is called maximal rank distance (MRD) codes, where $d_{r}({\bf C})$
is the minimum rank-distance of the rank-metric code ${\bf C}$. Gabidulin
codes are well-known MRD codes and can be thought as the rank-metric analogue
of Reed-Solomon codes, see [27]. It is a great achievement that some twisted
Gabidulin codes were found in [60]. These rank-metric codes are MRD codes,
which are not equivalent to Gabidulin codes, see [60, 52]. Then many papers,
see e.g., [17, 46, 65], were published for constructing new twisted Gabidulin
codes.

Motivated by the progress of twisted Gabidulin codes, twisted Reed-Solomon
codes were introduced by P. Beelen, S. Puchsinger, J. Nielson and J.
Rosenkilde in [10, 12]. Some of these twisted Reed-Solomon codes are MDS code,
see Section 4 of [12] and [45], and MDS twisted Reed-Solomon codes are non
Reed-Solomon type MDS codes. However it seems that there are strong
restrictions on lengths of these MDS twisted Reed-Solomon codes, see [12]. In
fact, in an earlier paper [56], some non-Reed-Solomon type MDS codes were
constructed and studied. Twisted Hermitian codes from Hermitian curves were
introduced in a recent paper [2].

The (Euclid) dual of a linear code ${\bf C}\subset{\bf F}_{q}^{n}$ is ${\bf
C}^{\perp}=\\{{\bf
c}=(c_{1},\ldots,c_{n}):\Sigma_{i=1}^{n}c_{i}x_{i}=0,\forall{\bf
x}=(x_{1},\ldots,x_{n})\in{\bf C}\\}$. A linear code is called self dual if
${\bf C}={\bf C}^{\perp}$. In general the linear code ${\bf C}\bigcap{\bf
C}^{\perp}$ is called the hull of ${\bf C}$. The Hermitian dual of a linear
code ${\bf C}\subset{\bf F}_{q^{2}}^{n}$ is

${\bf C}^{\perp_{h}}=\\{{\bf
c}=(c_{1},\ldots,c_{n}):\Sigma_{i=1}^{n}c_{i}x_{i}^{q}=0,\forall{\bf
x}=(x_{1},\ldots,x_{n})\in{\bf C}\\}.$

It is clear ${\bf C}^{\perp_{h}}=({\bf C}^{\perp})^{q}$, where

${\bf C}^{q}=\\{(c_{1}^{q},\ldots,c_{n}^{q}):(c_{1}\ldots,c_{n})\in{\bf
C}\\}.$

The minimum distance of the Euclid dual is called the dual distance and is
denoted by $d^{\perp}$. The minimum distance of the Hermitian dual is the same
as $d^{\perp}$. A linear code ${\bf C}\subset{\bf F}_{q^{2}}^{n}$ is called
Hermitian self-dual if ${\bf C}={\bf C}^{\perp_{h}}$. The intersection ${\bf
C}\bigcap{\bf C}^{\perp_{h}}$ is called the Hermitian hull of this code ${\bf
C}$. We refer to [22, 23] and [37, Chapter 9] for earlier results about self-
dual and Hermitian self-dual codes over small fields. From the Calderbank-
Shor-Steane (CSS) construction of entanglement-assisted quantum error
correction (EAQEC) codes in [15], Euclidean and Hermitian self-dual MDS codes
can be used to construct MDS EAQEC codes.

The construction of new self-dual MDS codes or near MDS codes has been a long
active topic in coding theory, see [31, 9, 36, 38, 39, 53, 68, 30, 26]. On the
other hand the construction of Hermitian self-orthogonal (or dual-containing)
MDS codes had been active for the purpose to construct MDS quantum codes, see
[34, 40, 4, 5, 6] and references therein. Since the introduction of twisted
Reed-Solomon codes in [10, 12], the construction of non-Reed-Solomon self-dual
MDS codes from twisted Reed-Solomon codes has been given in [36, 64]. These
codes are not equivalent to the Reed-Solomon codes and can be thought as new
self-dual MDS codes. From the view of coding theory, it is always interesting
to construct non-Reed-Solomon type MDS codes and non-Reed-Solomon type self-
dual MDS codes.

Let ${\bf X}$ be an absolutely irreducible, smooth and genus $g$ curve defined
over ${\bf F}_{q}$. Let ${\bf P}=\\{P_{1},\ldots,P_{n}\\}$ be the set of $n$
distinct rational points of ${\bf X}$ over ${\bf F}_{q}$. Let ${\bf G}$ be a
rational divisor over ${\bf F}_{q}$ of degree $\deg({\bf G})$ satisfying
$2g-2<\deg({\bf G})<n$ and

$support({\bf G})\bigcap{\bf P}=\emptyset.$

Let ${\bf L}({\bf G})$ be the function space associated with the divisor ${\bf
G}$, that is, ${\bf L}({\bf G})$ is the space of all rational functions $f$
satisfying $(f)+{\bf G}\geq 0$, where $(f)$ is the divisor associated with
$f$. The algebraic geometry code (functional code) associated with ${\bf G}$,
${\bf P}=\\{P_{1},\ldots,P_{n}\\}$ is defined by

${\bf C}({\bf P},{\bf G},{\bf X})={\bf C}(P_{1},\ldots,P_{n},{\bf G},{\bf
X})=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf L}({\bf G})\\}.$

The dimension of this code is

$k=\deg({\bf G})-g+1$

follows from the Riemann-Roch Theorem. The minimum Hamming distance is

$d\geq n-\deg({\bf G}).$

Algebraic-geometric residual code ${\bf C}_{\Omega}(P_{1},\ldots,P_{n},{\bf
G},{\bf X})$ with the dimension $k=n-m+g-1$ and minimum Hamming distance
$d\geq m-2g+2$ can be defined, we refer to [37, 66] for the detail. It is the
dual code of the functional code of the dimension $m-g+1$. The AG codes from
elliptic curves satisfy $k+d\geq\deg({\bf G})+n-\deg({\bf G})=n$. Hence these
elliptic curve codes are near MDS codes.

A divisor ${\bf G}=\Sigma m_{i}G_{i}$ where $G_{i}$’s are points of the curve,
is called effective if $m_{i}\geq 0$. Two effective divisor ${\bf G}_{1}$ and
${\bf G}_{2}$ are called linear equivalent if there is a rational function $f$
such that the divisor $(f)$ associated with $f$ is of the form

$(f)={\bf G}_{1}-{\bf G}_{2}.$

It is clear that for two linear equivalent divisors ${\bf G}_{1}$ and ${\bf
G}_{2}$, the AG codes ${\bf C}(P_{1},\ldots,P_{n},{\bf G}_{1},{\bf X})$ and
${\bf C}(P_{1},\ldots,P_{n},{\bf G}_{2},{\bf X})$ are equivalent linear codes.

It is well-known that AG codes from elliptic curves are best examples of
linear codes with the Singleton defect $n+1-d-k=1$. However it is also well-
known that MDS codes can be obtained from elliptic curve codes if the
evaluation points are carefully chosen. This is similar to many works on Reed-
Solomon codes in which evaluation points have to be determined in a
complicated pattern, see [32] and references therein. The main conjecture for
MDS codes from curves of genus $1$ (elliptic) and $2$ was proved in old papers
[50, 51], also see [67]. The main conjecture for MDS AG codes arising from
hyper-elliptic curves was proved independently in [19] and [14]. For a tighter
upper bound on the maximal length of MDS codes from elliptic curves, we refer
to a recent paper [33]. The self-dual near MDS codes from elliptic curves were
constructed in [39] and some non-extendable near MDS codes from elliptic
curves were constructed in a recent paper [1]. We also refer to [25] for the
earlier work on near MDS codes. In [8] some MDS $[n,k,n-k+1]_{q}$ codes with
the covering radius $n-k-1$ were constructed as extended codes of MDS codes
from elliptic curves. It is well-known that the covering radius of the Reed-
Solomon $[n,k,n-k+1]_{q}$ code is $n-k$. Therefore these MDS codes in [8] are
non-Reed-Solomon type MDS codes. It is interesting and important to ask the
following question about MDS AG codes.

Problem. Can MDS AG codes be obtained from arbitrary genus curves by choosing
evaluation points carefully? Are these MDS AG codes non-Reed-Solomon type?
Moreover are these MDS AG codes equivalent to each other?

In this paper, we prove that there are many non-Reed-Solomon type MDS codes
over ${\bf F}_{q}$ from arbitrary genus curves. It is proved that MDS AG codes
from genus $g_{1}$ curves are not equivalent to MDS AG codes from genus
$g_{2}$ curves, if $g_{1}>g_{2}$. In the range of lengths $n$ satisfying
$n\leq q^{1/4}$ and $\gcd(n,q)=1$, non-Reed-Solomon type MDS elliptic curve
codes can be constructed for consecutive lengths. These codes can be
constructed as AG codes from elliptic curves ${\bf E}$ defined over ${\bf
F}_{q}$ by choosing the evaluation point set as a coset of a subgroup of ${\bf
E}({\bf F}_{q})$. They are not equivalent to Reed-Solomon codes, not
equivalent to the known MDS twisted Reed-Solomon codes and not equivalent to
Roth-Lempel MDS codes in [56]. Moreover there are non-Reed-Solomon type MDS
elliptic curve codes with the same length and the same dimension. Many new
self-dual non-Reed-Solomon type MDS codes with various lengths are also
constructed. It is always good to understand that algebraic geometry codes can
give us more interesting non-Reed-Solomon type MDS codes.

##  2 AG codes from elliptic curves

###  2.1 Elliptic curves over finite fields

In this subsection, we recall basic facts about elliptic curves defined over a
finite field, which are mainly from the paper [57].

Let ${\bf E}$ be an elliptic curve defined over ${\bf F}_{q}$. It is well-
known that when $q$ is not a power of $2$ or $3$, then elliptic curves over
${\bf F}_{q}$ can be realized as a non-singular plane cubic curve. Let ${\bf
E}({\bf F}_{q})$ be the set of all ${\bf F}_{q}$-rational points of ${\bf E}$.
The number $|{\bf E}({\bf F}_{q})|$ of its rational points over ${\bf F}_{q}$
satisfies the Hasse bound

$|q+1-|{\bf E}({\bf F}_{q})||\leq 2\sqrt{q}.$

For any positive real number $x$ we set

$x^{-}=x+1-2\sqrt{x},$

and

$x^{+}=x=1+2\sqrt{x}.$

If $q=p$ is a prime number it follows from the result in [24, 57] that for any
positive integer $N$ satisfying $p^{-}<N<p^{+}$, there is an elliptic curve
${\bf E}$ defined over ${F}_{p}$ such that the number of ${\bf
F}_{p}$-rational points of ${\bf E}$ satisfying

$|{\bf E}({\bf F}_{p})|=N.$

It is well-known there is an Abelian group structure on ${\bf E}({\bf
F}_{q})$. As a group ${\bf E}({\bf F}_{q})\simeq{\bf Z}/m{\bf Z}\times{\bf
Z}/mk{\bf Z}$ for some positive integers $m$ and $k$. We refer to [62, 57] for
the detail. More accurately the following two results were proved in [57].

Theorem 2.1 (Theorem 1a in [57]). All the possible orders $|{\bf E}({\bf
F}_{q})|$ of an elliptic curve ${\bf E}$ defined over ${\bf F}_{q}$, where
$q=p^{n}$ is a prime power, are given by

$|{\bf E}({\bf F}_{q})|=1+q-\beta,$

where $\beta$ is an integer with $|\beta|\leq 2\sqrt{q}$ satisfying one of the
following conditions:
(a) $\gcd(\beta,p)=1$;
(b) If $n$ is even: $\beta=\pm 2\sqrt{q}$;
(c) If $n$ is even and $p\neq 1$ $mod$ $3$: $\beta=\pm\sqrt{q}$;
(d) If $n$ is odd and $p=2$ or $3$: $\beta=\pm p^{\frac{n+1}{2}}$;
(e) If either (i) $n$ is odd or (ii) $n$ is even, and $p\neq 1$ $mod$ $4$:
$\beta=0$.

All possible group structures of elliptic curves over ${\bf F}_{q}$ were also
determined in [57].

Theorem 2.2 (Theorem 3 in [57]). Let ${\bf E}$ be an elliptic curve over a
finite field ${\bf F}_{q}$ with $q=p^{n}$ elements. Let $|{\bf E}({\bf
F}_{q})|=\prod_{l}l^{h_{l}}$ be the prime factoring. Then all the possible
groups ${\bf E}({\bf F}_{q})$ with the order $|{\bf E}({\bf F}_{q})|$ are the
following,

${\bf Z}/p^{h_{p}}{\bf Z}\times\prod_{l\neq p}({\bf Z}/l^{a_{l}}{\bf
Z}\times{\bf Z}/l^{h_{l}-a_{l}}{\bf Z}),$

with
(a) In case (b) of Theorem 3.1: Each $a_{l}$ is equal to $\frac{h_{l}}{2}$;
(b) In cases (a), (c), (d), (e) of Theorem 3.1: $a_{l}$ is an arbitrary
integer satisfying

$0\leq a_{l}\leq\min\\{v_{l}(q-1),[\frac{h_{l}}{2}]\\},$

where $v_{l}(q-1)$ is the order of prime factor $l$ in $q-1$.

From Theorem 2.1 and 2.2, there are a lot of elliptic curves with different
orders $|{\bf E}({\bf F}_{q})|$ and different Abelian group structures.
Therefore we can construct many MDS elliptic curve codes from the following
Theorem 2.3.

###  2.2 MDS codes from elliptic curves

The following basic facts about AG codes from elliptic curves are well-known,
for example, see [51, 8]. Let ${\bf E}$ be an elliptic curve defined over the
finite field ${\bf F}_{q}$. Let $P_{0},P_{1},\ldots,P_{n}$ be $n+1$ rational
points. We take the divisor ${\bf G}=mP_{0}$, where $0<m\leq n-1$. Then an AG
code ${\bf C}(P_{1},\ldots,P_{n},{\bf G},{\bf E})$ from this elliptic curve
${\bf E}$ is constructed. This is a linear $[n,m,\geq n-m]_{q}$ code.

Theorem 2.3. 1) The minimum Hamming distance of ${\bf
C}(P_{1},\ldots,P_{n},{\bf G},{\bf E})$ is $n-m$ if and only if there are $m$
distinct points $P_{i_{1}},\ldots,P_{i_{m}}$ in the set
$\\{P_{1},\ldots,P_{n}\\}$ such that the effective divisor
$P_{i_{1}}+\cdots+P_{i_{m}}$ is linear equivalent to the divisor $mP_{0}$.
2) If there is an effective rational divisor ${\bf G}_{1}$ satisfying that
${\bf G}_{1}+{\bf G}$ is linearly equivalent to the effective divisor
$P_{1}+\cdots+P_{n}$. The the dual code of ${\bf C}(P_{1},\ldots,P_{n},{\bf
G},{\bf E})$ is equivalent to the AG code ${\bf C}(P_{1},\ldots,P_{n},{\bf
G}_{1},{\bf E})$.

Proof. 1) is direct from the definition of AG code. 2) is direct from the
definition of residual code, see [51].

Notice that the Jacobian of the elliptic curve ${\bf E}$ is itself, so the
condition in Theorem 2.3 1) is equivalent to if
$P_{i_{1}}+\cdots+P_{i_{m}}=mP_{0}$ is valid in the group ${\bf E}({\bf
F}_{q})$, we refer to [51].

###  2.3 The Schur squares of elliptic curve codes

Let ${\bf E}$ be an elliptic curve defined over ${\bf F}_{q}$ and $P_{0}$ is a
rational point. We now discuss some properties of the linear space $L(mP_{0})$
of rational functions $f$ satisfying $(f)+mP_{0}\geq 0$. The following
property is well-known.

Proposition 2.1. ${\bf L}(P_{0})$ is the one dimension linear space of all
constant functions. For each $m\geq 2$, there is one rational function $f$ in
${\bf L}(mP_{0})/{\bf L}((m-1)P_{0})$.

Proof. If there is a non-constant rational function $f$ in the space ${\bf
L}(P_{0})$, then $(f)=Q-P$ for some rational point $Q\in{\bf E}({\bf F}_{q})$.
That is, $P_{0}$ is linearly equivalent to another rational point $Q\in{\bf
E}({\bf F}_{q})$. This is a contradiction to the fact that ${\bf E}({\bf
F}_{q})$ is the Jacobian

$\\{{\bf G}:\deg({\bf G}=0\\}/linear-equivalence$

of ${\bf E}$.

On the other hand from the Riemann-Roch theorem, $\dim({\bf L}(mP_{0}))=m$
when $m\geq 2g-1=1$. The second conclusion follows immediately.

Theorem 2.4. The dimension of the Schur square of an one-point AG code ${\bf
C}(P_{1},\ldots,P_{n},mP_{0},{\bf E})$ from an elliptic curve ${\bf E}$ is
$2m$ if $6\leq 2m\leq n$.

Proof. Let $f_{1}$ be the constant function in ${\bf L}(mP_{0})$, $f_{i}$,
$i=2,\ldots,m$ be the rational function with the $i$-th order pole at the
point $P_{0}$. It is clear that ${\bf C}(P_{1},\ldots,P_{n},mP_{0},{\bf
E})=\\{(f(P_{1}),\ldots,f(P_{n})):f=\Sigma a_{i}f_{I},a_{i}\in{\bf F}_{q}\\}$.
It is clear that the Schur square of ${\bf C}(P_{1},\ldots,P_{n},mP_{0},{\bf
E})$ is in the AG code ${\bf C}(P_{1},\ldots,P_{n},2mP_{0},{\bf E})$. On the
other hand it is easy to verify that the evaluation codewords of
$f_{1},f_{2},\ldots,f_{m}$ are in the Schur square. The rational function
$f_{i}f_{j}$, where $i\geq 2$, $j\geq 2$ satisfying $m+1\leq i+j\leq 2m$, can
have $w$-th order pole at the point $P_{0}$ for $w=m+1,\ldots,2m$. Then the
Schur square of ${\bf C}(P_{1},\ldots,P_{n},mP_{0},{\bf E})$ is ${\bf
C}(P_{1},\ldots,P_{n},2mP_{0},{\bf E})$. The conclusion is proved.

It is obvious that the minimum Hamming distance of the Schur squares of an
elliptic curve $[n,k,\geq n-k]_{q}$ code is at least $n-2k$. Theorem 2.4 can
be generalized to one point AG codes from higher genus curves, see Theorem
4.1.

##  3 Non-Reed-Solomon type MDS codes from elliptic curves

Let $q$ be a prime power. In this section, the set ${\bf
P}=\\{P_{1},\ldots,P_{n}\\}$ is the disjoint union of several cosets of a
subgroup of ${\bf E}({\bf F}_{q})$. We show that there are many MDS AG codes
of consecutive lengths from elliptic curves ${\bf E}$ defined over ${\bf
F}_{q}$. These MDS codes are not equivalent to the Reed-Solomon codes from
dimensions of their Schur squares. On the other hand, MDS twisted Reed-Solomon
codes have been only constructed for some special lengths $n$ satisfying that
$n$ is a divisor of $q-1$ or $\gcd(n,q-1)=\frac{n}{2}$, or $n$ is a divisor of
$q$, see [12]. Therefore it is obvious that there are more non-Reed-Solomon
MDS AG codes from elliptic curves than twisted Reed-Solomon codes. In the
following part, $P_{0}$ is the zero element in the group ${\bf E}({\bf
F}_{q})$.

Theorem 3.1. 1) Let ${\bf E}_{1}\subset{\bf E}({\bf F}_{q})$ be a subgroup of
the order $n_{1}$ and $b\in{\bf E}({\bf F}_{q})$ be a nonzero element such
that the $n_{2}$ order cyclic subgroup $<b>$ generated by $b$ intersects ${\bf
E}_{1}$ at the zero element. Then for any positive integer $m\leq n_{2}-1$,
the elliptic curve code ${\bf C}(b+{\bf E}_{1},mP_{0},{\bf E})$ is an MDS
code.
2) Let ${\bf E}_{1}\subset{\bf E}({\bf F}_{q})$ be a subgroup of the order
$n_{1}$ and $b_{i}\in{\bf E}({\bf F}_{q})$, $i=1,\ldots,t$, be $t$ nonzero
elements in ${\bf E}({\bf F}_{q})$ such that the set
$\\{m_{1}b_{1}+\cdots+m_{t}b_{t}:m_{1}+\cdots+m_{t}=m\\}$ intersects the
subgroup ${\bf E}_{1}$ at the zero element. Set ${\bf P}$ be the union of $t$
cosets $b_{1}+{\bf E}_{1},\ldots,b_{t}+{\bf E}_{1}$. Then the elliptic curve
code ${\bf C}({\bf P},mP_{0},{\bf E})$ is an MDS code.

Proof. The sum $P_{i_{1}}+\cdots+P_{i_{m}}$ of $m$ rational points in the
coset $b+{\bf E}_{1}$ is of the form $mb+P$, where $P\in{\bf E}_{1}$. From the
condition that the the order $n_{2}$ cyclic subgroup $<b>\subset{\bf E}({\bf
F}_{q})$ intersects ${\bf E}_{1}$ only at zero element, this sum is not zero
element in ${\bf E}({\bf F}_{q})$, since $m\leq n_{2}-1$. The conclusion
follows directly. The second conclusion can be proved similarly.

Example 3.1. Let $q=p$ be a prime number, from the classical result in [24]
for any given positive integer satisfying $p^{-}\leq N\leq p^{+}$, there is an
elliptic curve ${\bf E}$ defined over ${\bf F}_{p}$ such that $N=|{\bf E}({\bf
F}_{p})|$. Suppose that $N=p_{1}p_{2}$ be the product of two different prime
numbers, where $\gcd(p,p_{i})=1$ for $i=1,2$. There is an elliptic curve
defined over ${\bf F}_{p}$ such that the group structure of ${\bf E}({\bf
F}_{p})$ is ${\bf Z}/p_{1}{\bf Z}\oplus{\bf Z}/p_{2}{\bf Z}$ from Theorem 2.2.
Let ${\bf E}_{1}$ be the cyclic subgroup ${\bf Z}/p_{1}{\bf Z}\times{\bf 0}$
of the order $p_{1}$. Then for each element of the form $({\bf 0},x)\in{\bf
0}\times{\bf Z}/p_{2}{\bf Z}$, the elliptic curve code ${\bf C}(b+{\bf
E}_{1},mP_{0},{\bf E})$ is an MDS code for $1\leq m\leq p_{1}$.

Let $b_{1}<\cdots<b_{t}$ be $t(\leq p_{2}-1)$ distinct nonzero elements in
${\bf 0}\times{\bf Z}/p_{2}{\bf Z}$ and $m$ be a positive integer satisfying
$mb_{t}\leq p_{2}$. Then $m_{1}b_{1}+\cdots+m_{t}b_{t}\leq mb_{t}<p_{2}$,
where $m_{1}+\cdots+m_{t}=m$. Let ${\bf P}$ be the union of $t$ cosets
$b_{1}+{\bf E}_{1},\ldots,b_{t}+{\bf E}_{1}$. The elliptic curve code ${\bf
C}({\bf P},mP_{0},{\bf E})$ is an MDS code.

It is obvious when $t\geq\frac{p_{2}+1}{2}$, then $m$ cannot bigger than or
equal to two. Hence if we want to construct a dimension $2$ MDS elliptic curve
code in this example, the length is smaller than $\frac{p_{1}p_{2}}{2}\leq
q+1$.

On the other hand we can take ${\bf E}_{1}$ be the subgroup ${\bf 0}\times{\bf
Z}/p_{2}{\bf Z}$, then for ${\bf 1}\times{\bf 0}=b$, the elliptic curve code
${\bf C}({\bf P},mP_{0},{\bf E})$ is an MDS code when $m\leq p_{1}-1$.

When $p=19$, we can get the following non-Reed-Solomon type MDS codes, an MDS
$[4,2,3]_{19}$ code from an elliptic curve with $12$ rational points, an MDS
$[5,2,4]_{19}$ code from an elliptic curve with $15$ rational points, an MDS
$[6,2,5]_{19}$ code from an elliptic curve with $18$ rational points, an MDS
$[5,2,4]_{19}$ code from an elliptic curve with $20$ rational points, and an
MDS $[6,3,4]_{19}$ code from an elliptic curve with $24$ rational points.

Corollary 3.1. Let ${\bf E}$ be an elliptic curve with the order $|{\bf
E}({\bf F}_{q})|=l_{1}l_{2}$ where $l_{1}<l_{2}$ are two positive integers
satisfying $\gcd(l_{i},q)=1$, $i=1,2$, and $\gcd(l_{1},l_{2})=1$. Then there
exists an order $l_{1}$ subgroup ${\bf E}_{1}$ of ${\bf E}({\bf F}_{q})$ and
one coset ${\bf P}$ of ${\bf E}_{1}$, the elliptic curve code ${\bf C}({\bf
P},mP_{0},{\bf E})$ is an MDS code for each $m$ satisfying $2\leq m\leq
l_{1}-1$.

Proof. We have an elliptic curve ${\bf E}$ defined over ${\bf F}_{q}$ such
that ${\bf E}({\bf F}_{q})$ has a subgroup of the form ${\bf Z}/l_{1}l_{2}{\bf
Z}$ from Theorem 2.2 and the condition $\gcd(l_{1},q)=\gcd(l_{2},q)=1$. From
the condition $\gcd(l_{1},l_{2})=1$, the group ${\bf E}({\bf F}_{q})$ is of
the form ${\bf Z}/l_{1}{\bf Z}\oplus{\bf Z}/l_{2}{\bf Z}$. In this case, by
setting ${\bf E}_{1}$ be the cyclic subgroup ${\bf Z}/l_{1}{\bf Z}\times{\bf
0}$ of the order $l_{1}$ and $b$ be the for ${\bf 0}\times x$, where $x$ is
the generator of ${\bf Z}/l_{2}{\bf Z}$, the conclusion follows from Theorem
3.1.

Corollary 3.2. Let $n$ be a positive integer satisfying $6\leq n\leq q^{1/4}$,
$\gcd(n,q)=1$, and $m$ be any positive integer satisfying $2\leq
m\leq\frac{n}{2}$. Then there is an MDS elliptic curve code over ${\bf F}_{q}$
with the length $n$ and dimension $m$. This MDS code is not equivalent to the
Reed-Solomon $[n,m,n-m+1]_{q}$ code when $m\geq 3$.

Proof. First of all, we can find an elliptic curve of the order $nl$ where $l$
is a positive integer satisfying $\gcd(n,l)=1$. Then the conclusion follows
from Theorem 3.1 and Theorem 2.4 immediately.

Since the general MDS conditions about twisted Reed-Solomon codes are
restricted to subfields or subgroups as in [12], certainly many MDS codes
constructed in Corollary 3.2 are not equivalent to these MDS twisted Reed-
Solomon codes, or there is no known MDS twisted Reed-Solomon code with the
corresponding length. Therefore many new non-Reed-Solomon type MDS codes from
elliptic curves are constructed for consecutive lengths. We can observe the
following example of MDS twisted Reed-Solomon codes as in [12].

Let $n$ and $k$ be two positive integers satisfying $n\ \leq q-1$ and $k\leq
n-1$. Let $\alpha_{1},\ldots,\alpha_{n}$ be $n$ distinct elements in the
finite field ${\bf F}_{q}$ such that
${\bf\alpha}=\\{\alpha_{1},\ldots,\alpha_{n}\\}$ is a $n$ element subset ${\bf
F}_{q}$. Let $\eta$ be a nonzero element of ${\bf F}_{q}$. Set ${\bf
g}_{0}=1+\eta x^{k}$, ${\bf g}_{1}=x$, …, ${\bf g}_{k-1}=x^{k-1}$. Let ${\bf
P}(\eta,k)$ be the linear span over ${\bf F}_{q}$ by ${\bf g}_{0},\ldots,{\bf
g}_{k-1}$. The linear $[n,k]_{q}$ code ${\bf C}_{{\bf\alpha},\eta,k}$ is the
evaluation code of these polynomials in ${\bf P}(\eta,k)$ at the above $n$
elements in the subset ${\bf\alpha}$. The dimension of the Schur square of
${\bf C}_{{\bf\alpha},\eta,k}$ is at least $2k$. Thus this code is not
equivalent to a Reed-Solomon code when $2k\leq n$. It is not hard to verify
that if $\eta$ can not be represented as the product of any $k$ elements in
${\bf\alpha}$, that is,

$\eta\neq\prod_{1\leq j\leq k}\alpha_{i_{j}},$

for any $k$ distinct $\alpha_{i_{1}},\ldots,\alpha_{i_{k}}\in{\bf\alpha}$,
this code ${\bf C}_{{\bf\alpha},\eta,k}$ is an MDS code.

The above condition about the set ${\bf\alpha}$ is strong, if we want to
construct MDS twisted Reed-Solomon codes for large dimensions. From the
construction in Theorem 3.1, the MDS condition for elliptic curve codes is not
so strong. Hence there are many MDS elliptic curve codes, which are not
equivalent to known MDS twisted Reed-Solomon codes, or there is no known MDS
twisted Reed-Solomon code with the corresponding length.

Corollary 3.3. Let $p$ be an odd prime number. Then there are MDS
$[\lfloor\sqrt{p}\rfloor,k,\lfloor\sqrt{p}\rfloor-k+1]_{p}$ codes for
$k=2,\ldots,\frac{\lfloor\sqrt{p}\rfloor}{2}$. There are MDS
$[\lfloor\sqrt{p}\rfloor+1,k,\lfloor\sqrt{p}\rfloor-k+2]_{p}$ codes for
$k=2,\ldots,\frac{\lfloor\sqrt{p}\rfloor}{2}$. These codes are not equivalent
to Reed-Solomon codes when $k\geq 3$.

Proof. Set $n=\lfloor\sqrt{p}\rfloor$, it is clear that

$p-\sqrt{p}\leq n(n+1)\leq p+\sqrt{p},$

$\gcd(n,p)=\gcd(n+1,p)=1$. Then there is an elliptic curve ${\bf E}$ defined
over ${\bf F}_{p}$ with $n(n+1)$ rational points from Theorem 2.1 and 2.2,
with the group structure $|{\bf E}({\bf F}_{p})={\bf Z}/n{\bf Z}\oplus{\bf
Z}/(n+1){\bf Z}$. The conclusion follows from Theorem 3.1.

Now we can use supersingular elliptic curves to construct non-equivalent MDS
codes. Let us recall some basic facts about supersingular elliptic curves.
From [62, page 152], the elliptic curve ${\bf E}$ defined over ${\bf F}_{p}$
by $y^{2}=x^{3}+1$ is supersingular when $p\equiv 2$ $mod$ $3$, and the
elliptic curve ${\bf E}$ defined over ${\bf F}_{p}$ by $y^{2}=x^{3}+x$ is
supersingular when $p\equiv 3$ $mod$ $4$. For a supersinglular elliptic curve
${\bf E}$ defined over ${\bf E}_{p}$ it is known that

$|{\bf E}({\bf F}_{p^{n}})|=p^{n}+1,$

if $n$ is an odd positive integer, or

$|{\bf E}({\bf F}_{p^{n}})|=(p^{\frac{n}{2}}-(-1)^{\frac{n}{2}})^{2},$

if $n$ is an even positive integer, see page 155 of [62]. We have the
following result.

Corollary 3.4. Let $p$ be an odd prime satisfying $p\equiv 2$ $mod$ $3$ or
$p\equiv 3$ $mod$ $4$. Let $N$ be a factor of $p^{n}+1$ satisfying
$N<\sqrt{p^{n}+1}$, when $n$ is odd, and $N$ be a factor of
$(p^{\frac{n}{2}}-(-1)^{\frac{n}{2}})^{2}$ satisfying
$N<p^{\frac{n}{2}}-(-1)^{\frac{n}{2}}$ when $n$ is even. Then there is an MDS
$[N,k,N-k+1]_{p^{n}}$ linear code. This MDS code is not equivalent to the
Reed-Solomon code when $k\leq\frac{N}{2}-1$.

Proof. There is no factor $p^{l}$ in $|{\bf E}({\bf F}_{p^{n}})|$, then we can
take $a(l)=0$ for any prime factor $l$ of $|{\bf E}({\bf F}_{p^{n}})|$ in
Theorem 2.2. The conclusion follows from Theorem 3.1 1) directly.

Some non-Reed-Solomon MDS codes were introduced in [56], it is not hard to
verify that the minimum Hamming distances of the Schur square of Roth-Lemple
MDS codes are very small. Hence many of our constructed MDS elliptic curve
codes are not equivalent to Roth-Lempel MDS codes.

Moreover from Theorem 2.3 and 2.4, we can construct some MDS elliptic curve
codes such that their Schur squares are MDS codes or not MDS codes. Therefore
some non-equivalent MDS elliptic curve codes from one elliptic curve or two
different elliptic curves (with different elliptic curve group structures) of
the same length and the same dimension can be constructed.

##  4 Non-Reed-Solomon type MDS codes from higher genus $g\geq 2$ curves

In this section, we prove that MDS codes from a genus $g>g^{\prime}$ curve is
not equivalent to MDS codes from a genus $g^{\prime}$ curve, when $m\geq 4g$.
Then MDS codes from genus $g\geq 2$ curves are essentially new if the degree
of ${\bf G}$ is bigger than or equal to $4g$. It is proved that at least short
length new non-Reed-Solomon type MDS codes from higher genus $g\geq 2$ curves
can be constructed.

The following result is a direct generalization of Theorem 2.4.

Theorem 4.1. Let ${\bf X}$ be a genus $g$ curve defined over ${\bf F}_{q}$,
$P_{0},P_{1},\ldots,P_{n}$ are $n+1$ rational point of ${\bf X}$, $m$ is a
positive integer satisfying $4g<m<n$ and $2m<n$. Then the dimension of the
Schur square of the dimension $k$ one point function code ${\bf
C}(P_{1},\ldots,P_{n},mP_{0},{\bf X})$ is exactly $2k+g-1$. In particular, MDS
AG codes from a genus $g_{1}$ curves are not equivalent to MDS AG codes from a
genus $g_{2}$ curve if $g_{1}>g_{2}$.

Proof. We recall the well-known Weierstrass gap theorem, see Chapter 6 of
[35], except $g$ positive integers
$1=\alpha_{1}<\alpha_{2}<\cdots<\alpha_{g}\leq 2g-1$, there is a rational
function $f\in{\bf L}(mP_{0})$ such that the pole part of the divisor $(f)$
associated with the function $f$ is exactly $m^{\prime}P_{0}$, where
$m^{\prime}\neq\alpha_{i}$, $i=1,\ldots,g$. Therefore for each positive
integer $m^{\prime}\geq 2g$ we can find a rational function $f\in{\bf
L}(mP_{0})$ such that the pole part of $f$ is exactly $m^{\prime}P_{0}$. Then
the Schur square of ${\bf C}(P_{1},\ldots,P_{n},mP_{0},{\bf X})$ is exactly
${\bf C}(P_{1},\ldots,P_{n},2mP_{0},{\bf X})$ with the dimension
$2m-g+1=2(m-g+1)+g-1=2k+g-1$.

Now we observe the MDS condition for AG codes from genus $g$ curves. In the
case $g=1$, this is just Theorem 2.3 1).

Theorem 4.2. Let ${\bf X}$ be a genus $g$ curve defined over ${\bf F}_{q}$,
$P_{0},P_{1},\ldots,P_{n}$ are $n+1$ rational point of ${\bf X}$, $m$ is a
positive integer satisfying $2g-1<m<n$. Then the one point function code ${\bf
C}(P_{1},\ldots,P_{n},mP_{0},{\bf X})$ is MDS if and only if the following MDS
condition holds.

MDS condition for AG codes: For every $m-g+1=k$ different points
$P_{i_{1}},\ldots,P_{i_{k}}$ among $P_{1},\ldots,P_{n}$, there is no degree
$g-1$ rational effective divisor ${\bf G}^{\prime}$ such that the divisor
$P_{i_{1}}+\cdots+P_{i_{m-g+1}}+{\bf G}^{\prime}$ is linear equivalent to the
divisor $mP_{0}$.

Proof. We only need to prove that there is no weight $w$ codeword, where
$n-m\leq w\leq n-m+g-1$. This is obvious since there is no weight $n-m+i$
codeword in this function code for $i=0,\ldots,g-1$, from the above MDS
condition.

The existence of such $n$ rational points $P_{1},\ldots,P_{n}$ satisfying the
above MDS condition can be proved by a counting argument, at least for small
$n\geq 5g$. We can consider the above MDS condition for the projective
imbedding $\Phi$ of the curve ${\bf X}$ in ${\bf P}^{m-g}$ defined by the
divisor $mP_{0}$. Let $\Phi({\bf X})$ be the image of this curve ${\bf X}$ in
${\bf P}^{m-g}$. Then the above MDS condition is equivalent to the following
condition, also see [67].

MDS condition for embedding: To find $n$ rational points $P_{1},\ldots,P_{n}$
in $\Phi({\bf X})$, such that there is no $m-g+1$ different points
$P_{i_{1}},\ldots,P_{i_{m-g+1}}$ among them, which are in a hyperplane of
${\bf P}^{m-g}$.

Therefore the following result is direct from a simple counting argument. The
existence of short length MDS codes from higher genus curves is proved.

Theorem 4.3. Let ${\bf X}$ be a genus $g\geq 2$ curve defined over ${\bf
F}_{q}$, and $m$ be a positive integer satisfying $m\geq 4g$. If $\Phi({\bf
X})\subset{\bf P}^{m-g}$ defined by the linear system $mP_{0}$ is a non-
singular curve with $N$ rational points which are images of rational points of
${\bf X}$. If $n$ is a positive integer satisfying $m<n$ and
$m\cdot\displaystyle{n\choose m-g}<N$, then there exists a length $n$ and
dimension $m-g+1$ MDS code from ${\bf X}$. These MDS codes are not equivalent
to Reed-Solomon codes.

Proof. For each different $m-g$ rational points in general position amonge
chosen evaluation points, we determine a hyperplane in ${\bf P}^{m-g}$. This
hyperplane interests $\Phi({\bf X})$ at $m$ points. Then the conclusion
follows directly.

In particular, when $m=O(g)$ is fixed then new non-Reed-Solomon MDS codes of
lengths $n\leq O(q^{\frac{1}{m-g}})$ over ${\bf F}_{q}$ of the dimension
$m-g+1$ can be constructed from Theorem 4.3, when $q$ tends to the infinity.

It would be interesting to construct explicit longer MDS AG codes from the
Hermitian curve, recent constructed maximal curves in[11]. This could give
explicit new non-Reed-Solomon type MDS codes from higher genus curves, which
are longer than MDS codes from Theorem 4.3. It is also easy to generalize
Theorem 4.1 to two point AG codes, see [7, 43], and to construct more new
longer non-Reed-Solomon type MDS codes from higher genus curves.

##  5 Self-dual MDS codes from elliptic curves over finite fields ${\bf
F}_{2^{s}}$.

In this section we restrict to the elliptic curves ${\bf E}$ defined over a
finite field ${\bf F}_{2^{s}}$ of the characteristic $2$. The set ${\bf
P}=\\{P_{1},\ldots,P_{n}\\}$ is one coset of a subgroup ${\bf
E}_{1}\subset{\bf E}({\bf F}_{2^{s}})$. We show that there are many self-dual
MDS elliptic curve codes from elliptic curves ${\bf E}$ defined over ${\bf
F}_{2^{s}}$. We always are in the case a) of Theorem 2.1. That is, $\beta$ is
an odd positive integer satisfying that $\gcd(2-\beta,2^{s}-1)>1$ has an odd
divisor. Then the group order $|{\bf E}({\bf F}_{2^{s}})|=2^{s}+1-\beta$ is an
even number, and $2^{s}+1-\beta=2^{s}-1+2-\beta$, $\gcd(|{\bf E}({\bf
F}_{2^{s}})|,2^{s}-1)>1$ has an odd divisor. Actually since $\beta$ can be any
odd number in the case a) of Theorem 2.1, when $q=2^{s}$, if $s$ is a
composite number $s=s_{1}s_{2}$ it is obvious we can take $2-\beta\equiv 0$
$mod$ $(2^{s_{1}}-1)$. Hence there are many such elliptic curves with the
desired group orders.

Therefore we need the following conditions to construct self-dual MDS elliptic
curve codes.
1) $q=2^{s_{1}s_{2}}$, $2-\beta\equiv 0$ $mod$ $2^{s_{1}}-1$;
2) $\beta\equiv 1$ $mod$ $8$;
3) An elliptic curve defined over ${\bf F}_{2^{s_{1}s_{2}}}$ with
$2^{s_{1}s_{2}}+1-\beta$ rational points;

Since $2^{s_{1}s_{2}}+1-\beta\equiv 0$ $mod$ $8$, the exponent $h_{2}$ of $2$
in the prime factor decomposition of

$|{\bf E}({\bf F}_{2^{s_{1}s_{2}}})|=2^{s_{1}s_{2}}+1-\beta,$

is at least $h_{2}\geq 3$.

4) The above elliptic curve is of the group structure ${\bf Z}/2^{h_{2}}{\bf
Z}\oplus{\bf Z}/L{\bf Z}$, where $h_{2}\geq 3$ and $L$ is an odd positive
integer.

From Theorem 2.1 and 2.2 there are many such an elliptic curve. Then the group
order of the elliptic curve is

$|{\bf E}({\bf F}_{2^{s_{1}s_{2}}})|=2^{h_{2}}L,$

where $h_{2}\geq 3$ and $L$ is an odd positive integer.

Theorem 5.1. Let $q=2^{s_{1}s_{2}}$ as above and $L^{\prime}$ be an odd
divisor of $L$, $n=2^{t}L^{\prime}$ where $t\leq h_{2}-1$. There exists a
self-dual $[n,\frac{n}{2},\frac{n}{2}+1]_{2^{s_{1}s_{2}}}$ MDS code equivalent
to an elliptic curve code from ${\bf E}$, which is not equivalent to the Reed-
Solomon code.

Proof. From Theorem 2.2, we can find elliptic curve such that for any odd
divisor $L^{\prime}|L$, there is an order $L^{\prime}$ subgroup ${\bf
E}_{2}\subset{\bf E}({\bf F}_{2^{s_{1}s_{2}}})$. Therefore we have an order
$2^{t}L^{\prime}$ subgroup ${\bf E}_{1}$ of the form
$(i2^{h_{2}-t}\theta)\times{\bf E}_{2}$, where $\theta$ is the generator of
the cyclic subgroup ${\bf Z}/2^{h_{2}}{\bf Z}\subset{\bf E}({\bf
F}_{2^{s_{1}s_{2}}})$, and $i=0,1,\ldots,2^{t}-1$.

Then set $b=2^{h_{2}-1-t}\theta\times{\bf 0}\subset{\bf E}({\bf
F}_{2^{s_{1}s_{2}}})$. The coset ${\bf P}=b+{\bf E}_{1}$ has $2^{t}L^{\prime}$
elements. The sum of arbitrary $\frac{n}{2}$ different elements in ${\bf P}$
is of the form $2^{t-1}L^{\prime}b+P$, where $P$ is an element in the subgroup
${\bf E}_{1}$. It is clear that $2^{t-1}L^{\prime}b+P$ is of the form

$2^{h_{2}-2}L^{\prime}\theta\times{\bf 0}+P.$

This is not zero. Therefore the elliptic curve code ${\bf C}({\bf
P},2^{t}L^{\prime}P_{0},{\bf E})$ is an MDS code from Theorem 2.3. Here
$P_{0}$ is the zero element of the group ${\bf E}({\bf F}_{2^{s_{1}s_{2}}})$.

The sum of all elements in the coset ${\bf E}_{1}$ is of the form
$-2^{h_{2}-1}L^{\prime}\theta\times{\bf 0}$, since the sum of all elements in
an order $L^{\prime}$ subgroup, $L^{\prime}$ odd, is zero, and the sum of all
elements in ${\bf Z}/2^{u}{\bf Z}$ is $-2^{u-1}$. Then the sum of all elements
in ${\bf P}$ is $2^{h_{2}-1}L^{\prime}\theta\times{\bf
0}-2^{h_{2}-1}L^{\prime}\theta\times{\bf 0}$ is zero element $P_{0}$.
Therefore from Theorem 2.3. 2), the dual code of ${\bf C}({\bf
P},2^{t-1}L^{\prime}P_{0},{\bf E})$ is equivalent to a linear code ${\bf
C}({\bf P},2^{t-1}L^{\prime}P_{0},{\bf E})$. Suppose that the dual code is of
the form

${\bf v}\cdot{\bf C}({\bf P},2^{t-1}L^{\prime}P_{0},{\bf
E})=\\{(v_{1}c_{1},\ldots,v_{n}c_{n}):(c_{1},c_{2},\ldots,c_{n})\in{\bf
C}({\bf P},2^{t-1}L^{\prime}P_{0},{\bf E})\\},$

where ${\bf v}=(v_{1},\ldots,v_{n})\in{\bf F}_{2^{s_{1}s_{2}}}^{n}$ is a
Hamming weight $n$ vector.

Since this field is of characteristic $2$, each element $v_{i}$ is a square,
set $v_{i}=v_{i}^{\prime 2}$, $i=1,\ldots,n$. Set ${\bf
v^{\prime}}=(v_{1}^{\prime},\ldots,v_{n}^{\prime})$, the equivalent code ${\bf
v^{\prime}}\cdot{\bf C}({\bf P},2^{t-1}L^{\prime}P_{0},{\bf E})$ is a self-
dual code. Actually $({\bf v^{\prime}}\cdot{\bf C}({\bf
P},2^{t-1}L^{\prime}P_{0},{\bf E}))^{\perp}=\frac{1}{{\bf
v^{\prime}}}\cdot{\bf C}({\bf P},2^{t-1}L^{\prime}P_{0},{\bf E})^{\perp}={\bf
v^{\prime}}\cdot{\bf C}({\bf P},2^{t-1}L^{\prime}P_{0},{\bf E})$. The
dimension of the Schur square of this self-dual code is exactly $n$. It is not
equivalent to a Reed-Solomon $[n,\frac{n}{2},\frac{n}{2}+1]_{2^{s_{1}s_{2}}}$
code, the dimension of its Schur square is $n-1$. The conclusion is proved.

Notice that $L^{\prime}$ can be any odd divisor of the group order $|{\bf
E}({\bf F}_{2^{s_{1}s_{2}}})|$, there are indeed many self-dual MDS codes
which are equivalent to elliptic curve codes. Actually self-dual MDS elliptic
curve codes over ${\bf F}_{2^{s}}$ of the length $4L$, where $L$ is any odd
positive number in the range $[1,\frac{2^{s}+1+\lfloor
2\sqrt{2^{s}}\rfloor}{8}]$, can be constructed. Hence there are many new self-
dual MDS elliptic curve codes over the finite field ${\bf F}_{2^{s}}$, which
are not equivalent to self-dual Reed-Solomon codes or self-dual twisted Reed-
Solomon codes.

From the result in [21], it is easy to construct equivalent LCD MDS codes from
self-dual MDS elliptic curve codes.

From Theorem 5.1 and the CSS construction of EAQEC codes in [15], the
following results follows immediately.

Corollary 5.1. Let $q=2^{s_{1}s_{2}}$ be an even prime power and $|{\bf
E}({\bf F}_{q})|=2^{h_{2}}\cdot L$ as in above, $n$ be a positive integer of
the form $2^{t}L^{\prime}$ where $L^{\prime}$ is an odd divisor of the group
order ${\bf E}({\bf F}_{2^{s_{1}s_{2}}})$ and $t\leq h_{2}-1$, and $k$ be a
positive integer satisfying $\frac{n}{2}\leq k\leq n-1$, and $h$ be a
nonnegative integer satisfying $0\leq h\leq\frac{n}{2}$, there exists an MDS
EAQEC $[[n,k-h,n-k+1,n-k-h]]_{2^{s_{1}s_{2}}}$ code.

Proof. From Theorem 5.1 we have an equivalent MDS self-dual elliptic curve
$[n,\frac{n}{2},\frac{n}{2}+1]_{2^{s_{1}s_{2}}}$ code. From the result in [21]
we have a linear MDS $[n,\frac{n}{2},\frac{n}{2}+1]_{2^{s_{1}s_{2}}}$ code
with the $h$-dimension hull, where $0\leq h\leq\frac{n}{2}$. Then the
conclusion follows from the CSS construction of EAQEC codes immediately.

Notice that the MDS elliptic curve codes in Theorem 5.1 are not equivalent to
Reed-Solomon code, then these MDS EAQEC codes in Corollary 5.1 are new MDS
EAQEC codes, comparing to previous constructed MDS EAQEC codes from
generalized Reed-Solomon codes.

##  6 Conclusion and unsolved problems

In this paper, we proved that there are many MDS AG codes from arbitrary genus
algebraic curves, and self-dual MDS AG codes from elliptic curves. These MDS
codes are not equivalent to Reed-Solomon codes, not equivalent to known MDS
twisted Reed-Solomon codes and not equivalent to Roth-Lempel MDS codes. This
showed that MDS AG codes can be obtained from carefully chosen evaluation
points in an arbitrary genus curve. The following two problems about longer
MDS AG codes seem interesting.

1) What is the range of lengths such that there are non-Reed-Solomon type MDS
AG codes. Ranges of lengths of MDS elliptic curve codes in Corollary 3.3 and
3.4 are obviously not optimal. Are there non-Reed-Solomon type MDS codes from
elliptic curve over prime field ${\bf F}_{p}$ with any given length
$n\leq\frac{p}{3}$?

2) Can longer explicit MDS $[n,k,n-k+1]_{q}$ codes be constructed as one point
AG codes from genus $g\geq 2$ curves for each genus $g\geq 2$? We proved that
there are very short length MDS codes from higher genus curves. It is
interesting to construct longer MDS AG codes from maximal curves, with
explicit evaluation points.

## References

  * [1] A. Aguglia, L. Giuzzi and A. Sonnino, Near MDS codes from elliptic curves, Des., Codes and Cryptogr., vol. 89, pp. 965-972, 2021.
  * [2] A. Allen, K. Blackwell, O. Fiol, R. Kshirsagar, B. Matsick, G. L. Matthews and Z. Nelson, Twisted Hermitian codes, Mathematics Special Issue” Algebra and its Application, vol. 9, no. 1, 2021.
  * [3] S. Ball, On large subsets of a finite vector space in which every subset of basis size is a basis, J. EMS, vol. 14, pp. 733-748, 2012.
  * [4] S. Ball, Some constructions of quantum MDS codes, Des., Codes and Cryptogra. vol. 89, pp. 811-821, 2021.
  * [5] S. Ball and R. Vilar, Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal, IEEE Trans. Inf. Theory, vol. 68, pp. 3796-3805, 2022.
  * [6] S. Ball and R. Vilar, The geometry of Hermitian orthogonal codes, Journal of Geometry, vol. 113, artical no. 7, 2022.
  * [7] E. Barelli, P. Beelen, M. Datta, V. Neiger and J. Rosenkilde, Two-point codes for the generalized GK cuvres, IEEE Trans. Inf. Theory, vol. 64, pp. 6268-6276, 2018.
  * [8] D. Bartoli, M. Giulietti and I. Platoni, On the covering radius of MDS codes, IEEE Trans. Inf. Theory, vol. 61, no. 2, pp. 801-811, 2015.
  * [9] A. Bassa and H. Stichtenoth, Self-dual codes better than the Gilbert-Varshamov bound, Des., Codes and Cryptogr., vol. 87, pp. 173-182, 2019.
  * [10] P. Beelen, S. Puchsinger and J. Nielsen, Twisted Reed-Solomon codes, Proc Int. Symp. Inf. Theory, 2017.
  * [11] P. Beelen and M. Montanucci, A new family of maximal curves, J. Lond. Math. Soc., vol. 18, pp. 573-592, 2018.
  * [12] P. Beelen, S. Puchinger and J. Rosenkilde, Twisted Reed-Solomon codes, IEEE Trans. Inf. Theory, vol. 68, no. 5, pp. 3047-3061, 2022.
  * [13] M. Ben-Or, S. Goldwasser and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of STOC 1988, ACM Press, pp.1–10, 1988.
  * [14] M. A. de Boer, MDS codes from hyperelliptic curves, Proc. Arithmetic, Geometry and Coding Theory, pp. 23-34, 1996.
  * [15] T. Brun, I. Devetak and Min-Hsiu Hsieh, Correcting quantum errors with entanglemnent, Science, vol. 304 (5798), pp. 436-439, 2006.
  * [16] V. R. Cadambe, S. A. Jafar and H. Maleki, Asymptotic interference alignment for exact repair in distributed storage systems, 2010 Conference Record of the Forty Fourth Asilomar Conference on Signals, Systems and Computers, 2010.
  * [17] B. Csajbok, G. Marino, O. Polverino and C. Zauelle, A new family of MRD-codes, Linear Alegbrai and Appl., vol. 548, pp. 203-220, 2018.
  * [18] D. Chaum, C. Crépeau and I. Damgaard, Multi-party unconditionally secure protocols, Proceedings STOC 1988, ACM Press, pp. 11–19, 1988.
  * [19] H. Chen, On the main conjecture of geometric MDS codes, International Mathematics Research Notices, no. 8, pp. 313-318, 1994.
  * [20] H. Chen and R. Cramer, Algebraic geometric secret sharing schemes and secure multiparty computation over small fields, Crypto 2006, LNCS 4117, pp. 521-536, 2006.
  * [21] H. Chen, On hull-variation problem of equivalent linear codes, IEEE Trans. Inf. Theory vol. 69, no. 5, pp. 2911-2922, 2023.
  * [22] J. H. Conway, V. Pless and N. J. A. Sloane, Self-dual codes over $GF(3)$ and $GF(4)$ of length not exceeding $16$, IEEE Trans. Inf. Theory, vol. 25, no. 3, pp. 312-322, 1979.
  * [23] J. H. Conway and N. J. A. Sloane, A new upper bound on the minimal distance of self-dual codes. IEEE Trans. Inf. Theory vol. 36, pp. 1319-1333, 1990.
  * [24] M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkorper, Abh. Math. Sem. Hansischen Univ., Vol. 14, pp. 197-272, 1941.
  * [25] S. Dodubekov and I. Landjev, On near MDS codes, J. Geometry, vol. 54, pp. 30-43, 1995.
  * [26] X. Fang, M. Liu and J. Luo, New MDS Euclidean self-orthogonal codes, IEEE Trans. Inf. Theory, vol. 67, no. 1, pp. 130-137, 2021.
  * [27] E. M. Gabidulin, Theory of codes with maximum rank distances, Problems of Information Transmission, vol. 21, pp. 1-21, 1985.
  * [28] Y. Gao, Q. Yue, X. Huang and J. Zeng, Hulls of generalized Reed-Solomon codes via Goppa codes and their applications to quamtum codes, IEEE Trans. Inf. Theory, vol. 67, no. 10, pp. 6619-6626, 2021.
  * [29] S. R. Ghorpade and G. Lachaud, Hyperplane sections of Grassmannians and number of MDS linear codes, Finite Fields Appl., vol. 7, pp. 468-506, 2001.
  * [30] G. Guo and R. Li, Hermitian self-dual GRS and entended GRS codes, IEEE Commun. Lett., vol. 25, no. 4, pp. 1062-1065, 2021.
  * [31] T. A. Gulliver, J-L. Kim and Y. Lee, New MDS or near MDS codes, IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 4354-4360, 2008.
  * [32] V. Guruswami, A. Rudra and M. Sudan, Essential coding theory, https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/, Jan., 2021.
  * [33] D. Han and Y. Ren, A tight upper bound for the maximal length of MDS elliptic codes, IEEE Trans. Inf. Theory, vol. 69, no. 2, pp. 819-822, 2023.
  * [34] X. He, L. Xu and H. Chen, New $q$-ary quamtum MDS codes with distances bigger than $\frac{q}{2}$, Quantum Inf. Process., vol. 15, pp. 2745-2758, 2016.
  * [35] J. W. Hirschfeld, G. Korchmáros and F. Torres, Algebraic curves over finite fields, Princeton University Press, Princeton, Oxford, 2008.
  * [36] D. Huang, Q. Yue, Y. Niu and X. Li, MDS or NMDS self-dual codes from twisted generalized Reed-Solomon codes, Des., Codes and Cryptogra., vol. 89, pp. 2195-2209, 2022.
  * [37] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, Cambridge, U. K., 2003.
  * [38] L. Jin and C. Xing, New MDS self-dual codes from generalized Reed-Solomon codes, IEEE Trans. Inf. Theory, vol. 63, no. 3, pp. 14-34-1438, 2017.
  * [39] L. Jin and H. Kan, Self-dual near MDS codes from elliptic curves, IEEE Trans. Inf. Theory, vol. 65, no. 4, pp. 2166-2170, 2019.
  * [40] X. Kai and S. Zhu, New quantum MDS codes from negacyclic codes, IEEE Trans. Inf. Theory, vol. 59, no. 2, pp. 1193-1197, 2013.
  * [41] K. V. Kaipa, An asymptotic formula in $q$ for the number of $[n,k]$ $q$-ary MDS codes, IEEE Trans. Inf. Theory, Vol. 60, no. 11, pp. 7047-7057, 2014.
  * [42] J. I. Kokkala, D. Krotov and P. R. J. Österga̋rd, On the classification of MDS codes, IEEE Trans. Inf. Theory, Vol. 61, pp. 6485-6492, 2015.
  * [43] L. Landi and L. Vicino, Two-ponit AG codes from Beelen-Montanucci cuvres, Finite Fields Appl., vol. 50, 102009, 2020.
  * [44] I. Landjev and A. Rousseva, The main conjcture for near MDS code, WCC 2015, in Proc. 9th Int. Workshop on Coding and Cryptography, A. Canteaut, G. Leurent, M. Naya-Plasencia, Apr 2015, Paris, France, hal-01276222, 2015.
  * [45] H. Liu and S. Liu, Construction of MDS twisted Reed-Solomon codes and LCD MDS codes, Des., Codes and Cryptogra., vol. 89, pp. 2051-2065, 2021.
  * [46] G. Lunardon, R. Trombetti and Y. Zhou, Generalized twisted Gabidulin codes, J. Combinat. Theory A, vol. 159, pp. 79-106, 2018.
  * [47] G. Luo, X. Cao and X. Chen, MDS codes with hulls of arbitray dimensions and their quantum error correction, IEEE Trans. Inf. Theory, vol. 65, no. 5, pp. 2944-2952, 2019.
  * [48] F. J. MacWilliams and N. J. A. Sloane, The Theory of error-correcting codes, 3rd Edition, North-Holland Mathematical Library, vol. 16. North-Holland, Amsterdam, 1977.
  * [49] R. J. McEliece and D. V. Sarvate, On sharing secrets and Reed-Solomon codes. Commun. ACM, vol 24, no. 11, pp. 583-584, 1981.
  * [50] C. Munuera, On main conjecture on MDS geometric codes, IEEE Trans. Inf. Theory, vol. 38, no. 5, 1992.
  * [51] C. Munuera, On elliptic MDS codes, Discrete Math., vol. 117, pp. 279-286, 1993.
  * [52] A. Neri, S. Puchsinger, A.-L. Horlemann-Trautmann, Equivalence and characterization of linear rank-metric codes based on invariants, Linear Alg.Appl., vol. 603, no. 15, pp. 418-469, 2020.
  * [53] Y. Niu, Q. Yue, Y. Wu and L. Hu, Hermitian self-dual, MDS and generalized Reed-Solomon codes, IEEE Commun. Lett., vol. 23, no. 5, pp. 781-784, 2019.
  * [54] K. Otal and F. Özbudak, Additive rank-metric codes, IEEE Trans. Inf. Theory, vol. 63, no. 1, pp. 164-168, 2017.
  * [55] I. Reed and G. Solomon, Polynomial codes over certain finite fields, J. SIAM, vol. 8, pp. 300-304, 1960.
  * [56] R. M. Roth and A. Lempel, A construction of non-Reed-Solomon type MDS codes, IEEE Trans. Inf. Theory, vol. 35, no. 3, pp. 655-657, 1989.
  * [57] H-G. Rück, A note on elliptic curves over finite fields, Math. Comput., Vol. 49, No. 179, pp. 301-304.
  * [58] B. Segre, Curve raizionali normali e k-archi negli spazi finiti, Ann. Mat. Pura Appl., Vol. 39, pp. 357-378, 1955.
  * [59] A. Shamir, How to share a secret, Commun. ACM, vol. 22, no. 11, pp. 612-613, 1979.
  * [60] J. Sheekey, A new family of linear maximum rank distance code, Adv Math. Commun., vol. 10, no. 3, pp. 475-488, 2016.
  * [61] P. W. Shor, Scheme for redcuing decoherence in quantum memory, Phys. Rev. A, vol. 52, pp. R2493-2496, 1995.
  * [62] J. H. Silverman, The arithemtic of ellptic curves, Chapter V, 2nd Edition, Springer Dordrecht Heidelberg London New York, 2009
  * [63] A. M. Steane, Mutiple particle interference and quantum error correction, Proc. Roy. Soc. London, vol. 452, pp. 2551-2577, 1996.
  * [64] J. Sui, Q. Yue, X. Li and D. Huang, MDS, near MDS or 2-MDS self-dual codes via twisted Reed-Solomon code, IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 7832-7841, 2022.
  * [65] R. Trombetti and Y. Zhou, A new family of MRD codes in ${\bf F}_{q}^{2n\times 2n}$ with right and middle nuclei ${\bf F}_{q}^{n}$, IEEE Trans. Inf. Theory, vol. 65, no. 2, pp. 1054 C1062, Feb. 2019.
  * [66] M. Tsfasman and S. G. Vlǎdut, Algebraic-geometric codes, Vol.58, Springer Science and Business Media, 2013.
  * [67] J. L. Walker, A new approach to the main conjcture of algebraic-geometric MDS codes, Des., Codes and Cryptogr., vol. 9, pp. 115-120, 1996.
  * [68] A. Zhang and K. Feng, A unified approch to construct MDS self-dual codes via Reed-Soloon code, IEEE Trans. Inf. Theory, vol. 66, no. 6, pp. 3650-3656, 2020.