Cyclic Self-Dual Z_{4}−Codes ^{∗}

Vera Pless

Department of Mathematics, Statistics and Computer Science

University of Illinois at Chicago, Chicago, IL 60607, USA

E-Mail: pless@math.uic.edu Patrick Solé^{†} Department of Mathematics Macquarie University, NSW 2109, Australia and Zhongqiang Qian

Department of Mathematics, Statistics and Computer Science

University of Illinois at Chicago, Chicago, IL 60607, USA E-Mail: qian@math.uic.edu

July 17, 1996

∗with an appendix by Pieter Moree, Max Planck Institut für Mathematik, Gottfried-Claren Str.26, 53225 Bonn, Germany. moree@antigone.mpim-bonn.mpg.de

†On leave from CNRS, I3S, France

Running Head: Cyclic Self-Dual Z_{4}−Codes Contact Author: Vera Pless Mathematics Department University of Illinois at Chicago 851 S.Morgan St. Chicago, IL 60607 Phone: 312-413-2177 Fax: 312-996-1491 E-Mail: pless@math.uic.edu

Abstract

For n odd, the Z_{4} cyclic code generated by (2) is self-dual. We call this a trivial cyclic self-dual code. When do there exist non-trivial cyclic self-dual codes of odd length n ? We give an answer in this paper by characterizing these n; this yields an existence test for cyclic difference sets. We also give some examples of non-trivial cyclic self-dual codes up to length 39. From these non-trivial cyclic, self-dual codes, construction A yields unimodular lattices of Type I, some of which are extremal; extension and augmentation yields three new extremal Type II codes of length 32, and an extremal selfdual code of Type II in length 40.

1 Introduction

Binary cyclic self-dual codes of odd length do not exist. It is not the case, however, of Z_{4}− cyclic self-dual codes. Some of the first examples, aside from the trivial (2), are supplemented quadratic residue codes the theory of which is developed in [2]. The aim of this paper is to characterize arithmetically the (odd) lengths where such non-trivial cyclic self-dual Z_{4}− codes can exist and to give some examples for short lengths. As the length is odd, it is hopeless to obtain directly Type II codes [3], i.e. codes whose Euclidean weights are multiples of 8 since these exist only for lengths a multiple of 8. It is possible, nonetheless, to obtain Type I Z_{4}− codes, and, accordingly, by construction A, Type I lattices. We obtain, in that way, the only two extremal odd lattices in dimensions 15-47 : the shorter Leech lattice O_{23} in dimension 23 and A_{15}^{+} in dimension 15. Invariant theory enables us to compute the symmetrized weight enumerators of the codes and therefore the theta series of the associated lattices, including the norm and kissing number thereof. En passant, we mention an amusing non-existence arithmetic criterion for cyclic projective planes. We can extend and augment these codes to get length n+1 Z_{4}− codes. In particular, when n = 31, such extensions and augmentations yield 5 inequivalent extremal Type II codes, three of which are new. For n = 40 we obtain in the same manner an extremal self dual code of Type II, and an extremal even lattice of rank 40.

The material is organized as follows. Section 2 recalls some basic facts of life in the Z_{4} world. In section 3 we show that for certain odd n, nontrivial cyclic Z_{4}− self-dual codes exist. Section 4 contains two general construction principles based on, respectively, binary Reed-Muller codes, and block designs. In section 5 we discuss the relation of self-dual codes to unimodular lattices. Section 6 gives examples of Z_{4}− cyclic self-dual codes of odd lengths up to length 39 as well as the unimodular lattices constructed from these codes via Construction A [7]. Appendix A collects the swes we computed. Appendix B, singly-authored by Pieter Moree, contains the proof of Theorem 4 and more arithmetic information on the lengths of non-trivial self-dual cyclic Z_{4}−codes.

2 Basic Facts and Notations:

For a vector x ∈ Z_{4}^{n} if n_{0}(x), n_{1}(x), n_{2}(x) denotes the number of, respectively, 0, ±1, 2 components, then the Lee weight of x is n_{1}(x) + 2n_{2}(x) and the Euclidean weight is n_{1}(x) + 4n_{2}(x). The symmetrized weight enumerator of a Z_{4} code C is denoted by swe_{C}(a, b, c) and is

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

The notion of the dual code C^{⊥} of a Z_{4}− linear code C is understood w.r.t. the standard scalar product, and so is the notion of self-dual code (C = C^{⊥}).

A self-dual Z_{4}− code is said to be of Type II if its Euclidean weights are multiples of 8 [3] and Type I otherwise.

Let μ: Z_{4}[x] → Z_{2}[x] be the map which sends 0, 2 to 0; 1, 3 to 1 and x to x.

With every quaternary code C one can associate two binary linear codes of dimension k_{1} , k_{2} respectively.

1. The residue code Res(C) := μ(C)

2. The torsion code T or(C) defined as the unique binary code B satisfying 2B = {c ∈ C|2c = 0}.

The parameters of a Z_{4}− code will be denoted by (n, 4^{k_{1}}2^{k_{2}}, d_{L}), where d_{L} stands for the minimum nonzero Lee weight. The minimum nonzero Euclidean weight is denoted by d_{E}. In [24] it was shown that any cyclic code over Z_{4} is uniquely generated by fh and 2fg denoted by C = (fh, 2fg), where fgh = x^{n} − 1 and |C| = 4^{degg}2^{degh}. The following observations, generally valid for a Z_{4}−linear code are useful:

Fact 1 If C is cyclic of the form (fh, 2fg) then both Res(C) and T or(C) are cyclic with generators μ(fh) and μf respectively.

Fact 2 If C is self-dual of length n ≡ −1 (mod 4), and contains the all-2 vector than the augmented extended code is self-dual.

Fact 3 If C is self-dual with a basis whose elements have Euclidean weights a multiple of 8, then C is Type II.

Recall that the componentwise product x ⊗ y of two binary vectors of length n say

x = (x_{1}, …, x_{n})

and

y = (y_{1}, …, y_{n})

is

x ⊗ y := (x_{1}y_{1}, x_{2}y_{2}, …, x_{n}y_{n}).

Accordingly the componentwise product of two binary codes C_{1}, C_{2} is

C_{1} ⊗ C_{2} := {x ⊗ y|x ∈ C_{1}, y ∈ C_{2}}.

If C_{1}, C_{2} are two binary codes we can construct a Z_{4}−code from them by the formula:

C_{1} + 2C_{2} := {x + 2y|x ∈ C_{1}, y ∈ C_{2}}.

Fact 4 If C_{1}, C_{2} are binary linear codes, then C_{1} + 2C_{2} is Z_{4}−linear if

C_{1} ⊗ C_{1} ⊆ C_{2}.

3 Cyclic Self-Dual Codes Over Z_{4}

Definition: A polynomial f ∈ Z_{4}[x] has the unique factorization property if whenever

f = f_{1}f_{2} ⋯ f_{k},

and

f = g_{1}g_{2} ⋯ g_{l},

where the f_{i} (g_{i}) are basic irreducible pairwise coprime polynomials, then l = k and by reordering, f_{i} = ϵg_{i} where ϵ is a unit.

Theorem 1: A polynomial f ∈ Z_{4}[x] has the unique factorization property if and only if f is in the set J= {f ∈ Z_{4}[x]| where μf has no repeated zeros in Z_{2} or is in the algebraic closure of Z_{2}}. Proof: If f ∈ J, then

μf = f̄_{1}f̄_{2} ⋯ f̄_{k},

where the f̄_{i} ∈ Z_{2}[x] are irreducible and relatively prime. By Hensel lifting,

f = g_{1}g_{2} ⋯ g_{k},

where μg_{i} = f̄_{i}. Hence the g_{i} are basic irreducible and pairwise coprime. Moreover by [17, page 263], this factorization is unique.

Conversely, if f has the unique factorization property, then

f = f_{1}f_{2} ⋯ f_{k},

where the f_{i} are basic irreducible pairwise coprime polynomials. Hence

μf = f̄_{1}f̄_{2} ⋯ f̄_{k},

and the μf_{i} are irreducible in Z_{2}[x] and relatively prime. Therefore, μf has no repeated roots in Z_{2} or in the algebraic closure of Z_{2}, i.e, f is in J.

Corollary: If n is odd, then x^{n} − 1 has the unique factorization property.

In [24] it was demonstrated that C^{⊥} = (g^{∗}h^{∗}, 2g^{∗}f^{∗}) , where C = (fh, 2fg), fgh = x^{n} − 1 and |C| = 4^{degg}2^{degh}.

