SPHERICAL 3-DESIGNS AND LATTICES FROM BINARY CODES

JACQUES MARTINET (*)

Abstract. Lifting binary codes over ℤ^{n} produces lattices, with some of which we construct spherical 3-designs. The case when the set of minimal vectors is a 3-design corresponds to the notion of strongly eutactic lattices, introduced by Boris Venkov in [V]. In this paper we consider a kind of counterpart of this notion for (linear) binary codes, with special emphasis on codes of weight 3.

1. Introduction

Let C be a linear binary code of length n. Denote by E the Euclidean space ℝ^{n}, equipped with its canonical basis B = (ε_{1}, …, ε_{n}) and its canonical scalar product (x_{i}) · (y_{i}) = ∑ x_{i}y_{i}, and by ℤ^{n} the lattice with ℤ-basis B. The norm of x ∈ E is N(x) = x·x, the Gram matrix of the basis (e_{1}, …, e_{n}) is Gram(B) = (e_{i} · e_{j}), the determinant of B is det(B) = det(Gram(B)).

The minimum of a lattice Λ ⊂ E is min Λ = min_{x∈Λ∖{0}} N(x). We set S(Λ) = {x ∈ Λ | N(x) = min Λ}, (the set of minimal vectors of Λ), s(Λ) = \frac{|S|}{2} (the [half-]kissing number of Λ), and define the determinant of Λ as the determinant of one of its bases over ℤ.

With each word α of C we associate the vector e_{α} = ^{\frac{∑_{α(i)=1} ε_{i}}{2}} , and with C the lattice

Λ_{C} = ⟨ℤ^{n}, e_{α} | α ∈ C⟩ .

The aim of this note is to study for such lattices Λ_{C} some notions related to perfection and eutaxy, the definitions of which we recall below. We also consider a second construction for even codes C, namely

L_{C} = ⟨𝔻_{n}, e_{α} | α ∈ C⟩ .

where 𝔻_{n} = {x ∈ ℤ^{n} | ∑ x_{i} ≡ 0 mod 2} is the even sublattice of ℤ^{n}.

For reasons which will be explained in the next section we shall essentially consider four situations:

(a) Λ_{C} with wt(C) = 3 ; (b) Λ_{C} with wt(C) = 4 ;

(c) L_{C} with wt(C) = 6 ; (d) L_{C} with wt(C) = 8.

Key words and phrases. Euclidean lattices, binary codes, spherical designs, eutaxy (*) Univ. Bordeaux, IMB & CNRS, UMR 5251.

Consider a finite, symmetric set S of vectors of E having the same norm, and set s = \frac{1}{2}|S|; the definitions below will then be applied to the set S of minimal vectors of a lattice, and sometimes more generally to various layers of the lattice. The notions relative to perfection and eutaxy that we recall below stem from papers of Korkine & Zolotareff (1873–1877) and Vorononoi (1907–1908); more details can be read in [M1], Chapter 3. Given a subspace F of E, we denote by p_{F} ∈ End^{s}(E) the orthogonal projection to F, and for x ∈ E, x ≠ 0, we denote by p_{x} the orthogonal projection to the line ℝ x.

The perfection rank of S is the rank r = r(S) in End^{s}(E) of the p_{x}, x ∈ S. One has r ≤ \frac{n(n+1)}{2} = dim End^{s}(E). The difference \frac{n(n+1)}{2} − r is the perfection co-rank of S. We say that S is perfect if its perfection co-rank is zero. A relation ∑_{x∈S/±1} λ_{x}p_{x} = 0 is called a perfection relation.

A eutaxy relation is a relation of the form Id = ∑_{x∈S/±1} ρ_{x}p_{x} with real coefficients ρ_{x}. Since Tr(p_{x}) = 1, we have ∑_{x∈S/±1} ρ_{x} = n. We say that S is weakly eutactic if the set of eutaxy relations on S is not empty, in which case it is an affine space over the real vector space of perfection relations. We say that S is semi-eutactic (resp. eutactic) if there exists a eutaxy relation with ρ_{x} ≥ 0 (resp. ρ_{x} > 0). We say that a lattice is extreme if its Hermite invariant achieves a local minimum (then necessarily strict modulo similarities). By a theorem of Vorononoi, a lattice is extreme if and only if it is perfect and eutactic.

Finally, we say that S is strongly eutactic if there exists a eutaxy relation with equal coefficients ρ_{x}, then equal to \frac{n}{s}; equivalent formulation: ∑_{x∈S/±} p_{x} is proportional to the identity. This condition amounts to saying that S is a spherical 3-design; see [V], Sections 3 and 6 for the application to lattices of the Delsarte-Goethals-Seidel theory of spherical designs; see also [B], [B-V], and [M-V1].

In the next section we consider the connection between codes and lattices with respect to the various notions of eutaxy and perfection. The following sections are then devoted to (linear, binary) codes, especially of weight 3, but we also consider related codes of various weights, which show up for instance as dual codes, or even subcodes or extended codes (by the parity check) of odd codes.

2. Lifting binary codes

Recall that C is a code of length n. We assume that C is non-zero, and denote by k ≥ 1 its dimension and d its weight or minimal distance. (For short, C is a (linear, binary) [n, k]- or [n, k, d]-code.) The code C is even if all its weights are even and odd otherwise, and doubly even if all its weights are divisible by 4. The dual of C is

C^{⊥} = {y ∈ 𝔽_{2}^{n} | ∀ x ∈ C, x · y = 0} ,

and we say that C is self-orthogonal if C ⊂ C^{⊥} and self-dual if C = C^{⊥}; note that doubly even codes are self-orthogonal.

Codes lift to lattices Λ_{C}, of minimum min(1, \frac{d}{4}), and L_{C}, of minimum min(2, \frac{d}{4}). We shall often rescale Λ_{C} to minimum min(4, d) and L_{C} to minimum min(8, d). In these scales they become integral, with determinants det(Λ_{C}) = 4^{n−k} and det(L_{C}) = 4^{n−k+1}, respectively. Then Λ_{C} is even is if and only if C is even whereas L_{C} is even for every C, and these lattices are primitive if and only if C is not self-dual. Otherwise, they become integral when rescaled to half their minimum (and are then primitive because C is not zero).

