Double circulant self-dual and LCD codes
over Galois rings ∗
arXiv:1801.06624v1 [cs.IT] 20 Jan 2018

Minjia Shi1,2 , Daitao Huang3 , Lin Sok3 , and Patrick Solé4
1 School

of Mathematical Sciences, Anhui University, Hefei, 230601, China

2 Key

Laboratory of Intelligent Computing & Signal Processing,

Ministry of Education, Anhui University No. 3 Feixi Road,
Hefei Anhui Province 230039, P. R. China;
National Mobile Communications Research Laboratory
Southeast University, 210096, Nanjing, P. R. China;
3
4 CNRS/LAGA,

Anhui University, Hefei, 230601, P. R. China

University of Paris 8, 2 rue de la Liberté, 93 526 Saint-Denis, France

Abstract: This paper investigates the existence, enumeration and asymptotic
performance of self-dual and LCD double circulant codes over Galois rings of characteristic p2 and order p4 with p and odd prime. When p ≡ 3 (mod 4), we give an
algorithm to construct a duality preserving bijective Gray map from such a Galois
ring to Z2p2 . Using random coding, we obtain families of asymptotically good self-dual
and LCD codes over Zp2 , for the metric induced by the standard Fp -valued Gray
maps.
Keywords: double circulant codes, self-dual codes, LCD codes
MSC (2010): Primary 94B65 Secondary 13K05 13.95
This research is supported by National Natural Science Foundation of China (61672036), Technology Foundation for Selected Overseas Chinese Scholar, Ministry of Personnel of China (05015133)
and the Open Research Fund of National Mobile Communications Research Laboratory, Southeast
University (2015D11) and Key projects of support program for outstanding young talents in Colleges
and Universities (gxyqZD2016008).
∗

1

1

Introduction

Double circulant self-dual codes over finite fields have been studied recently in [1].
Double circulant self-dual codes over a commutative ring can only exist if there is a
square root of −1 over that ring [10]. Such a root does not exist over Galois rings
of even characteristic which are not fields, but does exist over Galois rings of odd
characteristic and even extension degree [8, Lemma 3.1, Lemma 3.2]. We study these
codes in the case of Galois rings of characteristic p2 and size p4 , for p an odd prime. A
recent topic related to self-dual codes is LCD codes. They are popular because of their
connections with cybersecurity [2]. We also study LCD double circulant codes over
the same Galois rings. For every such Galois ring we construct a duality preserving
Gray map with image Z2p2 , which maps self-dual (resp. LCD) codes to self-dual (resp.
LCD) codes. Note that self-dual codes over Zp2 , for p an odd prime, have been studied
by many authors [3, 5]. This alphabet Zp2 , in turn can be mapped into Fpp by the Gray
map studied in [9]. For the two families of codes under scrutiny we give a complete
enumeration formula in length 2n when n is coprime with p. This formula relies on
the CRT approach to quasi-cyclic codes over rings [12, 10], and requires to count the
number of solutions of certain algebraic equations over Galois rings and over their
residue fields. From there, building on Artin conjecture in arithmetic progressions
[11], we construct infinitely many odd primes n such that xn − 1 has only three
factors over Fp2 the residue class ring of the Galois ring alphabet. Depending on the
congruence class of n modulo 4, these irreducible factors are all three self-reciprocal,
or consist of x − 1, and one reciprocal pair. When n varies in one of these two families
of primes, we obtain two infinite families of double circulant codes, one self-dual, one
LCD, of length 2n. By expurgated random coding, we derive a lower bound on the
relative Hamming distance of the Fp image of both families. This shows, in particular,
that both families are good.
The material is organized as follows. The next section collects the notions and
notations needed in the forthcoming sections. Section 3 contains the main results
on enumeration and Section 4 the main results on asymptotics. Section 5 displays
some numerical examples. Section 6 concludes the article and points out some open
problems.

2

2

Definitions and notation

2.1

Some rings

Throughout the paper, let p be an odd prime. The ring Zps is the ring of integers
⊥
modulo ps . A linear code of length N over Zp2 is a submodule of ZN
p2 . The dual C and
C ⊥H are understood with respect to the standard inner product and Hermitian inner
product, respectively. A code is self-dual if it is equal to its dual. It is LCD (linear
complementary dual) if it intersects its dual trivially. The Galois ring GR(ps , pms ) of
order pms and characteristic ps is the Galois extension of Zps with degree m. It is a
m
local ring, with maximal ideal (p). The Teichmuller set T = {x ∈ GR(ps , pms )|xp =
x} is a set of representatives of the residue field Fpm = GR(ps , pms )/(p). If r ∈
GR(ps , pms ), let rb denote its image in Fpm by reduction modulo (p). It is known that
GR(ps , pms ) = T ⊕ pT ⊕ · · · ⊕ ps−1 T (base p decomposition of GR(ps , pms )). See [13]
for background and details.

2.2

Double circulant codes
Z

2 [y]