Theorem 2: Let C be a cyclic code over Z_{4}, C = (fh, 2fg) where fgh = x^{n} − 1, n odd. Then C is self-dual if and only if f = ϵg^{⋆} and h = ϵh^{⋆}, where ϵ is a unit and g^{⋆} is the reciprocal of g. Proof: The sufficiency is obvious since

C^{⊥} = (g^{∗}h^{∗}, 2g^{∗}f^{∗}).

Now, if C is self-dual, by the above we know that (fh, 2fg) = (g^{⋆}h^{⋆}, 2f^{⋆}g^{⋆}). But these generators are the unique generators of this form. Hence,

fh = g^{⋆}h^{⋆}

and

fhg = g^{⋆}h^{⋆}g = g^{⋆}h^{⋆}f^{⋆} = x^{n} − 1.

Since f^{⋆} and g^{⋆}h^{⋆} are coprime, f^{⋆}|g. Similarly, since

fhf^{⋆} = g^{⋆}h^{⋆}f^{⋆} = fgh,

and g and fh are coprime, g|f^{⋆}. Therefore, g = ϵf^{⋆}. Now, fh = g^{⋆}h^{⋆} = ϵfh^{⋆} where h and f are coprime. Hence, h|h^{⋆}. Similarly, since f^{⋆}h^{⋆} = gh = ϵf^{⋆}h where h^{⋆} and f^{⋆} are coprime , h^{⋆}|h. Therefore, h^{⋆} = ϵh.

Throughout this paper, we use ϕ to represent the Hensel Lifting operator.

Theorem 3: Non-trivial cyclic, self-dual codes of length n exist if and only if −1 ≢ 2^{i} (mod n) for any i. Proof: By Theorem 2, non-trivial cyclic self-dual codes of length n exist whenever there is an f(x) dividing x^{n} −1 where f(x) ≠ f(x)^{⋆}. We show that this happens iff −1 ≢ 2^{i} (mod n), for any i.

Let f(x) ∈ Z_{2}[x] be irreducible and f(x)|x^{n}−1, then f(x) = ∏_{i∈C_{u}}(x−β^{i}) where C_{u} is the cyclotomic coset of n that contains the smallest element u and β is a primitive n^{th} root of unity [22]. It is easy to see that f^{⋆}(x) = ∏_{i∈C_{−u}}(x − β^{i}). It is not hard to verify that ϕ(f)^{⋆} = ϕ(f^{⋆}). Now if −1 ≢ 2^{i} (mod n) for any i, then C_{1} ≠ C_{−1}, hence, f ≠ f^{⋆} where f = ∏_{i∈C_{1}}(x − β^{i}) and the code (ϕ(f)ϕ(h), 2ϕ(f)ϕ(f^{⋆})) is a non-trivial self-dual code where ff^{⋆}h = x^{n} − 1 .

Conversely, if non-trivial cyclic self-dual codes exist, then there is an f|x^{n} − 1 with f ≠ f^{⋆}. Hence −1 ≢ 2^{i} (mod n), for any i because otherwise C_{u} = C_{−u} for all cyclotomic cosets C_{u} and f = f^{⋆} for any f|x^{n} − 1.

We remark that the hypothesis of the preceding theorem is not satisfied if n = p a prime ≡ ±3 (mod 8), for then 2 is not a quadratic residue (mod p), and Euler’s criterion yields 2^{\frac{p−1}{2}} ≡ −1 (mod p).

Lemma: Let p and q be two different odd primes and let the order of 2 (mod p) and (mod q) be 2^{l}i and 2^{l}j respectively, where i is odd, j is even and l ≥ 1, then −1 is not a power of 2 (mod pq). Proof: If −1 ≡ 2^{k} (mod pq) for some k, then −1 ≡ 2^{k} (mod p) and 2^{2k} ≡ 1 (mod p). Hence 2^{l}i|2k, i.e, 2^{l−1}i|k. Therefore,

2^{2^{l−1}ik/2^{l−1}i} ≡ (−1)^{k/2^{l−1}i} ≡ −1 (mod p).

Hence k/2^{l−1}i is odd, 2^{l−1} divides k exactly.

On the other hand, −1 ≡ 2^{k} (mod q). Hence 2^{2k} ≡ 1 (mod q). Therefore, 2^{l}j|2k, i.e, 2^{l−1}j|k and k must be divisible by 2^{l}, a contradiction.

It should be noted that the odd n for which the hypothesis of Theorem 3 holds are precisely those for which there is a self-dual binary cyclic code of length 2n [27]. The next theorem characterizes n such that the hypothesis in Theorem 3 holds.

Theorem 4: −1 is not a power of 2 (mod n) iff n is either divisible by

• a prime r ≡ −1 (mod 8)

• or a prime r ≡ 1 (mod 8) where the order of 2 (mod r) is odd

• or a prime p and a prime q, where p and q are as in the above Lemma.

Proof:

We only prove the sufficiency. The necessary condition is proved in Appendix B by Moree.

Case 1: We first consider a prime r where r ≡ 1 (mod 8) and the order of 2 (mod r) is odd (this sometimes happens) or r ≡ −1 (mod 8). In the last case, (r − 1)/2 is odd. Since 2 is a quadratic residue, 2^{r−1/2} ≡ 1 (mod r) so that the order of 2 (mod r) is odd. As the order of 2 (mod r) is odd and the order of −1 is even, −1 can not be a power of 2.

Case 2: We suppose that r is as case 1 and r|n. If −1 ≡ 2^{k} (mod n) for some i, let k = (r − 1)s + t where 0 ≤ t < r − 1, then −1 ≡ 2^{t} (mod r), a contradiction.

Proof of the case when n is divisible by a prime p and a prime q, where p and q are as in the Lemma, is analogous to that of the Lemma.

Remark. When we tried to characterize the n as stated in the above theorem, we got a chance to discuss the problem with Moree. Later, he did completely characterize the n where −1 is a power of 2 (mod n).

Corollary: Non-trivial odd length n, cyclic self-dual codes exist over Z_{4} iff n is an odd integer as in Theorem 4. In particular, non-trivial odd length n, cyclic self-dual codes exist over Z_{4} if n is divisible by a prime p ≡ 3 (mod 8) and a prime q ≡ 5 (mod 8). Proof: By the above theorem, when a prime p ≡ 3 (mod 8) and a prime q ≡ 5 (mod 8) both divide n, then −1 is not a power of 2 (mod n) for the following reasons.

(a) When p ≡ 3 (mod 8), −1 ≡ 2^{i} (mod p), for i odd.

(b) When q ≡ 5 (mod 8), −1 ≡ 2^{j} (mod q), for j even.

Statement (a) is true because −1 is a square (mod p) if and only if p ≡ 1 (mod 4). But when p ≡ 3 (mod 8), −1 is not a square (mod p), hence i must be odd.

For (b) −1 is a square (mod q), say −1 ≡ α^{2} (mod q). Then 2^{j} ≡ α^{2} (mod q) implies

2^{j(q−1)/2} ≡ α^{2(q−1)/2} ≡ α^{q−1} ≡ 1 (mod q).

But 2 is not a square (mod q) so that 2^{q−1/2} ≡ −1 (mod q). Therefore, (−1)^{j} ≡ 1 (mod q) and j must be even.

4 General Constructions

4.1 Binary Reed-Muller Codes

In [2] the following codes were introduced.

C_{m,r} := RM(r, m) + 2RM(m − r − 1, m).

These were shown to be of Type II for 0 ≤ r ≤ \frac{m−1}{3}. Denote by C^{x} and C^{+} the punctured, respectively punctured and expurgated codes of the binary code C along an arbitrary coordinate position. We define the codes

D_{m,r} := RM(r, m)^{+} + 2RM(m − r − 1, m)^{x}.

It is clear from their definition that the extended augmented codes are C_{m,r}. As for C_{m,r} the swe is easy to compute by applying the formula for joint weight enumerators [15]. They are Z_{4}−linear by Fact IV. It is easy to check that, using the same weight divisibility properties of binary Reed Muller codes as in [3], that these are self dual and of Type I for 0 ≤ r ≤ \frac{m−1}{3}. See the examples in section 6 for n = 15, 31 to see D_{4,1} and D_{5,1}. Further, the Gray map image of these are equivalent to binary cyclic self-dual codes with generator polynomial (μf)^{2}μh [27, 14]. We obtain in that way an infinite family of binary cyclic self-dual codes. In general Theorem 1 of [14] shows that any binary cyclic self dual code with generator g_{1}^{2}g_{2} (Cf formula (3) of [27]) is equivalent to the Gray image of the Z_{4}− code