To calculate s = s(Λ_{C}) in full generality, we need the invariant below of C.

Definition 2.1. Let M_{m} = M_{m}(C) be the number of words of C having a given weight m. When m is the weight d of C, we omit the subscript m.

Proposition 2.2. If d = 3, d = 4, d ≥ 5, then s(Λ_{C}) = 4M, 8M + n, n, respectively; if d = 6, d = 8, d ≥ 10, then s(L_{C}) = 16M, 64M + n(n − 1), n(n − 1), respectively.

Proof. Lifting a word x of weight wt(x) produces 2^{wt(x)−1} pairs of vectors of norm \frac{wt(x)}{4} in Λ_{C}; the same kind of calculation applies to L_{C}. □

[In the proposition above we have disregarded construction L_{C} with wt(C) = 2 or 4, since replacing ℤ^{n} by 𝔻_{n} does not produce interesting new sets of minimal vectors. We also left aside lattices Λ_{C} constructed with codes of weight w ≤ 2. These yield lattices of minimum 1 or 2, and the sublattice generated by vectors of norm 1 or 2 is a root lattice, thus isometric to an orthogonal sum of well-known irreducible lattices (ℤ, 𝔸_{n}, n ≥ 1, 𝔻_{n}, n ≥ 4, 𝔼_{n}, n = 6, 7, 8). A look at the determinants of lifts of doubly even codes generated by words of weight 4 shows that we may only obtain 𝔻_{n} (n ≥ 4 even), 𝔼_{7}, and 𝔼_{8}, which shows that these codes are concatenations of irreducible codes that we may call d_{n} (n ≥ 4 even), e_{7}, and e_{8}. The latter two are related to Hamming codes on which we shall return below; d_{n}, n = 2m is obtained by dividing {1, …, n} into the m blocks {1, 2}, …, {n − 1, n} and taking for words all words with support an even number of blocks.]

Example 2.3. We give here a few examples of construction L_{C}. Note that all lattices quoted below are strongly eutactic by Theorem 3.6 of next section.

(1) Doubling the code d_{4} (resp. d_{6}) we obtain for L_{C} a scaled copy of 𝔼_{8} (resp. of the laminated lattice Λ_{12}^{max}, for which s = 64 × 3 + 12 × 11 = 324; see [M2], Section 8.2).

(2) There are unique [15, 4, 8]- and [16, 5, 8]-codes. The corresponding lattices L_{C} are the laminated lattices Λ_{15} and Λ_{16} (the Barnes-Wall lattice BW_{16}). Note that BW_{16} as well as 𝔻_{4}, 𝔼_{7} and 𝔼_{8} which can be obtained by construction Λ_{C}, are spherical designs of level ℓ ≥ 5.

(3) Similarly rescaling the unique self-dual [16, 6, 6]-code of [B-G] produces the lattice O_{16} (with even sublattice Λ_{16}), again a spherical 5-design.

(4) Using the binary Golay code G, we obtain a lattice with s = 759×64+24× 23 = 49128, indeed the orthogonal in the Leech lattice of a norm-6 vector. To obtain the Leech lattice Λ_{24} we must use codes over ℤ/4ℤ, for instance, adjoin to L the vector \frac{1}{4}(−3, 1^{23}) ; this construction is better understood in terms of Kneser neighbours of Λ_{G}.

Recall that the dual lattice of a lattice Λ is

Λ^{∗} = {x ∈ ℝ^{n} | ∀ y ∈ Λ, x · y ∈ ℤ} .

We have [Λ_{C} : ℤ^{n}] = 2^{d}, hence [ℤ^{n} : Λ_{C^{⊥}}] = 2^{d}, and [ℤ^{n} : (2ℤ)^{n}] = 2^{n}. Now Λ_{C^{⊥}} contains (2ℤ)^{n} and we have [Λ_{C^{⊥}} : (2ℤ)^{n}] = 2^{n−k} = 2^{dim C^{⊥}}, which implies

Λ_{C^{⊥}}^{∗} = ⟨(2ℤ)^{n}, e_{w} | w ∈ C^{⊥}⟩ .

3. Perfection and eutaxy

We keep the notation of the previous sections.

Lemma 3.1. The set S = \{\frac{±ε_{1}±···±ε_{n}}{2} \} is strongly eutactic.

Proof. We apply the projection formula p_{e}(x) = \frac{e·x}{e·e} e with e ∈ S and and x equal to an ε_{i}. We have e · ε_{i} = ±\frac{1}{2} and e · e = \frac{n}{4}, hence p_{e}(ε_{i}) = ±\frac{2}{n} e, so that the component of p_{e}(ε_{i}) is +\frac{1}{n} on ε_{i}, whereas it is ±\frac{1}{n} on ε_{j}, j ≠ i, with the sign of ε_{j} in e. The sum of the p_{e}(ε_{i}) on a half-system of S is

\frac{1}{2} ∑_{e∈S} p_{e}(ε_{i}) = \frac{2^{n−1}}{n} ε_{i} ,

since there are in the sum above the same number of minus signs on the ε_{j}, j ≠ i. This shows that ∑_{e∈S/±} p_{e} and \frac{2^{n−1}}{n} Id, which agree on the basis B for E, are indeed equal. □

Proposition 3.2. Let C be a [n, k, 4] binary code. Then:

(1) In situation (b), Λ_{C} is eutactic.

(2) In situation (d), L_{C} is extreme.

(3) In situation (b), Λ_{C} is perfect if and only if every pair i, j of coordinates belongs to the support of a weight 4 word.

(4) In situation (a), Λ_{C} is perfect if and only if every pair i, j of coordinates belongs to the support of a (unique) weight 3 word.

Proof. The proof of eutaxy in situation (b) is dealt with in [K-M-S] by induction on the number w of weight-4 words of C, using when w = 0 the fact that ℤ^{n} is (strongly) eutactic. The same kind of proof applies to situation (d) with 𝔻_{n} instead of ℤ^{n} when w = 0. In this latter case, since L_{C} contains the perfect lattice 𝔻_{n} scaled to min L_{C}, it is moreover perfect, hence extreme by Voronoi’s theorem.