p
, where h(y) is a basic irreducible polynomial over
Denote by R the ring (h(y))
Zp2 with deg(h(x)) = 2. For any ring M, we denote by M ∗ the set of units in M.
Assume that n is an integer with gcd(n, p) = 1, and consider the code C of length
2n over R whose generator matrix has the form of (In , A), where In is the identity
matrix of order n and A is a circulant matrix over R. Note that C can be viewed as
2
a submodule of ( (xR[x]
n −1) ) , with generator (1, a(x)) where the x-expansion of a(x) is
the first row of A.

For all p’s, we know there exists w ∈ R such that w 2 = −1, by [8]. When p ≡ 3
(mod 4), the polynomial y 2 + 1 is irreducible over Fp , hence over Zp2 . We may write
R = Zp2 [y]/(y 2 + 1), and take w = y.

2.3

Gray map

Recall Lagrange’s four-square theorem, also known as Bachet’s conjecture [7].
Lemma 1. Every natural number can be represented as the sum of four integer
squares.

3

We will also need the sum of two squares theorem, and the Diophantus identity
[7].
Lemma 2. An integer greater than one can be written as a sum of two squares if and
only if its prime decomposition contains no prime congruent to 3 (mod 4) raised to
an odd power.
Lemma 3. The product of two sums of two squares is a sum of two squares in
following two different ways.
a2 + b2



c2 + d 2



= (ac − bd)2 + (ad + bc)2

= (ac + bd)2 + (ad − bc)2 .

(1)
(2)

Assume p ≡ 3 (mod 4). By Lemma 1, we define a Gray map from R to Z2p2 as follows:
φ : R → Z2p2
a + by 7→ (ka + sb, ta + rb),
where 3p2 = k 2 + s2 + t2 + r 2 . Then extend it in the obvious way to RN . This Gray
map is bijective, as the next result shows.
!
k t
Theorem 1. The matrix
is nonsingular.
s r
Proof. Suppose that, looking for a contradiction, a linear dependence between the two
rows of the matrix. Let µ, ν be two integers satisfying ν(k, t) = µ(s, r). Substituting
k and s by their values in 3ν 2 p2 we get
3ν 2 p2 = (µ2 + ν 2 )(r 2 + s2 ).
By Diophantus identity (Lemma 3) the RHS is a sum of two squares. This contradicts
Lemma 2, because the integer 3 times a square will always contain 3 to an odd power
in its primary factors decomposition.
Theorem 2. Assume p ≡ 3 (mod 4). For all codes C over R, we have φ(C)⊥ =
φ(C ⊥ ). If C is a self-dual (resp. LCD) code of length N over R, then φ(C) is selfdual (resp. LCD) of length 2N over Zp2 .

4

Proof. For any vector u = (u1 , u2, · · · , uN ), v = (v1 , v2 , · · · , vN ) ∈ RN , where ui =
ai1 + bi1 y, vi = ai2 + bi2 y ∈ R (i = 1, 2, · · · , N). Suppose uv = 0 (mod p2 ), and noting
that p ≡ 3 (mod 4), we have y 2 + 1 = 0 over R. Considering the standard inner
product, we then obtain
N
N
X
X
(ai1 + bi1 y)(ai2 + bi2 y) =
[(ai1 ai2 − bi1 bi2 ) + (ai1 bi2 + ai2 bi1 )y] = 0,
i=1

i=1

which is equivalent to

PN

i=1 (ai1 ai2
P
 N (ai bi
1 2
i=1

− bi1 bi2 ) ≡ 0 (mod p2 ),
+ ai2 bi1 ) ≡ 0

(mod p2 ).

We then naturally obtain
φ(u)φ(v) =
=
≡

N
X

i=1
N
X

i=1
N
X
i=1

φ(ui )φ(vi )
(kai1 + sbi1 , tai1 + wbi1 )(kai2 + sbi2 , tai2 + wbi2 )
[(k 2 + t2 )(ai1 ai2 − bi1 bi2 ) + (ks + tw)(ai1 bi2 + ai2 bi1 )y]

≡ 0 (mod p2 ).
This implies
φ(C ⊥ ) ⊆ φ(C)⊥ ,
and, since φ is a bijection the first statement follows by showing that both sides have
the same size.
The second statement for LCD codes is as in [4, Th. 5.2]. The second statement
for self-dual codes follows by plugging C ⊥ = C in the first statement.
Example: If p = 3, then 3p2 = 27 = 16 + 9 + 1 + 1. The Gray map can be taken
to be a + by 7→ (4a + 3b, a + b).

2.4

Finite fields

If L, K are two finite fields of respective orders prs and pr satisfying K ⊆ L, we
write the trace from L down to K as
rs

r

T rppr (z) = z + z p + · · · + z p
5

r(s−1)

,

where r, s are positive integers.

2.5

Codes over fields and asymptotics

Let p be an odd prime, and denote by Fp the finite field of order p. By a code of
length N over Fp , we shall mean a proper subset of FN
p . This code is linear if it is
a Fp -vector subspace of FN
p . The dimension of a code C, denoted by k, is equal to
its dimension as a vector space. Its (minimum) distance, denoted by d or d(C), is
defined as the minimum Hamming weight of its nonzero elements. The Hamming
weight of x = (x1 , x2 , · · · , xn ) ∈ Fnp , denoted by w(x), is the number of indices i where
xi 6= 0. The three parameters of a code are written compactly as [n, k, d]. We extend
this notation to a possibly nonlinear code C ⊆ Fnp , by letting then k = logp (|C|), and
letting d be the minimum pairwise distance between two nonzero codewords. If C(n)
is a family of codes of parameters [n, kn , dn ], the rate r and relative distance δ are
defined as
kn
r = lim sup ,
n
n→∞
and