(g_{1}g_{2}) + 2(g_{1}),

which is not, however, always Z_{4}−linear.

4.2 Irreducible Cyclic Codes

A generalization of D_{m,1} is the following.

Proposition: Let C_{2} be an [n, k, d] irreducible, cyclic binary code the weights of which are multiples of 8. Then C := C_{2} + 2C_{2}^{⊥} is a Z_{4}−linear selfdual cyclic Type I code with d_{E} = min(d, 4d^{⊥}). Its Gray image is a linear cyclic self-dual code of length 2n, and minimum distance min(d, 2d^{⊥}).

Proof: Observe firstly that C_{2} and its dual C_{2}^{⊥} are obtained by decimation (Cf. [16, §1]) by a factor (2^{k} − 1)/n from, respectively, the Simplex and Hamming codes of length 2^{k} − 1, in the sense that every word in these codes is obtained as a column in an array

x_{1} x_{2} … x_{n}
x_{n+1} x_{n+2} … x_{2n}
…
x_{2^{k}−n} … x_{2^{k}−2} x_{2^{k}−1}

where x_{1} … x_{2^{k}−1} is a word in the decimated code. Secondly, the componentwise product of the simplex code with itself is in the Hamming code. Linearity of C follows now on applying Fact IV.

Self-duality follows from the weight congruence property.

Properties of the Gray image follow from [14].

This happens [16] for instance for n = 45, 51, 85, 89, 93, 105, 117.

4.3 Cyclic Difference Sets

In [12], Klemm shows that if A denotes the adjacency matrix of a 2−(v, k, λ) design with odd λ and 4||k − λ then C := D + 2j is a self dual Z_{4} code where j denotes the all-one vector of length v and D is the Z_{4}−span of the rows of A . If the above design admits a cyclic automorphism of order v then the resulting Z_{4} code is cyclic. In particular this covers the case of a Desarguesian projective plane P G(2, 4) which is well-known to have a Singer cycle . One of the three codes of length 21 in section 6 is obtained in that way. Moreover, the construction S_{Q} is a special case of that construction when the underlying design is Paley-Hadamard.

On the other hand, if there is no nontrivial cyclic Z_{4} code of length s^{2} + s + 1 this implies that there is no cyclic P G(2, s). This is the case e.g. for s = 12 when n = 157 which is a prime congruent to 5 mod 8, or for s = 20 when n = 421 is the same kind of prime, but fails for s = 28 when n = 813 = 3.271 and 271 is a prime congruent to −1 mod 8. A similar result can be found in [23, Theorem 20]. Several possible parameters (extracted from Jungnickel’s survey [11, 312-316]) of cyclic difference sets that can be ruled out in that way are listed in the following table. The last column lists the integers a < v such that 2^{a} ≡ −1 (mod v).

\begin{matrix}k − λ & v & k & λ & a \\ 12 & 157 & 13 & 1 & 26 \\ 20 & 121 & 25 & 5 & 55 \\ 28 & 171 & 35 & 7 & 19 \\ 28 & 149 & 37 & 9 & 74 \end{matrix}

5 Unimodular Lattices

An n-dimensional lattice L in R^{n} is the set of integer linear combinations of n linearly independent vectors v_{1}, v_{2}, ⋯, v_{n}. The dual of L, denoted by L^{⋆}, is the set {x ∈ R^{n}| (x, a) ∈ Z, for all a ∈ L}. The lattice L is called integral if L ⊆ L^{⋆}. An integral lattice L with det L=1 ( or L = L^{⋆}) is called unimodular. The norm of an x ∈ L is the inner product (x, x) = ∑_{i=1}^{n} x_{i}^{2} and is denoted by N(x). The norm N(L) of L is the minimum of N(x) over all nonzero x. If N(x) is even for all x ∈ L, L is called even. A unimodular lattice L is of Type II if L is even, otherwise it is of Type I. The theta series θ_{L}(q) is the formal power series

θ_{L}(q) = ∑_{x∈L} q^{(x,x)} = ∑_{m=0}^{m=∞} N_{m}q^{m},

where N_{m} is the number of vectors x ∈ L with norm m. The kissing number τ(L) of a lattice L is N_{N(L)}.

If C is a Z_{4} linear code of length n, then applying Construction A [7] to Z_{4} codes we have a lattice L(C) which is

L(C) = {x ∈ (Z/2)^{n}| 2x ≡ c (mod 4) for some c ∈ C}.

If C has the generator matrix

( \begin{matrix}I_{k_{1}} & A & B \\ 0 & 2I_{k_{2}} & 2C \end{matrix} )

then the lattice L(C) has the generator matrix

1/2 ( \begin{matrix}I_{k_{1}} & A & B \\ 0 & 2I_{k_{2}} & 2C \\ 0 & 0 & 4I_{n−k_{1}−k_{2}} \end{matrix} ) .

As in the binary case [7, Chapter 7], using the above generator matrix of L(C) we can easily show that the following theorem is true.

Theorem 5 (i) detL(C)=2^{2n−4k_{1}−2k_{2}}; (ii) L(C) is integral if and only if C ⊆ C^{⊥}; (iii) L(C) is of Type I if and only if C is of Type I; (iv) L(C) is of Type II if and only if C is of Type II.

(v) N(L(C)) = min(4, d_{E}(C)/4) (vi)θ_{L(C)}(q^{4}) = swe_{C}(θ_{4Z}(q), θ_{4Z+1}(q), θ_{4Z+2}(q))

Note that the first non-trivial coefficient of the theta series

θ_{L}(q) = 1 + τ(L)q^{N(L)} + ...

is the kissing number τ(L) which therefore is uniquely determined by the swe. In the next section, we use table 16.7 of [7] to identify the Type I lattices obtained by construction A.

6 Examples of codes of length n ≤ 39

If C is a self-dual Z_{4} code of length n, we can extend this code by adding an over-all parity check and then augment the code by adjoining the all 1’s vector. The resulting code will be denoted by C̃. When n + 1 ≡ 0 (mod 4), C̃ is a length (n + 1) self-dual code. In particular, when n is a prime p ≡ −1 (mod 8) ,

x^{p} − 1 = (x − 1)m_{Q}(x)m_{N}(x)

where m_{Q}(x) = ∏_{i∈Q}(x − β^{i}) and m_{N}(x) = ∏_{i∈N}(x − β^{i}) are polynomials in Z_{2}[x], β is a primitive pth root of unity in an extension of Z_{2} and Q, N are sets of quadratic residues and non-quadratic residues in Z_{p} respectively. The Z_{4} quadratic residue codes defined in terms of idempotent generators [24] are the same as the cyclic codes generated by ϕ(m_{Q}(x)), ϕ(m_{N}(x)), ϕ((x − 1)m_{Q}(x)) and ϕ((x − 1)m_{N}(x)). These Z_{4} quadratic residue codes are denoted by Q_{4}, N_{4}, Q̄_{4} and N̄_{4} respectively [2]. The codes denoted by S_{Q} and S_{N} are the codes Q̄_{4}, N̄_{4} augmented with the all 2’s vector [2]. S_{Q} (S_{N}) is the code same as the cyclic code generated by f = ϕ(m_{Q}(x)) (ϕ(m_{N}(x))), h = x − 1 and g = ϕ(m_{N}(x)) (ϕ(m_{Q}(x))).

It is not hard to verify that S̃_{N} and S̃_{Q} are the extended Z_{4} quadratic residue codes. Since S_{Q} ⊆ Q̄_{4}, the extension of S_{Q} is contained in the extention of Q_{4} which is denoted by Q̂_{4}. Since Q̂_{4} contains the all 1′s vector and S̃_{N}, Q̂_{4} both are self-dual, S̃_{N} = Q̂_{4}. By the fact that the group of the Z_{4} quadratic residue codes is transitive, we can use the formula [3.3, 1], to find the symmetrized weight enumerator of S_{Q} and S_{N}.

By Theorems 3 and 4, for odd n ≤ 39, non-trivial cyclic self-dual codes exist for n = 7, 15, 21, 23, 31, 35 and 39.

¿From [10, Theorem 1.1] we can say that two Z_{4}− cyclic codes of length n, where gcd(n, ϕ(n)) = 1, are equivalent iff they are equivalent by a multiplier.

(i) n = 7:

x^{7} − 1 = (x − 1)f(3f^{⋆})

