Type II Codes over F_{4} (DRAFT 2.5)

Philippe Gaborit

Department of Mathematics, Statistics, and Computer Science

322 SEO, University of Illinois–Chicago, 851 S. Morgan, Chicago, IL 60607-7045, USA

                    Email: gaborit@math.uic.edu,

Vera Pless

Department of Mathematics, Statistics, and Computer Science

322 SEO, University of Illinois–Chicago, 851 S. Morgan, Chicago, IL 60607-7045, USA

                     Email: pless@math.uic.edu,

Patrick Solé CNRS, I3S, ESSI, BP 145 Route des Colles 06 903 Sophia Antipolis, France

                         Email: ps@essi.fr

and

Oliver Atkin

Department of Mathematics, Statistics, and Computer Science

322 SEO, University of Illinois–Chicago, 851 S. Morgan, Chicago, IL 60607-7045, USA

                    Email: aolatkin@math.uic.edu

Running Head: TYPE II F_{4}-CODES

Contact Author: Patrick Solé CNRS, I3S, ESSI, BP 145 Route des Colles 06 903 Sophia Antipolis France

Email: sole@diamant.unice.fr

Tel: (33)4 92 96 51 06 Fax: (33)4 92 96 51 55

Abstract

The natural analogues of Lee weight and Gray map over 𝔽_{4} are introduced. Selfdual codes for the Euclidean scalar product with Lee weights a multiple of 4 are called Type II. They produce Type II binary codes by the Gray map and even golden lattices by Construction A. All extended Q−codes of length a multiple of 4 are Type II. This includes generalized quadratic residue codes attached to a prime power q ≡ 7 (mod 8), certain double circulant codes and some affine invariant codes. A general mass formula is derived; weight enumerator invariant theory and shadow theory are developed.

1 Introduction

The notion of Type II codes over 𝔽_{2} was introduced by Gleason and Pierce in the sixties. More recently Type II codes over ℤ_{4} and 𝔽_{2} + u𝔽_{2} were introduced, motivated by coding constructions for even lattices [1] and even Hermitian lattices [9] respectively. In this article, Type II codes over 𝔽_{4} are introduced to construct Type II binary codes by projection on the unique trace-orthogonal basis. This transform maps self-dual codes for the Euclidean scalar product onto self-dual binary codes. We introduce the Lee weight over 𝔽_{4} as the Hamming weight of the Gray image. Self-dual codes over 𝔽_{4} for the Euclidean scalar product are called Type II if their Lee weights are multiples of 4 and Type I otherwise. It should be noted that the Euclidean scalar product has received much less attention so far than the Hermitian scalar product. Examples of Type II codes are generalized quadratic residue codes of length q + 1 with q a prime congruent to 3 mod 8 [4], some affine-invariant codes [14], and certain Q-codes introduced by Pless in [20].

While the binary images of these quadratic residue codes have been studied by several authors [16, p.509],[4], the binary images of the Q-codes are considered here for the first time. In addition, a connection with ℤ[τ]-lattices, where τ denotes the golden ratio, is developed.

The material is organized as follows. Section II collects definitions and notations. Section III establishes the basic properties of the Gray map, shadows, and Construction A. Section IV derives bounds on the minimum distance of the binary image as a function of the minimum distances of the subfield subcode and of the trace code. Section V studies algebraic Type II codes: quadratic residue, double circulant, affine invariant, and duadic codes. It turns out that all extended Q-codes of doubly even length are Type II; the proof appeals to elementary (but not easy!) number theory. Section VI is concerned with classification, Section VII with invariant theory, and Section VIII with shadows.

2 Notations and Definitions

In this section, we give the needed notation and definitions. In particular, we introduce Type II codes which are a remarkable class of self-dual codes.

Let 𝔽_{4} := {0, 1, ω, ω̄ = ω^{2}} be the finite field of order 4, A code C of length n over 𝔽_{4} is an 𝔽_{4}-subspace of 𝔽_{4}^{n}. An additive code is a subgroup of (𝔽_{4}^{n}, +). An element of C is called a codeword. Duality for codes is understood with respect to the Euclidean form ∑_{i} x_{i}y_{i}. C is said to be self-dual if C = C^{⊥}. The Lee composition of a vector x = (x_{1}, …, x_{n}) ∈ 𝔽_{4}^{n} is defined as (n_{0}(x), n_{1}(x), n_{2}(x)) where n_{0}(x) is the number of x_{i} = 0, n_{2}(x) the number of x_{i} = 1 and n_{1}(x) = n − n_{0}(x) − n_{2}(x) where n is the length. The Lee weight w_{L}(x) of x is then defined as n_{1}(x) + 2n_{2}(x). The symmetrized weight enumerator (swe for short) is defined as

swe_{C}(a, b, c) = ∑_{x∈C} a^{n_{0}(x)}b^{n_{1}(x)}c^{n_{2}(x)}.

There is a natural (not 𝔽_{4}-linear!) Gray map ϕ which is a 𝔽_{2}-linear isometry from (𝔽_{4}^{n}, Lee distance) onto (𝔽_{2}^{2n}, Hamming distance) where the Lee distance of two codewords x and y is the Lee weight of x − y. We let, for all x, y ∈ 𝔽_{2}^{n}

ϕ(ωx + ω̄y) = (x, y).

Consider the number field K := ℚ(\sqrt{5}). View 𝔽_{4} as the quotient of the ring ℤ[τ] by the ideal (2) with τ := \frac{1+\sqrt{5}}{2} the golden ratio. In this quotient τ is mapped to ω by the canonical surjection. Following [8] we equip the ring ℤ[τ] with the bilinear form (x, y) := T (xy/τ\sqrt{5}), where T denotes the trace from K down to ℚ. The lattice obtained in that way is equivalent to ℤ^{2}. Its Gram matrix is I_{2}. This leads us to introduce an Euclidean weight w_{E}(.) on 𝔽_{4} by the rule w_{E}(0) = 0, w_{E}(ω) = w_{E}(1) = 1, w_{E}(ω̄) = 2. Observe that x ↦ ωx is an isometry from (𝔽_{4}, w_{E}) to (𝔽_{4}, w_{L}).

