On additive MDS codes over small fields

Simeon Ball; Guillermo Gamboa; Michel Lavrauw

doi:10.3934/amc.2021024

Article Contents

2023, Volume 17, Issue 4: 828-844. Doi: 10.3934/amc.2021024

This issue Previous Article Some subfield codes from MDS codes Next Article Four by four MDS matrices with the fewest XOR gates based on words

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
^* Corresponding author: Simeon Ball

Received: December 2020

Revised: April 2021

Early access: July 2021

Published: August 2023

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by

Abstract

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\} $.

Keywords:

Mathematics Subject Classification: Primary: 94B27; Secondary: 51E22.

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[3]	S. Ball and M. Lavrauw, Arcs in finite projective spaces, EMS Surv. Math. Sci., 6 (2019), 133–172. doi: 10.4171/emss/33.
[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.
[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.
[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.
[7]	K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics, 23 (1952), 426–434. doi: 10.1214/aoms/1177729387.
[8]	P. Dembowski, Finite Geometries, Reprint of the 1968 original. Classics in Mathematics. Springer-Verlag, Berlin, 1997.
[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.
[10]	G. A. Gamboa Quintero, Additive MDS codes, Master's Thesis, Universitat Politècnica Catalunya, 2020.
[11]	The GAP Group, GAP – Groups, Algorithms, Programming -a System for Computational Discrete Algebra, Version 4.11.0, 2020. https://www.gap-system.org.
[12]	L. H. Soicher, GAP Package GRAPE, Version 4.8.5, 2021. https://gap-packages.github.io/grape.
[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.
[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.
[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.
[16]	A. Ketkar, A. Klappenecker, S. 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.
[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.
[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.
[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.
[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.
[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.
[22]	F. J. MacWilliams, Combinatorial Problems of Elementary Abelian Groups, Thesis (Ph.D.)–Radcliffe College, 1962.
[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.
[24]	L. H. Soicher, Computation of partial spreads web-page, http://www.maths.qmul.ac.uk/~lsoicher/partialspreads/
[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.