doi: 10.3934/amc.2021024
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

On additive MDS codes over small fields

1. 

Departament de Matemàtiques, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain

2. 

Faculty of Engineering and Natural Sciences, Sabancı University, Istanbul, Turkey

* Corresponding author: Simeon Ball

Received  December 2020 Revised  April 2021 Early access July 2021

Fund Project: The first author acknowledges the support of the project MTM2017-82166-P of the Spanish Ministerio de Ciencia y Innovación

Let $ C $ be a $ (n,q^{2k},n-k+1)_{q^2} $ additive MDS code which is linear over $ {\mathbb F}_q $. We prove that if $ n \geq q+k $ and $ k+1 $ of the projections of $ C $ are linear over $ {\mathbb F}_{q^2} $ then $ C $ is linear over $ {\mathbb F}_{q^2} $. We use this geometrical theorem, other geometric arguments and some computations to classify all additive MDS codes over $ {\mathbb F}_q $ for $ q \in \{4,8,9\} $. We also classify the longest additive MDS codes over $ {\mathbb F}_{16} $ which are linear over $ {\mathbb F}_4 $. In these cases, the classifications not only verify the MDS conjecture for additive codes, but also confirm there are no additive non-linear MDS codes which perform as well as their linear counterparts. These results imply that the quantum MDS conjecture holds for $ q \in \{ 2,3\} $.

Citation: Simeon Ball, Guillermo Gamboa, Michel Lavrauw. On additive MDS codes over small fields. Advances in Mathematics of Communications, doi: 10.3934/amc.2021024
References:
[1]

T. L. Alderson, $(6, 3)$-MDS codes over an alphabet of size $4$, Des. Codes Cryptogr, 38 (2006), 31–40. doi: 10.1007/s10623-004-5659-4.  Google Scholar

[2]

S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc., 14 (2012), 733–748. doi: 10.4171/JEMS/316.  Google Scholar

[3]

S. Ball and M. Lavrauw, Arcs in finite projective spaces, EMS Surv. Math. Sci., 6 (2019), 133–172. doi: 10.4171/emss/33.  Google Scholar

[4]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes. Classification by Isometry and Applications, Algorithms and Computation in Mathematics 18, Springer, 2006.  Google Scholar

[5]

A. Blokhuis and A. E. Brouwer, Small additive quaternary codes, European J. Combin., 25 (2004), 161–167. doi: 10.1016/S0195-6698(03)00096-9.  Google Scholar

[6]

K. Bogart, D. Goldberg and J. Gordon, An elementary proof of the MacWilliams theorem on equivalence of codes, Inform and Control, 37 (1978), 19–22. doi: 10.1016/S0019-9958(78)90389-3.  Google Scholar

[7]

K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics, 23 (1952), 426–434. doi: 10.1214/aoms/1177729387.  Google Scholar

[8]

P. Dembowski, Finite Geometries, Reprint of the 1968 original. Classics in Mathematics. Springer-Verlag, Berlin, 1997.  Google Scholar

[9]

J. Bamberg, A. Betten, Ph. Cara, J. De Beule, M. Lavrauw and M. Neunhöffer, Finite Incidence Geometry, FinInG–a GAP Package, Version 1.4.1, 2018. https://www.gap-system.org/Packages/fining.html. Google Scholar

[10]

G. A. Gamboa Quintero, Additive MDS codes, Master's Thesis, Universitat Politècnica Catalunya, 2020. Google Scholar

[11]

The GAP Group, GAP – Groups, Algorithms, Programming -a System for Computational Discrete Algebra, Version 4.11.0, 2020. https://www.gap-system.org. Google Scholar

[12]

L. H. Soicher, GAP Package GRAPE, Version 4.8.5, 2021. https://gap-packages.github.io/grape. Google Scholar

[13]

M. Grassl and M. Rötteler, Quantum MDS codes over small fields, in Proc. Int. Symp. Inf. Theory (ISIT), (2015), 1104–1108, arXiv: 1502.05267. doi: 10.1109/ISIT.2015.7282626.  Google Scholar

[14]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, Finite Geometries, Dev. Math., Kluwer Acad. Publ, Dordrecht, 3 (2001), 201-246.  doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[15]

F. Huber and M. Grassl, Quantum codes of maximal distance and highly entangled subspaces, Quantum, 4 (2020), 284, arXiv: 1907.07733. doi: 10.22331/q-2020-06-18-284.  Google Scholar

[16]