Since multiplying a column by ω does not preserve the Euclidean or Lee weight of a codeword, we need a restricted definition of equivalence and we say that two codes are equivalent if one can be obtained from the other by permuting the coordinates (this is not the usual monomial equivalence).

A self-dual code over 𝔽_{4} is said to be Type II if the Lee weight of every codeword is a multiple of 4 and Type I otherwise.

3 First Properties

3.1 Gray Map

First, we connect the properties of C to those of its Gray image.

Proposition 3.1 If C is self-orthogonal so is ϕ(C). In this case ϕ(C) is a Type I (resp. Type II) code iff C is a Type I (resp. Type II) code.

Proof. Let z = ωx + ω̄y (resp. z′ = ωx′ + ω̄y′), with x, y (resp. x′, y′) ∈ 𝔽_{2}^{n}. If zz′ = 0 in 𝔽_{4} then zz′ = ω(yy′ + xy′ + x′y) + ω̄(xx′ + xy′ + x′y) entails both yy′ + xy′ + x′y′ = 0 and xx′ + xy′ + x′y = 0. □

The following theorem gives a restriction on the length of a Type II code.

Corollary 3.2 There exists a Type II code of length n iff n ≡ 0 (mod 4).

Proof. It is known that if a binary Type II code exists for length n then n ≡ 0 (mod 8) (cf. [18]). Thus if a Type II code of length n exists then n must be divisible by four. The code with the following generator matrix

( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & ω & ω̄ \end{matrix} )

is Type II of length 4. It is therefore possible to construct by direct sums Type II codes over 𝔽_{4} for any length which is a multiple of 4. □

Remark. The above restriction may be obtained using invariants for the symmetrized weight enumerators of Type II codes (see Theorem 7.2).

Corollary 3.3 Let d_{L}(II, n) and d_{L}(I, n) be the highest minimum Lee weights of a Type II code and a Type I code, respectively, of length n. Then