Assertion (3) is also proved (in a more general form) in [K-M-S], (Lemma 7.2), and this proof adapts easily to the last two assertions. □

Remark 3.3. Property (4) in the proposition above amounts to saying that the code C (of weight 3 in this case) is perfect in the sense of coding theory; perfect codes are then the generalized Hamming codes defined in Section 4 below. The notions which appear in Assertions (3) and (5) are less restrictive than the corresponding notions of perfection for codes. In [K-M-S], for situation (b), such codes are called complete codes.

We now consider unions of sets S having a common length m ≤ n.

Proposition 3.4. Let k, m (m ≤ n) be positive integers, let E_{j}, j = 1, …, k

be subsets of \{1, 2, …, n\} of cardinality m, and for each j, let S_{j} = ^{\frac{∑_{i∈E_{j}} ε_{j}}{2}} . Then S = ∪_{j} S_{j} is strongly eutactic if and only if the number of sets E_{j} containing a given index i is independent of i.

Proof. For each j ≤ k, denote by F_{j} be the span of the ε_{i}, i ∈ E_{j}, and for i = 1, …, n, let μ_{i} be the number of j ≤ k with i ∈ E_{j}.

The set S is strongly eutactic if and only if the sum T := ∑_{j=1}^{k} ∑_{e∈S_{j}} p_{e} is proportional to the identity. Using Lemma 3.1, we see that the inner sum is equal to \frac{2^{m−1}}{m} p_{F_{j}} = \frac{2^{m−1}}{m} ∑_{i∈E_{j}} p_{ε_{i}}. We thus have T = \frac{2^{m−1}}{m} ∑_{i=1}^{n} μ_{i}p_{ε_{i}} , which shows that T is proportional to the identity if and only if the μ_{i} have a common value μ (and then we have ∑_{e∈S/±} = \frac{2^{m−1}μ}{m} Id). □

We now return to the data of a code C and the lattices Λ_{C} and L_{C}.

Definition 3.5. Let C be a (linear, binary) code and let m be a weight of C.

(1) We denote by t_{m}(i) the number of words w of weight m of C such that w(i) = 1.

(2) We say that C is m-equidistributed if t_{m}(i) does not depend on i; the common value of the t_{m}(i) is then called the m-distribution weight of C and denoted by t_{m} = t_{m}(C).

We omit the notation m when m = wt(C) is the weight of C, and also say that an equidistributed code is strongly eutactic.

In terms of combinatorial designs, this definition means that the words of weight m in C equip C with the structure of a 1 − (n, m, t_{m}) design. So various examples can be found in Bachoc-Gaborit’s paper [B-G].

Theorem 3.6. Let C be an equidistributed code. Then the lattices Λ_{C} in situations (a) and (b), and L_{C} in situations (c) and (d) are strongly eutactic.

Proof. Let S_{0} be the set of vectors in Λ_{C} or L_{C} which lift the words of weight wt(C). By Proposition 3.4, S_{0} is strongly eutactic. In situations (a) and (c), we have S(Λ_{C}) = S_{0} and S(L_{C}) = S_{0}, respectively, which proves the result in these two cases. In situations (b) and (d), the set of minimal vectors of the lattice is the disjoint union S_{0} ∪ S_{1} with S_{1} = S(ℤ^{n}) in case (b) and S_{1} = S(𝔻^{n}) in case (d). In both cases, S_{1} is strongly eutactic, hence the result in these latter cases. □

Note that the various notions of eutaxy as well as that of perfection for a lattice Λ solely depend on the set of minimal vectors of Λ. For this reason we shall most of the time restrict ourselves to lattices which are generated by their minimal vectors. Moreover, when this condition holds, these notions are easily tested using the corresponding knowledge for the irreducible components of Λ: the perfection rank is additive on the components, (weak, semi-, proper) eutaxy holds if and only if it holds on each component, and strong eutaxy holds if and only if (1) it holds on each component and (2) the ratio \frac{s}{n} is the same for all components.

As a consequence we shall mainly consider lattices which are irreducible and generated by their minimal vectors.

When performing one of the construction (a) to (d) with a code C, the condition above is satisfied if and only if C is generated by its words of minimal weight and is irreducible (i.e. not the concatenation of codes of smaller length). In particular, this excludes equidistributed codes with k = 1.

4. Equidistributed codes

We keep the notation of the previous section. We denote by C a (linear, binary) [n, k, d]-code, and refer to Definitions 2.1 and 3.5 for the notation M_{m}, M, t_{m}(i), t(i), t_{m}, t.

We denote by 000 the word 0 and by 111 the all ones word. We moreover denote by Aut(C) the automorphism group of C (and shall often use the letter G).

We first state two propositions, of which we omit the evident proofs.

Proposition 4.1. (1) The dual code C^{⊥} is even if and only if 111 ∈ C.

(2) For every weight m of C, the weight-m words of C add to the word (k_{m}(1), …, k_{m}(n)).

(3) If C is m-equidistributed, this sum is 000 if k_{m} is even and 111 if k_{m} is odd. □

Proposition 4.2. (1) We have ∑_{i=1}^{n} t_{m}(i) = m · M_{m} . In particular if

C is m-equidistributed, then

t_{m} · n = m · M_{m} .

(2) If the automorphism group of C acts transitively on the coordinates, then C and C^{⊥} are m-equidistributed for every m. □

We now consider the connections which might exist between a code C of weight 3, its even subcode and its extended even code (by the parity check).

Definition 4.3. Let C be an odd code. We denote by C′ its even subcode and by \overline{C} its extended code. We also write t′ = t(C′), \overline{t} = t(\overline{C}), M′ = M(C′), \overline{M} = M(\overline{C}).

This definition will mainly be applied when wt(C) = 3. Thus we shall consider codes with parameters

C : [n, k, 3] ; C′ : [n, k − 1, 4 or 6] ; \overline{C} : [n + 1, k, 4] .

[Under the conditions listed at the end of Section 3, one has wt(C′) = 4, since weight-3 words may not all have disjoint supports.]

Proposition 4.4. Let C be a code of weight 3. Assuming that C′ has weight 4, we have

