On the lattice of cyclic codes over finite chain rings
In this paper, R is a finite chain ring of invariants (q, s), and ℓ is a positive integer fulfilling gcd(ℓ, q) = 1. In the language of q-cyclotomic cosets modulo ℓ, the cyclic codes over R of length ℓ are uniquely decomposed into a direct sum of trace-representable cyclic codes over R and the lattic...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2019
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188436 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On the lattice of cyclic codes over finite chain rings / A. Fotue-Tabue, C. Mouaha // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 252–268. — Бібліогр.: 15 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188436 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1884362023-03-02T01:27:25Z On the lattice of cyclic codes over finite chain rings Fotue-Tabue, A. Mouaha, C. In this paper, R is a finite chain ring of invariants (q, s), and ℓ is a positive integer fulfilling gcd(ℓ, q) = 1. In the language of q-cyclotomic cosets modulo ℓ, the cyclic codes over R of length ℓ are uniquely decomposed into a direct sum of trace-representable cyclic codes over R and the lattice of cyclic codes over R of length ℓ is investigated. 2019 Article On the lattice of cyclic codes over finite chain rings / A. Fotue-Tabue, C. Mouaha // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 252–268. — Бібліогр.: 15 назв. — англ. 1726-3255 2010 MSC: 13B05, 94B05, 94B15, 03G10, 16P10. http://dspace.nbuv.gov.ua/handle/123456789/188436 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper, R is a finite chain ring of invariants (q, s), and ℓ is a positive integer fulfilling gcd(ℓ, q) = 1. In the language of q-cyclotomic cosets modulo ℓ, the cyclic codes over R of length ℓ are uniquely decomposed into a direct sum of trace-representable cyclic codes over R and the lattice of cyclic codes over R of length ℓ is investigated. |
| format |
Article |
| author |
Fotue-Tabue, A. Mouaha, C. |
| spellingShingle |
Fotue-Tabue, A. Mouaha, C. On the lattice of cyclic codes over finite chain rings Algebra and Discrete Mathematics |
| author_facet |
Fotue-Tabue, A. Mouaha, C. |
| author_sort |
Fotue-Tabue, A. |
| title |
On the lattice of cyclic codes over finite chain rings |
| title_short |
On the lattice of cyclic codes over finite chain rings |
| title_full |
On the lattice of cyclic codes over finite chain rings |
| title_fullStr |
On the lattice of cyclic codes over finite chain rings |
| title_full_unstemmed |
On the lattice of cyclic codes over finite chain rings |
| title_sort |
on the lattice of cyclic codes over finite chain rings |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2019 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188436 |
| citation_txt |
On the lattice of cyclic codes over finite chain rings / A. Fotue-Tabue, C. Mouaha // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 252–268. — Бібліогр.: 15 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT fotuetabuea onthelatticeofcycliccodesoverfinitechainrings AT mouahac onthelatticeofcycliccodesoverfinitechainrings |
| first_indexed |
2025-07-16T10:28:28Z |
| last_indexed |
2025-07-16T10:28:28Z |
| _version_ |
1837799004835938304 |
| fulltext |
“adm-n2” — 2019/7/14 — 21:27 — page 252 — #102
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 27 (2019). Number 2, pp. 252–268
c© Journal “Algebra and Discrete Mathematics”
On the lattice of cyclic codes
over finite chain rings
Alexandre Fotue-Tabue and Christophe Mouaha
Communicated by V. A. Artamonov
Abstract. In this paper, R is a finite chain ring of invariants
(q, s), and ℓ is a positive integer fulfilling gcd(ℓ, q) = 1. In the
language of q-cyclotomic cosets modulo ℓ, the cyclic codes over R
of length ℓ are uniquely decomposed into a direct sum of trace-
representable cyclic codes over R and the lattice of cyclic codes over
R of length ℓ is investigated.
Introduction
Research on linear codes over chain rings can be found in [8,13] and
cyclic codes were among the first codes practically used and they play a
very significant role in coding theory. For instance, cyclic codes can be
efficiently encoded using shift registers. Many important codes such as the
Golay codes, Hamming codes and BCH codes can be represented as cyclic
codes. Cyclic codes have been studied for decades and a lot of progress
has been made (see [15]).
Throughout this paper, R is a finite chain ring of invariants (q, s), and
ℓ is a positive integer such that gcd(q, ℓ) = 1. An R-linear code of length
ℓ is an R-submodule of Rℓ. An R-linear code C of length ℓ is cyclic if
the shift (cℓ−1, c0, . . . , cℓ−2) of each codeword (c0, c1, . . . , cℓ−1) in C, also
belongs to C. Unless otherwise specified, all cyclic codes are assumed to
2010 MSC: 13B05, 94B05, 94B15, 03G10, 16P10.
Key words and phrases: finite chain rings, cyclotomic cosets, linear code, cyclic
code, trace map.
“adm-n2” — 2019/7/14 — 21:27 — page 253 — #103
A. Fotue-Tabue, C. Mouaha 253
be linear. As usual, any cyclic code C over R of length ℓ is identified to
an ideal of R[X]/〈Xℓ − 1〉, via the R-module isomorphism
Ψ : Rℓ → R[X]/〈Xℓ − 1〉
(c0, . . . , cℓ−1) 7→
ℓ−1
∑
j=0
cjX
j + 〈Xℓ − 1〉
(1)
where 〈Xℓ − 1〉 is the ideal of R[X] generated by Xℓ − 1. The ideal
Ψ(C) is called the polynomial representation of C, and this polynomial
representation was used in [3, 5, 10, 13, 14] for studying the algebraic
structure of cyclic codes over finite chain rings. Three other general
approaches to the design and analysis of cyclic codes are based on generator
matrices, generator polynomials and idempotents. These approaches have
their advantages and disadvantages in dealing with cyclic codes. The
objectives of this paper are to introduce the cyclotomic approach to the
study of cyclic codes.
The paper is organized as follows. In Section 1, we collect the basic
results needed on finite chain rings as well as the characterization of their
Galois extension. Section 2 discusses the notions of the type of any linear
code over a finite chain ring and studies Galois-invariant linear codes. In
Section 3, we explore the lattice of cyclotomic cosets modulo ℓ in order to
obtain new properties of them. In Section 4, we show that any cyclic code
can be uniquely decomposed as a direct sum of trace-representable cyclic
codes.
1. Background on finite chain rings
In the rest of this paper, R is a finite local ring with maximal ideal
J(R) and R× denotes the group of units of R.
Definition 1. A finite local ring R is a chain ring of invariants (q, s), if
R is a principal ideal ring such that q is the cardinality of the residue field
of R, and s is the nilpotency index of J(R).
In the rest of this paper, R is a finite chain ring of invariants (q, s), the
residue field of R is Fq and θ is a generator of J(R). The ring epimorphism
π : R→ Fq,
c 7→ c+ θR,
“adm-n2” — 2019/7/14 — 21:27 — page 254 — #104
254 On the lattice of cyclic codes over finite rings
naturally extends toR[X], of the following way: π acts on all the coefficients
of any polynomial over R. Obviously, the cardinality of R× is qs−1(q−1). It
follows thatR× ≃ Γ(R)\{0R}×(1R+J(R)) with Γ(R) = {a ∈ R : aq = a}
and Γ(R) \ {0R} is a cyclic subgroup of R× of order q − 1. The set Γ(R)
is called the Teichmüller set of R.
We say that the ring S is an extension of R, and we denote it by S|R,
if R a subring of S and 1R = 1S . We denote by rankR(S), the rank of
R-module S. Let f be a monic polynomial over R[X] of degree m, and
〈 f 〉 is an ideal of R[X] generated by f . We say that f is basic irreducible
(resp. basic primitive) if π(f) is irreducible over Fq (resp. primitive).
Definition 2. The ring S is the Galois extension of degree m of R if
S ≃ R[α], (as R-algebras) where α is a root of a monic basic primitive
polynomial over R of degree m.
Remark 1. Let S be the Galois extension of degree m of R. Let ξ be a
generator of Γ(S) \ {0S}. Then S is also a finite chain ring of invariants
(qm, s) and S = R[ξ].
We denote by AutR(S), the group of all ring automorphisms of S
which fix the elements of R.
Proposition 1 ([4], Chap. III; Proposition 2.1(1)). The ring S is the
Galois extension of degree m of R if and only if
R = {a ∈ S : σ(a) = a for all σ ∈ AutR(S)}
and J(S) = θS.
For instance, for nonnegative integers p, n, s and p prime, the Galois
extension of Zps of degree n, is the Galois ring GR(ps, n) ≃ Zps [X]/〈 f 〉,
where 〈 f 〉 is the ideal generated by a monic basic irreducible polynomial
f over Zps of degree n.
Proposition 2 ([12], Theorem XV.10). Let S be the Galois extension of
degree m of R. Let ξ be a generator of Γ(S) \ {0S}. Then
1) S is a free R-module and {1, ξ, . . . , ξm−1} is a free R-basis of S;
2) AutR(S) is a cyclic group of order m, and a generator of AutR(S)
is given by σ : ξ 7→ ξq.
Definition 3. Let S be the Galois extension of degree m of R. Let σ be
a generator of AutR(S). The map TrSR :=
∑m−1
i=0 σi, is called the trace
map of S|R.
“adm-n2” — 2019/7/14 — 21:27 — page 255 — #105
A. Fotue-Tabue, C. Mouaha 255
Proposition 3 ([4], Chap. III; Corollary 2.2). Let S|R be the Galois
extension of finite chain rings. Then the trace map TrSR : S → R is an
epimorphism of R-modules.
Proposition 4. Let S be the Galois extension of degree m of R. Then for
all positive integer z, for all generator ξ of Γ(S) \ {0R}, the ring R[ξzq]
is the Galois extension of R of degree mz, and
mz := min{i ∈ N \ {0} : zqi ≡ 1 mod (qm − 1)}.
Proof. We set f := (X − ξzq)(X − ξzq
2
) · · · (X − ξzq
mz
). Since S is the
Galois extension de R, we deduce by Proposition 1, that f ∈ R[X] and
π(f) is irreducible. Hence f is a basic irreducible polynomial over R and
the degree of f is mz. It follows that R[ξzq] is the Galois extension of R
of degree mz, because by Definition 2, ξzq is a root of a basic irreducible
polynomial over R of degree of mz.
2. Linear codes over finite chain rings
The ring epimorphism π : R→ Fq naturally extends to Rℓ of the follow-
ing way: π(c) := (π(c0), π(c1), . . . , π(cℓ−1)), for all c := (c0, c1, . . . , cℓ−1)
in Rℓ. Recall that an R-linear code of length ℓ is an R-submodule of
the free R-moduleRℓ. We say that an R-linear code is free if it is free as
R-module.
2.1. Type and minimum Hamming weight of a linear code
A k× ℓ-matrix G over R, is called a generator matrix for C if the rows
of G span C and none of them can be written as an R-linear combination
of other rows of G. We say that G is a generator matrix in standard form
if
G =
Ik0 G0,1 G0,2 . . . G0,s−1 G0,s
0 θIk1 θG1,2 . . . θG1,s−1 θG1,s
. . . . . . . . . . . . . . . . . .
0 0 0 . . . θs−1Iks−1
θs−1Gs−1,s
U, (2)
where U is a suitable permutation matrix. The s-tuple (k0, k1, . . . , ks−1)
is called type of G and rank(G) = k0 + k1 + · · ·+ ks−1 is the rank of G.
Proposition 5 ([13], Proposition 3.2, Theorem 3.5). Each R-linear code
C admits a generator matrix G standard form. Moreover, the type is the
same for any generator matrix in standard form for C.
“adm-n2” — 2019/7/14 — 21:27 — page 256 — #106
256 On the lattice of cyclic codes over finite rings
Let C be an R-linear code and G be a generator matrix in standard
form. The rows of G form an R-basis for C, so-called standard R-basis
for C. So the type and the rank are the invariants of C, and henceforth
we have the following definition.
Definition 4. Let C be an R-linear code.
1) The type of C is the type of a generator matrix of C in standard
form.
2) The rank of C, denoted rankR(C), is the rank of a generator matrix
of C in standard form.
Obviously, any R-linear code C of length ℓ of type (k0, k1, . . . , ks−1)
is free if and only if the rank of C is k0, and k1 = k2 = · · · = ks−1 = 0.
It defines the scalar product on Rℓ by: a · bT :=
∑ℓ−1
i=0 aibi, where bT
is the transpose of b. Let C be an R-linear code of length ℓ. The dual
code of C, denoted C⊥, is an R-linear code of length ℓ, is defined by:
C⊥ := {a ∈ Rℓ : a · bT = 0Rfor all b ∈ C}. A generator matrix of C⊥,
is called parity-check matrix of C. We recall that an R-linear code C is
self-orthogonal if C ⊆ C⊥. An R-linear code C is self-dual if C = C⊥.
Proposition 6 ([8], Theorem 3.1). Let C and C ′ be R-linear codes of
length ℓ. Then (C + C ′)⊥ = C⊥ ∩ C ′⊥, (C ∩ C ′)⊥ = C⊥ + C ′⊥, and
(C⊥)⊥ = C.
Proposition 7 ([13], Theorem 3.10). Let C be an R-linear code of length ℓ,
of type (k0, k1, . . . , ks−1). Then
1) the type of C⊥ is (ℓ−k, ks−1, . . . , k1), where k := k0+k1+ · · ·+ks−1.
2) |C| = q
∑s−1
t=0
(s−t)kt , where |C| denotes the number of elements of C.
Definition 5. Let C be an R-linear code of rank k.
1) The R-linear subcode Soc(C) := {c ∈ C : θc = 0} of C is called the
socle of C.
2) The residue code of C is the Fq-linear code π(C) := {π(c) : c ∈ C}.
Remark 2. Let C be an R-linear code with generator matrix G, as in (2).
Then a generator matrix of Soc(C) is
θs−1
Ik0 G0,1 G0,2 . . . G0,s−1 G0,s
0 Ik1 G1,2 . . . G1,s−1 G1,s
. . . . . . . . . . . . . . . . . .
0 0 0 . . . Iks−1
Gs−1,s
U.
Let x ∈ Rℓ and C be an R-linear code of length ℓ. The Hamming weight
of x is the number of non-zero coordinates in x. It is denoted by wtH(x).
“adm-n2” — 2019/7/14 — 21:27 — page 257 — #107
A. Fotue-Tabue, C. Mouaha 257
The minimum Hamming weight of C is wtH(C) := min{wtH(x) : x ∈
C \ {0}}.
Proposition 8 ([9], Theorem 3.3). Let C be a free R-linear code of length ℓ
and D be an R-linear subcode of D such that rankR(C) = rankR(D). Then
wtH(C) = wtH(D) = wtH(Soc(D))
and wtH(C) = wtH(π(C)).
2.2. Galois closure of a linear code over a finite chain ring
Let S be a Galois extension of R and σ be a generator of AutR(S).
Let B be an S-linear code of length ℓ Then σ(B) := {(σ(c0), . . . , σ(cℓ−1)):
(c0, . . . , cℓ−1) ∈ B} is also an S-linear code of length ℓ. We say that the
S-linear code B is called Galois invariant if σ(B) = B. The restriction of
B to R, is an R-linear code ResR(B) := B ∩Rℓ, and the trace code of B
to R, is the R-linear code
TrSR(B) := {(TrSR(c0), . . . ,Tr
S
R(cℓ−1)) : (c0, . . . , cℓ−1) ∈ B}.
It is clear that TrSR(σ(B)) = TrSR(B). The extension code of an R-linear
code C to S, is the S-linear code ExtS(C), formed by taking all combi-
nations of codewords of C. The following theorem generalizes Delsarte’s
celebrated result (see [15, Chap. 7, § 8. Theorem 11]).
Theorem 1 ([11], Theorem 3). Let B be an S-linear code then TrSR(B
⊥) =
ResR(B)⊥, where B⊥ is the dual to B with respect to the usual scalar
product, and ResR(B)⊥ is the dual of ResR(B) in Rℓ.
Definition 6. Let B be an S-linear code. The Galois closure of B is the
smallest Galois invariant S-linear code Cl(B) containing B.
Proposition 9. Let B be an S-linear code. Then Cl(B) =
∑m−1
i=0 σi(B)
and TrSR(B) = TrSR(Cl(B)).
Proof. We haveB ⊆ Cl(B) andσ(Cl(B)) = Cl(B), by Definition 6 ofCl(B).
So σi(B) ⊆ Cl(B), for all i ∈ {0, 1, . . . ,m − 1}. Hence
∑m−1
i=0 σi(B) ⊆
Cl(B). Since σ(
∑m−1
i=0 σi(B)) =
∑m−1
i=0 σi(B) and B ⊆
∑m−1
i=0 σi(B), as
Cl(B) is the smallest S-linear code containing B, which is Galois invariant,
it follows Cl(B) ⊆
∑m−1
i=0 σi(B). Hence Cl(B) =
∑m−1
i=0 σi(B). Thanks to
[11, Proposition 1.], TrSR(Cl(B)) = TrSR(B).
The following theorem summarizes the obtained results in [11].
“adm-n2” — 2019/7/14 — 21:27 — page 258 — #108
258 On the lattice of cyclic codes over finite rings
Theorem 2. An S-linear code B is Galois invariant if and only if
TrSR(B) = ResR(B).
3. Cyclotomic partitions
Consider Zℓ, the ring of integers modulo ℓ and Σℓ := {0, 1, . . . , ℓ− 1}
the underlying set of Zℓ. Let A be a subset of Σℓ. The set of multiples
of u in A is uA := {uz (mod ℓ) : z ∈ A}. The q-closure of A modulo ℓ is
∁q(A) := ∪
i∈N
qiA. We see that ∁q(∅) = ∅.
Definition 7. Let z ∈ Σℓ. The q-cyclotomic coset modulo ℓ, containing
z, denoted ∁q(z), is the q-closure of {z}.
Denote by ℜℓ(q) the set of q-closure subsets of Σℓ, and by 2Σℓ the
set of subsets of Σℓ. Obviously, the q-cyclotomic cosets modulo ℓ, form a
partition of Σℓ. Let Σℓ(q) be a set of representatives of each q-cyclotomic
cosets modulo ℓ.
Proposition 10 ([1], Proposition 5.2). We have
|Σℓ(q)| =
∑
d|ℓ
φ(d)
ordd(q)
,
where
φ(d) := |{j ∈ Σd : gcd(j, d) = 1}|
and
ordd(q) := min{i ∈ N \ {0} : qi ≡ 1 (mod d)}.
We introduce the binary and unary operations on Σℓ. These operations
are necessary in the following section, for the construction of cyclic codes.
Definition 8. Let z ∈ Σℓ and A,B be two subsets of Σℓ.
1) The opposite of A is −A := {ℓ− z : z ∈ A}.
2) The complementary of A is A := {z ∈ Σℓ : z 6∈ A}.
3) The dual of A is A⋄ := −A.
Let L be a nonempty set. We recall that the quintuple 〈L;∨,∧; 0, 1〉 is
a bounded lattice if the operations ∨ and ∧ are commutative, associative,
idempotent and satisfy the following identities x = x∨(x∧x),x = x∧(x∨x),
x ∧ 0 = 0 and x ∨ 1 = 1.
Moreover, a lattice 〈L;∨,∧〉 is distributive if for all x, y, z ∈ L, (x∨y)∧
z = (x∧ z)∨ (y ∧ z), and a lattice 〈L;∨,∧〉 is modular if for all x, y, z ∈ L,
“adm-n2” — 2019/7/14 — 21:27 — page 259 — #109
A. Fotue-Tabue, C. Mouaha 259
x∧ (y∨ (x∨ z)) = (x∧ z)∨ (y∧ z). A more general and detailed treatment
of the topic can be found in textbooks on Lattices such as [7].
Example 1. The lattice 〈2E;∪,∩;∅,E〉 is distributive and bounded,
where 2E is the power set of a set E. The lattice 〈Lℓ(R);+,∩; {0}, R
ℓ〉
is modular and bounded, where Lℓ(R) is the set of all R-linear codes of
length ℓ.
The relationships among these operations, are given in the following:
Proposition 11. The lattice 〈 ℜℓ(q);∪,∩;∅,Σℓ(q) 〉 is bounded and dis-
tributive. Moreover, the map
∁q : 2
Σℓ → ℜℓ(q)
A 7→
⋃
i∈N
qiA
is a lattices epimorphism with ∁q(−A) = −∁q(A), ∁q(A) = ∁q(A), and
A ⊆ B implies ∁q(A) ⊆ ∁q(B).
Definition 9. The (s + 1)-tuple (A0,A1, . . . ,As) is an (q, s)-partition
cyclotomic modulo ℓ, if there exists a unique map λ : Σℓ(q) → {0, 1, . . . , s},
such that At = ∁q(λ
−1({t})), for all 0 6 t 6 s.
Denote by ℜℓ(q, s) the set of (q, s)-partition cyclotomic modulo ℓ, and
notes that
ℜℓ(q, s) := {(A0,A1, . . . ,As) : (∃λ ∈ {0, 1, . . . , s}Σℓ(q))(At = λ−1({t}))}.
By Definition 9, one check that |ℜℓ(q, s)| = (s+ 1)|Σℓ(q)|.
Example 2. The 3-cyclotomic cosets modulo 20 are ∁3({0}) = {0},
∁3({5}) = {5; 15}, ∁3({10}) = {10}, ∁3({1}) = {1; 3; 9; 7},
∁3({2}) = {2; 6; 18; 14}, ∁3({4}) = {4; 12; 16; 8},
∁3({11}) = {11; 13; 19; 17}.
So Σ20(3) = {0; 1; 2; 4; 5; 10; 11} and ∁3({−z}) = ∁3({z}), for all z ∈
{0; 2; 4; 5; 10}. We have A := ∁3({0; 1; 2; . . . ; 10}) = ∁3({0; 1; 2; 4; 5; 10}),
−A = ∁3({2; 4; 5; 10; 11}).
“adm-n2” — 2019/7/14 — 21:27 — page 260 — #110
260 On the lattice of cyclic codes over finite rings
4. Trace-representable cyclic codes
Let S be a Galois extension of R such that |Γ(S)| > ℓ and ξ be a
generator of Γ(S) \ {0}. Let η := ξ
qm−1
ℓ be an element in Γ(S) such
that ℓ is the multiplicative order of η. A cyclic cyclic code C over R is
trace-representable if there is a free R-linear code D such that C = θtD.
In this section, we give the trace representation of free cyclic codes over
R of length ℓ.
4.1. Cyclic polynomial codes over finite chain rings
Let A := {i1, i2, . . . , ik} be a subset of Σℓ and
P(S; A) := {a1x
i1 + a2x
i2 + · · ·+ akx
ik : (a1, a2 . . . , ak) ∈ Sk}
be an S-submodule of the free S-moduleS[X]. The evaluation
evη : P(S; A) → Sℓ
f 7→ (f(1), f(η), . . . , f(ηℓ−1)),
is an S-modules monomorphism.
We see that if A := {0, 1, . . . , k − 1} then for any ℓth-primitive root of
unity η in Γ(S), the S-linear code evη(P(S; A)) is a cyclic Reed-Solomon
code. For this reason, we define cyclic polynomial codes which is a family
of codes over large finite chain rings as follows.
Definition 10. Let A be a subset of Σℓ. The cyclic polynomial code over S
with defining set A, denoted Lη(S; A), is the free S-module evη(P(S; A)).
For every subset set A of Σℓ, and for all positive integer u such that
gcd(u, ℓ) = 1, we have Lηu(S; A) = Lη(S;uA) and
WA :=
1 ηi1 . . . η(ℓ−1)i1
...
...
...
1 ηik . . . η(ℓ−1)ik
(3)
is a generator matrix for Lη(S; A). Note that Lη(S;∅) = {0}, Lη(S; Σℓ) =
Sℓ, and Lη(S; {0}) = S · 1, where 1 := (1, 1, . . . , 1).
Proposition 12. Let A be a subset of Σℓ. Then Lη(S; A) is cyclic.
Proof. Consider the codeword ca = (1, ηa, . . . , ηa(ℓ−1)). Then the shift of
ca is η−aca. Since Lη(S; A) is S-linear, we have η−aca ∈ Lη(S; A). Hence
Lη(S; A) is cyclic.
“adm-n2” — 2019/7/14 — 21:27 — page 261 — #111
A. Fotue-Tabue, C. Mouaha 261
Proposition 13. Let A,B be two subsets of Σℓ. The following assertions
are satisfied:
1) Lη(S; A)
⊥ = Lη(S; A
⋄);
2) Lη(S; A∪B) = Lη(S; A)+Lη(S; B) and Lη(S; A∩B) = Lη(S; A)∩
Lη(S; B).
Proof. Let A,B be subsets of Σℓ.
1) An S-basis of Lη(S; A
⋄) is {ca : − a ∈ A} where ca := (1, η−a, . . . ,
η−a(ℓ−1)) ∈ Lη(S; A
⋄). Then for all b ∈ A, cb := (1, ηb, . . . , ηb(ℓ−1)) ∈
Lη(S; A), we have cbc
T
a =
∑ℓ−1
j=0 η
(b−a)j , where cTa is the transpose
of ca. It is easy to check that
∑ℓ−1
j=0 η
ij = 0, when i 6≡ 0(mod ℓ). Since
0 < b− a < ℓ, we have cbc
T
a = 0. So Lη(S; A
⋄) ⊆ Lη(S; A)
⊥. Comparison
of cardinality yields Lη(S; A)
⊥ = Lη(S; A
⋄).
2) We have Lη(S; A) ⊆ Lη(S; A∪B), Lη(S; B) ⊆ Lη(S; A∪B). There-
fore
Lη(S; A) + Lη(S; B) ⊆ Lη(S; A ∪ B)
and
Lη(S; A) ∩ Lη(S; B) ⊆ Lη(S; A ∪ B).
Since an S-basis of Lη(S; A)+Lη(S; B) is {ca : a ∈ A∪ (B \A)} and an S-
basis of Lη(S; A)∩Lη(S; B) is {ca : a ∈ A∩B}. We have the equalities.
We set Lℓ(S) to be the set of all cyclic polynomial codes of length ℓ
over S. Then the quintuple 〈Lℓ(S); +, ∩; {0}, S
ℓ〉 is a lattice and the map
Lη(S;−) : 2Σℓ → Lℓ(S),
A 7→ Lη(S; A),
is a lattice isomorphism. The following result extends [2, Theorem 5] to
finite chain rings.
Definition 11. A subset I of Σℓ is an interval of length δ if there exists
(a, u) ∈ Σℓ × Σℓ such that gcd(u, ℓ) = 1 and
I = {ua, u(a+ 1), . . . , u(a+ δ − 1)}.
Theorem 3. If A⋄ contains an interval of length δ then
wtH(Lη(S; A)) = wtH(Lπ(η)(Fqm ; A)) > δ + 1.
Proof. We have π(Lη(S; A)) = Lπ(η)(Fqm ; A). From Proposition 8,
wtH(Lη(S; A)) = wtH(Lπ(η)(Fqm ; A)).
“adm-n2” — 2019/7/14 — 21:27 — page 262 — #112
262 On the lattice of cyclic codes over finite rings
From [2, Theorem 6], we have wtH(Lπ(η)(Fqm ; A)) > δ + 1.
Proposition 14. Let S be a finite chain ring of invariants (2n, s) and
ℓ := 2sn − 1, A := {1, 2, . . . , d− 1} where d := 2sn−1. Then Lη(S; A
⋄) is
MDS and self-orthogonal.
Proof. We have A is an interval of length d − 1 and A⋄ := A ∪ {0}. So
We have Lη(S; A)
⊥ = Lη(S; A
⋄) = Lη(S; A) ⊕ S · 1. Thus Lη(S; A
⋄) is
self-orthogonal and A⋄ is also an interval of length d. By Theorem 3, we
see that Lη(S; A
⋄) is MDS.
4.2. Free cyclic codes over finite chain rings
We consider the trace-evaluation TrSR ◦ evη : Pη(S; A) → Rℓ defined
as follows:
TrSR ◦ evη(λX
a) := (TrSR(λ),Tr
S
R(λη
a), . . . ,TrSR(λη
a(ℓ−1))),
for all a ∈ A and for all λ ∈ R. In the sequel, we write: Cη(R; A) :=
TrSR(Lη(S; A)), and Cη(R; A) is a free cyclic code over R of length ℓ. Let
Cℓ(R) := {Cη(R; A) : A ⊆ Σℓ} be the set of all free cyclic linear codes
over R of length ℓ.
Proposition 15. Let A,B be two subsets of Σℓ. Then
1) Lη(S; ∁q(A)) is the Galois closure of Lη(S; A) and Cη(R; A) =
Cη(R; ∁q(A));
2) rankS(Lη(S; ∁q(A))) = |∁q(A)|;
3) Cη(R; A)
⊥ = Cη(R; A
⋄);
4) Cη(R; A∪B) = Cη(R; A)+Cη(R; B) andCη(R; A∩B) = Cη(R; A)∩
Cη(R; B).
Proof. Let A,B be two subsets of Σℓ.
1) On the one hand, it is clear that σ(Lη(S; A)) = Lη(S; qA). So by
Proposition 9, we have
Cl(Lη(S; A)) =
m−1
∑
i=0
Lη(S; q
iA) = Lη
(
S;
m−1
⋃
i=0
qiA
)
.
Since ∁q(A) =
⋃m−1
i=0 qiA, we obtain Cl(Lη(S; A)) = Lη(S; ∁q(A)) and
on the other hand, from Proposition 9, Cη(R; A) = Tr(Lη(S; A)) =
Tr(Lη(S; ∁q(A))) = Cη(R; ∁q(A)).
2) Theorem 2 yields
Cη(R; A) = Tr(Lη(S; ∁q(A))) = ResR(Lη(S; ∁q(A))).
“adm-n2” — 2019/7/14 — 21:27 — page 263 — #113
A. Fotue-Tabue, C. Mouaha 263
So rankR(Cη(R; A)) = rankS(Lη(S; ∁q(A))) = |∁q(A)|.
3) We have
Cη(R; A)
⊥ = ResR(Lη(S; ∁q(A))
⊥), by Theorem 2;
= ResR(Lη(S; ∁q(A)
⋄)), by Proposition 13;
= Cη(R; A
⋄).
4) By Proposition 13,
Cη(R; A ∪ B) = Tr(Lη(S; A ∪ B)) = Tr(Lη(S; A)) + Tr(Lη(S; B)).
Since ∁q(A)∩∁q(B) = ∅, we have Tr(Lη(S; A))∩Tr(Lη(S; B)) = {0}.
Theorem 4. Let ℓ, q be nonnegative integers such that q is a prime power
and gcd(q, ℓ) = 1. Then the lattices
〈Cℓ(R); +,∩; {0}, R
ℓ 〉 and 〈 ℜℓ(q);∪,∩;∅,Σℓ(q) 〉
are isomorphic.
Proof. It is obvious that prove that the map Cη(R ;−) : ℜℓ(q) → Cℓ(R),
is a bijective. From Proposition 15, this map is a lattice isomorphism.
Corollary 1. Let ℓ, q be nonnegative integers such that q is a prime power
and gcd(q, ℓ) = 1. Then the lattices
〈Cy(Fq, ℓ); +,∩; {0},F
ℓ
q〉 and 〈Cℓ(R); +,∩; {0}, R
ℓ 〉
are isomorphic.
Proof. For all finite chain rings R1 and R2 of invariants (q, s1) and
(q, s2) respectively. By Theorem 4, lattices 〈Cℓ(R1);+,∩; {0}, R
ℓ
1 〉 and
〈Cℓ(R2);+,∩; {0}, R
ℓ
2 〉 are isomorphic. Since Cℓ(Fq) = Cy(Fq, ℓ), we
have the result.
Lemma 1. Let z ∈ Σℓ. Set mz := |∁q(z)| and ζ := η−z. Then the map
ψz : R[ξ
z] → Cη(R; {z})
a 7→ TrSR(evη(aX
z))
is an R-module isomorphism. Further ψz ◦ tζ = τ1 ◦ ψz, where τ1 is the
cyclic shift and tζ(a) = aζ, for all a ∈ R[η].
“adm-n2” — 2019/7/14 — 21:27 — page 264 — #114
264 On the lattice of cyclic codes over finite rings
Proof. It is clear that a ∈ Ker(ψz) if and only if a ∈ R[ξz]⊥Tr ∩ R[ξz],
where duality ⊥Tr is with respect to trace form. As the trace bilinear
form is nondegenerate, we have S = R[ξz]⊥Tr ⊕R[ξz] and Ker(ψz) = {0R}.
Hence ψz is an R-module monomorphism. We remark that, Cη(R; {z}) is
cyclic, if and only if ψz ◦ tζ = τ1 ◦ ψz. Finally, we have S = R[ξ], and by
Proposition 4, the ring R[ξz] is the Galois extension of R of degree mz.
Hence, ψz is an R-module isomorphism.
Definition 12. A non trivial cyclic code over R C is said to be indecom-
posable, if for all R-linear cyclic subcodes C1 and C2 of C, the implication
holds: C = C1 ⊕ C2, then C1 = {0} or C2 = {0}.
Proposition 16. The indecomposable cyclic linear codes over R are pre-
cisely θtCη(R; {z})s, where t ∈ {0, 1, . . . , s− 1} and z ∈ Σℓ(q).
Proof. By Lemma 1, the free cyclic linear codes over R of length ℓ
are Cη(R; {z}))s where z ∈ {0, 1, . . . , ℓ − 1} and all the cyclic and R-
linear subcodes of each cyclic code over R, are indecomposable. Let C
be an indecomposable, cyclic and R-linear code and I(C) be the small-
est free, cyclic and R-linear code containing C. Then A := Soc(C) is
also an indecomposable, cyclic and R-linear code and A ⊂ I(C) with
rankR(A) = rankR(I(C)). Assume that |A| > 1. Then Cη(R; A) =
Cη(R; A1) ⊕ Cη(R; A2) where A1 ∩ A2 = ∅, A1 6= ∅ and A2 6= ∅.
We have C ∩ Cη(R; A1) 6= {0} and C ∩ Cη(R; A2) 6= {0}. Therefore
C = (C ∩Cη(R; A1))⊕ (C ∩Cη(R; A2)). It is impossible, because C be
an indecomposable. So |A| = 1. Now, C ⊆ Cη(R; {z}), it follows that
C = θtCη(R; {z}), for some t ∈ {0, 1, . . . , s− 1}.
5. Sum and intersection of cyclic codes
Consider the map
Cℓ,R : ℜℓ(q, s) → Cy(R, ℓ)
(A0,A1, . . . ,As) 7→
s−1
⊕
t=0
θtCη(R; At).
(4)
In this section, on the one hand, we show that the map Cℓ,R : ℜℓ(q, s) →
Cy(R, ℓ) is bijective and on the other hand we equip the set ℜℓ(q, s) of bi-
nary operations ⊔ and ⊓ such that Cℓ,R : 〈ℜℓ(q, s);⊔,⊓〉→〈Cy(R, ℓ); +,∩ 〉
is a lattice homomorphism.
The following Lemma gives the number of cyclic codes over finite chain
rings.
“adm-n2” — 2019/7/14 — 21:27 — page 265 — #115
A. Fotue-Tabue, C. Mouaha 265
Lemma 2 ([1], Theorem 5.1). Let R be a finite chain ring of invariants
(q, s). Then the number of cyclic codes over R of length ℓ, is equal to
(s+ 1)|Σℓ(q)|.
Lemma 3 ([7], Corollary 11). A finite lattice is distributive if and only if
it is isomorphic to 〈2E;∪,∩;∅,E〉, where E is a finite set.
Obviously, 〈Cℓ(R);+,∩; {0}, R
ℓ 〉 is an sublattice of 〈Cy(R, ℓ);+,∩;
{0}, Rℓ 〉 and by Theorem 4, 〈Cℓ(R); +,∩; {0}, R
ℓ 〉 is distributive. Thus
Lemmas 2 and 3, give the following fact.
Theorem 5. Let R be a finite chain ring of invariants (q, s) and ℓ be
a nonnegative integer such that gcd(ℓ, q) = 1. Then s 6= 1 if and only if
〈Cy(R, ℓ); +,∩; {0}, Rℓ 〉 is not distributive.
We show that each cyclic code over R can be written as a direct sum
of trace-representable cyclic codes in precisely one way.
Lemma 4. Let R be a finite chain ring of invariants (q, s). Then the
map Cℓ,R : ℜℓ(q, s) → Cy(R, ℓ) is a bijection and the type of Cℓ,R(A)
is (|∁q(A0)|, |∁q(A1)|, . . . , |∁q(As−1)|), for some A := (A0,A1, . . . ,As) ∈
ℜℓ(q, s).
Proof. Let C be a cyclic code over R of length ℓ. From Proposition 15,
we have
Rℓ = Cη(R; Σℓ(q)) =
⊕
z∈Σℓ(q)
Cη(R; {z})
and Cη(R; {z})’s are free, indecomposable, cyclic codes over R.
It follows that C =
⊕
z∈Σℓ(q)
Cz, where Cz = Cη(R; {z}) ∩ C.
By Proposition 16, Cz = θtzCη(R; {z}), where tz ∈ {0, 1, . . . , s}.
Thus
⊕
z∈Σℓ(q)
θtzCη(R; {z}) = Cℓ,R(A0,A1, . . . ,As), where At = {z ∈
Σℓ : tz = t}. Since |ℜℓ(q, s)| = (s+1)|Σℓ(q)|, by Theorem 2, the uniqueness
of A := (A0,A1, . . . ,As) ∈ ℜℓ(q, s) such that C = Cℓ,R(A) is guaran-
teed. Moreover, for all t ∈ {0, 1, . . . , s − 1}, the cyclic code over R
Cη(R; At) is free and rankR(Cη(R; At)) = |∁q(At)|. Since the direct sum
⊕s−1
t=0 θ
t
Cη(R; At) gives the type of Cℓ,R(A), the type of Cℓ,R(A) is
(k0, k1, . . . , ks−1), where kt := |∁q(At)|, for all 0 6 t < s− 1.
Definition 13. Let C be a cyclic code over R of length ℓ. The defining
multiset of C is the (q, s)-partition cyclotomic A modulo ℓ, such that
C = Cℓ,R(A).
“adm-n2” — 2019/7/14 — 21:27 — page 266 — #116
266 On the lattice of cyclic codes over finite rings
Proposition 17. Let
A := (A0,A1, . . . ,As) ∈ ℜℓ(q, s) and t ∈ {0, 1, . . . , s− 1}.
Then
Cℓ,R(A)
⊥ = Cℓ,R(A
⋄̃),
where A⋄̃ := (−As,−As−1, . . . ,−A1,−A0).
Proof. Let A := (A0,A1, . . . ,As) ∈ ℜℓ(q, s). We have
Cℓ,R(A)⊥ ⊇
s−1
⋂
u=0
(θs−uRℓ +Cη(R; A
⋄
u))
and
θs−t
Cη(R;−At) ⊆
s−1
⋂
u=0
(θs−uRℓ +Cη(R; A
⋄
u)),
for all t ∈ {1, 2, . . . , s}. It follows that
Cℓ,R(−As,−As−1, . . . ,−A1,−A0) ⊆ Cℓ,R(A)
⊥.
From Proposition 7 and Theorem 6, Cℓ,R(−As,−As−1, . . . ,−A1,−A0)
and Cℓ,R(A)
⊥ have the same type, we have
Cℓ,R(A)⊥ = Cℓ,R(−As,−As−1, . . . ,−A1,−A0).
Corollary 2. Let A := (A0,A1, . . . ,As) ∈ ℜℓ(q, s). Then Cℓ,R(A) is
self-dual if and only if At = −As−t, for all t ∈ {0, 1 . . . , s}.
Corollary 3. Let R be a finite chain ring of invariants (q, s) and s is an
even integer. Then the following are equivalent.
1) there exists a subset A of Σℓ such that A 6= −A;
2) the nontrivial self-dual cyclic linear codes over R of length ℓ exist.
Proof. Let R be a finite chain ring of invariants (q, s) and s is an even
integer.
1) ⇒ 2). Assume that there exists a subset A of Σℓ such that ∁q(A) 6=
−∁q(A). Set u = s
2 , and B := A ∪ (−A). Consider
C := Cℓ,R(. . . ,∅,Au−1,Au,Au+1,∅, . . . ),
where Au−1 := ∁q(A), Au := ∁q(B) and Au+1 := −Au−1. We have
As−u+1 = −Au+1, Au = −As−u = −Au and At = −As−t = ∅, for
“adm-n2” — 2019/7/14 — 21:27 — page 267 — #117
A. Fotue-Tabue, C. Mouaha 267
all t ∈ {0, 1, . . . , u− 2}. Thanks to Corollary 2, we can affirm that C is
self-dual.
2) ⇒ 1) Now, we assume that C is a self-dual cyclic code over R of
length ℓ and every subset A of Σℓ satisfies A = −A. Set C = Cℓ,R(A0,A1,
A2, . . . ,As). From Corollary 2, At = −As−t, for all t ∈ {0, 1, . . . , s}. Since
−As−t = As−t, we have At = As−t = ∅ for all t ∈ {0, 1 . . . , s} \ { s
2} and
A s
2
= Σℓ(q). Therefore,
C = Cℓ,R(. . . ,∅,Σℓ(q),∅, . . . ) = θ
s
2Rℓ,
which is the trivial self-dual code.
In order to determine the defining multiset of the sum and the inter-
section of cyclic codes over R, we extend the binary operations ∪ and ∩
of ℜℓ(q) to ℜℓ(q, s) as follows:
1) A ⊔ B := (C0,C1, . . . ,Cs), where C0 := A0 ∪ B0 and Ct := (At ∪
Bt) \ (
t−1
∪
u=0
Cu), for all 0 < t 6 s.
2) A ⊓ B := (A⋄̃ ∨ B⋄̃)⋄̃.
for all A := (A0,A1, . . . ,As) and B := (B0,B1, . . . ,Bs) be elements
of ℜℓ(q, s).
Theorem 6. The map (4) is a lattice isomorphism of
〈 ℜℓ(q, s);⊔,⊓;∅,Σℓ(q) 〉 to 〈Cy(R, ℓ); +, ∩; {0}, Rℓ〉,
where ∅ := (∅, . . . ,∅,Σℓ(q)) and Σℓ(q) := (Σℓ(q),∅, . . . ,∅).
Proof. Let A := (A0,A1, . . . ,As) ∈ ℜℓ(q, s), and B := (B0,B1, . . . ,Bs) ∈
ℜℓ(q, s). We have
Cℓ,R(A) +Cℓ,R(B)
=
s−1
∑
t=0
θt(Cη(R; At) +Cη(R; Bt)), by the associativity of +,
= Cη(R; A0 ∪ B0)⊕ θCη(R; (A1 ∪ B1) \ (A0 ∪ B0))
⊕ · · · ⊕ θtCη
(
R; (At ∪ Bt) \
(
t−1
⋃
u=0
(Au ∪ Bu)
)
)
⊕ · · · ⊕ θs−1
Cη
(
R; (As−1 ∪ Bs−1) \
(
s−2
⋃
u=0
(Au ∪ Bu)
)
)
= Cℓ,R(A ⊔ B).
“adm-n2” — 2019/7/14 — 21:27 — page 268 — #118
268 On the lattice of cyclic codes over finite rings
From Propositions 6 and 17, we deduce that Cℓ,R(A)∩Cℓ,R(B) = Cℓ,R(A⊓
B). Finally, by Lemma 4, we have the expected result.
References
[1] A. Batoul, K. Guenda, and T.A. Guelliver, On the self-dual cyclic codes over finite
chain rings, Des. Codes Cryptogr. 70(1): (2014), pp. 347-358.
[2] J. Bierbrauer , The Theory of Cyclic Codes and a Generalization to Additive Codes.
Des.Codes.Cryptogr. 25(2): (2002), pp. 189-206.
[3] A. R. Calderbank and N. J. A. Sloane , Modular and p-adic cyclic codes, Des.
Codes Cryptogr. 6(1): (1995), pp. 21-35.
[4] F. DeMeyer and E. Ingraham, Separable Algebras Over Commutative Rings,
Springer, 1971.
[5] H. Dinh and S. R. López-Permouth, Cyclic and negacyclic codes over finite chain
rings, IEEE Trans. Inform. Theory 50 (8) (2004), pp. 1728-1744.
[6] A. Fotue Tabue and C. Mouaha, A New Approach of Free Cyclic Linear Codes
over Commutative Finite Chain Rings. GJPAM, 9(5), 475-482 (2013).
[7] G. Gratze, Lattices Theory: First Concepts and Distributive Lattices, Dover Publi-
cations, Inc., 2009.
[8] T. Honold and I. Landjev, Linear codes over finite chain rings, Electron. J. Com-
binat., vol. 7, no. 1, (2000), pp. R11.
[9] H. Horimoto and K. Shiromoto, On generalized Hamming weights for codes over
finite chain rings. In: Proceedings of the 14th International Symposium on Applied
Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, Berlin,
Heidelberg, 2001, 141-150.
[10] P. Kanwar and S. R. López-Permouth , Cyclic codes over the interger modulo p
m,
Finite Fields Appl. Vol 3 (1997), pp. 334-352.
[11] E. Martinez-Moro, A. P. Nicolas and F. Rua ,On trace codes and Galois invariance
over finite commutative chain rings, Finite Fields Appl. Vol. 22, (2013), pp. 114-
121.
[12] B. R. McDonald, Finite Rings with Identity, Marcel Dekker, New York, 1974.
[13] G. H. Norton and A. Salagean, On the Structure of Linear and Cyclic Codes over
a Finite Chain Ring, AAECC Vol. 10, (2000), pp. 489-506.
[14] Z. Wan, Cyclic codes over Galois rings, Alg. Colloq., 6 (1999), pp. 291-304.
[15] F. J. McWilliams and N. J. A. Sloane , The Theory of Error-Correcting Codes,
North-Holland Math. Library, vol. 16, North-Holland, Amsterdam, 1977.
Contact information
Alexandre
Fotue-Tabue
Department of Mathematics, Faculty of Science,
University of Yaoundé 1, Cameroon
E-Mail(s): alexfotue@gmail.com
Christophe Mouaha Department of Mathematics, Higher Teachers
Training College, University of Yaoundé 1,
Cameroon
E-Mail(s): cmouaha@yahoo.fr
Received by the editors: 16.03.2017.
|