where f = (x^{3} + 3x^{2} + 2x + 3). Here the only non-trivial cyclic self-dual code C(7, 4^{3}2, 4) is S_{Q}. The extended augmented code is the celebrated octacode [7].

(ii) n = 15:

x^{15} − 1 = (x − 1)(x^{4} + x^{3} + x^{2} + x + 1)(x^{2} + x + 1)ff^{⋆}

where f = x^{4} +2x^{2} +3x+1. The only cyclic self-dual code is C(15, 4^{4}2^{7}, 6) = (fh, 2fg) where

h = (x − 1)(x^{4} + x^{3} + x^{2} + x + 1)(x^{2} + x + 1) and
g = x^{4} + 3x^{3} + 2x^{2} + 1.

It is interesting to notice that the residue code is the simplex code S_{15} and that the torsion code is the Hamming code H_{15}. It is easy to check directly (Cf §3.1) that S_{15} + 2H_{15} is also a cyclic self dual Z_{4} code, therefore isomorphic to the preceding one. Using the Gray map we get a self dual Type I binary code with parameters (30, 15, 6). This is the code r_{30} in the classification of [21]. Using construction A we obtain a Type I lattice with kissing number 240: this is the unique extremal Type I lattice in dimension 15 called A_{15}^{+} [17, Chap. 19]. The extended and augmented code is Type II with d_{E} = 8, therefore extremal. Consequently the lattice associated by construction A is an extremal Type II lattice. From the said table [7, 16.7] and [7, p.194] we know it to be either D_{16}^{+} or E_{8}^{2}. From the swe we check that the kissing number is 480. Using the Gray map we get a self dual Type II binary code with parameters [32, 16, 8]. Comparing this with the squaring construction for Reed Muller codes we see that it is RM(2, 5).

(iii) n = 21:

x^{21} − 1 = (x − 1)(x^{2} + x + 1)f_{1}f_{1}^{⋆}f_{2}(3f_{2}^{⋆})

where f_{1} = (x^{6} + 2x^{5} + 3x^{4} + 3x^{2} + x + 1) and f_{2} = (x^{3} + 2x^{2} + x + 3). There are three inequivalent (their swe’s are different) non-trivial cyclic self-dual codes of length 21.The first is C_{21,1}(21, 4^{6}2^{9}, 6) = (f_{1}h, 2f_{1}f_{1}^{⋆}) where

h = x^{9} + x^{8} + x^{7} + 3x^{2} + 3x + 3.

Construction A yields a lattice of norm 2 and kissing number 84 (V = A_{3}^{7}). The second is C_{21,2}(21, 4^{3}2^{15}, 4) = (f_{2}h, 2f_{2}f_{2}^{⋆}) where

h = x^{15} + 3x^{14} + x^{8} + 3x^{7} + x + 3.

Construction A yields again a lattice of norm 2 and kissing number 84. ¿From the table [7, 16.7], we see that this lattice must be similar to L(C_{21,1}). The last code is C_{21,3}(21, 4^{9}2^{3}, 4) = (f_{1}f_{2}h, 2f_{1}f_{2}f_{1}^{⋆}f_{2}^{⋆}) where h = x^{3} + 3. This gives a lattice of norm 1, therefore not included in table 16.7 of [7]. The extended augmented codes are not self-dual, as Fact 2 does not apply.

(iv) n = 23:

x^{23} − 1 = (x − 1)f(3f^{⋆}) where
f = (x^{11} + 2x^{10} + 3x^{9} + 3x^{7} + 3x^{6} + 3x^{5} + 2x^{4} + x + 3).

The only non-trivial cyclic self-dual code C(23, 4^{11}2, 10) is S_{Q} (S_{N}). As in [2], we obtain the shorter Leech lattice with norm 3 and kissing number 4600.

(v) n = 31:

x^{31} − 1 = (x − 1)f_{1}(3f_{1}^{⋆})f_{2}(3f_{2}^{⋆})f_{3}(3f_{3}^{⋆})

where

f_{1} = x^{5} + 3x^{2} + 2x + 3,
f_{2} = x^{5} + 2x^{4} + 3x^{3} + x^{2} + 3x + 3 and
f_{3} = x^{5} + 3x^{4} + x^{2} + 3x + 3.

Note, for future use, that the cyclotomic classes C_{1}, C_{3}, C_{5} correspond respectively to f_{1}, f_{2}^{∗}, f_{3}. By the criterion in [10] we easily determine that there are five inequivalent non-trivial cyclic self-dual codes of length 31. These are as follows:

(1) C_{31,1}(31, 4^{5}2^{21}, 6) = (f_{1}h, 2f_{1}f_{1}^{⋆}) where

h = (x − 1)f_{2}f_{2}^{∗}f_{3}f_{3}^{∗},

i.e.

h = x^{21} + 2x^{20} + 3x^{19} + x^{18} + x^{17} + 3x^{16} + 3x^{13} + 3x^{11} + x^{10}

+x^{8} + x^{5} + 3x^{4} + 3x^{3} + x^{2} + 2x + 3.

(2) C_{31,2}(31, 4^{10}2^{11}, 10) = (f_{1}f_{2}h, 2f_{1}f_{2}f_{1}^{⋆}f_{2}^{⋆}) where

h = (x − 1)f_{3}f_{3}^{∗},

that is

h = x^{11} + 3x^{10} + 2x^{9} + 3x^{7} + 2x^{6} + 2x^{5} + x^{4} + 2x^{2} + x + 3.

(3) C_{31,3}(31, 4^{10}2^{11}, 10) = (f_{1}f_{2}^{⋆}h, 2f_{1}f_{2}f_{1}^{⋆}f_{2}^{⋆}) where h = (x − 1)f_{3}f_{3}^{∗}.

(4) C_{31,4}(31, 4^{15}2, 12) = (f_{1}f_{2}f_{3}h, 2f_{1}f_{2}f_{3}f_{1}^{⋆}f_{2}^{⋆}f_{3}^{⋆}) where h = x − 1.

(5) C_{31,5}(31, 4^{15}2, 12) = (f_{1}f_{2}^{⋆}f_{3}h, 2f_{1}f_{2}f_{3}f_{1}^{⋆}f_{2}^{⋆}f_{3}^{⋆}), where h = x − 1.

Among these five codes, C_{31,2} and C_{31,3} have the same symmetrized weight enumerator as do C_{31,4} and C_{31,5}. In the notation of §3.1 , C_{31,1} = D_{5,1}.

¿From the above codes we can construct five inequivalent self-dual codes of length 32, i.e, C̃_{31,i} where i = 1, 2, 3, 4, 5. Note that C̃_{31,1} = C_{5,1}. Among them C̃_{31,4} is the extended Q.R code and C̃_{31,5} is the extended R.M code. As shown in [6] these two codes yield by construction A the only two unimodular lattices in dimension 32 of norm 4 with an automorphism of order 31 [25]. One or the other of these two lattices can also be obtained by construction A applied to C̃_{31,i} where i = 1, 2, 3. These three new codes are of Type II as can be shown by considering a generator matrix and using Fact 3. By the extremality of the associated lattice they are extremal in the sense of [3]. (vi) n = 35 :

x^{35} − 1 = f_{3}f_{3}^{⋆}f_{12}f_{12}^{⋆}h_{0},

with f_{3} = x^{3} + 2x^{2} + x + 3,

f_{12} = x^{12} + 2 x^{11} + 3 x^{10} + x^{9} + x^{8} + 3 x^{7} + 2 x^{6} + 2 x^{5} + x^{4} + 2 x^{3} + 3 x^{2} + x + 1,

and

h_{0} = x^{5} − 1 = (x − 1)(x^{4} + x^{3} + x^{2} + x + 1).

There are four inequivalent (again by the criterion in [10] ) cyclic self dual codes as follows,

(1) h = h_{0}, f = f_{3}f_{12}

(2) h = h_{0}, f = f_{3}^{⋆}f_{12} (3) h = h_{0}f_{3}f_{3}^{⋆}, f = f_{12} Its residue code is irreducible cyclic with check polynomial μf_{12}^{∗} by Fact

1, and minimum distance 8, by [16].

(4) h = h_{0}f_{12}f_{12}^{⋆}, f = f_{3}

Its residue code is a degenerate cyclic code with period 7 and irreducible check polynomial μf_{3}^{∗}.

The extended augmented codes are self-dual Type I codes. (vii) n = 39 :

x^{39} − 1 = hff^{⋆},

where

h = (x − 1)(x^{2} + x + 1)(x^{12} + x^{11} + … + x + 1),