dn
.
n
A family of codes is said to be good iff rδ > 0.
δ = lim inf
n→∞

Recall that the q-ary entropy function Hq (·) is defined for 0 < y <

q−1
q

by

Hq (y) = y logq (q − 1) − y logq (y) − (1 − y) logq (1 − y).

3
3.1

Main results
Enumeration in a special case
n−1

Assume that p is a primitive root modulo n with n an odd prime. Then, (p2 ) 2 ≡
1 (mod n), and we have xn −1 = (x−1)g˜2 (x)g̃3 (x) with g˜2 (x), g˜3 (x) monic irreducible
polynomials over Fp2 . By Hensel lifting, since (n, p) = 1, we have xn − 1 = ϑ(x −
1)g2 (x)g3 (x) over R, with g2 (x) ≡ g˜2 (x) (mod p), g3 (x) ≡ g˜3 (x) (mod p) and ϑ ∈ R∗ .
Both g2 (x) and g3 (x) are monic basic irreducible polynomials over R. The following
lemma is taken from [13].

6

Lemma 4. Let R1 = GR(ps , psm ) and h(x) be a monic basic irreducible polynomial of
R1 [x]
is a Galois ring of characteristic
degree l over R1 . Then the residue class ring (h(x))
s
sml
p and cardinality p
and contains R1 as a subring. Thus
R1 [x]
= GR(ps , psml ).
(h(x))
Thus this lemma shows that the alphabet rings Ri for i = 2, 3 of the constitutent
codes defined below are also Galois rings.
3.1.1

n ≡ 1 (mod 4)
n−1

Firstly, if n ≡ 1 (mod 4), since p is primitive modulo n, we can deduce (p2 ) 4 ≡
−1 (mod n). This implies that −1 is in the p2 -cyclotomic coset modulo n. Consequently, we obtain gi∗(x) = gi (x) for i = 2, 3. Note that deg(gi (x)) = n−1
. By the
2
L L
CRT, we have C = C1 C2 C3 , where C1 is a code of length 2 over R and Ci is
for i = 2, 3. Let Ri = (gR[x]
for i = 2, 3. The
a code of length 2 over the ring (gR[x]
i (x))
i (x))
properties of C3 being similar to that of C2 , we only investigate C2 for simplicity’s
sake.
Write C2 = h[1, b]i, where b ∈ R2 . Note that b can be uniquely decomposed in
n−1
base p as b = α + pβ, where α, β ∈ T = {x ∈ R2 | xp
= x}. Define a generalized
2

2

n−1

n−1

n−1

Frobenius map F as F (b) = αp + pβ p , then F 4 (b) = αp 2 + pβ p 2 . The
n−1
n−1
conjugate b of b is F 4 (b). Throughout this paper, we let u = p 2 . With this
notation b = αu + pβ u . We can then define a Hermitian scalar product on R22 , by
the formula x · y = x1 y1 + x2 y2 for x = (x1 , x2 ), y = (y1 , y2 ) ∈ R22 .

From the introduction we know there is w ∈ R such that w 2 = −1. Write w =
2
w1 + pw2 , w1 , w2 ∈ T1 = {x ∈ R | xp = x}. Then w 2 = w12 + 2pw1 w2 = −1, which is
equivalent to w12 = −1, w2 = 0. That is to say, only has two choices for w in R such
√
that w 2 = −1. Let us denote one of this two w ′ s by −1.

Theorem 3. Writing C1 = h[1, a]i, where a ∈ R. Then we have C1 is self-dual over
√
R iff a = ± −1.
√
Proof. C1 is self-dual iff 1 + aa = 0, which implies a = ± −1.

The following lemma generalizes the Yamada normal form of [13].

7

Lemma 5. Let A, B ∈ T , then we have A + B = T1 + pT2 with T1 , T2 ∈ T is uniquely
given by

T = (A p1 + B p1 )p ,
1

where pPp (A, B) =
gral coefficients.

T2 ≡ −Pp (A p1 , B p1 ) (mod p),

Pp−1

p
i p−i
,
i=1 (i )A B

and Pp (A, B) is a polynomial in A, B with inte-

Proof. Note that
(A + B)p = Ap + B p + pPp (A, B).
i

i

i

We then claim that (A + B)p = Ap + B p + pPp (Ap
can be proved by induction on n as follows.
(A + B)p

n

= (Ap

n−1

+ Bp

n−1

= (Ap

n−1

+ Bp

n−1

n

n

i−1

, Bp

+ pPp (Ap

i−1

n−1

) for any integer i. This

, Bp

n−1

))p

)p

= Ap + B p + pPp (Ap

n−1

, Bp

n−1

),

where the first and last equality hold by induction hypothesis. We then obtain
1

1

1

1

A + B = (A p + B p )p − pPp (A p , B p ),
which implies