d_{L}(II, n) ≤ 4 [\frac{n}{12}] + 4,
d_{L}(I, n) ≤ \{ \begin{matrix}4 [\frac{n}{24}] + 4, & if n ≠ 22, \\ 4 [\frac{n}{24}] + 6, & if n = 22. \end{matrix}

Proof. The Gray map is an isometry from (𝔽_{4}^{n}, Lee distance) to (𝔽_{2}^{2n}, Hamming distance). An upper bound on the minimum Hamming weight of a binary Type II (resp. Type I) code is given in [18] (resp. [21]). □

Lemma 3.4 Let C and C′ be equivalent self-dual codes over 𝔽_{4}. Then ϕ(C) and ϕ(C′) are equivalent.

Proof. This follows from the definition of the Gray map. □

3.2 Lattices

3.2.1 Construction A

With every code C over 𝔽_{4} we attach the lattice

A(C) = L(C)/\sqrt{2}.

where we have set

L(C) := {x ∈ ℤ[τ]^{n}| x (mod 2) ∈ C}.

This is the golden analogue of the construction A_{2}(C_{b}) of [7] given for a binary linear code C_{b} by

\sqrt{2}A_{2}(C_{b}) := \{x ∈ ℤ^{n}| x (mod 2) ∈ C_{b}\}.

We connect the properties of C to those of its attached lattice. We call the projection p(z) of a golden number a + bτ the pair (a, b) and extend it component-wise to get a 1 − 1 map from ℤ[τ]^{n} onto ℤ^{2n}. Observe that p is an isometry from ℤ[τ]^{n} with the metric induced by the quadratic form x ↦ T (x^{2}/τ\sqrt{5}) onto ℤ^{2n} with the standard Euclidean metric.

Proposition 3.5 If C is Type II then A(C) is even unimodular, and unimodular if C is Type I. Further, p(A(C)) = A_{2}(ϕ(C)).

Proof. The first assertion follows from the fact that the Lee weight distribution is the same as the Euclidean weight distribution. The second follows by observing that, for a, b in 𝔽_{2}^{n} and x, y ∈ ℤ^{n} we have

p(τ(a + τb + 2(x + τy))) = (b + 2y| a + b + 2(x + y)),

and

ϕ(ω̄(a + bω)) = (b, a + b).
□

Remark. This gives a new proof of Corollary 3.2. since golden unimodular even lattices only exist in length multiple of 4 [8, p. 242].

3.2.2 Construction B

Let us attempt to define the golden analogue of the classical Construction B hereby called B_{2}. Recall that this construction attaches to a doubly-even binary code C_{b} the lattice

\sqrt{2}B_{2}(C_{b}) := \{x ∈ ℤ^{n}| x (mod 2) ∈ C_{b} and ∑_{i} x_{i} = 0 (mod 4)\}.

Let G_{n} denote any code of 𝔽_{4}^{n} whose Gray image is the parity-check code of length 2n.

With every code C over R we attach the sphere packing:

B(C) = L′(C)/\sqrt{2},

where we have set

L′(C) := C + 2G_{n} + 4ℤ[τ]^{n}.

The following proposition is now immediate.

Proposition 3.6 If C is Type II then B(C) is an integral ℤ−lattice, and p(B(C)) = B_{2}(ϕ(C)).

Unfortunately B(C) is not, for C a general 𝔽_{4}-linear code, a golden lattice, for G_{n}, of size 2^{2n−1} (not a power of 4) is never an 𝔽_{4}-linear code.

3.3 Shadows

We define the even-weight additive subcode C_{0} of a Type I code C as the additive subcode consisting of all codewords of C with Lee weights a multiple of 4. Clearly C_{0} is of index 2 in C and C of index 2 in C_{0}^{⊥}. We write C_{0}^{⊥} = C_{0} ⋃ C_{1} ⋃ C_{2} ⋃ C_{3}. We let C = C_{0} ⋃ C_{2} and define the shadow S of C as S = C_{1} ⋃ C_{3}.

Finally note that the Gray image of the shadow is the shadow of the Gray image.

Proposition 3.7 If C is Type I then ϕ(C_{j}) = ϕ(C)_{j} for j = 0, 1, 2, 3, that is,

C ⟶_{ϕ}  ϕ(C)
↓ ; coset ↓coset
C_{j} ⟶_{ϕ} ϕ(C_{j}) = ϕ(C)_{j}

Corollary 3.8 If C is a Type I code of length n then ϕ(S) is the shadow of ϕ(C). Hence if the shadow of C has minimum Lee weight d_{S} then ϕ(C) is a binary [2n, n] code whose shadow has minimum Hamming weight d_{S}.

4 Bounds on the minimum distance

The subfield subcode C_{2} of C is the linear subcode of C consisting of those codewords all entries of which are binary. The trace code T r(C) of C is the binary code obtained from C by taking the trace of each codeword coordinatewise.

Proposition 4.1 The minimum Lee distance d_{L} of C is at least the Hamming distance of Tr(C) and at most the Hamming distance of C_{2}.

Proof. The first assertion follows by noticing for all x, y ∈ 𝔽_{2}^{n} the identities

T r(ω(ωx + ω̄y)) = x,
T r(ω̄(ωx + ω̄y)) = y.

The second assertion follows by multiplying a vector of C_{2} by ω and taking its binary image. □

5 Constructions

5.1 Quadratic residue codes

Let q be a power of a prime with q congruent to 3 (mod 8). Let C(q) denote the extended generalized quadratic residue code of length q + 1 over 𝔽_{4}.

Proposition 5.1 The code C(q) is a Type II code over 𝔽_{4} and its minimum Lee distance d_{L} satisfies

(d_{L} − 1)^{2} − (d_{L} − 1) + 1 ≥ 2q + 1.

Proof. By [15] the code is self-dual for the Euclidean scalar product and by [4] the Lee weights of the codewords are multiples of 4 and satisfy the said bound. □

Remark : In the case q ≡ ±1 (mod 8), C(q) is obtained by extension of the field of scalars from its subfield subcode and its Gray image is the direct sum of two copies of the binary quadratic residue code. In the case q ≡ −3 (mod 8), C(q) is self-dual only for the Hermitian scalar product.

A study of the Gray image can be found in [16, p. 509]. In Table 1 we extend their results and in particular correct to 16 the minimum (Hamming) weight of the extended quadratic 𝔽_{4} code of length 60, which was incorrectly given as 14 in [13].

5.2 Quadratic double circulant codes

Recently Gaborit introduced in [11] a class of codes which generalizes binary double circulant codes and the Pless symmetry codes to codes over 𝔽_{4}. For m an odd prime or the power of an odd prime and a = 0 or 1, we let the matrix Q(a, w, w^{2}) be the m × m matrix on 𝔽_{4} labeled on its rows and its columns by elements of GF (m): r_{0} = a, r_{1}, ⋯, r_{m−1}, with components q_{ij}. The entries q_{ij} are defined in terms of quadratic residues and by the function χ defined on GF (m) by χ(r_{0}) = 1, χ(r_{i}) = w if r_{i} is a quadratic residue in GF (m), and χ(r_{i}) = w^{2} otherwise. Then we define q_{ij} as χ(a_{j} − a_{i}). In the important case where m is a prime we Table 1: Extended generalized quadratic residue codes over 𝔽_{4} and their Type II binary images

n k d → n_{b} k_{b} d_{b} Comments
12 6 6  24 12 8 Golay code
20 10 8  40 20 8  extremal
28 14 10  56 28 12  extremal
44 22 14  88 44 16  extremal
60 30 16  120 60 ≥ 20 optimal
68 34 ≤16  136 68 24  extremal

set r_{0} = 0, r_{1} = 1, ⋯, r_{m−1} = m − 1, which leads to a circulant Q(1, w, w^{2}) matrix. We let B(m) be the [2m + 2, m + 1] code with generator matrix:

( \begin{matrix}1 & 0 ⋯ 0 & 0 & 1 ⋯ 1 \\ 0 & & 1 \\ 0 & & 1 \\ ⋮ & I & ⋮ & Q(1, w, w^{2}) \\ 0 & & 1 \end{matrix} ) ,

and we let P (m) be the [2m, m] code with generator matrix

( I Q(0, w, w^{2}) ) .

It is proven in [11] that B(m) and P (m) are Euclidean self-dual for m = 8k−1 and therefore the straightforward proposition follows :

Proposition 5.2 The codes C(m) with m = 8k − 1 are Type II Euclidean self-dual codes over 𝔽_{4}.

The binary image of C(m) for m = 7 (a [16, 8, 6] code over 𝔽_{4}) is an extremal binary Type II [32, 16, 8] code which corresponds to the code C83 of the Conway-Pless classification of [5]. The Gray image of P (m) for m = 23 is a [92, 46, 16] extremal binary self-dual code, which is better than any previously known code (cf [2]). The binary images of these codes are displayed in Table 2.

5.3 Affine invariant Codes

These codes have been studied by Lévy-dit-Vehel in her Ph.D. thesis [14, Chapter V]. In particular she determined that there are exactly nine such codes of length 64. All but one Table 2: Quadratic double circulant codes over 𝔽_{4} and their Type II binary images

n k d → n_{b} k_{b} d_{b} Type
14 7 6  28 14 6  I
16 8 6  32 16 8  II
46 23 14  92 46 16  I
48 24 14  96 48 16 II
62 31 16 124 62 16 I
64 32 16  128 64 16 II

of them [14, Property IV.1] contain RM(2, 6) as a subfield subcode and are therefore, by Proposition 4.1, of minimum Lee distance at most 16. They are all Type II [14, §4.3.1].

5.4 Q-codes

This case encompasses both extended cyclic quadratic residue codes and the codes of the preceding section as this class contains all extended cyclic self-dual codes [20]. The case of quadratic residue codes is a special case of Q-codes of prime length. An extended Q-code of composite length is Euclidean self-dual if and only if its length is a multiple of primes which are congruent to 3 modulo 4 ([20]). We already saw that Euclidean self-dual quadratic residue codes were Type II. We now generalize this result to Q-codes:

Theorem 5.3 Let C be an odd-like duadic code (or Q-code) over 𝔽_{4} of length n ≡ 3 modulo 4, with splitting given by μ_{−1}. Let \overline{C} be the extended code of C. Then the Gray image of \overline{C} is of Type II.

We first prove some number theory results.

Let a and N be two integers satisfying (a, N) = 1 and let {a} = (a, a^{2}, …, a^{d} = 1) = {a}_{N} be the cyclotomic coset of a modulo N. We denote by redsets of a modulo N the sets λ{a} with (λ, N) = 1. The redsets correspond to the cyclotomic cosets of the units of Z/(N). It follows that the number of redsets is equal to \frac{ϕ(N)}{d} and that they all have size d. Now any coset of a modulo N can be written as n_{1}λ{a}_{n_{2}}, with n_{1}n_{2} = N and λ{a}_{n_{2}} a redset of a modulo n_{2}. Conversely any redset of a modulo n_{2} gives a unique coset of a modulo N. Recall that the Jacobi symbol [12, p.51] (a/p) attached to an integer a and a prime p is 1 if a is a residue mod p and −1 otherwise. If N = ∏_{i=1}^{r} p_{i}^{α_{i}} then the Legendre symbol [12, p.56] (a/N) is defined as ∏_{i=1}^{r}(a/p_{i})^{α_{i}}.

The following lemma holds:

Lemma 5.4 The number of redsets of a modulo N is odd if and only if N = p^{α} with p a prime satisfying (a/p) = −1.

Proof. If N = ∏_{i=1}^{r} p_{i}^{α_{i}}, then the order d of a modulo N is lcm(d_{1}, …, d_{r}) with d_{i} the order of a modulo p_{i}^{α_{i}}. Since ϕ(p_{i}^{α_{i}}) = (p_{i} − 1)p_{i}^{α_{i}−1}, it follows that 2 divides \frac{ϕ(N)}{d} if i is greater than 1. Now suppose that i = 1, N = p^{α}. If (a/p) = 1, a is a quadratic residue modulo p and d divides \frac{ϕ(N)}{2}. Conversely if (a/p) = −1, then d does not divide \frac{ϕ(N)}{2} and so 2 does not divide \frac{ϕ(N)}{d}. □

We now prove the general result:

Theorem 5.5 Let a and N be two integers such that (a, N) = 1. Then the number of cyclotomic cosets of a modulo N is odd if and only if (a/N) = −1, where (a/N) is the Legendre symbol (or the Jacobi symbol if N is composite).

Proof. Let a and N be two integers such that (a, N) = 1 and N = ∏_{i=1}^{r} p_{i}^{α_{i}}. Then by the preceding lemma and the structure of the cosets in function of the redsets, we find that the parity of the number of cosets is congruent modulo 2 to

∑_{\begin{matrix}p^{α}|N \\ (a/p) = −1 \end{matrix}} 1 = ∑_{(a/p_{i})=−1} α_{i} = S, say.

The identity (a/N) = (−1)^{S} gives the result. □

Corollary 5.6 If a = 2 the number of cosets of a modulo N is odd if and only if N = ∓3(8). If a^{2} = 4 the number of cosets of a^{2} modulo N is always even.

Proof of Theorem 5.3: Let C be an odd-like Q-code of length n ≡ 3 modulo 4, with splitting given by μ_{−1}. As the splitting is given by μ_{−1}, n must be the product of primes, each congruent to 3 modulo 4. The number of these primes is odd. Since μ_{−1} gives the splitting, \overline{C} is Euclidean self-dual. We know that the Gray image of \overline{C} is self-dual by Theorem 3.1. We show now that this image is Type II by giving a basis of doubly even vectors.

Let e(x) be the generating idempotent of C and \overline{e(x)} its extension. It will be enough to prove that the Lee weights of \overline{e(x)} and w\overline{e(x)} are congruent to 0 modulo 4 as the Gray images of the extensions of e(x) and its shifts and the extension of we(x) and its shifts form the desired basis.

Now 4 is a quadratic residue for any prime p. If p is 3 modulo 4, the order of 4 modulo p is odd as it divides \frac{p−1}{2} which is odd. Hence the size of any cyclotomic coset of 4 modulo n is odd.

Let S_{1} be the set of elements of 4-cyclotomic cosets of n which are not 2-cyclotomic cosets and S_{2} the set of elements of 4-cyclotomic cosets which are 2-cyclotomic cosets. Define m_{1} = |S_{1}| and m_{2} = |S_{2}|. Note that m_{1} and m_{1} + m_{2} are even. Hence m_{2} is also even. As μ_{−1} gives the splitting, for each cyclotomic coset, there is another of the same size namely μ_{−1} of it. Since each 4-cyclotomic coset has odd size and each is paired with another of the same size, m_{1} + m_{2} ≡ n − 1 (mod 4).

Let e(x) = ∑_{i=0}^{n−1} e_{i}X^{i}. The characterization of the e_{i} can be found in [20]. If i ∈ S_{1}, then e_{i} can equal w(or w^{2}) or 1 (or 0). If e_{i} = w, then e_{2i} = w^{2} or if e_{i} = w^{2} then e_{2i} = w. If i ∈ S_{2}, e_{i} = 0 or 1. If e_{i} = 0, then e_{2i} = 1 and if e_{i} = 1 then e_{2i} = 0. Hence as ∑ e_{i} ≡ \frac{m_{1}}{2} + \frac{m_{2}}{2} ≡ \frac{n−1}{2} ≡ 1( mod 2), ∑ e_{i} = 1. As e(x) has odd weight , e_{0} = 0. When we extend e(x) to \overline{e(x)}, the extended position is 1. We see that the Lee weight of \overline{e(x)} modulo 4 is m_{1} + m_{2} + 2 ≡ 0( mod 4).

Note that \frac{m_{1}}{2} + m_{2} is the number of 2-cyclotomic cosets for n. We now look at the Lee weight of w\overline{e(x)} modulo 4 and consider two cases:

Case 1: n ≡ 3( mod 8).

Either m_{1} + m_{2} ≡ n − 1 ≡ 2( mod 8) or m_{1} + m_{2} ≡ 4 + n − 1 ≡ 6( mod 8).

If m_{1} +m_{2} ≡ n−1 ≡ 2( mod 8), then the Lee weight of w\overline{e(x)} modulo 4 is m_{1} + \frac{m_{1}+m_{2}}{2} + 1 ≡ m_{1} + 2( mod 4). As \frac{m_{1}}{2} is odd by Corollary 5.6, m_{1} is singly even so that this weight is doubly even.

If m_{1} +m_{2} ≡ n−1 ≡ 6( mod 8), then the Lee weight of w\overline{e(x)} modulo 4 is m_{1} + \frac{m_{1}+m_{2}}{2} + 2 + 1 ≡ m_{1} + 2( mod 4), which is 0 (mod 4) as m_{1} is singly even.

Case 2: n ≡ 7( mod 8).

Again we must distinguish between whether m_{1} + m_{2} ≡ n − 1 ≡ 6( mod 8) or 2( mod 8). If m_{1} + m_{2} ≡ 6( mod 8), the Lee weight of w\overline{e(x)} modulo 4 is m_{1} + \frac{m_{1}+m_{2}}{2} + 1 ≡

m_{1}( mod 4). As \frac{m_{1}}{2} is even (Corollary 5.6), m_{1} ≡ 0( mod 4).

If m_{1} + m_{2} ≡ 2( mod 8), the Lee weight of w\overline{e(x)} modulo 4 is m_{1} + \frac{m_{1}+m_{2}}{2} + 3, which is m_{1} ≡ 0( mod 4). □

In Table ?? we give the binary images of Euclidean self-dual Q-codes with composite length less than 57. The next length is 63 for which there are 1024 possible codes which are all Type II. We checked some of them and we give in Table 4 two [64, 32, 16] codes whose binary images are [128, 64, 20] binary Type II codes. The notation used in the tables defines Q-codes in terms of the value of the idempotent on each cyclotomic class and is identical to the notation used in [20]. In the table ’l’ stands for the length of the Q-code, ’Q’ stands for the number of equivalent Q-codes, ’n’,’k’ and ’d’ (resp. ’n_{b}’,’k_{b}’ and ’d_{b}’) stand for the length, dimension and minimum weight of the Q-code (resp. the binary image of the Q-code). In particular we obtain extremal binary codes of lengths 44 and 68.

Table 3: Binary images of some extended Q-codes of length ≤ 58

l n k d Q  → n_{b} k_{b} d_{b} Type
9  0 1 3
10 5 3 2 1 w w 20 10 4 I
21  0 1 3 5 7 9
22 11 6 2 1 w 0 w^{2} w^{2} 1  44 22 6  I
22 11 4 2 1 w 0 w^{2} w 1  44 22 4  I
22 11 6 2 1 1 1 0 w^{2} 0  44 22 8  I
22 11 3 2 1 1 0 0 w^{2} 0  44 22 4  I
27  0 1 3 9  I
28 14 4 2 0 w w w  56 28 4  II
28 14 4 2 0 w w^{2} w^{2}  56 28 4  II
33  0 1 3 5 11  I
34 17 3 2 1 w w w w  68 34 4  I
34 17 10 2 1 w w w^{2} w  68 34 12  I
34 17 6 2 1 w w w^{2} w^{2}  68 34 8  I
34 17 6 2 1 w w^{2} w w  68 34 8  I
57  0 1 3 5 19  I
58 29 8 2 1 w w w^{2} w  116 58 8  I
58 29 4 2 1 w w^{2} w w  116 58 4  I
58 29 12 2 1 w w w^{2} w^{2}  116 58 16  I
58 29 6 2 1 w w w w^{2}  116 58 8  I

6 Classification

6.1 Mass Formulas

Finding a mass formula for a given class of codes is in fact counting the number of distinct codes in this class. Mass formulas are a very important tool to classify codes.

The mass formula for Type I codes can be found in [19], we give here a mass formula for Type II codes over 𝔽_{4}:

Theorem 6.1 Let n be an integer multiple of 4 and let N_{d_{II}}(n) be the number of distinct Type II codes over 𝔽_{4} then:

N_{d_{II}}(n) = ∏_{i=1}^{\frac{n}{2} −1} \frac{4^{n−2k−1} + 3.2^{n−2−2k} − 1}{4^{k} − 1}.

Let us denote by 1 the all-one vector (1, 1, …, 1) of length n of 𝔽_{4}^{n} , recall that any Euclidean self-dual code over 𝔽_{4} contains 1 since its binary image is self-dual.

Table 4: Q-codes of length 64 with [128, 64, 20] Type II binary images

0 1 3 15 5 43 7 9 11 13 21
C128 1 0 1 1 0 1 0 2 0 0 1 3
C128 2 0 1 1 0 1 0 w^{2} 0 0 1 w^{2}

By the Gray map there is a correspondence between Type II codes over 𝔽_{4} of length n and Type II binary codes of length 2n. Since the correspondence also preserves their doubly even subcodes, it seems natural to generalize the mass formula for Type II binary codes to the case 𝔽_{4}. In this case the problem is that if we consider a Lee doubly even code over 𝔽_{4} that we want to extend to a code with one more dimension, we have to add a vector v which is not only Lee doubly even but also such that ωv and ω̄v are Lee doubly even.

Lemma 6.2 Let C be a self-orthogonal [n, k] code of length n a multiple of 4, containing 1, with doubly even Lee weight codewords. Let us denote by T (n, k) the number of vectors in C^{⊥} which have doubly even Lee weight and whose product with ω is still Lee doubly even. Then we have the following:

T (n, k) = 4^{n−k−1} + 3.2^{n−2}.

Proof. First we notice that since the Gray map ϕ preserves duality, the number of doubly even (resp. singly even) Lee weight vectors D (resp. S) in C^{⊥} is the same that the number of doubly even (resp. singly even) vectors in ϕ(C)^{⊥}. In our case, since n ≡ 0 (mod 4) these numbers can be found in [10],[17]:

D = 2^{2n−2k−1} + 2^{n−1} and S = 4^{n−k} − D

Let v be a vector of C^{⊥}. Since 1 ∈ C, the Lee weight of v has to be even. Let us denote by n_{1}, n_{ω} and nω̄ the number of respectively 1’s, ω’s and ω̄’s components in v. Then w_{L}(v) = 2n_{1} + n_{ω} + nω̄, and w_{L}(ωv) = n_{1} + n_{ω} + 2nω̄, from which we deduce:

w_{L}(v) + w_{L}(ωv) + w_{L}(ω̄v) ≡ 0 (mod 4).

In particular this implies that if v is Lee doubly even and either ωv or ω̄v is singly even, then both ωv and ω̄v have to be singly even. Moreover if v is singly even then either ωv or ω̄v, but not both, has to be doubly even. The latter remark gives the number of doubly even vectors of C^{⊥} which do not remain doubly even when they are multiplied by ω or ω̄. The result follows:

T (n, k) = D − \frac{S}{2} .

□

Proof of Theorem 6.1: Let us denote by σ(n, k) the number of doubly even Lee weight subspaces of 𝔽_{4}^{n} containing 1. Using the usual induction procedure of [10] and [19], we deduce:

σ(n, k + 1) = \frac{T (n, k) − 4^{k}}{4^{k}(4^{k} − 1)} σ(n, k).

The theorem follows starting from σ(n, 1) = 1. □

6.2 Type II Codes of Length up to 8

Using the mass formula we check that there is only one Type II code C_{4} of length 4 with generator matrix:

( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & w & w^{2} \end{matrix} ) .

Construction A yields the unique even unimodular lattice in dimension 8 namely E_{8}. There are only two Type II codes of length 8: the code 2C_{4} and the extended binary Hamming code of length 8 considered as a code over 𝔽_{4}. Both yield E_{8}^{2} by Construction A.

7 Invariants

7.1 Type II

We let G_{2} denote the matrix group of order 96 with generators

M = \frac{1}{2} ( \begin{matrix}1 & 2 & 1 \\ 1 & 0 & −1 \\ 1 & −2 & 1 \end{matrix} ) ,

and

M_{L} = ( \begin{matrix}1 & 0 & 0 \\ 0 & i & 0 \\ 0 & 0 & −1 \end{matrix} ) .

Theorem 7.1 The symmetrized weight enumerator of a Type II code over 𝔽_{4} is left invariant by the group G_{2} of order 96.

Proof. The two generators M, M_{L} are respectively the matrix of the MacWilliams relations and the congruence of n_{1}(x) + 2n_{2}(x) modulo 4 for a codeword x. The result follows by definition of Type II codes. □

The group G_{2} has for its Molien series

M_{4}(t) := \frac{1 + t^{8}}{(1 − t^{4})^{2}(1 − t^{12})}.

This means a secondary invariant of order 8 and three primary invariants: two of order 4 and one of order 12. Magma computations give as secondary invariant

s8 := a^{8} + 28 a^{6}c^{2} + 70 a^{4}c^{4} + 28 a^{2}c^{6} + 128 b^{8} + c^{8},

as primary invariants of degree 4

p41 := (b^{2} − ac)^{2} and
p42 := 5 a^{4} + 6 a^{2}c^{2} + 48 ab^{2}c + 16 b^{4} + 5 c^{4},

and as the primary invariant of degree 12

p12 := 495 a^{8}c^{4} + 7920 a^{8}b^{4} + 924 a^{6}c^{6} + 126720 a^{4}b^{8} + 495 a^{4}c^{8}
+66 a^{2}c^{10} + 126720 b^{8}c^{4} + 7920 b^{4}c^{8} + 66 a^{10}c^{2} + 760320 a^{2}b^{8}c^{2}

+1182720 a^{3}b^{6}c^{3} + 66528 a^{5}b^{2}c^{5} + 554400 a^{4}b^{4}c^{4} + 354816 ab^{6}c^{5} + 2640 a^{9}b^{2}c

+31680 a^{7}b^{2}c^{3} + 2640 ab^{2}c^{9} + 31680 a^{3}b^{2}c^{7} + 135168 ab^{10}c + 354816 a^{5}b^{6}c
+221760 a^{2}b^{4}c^{6} + 221760 a^{6}b^{4}c^{2} + 1025 a^{12} + 1025 c^{12} + 4096 b^{12}.

A Taylor series up to order 32 is

1 + 2 t^{4} + 4 t^{8} + 7 t^{12} + 10 t^{16} + 14 t^{20} + 19 t^{24} + 24 t^{28} + 30 t^{32} + O(t^{36}).

Theorem 7.2 The swe of a Type II code over R belongs to the ring R ⊕ s8R where R is either ℂ[p41, p42, p12] or ℂ[f_{4}, (b^{2} − ac)^{2}, f_{12}].

Proof. The first statement should be attributed to Magma. To check the algebraic independence of f_{4}, (b^{2} − ac)^{2}, f_{12} one verifies (in Maple) that the Jacobian of f_{4}, (b^{2} − ac)^{2}, f_{12} does not vanish identically and concludes by the implicit function theorem. □

Remark. The degrees of the basic polynomials in the above rings are divisible by four. This gives an alternative proof of Corollary 3.2.

7.2 Even Type II codes

We let G_{384} denote the matrix group of order 384 with generators M, M_{L} and

M_{H} = ( \begin{matrix}1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & −1 \end{matrix} ) .

The group G_{384} is the unitary reflection group G(4, 1, 3) and has the following Molien series:

\frac{1}{(1 − t^{4})(1 − t^{8})(1 − t^{12})} = 1 + t^{4} + 2 t^{8} + 3 t^{12} + 4 t^{16} + 5 t^{20} + · · · .

Let ℂ[a, b, c]^{G_{384}} denote the invariant polynomial ring with three variables of the group G_{384}. Lemma 7.3

ℂ[a, b, c]^{G_{384}} = ℂ[f_{4}, f_{8}, f_{12}]

where f_{n} = \frac{1}{2}((a + c)^{n} + (a − c)^{n}) + 2^{n−1}b^{n}. Proof. f_{4}, f_{8} and f_{12} are invariant under the group G_{384}, and the Molien series describes the structure of the ring. The result follows. □

8 Shadows

8.1 Symmetrized Weight Enumerators

The following theorem is proved in a standard way: Theorem 8.1 The symmetrized weight enumerator of a Type I code is an isobaric polynomial in

q_{1} = a + c,  (1)
q_{2} = ac − b^{2} and  (2)
q_{3} = b^{2}(a − c)^{2},  (3)

that is

∑_{j,k} a_{j,k}q_{1}^{n−2j−4k}q_{2}^{j}q_{3}^{k}.

Proof. The swe is invariant under a dihedral group of order 8 with generators

M = \frac{1}{2} ( \begin{matrix}1 & 2 & 1 \\ 1 & 0 & −1 \\ 1 & −2 & 1 \end{matrix} ) ,

and

M_{4} = ( \begin{matrix}1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix} ) ,

