Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes

G assl-R ¨ o ele cyclic and cons a-cyclic MDS codes a e gene alised Reed-Solomon codes Simeon Ball* Abs ac We p o e ha he cyclic and cons acyclic codes cons uc ed by G assl and R ¨ o ele in [ 6 ] a e gene alised Reed-Solomon codes. This no e can be conside ed as an addendum o G assl and R ¨ o ele [ 6 ]. I can also be conside ed as an appendix o Ball and Vila [ 4 ], whe e Conjec u e 11 o [ 6 ], which was s a ed o G assl-R ¨ o ele codes, is p o en o gene alised Reed-Solomon codes. The con en o his no e, oge he wi h [ 4 ], he e o e implies ha Conjec u e 11 om [6] is ue. 1 In oduc ion Le Fq deno e he ini e ield wi h q elemen s. The weigh o an elemen o Fn q is he numbe o non-ze o coo dina es ha i has. A k -dimensional linea code o leng h n and minimum dis ance d o e Fq , deno ed as an [n, k, d]q code, is a k -dimensional subspace o Fn q in which e e y non-ze o ec o has weigh a leas d. The Single on bound o linea codes s a es ha n⩾k+d−1 and a linea code which a ains he Single on bound is called a maximum dis ance sepa able code, o MDS code o sho . I is a simple ma e o p o e he bound n⩽q+k−1. The MDS conjec u e, o linea codes, s a es ha i 4⩽k⩽q−2 hen n⩽q+ 1. * 14 Decembe 2022. The au ho acknowledges he suppo o MTM2017-82166-P and PID2020-113082GB-I00 inanced by MCIN / AEI / 10.13039/501100011033, he Spanish Minis y o Science and Inno a ion. 1 2 Fo alues o k ou side o his ange i is no di icul o de e mine he longes leng h o a linea MDS code. The MDS conjec u e is known o hold o q p ime [ 1 ], whe e i was also p o en ha i k6= (q+ 1)/2 and q is p ime hen a [q+ 1, k, q + 2 −k]q MDS code is a gene alised Reed-Solomon code. Le {a1, . . . , aq}be he se o elemen s o Fq. Agene alised Reed-Solomon code o e Fqis D={(θ1 (a1), . . . , θq (aq), θq+1 k−1)| ∈Fq[X],deg ⩽k−1},(1) whe e ideno es he coe icien o Xiin (X)and θi∈Fq {0}. The Reed-Solomon code is he case in which θj= 1, o all j. We no e ha ou de ini ion o a (gene alised) Reed-Solomon code is wha some au ho s call he ex ended o doubly ex ended Reed-Solomon code. Tha is, many au ho s do no include he inal coo dina e o he e alua ion a ze o. Howe e , a mo e na u al de ini ion o he Reed- Solomon code, which is en i ely equi alen o he abo e, is ob ained by e alua ing homogeneous polynomials ∈Fq[X1, X2]o deg ee k−1, a he poin s o he p ojec i e line, D={(θ1 (a1,1), . . . , θq (aq,1), θq+1 (1,0)) | ∈Fq[X1, X2], homogeneous,deg =k−1}. (2) The He mi ian p oduc code o a linea code Co e Fq2is H(C) = {uq· |u, ∈C} whe e uq= (uq 1, . . . , uq n) and · is he s anda d inne -p oduc . The punc u e code is he in e sec ion o H(C)⊥ ( he dual code o H(C) ) wi h Fn q . This no e was mo i a ed by Conjec u e 11 om [ 6 ] which s a es ha he minimum dis ance d o he punc u e code o he G assl-R ¨ o ele code sa is ies d=       2ki 1 ⩽k⩽q/2 (q+ 1)(k−1 2(q−1)) i (q+ 1)/2⩽k⩽q−1, q odd q(k+ 1 −q/2) i q/2⩽k⩽q−1, q e en q2+ 1 i k=q. The equi alen e sion o his conjec u e o gene alised Reed-Solomon codes is p o en in [ 4 ] o gene alised Reed-Solomon codes. Combined wi h he con en o his no e, his implies ha Conjec u e 11 om [6] is indeed ue. 2 Gene alised Reed-Solomon codes In his sec ion we p o e ha a gene alised Reed-Solomon code can be cons uc ed as an e alua ion code, e alua ing a he (q+ 1) - h oo s o uni y o Fq2 . Thus, any gene alised Reed-Solomon 3 code can be ob ained in his way by mul iplying he i - h coo dina e by a non-ze o θi∈Fq , as in de ini ion (1) and (2). Le {α1, . . . , αq+1}be he se o (q+ 1)- h oo s o uni y o Fq2. Lemma 1. I k⩽qis odd hen he code C={(h(α1) + h(α1)q, . . . , h(αq+1) + h(αq+1)q)|h∈Fq2[X],deg h⩽1 2(k−1)} is a [q+ 1, k, q + 2 −k]qgene alised Reed-Solomon code. P oo . Le σ be he map om he polynomials o Fq2[X] o deg ee a mos 1 2(k−1) o Fq+1 q de ined by σ(h) = (h(α1) + h(α1)q, . . . , h(αq+1) + h(αq+1)q). Since, o all λ, ν ∈Fqand g, h ∈Fq2[X], (λh(α1) + λh(α1)q, . . . , λh(αq+1) + λh(αq+1)q) +(νg(α1) + νg(α1)q, . . . , νg(αq+1) + νg(αq+1)q) = ((λh +νg)(α1) + ((λh +νg)(α1))q,...,(λh +νg)(αq+1) + ((λh +νg)(αq+1))q), i ollows ha σis an Fq-linea map. Le h(X) = 1 2(k−1) X i=0 ciXi. Fo α, a (q+ 1)-s oo o uni y, we ha e h(α) + h(α)q=c0+cq 0+ 1 2(k−1) X i=1 ciαi+ 1 2(k−1) X i=1 cq iα−i. I ci6= 0 o some i6= 0 o c0+cq 06= 0 hen his implies ha a mos k−1⩽q−1 o he coo dina es o σ(h) a e ze o. This implies ha σ(h) = 0 i and only i ci= 0 o all i6= 0 and c0+cq 0= 0 . The e o e, σ is an Fq -linea map which has a one-dimensional ke nel. I ollows ha he image o he map σ , which is C , has dimension 21 2(k+ 1) −1 = k . We conclude ha C is a k-dimensional subspace o Fq+1 q. Suppose ha {1, e}is a basis o Fq2o e Fq. Fo α, a (q+ 1)- h oo o uni y, le x1, x2∈Fqbe such ha α= (x1+ex2)q−1. 4 Obse e ha as (x1, x2) a y o e he poin s o he p ojec i e line, α will un h ough he dis inc (q+ 1)- h oo s o uni y. Then h(α) + h(α)q= 1 2(k−1) X i=0 ci(x1+ex2)i(q−1) +cq i(x1+ex2)i(1−q) = 1 2(k−1) X i=0 ci(x1+eqx2)i(x1+ex2)−i+cq i(x1+ex2)i(x1+eqx2)−i = (x1+ex2)−1 2(k−1)(q+1)X i ci(x1+ex2)1 2(k−1)−i(x1+eqx2)1 2(k−1)+i +cq i(x1+ex2)1 2(k−1)+i(x1+eqx2)1 2(k−1)−i. No e ha (x1+ex2)−1 2(k−1)(q+1) ∈Fq, does no depend on h(X). Thus, he coe icien o xj 1xk−j−1 2o 1 2(k−1) X i=0 ci(x1+ex2)1 2(k−1)−i(x1+eqx2)1 2(k−1)+i+cq i(x1+ex2)1 2(k−1)+i(x1+eqx2)1 2(k−1)−i, is also an elemen o Fq . Hence, he α coo dina e o a codewo d o C is he e alua ion o a homogeneous polynomial in Fq[x1, x2] o deg ee k−1 , mul iplied by a non-ze o elemen o Fq . By de ini ion (2), we conclude ha such a code Cis a gene alised Reed-Solomon code. The p e ious lemma only applies o he case when k is odd. The ollowing lemma deals wi h he case kis e en. Lemma 2. Fo αi , a (q+ 1) - h oo o uni y, le ωi be such ha αi=ωq−1 i . I k is e en hen he code C={ωq 1h(α1) + ω1h(α1)q, . . . , ωq q+1h(αq+1) + ωq+1h(αq+1)q)|h∈Fq2[X],deg h⩽1 2k−1} is a [q+ 1, k, q + 2 −k]qgene alised Reed-Solomon code. P oo . The p oo is simila o ha o Lemma 1. In his case we ha e ha , ω=x1+ex2 and so ωqh(α) + ωh(α)q= 1 2k−1 X i=0 ci(x1+ex2)i(q−1)+q+cq i(x1+ex2)i(1−q)+1 = (x1+ex2)−(1 2k−1)(q+1) X i ci(x1+ex2)1 2k−1−i(x1+eqx2)1 2k+i 5 +cq i(x1+ex2)1 2k+i(x1+eqx2)1 2k−1−i. The coe icien o xj 1xk−j−1 2o X i ci(x1+ex2)1 2k−1−i(x1+eqx2)1 2k+i+cq i(x1+ex2)1 2k+i(x1+eqx2)1 2k−1−i, is an elemen o Fq. Thus, he lemma ollows in he same way as Lemma 1. 3 G assl-R¨ o ele cyclic and cons acyclic MDS codes A k -dimensional cyclic o cons acyclic code hgi o leng h n o e Fq , wi h gene a o polynomial g(X) = n−k X j=0 cjXj∈Fq[X] o deg ee n−k, is a linea code o leng h nspanned by he kcyclic shi s o he codewo d (c0, . . . , cn−k,0,...,0). I is a cyclic code i g di ides Xn−1 and cons acyclic code i g di ides Xn−η , o some η6= 1 . See [2] o [8] o he basic esul s conce ning cyclic codes. In [ 6 ], G assl and R ¨ o ele in oduced h ee [q+ 1, k, q + 2 −k]q MDS codes, he i s wo a e cons uc ed as cyclic codes and he hi d as a cons acyclic code. As men ioned in he in oduc ion, i ollows om [ 1 ] ha when q is p ime and k6=1 2(q+ 1) , hese codes a e gene alised Reed- Solomon codes. In his sec ion we shall p o e ha hey a e gene alised Reed-Solomon codes o all qand k. Le ωbe a p imi i e elemen o Fq2and le α=wq−1, a p imi i e (q+ 1)- h oo o uni y. The G assl-R¨ o ele codes depend on he pa i y o qand k. Fo qand kbo h odd, and qand kbo h e en, he G assl-R¨ o ele code is hg1i, whe e g1(X) = Y i=− (X−αi). Fo kodd and qe en, he G assl-R¨ o ele code is he cyclic code hg2i, whe e g2(X) = 1 2q+ +1 Y i=1 2q− (X−αi). 6 And o ke en and qodd, he G assl-R¨ o ele code is he cons acyclic code hg3i, whe e g3(X) = Y i=− +1 (X−ωαi). I is a simple ma e o check ha o i∈ {1,2,3} , gi∈Fq[X] and o i∈ {1,2} , he polynomial gidi ides Xq+1 −1and g3di ides Xq+1 −ωq+1. We now ea each o he ou cases, which depends on he pa i y o k and q , in u n and p o e ha hey a e all gene alised Reed-Solomon codes. Le {e1, . . . , eq+1}be he canonical basis o Fq+1 q. Le β∈Fq2be such ha β+βq= 1. Theo em 3. I k and q a e bo h odd hen he [q+ 1, k, q + 2 −k]q code hg1i is a gene alised Reed-Solomon code. P oo . Le cjbe de ined by g1(X) = Y i=− (X−αi) = 2 +1 X j=0 cjXj. Obse e ha k=q−2 . We will p o e ha , o a∈ {0, . . . , k −1}, q+1−k+a X s=a (−1)scs−aes+1 = (0,...,0 | {z } a ,(−1)ac0,...,(−1)q+1−k+acq+1−k,0,...,0 | {z } k−1−a ) a e he e alua ions o ce ain polynomials, h(X) + h(X)q whe e h∈Fq2[X]is o deg ee a mos 1 2(k−1), e alua ed a he (q+ 1)- h oo s o uni y. By Lemma 1 hese codes a e gene alised Reed-Solomon codes, which implies ha hg1i is a gene alised Reed-Solomon code. Fo a∈ {0, . . . , k −1}, de ine ha(X) = 1 2(q−1) X i=1 2 +1 X j=0 cjαi(j+a)X(q+1)/2−i+ 2 +1 X j=0 cj(−1)j+aβ+ 2 +1 X j=0 cjβX 1 2(q+1). 7 Fo all i∈ {0, . . . , }, 2 +1 X j=0 cjαij = 0, since g1(αi)=0 . Thus, ha(X) has no e ms o deg ee X1 2(q+1)−i o i∈ {0, . . . , } . Hence, he deg ee o hais a mos 1 2(q−1) − =1 2(k−1). We ha e ha ha(αs) = 1 2(q−1) X i=1 2 +1 X j=0 cjαi(j+a−s)(−1)s+ 2 +1 X j=0 cj(−1)j+aβ+ 2 +1 X j=0 cjβ(−1)s. Since,   1 2(q−1) X i=1 cjαi(j+a−s)  q = q X i=(q+3)/2 cjαi(j+a−s), and β+βq= 1, i ollows ha ha(αs) + ha(αs)q= (−1)s 2 +1 X j=0 q X i=0 cjαi(j+a−s). Since Pq i=0 αij = 0 unless j= 0, in which case i is one, ha(αs) + ha(αs)q= (−1)scs−a, which is p ecisely wha we had o p o e. We nex deal wi h he case kand qa e bo h e en, since his is again he code hg1i. Theo em 4. I k and q a e bo h e en hen he [q+ 1, k, q + 2 −k]q code hg1i is a gene alised Reed-Solomon code. P oo . We can simply copy he p oo o Theo em 3 un il we de ine ha(X) . Then we ha e o de ine ha(X)di e en ly, pa ly because we will apply Lemma 2 in place o Lemma 1. Fo a∈ {0, . . . , k −1}, de ine ha(X) = 1 2q X i=1 2 +1 X j=0 cjαi(j+a)X1 2q−i+ 2 +1 X j=0 cjβX 1 2q. Since g1(αi) = 0, one has ha 2 +1 X j=0 cjαij = 0 8 o all i∈ {0, . . . , } . Thus, ha(X) has no e ms o deg ee X1 2q−i o i∈ {0, . . . , } . Hence, he deg ee o hais a mos 1 2q− −1 = 1 2k−1. As be o e, le ω be a ixed p imi i e elemen o Fq2 and le α=ωq−1 , a p imi i e (q+ 1) - h oo o uni y. Then ha(αs) = 1 2q X i=1 2 +1 X j=0 cjαi(j+a−s)α1 2sq + 2 +1 X j=0 cjβα1 2sq. and so α−sha(αs)q= 1 2q X i=1 2 +1 X j=0 cjα−i(j+a−s)α−1 2sq−s+ 2 +1 X j=0 cjβqα−1 2sq−s. Since, β+βq= 1 and α−1 2sq−s=α1 2sq, i ollows ha ha(αs) + α−sha(αs)q=α1 2sq 2 +1 X j=0 q X i=0 cjαi(j+a−s). Since Pq i=0 αij = 0 unless j= 0, in which case i is one, ha(αs) + α−sha(αs)q=α1 2sqcs−a. Hence, ωsqha(αs) + ωsha(αs)q=ω1 2s(q+1)cs−a. Lemma 2 implies ha i we mul iply he (s+1) - h coo dina e o he codewo ds in hg1i by ω1 2s(q+1) hen we ob ain a gene alised Reed-Solomon code, which implies ha hg1i is a gene alised Reed- Solomon code. The nex heo em deals wi h he case k is odd and q is e en. In his case he G assl-R ¨ o ele code is hg2i. Theo em 5. I k is odd and q is e en hen he [q+ 1, k, q + 2 −k]q code hg2i is a gene alised Reed-Solomon code. P oo . Le cjbe de ined by g2(X) = 1 2q+ +1 Y i=1 2q− (X−αi) = 2 +2 X j=0 cjXj. 9 Obse e ha k=q−2 −1. As in Theo em 3, we look o polynomials ha(X)which allow us o apply Lemma 1. Fo a∈ {0, . . . , k −1}, le ha(X) = 1 2q X i=1 2 +2 X j=0 cjα(i+1 2q)(j+a)X1 2q+1−i+ 2 +2 X j=0 cjβ. Obse e ha , o all i∈ {1 2q+ 1,...,1 2q+ + 1}, 2 +2 X j=0 cjαij = 0, since g1(αi)=0 . Thus, ha(X) has no e ms o deg ee X1 2q+1−i o i∈ {0, . . . , + 1} . Hence, he deg ee o hais a mos 1 2q+ 1 −( + 2) = 1 2(k−1). We ha e ha ha(αs) = 1 2q X i=1 2 +2 X j=0 cjα(i+1 2q)(j+a−s)+ 2 +2 X j=0 cjβ. and so ha(αs)q= 1 2q X i=1 2 +2 X j=0 cjα(−i+1 2q+1)(j+a−s)+ 2 +2 X j=0 cjβq. Since, β+βq= 1, i ollows ha ha(αs) + ha(αs)q= 2 +2 X j=0 q X i=0 cjαi(j+a−s). Since Pq i=0 αij = 0 unless j= 0, in which case i is one, ha(αs) + ha(αs)q=cs−a. Lemma 2 implies ha hg1iis a gene alised Reed-Solomon code. Finally, we deal wi h he case kis e en and qis odd, which is he cons acyclic code hg3i. Theo em 6. I k is e en and q is odd hen he [q+ 1, k, q + 2 −k]q code hg3i is a gene alised Reed-Solomon code.