\overline{t}(i) = t(i) + t′(i) (1 ≤ i ≤ n), \overline{t}(n + 1) = M , and \overline{M} = M + M′.

Proof. The words of weight 4 of \overline{C} are those of C′ and the extensions of words of weight 3 of C. □

This proposition, which reduces to \overline{t}(i) = t + t′ if i ≤ n and \overline{t}(n + 1) = M when both C and C′ are equidistributed, allows calculations for \overline{C}, but says nothing on putative relations between C and C′. We shall construct examples in which C but not C′, or C′ but not C, is equidistributed.

In the remaining of this section we concentrate on codes of weight 3, giving three important examples.

Recall that the (generalized) Hamming codes H_{n} of length n = 2^{p} − 1, p ≥ 3, are [n, n − p, 3]-codes defined up to equivalence by their parity check matrix A, a p×n matrix having for columns the n non-zero columns of zeros or ones.

We order them so has to have A = (I_{p} | A_{0}), which gives the codes the generator matrices H_{n} = (I_{n−p} | ^{t}A_{0}). The weight-3 words of H_{n} can be viewed as the lines of the projective space P_{p}(𝔽_{2}), thus Aut(H_{n}) as the group PSL_{p}(𝔽_{2}), of order 2^{p(p−1)/2} · (2^{p} − 1) ⋯ (2^{2} − 1) · (2 − 1), acting 2-fold transitively on the coordinates, hence transitively on the weight-3 words. Let w be weight-4 word with support {i, j, i′, j′}. Then (i, j, i_{w}) is a weight-3 word of C for a uniquely defined coordinate i_{w}, and (i′, j′, i_{w}) also belongs to C. We see that M_{3}(H_{n}) = \frac{1}{3} \binom{n}{2} and M_{4}(H_{n}) = \frac{n−3}{4} M_{3}. A closer look at the automorphism group moreover shows that Aut(H_{n}) also acts transitively on the sets of weight-4 words.

The following proposition easily follows from the data above.

Proposition 4.5. The codes H_{n}, H′_{n} and \overline{H}_{n}, n = 2^{p} −1, p ≥ 3 are equidistributed, with the following invariants:

(1) H_{n}: t = \frac{n−1}{2}, M = \frac{n(n−1)}{6} ;

(2) H′_{n}: t′ = \frac{(n−1)(n−3)}{6}, M′ = \frac{n(n−1)(n−3)}{24} ;

(3) \overline{H}_{n}: \overline{t} = \frac{n(n−1)}{6}, \overline{M} = \frac{n(n^{2}−1)}{24} . □

Note that one has PSL_{p}(𝔽_{2}) = GL_{p}(𝔽_{2}), so that Aut(\overline{H}_{n}) can be identified with the affine group AGL_{p}(𝔽_{2}), which is 3-fold transitive on the coordinates.

The Hamming codes are the only perfect codes of weight 3. (For weight-3 codes, perfection amounts to saying that there exists for each set {i, j} of coordinates a (unique) word w of weight 3 with w(i) = w(j) = 1.)

Thanks to the transitivity properties of the Hamming codes, we can associate with H_{n} (canonically up to isomorphism) an [n−1, k−1, 3]-code H_{n−1}, its punctured code, obtained by removing one coordinate i and all the words with w(i) = 1. Thanks to the 2-fold transitivity of Aut(H_{n}), the punctured code of H_{n} is well defined up to isomorphism and its automorphism group again acts transitively on the coordinates. We denote this code by Hp_{n}, this time with n = 2^{p} − 2, p ≥ 3. Using Proposition 4.5 above, we obtain:

Proposition 4.6. The codes Hp_{n} and Hp′_{n} (n = 2^{p} − 2) are equidistributed codes having the following invariants:

t = \frac{n−2}{2}, M = \frac{n(n−2)}{6}, t′ = \frac{(n−2)(n−3)}{6}, and M′ = \frac{n(n−2)(n−3)}{24} ;

\overline{Hp}_{n} is isomorphic to H′_{n+1}. □

Our last family, though having nothing to do with the previous two families except for a coincidence with Hp_{6} for n = 6, again relies on a parameter p ≥ 3. We define it through its dual codes. We first state a lemma, without writing its evident proof.

Lemma 4.7. Let C be an [n, k]-code and let A be a generator matrix for C. The words of weight ℓ in C^{⊥} are in one-to-one correspondence with the sets of ℓ columns of A adding to zero in C^{⊥}. In particular we have wt(C^{⊥}) ≥ 3 if and only if the columns of A are distinct and non-zero. This implies the bound n ≤ 2^{k} − 1, attained only on the duals of Hamming codes. □

Proposition 4.8. For any p ≥ 3, there exists (up to isomorphism) a unique [n = \frac{p(p+1)}{2}, p, p]-code K′(p) having M = p + 1 words of weight p which have pairwise a unique 1 in common (thus they add to 000). Its automorphism group is isomorphic to S_{p+1} acting faithfully on the p + 1 words of weight p and on the coordinates as the action on the 2-subsets of {1, 2, …, p + 1}.

The dual code K_{n} of K′(p) is an equidistributed [n = \frac{p(p+1)}{2}, k = \frac{p(p−1)}{2}, 3]- code with M = \frac{p(p^{2}−1)}{6} and t = p − 1; its even subcode has M′ = \frac{p(p^{2}−1)(p−2)}{8} and t′ = (p − 1)(p − 2).

Proof. We just sketch it. In the spirit of coding theory, a canonical construction for such a code can be done inductively as follows: start with the matrix I_{p}, then extend it to the right by p − 1 ones on the first row and by I_{p−1} below this row, then complete the first row by 0’s, forget it, and go on inductively, putting p − 2 ones on the second row and writing down I_{p−2} below, etc. The lines of this matrix define p words w_{1}, …, w_{p} which add to w_{p+1} = (1^{p}, 0^{p(p−1)/2}). Here is the generator matrix for p = 4:

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