and Molien series \frac{1}{(1−t)(1−t^{2})(1−t^{4})}. □

We now proceed to study the swe of the shadow. We begin with an easy lemma. Lemma 8.2 If C is a Type I code, then the swe of C_{0} is

swe_{C_{0}}(a, b, c) = \frac{1}{2}(swe_{C}(a, b, c) + swe_{C}(a, ib, −c)).

We can now give a simple expression for the swe of the shadow as a function of the swe of the code. Theorem 8.3 The swe of S is related to the swe of C by the relation

swe_{S}(a, b, c) = swe_{C}(b + (a + c)/2, i(a − c)/2, b − (a + c)/2)

Proof. We proceed as in [6, p. 1323] by computing the swe of its even weight subcode using the preceding lemma, then the swe of C_{0}^{⊥} by the MacWilliams relation

swe_{C^{⊥}}(a, b, c) = \frac{1}{|C|}swe_{C}(a + 2b + c, a − c, a − 2b + c),

and finally the swe of the shadow by subtracting the swe of C from the swe of C_{0}^{⊥}. □

We now give a Gleason-like theorem for the shadow. Theorem 8.4 If the swe of a Type I code C can be expressed as

∑_{j,k} α_{jk}(a + c)^{n−2j−4k}(ac − b^{2})^{j}(b^{2}(a − c)^{2})^{k},

