Jacobi Polynomials, Type II Codes, and Designs.
Jacobi polynomials were introduced by Ozeki in analogy with Jacobi forms of lattices. They are useful to compute coset weight enumerators, and weight enumerators of children. We determine them in most interesting cases in length at most 32, and in some cases in length 72. We use them to construct group divisible designs, packing designs, covering designs, and (t,r)-designs in the sense of Calderbank-Delsarte. A major tool is invariant theory of finite groups, in particular simultaneous invariants in the sense of Schur, polarization, and bivariate Molien series. A combinatorial interpretation of the Aronhold polarization operator is given. New rank parameters for spaces of coset weight distributions and Jacobi polynomials are introduced and studied here.
Introduction
While the use of invariants of finite groups to study weight enumerators of self-dual codes has a long and
distinguished history [22, Chap.19], they were introduced only recently in the study of the weight distribution
of cosets of self-dual codes [2, 19]. The polynomial invariant of the code on which a finite group acts by
linear substitutions of the variables is the Jacobi polynomial. Roughly speaking, Jacobi polynomials are
to binary codes what Jacobi forms [13] are to lattices. If the code is self-dual, they are invariant under
the same group that fixes the weight enumerator of the code and contain more information than the coset
weight distribution or outer distribution matrix in Delsarte sense. They are, however, strongly related to
the t-distribution matrix of [7] or outer distribution matrix in a Johnson scheme. New rank parameters for
spaces of Jacobi polynomials (b t ) and the outer distribution of a code (a t ) are introduced in this paper.
Introduced by Ozeki [19] Jacobi polynomials were studied by Bannai and Ozeki [2] by polarization techniques.
A very simple combinatorial interpretation of polarization is given here for codes whose codewords hold
t\Gammadesigns. Since the motivation of these authors was to build large spaces of modular forms they used a
group of order 96: For combinatorial purposes it seems more natural to use the larger group of order 192:
Our motivation is to construct designs of various kinds and in particular group divisible designs when the
Assmus-Mattson theorem cannot yield classical designs which do not exist anyways.
The paper is organized as follows. Section 2 collects definitions and some basic results. Subsections 2.3 and
2.5 are required reading for understanding the rest of the paper. Section 3 derives ( in a different way than
[19]) a MacWilliams formula for Jacobi polynomials thus solving a covering open problem of long standing.
Section 4 is devoted to bivariate Molien series. Section 5 studies invariants and how polarization produces
them. Section 6 studies examples of Jacobi polynomials in lengths 8,16,24,32, and 72.
Notations and definitions
2.1 Codes
All codes here are binary linear of length n. By weight w(x) we mean the number of 1's in x and by
Hamming composition the ordered pair (n \Gamma w(x); w(x)): A self-dual code is said to be Type II if its
weights are multiple of 4 and Type I otherwise. Let A i stands for the number of codewords of weight i; and
A i (x) for the weight distribution of the coset x C: The weight of a coset x + C is the smallest i ? 0
such that A i (x) ? 0: The Covering Radius R is the largest weight of a coset. The weight enumerator
WC (x; y) is the generating series
The joint weight enumerator J A;B of two codes A and B is
i;j;k;l
where A i;j;k;l is the number of pairs (a; b) in A \Theta B containing i patterns 10, j patterns 11, k patterns 00, l
patterns 01.
2.2 Designs
A design with parameters
N )) is a collection of k\Gammasets called blocks of a v-set (the
varieties) and a partition of the set of all t\Gammauples into N groups such that every t\Gammaset within a group of
a i such t-sets is contained in exactly - i blocks of size k:
A t-design with no further precision will mean a design with
A packing (resp. covering) design with parameters t \Gamma (v; k; -) is a design with
9]. The minimum (resp. maximum) size of a covering (resp. packing) design is
denoted by C - (v; k; t) (resp. D - (v; k; t)).
A group-divisible block design (GDD for short) [5] noted GD(k; with blocks of
size k and N groups of size g such that pairs in the same group occur in - 1 blocks and pairs with varieties
belonging to two different groups occur in - 2 blocks. GDD incidence matrices produce distance regular
graphs of diameter 3 [5, x1.10]. Observe that a GDD is a
design with a 1 =number of
pairs in the same block and a 2 =number of pairs in two different blocks.
We shall need the following consequence of the Assmus-Mattson theorem.
Theorem 1 If C is an extremal Type II code of length n congruent to 0 (respectively 8; 16) modulo 24 then
the vectors of any given weight in C hold a 5\Gammadesign (respectively a 3\Gammadesign, a 1\Gammadesign).
Define the Assmus-Mattson index am(n) of an integer n divisible by 8 as
congruent to s modulo 3 and 2: The above theorem says that an extremal Type II code C of length
n is an am(n) design.
2.3 Enumerators
By the Jacobi polynomial attached to a set T of coordinate places of a code C of length n over F 2 we
shall mean the polynomial in four variables
w m0 (c) z m1 (c) x n0 (c) y n1 (c)
where T ' [n]; and where m i (c) is the Hammingcomposition of c on T and n i (c) is the Hammingcomposition
on
The basic observation is that if T supports a coset leader x T of x is the weight
enumerator of x is constant for all T such that jT then the codewords whose monomials
have hold a t-design possibly with several groups (one for each possible J C;T ).
Relations with two other polynomial invariants of a code are to be noted.
2.4 Joint weight enumerators
First, the Jacobi polynomial is, up to variables permutation, the joint weight enumerator of C with the
singleton code reduced to the characteristic vector x T of T: Let J A;B denote the joint weight enumerator of
two linear codes A and B. Denote by ! T ? the monodimensional code spanned by x T : The following is
immediate from [22, p.147].
2.5 (t; r)-designs
Second, consider the set of codewords of weight j of C as a collection B j of j \Gammasubsets of an n\Gammaset. Let
the coefficient of w i z t\Gammai x n\Gammaj y j in J C;T . Then the
matrix with generic element
is the t-distribution matrix D t of [7]. A t\Gammaform is a row vector which is sent to a constant vector by
left multiplication by D t : A (t; r) design in the sense of [7] is a collection B j such that the space of t\Gammaforms
has dimension t is shown in [7] that the rank of D is either r of r + 1). It is shown in [7] that a
t\Gammadesign with design and conversely.
(C) denote the dimension of the real vector space of Jacobi polynomials J C;T with T ranging over
t-sets. Any upper bound on b t (C) yields an upper bound on r uniform in j: For instance that all codewords
of given weight hold a t\Gammadesign entails b (the converse is false as can be seen for e 8 and
that all codewords of given weight hold a (t; 1)\Gammadesign. In the case of C of type II a trivial
upper bound on b t (C) is the coefficient of u n\Gammat v t in the Molien series defined below.
A trivial lower bound is the rank a t
(C) say, of the
bound is not applicable (NA in the tables below) for t ? R: A well-known result due to Delsarte is that
R
a t
where s 0 is the number of nonzero dual weights. Recently there was some work on J C;T with jT
[8, 6, 7, 18] but little on jT 1: In this article we will show how to construct GDD in some of
these two cases, but, as examples of C for will show, there is little hope of a general upper bound
on b am(n)+1 even for the restricted class of extremal codes .
3 A MacWilliams formula for Jacobi Polynomials
We give an independent derivation of the MacWilliams relation for Jacobi polynomials of [19].
Theorem 2 (Ozeki) Let C be a binary linear code.
Proof:Follows by Lemma 1 and the MacWilliams relation for the ordinary and joint [22, p.148] weight
enumerator. 2
Observe that this essentially solves Open Problem 15 of [10, xIX].
4 Molien Series
It has been known since Gleason's address to the International Congress of Mathematics of Nice 1970 [14]
that the weight enumerator of a type II binary code is left invariant by a group G 2 of order 192 generated
by two matrices of size two by two defined as
and
corresponding respectively to the MacWilliams Transform, and mod 4 congruence condition. It is a simple
exercise, using Theorem 1, to show that, for any T , the Jacobi polynomial is invariant under the same group
acting in the same way on each pair of variables. This is therefore a simultaneous invariant in the sense
of Issai Schur [24] for the diagonal action of G There is a bivariate Molien series that enumerates invariant
polynomials by their homogeneous degrees in w; z and x; y. It can be shown [25, equ. (13)] that
where det(h) stands for the determinant of a matrix For instance in the case of the group G 2 a Magma
computation yields an expression for f(u; v) whose denominator factors as d(u)d(v) with
or, more suggestively
A Taylor decomposition yields after reordering terms of degree 40
6
terms of degree
5
terms of degree 24,
6
5
terms of degree 16,
terms of degree 8
and the constant term
Assume an Hironaka decomposition [24] of the algebra of invariants I of the type
where the j i s are so-called secondary invariants and where P is the algebra of primary invariants (or
homogeneous system of parameters) of the type
Then the bivariate Molien series can be written as
P a
In that expression dm (:) (resp. dn (:)) denote the degree in the first (resp. second) set of two variables. In
the case at hand we have primary invariants and a = 192 secondary invariants. One may take as
h.s.o.p. the system
(1)
(2)
5 Invariants
In principle some simultaneous invariants for a group G can be computed from usual invariants of the
Aronhold polarization operator A [24] which we now describe. Let P 0
y ) denote the partial
derivative with respect to variable x (resp. y). Let P (x; y) denote a polynomial in two variables. Define the
polarization operator A as
x
The following basic lemma can be found in a much more general form in [24].
is an invariant for G 2 then A:P is a simultaneous invariant for G 2 . The map P 7! AP is
injective, the inverse map being given by
Proof:For every complex scalar i the quantity
is a simultaneous invariant of G 2 . A Taylor expansion yields
Each coefficient of this expansion in powers of i is a simultaneous invariant. Setting y in the
preceding expansion and identifying coefficients of i on both sides yields the inversion formula. 2
There is a simple combinatorial interpretation of the polarization of the weight enumerator of a code.
The code obtained from C by puncturing (resp. shortening) at coordinate place i will be denoted
by We shall denote by C the coset of C=i into C \Gamma i. We shall say that a code is
homogeneous if the codewords of every given weight hold a 1-design, and more generally t-homogeneous
if the codewords of every given weight hold a t-design.
In that situation, the Jacobi polynomial J C;T does not depend on T for t; and for convenience,
this common value is denoted J
Theorem 3 For every binary code C and every coordinate place i we get
If C contains no word of weight 1 we have
If C is 1\Gammahomogeneous then
Proof:The first and second assertion are restatements of the definition of the Jacobi polynomial and
of the polarization operator. The third assertion follows by noticing that, in the second assertion, for an
homogeneous code the polynomials WC=i and WC+i are independent of i: It also follows from [22, Pb. (37)
p.233] which is a re-statement of Prange Theorem [21, Th. 80] in terms of generating series. 2
The generalization for all t is a bit more cumbersome to write down but no more difficult. We leave the
proof to the reader.
Theorem 4 If C is t\Gammahomogeneous and contains no word of weight - t then
A useful corollary concerns children C of a self-dual code D obtained by subtraction, i.e. taking all
codewords whose value on two given coordinates is 00 or 11 and puncturing at those places.
Corollary 1 If D is a self-dual t\Gammahomogeneous binary code with t - 2 then the weight enumerator of C is
As an application we recover the weight enumerators of both the extremal [70; 35; 14] [11, 18] extremal
Type I code and the elusive shadow extremal [68; 34; 12] code obtained [11] by subtraction from the putative
extremal [72; 36; 16] Type II code, whose Jacobi polynomials are calculated in x6.5. They are, respectively,
and
5.1 When polarization fails
The question arises: how many invariants in w; z; x; y are polarizations of invariants in x; y? The answer is
given in terms of generating series. Let D denote the bivariate generating series enumerating by bidegree the
invariants in four variables that cannot be obtained by successive polarizations of two-variable invariants.
Proposition denote the Molien series of G
Proof:By the injectivity of the polarization operation every term m j u j in the Taylor series of M (u)
yields geometrically as m j
The Taylor series up to degree 40 can be written in decresing degree order as:
In this case we use the Reynolds operator which is defined as in [22, p.609]. Let M 2 G 2 . Denote its
action on P (w; z; x; y) as M ffi P: With these notations we define the Reynolds operator as
The following result is a special case of [22, Th.4,p.609].
Proposition 2 The polynomial R ffi P is a simultaneous invariant of G
An example is given in x5.1. It was shown by EmmyNoether in 1916 that all invariants can be constructed
in that way [26, Th. 2.1.4].
6 Examples
Let w 8 and g 24 denote the weight enumerator of the extended Hamming and Golay codes of length 8 and
24: These codes hold respectively 3\Gamma and 5\Gamma designs. Let J 8;t and J 24;m denote for t - 3 and m - 5 their
Jacobi we corresponding to coset leaders of weight t and m. Similarly for the code E 16 of [20] let J 16;i be
the Jacobi polynomial of index i for 2: We denote by f [a] the homogeneous part of degree a of the
Molien Series f:
6.1 Length 8
This corresponds to J 8;s with 3: Alternatively this corresponds to A s w 8 with 3: As the
coefficient of w s y 8\Gammas in J 8;s should be 1; and the coefficient of u n\Gammas v s in the Molien series f(u; v) is 1 we
see that for
This also follows from Theorem 1. Specifically we get:
To actually compute a basis of the invariant space, we use the Reynolds operator acting on (wzxy) 2 which
gives, up to scalar multiple
r := (w 4
Let T be of size 4: Then we know that J C;T is a combination of r and AJ 8;3 . Two cases occur:
1. If T supports a codeword, then it can be seen combinatorially (minimum distance 4 and so on) that
2. If T does not support a codeword then J r)=4 as the term in x 4 z 4 must vanish
6.2 Length
This counts
The calculation of J 16;1 is consistent with [1, p.361, Table I].
Taking the linear combination
8;1 )=3 we obtain
which yields after the substitution x the coset weight enumerator
Similarly the linear combination
8;1 )=21 yields the Jacobi polynomial
which corresponds to the coset weight distribution
Combining these two equations (accounting for all the
2-designs
with parameters
This gives packing and covering designs
In fact these are indeed GDD's with parameters
because the 8 pairs in the same coset are disjoint, the minimum distance being 4:
The space of Jacobi polynomials J d16 ;T with jT may be generated by the two polynomials J 1631 =42 A 3 w
which gives the packing and covering designs
The space of Jacobi polynomials J d16 ;T with jT may be generated by the following three polynomials
z
which gives the packing and covering designs
d
d
6.3 Length 24
This counts respectively
Observe that
This is consistent with the Pascal triangle for the Witt design on 24 points [22, p.68].
In this paragraph, we call B 6 the basis of invariants for jT
The space of Jacobi polynomials JG24;T with jT generated by two polynomials. If T is not contained in
an octad, then it can be seen combinatorially (using that J C;T has the following decomposition
relatively to B 6
If we call J 2461 this polynomial, we have
Note that the coefficient of wz 5 x 15 y 3 is 6, which corresponds to the number of possible 5\Gammasets in T .
If T is contained in an octad, then J with the following decomposition
yielding
z 6 y
Note that this polynomial contains the monomial z 6 x which corresponds to an octad of the Golay.
From these polynomials, we obtain the packing and covering designs
Golay
Golay
Golay
Golay
Golay 5 NA 1 5
Golay 6 NA 2 6
6.4 Length
We focus our study on The Reed-Muller code of length 32. Observe that
From

Table

I in [9] it seems that the second order Reed Muller code in length would yield a 4-design
with 2 classes. Furthermore since the second type of coset contains exactly 8 vectors of weight 4 any such
coset define a partition of [32] into disjoint (by Hamming distance quadruples.
Consider the following two polynomials belonging to the invariant space
z 4 x
and
which correspond respectively to the two cosets of weight 4
and
14336 y 14 x
We obtain by this way a 4-design with parameters
and four other designs with parameters
From the packing and covering point of view
Note that the first covering design is the record owner in [15]. Here we know that b 4 is indeed 2. A basis of
the invariant space is given by J
The denotations of the codes and the information on a t are from [9]. CP means an extremal Type II
code of length 32.
6.5 Length 72
It is still an open problem to know if there exist a [72,36,16] binary type II code. However, its weight
enumerator can be computed by using invariant theory [17]. By theorem 1, the vectors of any given weight
in the code hold a 5-design. Theorem 4 then gives the Jacobi polynomials for jT
We have:
4397342400 x 44 y 28
4397342400 x 28 y 44
9223731055 zx 28 y 43
2119532800 wzx 43 y
43719104 w 3 zx 21 y
43719104 wz 3 x
30888000 z 5 x 44 y
z 5 y
28 y

Acknowledgements

P. Sol'e thanks Christine Bachoc and Eiichi Bannai for helpful discussions, and Michio Ozeki for sending him
[19]. A. Bonnecaze and P. Sol'e thank Allan Steel for programming help in Magma [3, 4].



--R

On the covering radius of extremal self-dual codes
Construction of Jacobi forms from certain combinatorial polynomials
The Magma algebra system I: The user language.
Magma: A new computer algebra system.

of Discr.
Extending the t
A strengthening of the Assmus-Mattson theorem
Cosets weight enumerators of the extremal self-dual binary codes of length

New Extremal Self-dual codes of Length 68
Contemporary Design Theory: a collection of surveys Wiley
The theory of Jacobi forms
Actes Congr'es International de Math'ematiques Nice
New Constructions for Covering Designs
A coding theoretic approach to extending designs
An upper bound for self-dual codes
On self-dual doubly even extremal codes
On the notion of Jacobi polynomials for codes
A classification of self-orthogonal codes over GF (2)
Introduction to the theory of error correcting codes
The theory of error-correcting codes
On the classification and enumeration of self-dual codes

Invariants of Finite Groups and their Applications to Combinatorics
Algorithms in Invariant Theory
--TR

--CTR
Christine Bachoc, On Harmonic Weight Enumerators of Binary Codes, Designs, Codes and Cryptography, v.18 n.1-3, p.11-28, December 1999
Y. Choie , P. Sol, A Gleason formula for Ozeki polynomials, Journal of Combinatorial Theory Series A, v.98 n.1, p.60-73, April 2002
group divisible designs;type II codes;jacobi polynomials;invariant theory;packing and covering designs