A. KetkarA. KlappeneckerS. Kumar and P. K. Sarvepalli, Nonbinary stabilizer codes over finite fields, IEEE Trans. Inf. Theory, 52 (2006), 4892-4914.  doi: 10.1109/TIT.2006.883612.  Google Scholar

[17]

J. I. Kokkala, D. S. Krotov and P. R. J. Östergård, On the classification of MDS codes, IEEE Trans. Inf. Theory, 61 (2015), 6485–6492. doi: 10.1109/TIT.2015.2488659.  Google Scholar

[18]

J. I. Kokkala and P. R. J. Östergård, Further results on the classification of MDS codes, Adv. Math. Commun., 10 (2016), 489–498. doi: 10.3934/amc.2016020.  Google Scholar

[19]

M. Lavrauw and G. Van de Voorde, Field reduction and linear sets in finite geometry, in: Contemporary Mathematics, (eds: G Kyureghyan, GL Mullen, and A Pott), American Mathematical Society, 632 (2015), 271–293. doi: 10.1090/conm/632/12633.  Google Scholar

[20]

S. Linton, Finding the smallest image of a set, in: ISSAC '04: Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, 2004 (2004), 229–234. doi: 10.1145/1005285.1005319.  Google Scholar

[21]

L. Lunelli and M. Sce, Considerazione aritmetiche e risultati sperimentali sui $\{K; n\}_q$-archi, Ist. Lombardo Accad. Sci. Rend. A, 98 (1964), 3-52.   Google Scholar

[22]

F. J. MacWilliams, Combinatorial Problems of Elementary Abelian Groups, Thesis (Ph.D.)–Radcliffe College, 1962.  Google Scholar

[23]

K. Shiromoto, Note on MDS codes over the integers modulo $p^{m}$,, Hokkaido Mathematical Journal, 29 (2000), 149–157. doi: 10.14492/hokmj/1350912961.  Google Scholar

[24]

L. H. Soicher, Computation of partial spreads web-page, http://www.maths.qmul.ac.uk/~lsoicher/partialspreads/ Google Scholar

[25]

H. N. Ward and J. A. Wood, Characters and the equivalence of codes, J. Combin. Theory Ser. A, 73 (1996), 348–352. doi: 10.1016/S0097-3165(96)80011-2.  Google Scholar

show all references

References:
[1]

T. L. Alderson, $(6, 3)$-MDS codes over an alphabet of size $4$, Des. Codes Cryptogr, 38 (2006), 31–40. doi: 10.1007/s10623-004-5659-4.  Google Scholar

[2]

S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc., 14 (2012), 733–748. doi: 10.4171/JEMS/316.  Google Scholar

[3]

S. Ball and M. Lavrauw, Arcs in finite projective spaces, EMS Surv. Math. Sci., 6 (2019), 133–172. doi: 10.4171/emss/33.  Google Scholar

[4]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes. Classification by Isometry and Applications, Algorithms and Computation in Mathematics 18, Springer, 2006.  Google Scholar

[5]

A. Blokhuis and A. E. Brouwer, Small additive quaternary codes, European J. Combin., 25 (2004), 161–167. doi: 10.1016/S0195-6698(03)00096-9.  Google Scholar

[6]

K. Bogart, D. Goldberg and J. Gordon, An elementary proof of the MacWilliams theorem on equivalence of codes, Inform and Control, 37 (1978), 19–22. doi: 10.1016/S0019-9958(78)90389-3.  Google Scholar

[7]

K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics, 23 (1952), 426–434. doi: 10.1214/aoms/1177729387.  Google Scholar

[8]

P. Dembowski, Finite Geometries, Reprint of the 1968 original. Classics in Mathematics. Springer-Verlag, Berlin, 1997.  Google Scholar

[9]

J. Bamberg, A. Betten, Ph. Cara, J. De Beule, M. Lavrauw and M. Neunhöffer, Finite Incidence Geometry, FinInG–a GAP Package, Version 1.4.1, 2018. https://www.gap-system.org/Packages/fining.html. Google Scholar

[10]

G. A. Gamboa Quintero, Additive MDS codes, Master's Thesis, Universitat Politècnica Catalunya, 2020. Google Scholar

[11]

The GAP Group, GAP – Groups, Algorithms, Programming -a System for Computational Discrete Algebra, Version 4.11.0, 2020. https://www.gap-system.org. Google Scholar

[12]

L. H. Soicher, GAP Package GRAPE, Version 4.8.5, 2021. https://gap-packages.github.io/grape. Google Scholar