then the swe of its shadow is

∑_{j,k} α_{jk}(−1)^{k}2^{n−2j−6k}(b)^{n−2j−4k}(b^{2} − ac)^{j}(a^{2} − c^{2})^{2k}.

In particular the Lee weight enumerator W_{L}(y) of the shadow is

∑_{k} α_{0k}(−1)^{k}2^{n−6k}y^{n−4k}(1 − y^{4})^{2k}.

The Lee weights of codewords of S are congruent to n modulo 4.

Proof. The first assertion follows from the preceding lemma. The second follows from the first by letting a = 1, c = b^{2}. The third assertion follows from the second or, alternatively, by the fact that the Gray map of the shadow is the shadow of the Gray image of the code. □

8.2 Cosets and Extensions of Type I Codes

Let s and t be vectors such that C = ⟨C_{0}, t⟩ and C_{0}^{⊥} = ⟨C, s⟩. Then C_{2} = (C_{0} + t), C_{1} = (C_{0} + s) and C_{3} = (C_{0} + s + t). Notice that C_{0}^{⊥}/C_{0} is the Klein 4-group for all n.

Let α = s · s and β = s · t. It is easy to determine the orthogonality relations among C_{i}’s if α and β are known, where the result is given in Table 5.

Table 5: Orthogonality Relations

