Additive MDS codes

ADDITIVE MDS CODES SIMEON BALL AND SAM ADRIAENSEN Abstract. We prove that an additive code over a finite field which has a few projections which are equivalent to a linear code is itself equivalent to a linear code, providing the code is not too short. 1. MDS codes Let Abe a finite set and let nand kbe positive integers. A code Cof minimum distance dis a subset of Anin which any two elements of Cdiffer in at least dcoordinates. Fixing any d−1coordinates, it follows that any two codewords cannot agree on the remaining n−d+ 1 coordinates. Thus, we arrive at the Singleton bound |C|⩽|A|n−d+1. Amaximum distance separable (MDS) code Cis a subset of Anof size |A|n−d+1. If there is no restriction on the size of Athen MDS codes are the best performing codes when we apply nearest neighbour decoding. They have the property that a codeword can be recovered from any k=n−d+ 1 coordinates, which makes them very useful, for example, in distributed storage systems. Assuming that |C|=|A|k, the Singleton bound can be rewritten as n⩾k+d−1. The ubiquitous example of an MDS code is the Reed-Solomon code. The Reed-Solomon code is an example of a linear code in which the alphabet is a finite field Fqand Cis a k-dimensional subspace of Fn q. The Reed-Solomon code has length n=q+ 1 which can be extended to a code of length q+2 in the case that k∈ {3, q−1}and qis even. Its codewords are the evaluation of polynomials of degree at most k−1. To give a more precise definition, suppose Fq={a1, . . . , aq}. The Reed-Solomon code is C={(f(a1), . . . , f(aq), cf)|f∈Fq[X],deg f⩽k−1}, where cfis the coefficient of Xk−1in f. There are no known MDS codes which are better than the Reed-Solomon code and it is generally assumed that there are none. The MDS conjecture reflects this and states that for an (n, qk, d)qMDS code where d⩾3, the length nsatisfies n⩽q+ 1, unless k∈ {3, q −1} and q= 2hin which case n⩽q+ 2. The MDS conjecture has been verified for linear codes when qis prime [2]. It is also known to hold for linear codes when qis square and k⩽c√q, where the constant cdepends Date: 16 June 2022. The author has been partially supported by PID2020-113082GB-I00 financed by MCIN / AEI / 10.13039/501100011033, the Spanish Ministry of Science and Innovation. The talk at the 8IMM 2022 has been given by the first author. 1 2 SIMEON BALL AND SAM ADRIAENSEN on whether qis odd or even. And for qnon-square and k⩽c0√pq, where again the constant c0depends on whether qis an odd power of an even or odd prime. See [3] for a recent survey. It is also known to hold for all MDS codes over alphabets of size at most 8, see [5]. 2. Additive MDS codes Here, we will be interested in additive codes over Fq. It seems reasonable that relaxing linear to additive might allow one to find counter-examples to the MDS conjecture. However, this has not been the case thus far. Since additive are always linear over some subfield, we fix this subfield as Fqand consider the code over Fqh. In [4] it was confirmed that the MDS conjecture is true for additive MDS codes over F9and F16, where in the last case linearity over F4is assumed. Let us denote by an [n, k]qhMDS code any (n, qk, n −k+ 1)qhadditive MDS code which is linear over Fq. Recall that the projection of a code Con the i-th coordinate is the code obtained from Ctaking those codewords with a zero in the i-th coordinate. The projection of a [n, k]qhMDS code is a [n−1, k −1]qhMDS code. The following theorem from [1] is a strengthening of a similar theorem used in [4] and will be the main focus of the talk. Theorem 2.1. Let Cbe an [n, k]qhMDS code. Suppose one of the following holds. (1) k= 3,h∈ {2,3},n > max{qh−1, hq −1}+ 3 and Chas three coordinate positions from which its projection is equivalent to a linear code. (2) k > 3,n>qh−1+kand there are disjoint subsets Aand Bof the coordinate positions of Csuch that |A|+|B| ≤ k−2, and the projections from Aand Bare equivalent to linear codes. Then Citself is equivalent to a linear code. Note that in the above an additive code Cis equivalent to a linear code if there are linearised maps σi:x7→ h−1 X i=0 cijxqi such that {(σ1(u1), . . . , σn(un)|(u1, . . . , un)∈C} is linear over Fqh. References [1] S. Adriaensen and S. Ball, On additive MDS codes with linear projections, preprint. [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. [3] S. Ball and M. Lavrauw, Arcs in finite projective spaces, EMS Surv. Math. Sci.,6(2019) 133–172. [4] S. Ball, G, Gamboa and M. Lavrauw, On additive MDS codes over small fields, Adv. Math. Commun., to appear. [5] J. I. Kokkala and P. R. J. Östergård, Further results on the classification of MDS codes, Adv. Math. Commun.,10 (2016) 489–498. ADDITIVE MDS CODES 3 Simeon Ball Universitat Politècnica Catalunya Email address:[email protected] Sam Adriaensen Vrije Universiteit Brussel Email address:[email protected]