Uniqueness is proved by noticing that two words w, w′ can be exchanged by exchanging conveniently the p − 1 coordinates at which they differ. (If w(i) = 1, let w′′ be the word having w′′(i) = 1 and w′′(i′) = 1 where i′ satisfies w′(i′) = 1, and exchange i and i′). This also shows that the automorphism group is generated by products of p − 1 transpositions on the coordinates which induce all possible transpositions on the set of words of weight p, and that the action on the coordinates is induced by the action of S_{p+1} on the 2-sets, each coordinate being associated with the pair (w, w′) of weight-3 words such that w(i) = w′(i) = 1.

We have n = \frac{p(p+1)}{2} and dim K(p) = p, and it is clear that for any pair (i, j) of coordinates of K(p), there are words having components (1, 0) and (0, 1) at (i, j). This shows that K(p)^{⊥} is a [\frac{p(p+1)}{2}, \frac{p(p−1)}{2}, d ≥ 3]-code.

Pick any coordinate i, denote by w_{1} and w_{2} the words of weight 3 such that w_{1}(i) = w_{2}(i) = 1. and choose j ≠ i such that w_{1}(j) = 1. Then there is a unique word w_{3} of weight 3 such that w_{3}(j) = 1 and a unique coordinate ℓ such that w_{3}(ℓ) = w_{2}(ℓ) = 1. The set of p − 1 weight-3 words we obtain this way does not depend on the choice of w_{1} among {w_{1}, w_{2}}. This shows that wt(K^{⊥}) = 3 and that M = \frac{n(p−1)}{3} = \frac{p(p^{2}−1)}{6}. By the transitivity of its automorphism group, K^{⊥} is equidistributed, and by Proposition 4.2 we have t = \frac{3M}{n} = p − 1.

The same kind of argument then allows us to enumerate weight-4 words, which completes the proof of the proposition. □

Remark 4.9. The only known perfect, integral lattices of minimum 3 in the range [2, 15] are those which lift the codes H_{7} (similar to 𝔼_{7}^{∗}) and H_{15}. I conjecture that these two lattices are the only such perfect lattices, and even that the perfection bound \frac{n(n+1)}{2} is not attained by the kissing number for n ≤ 13, n ≠ 7. This is proved in [M-V2] for n ≤ 9. For n = 14 (resp. 15), the largest known value for s is 112, given by the lift of Hp_{14} (resp. 160).

Remark 4.10. The codes dual to K_{n}, Hp_{n}, H_{n} all have weight t + 1, and can be constructed using design structures on their sets of words of minimal weight. Probably, other examples could be constructed following the method we used for K(p). Due to the big gap which exists between \frac{p(p+1)}{2} and 2^{p} − 2, I do not expect the three examples above to be the only ones. !e

We end this section by describing a construction which doubles both the length and the distribution weight of an equidistributed code of weight 3. Let C be an [n, k, 3]-code and let D be the code obtained by repeating C^{⊥}. If C^{⊥} has minimal distance δ, this is an [2(n − k), n − k, 2δ]-code, having pairwise equal columns for any choice of a generator matrix G for it, an (n − k) × n matrix invariant under each of the n transpositions (1, n + 1), (2, n+2), …, (n, 2n). Enlarge G to an (n−k +1)×n matrix G̃ by adjoining a row having a one and a zero at each pair of equal columns of G. Then up to isomorphism, the code D̃ defined by G̃ does not depend on the choice of G nor on the distribution of the ones and zeros in the last row (we shall for convenience put a 1 at the first n coordinates and a o at the last n), and its dual C̃ has weight 3.

We state the proposition below without giving its easy proof.

Proposition 4.11. Let C be an [n, k, 3]-code having M words of weight 3. The its double C̃ is a [2n, n+k−1, 3]-code having M̃ = 4M words of weight 3. If C is equidistributed with distribution weight k, C̃ is equidistributed with distribution weight 2k.

Applied to C = H_{n}, this construction yields Hp_{2n}; applied to C = Hp_{n}, it yields the orthogonal of the (well-defined) code deduced from H_{2n+1}^{⊥} by deleting three columns adding to 0^{1}.

5. Codes of weight 3: low length classification

In this section we consider an irreducible, equidistributed [n, k, 3] code C generated by its words of weight 3. This implies that t ≥ 2. We shall often denote a word w of weight ℓ by its coordinates having w(i) = 1: w = (i_{1}, i_{2}, …, i_{ℓ}), and most of the time, begin the enumeration of its weight-3 words with w_{1} = (1, 2, 3), w_{2} = (1, 4, 5), …, w_{t} = (1, 2t, 2t + 1). We have

n ≥ 2t + 1 and wt(C^{⊥}) ≥ t + 1 .

[For the second inequality, observe that a word w ∈ C^{⊥} with w(1) = 1 satisfies w(i) = 1 for exactly one coordinate i in each of the 2-sets {2, 3},…,{2t, 2t + 1}, and may be for some coordinates j > 2t + 1.]

When n is close to its lower bound 2t + 1, we have:

Proposition 5.1. (1) If n > 2t + 1 and 111 ∈ C, and in particular if t is

odd, then n ≥ 2t + 4.

(2) If n = 2t + 1, then n = 2^{p} − 1 for some p ≥ 3 and C is isomorphic to H_{n}.

(3) If n = 2t + 2, then n = 2^{p} − 2 for some p ≥ 3 and C is isomorphic to Hp_{n}.

Proof. (1) The words w_{1}, …, w_{t} and 111 add to w = (2t + 2, …, n), of weight n − 2t − 1.

(2) We may assume that C^{⊥} contains a word w of the form (1, 2, 4, …, 2t). Then words of weight 3 containing an even index i are of the form (i, i′, j) with even i′ and odd j = j(i, i′). Since (1, i, i + 1), (1, i′, i + 1) and (i, i′, j) add to (i + 1, i′ + 1, j), we see that for every pair (i_{1}, i_{2}) of coordinates, C contains a word of the form (i_{1}, i_{2}, i_{3}). This proves that C is perfect, hence that n = 2^{p} − 1 for some p ≥ 3 and that C is isomorphic to H_{n}.