C_{0} C_{1} C_{2} C_{3}
C_{0} 0  0  0  0
C_{1} 0  α  β α + β
C_{2} 0  β  0  β
C_{3} 0 α + β β  α

The Lee weight of s is n (mod 4), hence

2n_{2}(s) + n_{1}(s) ≡ n (mod 4).

If n is even this implies that n_{1}(s) is even and hence α = 0. If n is odd then n_{1}(s) is odd and there are no self-orthogonal vectors in the shadow; moreover α = 1.

It is clear from the construction that β cannot be zero. Notice also that ut is in C_{0}. Since

2n_{2}(t) + n_{1}(t) ≡ 2 (mod 4),

n_{1}(t) is even and ut has doubly-even Lee weight. We have that ut·s = 0 and then u(t·s) = 0 so that t · s = u.

Therefore we have the following lemma.

Lemma 8.5 Suppose that C is a self-dual code of length n. Then Table 6 holds where n is odd and Table 7 holds where n is even with the value in position (i, j) equal to x · y for any vector x ∈ C_{i} and any vector y ∈ C_{j}.

Now we give a method to extend Type I codes using shadow codes.

Table 6: Orthogonality Relations for n odd

C_{0} C_{1} C_{2} C_{3}
C_{0} 0 0 0 0
C_{1} 0 ω 1 ω̄
C_{2} 0 1 0 1
C_{3} 0 ω̄ 1 ω̄