T = (A p1 + B p1 )p ,
1
T2 ≡ −Pp (A p1 , B p1 ) (mod p),

1

1

n

1

1

since it can be checked by the formulas above that (A p + B p )p = (A p + B p )p ,
1
1
showing that (A p + B p )p ∈ T . This determines T1 uniquely. We can only determine
T2 (mod p), which is enough for our purpose. Then the result follows.
With Lemma 5, we then obtain the following important theorem, which gives a
necessary and sufficient condition for C2 to be a self-dual code over R2 .
Theorem 4. C2 is self-dual over R2 with respect to Hermitian inner product iff

1 + α 1+u
p
≡ 0 (mod p),
βαu + β u α − Pp (1, α 1+u
p ) ≡ 0
(mod p).
8

Proof. C2 is self-dual iff 1 + bb = 0, i.e. 1 + bF

n−1
4

(b) = 0, which is equivalent to

1 + α1+u + pβαu + pβ u α = 0 = T1 + pT2 ,

(3)

where T1 ∈ T , T2 ∈ T and T1 = T2 = 0.

By Equation (3) and Lemma 5, we can then have
1 + α1+u = (1 + α

1+u
p

)p − pPp (1, α

1+u
p

).

Then Equation (3) is equivalent to
(1 + α
That implies

1+u
p

)p + p(βαu + β u α − Pp (1, α


1 + α 1+u
p
≡ 0 (mod p)
βαu + β u α − Pp (1, α 1+u
p ) ≡ 0

1+u
p

)) = 0.

(mod p)

Then the result follows.

Next, we will enumerate the number of possible choices for C2 .
Theorem 5. The number of self-dual codes C2 over R2 is equal to u(1 + u).
1

Proof. Let x = α p and we then consider the equation
x1+u ≡ −1

(mod p).

It can be obtained that, noting that 2(1 + u) is a divisor of u2 − 1, the number of
1+u
choices for x, hence for α, is 1 + u. Then by the equation βαu + β u α − Pp (1, α p ) ≡ 0
(mod p), we get
2
T ruu (βbα
bu ) = f (b
α),
1+u

where f (b
α) denotes Pp (1, α p ) ≡ 0 (mod p). That implies that there are u choices
for β when fixed α. Thus, the number of C2 is equal to u(1 + u).
By the CRT, the following theorem can be derived.

Theorem 6. The number of self-dual codes C over R is equal to 2u2(u + 1)2 .
Proof. By Theorems 3 and 5, we obtain the number of C’s as 2u2 (u + 1)2 .

9

We are now ready to investigate the number of LCD codes. We firstly introduce
the following proposition.
Proposition 1. C2 is LCD over R2 iff 1 + b · b ∈ R∗2 .
Proof. “ ⇐ ”
1. If b ∈ R∗2 , we then obtain C2⊥H = h[1, − 1b ]i. Suppose C2 is not LCD, then
there exist nonzero t, k ∈ R2 such that t(1, b) = k(1, − 1b ). We then obtain
t(1 + bb) = 0, which implies t = 0 since 1 + b · b ∈ R∗2 . Contradiction !
2. If b ∈ R2 \R∗2 , write b = pb′ with b′ ∈ T . Then we have
!
′
1
2b
C2⊥H =
0 2b′′
with b′′ ∈ T . Suppose C2 is not LCD, then there exist nonzero m, n, l ∈ R2
such that m(1, 2b′ ) = n(2b′ , 1) + l(0, 2b′′ ). That implies

m = 2nb′ ,
2mb′ = n + 2lb′′ ,
then we obtain m = 0, a contradiction !

“ ⇒ ” Suppose 1 + b · b ∈ R2 \R∗2 , then we have the following two cases.
1. If b ∈ R∗2 , we have p(1 + b · b) = 0 = p(1, b) · (1, b). Note that C2⊥H = h[1, − 1b ]i,
we then obtain p(1, b) ∈ C2⊥H , which implies p(1, b) ∈ C2⊥H ∩ C2 . Contradiction!
2. If b ∈ R2 \R∗2 , we then get 1 ∈ R2 \R∗2 , a contradiction !
This completes the proof.
Similarly, we have Proposition 2 about C1 , which is a constituent code over R.
Proposition 2. The code C1 is LCD over R iff 1 + a · a ∈ R∗ . In particular, the
number of possible choices for a is p4 − 2p2 .

10

Proof. The proof of the first statement is similar to that of Proposition 1, with the
Euclidean inner product replacing the Hermitian inner product. We omit it here.
Write a = a1 + pa2 with a1 , a2 ∈ T1 . By this criterion the number of possible choices
for a is equal to
p4 − |{a | a2 + 1 = pa′ , a′ ∈ T1 }| = p4 − |{(a1 , a2 ) | a21 + 1 = 0}|,
2

where T1 = {x ∈ R | xp = x}. Then the result follows.
To determine the number of LCD codes C2 , we will reason by complementation.
Theorem 7. C2 is not LCD code over R2 with respect to Hermitian inner product
iff
1+u
1 + α p ≡ 0 (mod p).
Proof. C2 is not LCD iff 1 + bb ∈ pR2 , i.e.,
1 + α1+u + pβαu + pβ u α = T1 + pT2 ,

