On Harmonic Weight Enumerators of Binary Codes.
We define some new polynomials associated to a linear binary code and a harmonic function of degree k. The case k=0 is the usual weight enumerator of the code. When divided by (xy)^k, they satisfy a MacWilliams type equality. When applied to certain harmonic functions constructed from Hahn polynomials, they can compute some information on the intersection numbers of the code. As an application, we classify the extremal even formally self-dual codes of length 12.
Introduction
In the theory of lattices, some modular forms play a special role, the so-called
theta series with spherical coe-cients. They are generalizations of the theta
series of the lattice which counts the number of vectors of given norm; they
are a powerful tool for the study of the spherical codes supported by the
vectors of an even unimodular lattice, as shown in [24], and also provide some
knowledge on the values of the scalar product of the vectors of the lattice
with a given vector of the Euclidean space (i.e. on the so-called Jacobi
theta series of the lattice). For example, they have allowed B. Venkov to
settle \a priori" the list of the possible root systems of an even unimodular
24-dimensional lattice [7, Chapter 18]. See [1] for a generalization of these
methods to non-unimodular lattices.
Inspired by the analogy pointed out in [8], [9] between the theory of
combinatorial and euclidean designs and their connection in both cases with
harmonic spaces, we dene here analogues of these for linear binary codes.
More precisely, we associate to a binary code C and a harmonic function f
of degree k in the sense of [8], a polynomial W C;f (x; y), which, when divided
by (xy) k , behaves, up to a sign, like the usual weight enumerator WC (x; y)
under the MacWilliams transform. In particular, when C is a doubly even
self-dual code, we get a whole set of polynomials which are relative invariants
under the usual group G 1 of 2  2-matrices of order 192 generated byp1 1
and ( 1 0
In the case of an even formally self-dual code, the group
to be considered is the subgroup G 2 generated by 1
and 1 0
, and
the polynomials (xy) k (W C;f W C ? ;f ) are relative invariants for G 2 .
In both cases, these results can be used to derive some information on
the way a given t-set T meets the codewords. In particular, we give another
proof of the fact that the words of xed weight in an extremal code (resp.
and its dual in the case formally self-dual) support \t 1
"-designs, as shown
in [6], [16].
More generally, we can derive some \invariant linear forms" in the sense
of [5] on the so-called intersection numbers:
(1)
not only in the case when jT and one has t-designs, but also for all
value of through the explicit description of the space of relative
invariant polynomials in which (xy) k (W C;f  W C ? ;f ) falls. Therefore, we
specialize to certain harmonic functions associated to T , which
have the property that H k;T (u) only depends on t, juj, and ju \T j; they are
constructed from Hahn polynomials. As an example and application, we
derive a classication of the extremal even formally self-dual codes of length
12. This classication has been extended in [11], [12], where intersection
numbers play an important role.
Another method is used in [14] to derive analogous results. It involves
some other kinds of polynomials, the so-called overlap and covering polyno-
mials, which are closely connected to Ozeki's Jacobi polynomials([18]). The
author is grateful to one referee for pointing out this reference.
This paper is organized in the following way: Section 1 contains the
needed denitions and properties of harmonic functions and binary linear
codes. Section 2 contains the denition of harmonic weight enumerators
and the proof of the MacWilliams-type formula (Theorem 2.1). The consequences
on the invariance properties of these polynomials in the cases of
doubly even self-dual codes and of even formally self-dual codes are stated
in Corollaries 2.1 and 2.2. Section 3 gathers the needed results of invariant
theory. In Section 4, we reprove Assmus-Mattson theorem and Calderbank-
Delsarte strengthening of it for doubly even self-dual codes. Section 5 explains
the method based on Hahn polynomials used to compute the intersection
numbers, and Section 6 contains the classication of the extremal
even formally self-dual codes of length 12 (Theorem 6.1).
We now recall some denitions and properties of discrete harmonic func-
tions, which are developed in [8].
Let
ng be a nite set (which will be the set of coordinates
of the code C) and let X be the set of its subsets, while, for all
k is the set of its k-subsets. We denote by RX, RX k the free real vector
spaces spanned by respectively the elements of X, X k . An element of RX k
is denoted by
f(z)z (2)
and is identied with the real-valued function on X k given by z ! f(z).
The complementary set of z is denoted by z.
Such an element f 2 RX k can be extended to an element ~
setting, for all u 2 X,
~
(In the notations of [8], the restriction of ~
f to RX n is dened to be (f ).)
We may later on denote again ~
f by f . If an element g 2 RX is equal to
some ~
f , for f 2 RX k , we say that g has degree k. The dierentiation
is
the operator dened by linearity from
for all z 2 X k and for all is the kernel of
Harm k := Ker(
Concerning codes, we take the following notations: we freely identify
words of F n
2 and subsets of
the weight of an element u 2 F n
2 is also
the cardinality of its support and is denoted by wt(u) or juj. We recall
some basic notions of coding theory, for which we refer to [17], [22]; we only
consider linear codes. The weight enumerator WC (x; y) of a binary code C
is
where A i is the number of codewords of weight i and satises the MacWilliams
A code C is said to be formally self-dual if It is even if
doubly even if wt(u)  0 mod 4 for all
codes are even and formally self-dual, while the converse
is not true; see [16], [22] for examples. If a formally self-dual code is in
addition doubly even, then it is necessarily self-dual. From the facts that
the polynomial WC is invariant under the group G 1 in the self-dual doubly
even case (resp. under G 2 in the even formally self-dual case), one deduces
the inequalities for the minimal weight d(C) of C: d(C)  4([n=24]
(respectively meeting these bounds is said to
be extremal; its weight enumerator is then uniquely determined.
Harmonic weight enumerators
In this section, we dene the harmonic weight enumerators associated to a
binary linear code C and prove a MacWilliams type equality.
Denition 2.1 Let C be a binary code of length n and let f 2 Harm k . The
harmonic weight enumerator associated to C and f is
~
Theorem 2.1 Let WC;f (x; y) be the harmonic weight enumerator associated
to the code C and the harmonic function f of degree k. Then
where Z C;f is a homogeneous polynomial of degree n 2k, and satises
x y
Proof. Like in the classical case of MacWilliams formula for weight enu-
merators, the proof relies on Poisson summation formula, which we recall
here:
Theorem 2.2 (Poisson summation formula) Let  : F n
R be a function
taking its values into a ring R, and let ^
be its Fourier transform,
dened by
(v) :=
Then, for all linear code C  F n
(v) (12)
We shall apply Poisson formula to each term of Z C;f , namely to:
Therefore, we compute the Fourier transform of , rst in the case
2.2), and in the general case but for harmonic functions in
Lemma 2.3. In order to prove that the ZC;f are actually polynomials, we
start with a technical lemma on harmonic functions.
Lemma 2.1 Let f 2 Harm k and v 2 F n
. Let
f (i) (v) :=
Then, for all 0  i  k, f (i)
~
f(v).
Proof. For all 0  i  k 1,
which means (from (4)) that
tz
The evaluation at v 2 F n
is:
tz
The proof then follows by induction on k i, since clearly f
and the previous equality implies
~
We can notice now that, for all u such that wt(u) < k, from denition (3)
of ~
f , ~
0, and from Lemma 2.1, ~
is a polynomial. We now compute the Fourier transform of  (see (13)).
Lemma 2.2 Let
Proof.
(v) :=
We can write runs through F n k
and are then reduced to the usual
formula for the Fourier transform of x n k wt(v\z) y wt(v\z) .
We now consider the case of a harmonic function of degree k and prove
Lemma 2.3 Let f 2 Harm k . Then
Proof. Since
f(z)z, and from Lemma 2.2,
To conclude for Lemma 2.3, we need another last lemma:
Lemma 2.4 Let f 2 Harm k . Then, for all v 2 F n
Proof. Let B s be the coe-cient of x k s y s in this polynomial. We must
show that B
We sum over with the notations of Lemma 2.1, it is equal
to
j+l=s
l
j+l=s
l
i;j;l
j+l=s
j;l;t;r
j+l=s
where the last equality is the computation of the coe-cient of x s in the
specialization of
Theorem 2.1 now follows from Lemma 2.3 and the Poisson summation formula
(12).
In the special case of doubly even self-dual codes, an immediate consequence
of Theorem 2.1 is that the polynomials Z C;f are relative invariants
for the group G 2 . This result is stated in Corollary 2.1, and an analogous
result for even formally self-dual codes is stated in Corollary 2.2.
We take the following notations:
We consider the group G 1 =< together with the characters  k
dened by:
and the group G 2 =< together with the characters
dened
by
Corollary 2.1 If C is a self-dual, doubly even code of length n, for all
, the polynomial Z C;f (x; y) satises
Z C;f (A(x;
for all matrix A 2 G 1 .
Corollary 2.2 If C is an even formally self-dual code of length n, for all
, the polynomials Z C;f  Z C ? ;f satisfy
for all matrix A 2 G 2 .
3 Some invariant theory
We gather here some well-known results of invariant theory that will be
of further use. We denote by C [x the polynomial algebra in n
variables, together with the left action of the algebra M n (C ) of nn complex
matrices given by (M:P
the transposition).
If G is a subgroup of M n (C ), we denote by IG the algebra of invariants
of G, namely
If  is a character of G, the space of relative invariants with respect to
is
I G; = fP
It is clearly a module over IG . In view of our situation, we need to compute
I
, for the characters  k dened in (15). It is well-known to be, in the
case k  0 mod 4, the polynomial algebra C [P
. The other cases are probably also
very classical, but we recall the result:
Lemma 3.1
I
Proof. The dimension a ;d of (I G; ) d , the homogeneous component of
degree d of (I G; ) is computed by Molien's series:
a ;d X
In the case of the group G 1 , and for the characters  k given by (15), we
nd respectively 1=((1 X 8 )(1 X 24 )), X
It is easy to verify that the
polynomials announced in the lemma do belong to the spaces I G1 ; k
; the
result then follows from the equality of the dimensions.
The case of the group G 2 goes the same; we have I
and the I G 2 ;
for the characters
(16), (17), are principal ideals. Clearly these characters only depend on k
mod 2.
Lemma 3.2
I
R 4 I G2 if
4 New proofs of some classical results
In this section, we recover the classical results on t-designs supported by
words of binary linear codes, using the harmonic weight enumerators previously
dened, and the characterization of designs in terms of the harmonic
spaces given in [8]: a set B of blocks is a t-design if and only if
~
for all f 2 Harm k , 1  k  t. Hence, the set of words of xed weight in
a code C form a t-design if and only if W C;f (x;
t.
We start with Assmus-Mattson theorem:
Theorem 4.1 (Assmus-Mattson) Let C be a binary code of length n and
distance d, and let C ? be its dual, of distance e. If t  d is such that the
number of non zero weights of C ? which are lower or equal to n t, is at
most d t, then the set of codewords of C (respectively C ? ) of xed weight
w form a t-design, for d  w  n (respectively e  w  n t).
Proof. Let f 2 Harm k , 1  k  t. Write A i;f :=
~
f(u) and
~
f(u). We want to prove that, for all i (rep. i  n
Theorem 2.1 translates, in terms of these, into:
kin k
for all j, k  j  n k, where the P (n 2k)
are the Krawtchouck polynomials
([17, Chap 5]). Since C has distance d, we have A
which leads to d k independent equations in the B i;f , k  i  n k. By
hypothesis, there are at most d k unknowns and hence the only solution
is trivial . Hence B t.
Now the n 2k
equations in the A i;f , d  i  n d, using equations (18) applied to C
since k  d and the equations are independent, the only solution is trivial.
In the case of extremal doubly even self-dual codes, we can prove the
result directly from the description of the relative invariants of the group G 1 ,
avoiding the use of Krawtchouck polynomials; moreover, the extra property
that the t-designs are \t 1"-designs (which was shown rst by B. Venkov by
means of spherical theta series, then in [6] in a combinatorial setting) follows
easily, and is very similar to the initial proof of B.Venkov [24] concerning
the spherical designs in extremal even unimodular lattices. We recall the
slightly more general denition of the notion of a T -design, for a subset T of
ng: a set B of blocks is called a T -design if and only if
~
0 for all f 2 Harm k and for all k 2 T . Hence a t-design is a
design.
Theorem 4.2 ([5]) Let C be an extremal self-dual doubly even code of
length n.
If n  0 mod 24, the codewords of xed weight in C form a
If n  8 mod 24, the codewords of xed weight in C form a
If n  16 mod 24, the codewords of xed weight in C form a
Proof. Let the extremality of C means that
We prove that WC;f (x; the
other cases being similar. From Theorem 2.1 and Lemma 3.1, for all f 2
Harm k , W C;f (x;
Since the valuation at y of Q, (i.e. the least power of y in Q) is 4(m+1) k 3,
We compute the degree of
this polynomial is non zero, it has degree n 2k
Notice that, if the polynomial Q 0 is determined up to a scalar: it is
proportional to 1 if respectively to P 8 if 8.
Remark 4.1 With the same method, we can recover the results of [16] on
the designs supported by codewords of xed weight in C [C ? , when C is an
extremal even formally self-dual code. We omit the proof.
5 Harmonic weight enumerators and the computation
of Jacobi polynomials
In this section, we show how harmonic weight enumerators can be used to
compute Jacobi polynomials. We rst recall the denition of these: Let C
be a binary code of length n and T  ng.
JC;T (v; z; x; y) :=
where, for is the number of coordinates of
u\T (respectively of u\T ) equal to i. They have been introduced by Ozeki
[18] in analogy with Jacobi forms of lattices, and studied by A. Bonnecaze,
P. Sole et al. [2], [3], [4] in the case of type II binary and Z 4 -codes. In
particular they point out the following characterization of codes supporting
designs: the set of codewords of a code C form a t-design for every xed
weight, if and only if the Jacobi polynomial JC;T for a t-set T is independent
of T .
Since we can also characterize this property of a code C by the set of
conditions:
a natural question is: how can one compute JC;T for a t-set T given in (19)
from the set of conditions (20)? The answer lies in the fact that one can
attach to every t-set T some harmonic functions H k;T of degree k, 1  k  t;
the values H k;T (u) are expressed in terms of Hahn polynomials, and only
depend on juj and ju \ T j. They are described in [8] as the orthogonal
projection of T 2 RX t over Harm k . In view of our applications, we need to
generalize [8, Theorem 5] to the case of subsets of non equal cardinality. For
the denition and properties of Hahn polynomials, we refer to [15].
Proposition 5.1 [8, Theorem 5] Let T be a t-subset of ng. For all
for all t-set u, where ([15]) Q t
are
orthogonal Hahn polynomials. Then H k;T 2 Harm k .
Proof. In the notations of [8], H k;T
Proposition 5.2 With the same hypothesis, as an element of RX, the
H k;T (u) for all subsets u of ng only depend on
We set H k;T
I
where
Proof. From [8, Theorem 3] applied to
have H k;T
zx
jx \ uj
which leads to the announced formula by setting
Remark: The same argumentation as in [8] applied to H k;T
for juj > t show that they are also linked to Hahn polynomials but for the
parameters (with the notations of [15]): Q k (x; juj n
From (1) and (19), the numbers nw;i (T ) are the coe-cients of JC;T :
On the other hand, the harmonic weight enumerators WC;H k;T
have the
following
WC;H k;T
f
Hence the set of equations (20) for leads for every w to
the following t linear equations in the t
We denote by Cw the set of codewords of weight w. Its cardinality is is
equal to the coe-cient Aw of the weight enumerator of the code C, dened
by (6). Then, another equation, corresponding to the degree 0 case, is:
For all w, the nw;i (T ) are the solutions of the system of equations (29),
(30).
Remark: In the cases when the polynomials ZC;H k;T
are invariant polyno-
mials, i.e. in the cases of doubly even self-dual codes or of even formally
self-dual codes, we can more generally get some information on the nw;i (T ),
not only when the codewords support t-designs, in the following way: a condition
of the type Z C;f 2 I G; , joined with the knowledge of d(C), says that
Z C;f sits in a nite-dimensional vector space, which is explicitly described.
Hence this information can be turned into linear equations in the nw;i (T ).
Of course, the smaller this dimension is, the more equations we get, and the
case when the codewords support designs is the 0-dimensional case. The
higher d(C) is, the smaller are these dimensions, the most interesting cases
being the extremal codes. An example of this method is treated in next
section.
6 A classication result
In this section, we classify, with the help of harmonic weight enumerators,
the extremal even formally self-dual codes of length 12. These codes have
weight 4 and their weight enumerator is
There is a unique code which is self-dual; it is the code B 12 with component
d 12 of [19], [20]; we nd two other codes which are isodual, one of them
is described in [22, Chap.3]. They both appear in [13] as double circulant
codes.
First step in this classication result is the computation of the
w;i (T )g 0it (see (1)). We rst show that, if T is a word of
C of weight 4 or 6, there are only two solutions for fnw;i (T ); n
therefore, we use the results of the previous section to derive some equations
satised by these numbers.
Lemma 6.1 Let C be an extremal even formally self-dual code of length
12 and let T 2 C, of weight 4 or 6. There are only two possibilities for
w;i (T )g 0it , which are given in the following tables:
If wt(T
If wt(T
Proof. We rst make some easy remarks: since
odd. Moreover, since the all-one word 1 belongs to C \C ? ,
From (31), we have:
and
4. Some of the entries are easily computed from the hypothesis
on the code C: n 4;3 (T otherwise the sum with T
would be a weight 2 word in C, and clearly n 4;4 (T Taking into account
the equations (32) and (33), we are reduced to the set of six unknowns:
)g. We now consider
the harmonic weight enumerators WC;H k;T
dened in the previous section.
From Corollary 2.2 and Lemma 3.2, ZC;H 1;T
but, since C and C ? have weight 4, ZC;H 1;T
must be a multiple
of (xy) 3 , and hence of Q 8 P 0
8 . This last polynomial is of degree
while ZC;H 1;T
is of degree 10; hence it is zero. A similar discussion
shows that ZC;H 1;T
We derive the
following equations:
which, in terms of our six unknowns, the coe-cients h k;4 (w; i) being computed
from equation (), lead to:
Since we look for positive integral solutions, we see from the rst two
equations of (35) that the only possibilities are n
the two announced solutions. Clearly, n
depending whether T
belongs to C ? or not.
arguments lead to the result.
Theorem 6.1 There are exactly three extremal formally self-dual codes with
even weights of length 12; one is the unique self-dual code B 12 and the two
others are given by the following generator matrices:
Permutation group of order 384
C (2)
C (2)
Permutation group of order 120
Proof. Let C be such a code. Let T 6 2 C be a word of weight 6, not
belonging to C ? . From Lemma 6.1 we know that n
is a unique word u 4 of weight 4 in C ? whose support is contained in T 6 .
belong to C because 2. On the other
hand, since n
we see that each such u 4 is associated to exactly
two weight 6 words of C (we have reversed the roles of C and C ? in Lemma
6.1). Hence the number of weight 6 words in C but not in C ? is at most
there is at least one pair of words of
weight 6 belonging to C \ C ? .
Each of the words of weight 4 in C intersects T in two positions, which
are never the same, otherwise the sum of two such words with 1+T would be
a weight 2 word in C. Hence there is a one-to-one correspondence between
the 15 elements in C 4 and the 2-subsets of T (respectively of 1+T ).
We denote them by u
Let u be a xed weight 4 word in C. Up to permutation, we can assume
that T , u are in the following position:
We assume rst that u 2 C \ C ? . From Lemma 6.1, there are 8 words
meeting u in two positions; since t(u 0
are four possibilities for u \ Assume one of
them appears at least three times, say the rst one and for
Again because t and t are bijections, there is up to permutation only one
possibility:
generates the self-dual code B 12 ([19],[20]). We can
next assume that the eight u 0 reach exactly twice the four possibilities for
Again for the same argument, there is up to permutation only one
possibility:
and now
generates the code C (1)
12 .
The last case to consider is the case when no weight 4 word in C belongs
to C ? . Hence C \ C ? is the 2-dimensional code generated by T and 1.
From Lemma 6.1, we know that eight words of weight 4 in C meet u in one
position. Then, at least one position is reached at least twice, say by
must share another
position outside u. Up to permutation, they are in the following positions:
If a third word u 4 meets u again in the same position as u 2 and u 3 ,
this is also true for the other pairs but then either
or u 2 +u 3 +u 4 +T +1 has weight 2, which is not possible.
Hence each position in u corresponds to a pair of weight 4 words in C
intersecting at that position. From the previous discussion, the sum is a
weight 4 word which is disjoint from u; there are exactly two such words
since n 4;0 and they are necessarily disjoint (if w is one of them, the
other is w corresponds to
and let be such that We have two choices up to
permutation for the common position of u; u can be (on u) either
1000 or 0010. But it is easy to see that the rst one is not possible under
the condition that t, t are bijective and that the second one leads to only
one possibility:
In that case, f1; generate the code C (2)
12 .
Since we nd up to permutation two codes, which are distinguished by
the dimension of C\C ? , and since the dual of an extremal even formally self-dual
code is again an extremal formally self-dual code with even weights,
these codes are necessarily equivalent to their duals. The automorphism
groups have been computed with Magma.
Remark 6.1 By \construction A", these codes construct non-isometric lattices
which are 4-modular and extremal in the sense of H.-G. Quebbemann
[21].



--R

lattices and spherical designs preprint



On error-correcting codes and invariant linear forms SIAM J
A strengthening of the Assmus-Mattson theorem IEEE Trans


Spherical codes and designs Geom.




Overlap and covering polynomials with applications to designs and self-dual codes
The
On designs and formally self-dual codes De- signs

On the notion of Jacobi polynomial for codes Math.
A classi
On the classi
A shadow identity and an application to isoduality Abh.
Handbook of Coding Theory

Even unimodular extremal lattices
--TR

--CTR
Koichi Betsumiya , Masaaki Harada, Classification of Formally Self-Dual Even Codes of Lengths up to 16, Designs, Codes and Cryptography, v.23 n.3, p.325-332, August 2001
Koichi Betsumiya , Masaaki Harada, Binary Optimal Odd Formally Self-Dual Codes, Designs, Codes and Cryptography, v.23 n.1, p.11-22, May 2001
J. E. Fields , P. Gaborit , W. C. Huffman , V. Pless, On the Classification of Extremal Even Formally Self-DualCodes, Designs, Codes and Cryptography, v.18 n.1-3, p.125-148, December 1999
Christine Bachoc , Philippe Gaborit, Designs and self-dual codes with long shadows, Journal of Combinatorial Theory Series A, v.105 n.1, p.15-34, January 2004
Olgica Milenkovic, Support Weight Enumerators and Coset Weight Distributions of Isodual Codes, Designs, Codes and Cryptography, v.35 n.1, p.81-109, April     2005
Kenichiro Tanabe, A Criterion for Designs in
{\tf="P101461" Z}_4
David Masson, Designs and Representation of the Symmetric Group, Designs, Codes and Cryptography, v.28 n.3, p.283-302, April
codes;formally self-dual codes;harmonic functions;weight enumerator