and

f = x^{12} + x^{11} − x^{10} − x^{9} + 2x^{6} + x^{5} − x^{4} + x^{3} − x^{2} + 2x + 1.

There is a unique non-trivial self-dual cyclic code : (fh, 2ff^{⋆}), with residue code an irreducible cyclic code with check polynomial μf^{∗}, by Fact 1, and the torsion code is its dual. Same irreducible cyclic codes have been completely enumerated [16], and the weight enumerator of their duals are accessible via the MacWilliams transform. The extended augmented code of length 40 is self-dual by Fact 2 and Type II by Fact 3. The minimum distance of Res(C) is 12 [16], and the minimum distance of T or(C) is 3, and this still holds after augmentation by the all-one vector since the maximum weight of the residue code is 24 and the torsion code already contains the all-one vector. Therefore for the extended augmented code d_{E} ≥ 12, and since d_{E} must be a multiple of 8 we get d_{E} ≥ 16, which gives an extremal Type II code in the sense of [3]. These facts imply that the associated lattice is Type II extremal of dimension 40. It would be interesting to compare it to the other extremal even lattices of that dimension [20]. Note: In Appendix A, we listed swes of the above examples up to length 31. swe(C_{31,1}) and swe(C_{31,2}) have been computed by finding the Hamming weight distribution of their residue and torsion codes. This information determines enough coefficients in swe(C_{31,1}) and swe(C_{31,2}) so that we can find the total weight enumerators. If we knew that C̃_{31,1} and C̃_{31,2} had transitive automorphism groups, we could use the formula in [2] to get these results. C̃_{31,4} is a Q.R code. swe(C̃_{31,4}) has been computed many times [3, 24, 5].

Appendix A

The symmetrized weight enumerators

n = 7, the only non-trivial cyclic self-dual code of C(7, 4^{3}2, 4) has weight distribution:

a^{7} + 7 a^{4} c^{3} + 7 a^{3} c^{4} + c^{7} + 14 a^{3} b^{4} + 42 a^{2} b^{4} c

+ 42 a b^{4} c^{2} + 14 b^{4} c^{3}

n = 15, the only non-trivial cyclic self-dual code has weight distribution: swe(C(15, 4^{4}2^{7}, 6))=

a^{15} + 35 a^{12} c^{3} + 105 a^{11} c^{4} + 168 a^{10} c^{5} + 280 a^{9} c^{6} + 435 a^{8} c^{7} + 435 a^{7} c^{8} + 280 a^{6} c^{9} + 168 a^{5} c^{10} + 105 a^{4} c^{11} + 35 a^{3} c^{12} + c^{15} + (240 a^{7} + 1680 a^{6} c + 5040 a^{5} c^{2} + 8400 a^{4} c^{3} + 8400 a^{3} c^{4} + 5040 a^{2} c^{5} + 1680 a c^{6} + 240 c^{7})b^{8}

swe(C̃(16, 4^{4}2^{8}, 8))=

a^{16} + 140 a^{12} c^{4} + 448 a^{10} c^{6} + 870 a^{8} c^{8} + 448 a^{6} c^{10} + 140 a^{4} c^{12} + 2048 b^{16} + c^{16} + ( 480 a^{8} + 13440 a^{6} c^{2} + 33600 a^{4} c^{4} + 13440 a^{2} c^{6} + 480 c^{8} ) b^{8}

n = 21: swe(C_{21,1}(21, 4^{6}2^{9}, 6))=

a^{21} + 28 a^{18} c^{3} + 84 a^{17} c^{4} + 273 a^{16} c^{5} + 924 a^{15} c^{6} + 1956 a^{14} c^{7} + 2982 a^{13} c^{8} + 4340 a^{12} c^{9} + 5796 a^{11} c^{10} + 5796 a^{10} c^{11} + 4340 a^{9} c^{12} + 2982 a^{8} c^{13} + 1956 a^{7} c^{14} + 924 a^{6} c^{15} + 273 a^{5} c^{16}

+ 84 a^{4} c^{17} + 28 a^{3} c^{18} + c^{21} + (2688 a^{9} + 24192 a^{8} c

+ 96768 a^{7} c^{2} + 225792 a^{6} c^{3} + 338688 a^{5} c^{4} + 338688 a^{4} c^{5}

+ 225792 a^{3} c^{6} + 96768 a^{2} c^{7} + 24192 a c^{8} + 2688 c^{9})b^{12} + (

84 a^{13} + 1092 a^{12} c + 6552 a^{11} c^{2} + 24024 a^{10} c^{3} + 60060 a^{9} c^{4}

+ 108108 a^{8} c^{5} + 144144 a^{7} c^{6} + 144144 a^{6} c^{7} + 108108 a^{5} c^{8}

+ 60060 a^{4} c^{9} + 24024 a^{3} c^{10} + 6552 a^{2} c^{11} + 1092 a c^{12} + 84 c^{13})b^{8}

swe(C̃_{21,1}(22, 4^{6}2^{10}, 8))=

a^{22} + 112 a^{18} c^{4} + 1197 a^{16} c^{6} + 4938 a^{14} c^{8} + 10136 a^{12} c^{10}

+ 10136 a^{10} c^{12} + 4938 a^{8} c^{14} + 1197 a^{6} c^{16} + 112 a^{4} c^{18}

+ 32768 b^{22} + c^{22} +

( 5376 a^{8} + 150528 a^{6} c^{2} + 376320 a^{4} c^{4} + 150528 a^{2} c^{6} + 5376 c^{8} )

b^{14} + (26880 a^{9} c + 322560 a^{7} c^{3} + 677376 a^{5} c^{5} + 322560 a^{3} c^{7}

+ 26880 a c^{9})b^{12} + (8064 a^{11} c + 147840 a^{9} c^{3} + 532224 a^{7} c^{5}

+ 532224 a^{5} c^{7} + 147840 a^{3} c^{9} + 8064 a c^{11})b^{10} + (84 a^{14}

+ 7644 a^{12} c^{2} + 84084 a^{10} c^{4} + 252252 a^{8} c^{6} + 252252 a^{6} c^{8}

+ 84084 a^{4} c^{10} + 7644 a^{2} c^{12} + 84 c^{14})b^{8}

swe(C_{21,2}(21, 4^{3}2^{15}, 4))=

a^{21} + 21 a^{19} c^{2} + 189 a^{18} c^{3} + 756 a^{17} c^{4} + 2457 a^{16} c^{5} + 6804 a^{15} c^{6}

+ 14724 a^{14} c^{7} + 25326 a^{13} c^{8} + 36484 a^{12} c^{9} + 44310 a^{11} c^{10}

+ 44310 a^{10} c^{11} + 36484 a^{9} c^{12} + 25326 a^{8} c^{13} + 14724 a^{7} c^{14}

+ 6804 a^{6} c^{15} + 2457 a^{5} c^{16} + 756 a^{4} c^{17} + 189 a^{3} c^{18} + 21 a^{2} c^{19} + c^{21} + (3584 a^{9} + 32256 a^{8} c + 129024 a^{7} c^{2} + 301056 a^{6} c^{3}

+ 451584 a^{5} c^{4} + 451584 a^{4} c^{5} + 301056 a^{3} c^{6} + 129024 a^{2} c^{7}

+ 32256 a c^{8} + 3584 c^{9})b^{12}

swe(C̃_{21,2}(22, 4^{3}2^{16}, 4))=

a^{22} + 21 a^{20} c^{2} + 945 a^{18} c^{4} + 9261 a^{16} c^{6} + 40050 a^{14} c^{8} + 80794 a^{12} c^{10}

+ 80794 a^{10} c^{12} + 40050 a^{8} c^{14} + 9261 a^{6} c^{16} + 945 a^{4} c^{18}

+ 21 a^{2} c^{20} + 262144 b^{22} + c^{22} + (35840 a^{9} c + 430080 a^{7} c^{3}

+ 903168 a^{5} c^{5} + 430080 a^{3} c^{7} + 35840 a c^{9})b^{12} + (10752 a^{11} c

+ 197120 a^{9} c^{3} + 709632 a^{7} c^{5} + 709632 a^{5} c^{7} + 197120 a^{3} c^{9}

+ 10752 a c^{11})b^{10}

swe(C_{21,3}(21, 4^{9}23, 4))=

a^{21} + 21 a^{18} c^{3} + 21 a^{17} c^{4} + 147 a^{15} c^{6} + 297 a^{14} c^{7} + 147 a^{13} c^{8}

