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.