[13]

M. Grassl and M. Rötteler, Quantum MDS codes over small fields, in Proc. Int. Symp. Inf. Theory (ISIT), (2015), 1104–1108, arXiv: 1502.05267. doi: 10.1109/ISIT.2015.7282626.  Google Scholar

[14]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, Finite Geometries, Dev. Math., Kluwer Acad. Publ, Dordrecht, 3 (2001), 201-246.  doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[15]

F. Huber and M. Grassl, Quantum codes of maximal distance and highly entangled subspaces, Quantum, 4 (2020), 284, arXiv: 1907.07733. doi: 10.22331/q-2020-06-18-284.  Google Scholar

[16]

A. KetkarA. KlappeneckerS. Kumar and P. K. Sarvepalli, Nonbinary stabilizer codes over finite fields, IEEE Trans. Inf. Theory, 52 (2006), 4892-4914.  doi: 10.1109/TIT.2006.883612.  Google Scholar

[17]

J. I. Kokkala, D. S. Krotov and P. R. J. Östergård, On the classification of MDS codes, IEEE Trans. Inf. Theory, 61 (2015), 6485–6492. doi: 10.1109/TIT.2015.2488659.  Google Scholar

[18]

J. I. Kokkala and P. R. J. Östergård, Further results on the classification of MDS codes, Adv. Math. Commun., 10 (2016), 489–498. doi: 10.3934/amc.2016020.  Google Scholar

[19]

M. Lavrauw and G. Van de Voorde, Field reduction and linear sets in finite geometry, in: Contemporary Mathematics, (eds: G Kyureghyan, GL Mullen, and A Pott), American Mathematical Society, 632 (2015), 271–293. doi: 10.1090/conm/632/12633.  Google Scholar

[20]

S. Linton, Finding the smallest image of a set, in: ISSAC '04: Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, 2004 (2004), 229–234. doi: 10.1145/1005285.1005319.  Google Scholar

[21]

L. Lunelli and M. Sce, Considerazione aritmetiche e risultati sperimentali sui $\{K; n\}_q$-archi, Ist. Lombardo Accad. Sci. Rend. A, 98 (1964), 3-52.   Google Scholar

[22]

F. J. MacWilliams, Combinatorial Problems of Elementary Abelian Groups, Thesis (Ph.D.)–Radcliffe College, 1962.  Google Scholar

[23]

K. Shiromoto, Note on MDS codes over the integers modulo $p^{m}$,, Hokkaido Mathematical Journal, 29 (2000), 149–157. doi: 10.14492/hokmj/1350912961.  Google Scholar

[24]

L. H. Soicher, Computation of partial spreads web-page, http://www.maths.qmul.ac.uk/~lsoicher/partialspreads/ Google Scholar

[25]

H. N. Ward and J. A. Wood, Characters and the equivalence of codes, J. Combin. Theory Ser. A, 73 (1996), 348–352. doi: 10.1016/S0097-3165(96)80011-2.  Google Scholar