Table 7: Orthogonality Relations for n even

C_{0} C_{1} C_{2} C_{3}
C_{0} 0 0 0 0
C_{1} 0 0 1 1
C_{2} 0 1 0 1
C_{3} 0 1 1 0

Theorem 8.6 Suppose that C is a Type I code of odd length n. Let C^{∗} be the code of length n + 1 obtained by extending C_{0}^{⊥} as follows:

(0, C_{0}), (ω, C_{1}), (1, C_{2}), (ω̄, C_{3}).

Then C^{∗} is a self-dual code of length n + 1. In addition, the swe of C^{∗} is

a swe_{C_{0}}(a, b, c) + c swe_{C_{2}}(a, b, c) + b(swe_{C_{1}}(a, b, c) + swe_{C_{3}}(a, b, c)).

Proof. It is easy to show that C^{∗} is a linear code. The self-orthogonality of the code follows from Lemma 8.5. Since |C^{∗}| = 2^{n+1}, the code is self-dual. A direct calculation determines the swe. □

Similarly we have the following:

Theorem 8.7 Suppose that C is a Type I code of even length n. Let C^{∗} be the code of length n + 2 obtained by extending C_{0}^{⊥} as follows:

(0, 0, C_{0}), (1, 1, C_{0}), (1, 0, C_{2}), (0, 1, C_{2}), (ω, ω, C_{1}), (ω̄, ω̄, C_{1}), (ω, ω̄, C_{3}), (ω̄, 1, C_{3}).