(3) We assume as usual that C contains the words w_{1} = (1, 2, 3), …, w_{t} = (1, 2t, 2t + 1). Then C must also contain t words (i, j, n) with 1 < i < j < n and (1, i, j) ∉ C. With (i, j, n), C also contain (i′, j′, n) such that (1, i, i′) and (1, j, j′) ∈ C; we may assume that these words are (2, 4, n), (6, 8, n), …, and their “odd” counterparts (3, 5, n), (7, 9, n), . . ..

1 This produces a fourth family of codes of weight 3 whose automorphism group acts transitively on the coordinates; the code with (n, k) = (12, 4) of Theorem 5.6 is H̃p_{6}.

Deleting from H_{2n+1}^{⊥}two columns of three columns which do not add to zero yields nonequidistributed codes.

We now consider the code C̃ which extends C to length n + 1, generated by C and the word w_{0} = (1, n, n + 1). The words of C̃ are those of C and the new words w̃ = w + w_{0}, w ∈ C. Note that the number r of components that w and w_{0} have in common is at most 2, and that denoting by m the weight of w, that of w̃ is m + 3, m + 1, or m − 1 if r = 0, 1, 2, respectively, and that if m = 3, then r = 0 or 1. This shows the lower bounds wt(w̃ ≥ m + 1 ≥ 4 if m = 3 or w = 0, and wt(w̃ ≥ m − 1 ≥ 4 if m > 3. Hence wt(C̃) = 3.

For the number t̃(i) of weight-3 words of C̃containing a given component i, we have t̃(i) = t + 1 if i = 1 or n, and if i ∈ (2, n), then C contains a unique word of the form (i, j, n), and also the related word (i′, j′, n). We have

(i′, j′, n) + (1, i, i′) + (1, n, n + 1) = (i, j′, n + 1) ,

which bounds from below by t + 1 all t̃(i) with 2 ≤ i ≤ n − 1 and also t̃(n + 1). Hence C is an equidistributed code of length 2t(C̃) + 1, which is consequently isomorphic to H_{n+1}, and C is its punctured code Hp_{n}. □

Given an equidistributed code, we know the value of M (= \frac{tn}{3}) by Proposition 4.2. The proposition below gives the value of the dimension k for codes with t = 2. It would be interesting to prove formulae for larger values of t, or at least to find sharp lower and upper bounds for the dimension.

Proposition 5.2. If C is an equidistributed code with t = 2 (irreducible, generated by weight-3 words), then

M = \frac{2n}{3} and k = M − 1 .

Proof. Let W be the set of weight-3 words of C, let W′ be a minimal subset of W on which we have ∑_{w∈W′} w = 0, and let T′ be the support of W′. Every coordinate i ∈ T′ belongs to an even number of words of W′, hence to exactly two words because k = 2. Hence a word x ∈ W ∖W′ cannot meet any word of W′, and since C is generated by W, it is the concatenation of the codes generated by W′ and by W ∖W′. Since C is irreducible, we have W = W′, hence ∑_{w∈W} w = 0 is the unique linear relation between weight-3 words of C. □

The following proposition provides a classification result in (very) low dimensions together with some information on the weight of the dual codes, which we shall use later to push forward the classification results stated below.

Proposition 5.3. Let C is an equidistributed code with t ≥ 2 (irreducible, generated by weight-3 words).

(1) If t = 2 then either C is isomorphic to Hp_{6} ≃ K_{6}, or to a code containing the words w_{1} = (1, 2, 3), w_{2} = (1, 4, 5), w_{3} = (2, 6, 7), and w_{4} = (3, 8, 9).

(2) If n ≤ 10, the C is isomorphic to Hp_{6} ≃ K_{6}, H_{7}, K_{10}, or to the [9, 5, 3]-code C_{9} with k = 2 and weight-3 words w_{1}, w_{2}, w_{3}, w_{4}, w_{5} = (4, 6, 8) and w_{6} = (5, 7, 9).

(3) wt(C^{⊥}) is bounded from below by 4 if t = 2 and by 6 if t ≥ 3 except it C is one of the four codes Hp_{6} (k = 2, wt(C^{⊥}) = 3), H_{7} or K_{10} (t = 3 and wt(C^{⊥}) = 4), and C = K_{15} (k = 4, wt(C^{⊥}) = 5).

Proof. We first observe that because of the inequalities n ≥ 2t + 1 and wt(C^{⊥}) ≥ t + 1, it suffices to consider codes with t = 2, 3 or 4; and that the four codes listed in (3) are indeed exceptions (note in particular that Hp_{6} is isodual). We now consider successively the three possible values for t.

\underline{t = 2}. We may assume that C contains the words w_{1} = (1, 2, 3) and w_{2} = (1, 4, 5). If C contains a word w_{3} = (i_{1}, i_{2}, j) with i_{1} ∈ {2, 3} and i_{2} ∈ {4, 5}, we may assume that w_{3} = (2, 4, 6), then w_{1}, w_{2}, w_{3} generate a code C_{0} isomorphic to H_{6}, and since C is irreducible, we have C = C_{0}. Otherwise we may assume that C also contains the words w_{3} and w_{4} above.

This proves (1), and shows that we may assume that a word w ∈ C^{⊥} with w(1) = 1 also has w(2) = w(4) = 1, hence also w(6) = 1 or w(7) = 1, which proves (3) for t = 2.

Finally if n > 6, since n ≡ 0 mod 3, we have n ≥ 12 or n = 9, and in the latter case, for a word (4, i, j) ∈ C, we must have, say, i ∈ {6, 7} and j ∈ {8, 9}, and we obtain a code isomorphic to C_{9}, with e.g. w_{5} = (4, 6, 8) and w_{6} = (5, 7, 9).

\underline{t = 3}. We start with w_{1} = (1, 2, 3), w_{2} = (1, 4, 5) and w_{3} = (1, 6, 7). If there is a word w_{4} = (i_{1}, i_{2}, i_{3}) with i_{j} ≤ 7, say, w_{4} = (2, 4, 6) (which is necessary if n = 7), then C also contains the three words (3, 5, 6), (3, 4, 7) and (2, 5, 7). We obtain this way a unique code with t = 3, necessarily isomorphic to H_{7}, and such a code does not extend to a code with t = 3 and n > 7.

If n > 7, we have n ≥ 10 by Proposition 5.1, and if n = 10, then C contains w_{0} = (8, 9, 10). This shows that C may not contain words of the form (i, j, j′) with i ≤ 7 and j, j′ ≥ 8, so that we may assume that C contains w_{4} = (2, 4, 8), w_{5} = (2, 6, 9) and w_{6} = (4, 6, 10) (we have w_{4}+w_{5}+w_{6} = w_{0}). This unique code is necessarily isomorphic to K_{10}.

Finally if wt(C^{⊥}) = 4, we may assume that C^{⊥} contains w = (1, 2, 4, 6). Then words of weight 3 containing 2 or 4 may be assumed to be (2, 4, 8) and (2, 6, 9), unless one of them is (2, 4, 7), and C is then one of the codes K_{10} or H_{7}.

\underline{t = 4}. We start with w_{1} = (1, 2, 3), w_{2} = (1, 4, 5), w_{3} = (1, 6, 7) and w_{4} = (1, 8, 9). We may assume that C^{⊥} contains a word w with ones at 1, 2, 4, 6, 8. If wt(w) > 5, we then have n ≥ 10, hence n ≥ 12, which proves (2) in this case. It now suffices to consider the case when w = (1, 2, 4, 6, 8).

We now show that C may not contain a word of the form (i_{1}, i_{2}, j) with i_{1}, i_{2} ≤ 8 even and j ≤ 9 odd, say, w_{5} = (2, 4, 7), hence also (2, 5, 6), (3, 4, 6), and (3, 5, 7). To push t(i), i = 2, 4, 6 to t(i) = 4, we need add words such as (2, 8, 10), (4, 8, 11), (6, 8, 12), hence also (3, 9, 10), (5, 9, 11), (7, 9, 12), and since (3, 5, 7) + (5, 9, 11) + (7, 9, 12) = (3, 11, 12), we have t(3) ≥ 5, a contradiction.

We may now assume that C contains w_{5} = (2, 4, 10), w_{6} = (2, 6, 11) and w_{7} = (2, 8, 12). We exclude as above a word of the form (4, 6, 12) (which would imply t(12) ≥ 5), and may thus go on with w_{8} = (4, 6, 13), w_{9} = (4, 8, 14) and w_{10} = (6, 8, 15). We have found a unique code, which must be isomorphic to K_{15}.

This proves (2) and (3) for t = 4 and completes the proof of the proposition. □

Remark 5.4. The automorphism groups of the four codes of Proposition 5.3 are all generated by products of a constant number of disjoint transpositions and act transitively on the coordinates and on the sets of words having a given weight. Only C_{9} needs a proof. One checks that Aut(C_{9}) is a group of order 72 generated by convenient products of 3 disjoint transpositions (typically, (2 5)(3 4)(6 9)), which can be identified by its action on weight-3 words with a maximal solvable transitive subgroup of 𝔖_{6}.

Remark 5.5. The classification of Proposition 5.3 remains true without any restriction on the codes. This is no longer true in higher dimensions: the code H_{6} ⊥ H_{6} is reducible, and possesses an irreducible enlargement with a weight-4 word; both have t = 2.

We now turn to classification in higher dimensions. We shall make direct calculations when k = 2 and make use when k = 3 of results on the dual code proved in Proposition 5.3. We observe that Lemma 4.7 shows that for the dimension k^{∗} of the dual code, we have 2^{k^{∗}} ≥ n+1 , and even 2^{k^{∗}} ≥ n+2 if C is not a Hamming code H_{n}, and that given k^{∗}, a code with weight w ≥ 3 is dual to a code extracted from the columns of the k^{∗} × n matrix defining the dual of H_{n}, n = 2^{k^{∗}} − 1. This extraction procedure can be used when k^{∗} is known and n − k^{∗} not too large.

Theorem 5.6. Let C is an equidistributed code with t ≥ 2 (irreducible, generated by weight-3 words), of dimension n ≤ 14. Then C is one of the eight codes displayed in the numerical appendix: t = 2: C_{6}, C_{9}, C_{12a}, C_{12b}; t = 3: C_{7}, C_{10} ; t = 4: C_{12c}; t = 6: C_{14} ≃ Hp_{14} . In dimension 15, there exists such codes with t = 2 (at least two), 3, 4

and 7.

Proof. By Proposition 5.3, it suffices to consider lengths n ∈ [11, 15], and the case when n = 15 results from the numerical appendix.

First consider a code C with t = 3. We then have wt(C^{⊥}) ≥ 6 and dim C^{⊥} ≥ 4, and an easy inductive calculation shows that for n = 9, 11, 12, the maximal dimension of a code of weight w ≥ 6 is 2, 3, and 12, respectively. In each case there a unique code, which is even. Using this result, we easily check that in length 13, the maximal dimension is again 4. This proves the theorem for n = 11, an and inspection of the sections of H_{15}^{∗} shows that there is no equidistributed code in of length 13 and a unique one of length 12, which has t = 4.

The case of length 14 is more difficult. We must have t = 3 or 6, and if t = 6, the unique possibility is Hp_{14}. Otherwise C^{⊥} must be an even code of weight 6 and dimension k^{∗} ≥ 5, hence 5. This is proved by classifying [n ≤ 13, 4, 3]-codes; see Appendix 2.

There remains to consider the case when t = 2. By Proposition 5.3, we may start with w_{1} = (1, 2, 3), w_{2} = (1, 4, 5), w_{3} = (2, 6, 7) and w_{4} = (3, 8, 9), and must avoid words (i_{1}, i_{2}, i_{3}) with i_{j} ≤ 9; also there can be at most three words of the form (i, i_{2}, i_{3}) with i ≤ 9 and j_{1}, j_{2} ≥ 10, and three such words will add to a word (i_{1}, i_{2}, i_{3}), a possibility which we have discarded. Hence we may go on with w_{5} = (4, 6, 10) and either w_{6} = (5, 7, 11) or w_{6} = (5, 8, 11).

If w_{6} = (5, 7, 11) then w_{1} + w_{2} + w_{4} + w_{5} + w_{6} = (3, 10, 11), which implies t(3) > 2. Hence we choose w_{6} = (5, 8, 11), and the last two words must must be of the form (i, j, 12) and (i′, j′, 12), with i = 7 and j = 9, 10, 11, but if w_{7} = (7, 10, 11), we then have w_{3} + w_{5} + w_{7} = (2, 4, 12), hence t(2) > 2. Choosing, j = 9, 11 we obtain the codes C_{a12}, C_{b12}, respectively. □

Remark 5.7. (1) The automorphism groups of the codes of length n ≤ 15 displayed in the numerical appendix act transitively on the coordinates, except those of C_{a12}, C_{a15} and C_{b15}.

(2) The same transitivity property holds for the even extension to length 16 of C_{c15}, a code which is dual to Bachoc-Gaborit’s [16, 6, 6]-code quoted in Example 2.3, (3).

APPENDIX 1: GENERATOR MATRICES of WEIGHT 3

The list below together with C_{14} = Hp_{14} is complete up to length 14.

C_{6} ≃ Hp_{6} ≃ K_{6} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) ; C_{7} ≃ H_{7} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} ) .