Table 1.  The classification of arcs of lines of $\mathrm{PG}(5, 2)$
size 4 5 6
number of arcs of points of $\mathrm{PG}(2, 4)$ 1 1 1
number of arcs of lines of $\mathrm{PG}(5, 2)$ 1 1 1
size 4 5 6
number of arcs of points of $\mathrm{PG}(2, 4)$ 1 1 1
number of arcs of lines of $\mathrm{PG}(5, 2)$ 1 1 1
Table 2.  The classification of arcs of planes of PG(8, 2)
size 4 5 6 7 8 9 10
number of arcs of points of PG(2, 8) 1 1 3 2 2 2 1
number of arcs of planes of PG(8, 2) 1 2 4 2 2 2 1
size 4 5 6 7 8 9 10
number of arcs of points of PG(2, 8) 1 1 3 2 2 2 1
number of arcs of planes of PG(8, 2) 1 2 4 2 2 2 1
Table 3.  The classification of arcs of lines of PG(5, 3)
size 4 5 6 7 8 9 10
# of arcs of points of PG(2, 9) 1 2 6 3 2 1 1
# of arcs of lines of PG(5, 3) 1 4 13 4 3 1 1
size 4 5 6 7 8 9 10
# of arcs of points of PG(2, 9) 1 2 6 3 2 1 1
# of arcs of lines of PG(5, 3) 1 4 13 4 3 1 1
Table 4.  The classification of arcs of lines of PG(3, 3)
size 4 5 6 7 8 9 10
# of arcs of points of PG(1, 9) 2 2 2 1 1 1 1
# of arcs of lines of PG(3, 3) 3 4 5 4 3 2 2
size 4 5 6 7 8 9 10
# of arcs of points of PG(1, 9) 2 2 2 1 1 1 1
# of arcs of lines of PG(3, 3) 3 4 5 4 3 2 2
Table 5.  The classification of arcs of lines of $\mathrm{PG}(5, 4)$
size 5 6 7 8 9 10 11
# of arcs of $\mathrm{PG}(2, 16)$ 3 22 125 865 1534 1262 300
# of line-arcs of $\mathrm{PG}(5, 4)$ 10 360 8294 15162 2869 1465 301
size 12 13 14 15 16 17 18
# of arcs of $\mathrm{PG}(2, 16)$ 159 70 30 9 5 3 2
# of line-arcs of $\mathrm{PG}(5, 4)$ 159 70 30 9 5 3 2
size 5 6 7 8 9 10 11
# of arcs of $\mathrm{PG}(2, 16)$ 3 22 125 865 1534 1262 300
# of line-arcs of $\mathrm{PG}(5, 4)$ 10 360 8294 15162 2869 1465 301
size 12 13 14 15 16 17 18
# of arcs of $\mathrm{PG}(2, 16)$ 159 70 30 9 5 3 2
# of line-arcs of $\mathrm{PG}(5, 4)$ 159 70 30 9 5 3 2
[1]

Can Xiang, Jinquan Luo. Some subfield codes from MDS codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021023

[2]

Janne I. Kokkala, Patric R. J.  Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 2016, 10 (3) : 489-498. doi: 10.3934/amc.2016020

[3]

Anna-Lena Horlemann-Trautmann, Alessandro Neri. A complete classification of partial MDS (maximally recoverable) codes with one global parity. Advances in Mathematics of Communications, 2020, 14 (1) : 69-88. doi: 10.3934/amc.2020006

[4]

Sara D. Cardell, Joan-Josep Climent, Daniel Panario, Brett Stevens. A construction of $ \mathbb{F}_2 $-linear cyclic, MDS codes. Advances in Mathematics of Communications, 2020, 14 (3) : 437-453. doi: 10.3934/amc.2020047

[5]

Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005

[6]

Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349

[7]

Ram Krishna Verma, Om Prakash, Ashutosh Singh, Habibul Islam. New quantum codes from skew constacyclic codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021028

[8]

Cem Güneri, Ferruh Özbudak, Funda ÖzdemIr. On complementary dual additive cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 353-357. doi: 10.3934/amc.2017028

[9]

Martianus Frederic Ezerman, San Ling, Patrick Solé, Olfa Yemen. From skew-cyclic codes to asymmetric quantum codes. Advances in Mathematics of Communications, 2011, 5 (1) : 41-57. doi: 10.3934/amc.2011.5.41

[10]

Karim Samei, Saadoun Mahmoudi. Singleton bounds for R-additive codes. Advances in Mathematics of Communications, 2018, 12 (1) : 107-114. doi: 10.3934/amc.2018006

[11]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163

[12]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

[13]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[14]

Evangeline P. Bautista, Philippe Gaborit, Jon-Lark Kim, Judy L. Walker. s-extremal additive $\mathbb F_4$ codes. Advances in Mathematics of Communications, 2007, 1 (1) : 111-130. doi: 10.3934/amc.2007.1.111

[15]

Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425

[16]

W. Cary Huffman. Additive cyclic codes over $\mathbb F_4$. Advances in Mathematics of Communications, 2008, 2 (3) : 309-343. doi: 10.3934/amc.2008.2.309

[17]

W. Cary Huffman. Additive cyclic codes over $\mathbb F_4$. Advances in Mathematics of Communications, 2007, 1 (4) : 427-459. doi: 10.3934/amc.2007.1.427

[18]

Habibul Islam, Om Prakash, Ram Krishna Verma. New quantum codes from constacyclic codes over the ring $ R_{k,m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020097

[19]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[20]

Ranya Djihad Boulanouar, Aicha Batoul, Delphine Boucher. An overview on skew constacyclic codes and their subclass of LCD codes. Advances in Mathematics of Communications, 2021, 15 (4) : 611-632. doi: 10.3934/amc.2020085

2020 Impact Factor: 0.935

Article outline

Figures and Tables

[Back to Top]