Then C^{∗} is a self-dual code of length n + 2. In addition, the swe of C^{∗} is

(a^{2} + c^{2})swe_{C_{0}}(a, b, c) + 2ac swe_{C_{2}}(a, b, c) + 2b^{2}(swe_{C_{1}}(a, b, c) + swe_{C_{3}}(a, b, c)).

By this construction, codes with high minimum weight cannot be constructed. Remark. Some construction techniques of binary self-dual codes using shadows were given in [3]. Theorems 1 and 2 in [3] may be also obtained from Theorems 8.6 and 8.7, respectively, by Proposition 3.7.

References

[1] A. Bonnecaze, P. Solé, C. Bachoc and B. Mourrain, Type II codes over ℤ_{4}, IEEE Trans. Inform. Theory 43(1997) pp. 969–976.

[2] A. E. Brouwer, “Bounds on the size of linear codes,” Handbook of Coding Theory, edited by V. Pless and W. C. Huffman, North Holland, Amsterdam, 1998.

[3] R.A. Brualdi and V. Pless, Weight enumerators of self-dual codes, IEEE Trans. Inform. Theory 37 (1991), 1222–1225.

[4] A. R. Calderbank, A square root bound on the minimum weight in quasi-cyclic codes, IEEE Trans. Inform. Theory 29 (1983), 332–337.

[5] J.H. Conway and V. Pless, On the enumeration of self-dual codes, J. Combin. Theory Ser. A 28 (1980), 26–53.

[6] J.H. Conway, N.J.A. Sloane, An upper bound on the minimum distance of self-dual codes, IEEE Trans. Inform. Theory 36 (1990), 1319–1333.

[7] J.H. Conway and N.J.A. Sloane, “Sphere Packing, Lattices and Groups (2nd ed.),” Springer-Verlag, New York, 1993.

[8] P. J. Costello, J.S. Hsia, Even Unimodular 12-dimensional quadratic forms over ℚ(\sqrt{5}), Advances in math 64 (1987) 241-278.

[9] S. Dougherty, P. Gaborit, M. Harada, P. Solé, Type II codes over 𝔽_{2} +u𝔽_{2}, IEEE Trans. Inform. Theory 45 (1999)

[10] P. Gaborit, Mass formula for self-dual codes over ℤ_{4} and 𝔽_{q} + u𝔽_{q} rings, IEEE Trans. Inform. Theory 42 (1996), 1222–1228.

[11] P. Gaborit, Quadratic double circulant codes over GF(q), preprint.

[12] K.Ireland, M. Rosen, “A classical Introduction to Modern Number Theory”, second edition, Springer (1990).

[13] M. Karlin, V. Bhargava and S. Tavares, A Note on Extended Quaternary Quadratic Residue Codes and Their Binary Images Inf. and Control 38 (1978), 148–153.

[14] F. Lévy-dit-Vehel, PhD Thesis, Paris VI University (1994).

[15] J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes, IEEE Trans. Inform. Theory 24, (1978), 730-737.

[16] F.J. MacWilliams and N.J.A. Sloane, “The Theory of Error-Correcting Codes,” North-Holland, Amsterdam 1977.

[17] F.J. MacWilliams N.J.A Sloane and J.G. Thompson Good Self-Dual Codes exist Discrete Mathematics 3 (1972), 153–162

[18] C. L. Mallows and N.J.A. Sloane, An upper bound for self-dual codes, Inform. Control 22 (1973), 188–200.

[19] V. Pless, The number of isotropic subspaces in a finite geometry, Atti. Accad. Naz. Lincei Rendic 39 (1965), 418–421.

[20] V. Pless, Q-Codes, J. Combin. Theory Ser. A 43 (1986), 258–276.

[21] E. M. Rains, Shadow bounds for self-dual codes, IEEE Trans. Inform. Theory 44, (1998), 134-139.