C_{9} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \end{matrix} ) ; C_{10} ≃ K_{10} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{matrix} ) .

C_{a12} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \end{matrix} ) C_{b12} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \end{matrix} )

C_{c12} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

C_{a15} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{matrix} ) ; C_{b15} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} ) .

C_{c15} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) ; C_{d15} ≃ K_{15} : ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

Remark.

• C_{14} = Hp_{14} and C_{e15} = H_{15} must be added to the list above.

• C_{c15} is dual to Bachoc-Gaborit’s C_{15} of [B-G]; see Remark 5.7.

APPENDIX 2: GENERATOR MATRICES of WEIGHT 6

To complete the proof of Theorem 5.6 we list the even [13, 4, w ≥ 6]-codes, which is done inductively from the even [11, 2, w ≥ 6]- and [12, 3, w ≥ 6]-codes. We only list below primitive codes, those which do not trivially extend a code of lower length, and thus consider primitive codes of length n ≤ 11, 12, 13 having dimensions d = 2, 3, 4, respectively. Actually it suffices to consider codes of weight 6.

For d = 2 we trivially have one code for each length n = 9, 10, 11. The [9, 2, 6]-codes is made of the three blocks {1, 2, 3}, {4, 5, 6} and {7, 8, 9}. It has a unique extension to n = 11 and three primitive extensions to n = 12, generated! by a word with ones at {10, 11, 12} and three extra ones belonging to one, two, or three of the blocks above.