+ 343 a^{12} c^{9} + 1071 a^{11} c^{10} + 1071 a^{10} c^{11} + 343 a^{9} c^{12}

+ 147 a^{8} c^{13} + 297 a^{7} c^{14} + 147 a^{6} c^{15} + 21 a^{4} c^{17} + 21 a^{3} c^{18} + c^{21}

+ (2744 a^{9} + 24696 a^{8} c + 98784 a^{7} c^{2} + 230496 a^{6} c^{3}

+ 345744 a^{5} c^{4} + 345744 a^{4} c^{5} + 230496 a^{3} c^{6} + 98784 a^{2} c^{7}

+ 24696 a c^{8} + 2744 c^{9})b^{12} + (588 a^{13} + 3528 a^{12} c + 8820 a^{11} c^{2}

+ 15876 a^{10} c^{3} + 37632 a^{9} c^{4} + 89964 a^{8} c^{5} + 144648 a^{7} c^{6}

+ 144648 a^{6} c^{7} + 89964 a^{5} c^{8} + 37632 a^{4} c^{9} + 15876 a^{3} c^{10}

+ 8820 a^{2} c^{11} + 3528 a c^{12} + 588 c^{13})b^{8} + (42 a^{17} + 126 a^{16} c

+ 126 a^{15} c^{2} + 630 a^{14} c^{3} + 2352 a^{13} c^{4} + 3528 a^{12} c^{5} + 4410 a^{11} c^{6}

+ 10962 a^{10} c^{7} + 20832 a^{9} c^{8} + 20832 a^{8} c^{9} + 10962 a^{7} c^{10} + 4410 a^{6} c^{11} + 3528 a^{5} c^{12} + 2352 a^{4} c^{13} + 630 a^{3} c^{14} + 126 a^{2} c^{15} + 126 a c^{16} + 42 c^{17})b^{4}

swe(C̃_{21,3}(22, 4^{9}2^{4}, 6))=

a^{22} + 42 a^{18} c^{4} + 147 a^{16} c^{6} + 444 a^{14} c^{8} + 1414 a^{12} c^{10} + 1414 a^{10} c^{12} + 444 a^{8} c^{14} + 147 a^{6} c^{16} + 42 a^{4} c^{18} + 4096 b^{22} + c^{22} + ( 43008 a^{3} c + 43008 a c^{3} ) b^{18} + ( 150528 a^{6} c^{2} + 301056 a^{4} c^{4} + 150528 a^{2} c^{6} ) b^{14} + (27440 a^{9} c + 329280 a^{7} c^{3} + 691488 a^{5} c^{5} + 329280 a^{3} c^{7} + 27440 a c^{9})b^{12} + ( 175616 a^{9} c^{3} + 526848 a^{7} c^{5} + 526848 a^{5} c^{7} + 175616 a^{3} c^{9} ) b^{10} + (588 a^{14} + 12348 a^{12} c^{2} + 53508 a^{10} c^{4} + 234612 a^{8} c^{6} + 234612 a^{6} c^{8} + 53508 a^{4} c^{10} + 12348 a^{2} c^{12} + 588 c^{14})b^{8} + ( 168 a^{17} c + 756 a^{15} c^{3} + 5880 a^{13} c^{5} + 15372 a^{11} c^{7} + 41664 a^{9} c^{9} + 15372 a^{7} c^{11} + 5880 a^{5} c^{13} + 756 a^{3} c^{15} + 168 a c^{17})b^{4}

n = 23, The weight distribution of the only cyclic non-trivial length 23 code C(23, 4^{11}2, 10):

a^{23} + 253 a^{16} c^{7} + 506 a^{15} c^{8} + 1288 a^{12} c^{11} + 1288 a^{11} c^{12} + 506 a^{8} c^{15} + 253 a^{7} c^{16} + c^{23} + (8096 a^{7} + 56672 a^{6} c + 170016 a^{5} c^{2} + 283360 a^{4} c^{3} + 283360 a^{3} c^{4} + 170016 a^{2} c^{5} + 56672 a c^{6} + 8096 c^{7})b^{16} + (2576 a^{11} + 28336 a^{10} c + 141680 a^{9} c^{2} + 425040 a^{8} c^{3} + 850080 a^{7} c^{4} + 1190112 a^{6} c^{5} + 1190112 a^{5} c^{6} + 850080 a^{4} c^{7} + 425040 a^{3} c^{8} + 141680 a^{2} c^{9} + 28336 a c^{10} + 2576 c^{11})b^{12} + (1012 a^{14} c + 7084 a^{13} c^{2} + 28336 a^{12} c^{3}

+ 85008 a^{11} c^{4} + 191268 a^{10} c^{5} + 318780 a^{9} c^{6} + 404800 a^{8} c^{7}

+ 404800 a^{7} c^{8} + 318780 a^{6} c^{9} + 191268 a^{5} c^{10} + 85008 a^{4} c^{11}

+ 28336 a^{3} c^{12} + 7084 a^{2} c^{13} + 1012 a c^{14})b^{8}

n = 31:

swe(C_{31,1}(31, 4^{5}2^{21}, 6))=

a^{31} + 155 a^{28} c^{3} + 1085 a^{27} c^{4} + 5208 a^{26} c^{5} + 22568 a^{25} c^{6}

+ 82615 a^{24} c^{7} + 247845 a^{23} c^{8} + 628680 a^{22} c^{9} + 1383096 a^{21} c^{10}

+ 2648919 a^{20} c^{11} + 4414865 a^{19} c^{12} + 6440560 a^{18} c^{13}

+ 8280720 a^{17} c^{14} + 9398115 a^{16} c^{15} + 9398115 a^{15} c^{16}

+ 8280720 a^{14} c^{17} + 6440560 a^{13} c^{18} + 4414865 a^{12} c^{19}

+ 2648919 a^{11} c^{20} + 1383096 a^{10} c^{21} + 628680 a^{9} c^{22}

+ 247845 a^{8} c^{23} + 82615 a^{7} c^{24} + 22568 a^{6} c^{25} + 5208 a^{5} c^{26}

+ 1085 a^{4} c^{27} + 155 a^{3} c^{28} + c^{31} + (63488 a^{15} + 952320 a^{14} c

+ 6666240 a^{13} c^{2} + 28887040 a^{12} c^{3} + 86661120 a^{11} c^{4}

+ 190654464 a^{10} c^{5} + 317757440 a^{9} c^{6} + 408545280 a^{8} c^{7}

+ 408545280 a^{7} c^{8} + 317757440 a^{6} c^{9} + 190654464 a^{5} c^{10}

+ 86661120 a^{4} c^{11} + 28887040 a^{3} c^{12} + 6666240 a^{2} c^{13}

+ 952320 a c^{14} + 63488 c^{15})b^{16}

swe(C_{31,2}(31, 4^{10}2^{11}, 10)) =

a^{31} + 186 a^{26} c^{5} + 806 a^{25} c^{6} + 2635 a^{24} c^{7} + 7905 a^{23} c^{8} + 18910 a^{22} c^{9}

+ 251100 a^{17} c^{14} + 301971 a^{16} c^{15} + 301971 a^{15} c^{16}

+ 41602 a^{21} c^{10} + 85560 a^{20} c^{11} + 142600 a^{19} c^{12} + 195300 a^{18} c^{13} + 251100 a^{14} c^{17} + 195300 a^{13} c^{18} + 142600 a^{12} c^{19}

+ 85560 a^{11} c^{20} + 41602 a^{10} c^{21} + 18910 a^{9} c^{22} + 7905 a^{8} c^{23}