(4)

where T1 = 0, T2 ∈ T . By Equation (4) and Lemma 5, we can then have
1 + α1+u = (1 + α

1+u
p

)p − pPp (1, α

1+u
p

).

Then Equation (4) is equivalent to
(1 + α

1+u
p

)p + p(βαu + β u α − Pp (1, α

1+u
p

)) = pT2 .

That implies
1+α

1+u
p

≡ 0 (mod p),

with β is arbitrary.
Combining Proposition 2 and Theorem 7, we have the following important theorem.
Theorem 8. The number of LCD codes C over R is equal to (p4 − 2p2 )(p2(n−1) −
u 3 − u 2 )2 .
Proof. We know that the total number of codes over R and R2 are p4 and p2(n−1) ,
respectively. Based on Theorems 3 and 5, the choice for non LCD codes is (u + 1)u2 ,
then the result follows by subtraction.
11

3.1.2

n ≡ 3 (mod 4)

If n ≡ 3 (mod 4), we have g3∗ (x) = g2 (x), g2∗ (x) = g3 (x). Then by the CRT, we
L L ′
and C3′
obtain C = C1 C2′
C3 , where C2′ is a code of length 2 over the ring (gR[x]
2 (x))

is a code of length 2 over the ring (gR[x]
. Writing C2′ = h[1, b′ ]i. Let R′i = (gR[x]
for
∗
i (x))
2 (x))
′
′
′
′
i = 2, 3. Similarly, b can be uniquely decomposed in base p as b = α + pβ , where
n−1
α′ , β ′ ∈ T ′ = {x ∈ R′2 | xp
= x}.

Note that, if C is self-dual we then have C3′ = C2′⊥ . The following result is needed
to count the number of self-dual C’s.

Theorem 9. The number of dual pairs (C2′ , C3′ = C2′⊥ ) over R′2 is equal to p2(n−1) −
pn−1 .
Proof. Assume that C2′ = h[1, b′ ]i, let C3′ = C2′⊥ , then we have the following discussion.
(i) If b′ is a unit, we then obtain C3′ = h[1, − b1′ ]i.
(ii) If b′ is not a unit, let b′ = pβ ′ , then we get C3′ = h[−pβ ′ , 1]i.
Thus, from the form of the generator matrix of C3′ , it is clear that the number of dual
2(n−1)
pairs (C2′ , C3′ = C2′⊥ ) is exactly the size of R′∗
− pn−1 .
2 , i.e., is equal to p
Theorem 10. The number of self-dual codes C over R is equal to 2 · (p2(n−1) − pn−1 ).
Proof. Based on Theorems 3 and 9, we can obtain the desired results.
Lemma 6. Writing C2′ = h[1, b′ ]i and C3′ = h[1, c′]i. Then

C ′ ∩ C ′⊥ = {0},
2
3
C ′⊥ ∩ C ′ = {0}
2

3

′

iff 1 + b′ c′ ∈
/ pR2 .

′

Proof. “ ⇒ ” If 1 + b′ c′ ∈ pR2 , we then obtain p(1 + b′ c′ ) = 0, which implies
p(1, b′ ) · (1, c′ ) = 0. That is equivalent to p(1, b′ ) ∈ C3′⊥ , noting that p(1, b′ ) ∈ C2′ ,
which is a contradiction with C2′ ∩ C3′⊥ = {0}.
“ ⇐ ” If C2′ ∩ C3′⊥ 6= {0}, then we must have λ ∈ GR(p2 , p2(n−1) ) such that
λ(1, b′ )(1, c′ ) = λ(1 + b′ c′ ) = 0.
(1) If λ is a unit, we get 1 + b′ c′ = 0, which is a contradiction with 1 + b′ c′ ∈
/ pR′2 .
12

(2) If λ is not a unit, writing λ = pλ1 with λ1 ∈ Tej , we can obtain 1 + b′ c′ ∈ pR′2 ,
Contradiction !
Then the result follows.
Theorem 11. Suppose u′ = pn−1 , the number of LCD codes over R is equal to
(p4 − 2p2 ) · (u′4 − u′2 + u′ ).
Proof. Just keep the same notations as in Lemma 6. In the following, we aim to
count the possible choices for C2′ and C3′ . Then we have
(1) If b′ is a unit, then c′ is arbitrary except the case when c′ ∈
implies the number of pairs (b′ , c′ ) is (u′2 − u′ )2 .

−1
b′

+ pR′2 , which

(2) If b′ is not a unit, i.e., b′ = pb′1 with b′1 ∈ T ′ , then c′ is arbitrary. In detail,
/ pR′2 . Thus, the
c′ = c′1 + pc′2 with c′1 , c′2 ∈ T ′ , we have 1 + b′ c′ = 1 + pc′1 b′1 ∈
number of pairs (b′ , c′ ) is u′ · u′2 = u′3 .
Thus, the total number of Cj′ , Cj′′ is (u′2 − u′ )2 + u′3 = u′4 − u′3 + u′2 . Therefore, the
total number of LCD double circulant codes is equal to, based on Proposition 2,
(p4 − 2p2 ) · (u′4 − u′3 + u′2 ).
This completes the proof.