The [11, 3, 6]-code, that we denote by F_{11,3} is better understood as a kind of concatenation of the [8, 4, 3]-code d_{8} with the [3, 2, 2]-code. It has a unique extension to n = 12, in which we replace d_{8} by d_{8}^{+}, the code for 𝔼_{8}. We display below a generator matrix for this code, the dual of which is C_{c12}; F_{11,3} is obtained by deleting from it the last row and the last column:

F_{12,4} = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \end{matrix} ) .

We now turn to the classification of even [n ≤ 13, 4, 6]-codes, making use of automorphisms of the codes of dimension 3 that we found above. It turns out that the generator matrices of extensions of the three primitive [12, 3, 6]-codes all have a pair of columns of the form ^{t}(0, 0, 0, 1), so that all these extensions indeed extend the [11, 3, 6]-code. Simple calculations show that there exactly four primitive even [12, 3, 6]-codes, namely

F_{13,4a} = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{matrix} ) ; F_{13,4b} = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} ) ;

F_{13,4c} = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \end{matrix} ) ; F_{13,4d} = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} ) .

Using these data it is easy to run through all extensions to length 14 and dimension 5 of the five matrices above, discarding those which have a zero column or two equal columns, so as to keep only those defining a dual code of weight at least 3, and to check that no equidistributed dual code shows up. This completes the proof of Theorem 5.6.

I have also constructed inductively some [n, n − 9, 6]-codes for n = 14 to 18, keeping at each step one code per weight distribution. I obtained this way one code with n = 17 and n = 18, both equidistributed with t = 24 and t = 34, respectively. Here is a generator matrix for length 18; deleting the last row and the last column yields the code for n = 17:

F_{18,9} = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} ) .

By lack of a reliable isomorphism test I cannot assert that the list lattices I found in lengths 14 – 18 is complete. If it is, F_{18,9} is then necessarily isodual, and F_{17,8} is isomorphic to the even subcode of its dual (of weight 5).

References

[B] C. Bachoc, Designs, groups, and Lattices, J. Th. Nombres de Bordeaux (issue

dedicated to the Journées Arithmétiques of Graz, 2003) 17 (2005), 25–44.

[B-G] C. Bachoc, Ph. Gaborit, Designs and self-dual codes with long shadows, J. Comb.

Th., A 105 (2004), 15–34.

[B-V] C. Bachoc, B. Venkov, Modular forms, lattices and spherical designs, [M1],

87–111.

[C-vL] P.J. Cameron, J.H. van Lint, Designs, Graphs, Codes and their Links, Student Text 22 of the London Mathematical Society, Cambridge University Press, Cambridge, 1991.

[M1] J. Martinet (ed), Réseaux Euclidiens, designs sphériques et formes modulaires, Monogr. Enseign. Math. 37, Genève (2001).

[M2] J. Martinet, Perfect lattices in Euclidean spaces, Grundlehren 327, Springer-Verlag, Heidelberg, 2003.

[K-M-S] W. Keller, J. Martinet, A. Schürmann, On classifying Minkowskian sublattices,

Math. Comp., 81 (2012), 1063-1092; see also arXiv:0904.3110v3 [math.NT].

[M-V1] J. Martinet, B. Venkov, Les réseaux fortement eutactiques (with an appendix by

R. Coulangeon), [M1], 112–134.

[M-V2] J. Martinet, B. Venkov, On integral lattices having an odd minimum, Algebra

and Analysis (Saint-Petersburg) 16, 3 (2004), 99–142.

[V] B. Venkov, Réseaux et “designs” sphériques (notes by J. Martinet), [M1], 10–86.

Université de Bordeaux, Institut de Mathématiques, 351, cours de la Libération, 33405 Talence cedex, France

   E-mail address: Jacques.Martinet@math.u-bordeaux1.fr