Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal

Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal Simeon Ball and Ricard Vilar ∗ 23 December 2021 Abstract We prove that there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n⩽q2 over Fq2 if and only if there is a polynomial g∈Fq2 of degree at most ( q−k ) q− 1 such that g + gq has q2−n distinct zeros. This allows us to determine the smallest n for which there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n over Fq2 , verifying a conjecture of Grassl and R¨otteler. We also provide examples of Hermitian self-orthogonal k -dimensional generalised Reed-Solomon codes of length q2 + 1 over Fq2 , for k = q− 1 and q an odd power of two. 1 Introduction The study of Hermitian self-orthogonal linear codes is motivated by the fact that given such a code one can easily construct a quantum error-correcting code. A quantum error-correcting code is a subspace of ( Cq ) ⊗n . The parameter q is called the local dimension and corresponds to the number of mutually orthogonal states each quantum particle of the system has. A quantum code with minimum distance d is able to detect errors, which act non-trivially on the code space, on up to d− 1 of the subsystems and correct errors on up to 1 2(d−1) of the subsystems. Let Fq denote the finite field with q elements. A linear code C of length n over Fq is a subspace of Fn q . If the minimum weight of a non-zero element of C is d then the minimum (Hamming) distance between any two elements of C is d and we say that Cis [n, k, d]qcode, where kis the dimension of the subspace C. A canonical Hermitian form on Fn q2is given by (u, v)h= n X i=1 uivq i. ∗ The first author acknowledges the support of the Spanish Ministry of Science and Innovation grants MTM2017-82166-P and PID2020-113082GB-I00 funded by MCIN / AEI / 10.13039/501100011033. 1 If Cis a linear code over Fq2then its Hermitian dual is defined as C⊥h={v∈Fn q2|(u, v)h= 0,for all u∈C}. One very common construction of quantum stabiliser codes relies on the following theorem from Ketkar et al. [ 16 , Corollary 19]. It is a generalisation from the qubit case of a construction introduced by Calderbank et al. [3, Theorem 2]. Theorem 1.1 If there is a [ n, k, d0 ] q2 linear code C such that C⊆C⊥h then there exists an [[ n, n− 2 k, d ]] q quantum code, where d is the minimum weight of the elements of C⊥h\C if k6 = 1 2n and d is the minimum weight of the non-zero elements of C⊥h=Cif k=1 2n. If C⊆C⊥h then we say the linear code C is Hermitian self-orthogonal. Theorem 1.1 is our motivation to study Hermitian self-orthogonal codes. We can multiply the i -th coordinate of all the elements of C by a non-zero scalar θi , without altering the parameters of the code. Such a scaling, together with a reordering of the coordinates, gives a code which is said to be linearly equivalent or monomially equivalent to C. A linear code D is linearly equivalent to a linear code C over Fq if, after a suitable re-ordering of the coordinates, there exist non-zero θi∈Fqsuch that D={(θ1u1, . . . , θnun)|(u1, . . . , un)∈C}. Atruncation of a code is a code obtained from Cby deletion of coordinates. In this article we consider the generalised Reed-Solomon code, any code which is linearly equivalent to a Reed-Solomon code. In Section 3 we will prove that there exists a k -dimensional Hermitian self-orthogonal generalised Reed-Solomon code of length n⩽q2 if and only if there is a polynomial g∈Fq2 of degree at most ( q−k ) q− 1 such that g + gq has q2−n distinct zeros. We go on to give examples of such polynomials g , which imply the existence of k -dimensional Hermitian self-orthogonal generalised Reed-Solomon codes of length n, for many values of nwhich were previously unknown. In Section 4 we determine the minimum n for which there exists a Hermitian selforthogonal generalised Reed-Solomon code of length n , verifying a conjecture of Grassl and R¨otteler from [8]. In Section 5, for q an odd power of two, we provide an example of a polynomial g of degree less than q− 1 such that g + gq has no zeros. This implies, applying Theorem 3.2, that there is a ( q− 1)-dimensional Hermitian self-orthogonal generalised Reed-Solomon code of length q2 + 1 when q = 2 2h+1 . This was previously unknown for h⩾4. 2 2 Hermitian self-orthogonal codes In this section we introduce the puncture code P ( C ) of a linear code C and explain its connection to Hermitian self-orthogonal codes. Let C be a linear code of length n over Fq2 . The code C is linearly equivalent to a Hermitian self-orthogonal code if and only if there are non-zero θi∈Fq2such that n X i=1 θq+1 iuivq i= 0,(1) for all u, v ∈C . Note that θq+1 i is a non-zero element of Fq , so equivalently C is linearly equivalent to a Hermitian self-orthogonal code if and only if there are non-zero λi∈Fqsuch that n X i=1 λiuivq i= 0. For any linear code C over Fq2 of length n , Rains [ 20 ] defined the puncture code P(C) to be P(C) = {λ= (λ1, . . . , λn)∈Fn q| n X i=1 λiuivq i= 0,for all u, v ∈C}.(2) Then, clearly we have the following theorem. Theorem 2.1 Let C be a linear code over Fq2 of length n . There is a truncation of C to a linear code over Fq2 of length r⩽n which is linearly equivalent to a Hermitian self-orthogonal code if and only if there is an element of P(C)of weight r. Thus, as emphasised in [ 8 ], the puncture code is an extremely useful tool in constructing Hermitian self-orthogonal codes. Observe that the minimum distance of any quantum code, given by an element in the puncture code, will have minimum distance at least the minimum distance of C⊥ . This follows since any element in the dual of the truncated code will be an element of C⊥ if we replace the deleted coordinates with zeros. 3 Hermitian self-orthogonal generalised Reed-Solomon codes In this section we focus on the puncture code of the Reed-Solomon code. We will prove that the puncture code can be obtained as the evaluation code of polynomials which belong to a specified subspace (5). This leads to the particularly useful Theorem 3.4. This theorem gives necessary and sufficient conditions on the existence of a truncation of a Reed-Solomon code being linearly equivalent to a Hermitian self-orthogonal code. This equivalence is in terms of the existence of a polynomial 3 with certain properties. These properties bound the degree of the polynomial and the number of trace zero evaluations that it has. Here, the trace refers to the standard trace function from Fq2 to Fq . Finally, we give examples of such polynomials and therefore truncations of the Reed-Solomon code to codes which are linearly equivalent to Hermitian self-orthogonal codes. Throughout the article {a1, . . . , aq2}will denote the set of elements of Fq2. Ageneralised Reed-Solomon code over Fq2is D={(θ1f(a1), . . . , θq2f(aq2), θq2+1fk−1)|f∈Fq2[X],deg f⩽k−1}, where fidenotes the coefficient of Xiin f(X) and θi∈Fq2\ {0}. The Reed-Solomon code over Fq2 C={(f(a1), . . . , f(aq2), fk−1)|f∈Fq2[X],deg f⩽k−1}, is obtained from the above definition by setting θi = 1 for all i∈ { 1 , . . . , q2 + 1 } . Thus, a generalised Reed-Solomon code, up to permutation of the coordinates, simply describes all linear codes linearly equivalent to the Reed-Solomon code C. We note that our definition of a Reed-Solomon code, and its generalised version, is what some authors call the extended or doubly extended Reed-Solomon code. That is, many authors do not include the final coordinate or the evaluation at zero. A generalised Reed-Solomon code is an example of a maximum distance separable code (MDS code). By definition, MDS codes are those codes attaining the Singleton bound which, for linear [n, k, d] codes, is k⩽n−d+ 1. By (1), the Reed-Solomon code C (or its truncation if some of the θi are zero) is linearly equivalent to a Hermitian self-orthogonal code if and only if θq+1 q2+1fq k−1gk−1+ q2 X i=1 θq+1 if(ai)qg(ai)=0,(3) for all polynomials f, g ∈Fq2[X] of degree at most k−1. Equivalently, according to (2), (θq+1 1, . . . , θq+1 q2, θq+1 q2+1)∈P(C).(4) Thus, to determine all truncations of a generalised Reed-Solomon code which are Hermitian self-orthogonal, it suffices to determine the puncture code P ( C ) of the Reed-Solomon code. In the following theorem we prove that P ( C ) is the evaluation code of the Fq-subspace U=   h∈Fq2[X]|h(X) = q−k−1 X i=0 q−1 X j=i+1 (hijXiq+j+hq ijXjq+i) + q−k X i=0 hiXi(q+1)   , (5) 4 where hij ∈Fq2and hi∈Fq. Observe that U is a subspace over Fq since h, g ∈U implies g + h∈U and λh ∈U for all λ∈Fq. The size of Uis q2((q−1)(q−k)−1 2(q−k−1)(q−k))qq−k+1 =qq2−k2+1. Hence, the dimension of U, as a subspace over Fq, is q2+ 1 −k2. It was proven in [ 1 , Theorem 5] that if k⩾q + 1 then for C , the k -dimensional Reed-Solomon code, P(C) = {0}. Theorem 3.1 If k⩽qand Cis a k-dimensional Reed-Solomon code then P(C) = {(h(a1), . . . , h(aq2), hq−k)|h∈U}, where Uis defined as in (5). In particular, we have that dim P(C) = q2+ 1 −k2. Proof. Firstly we verify that all functions from Fq2 to Fq are evaluations of polynomials of the form h(X) = q−2 X i=0 q−1 X j=i+1 (hijXiq+j+hq ijXjq+i) + q−1 X i=0 hiXi(q+1),(6) where hij ∈Fq2and hi∈Fq. Note that h(x)∈Fqfor all x∈Fq2and there are q2(q−1 2)qq=qq2 polynomials of this form. Each defines a distinct function from Fq2 to Fq and since there are qq2 such functions, the evaluation of such polynomials describes all of them. The condition (4) (h(a1), . . . , h(aq2), c)∈P(C) is equivalent to condition (3), which in this case is cfq k−1gk−1+ q2 X `=1 h(a`)f(a`)qg(a`)=0, for all polynomials f, g ∈Fq2[X], where deg f, deg g⩽k−1, Substituting, f(X) = Xrand g(X) = Xs, where s<r⩽k−1, this becomes q2 X `=1 h(a`)arq+s `= 0. 5 Thus, from (6), q2 X `=1 q−2 X i=0 q−1 X j=i+1 (hija(i+r)q+j+s `+hq ija(j+r)q+i+s `) + q2 X `=1 q−1 X i=0 hia(i+r)q+i+s `= 0. The only term in these sums whose exponent is q2−1 is hq−1−r,q−1−saq2−1 `. Using the fact that X t∈Fq2 ti= 0, for all i= 0, . . . , q2−2 and X t∈Fq2 tq2−1=−1, we have that hij = 0 for i⩾q−kand j⩾i+ 1. Similarly, substituting f ( X ) = Xr and g ( X ) = Xr , where r⩽k− 2 implies hi = 0 for i⩾q−k + 1. And substituting f ( X ) = Xk−1 and g ( X ) = Xk−1 , we conclude that c=hq−k. Thus, we have proved that P(C)⊆CU={(h(a1), . . . , h(aq2), hq−k)|h∈U}. To prove equality, suppose f(a`) = k−1 X r=0 frar `and g(a`) = k−1 X s=0 gsas `. The sum hq−kfq k−1gk−1+ q2 X `=1 k−1 X r,s=0 q−k−1 X i=0 q−1 X j=i+1 fq rgs(hija(i+r)q+s+j `+hq ija(r+j)q+s+i `) + q2 X `=1 q−k X i=0 fq rgshia(i+r)q+s+i ` is zero, since the only term in the sums whose exponent is q2− 1 is the term in the last sum when r=s=k−1 and i=q−k. Thus, we have that this sum is hq−kfq k−1gk−1−hq−kfq k−1gk−1= 0. Hence, CU⊆P(C). The dimension of P(C) follows from the fact that dim U=q2+ 1 −k2. 6 Theorem 3.1 has the following corollary. Theorem 3.2 Suppose k⩽q− 1. There is a linear [ n, k, n −k + 1] q2 Hermitian self-orthogonal truncated generalised Reed-Solomon code if and only if there is a polynomial h(X) = q−k−1 X i=0 q−1 X j=i+1 (hijXiq+j+hq ijXjq+i) + q−k−1 X i=0 hiXi(q+1) +X(q−k)(q+1), which has q2 + 1 −n distinct zeros when evaluated at x∈Fq2 , or a polynomial h(X)∈Fq2[X]of the form h(X) = q−k−1 X i=0 q−1 X j=i+1 (hijXiq+j+hq ijXjq+i) + q−k−1 X i=0 hiXi(q+1) which has q2−ndistinct zeros when evaluated at x∈Fq2. Proof. This follows directly from Theorem 3.1 and the definition of U . The two cases depend on whether h ( X ) has a term of degree ( q−k )( q + 1) or not. If it does then we can scale h(X) so that the coefficient of X(q−k)(q+1) is one.  In the following theorem we prove that the subspace U , as a subspace of functions from Fq2 to Fq , has an alternative and more useful description. Specifically, the functions defined by the polynomials h can be obtained from polynomials of small degree as specified in the following theorem. Theorem 3.3 If k⩽qand Cis a k-dimensional Reed-Solomon code then P(C) = {(g(a1) + g(a1)q+ca(q−k)(q+1) 1, . . . , g(aq2) + g(aq2)q+ca(q−k)(q+1) q2, c) |g∈Fq2[X],deg g⩽(q−k)q−1, c ∈Fq}. Proof. We have to show that for each h∈U there is a g∈Fq2 [ X ], where deg g⩽ (q−k)q−1, such that h(X) and g(X) + g(X)q+cX(q−k)(q+1) define the same function, and vice-versa. Suppose h(X) = q−k−1 X i=0 q−1 X j=i+1 (hijXiq+j+hq ijXjq+i) + q−k X i=0 hiXi(q+1). 7 Define g(X) = q−k−1 X i=0 q−1 X j=i+1 hijXiq+j+ q−k−1 X i=0 giXi(q+1), where gi+gq i=hifor i∈ {0, . . . , q −k−1}, and let c=hq−k. Then, g(x) + g(x)q+cx(q−k)(q+1) =h(x), for all x∈Fq2. Vice-versa, suppose g(X) = q−k−1 X i=0 i−1 X j=0 gijXiq+j+ q−k−1 X i=0 q−1 X j=i+1 gijXiq+j+ q−k−1 X i=0 giXi(q+1) and c∈Fq. For all x∈Fq2, switching the order of the sums in the first and third sums, g(x) + g(x)q= q−k−2 X j=0 q−k−1 X i=j+1 gijxiq+j+ q−k−1 X i=0 q−1 X j=i+1 gijxiq+j + q−k−2 X j=0 q−k−1 X i=j+1 gq ijxjq+i+ q−k−1 X i=0 q−1 X j=i+1 gq ijxjq+i+ q−k−1 X i=0 (gi+gq i)xi(q+1). Since gij = 0 for i>j⩾q−k−1 and for i⩾q−k, g(x) + g(x)q= q−k−1 X j=0 q−1 X i=j+1 gijxiq+j+ q−k−1 X i=0 q−1 X j=i+1 gijxiq+j + q−k−1 X j=0 q−1 X i=j+1 gq ijxjq+i+ q−k−1 X i=0 q−1 X j=i+1 gq ijxjq+i+ q−k−1 X i=0 (gi+gq i)xi(q+1). = q−k−1 X i=0 q−1 X j=i+1 ((gij +gq ji)xiq+j+ (gq ij +gji)xjq+i) + q−k−1 X i=0 (gi+gq i)xi(q+1) Thus, we define h(X) = q−k−1 X i=0 q−1 X j=i+1 ((gij+gq ji)Xiq+j+(gq ij+gji)Xjq+i)+ q−k−1 X i=0 (gi+gq i)Xi(q+1)+cX(q−k)(q+1) and conclude that g(x) + g(x)q+cx(q−k)(q+1) =h(x), for all x∈Fq2. 8 If k = q then the puncture code has dimension one and is spanned by the all-one vector and, as mentioned before, if k⩾q + 1 then the puncture code is trivial. Thus, we can restrict to the case k⩽q−1. The case in which n = q2 +1 will be dealt with separately in Section 5. In the case n⩽ q2 we can apply the description of the puncture code given in Theorem 3.3. This leads to the following theorem which gives a straightforward method to obtain Hermitian self-orthogonal truncations of a generalised Reed-Solomon code. One chooses a polynomial g ( X ) of small degree and deduces how many zeros the polynomial g(X) + g(X)qhas. Theorem 3.4 Suppose k⩽q− 1and n⩽q2 . There is a linear [ n, k, n −k + 1] q2 Hermitian self-orthogonal truncated generalised Reed-Solomon code if and only if there is a polynomial g(X)∈Fq2[X]of degree at most (q−k)q−1, where g(X) + g(X)q has q2−ndistinct zeros when evaluated at x∈Fq2. Proof. The reverse implication follows from Theorem 2.1 and Theorem 3.3 (taking c= 0). For the forward implication, Theorem 2.1 implies there is a codeword in the puncture code of weight n. If the final coordinate is zero then Theorem 3.3 suffices. If not then we have to prove that a codeword in the puncture code of weight n with a non-zero final coordinate implies there is also a codeword in the puncture code of weight nwhose final coordinate is zero. Then we can apply Theorem 3.3. Suppose that the j -th coordinate is the coordinate of a codeword in the puncture code of weight nwhich is zero. Then, by (3), there are elements θi∈Fq2such that, for all polynomials f, g ∈Fq2[X] of degree at most k−1, θq+1 q2+1fq k−1gk−1+ q2 X i=1 i6=j θq+1 if(ai)qg(ai)=0, where as before fk−1 and gk−1 are the coefficients of Xk−1 in f ( X ) and g ( X ) respectively. Now, f(X)=(X−aj)k−1f(1 X−aj ), for some polynomial fof degree at most k−1. Thus, with bi=1 ai−aj , 9 The degree of cg is at most (3 2q−k−2)q+1 2q−m−3⩽(m+1 2)q−1 2q−m−3. Arguing as in Case 1, the only terms of degree aq + b in cgq modulo Xq2−X , for which a∈ {1 2q+m, . . . , q −1}, have b∈ {0,...,1 2q−2}, since q−k−1 + 1 2q−m−2⩽1 2q−2. However, we chose c ( X ) so that c ( g + gq ) has no terms of degree aq + b , where a∈ {1 2q+m+ 1, . . . , q −1}and b∈ {0,...,1 2q−2}. Hence, we conclude that c(g+gq) (mod Xq2−X) has degree at most (1 2q+m)q+1 2q−2. Now we use the fact that g + gq has at least ( 1 2q + m + 1 2 ) q + 1 zeros to conclude that c(g+gq) = 0 (mod Xq2−X). Then the fact that g + gq has at most ( 1 2q + m + 1) q distinct zeros implies that c has more than (1 2q−m−1)qdistinct zeros. However, cq= 1 2q−1 X i=0 1 2q−m−2 X j=0 cq ijXjq+i(mod Xq2−X), which has degree at most ( 1 2q−m− 2) q + 1 2q− 1. This implies c = 0, contradicting the fact that c6= 0.  Lemma 4.4 If ( q + 1) / 2 ⩽k⩽q− 1and q is odd then the minimum distance of the puncture code P ( C )of the [ q2 + 1 , k, q2 + 2 −k ] q2 Reed-Solomon code C is at most (q+ 1)(k−(q−1)/2). Proof. Let R be a subset of Fq of size q−k− 1 such that e(q−1)/2 = 1 for all e∈R . Define g(X) = X(q+1)/2Y e∈R (Xq+1 −e) = q−k−1 X i=0 q−1 X j=0 gijXiq+j. For all x∈Fq2, g(x) + g(x)q= (x(q2+q)/2+x(q+1)/2)Y e∈R (xq+1 −e). There are q +1 elements of Fq2 such that xq+1 = e and for these elements x(q+1)(q−1)/2 = 1, since e(q−1)/2= 1. There are (q2+ 1)/2 elements of Fq2such that x(q2+q)/2+x(q+1)/2=x(q+1)/2(x(q2−1)/2+ 1) = 0 16 which are distinct from the other (q−k−1)(q+ 1) zeros. Thus, g(x) + g(x)qhas (q2+ 1)/2+(q−k−1)(q+ 1) distinct zeros. By Theorem 3.3, P(C) has a codeword of weight q2−(q2+ 1)/2−(q−k−1)(q+ 1) = (q+ 1)(k−(q−1)/2).  Theorem 4.5 If ( q + 1) / 2 ⩽k⩽q− 1and q is odd then the minimum distance of the puncture code P ( C )of the [ q2 + 1 , k, q2 + 2 −k ] q2 Reed-Solomon code C is (q+ 1)(k−1 2(q−1)). Proof. Lemma 4.4 implies that there is a codeword of weight ( q + 1)( k−1 2 ( q− 1)) in the puncture code, so we only need show that P ( C ) cannot have codewords of less weight. Suppose that P ( C ) has a codeword of weight at most ( q + 1)( k−1 2 ( q− 1)) − 1. By Theorem 3.4 and Theorem 2.1, there is a polynomial g∈Fq2 [ X ] of degree at most (q−k)q−1 such that g+gq has at least q2−(q+ 1)(k−1 2(q−1)) = (q+1 2(q−1) −k)q+1 2(q+ 1) −kzeros. As in the proof of Theorem 4.3, we will obtain a contradiction considering two separate cases. Case 1: Suppose that g + gq has between ( 1 2 ( q− 1) + m ) q + 1 2 ( q + 1) −k and (1 2(q−1) + m)q+q−kdistinct zeros in Fq2, for some m. By the above, we have that m⩾q−k . If m⩾1 2 ( q + 1) then this would imply that g+gqhas more zeros than its degree, so m⩽1 2(q−1). Let c(X) = 1 2(q−1) X i=0 1 2(q−1)−m X j=0 cijXiq+j, where the coefficients cij are zero when j = 1 2 ( q− 1) −m and i⩾m + 1 and are chosen so that c(g+gq) (mod Xq2−X) has no terms of degree aq + b , where a∈ {1 2 ( q− 1) + m, . . . , q − 1 } and b∈ {0,...,1 2(q−3)}, unless a=1 2(q−1) + mand b⩽1 2(q−1) −k. The degree of cg is at most (3 2(q−1) −k)q+3 2(q−1) −m. 17 Thus, in the case m = q−k we must also choose the coefficients of c ( X ) so that c ( g + gq ) has no terms of degree ( 1 2 ( q− 1) + m ) q + r , for r∈ {1 2 ( q + 1) −k, . . . , − 1 } . Thus, in doing so, the degree of c(g+gq) (mod Xq2−X) is less than the number of distinct zeros of g+gq. Such a non-zero polynomial c(X) exists since, in the case m>q−k, we impose (1 2(q+ 1) −m)1 2(q−1) linear homogeneous conditions and we have (1 2(q−1) −m)1 2(q+ 1) + 1 2(q+ 1) −m coefficients defining c(X). In the case m=q−k, we impose (k−1 2(q−1))1 2(q−1) + k−1 2(q+ 1) linear homogeneous conditions and we have (k−1 2(q−1))1 2(q−1) + k−1 2(q−1) coefficients defining c(X). Now we use the fact that g+gqhas at least (1 2(q−1) + m)q+1 2(q+ 1) −k zeros to conclude that c(g+gq) = 0 (mod Xq2−X). Then the fact that g+gqhas at most (1 2(q−1) + m)q+q−1−k distinct zeros implies that chas more than (1 2(q−1) −m)q+k+ 1 distinct zeros. However, cq= 1 2(q−1) X i=0 1 2(q−1)−m X j=0 cq ijXjq+i(mod Xq2−X), which has degree at most ( 1 2 ( q− 1) −m ) q + m . Recall that the coefficients cij are zero when j=1 2(q−1) −mand i⩾m+ 1. 18 This implies c= 0, contradicting the fact that c6= 0. Case 2: Suppose that g + gq has between ( 1 2 ( q− 1) + m ) q + q−k + 1 and ( 1 2 ( q− 1) + m + 1) q + 1 2 ( q− 1) −k distinct zeros in Fq2 , for some m . As before, we have that 1 2(q−1) ⩾m⩾q−k. Let c(X) = 1 2(q−1) X i=0 1 2(q−1)−m X j=0 cijXiq+j, where cij = 0, if j = 1 2 ( q− 1) −m and i⩾k−1 2 ( q− 1), and the coefficients cij are chosen so that c(g+gq) has no terms of degree aq + b , where a∈ {1 2 ( q− 1) + m, . . . , q − 1 } and b∈ {0,...,1 2(q−3)}, unless a=1 2(q−1) + mand b⩽q−k−1. Such a non-zero polynomial c(X) exists since we impose (1 2(q+ 1) −m)1 2(q−1) −(q−k) linear homogeneous conditions and we have (1 2(q−1)−m)1 2(q+1)+k−1 2(q−1) ⩾(1 2(q+1)−m)1 2(q−1)−(q−k)−m+1 2(q+1) coefficients defining c(X). The degree of cg is at most (3 2(q−1) −k)q+3 2(q−1) −m⩽(m+1 2(q−1))q+1 2(q−3) −m. Arguing as in Case 1, the only terms of degree aq + b in cgq modulo Xq2−X , for which a∈ {1 2(q−1) + m, . . . , q −1}, have b∈ {0,...,1 2(q−3)}. However, we chose c ( X ) so that c ( g + gq ) has no terms of degree aq + b , where a∈ {1 2 ( q− 1) + m, . . . , q − 1 } and b∈ { 0 ,...,1 2 ( q− 3) } , unless a = 1 2 ( q− 1) + m and b⩽q−k−1. Hence, we conclude that c(g+gq) (mod Xq2−X) has degree at most (1 2(q−1) + m)q+q−k−1. Now we use the fact that g + gq has at least ( 1 2 ( q− 1) + m ) q + q−k zeros to conclude that c(g+gq) = 0 (mod Xq2−X). Then the fact that g+gqhas at most (1 2(q−1) + m+ 1)q+1 2(q−1) −k 19 distinct zeros implies that chas at least (1 2(q−1) −m)q+k−1 2(q−1) distinct zeros. However, cq(X) = 1 2(q−1) X i=0 1 2(q−1)−m X j=0 cijXjq+i(mod Xq2−X), and cij = 0, if j=1 2(q−1) −mand i⩾k−1 2(q−1). Thus, cq(mod Xq2−X) has degree at most (1 2(q−1) −m)q+k−1 2(q−1) −1. This implies c= 0, contradicting the fact that c6= 0.  5 Hermitian self-orthogonal generalised Reed-Solomon codes of length q2+ 1 The existence of a Hermitian self-orthogonal [ q2 +1 , k, q2−k +2] q2 code is of particular importance since these codes are of the same length as the Reed-Solomon code. Apart from the exceptional case q is even and k∈ { 3 , q − 1 } , no longer non-trivial MDS code is known. Existence was already demonstrated in [ 1 ] for k⩽q− 2, so we restrict ourselves to the case k = q− 1. In [ 8 ], the existence of a Hermitian self-orthogonal [ q2 + 1 , q − 1 , q2−q + 3] q2 code was shown for q odd and for q = 2 h , where h∈ { 3 , 4 , 5 , 6 , 7 } , whereas in [1] non-existence was proven for q= 4. Here we will prove that such codes exist for all q= 2r, when r⩾3 is odd. Lemma 5.1 Suppose that q = 2 r , where r is odd. If e is such that eq+1 = 1 and e(q+1)/36= 1 then the polynomial eX3+eqX3q+Xq+1 + 1 has no zeros in Fq2. Proof. Suppose ex3+eqx3q+xq+1 + 1 = 0, for some x∈Fq2. 20 We can write x=ay, where aq+1 = 1 and y∈Fq. Then, the above becomes, (ea3)+(ea3)−1+y−1+y−3= 0.(8) If c is a ( q +1)-st root of unity or an element of Fq then c + c−1∈Fq . If c + c−1 = b + b−1 then c=bor c=b−1. Thus, there is a c∈Fq2such that y−1=c+c−1. Observe that y−1+y−3=c3+c−3, so (8) becomes (ea3+c3)(1 + (ea3c3)−1) = 0. Thus, either e = c3/a3 or e = ( ca ) −3 . Either way, e is a cube. Since ( q− 1 , 3) = 1 and e is also a ( q + 1)-st root of unity, e = t3(q−1) , for some t∈Fq2 . Hence, e(q+1)/3 = 1, contradicting the assumption that e(q+1)/36= 1.  Theorem 5.2 If q = 2 r and r⩾ 3is odd then there is a Hermitian self-orthogonal [q2+ 1, q −1, q2−q+ 3]q2generalised Reed-Solomon code. Proof. This follows from Theorem 3.2 and Lemma 5.1.  6 Previous results on Hermitian self-orthogonal MDS codes There are many constructions of quantum MDS codes with d⩽q + 1, mostly based on cyclic or constacyclic constructions and generalised Reed-Solomon codes. For example those contained in [4–6], [8, 9], [11], [12–15], [18, 19], [21–23] and [24–26]. These articles contain too many constructions to list them all. By means of example, in Table 1, we detail the seven classes constructed by Tao Zhang and Gennian Ge in [26] using Hermitian self orthogonal generalised Reed-Solomon codes. Examples 3.5, 3.6 and 3.7 give examples of Hermitian self-orthogonal MDS codes of length n , where n is not just a multiple of q + 1 or q− 1. Using Theorem 3.4, one has much more scope to construct examples than using the previous methods which were employed in the articles cited above. 7 Further work and open problems As mentioned in Section 5, the existence of a [ q2 + 1 , k, q2−k + 2] q2 Hermitian self-orthogonal generalised Reed-Solomon code is of particular interest, since this determines if the Reed-Solomon code itself is linearly equivalent to a Hermitian self-orthogonal code. It was proven in [ 1 ] that such codes exist for all k⩽q− 2 and k = q + 1 and do not exist for k⩾q + 2. Thus, in the case n = q2 + 1, we are only interested in k = q− 1. In [ 8 ], existence was shown for q odd and q = 2 h , where h∈ { 3 , 4 , 5 , 6 , 7 } , whereas in [ 1 ] non-existence was proven for q = 4. In Theorem 5.2 21 Class Length Distance 1n=bm(q+ 1),2≤d≤q+1 2+m m|q−1 2, bm ≤q−1 2n= (bm +c(m−1))(q+ 1), 2 ≤d≤q−1 2+m m|q−1 2, b, c ≥0,(b+c)m≤q−1 and b≥1 or m≥2 3n=bm(q−1),2≤d≤q−1 2+m m|q+1 2, bm ≤q+ 1 4n= (bm +c(m−1))(q−1), 2 ≤d≤q−3 2+m m|q−1 2, b, c ≥0,(b+c)m≤q+ 1 and b≥1 or m≥2 5n= (c1(2m−1) + (c2+c3)m)(q−1) 2 ≤d≤q−1 2+m m|q+1 2, c1, c2, c3≥0,0≤c1+c2≤q+1 2m, 0≤c1+c3≤q+1 2mand c1+c2+c3≥1 6n=c(q−1),2≤d≤q−1 2+c1, q= 2am −1, gcd(a, m)=1, c1=(c; if 1 ≤c≤a+m−1, bc 2c; if a+m≤c≤2(a+m−1). 1≤c≤2(a+m−1) 7n=c(q+ 1),2≤d≤q+1 2+c1, q= 2am −1, gcd(a, m)=1, c1=(c; if 1 ≤c≤a+m−1, bc 2c; if a+m≤c≤2(a+m−1). 1≤c≤2(a+m−1) Table 1: Summary of Quantum MDS Codes constructed in [26]. of this article, we have proved existence for all q = 2 h with h odd. Thus, we are left with only the cases q = 2 h , h even and h⩾ 8. According to Theorem 3.2, to prove existence it suffices to find a polynomial h(X) = q−1 X i=1 (hiXi+hq iXiq) + c+Xq+1, where hi∈Fq2and c∈Fq, which has no zeros in Fq2. Conjecture 15 from [ 8 ] addresses another question. It conjectures that, for q = 2 h and q6 = 4, there are quantum MDS codes with parameters [[ n, n − 6 , 4]] q for all 6 ⩽n⩽q2 + 2. According to Theorem 3.4, together with Theorem 1.1, this would be verified (for n⩽q2 ) if one could find a polynomial g∈Fq2 [ X ], of degree at most ( q− 3) q− 1, such that g ( x ) + g ( x ) q has q2−n distinct zeros in Fq2 , for values of n⩽q2. 22 8 Acknowledgements The proof of Lemma 5.1 is due to Prof. Aart Blokhuis and we are very grateful to him for providing us with a proof of what we had only been able to verify by computer for r⩽19. We are grateful to the referees and the editor who provided us with feedback which was very helpful. References [1] S. Ball, Some constructions of quantum MDS codes, Des. Codes Cryptogr.,89 (2021) 811–821. [2] S. Ball, The Grassl-R¨otteler cyclic and consta-cyclic MDS codes are generalised Reed-Solomon codes, arXiv:2112.11896. [3] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, Quantum error correction via codes over GF (4), IEEE Trans. Inform. Theory,44 (1998) 1369–1387. [4] B. Chen, S. Ling and G. Zhang, Application of constacyclic codes to quantum MDS codes. IEEE Trans. Inform. Theory,61 (2015) 1474–1484. [5] W. Fang and F. Fu, Some new constructions of quantum MDS codes. (2018). arXiv:1804.08213vl. [6] W. Fang and F. Fu, Two new classes of quantum MDS codes. Finite Fields Appl.,53 (2018) 85–98. [7] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, (available online at http://www.codetables.de). [8] M. Grassl and M. R¨otteler, Quantum MDS codes over small fields, in Proc. Int. Symp. Inf. Theory (ISIT), 1104–1108 (2015). [9] X. He, L. Xu and H. Chen, New q -ary quantum MDS codes with distances bigger than q/2, Quantum Inf. Process.,15 (2016) 2745–2758. [10] F. Huber and M. Grassl, Quantum codes of maximal distance and highly entangled subspaces, Quantum,4284 (2020). [11] L. Jin, H. Kan and J. Wen, Quantum MDS codes with relatively large minimum distance from Hermitian self-orthogonal codes. Des. Codes Cryptogr.,84 (2017) 463–471. [12] L. Jin, S. Ling, J. Luo and C. Xing, Application of classical Hermitian selforthogonal MDS codes to quantum MDS codes, IEEE Trans. Inform. Theory, 56 (2010) 4735–4740. 23 [13] L. Jin and C. Xing, A construction of new quantum MDS codes. IEEE Trans. Inform. Theory,60 (2014) 2921–2925. [14] X. Kai and S. Zhu, New quantum MDS codes from negacyclic codes, IEEE Trans. Inform. Theory,59 (2012) 1193–1197. [15] X. Kai, S. Zhu and P. Li, Constacyclic codes and some new quantum MDS codes, IEEE Trans. Inform. Theory,60 (2014) 2080–2086. [16] A. Ketkar, A. Klappenecker, S. Kumar and P. K. Sarvepalli, Nonbinary stabilizer codes over finite fields, IEEE Trans. Inform. Theory,52 (2006) 4892–4914. (available online at https://arxiv.org/abs/quant-ph/0508070) [17] E. Knill and R. Laflamme. Theory of quantum error-correcting codes, Phys. Rev. A,55 (1997) 900–911. [18] R. Li and Z. Xu, Construction of [[ n, n − 4 , 3]] q quantum MDS codes for odd prime power q,Phys. Rev. A,82 052316-1-052316-4 (2010). [19] Z. Li, L. Xing and X. Wang, Quantum generalized Reed-Solomon codes: unified framework for quantum MDS codes. Phys. Rev. A,77 012308-1-012308-4 (2008). [20] E. M. Rains, Nonbinary quantum codes, IEEE Transactions on Information Theory,45 (1999) 1827–1832. [21] X. Shi, Q. Yue and Y. Chang, Some quantum MDS codes with large minimum distance from generalized Reed-Solomon codes, Cryptogr. Commun.,10 (2018) 1165–1182. [22] X. Shi, Q. Yue and Y. Wu, New quantum MDS codes with large minimum distance and short length from generalized Reed-Solomon codes, Discrete Math., 342 (2019) 1989–2001. [23] X. Shi, Q. Yue and X. Zhu, Construction of some new quantum MDS codes. Finite Fields Appl.,46 (2017) 347–362. [24] L. Wang and S. Zhu, New quantum MDS codes derived from constacyclic codes, Quantum Inf. Process.,14 (2015) 881–889. [25] G. Zhang and B. Chen, New quantum MDS codes, Int. J. Quantum Inf.,12 (2014) 1450019-1-1450019-10. [26] T. Zhang and G. Ge, Quantum MDS codes with large minimum distance, Des. Codes Cryptogr.,83 (2017) 503–517. Simeon Ball Departament de Matem`atiques, 24 Universitat Polit`ecnica de Catalunya, M`odul C3, Campus Nord, Carrer Jordi Girona 1-3, 08034 Barcelona, Spain [email protected] Ricard Vilar Departament de Matem`atiques, Universitat Polit`ecnica de Catalunya, M`odul C3, Campus Nord, Carrer Jordi Girona 1-3, 08034 Barcelona, Spain [email protected] 25