3.2

Enumeration in the general case

The following result, while not needed for the asymptotics, is of interest in its own
right.
Theorem 12. Let n be an odd integer, assume that the factorization of xn − 1 into
irreducible polynomials over R is of the form
n

x − 1 = ς(x − 1)

s
Y

gi (x)

i=2

t
Y

hj (x)h∗j (x),

j=1

with ς ∈ R∗ , and gi (x) is a self-reciprocal polynomial of degree di with di a even
integer, the polynomial hj (x) is of degree ej and ∗ denotes reciprocation. The number
of self-dual double circulant codes over R is
2

s
Y
i=2

(u2i

t
Y
′
+ ui ) (u′2
j − uj ),
j=1

13

The number of LCD double circulant codes over R is
s
t
Y
Y
4
3
2
′3
′2
(p − 2p ) (ui − ui − ui ) (u′4
j − uj + uj ),
4

2

i=2

j=1

where ui = pdi , u′j = p2ej .
Proof. Let R =

R[x]
.
(xn −1)

We know that

R[x]
R≃
⊕
(x − 1)

M
s
i=2

R[x]
(gi (x))

by the CRT. Denote by Gi the ring
R[x]
.
(h∗j (x))



R[x]
,
(gi (x))

⊕

M
t

R[x]
R[x]
(
⊕ ∗
)
(hj (x)) (hj (x))
j=1

by Hj′ the ring

R[x]
(hj (x))



and by Hj′′ the ring

This decomposition naturally extends to R2 as
2

2

R ≃R ⊕

M
s

G2i

i=2



M

t
′2
′′2
⊕
(Hj ⊕ Hj ) .
j=1

In particular, each R-linear code of length 2 can be decomposed as the “CRT sum”
C ≃ C1 ⊕

M
s
i=2

Ci



⊕

M
t

(Cj′

j=1

⊕

Cj′′ )


.

By Theorem 3, and the analogues of Theorems 5 and 9, the number of self-dual codes
is
s
t
Y
Y
′
2
ui (1 + ui ) (u′2
j − uj ).
i=2

j=1

Based on Theorems 8 and 11, the number of LCD codes is equal to

s
t
Y
Y
4di
2
′3
′2
(p − 2p ) (p − ui (ui + 1)) (u′4
j − uj + uj ),
4

2

i=2

j=1

where ui = pdi , u′j = p2ej . Then the result follows.

4

Relative distance bound

This section only uses enumeration for the special case of the factorization of xn −1
into two irreducibles. We assume p ≡ 3 (mod 4) to use the duality-preserving Gray
14

map given by Section 2.3. If C is an R-code, we call its Fp image the image of φ(C)
by the Gray map of [9] with k = 1. Note that if C is a code of length 2n over R then
φ(C) is of length 4n over Zp2 and the Fp -image of φ(C) has length 4pn over Fp . We
prepare for the proof of the main result by the following result.
Theorem 13. If e, f ∈ Rn , and (0, 0) 6= (e, f ) has Hamming weight < n, then the
vector (e, f ) is in at most λ double circulant codes of length 2n with λ = p3n+1 .
Proof. Write (e, f ) = (e1 , f1 ) ⊕ (e2 , f2 ) ⊕ (e3 , f3 ) for the CRT decomposition of (e, f ).
2
Consider C1 = h[1, a]i, a = α1 +pβ1 , α1 , β1 ∈ T1 = {x ∈ R | xp = x}. Let (e1 , f1 ) ∈ C1 ,
we have f1 = e1 a.
(i) If e1 is a unit, a =

f1
.
e1

(ii) If e1 (6= 0) is not a unit, write e1 = pe′1 with e′1 ∈ T1∗ . We then obtain f1 = pae′1 .
(ii-1) α1 6= 0, we have f1 = pf1′ = pα1 e′1 , which implies α1 =

f1′
,
e′1

β1 is arbitrary.

(ii-2) α1 = 0, we have a = pβ1 , which implies f1 = 0, β1 is arbitrary.
(iii) If e1 = 0, we then get f1 = 0. That implies a is arbitrary. We can easily get
there are at most p4 double circulant codes that containing (e1 , f1 ).
Consider C2 = h[1, b]i, b = α2 + pβ2 , α2 , β2 ∈ T2 , where the case is similar to that of
C1 with T2 playing the role of T1 . Note that T2 = T or T ′ . Thus, the number of
constituent codes C2 is at most |T |2 = |T ′ |2 .

The case is the same as that of C3 . However, these two analyses cannot be run
independently. The detail is as follows.
1. If both e2 and e3 are 0, then we obtain e ∈ (g2 (x)g3 (x)), the repetition code of
length n. So either e = 0 yielding f = 0, or wH (e) = n, contradicting the hypothesis. This argument shows that the case (iii) cannot happen simultaneously
for C2 and C3 .
2. If both e2 and e3 are not units, and e2 , e3 6= 0, we can easily get eb ≡ ed
2 e3 ≡ 0
(mod g2 (x)g3 (x)).
(a) If b
e 6= 0, we then obtain wH (e) ≥ wH (b
e) = n, a contradiction !
15