+ 2635 a^{7} c^{24} + 806 a^{6} c^{25} + 186 a^{5} c^{26} + c^{31} + (190464 a^{11}

+ 2095104 a^{10} c + 10475520 a^{9} c^{2} + 31426560 a^{8} c^{3}

+ 62853120 a^{7} c^{4} + 87994368 a^{6} c^{5} + 87994368 a^{5} c^{6}

+ 62853120 a^{4} c^{7} + 31426560 a^{3} c^{8} + 10475520 a^{2} c^{9}

+ 2095104 a c^{10} + 190464 c^{11})b^{20} + (33728 a^{15} + 505920 a^{14} c

+ 3541440 a^{13} c^{2} + 15346240 a^{12} c^{3} + 46038720 a^{11} c^{4}

+ 101285184 a^{10} c^{5} + 168808640 a^{9} c^{6} + 217039680 a^{8} c^{7}

+ 217039680 a^{7} c^{8} + 168808640 a^{6} c^{9} + 101285184 a^{5} c^{10}

+ 46038720 a^{4} c^{11} + 15346240 a^{3} c^{12} + 3541440 a^{2} c^{13}

+ 505920 a c^{14} + 33728 c^{15})b^{16} + (1240 a^{19} + 23560 a^{18} c

+ 212040 a^{17} c^{2} + 1201560 a^{16} c^{3} + 4806240 a^{15} c^{4}

+ 14418720 a^{14} c^{5} + 33643680 a^{13} c^{6} + 62481120 a^{12} c^{7}

+ 93721680 a^{11} c^{8} + 114548720 a^{10} c^{9} + 114548720 a^{9} c^{10}

+ 93721680 a^{8} c^{11} + 62481120 a^{7} c^{12} + 33643680 a^{6} c^{13}

+ 14418720 a^{5} c^{14} + 4806240 a^{4} c^{15} + 1201560 a^{3} c^{16}

+ 212040 a^{2} c^{17} + 23560 a c^{18} + 1240 c^{19})b^{12}

swe(C_{31,4}(31, 4^{15}2, 12)) =

a^{31} + 155 a^{24} c^{7} + 465 a^{23} c^{8} + 5208 a^{20} c^{11} + 8680 a^{19} c^{12}

+ 18259 a^{16} c^{15} + 18259 a^{15} c^{16} + 8680 a^{12} c^{19} + 5208 a^{11} c^{20}

+ 465 a^{8} c^{23} + 155 a^{7} c^{24} + c^{31} + (79360 a^{7} + 555520 a^{6} c + 1666560 a^{2} c^{5} + 555520 a c^{6} + 79360 c^{7})b^{24} + (166656 a^{11}

+ 1833216 a^{10} c + 9166080 a^{9} c^{2} + 27498240 a^{8} c^{3}

+ 54996480 a^{7} c^{4} + 76995072 a^{6} c^{5} + 76995072 a^{5} c^{6}

+ 54996480 a^{4} c^{7} + 27498240 a^{3} c^{8} + 9166080 a^{2} c^{9}

+ 1833216 a c^{10} + 166656 c^{11})b^{20} + (33728 a^{15} + 550560 a^{14} c

+ 3853920 a^{13} c^{2} + 16596160 a^{12} c^{3} + 49788480 a^{11} c^{4}

+ 109722144 a^{10} c^{5} + 182870240 a^{9} c^{6} + 234895680 a^{8} c^{7}

+ 234895680 a^{7} c^{8} + 182870240 a^{6} c^{9} + 109722144 a^{5} c^{10}

+ 49788480 a^{4} c^{11} + 16596160 a^{3} c^{12} + 3853920 a^{2} c^{13}

+ 550560 a c^{14} + 33728 c^{15})b^{16} + (1240 a^{19} + 23560 a^{18} c

+ 182280 a^{17} c^{2} + 1032920 a^{16} c^{3} + 4220960 a^{15} c^{4}

+ 12662880 a^{14} c^{5} + 29407840 a^{13} c^{6} + 54614560 a^{12} c^{7}

+ 82026000 a^{11} c^{8} + 100254000 a^{10} c^{9} + 100254000 a^{9} c^{10}

+ 82026000 a^{8} c^{11} + 54614560 a^{7} c^{12} + 29407840 a^{6} c^{13}

+ 12662880 a^{5} c^{14} + 4220960 a^{4} c^{15} + 1032920 a^{3} c^{16}

+ 182280 a^{2} c^{17} + 23560 a c^{18} + 1240 c^{19})b^{12} + (7440 a^{20} c^{3}

+ 37200 a^{19} c^{4} + 119040 a^{18} c^{5} + 357120 a^{17} c^{6} + 892800 a^{16} c^{7}

+ 1785600 a^{15} c^{8} + 2976000 a^{14} c^{9} + 4166400 a^{13} c^{10}

+ 4895520 a^{12} c^{11} + 4895520 a^{11} c^{12} + 4166400 a^{10} c^{13}

+ 2976000 a^{9} c^{14} + 1785600 a^{8} c^{15} + 892800 a^{7} c^{16}

+ 357120 a^{6} c^{17} + 119040 a^{5} c^{18} + 37200 a^{4} c^{19} + 7440 a^{3} c^{20})b^{8} swe(C̃_{31,1}(32, 4^{5}2^{22}, 8))=

a^{32} + 1240 a^{28} c^{4} + 27776 a^{26} c^{6} + 330460 a^{24} c^{8} + 2011776 a^{22} c^{10}

+ 7063784 a^{20} c^{12} + 14721280 a^{18} c^{14} + 18796230 a^{16} c^{16}

+ 14721280 a^{14} c^{18} + 7063784 a^{12} c^{20} + 2011776 a^{10} c^{22}

+ 330460 a^{8} c^{24} + 27776 a^{6} c^{26} + 1240 a^{4} c^{28} + 67108864 b^{32}

+ c^{32} + (126976 a^{16} + 15237120 a^{14} c^{2} + 231096320 a^{12} c^{4}

+ 1016823808 a^{10} c^{6} + 1634181120 a^{8} c^{8} + 1016823808 a^{6} c^{10}

+ 231096320 a^{4} c^{12} + 15237120 a^{2} c^{14} + 126976 c^{16})b^{16}

swe(C̃_{31,2}(32, 4^{10}2^{12}, 12))=

a^{32} + 992 a^{26} c^{6} + 10540 a^{24} c^{8} + 60512 a^{22} c^{10} + 228160 a^{20} c^{12}

+ 446400 a^{18} c^{14} + 603942 a^{16} c^{16} + 446400 a^{14} c^{18}

+ 228160 a^{12} c^{20} + 60512 a^{10} c^{22} + 10540 a^{8} c^{24} + 992 a^{6} c^{26}

+ 2097152 b^{32} + c^{32} + (6094848 a^{11} c + 111738880 a^{9} c^{3}

+ 402259968 a^{7} c^{5} + 402259968 a^{5} c^{7} + 111738880 a^{3} c^{9}

+ 6094848 a c^{11})b^{20} + (67456 a^{16} + 8094720 a^{14} c^{2}

+ 122769920 a^{12} c^{4} + 540187648 a^{10} c^{6} + 868158720 a^{8} c^{8}

+ 540187648 a^{6} c^{10} + 122769920 a^{4} c^{12} + 8094720 a^{2} c^{14}

+ 67456 c^{16})b^{16} + (39680 a^{19} c + 2261760 a^{17} c^{3}

+ 30759936 a^{15} c^{5} + 153799680 a^{13} c^{7} + 333232640 a^{11} c^{9}

+ 333232640 a^{9} c^{11} + 153799680 a^{7} c^{13} + 30759936 a^{5} c^{15}

+ 2261760 a^{3} c^{17} + 39680 a c^{19})b^{12}

Appendix B

Study of the integers n where n|2^{k} + 1 for some k

P ieterMoree

We say n ≥ 1 is good if it divides 2^{k} + 1 for some k ≥ 1 and bad otherwise. Brauer [4] showed that a bad integer divides at least one integer of the form 2^{2k−1} − 1. It is an elementary observation that if n is good, then ord_{p}(2) is even for every prime divisor p of n. The primes for which ord_{p}(2) is even were first studied by Sierpinski [26]. His result was extended by Brauer [4] and later by Hasse [9]. The latter proved that the Dirichlet density of the primes p for which ord_{p}(2) is even is \frac{17}{24}. To this end he used algebraic number theory to express the Dirichlet density in terms of degrees of certain Kummer fields. It is not too difficult to compute these degrees, making use of some basic facts on cyclotomic number fields. Wiertelak in a series of papers ([28, 29, 30, 31, 32]), went well beyond Hasse. Several authors have studied good primes, see e.g. [1, 14, 19, 32] and the references cited there. In contrast little seems to be known about good integers.

Although 3 and 5 are both good, 15 isn’t. Thus the necessary condition for n to be good that all its prime divisors are good, is not sufficient. The following result gives a necessary and sufficient condition for n to be good.

Theorem 1 [18] A number n is good iff there exists an e ≥ 1 such that 2^{e} exactly divides ord_{p}(2) for every prime p dividing n.

Theorem 1 motivates, for e ≥ 0, the following definition:

C_{e} = {p : 2^{e}||ord_{p}(2)}.