(b) If eb = 0, assume that 0 6= e = pe′ , then we have f = pf ′ . Write C = h[1, d]i,
R[x]
p2n
= x}. We
where d = d1 + pd2 with d ∈ (xR[x]
n −1) , d1 , d2 ∈ {x ∈ (xn −1) | x
′

can get d1 = fe′ and d2 is arbitrary. In this case, there are at most p2n
double circulant codes containing (e, f ).

Thus, we obtain λ = p4 |T |2 |T | = p3n+1 when e1 = e2 = 0 and e3 is not unit.
Theorem 14. If e, f ∈ Rn , and (0, 0) 6= (e, f ) has Hamming weight < n, then
the vector (e, f ) is in at most λ self-dual double circulant codes of length 2n with
λ = 2u2 (u + 1).
Proof. Write (e, f ) = (e1 , f1 ) ⊕ (e2 , f2 ) ⊕ (e3 , f3 ) for the CRT decomposition of (e, f ).
2
Let (e1 , f1 ) ∈ C1 = h[1, a]i, a = α1 + pβ1 , α1 , β1 ∈ T1 = {x ∈ R | xp = x}. We
can easily get there at most exist 2 self-dual codes which contain (e1 , f1 ). Consider
(e2 , f2 ) ∈ C2 = h[1, b]i, b = α2 + pβ2 , with α2 , β2 ∈ T or T ′ , we then obtain f2 = be2 .
(i) If e2 is a unit, then b =

f2
.
e2
2

(ii) If e2 (6= 0) is not a unit, write e2 = pe′2 with e′2 ∈ T2∗ = {x ∈ R | xp = x}. We
then obtain f2 = pae′2 .
(ii-1) α2 6= 0, we have f2 = pf2′ = pα2 e′2 , which implies α2 =

f2′
,
e′2

β2 is arbitrary.

(ii-2) α2 = 0, we have b = pβ2 , which implies f2 = 0, β2 is arbitrary.
(iii) If e2 = 0, we then get f2 = 0. That implies b is arbitrary. We can easily get
there are at most u(1 + u) self-dual codes that containing (e2 , f2 ).
By Theorem 13, then e2 , e3 6= 0. If e2 , e3 are not units with e2 , e3 6= 0, based
on 2 in Theorem 13, for the subcase 2(b), we obtain 1 + d2 = 0. We then get
1 + d21 + 2pd1 d2 = 0, where d = d1 + pd2 . Then we have 1 + d21 ≡ 0 (mod p), which
2
implies two coices for d1 . By Lemma 5, we can get 2db1 db2 − Pp (1, db1 p ) = 0, which
2

c
d1 p )
implies db2 = Pp (1,
. Then d2 is uniquely determined by d1 . That is to say, there
2c
d1
are at most 2 self-dual codes containing (e, f ) when e2 , e3 are not units.

Thus, by Theorem 5, we obtain λ = 2u2 (u + 1) with at most u self-dual codes
containing (e3 , f3 ) if n ≡ 1 (mod 4). When n ≡ 3 (mod 4), C3 is determined by C2 .
Then, the result follows.

We can now state and prove the main result of this paper.
16

Theorem 15. Assume the Artin conjecture for primes in arithmetic progression [11]
holds. There is an infinite family of double circulant self-dual (resp. LCD) R-codes
with rate 21 and relative Hamming distance of the Fp image δ ≥ Hp−1 (1/8p) (resp.
δ ≥ Hp−1 (1/4p)).
Proof. Artin conjecture for primes in arithmetic progression shows in particular that
p and ǫ ∈ {±1} being given, there are infinitely many primes n ≡ ǫ (mod 4) such
that p is primitive modulo n. It should be noted that the size Ωn of the family of codes
we consider is asymptotically equivalent to 2u4 for self-dual codes and to p4n for LCD
codes. This holds for the case ǫ = 1 by Subsection 3.1.1 like for the case ǫ = −1 by
Subsection 3.1.2. Assume we can prove that for n large enough Ωn > λB(dn ), where
λ = p3n+1 for LCD codes and λ = 2u2 (u + 1) for self-dual codes and B(r) denotes the
number of vectors in R2n with Hamming weight of their Fp image < r. This would
imply by Theorem 13 that there are codes of length 2n in the family with Fp image
distance ≥ dn . Denote by δ the relative distance of this family of p-ary codes. If we
take dn the largest number satisfying the said inequality, and assume a growth of
the form dn ∼ 4pδ0 n, then, using an entropic estimate for B(dn ) ∼ p4pnHp (δ0 ) (cf. [6,
1
for
Lemma 2.10.3]) yields, with the said values of Ωn and λ the estimate Hp (δ0 ) = 8p
1
self-dual codes and Hp (δ0 ) = 4p for LCD codes. The result follows by observing that,
by definition of the family of codes so constructed, δ ≥ δ0 .

5

Numerical examples

Assume p = 3 and C = h[I, A0 + yA1 ]i, where A0 , A1 are circulant matrices of
size n and I is the identity matrix of the same size. The generator matrix of φ(C)
can be computed as
4I I 4A0 + 3A1 A0 + A1
3I I 3A0 − 4A1 A0 − A1

!

.

Define the base 3 decomposition of x ∈ Z9 as
x = r0 (x) + 3r1 (x),
where ri (x) ∈ {0, 1, 2}. Then we can define the Gray map of [9] as
Φ : Z9 → Z33
17

Table 1: Double circulant LCD codes over Z9 + uZ9 and their Gray images φ, Φ
n
2
3
4
5

a1 (x)
41
811
3651
10856

a0 (x) (4n, 92n , dφ(C) )Z9 [12n, 4n, dΦ(C) ]Z3 Distance of BKLC over Z3
51
(8, 94, 4)
[24, 8, 6]
11
081
(12, 96 , 6)
[36, 12, 12]
15
8
6505
(16, 9 , 5)
[48, 16, 14]
18
10
57664
(20, 9 , 6)
[60, 20, 16]
21

a 7→ (a0 , a1 , a2 ),
where ai = r1 (a) + ir0 (a). The explicit map is tabulated below.

x
0
1
2
3
4
5
6
7
8

Φ(x) wH (Φ(x))
(0,0,0)
0
(0,1,2)
2
(0,2,1)
2
(1,1,1)
3
(1,2,0)
2
(1,0,2)
2
(2,2,2)
3
(2,0,1)
2
(2,1,0)
2

In Table 1 and Table 2 we have collected some examples of double circulant LCD
and self-dual codes obtained by random search in Magma. The coefficients of degree
n polynomial a(x) are written in decreasing powers of x, for example for n = 3,
the entry 811 means 8x2 + x + 1. The parameters over Z9 and Z3 are given in the
form (4n, 92n , dφ(C) ) and [12n, 4n, dΦ(C) ] respectively, where dφ(C) and dΦ(C) are the
Hamming minimum distancess of their Gray images φ and Φ respectively. The entry
in the rightmost column is the best known distance of an [12n, 4n] tenary linear code,
obtained by looking up at the tables in www.codetables.de.

18

Table 2: Double circulant self-dual codes over Z9 + uZ9 and their Gray images φ, Φ
n
2
3
4
5

6

a1 (x)
10
811
6731
26758

a0 (x) (4n, 92n , dφ(C) )Z9 [12n, 4n, dΦ(C) ]Z3 Distance of BKLC over Z3
00
(8, 94, 3)
[24, 8, 10]
11
081
(12, 96 , 6)
[36, 12, 12]
15
8
4752
(16, 9 , 6)
[48, 16, 15]
18
10
62532
(20, 9 , 6)
[60, 20, 18]
21

Conclusion

In this article we have studied double circulant codes either self-dual or LCD over
Galois rings of characteristic p2 and size p4 . Extending the study to GR(ps , pms ), with
s > 2 would result in more terms in the base p expansion of a ring element and would
make the computations of Section 3 more difficult. A similar remark can be made
about using m > 2. More tractable could be to study quasi-cyclic codes of higher
index, like four-circulant codes, for instance.
We have used the composition of two Gray maps to derive codes over Fp . While
the choice of the Hamming metric over Fp is the most natural one, the study of the
Lee minimum distance of the Fp -image could also be worthwhile.

References
[1] A. Alahmadi, F. Özdemir, P. Solé, On self-dual double circulant code, Designs,
Codes Cryptogr., online July 20, 2017.
[2] C. Carlet, S. Guilley, Complementary Dual Codes for Counter-Measures to SideChannel Attacks, Adv. in Math. of Comm. , 10(1), (2016), 131-150 .
[3] S.T. Dougherty, T.A. Gulliver, and J. Wong, Self-Dual Codes over Z8 and Z9 ,
Designs, Codes, and Cryptography,(2006), 235–249.
[4] S. T. Dougherty, J.L. Kim, B. Özkaya, L. Sok, P. Solé, The combinatorics of LCD
codes: linear programming bound and orthogonal matrices. Int. J. of Information
and Coding Theory, 4(2/3), (2017), 116–128.
19

[5] M. Harada, A. Munemasa, On the classification of self-dual Zk -codes,Lecture
Notes in Comput. Sci.,5921, Springer, (2009), 78–90.
[6] W. C. Huffman, V. Pless, Fundamentals of error correcting codes, Cambridge
University Press, 2003.
[7] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory (2nd
ed.) (1990), Springer
[8] J-L. Kim, Y. Lee, Construction of MDS self-dual codes over Galois rings. Des.
Codes Cryptography, 45(2), (2007), 247–258.
[9] S. Ling, T. Blackford, Zpk+1 -linear codes, IEEE trans. on Information Theory
48(9), (2002), 2592–2605.
[10] S. Ling, P. Solé, On the Algebraic Structure of Quasi-cyclic Codes II: Chain
Rings, Des. Codes Cryptography, 30(1), (2003), 113–130.
[11] P. Moree, On primes in arithmetic progression having a prescribed primitive
root, Journal of Number Theory, 78(1), (1999), 85-98.
[12] M. Shi, A. Alahmadi, P. Solé,Codes and Rings: Theory and Practice, Academic
Press (2017).
[13] Z. X. Wan, Finite Fields and Galois Rings, World Scientific (2003).

20