By 2^{e}||a, we mean that 2^{e} divides a and 2^{e+1} does not divide a. Notice that the primes not in C_{0} are all good. It is not difficult to compute the Dirichlet density of C_{e}, see e.g. [28, Theorem 1]. Let δ_{e} be the Dirichlet density of the set C_{e}. Then δ_{0} = δ_{1} = \frac{7}{24}, δ_{2} = \frac{1}{3} and δ_{e} = \frac{1}{3} · \frac{1}{2^{e}} for e ≥ 3.

The following result that is easily proved using special cases of quadratic, biquadratic and octic reciprocity (cf. [4]), gives some algebraic information on the sets C_{e}.

Theorem 2 Let p be an odd prime and 2^{r}||p − 1. Then at most one of the following holds:

(i) If p ≡ 7(mod 8), then p ∈ C_{0};

(ii) If r = 3 and p is represented by the form 65X^{2} + 256XY + 256Y^{2}, then p ∈ C_{0};

(iii) If p ≡ 3(mod 8), then p ∈ C_{1};

(iv) If r = 3 and p is represented by the form X^{2} + 256Y^{2}, then p ∈ C_{1};

(v) If p ≡ 5(mod 8), then p ∈ C_{2};

(vi) If r ≥ 4 and p is represented by the form 65X^{2} + 256XY + 256Y^{2}, then p ∈ C_{r−2};

(vii) If p is represented by the form 17X^{2} + 64XY + 64Y^{2}, then p ∈ C_{r−1}.

The smallest odd prime that is not covered is 337. The Dirichlet density of the primes not covered is \frac{1}{32}.

¿From Theorems 1 and 2 it follows, for example, that if n is composed only of primes p such that p ≡ 3(mod 8), then n is good. The same holds with 3(mod 8) replaced by 5(mod 8). Theorem 2 gives some algebraic information on good numbers; Theorem 3 analytic information. It gives an estimate for G(x), the number of good integers not exceeding x.

Theorem 3 [18] Let 0 < ϵ ≤ \frac{1}{24} and let r be the smallest integer such that \frac{1}{3} · \frac{1}{2^{r+3}} ≤ ϵ. Then there exist positive constants c_{1}, ⋯, c_{r} such that

G(x) = \frac{x}{log x}(c_{1} log^{\frac{1}{3}} x + c_{2} log^{\frac{7}{24}} x + ∑_{k=0}^{r} c_{3+k} log^{\frac{1}{3} · \frac{1}{2^{k+3}}} x + O(log^{ϵ} x)). (1)

The implied constant may depend on ϵ.

It follows that asymptotically G(x) ∼ c_{1}x log^{− \frac{2}{3}} x. In particular almost all integers are bad.

Notice that an integer n has a, not necessarily proper, divisor m ≡ 7(mod 8), if and only if either there is a prime p ≡ 7(mod 8), or both a prime p ≡ 3(mod 8) and a prime q ≡ 5(mod 8) dividing n. Using Theorem 2 one then deduces:

Lemma 1 If n has a divisor m such that m ≡ 7(mod 8), then n is bad.

The bad numbers n < 100 that are ≢ 7(mod 8) are 21, 35, 45, 49, 51, 69, 73, 75, 77, 85, 89, 91 and 93. The bad numbers n < 200 that have no divisors ≡ 7(mod 8) are 51, 73, 85, 89, 123, 153 and 187. There are O(x log^{−1/2} x) integers ≤ x that have no divisors ≡ 7(mod 8). By equation (1), O(x log^{−1/2} x) of these are bad. Thus Lemma 1 is enough to determine almost all bad integers.

More details will appear in [18], where the more general problem of estimating the number of divisors m of numbers of the form a^{k} +b^{k} is considered (for fixed a and b). The case a = 2 and b = 1 turns out to be atypical.

References

[1] C. Ballot, Density of prime divisors of linear recurrences, Mem. of the Am. Math. Soc. 551, 1995.bibitemB C. Ballot, Density of prime divisors of linear recurrences, Mem. of the Am. Math. Soc. 551, 1995.

[2] A.Bonnecaze, P.Solé, and A.R.Calderbank, Quaternary Quadratic residue Codes and Unimodular Lattices, IEEE Transactions on Information Theory, 41:366-377, 1995.

[3] A.Bonnecaze, P.Solé, C. Bachoc, B.Mourrain,Quaternary Type II Codes, IEEE Transactions on Information Theory, submitted.

[4] A. Brauer, A note on a number theoretical paper of Sierpinski, Proc. Amer. Math. Soc. 11 (1960), 406-409.

[5] A.R.Calderbank, N.J.A. Sloane, Double Circulant Codes over Z_{4} and Unimodular Lattices, J. of Alg. Comb. submitted in 1995.

[6] R. Chapman, P. Solé, Universal Codes and Unimodular Lattices, preprint 1995.

[7] J.H.Conway and N.J.A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, 1988.

[8] J.H.Conway and N.J.A. Sloane, ‘A new upper bound on the minimal distance of self-dual codes’, IEEE IT-36 (1990) , 1319-1333.

[9] H. Hasse, Über die Dichte der Primzahlen p für die eine vorgegebene ganzrationale Zahl a ≠ 0 von gerader bzw, ungerader Ordnung mod. p ist, Math. Ann. 166 (1966), 19-23.

[10] W.Cary Huffman, Vanessa Job and Vera Pless, Multipliers and Generalized Multipliers of Cyclic Objects and Cyclic Codes, J.Combin.Theory 62, No.2, 183-215, March 1993.

[11] D. Jungnickel, Difference Sets, in J.H. Dinitz, D.R. Stinson Contemporary Design Theory, Wiley (1992). 11

[12] M. Klemm, ‘Sebstduale Codes ueber dem Ring der Ganzen Zahlen modulo 4’, Arch. Math. Vol. 53 (1989) 201-207.

[13] J. C. Lagarias, The set of primes dividing the Lucas numbers has density 2/3, Pacific J. Math. 118 (1985), 449-461.

[14] J.H. van Lint,‘Repeated Root Cyclic Codes’, IEEE Trans. on Inform. Theory IT-37 (1991) 343-345.

[15] F. J. MacWilliams, C. L. Mallows, N.J. A. Sloane, ‘Generalizations of Gleason ’s Theorem on Weight Enumerators of Self-Dual Codes’, IEEE IT-18 (1972) 794-805.

[16] F. J. MacWilliams, J. Seery, The weight distribution of some minimal cyclic codes, IEEE Trans. Inform. Th. IT-27 (1981) 796-801.

[17] B.R.McDonald, Finite Rings with Identity, Dekker, NY, 1974.

[18] P. Moree, On the divisors of a^{k} + b^{k}, preprint.

[19] R. W. K. Odoni, A conjecture of Krishnamurty on decimal periods and some allied problems, J. Number Theory 13 (1981), 303-319.

[20] M. Ozeki,‘ Examples of Even Unimodular Extremal Lattices of rank 40 and their Siegel Theta-Series of degree 2′, J. of Number Th. 28 (1988) 119-131.

[21] V. Pless,‘ The children of the (32,16) doubly even codes’, IEEE Inform. Th. IT-24 (1978) 738-746.

[22] V.Pless, Introduction to the Theory of Error-Correcting Codes, Second Edition, Wiley Interscience, 1989.

[23] V.Pless, Q-Codes, J.Combin.Theory 43, No.2, 258-276, 1986.

[24] V.Pless and Z.Qian, Cyclic Codes and Quadratic Residue Codes over Z_{4}, preprint, 1994.

[25] H.-G. Quebemann, Zur Klassifikation unimodularer Gitter mit Isometrie von Primzahlordnung, Crelle 326 (1981)158-170.

[26] W. Sierpinski, Sur une décomposition des nombres premiers en deux classes, Collect. Math. 10 (1958), 81-83.

[27] N.J.A. Sloane, J.G. Thompson,‘ Cyclic Self-Dual Codes’, IEEE Trans. on Inform. Theory, IT-29 (1981) 364-366.

[28] K. Wiertelak, On the density of some sets of primes. I, II, Acta Arith. 34 (1977/78), 183-196, 197-210.

[29] K. Wiertelak, On the density of some sets of primes. III, Funct. Approx. Comment. Math. 10 (1981), 93-103.

[30] K. Wiertelak, On the density of some sets of primes. IV, Acta Arith. 43 (1984), 177-190.

[31] K. Wiertelak, On the density of some sets of integers, Funct. Approx. Comment. Math. 19 (1990), 71-76.

[32] K. Wiertelak, On the density of some sets of primes p, for which ord_{p}(n) = d. Funct. Approx. Comment. Math. 21 (1992), 69-73.