GEORGIAN MATHEMATICAL JOURNAL: Vol. 4, No. 5, 1997, 451-460

ON MCELIECE’S THEOREM

N. LOMADZE

Abstract. A new simple proof of the well-known theorem of McEliece about the complete weight enumerators of ternary self-dual codes is given.

0. Introduction. Let C be a ternary linear code of length n. The complete weight enumerator of C is the homogeneous polynomial

W_{C}(x_{0}, x_{1}, x_{2}) = ∑_{i+j+k=n} A_{ijk}x_{0}^{i}x_{1}^{j}x_{2}^{k},

where A_{ijk} stands for the number of codewords that consist of i zeros, j ones, and k twos. One knows well that the function W_{C}(x_{0}, x_{1}, x_{2}) satisfies the MacWilliams identity

W_{C}(x_{0}, x_{1}, x_{2}) =

= W_{C}(\frac{1}{\sqrt{3}}(x_{0} + x_{1} + x_{2}), \frac{1}{\sqrt{3}}(x_{0} + ωx_{1} + ω^{2}x_{2}), \frac{1}{\sqrt{3}}(x_{0} + ω^{2}x_{1} + ωx_{2}))

(here and below ω = e^{2πi/3}); in other words, the polynomial W_{C} is invariant under the linear transformation

α = \frac{1}{\sqrt{3}} (\begin{matrix}1 & 1 & 1 \\ 1 & ω & ω^{2} \\ 1 & ω^{2} & ω \end{matrix}) .

Further, since the weight of any codeword of C is divisible by 3, one has

W_{C}(x_{0}, x_{1}, x_{2}) = W_{C}(x_{0}, ωx_{1}, ωx_{2});

451 this is equivalent to saying that the polynomial W_{C} is invariant under the linear transformation

Key words and phrases. Linear code, group, invariant, reflection, character, homogeneous polynomial.

1072-947X/97/0900-0451$12.50/0 \begin{matrix}c \\ ◯ \end{matrix} 1997 Plenum Publishing Corporation

β = (\begin{matrix}1 & 0 & 0 \\ 0 & ω & 0 \\ 0 & 0 & ω \end{matrix}) .

Thus the complete weight enumerator of the ternary self-dual code C is invariant relative to the group generated by the matrices α and β. Let \overline{G} denote this group. This is a group of cardinality 96. (See [1].)

The question of describing all invariants of this group arises naturally. This was done by McEliece using the method of invariant theory for finite groups. (See [1,2].) In this way McEliece obtained

Theorem. Let x = x_{0}, y = x_{1} + x_{2} and z = x_{1} − x_{2}. Then

W_{C}(x_{0}, x_{1}, x_{2}) ∈ ⊕_{k=0}^{5}h_{k}z^{2k}ℂ[f, ψ^{3}, z^{12}],

where

f = x^{4} + xy^{3}, ψ = y(8x^{3} − y^{3}), φ = 8x^{6} − 20x^{3}y^{3} − y^{6},
h_{0} = 1, h_{1} = φψ, h_{2} = ψ^{2}, h_{3} = φ, h_{4} = ψ, h_{5} = φψ^{2}.

The goal of this paper is to carry out a proof of this important theorem which, we believe, is much simpler and clearer than that given by McEliece [1].

Our approach is based on the following observation. The whole space on which \overline{G} acts splits up into a direct sum of two invariant irreducible subspaces, two-dimensional and one-dimensional ones. The “restriction” of \overline{G} on the two-dimensional subspace is therefore a two-dimensional group generated by reflections. Finding invariants of such a group (both absolute and relative) is very easy. Knowledge of all such invariants leads immediately to McEliece’s result.

It should be pointed out that the idea to apply invariant theory of finite groups to coding theory goes back to Gleason. Gleason himself described complete weight enumerators of binary codes. McEliece’s theorem is one of the most interesting generalizations of Gleason’s theorem.

Concluding the introduction, we would like to thank the anonymous referee for useful suggestions.

1. Preliminaries. We recall here the definitions and facts concerning invariant theory which are needed. For details we refer to [3–6]. We restrict ourselves to the two-dimensional case.

Let V be a two-dimensional complex vector space, and let R = ℂ[x, y] be the ring of polynomials in the variables x and y with complex coefficients.

Fix a basis (e_{1}, e_{2}) in V and identify via it transformations of V with nonsingular complex 2 × 2 matrices, and polynomials in R with complex valued functions on V.

The group GL_{2}(ℂ) of all nonsingular 2 × 2 matrices acts on R in the following way. If

M = (\begin{matrix}a & b \\ c & d \end{matrix}) ∈ GL_{2}(ℂ) and f = f(x, y) ∈ R,

then

Mf = f(ax + by, cx + dy).

Let Γ be a finite subgroup in GL_{2}(ℂ). A polynomial f ∈ R is said to be an invariant of Γ if

Mf = f for all M ∈ Γ.

Clearly, the invariants of Γ form a subring in R, denoted by R^{Γ}.

A character of the group Γ is a homomorphism of Γ into the multiplicative group of complex numbers. If χ is a character of Γ, then a polynomial f ∈ Γ is called a χ-invariant of Γ if

Mf = χ(M)f for all M ∈ Γ.

It is clear that the χ-invariants of Γ form a R^{Γ}-submodule in R which is denoted by R_{χ}^{Γ}.

A reflection of V is a transformation one of whose eigenvalues is equal to 1 and the other is distinct from 1. If P is a reflection, then the eigenvectors corresponding to 1 form a one-dimensional subspace in V, i.e., a line. This is called the reflecting line of P.

From now on we assume that Γ is generated by reflections. Let χ be a character of Γ and H be a line. Denote by Γ(H) the subgroup in Γ consisting of those transformations which are identical on H. The determinant induces an injective homomorphism of Γ(H) into the group ℂ^{∗} and hence Γ(H) is cyclic. Let s(χ, H) denote the least nonnegative integer s such that

χ(P) = (det P)^{s},  (1.1)

where P is any generator of Γ(H). This is well defined. Let L_{H} be any linear form which determines the line H. This is determined uniquely up to a constant factor. For any character χ of Γ, set

h_{χ} = ∏_{H} L_{H}^{s(χ,H)},  (1.2)

where H runs over different reflecting lines of reflections in Γ.

We shall need the following two lemmas.

Lemma 1.1. Suppose that the Molien series of Γ is

Φ(λ) = \frac{1}{(1 − λ^{d_{1}}) · (1 − λ^{d_{2}})},

where d_{1} and d_{2} are nonnegative integers. If Θ_{1} and Θ_{2} are algebraically independent homogeneous invariants of Γ having degrees d_{1} and d_{2}, respectively, then

R^{Γ} = ℂ[Θ_{1}, Θ_{2}].

Lemma 1.2. Let χ be a character of Γ. Then R_{χ}^{Γ} is a free R^{Γ}-module of rank 1 and

R_{χ}^{Γ} = h_{χ}R^{Γ}.

2. Group G. Let G denote the group generated by the matrices

A = \frac{1}{\sqrt{3}} (\begin{matrix}1 & 1 \\ 2 & −1 \end{matrix}) and B = (\begin{matrix}1 & 0 \\ 0 & ω \end{matrix}) .

Notice that A^{2} = E and B^{3} = E. For any integers k and l, set

A(k, l) = B^{k}AB^{l} = \frac{1}{\sqrt{3}} (\begin{matrix}1 & ω^{l} \\ 2ω^{k} & −ω^{k+l} \end{matrix}) .

One can easily check that

A(k, l) · A(m, n) = \begin{cases}B^{k+n} & if l + m ≡ 0 (mod 3), \\ iA(k + 2, n + 2) & if l + m ≡ 1 (mod 3), \\ −iA(k + 1, n + 1) & if l + m ≡ 2 (mod 3). \end{cases}

This computation leads to

Lemma 2.1. G is a disjoint union

G = {i^{α}A(k, l)} ∪ {i^{β}B^{m}},

where 0 ≤ α, β ≤ 3, 0 ≤ k, l, m ≤ 2.

This lemma implies in particular that G consists of 48 elements.

It is clear that among the transformations i^{β}B^{m} only B and B^{2} are reflections. A transformation i^{α}A(k, l) is not identical and therefore is a reflection if and only if 1 is a root of its characteristic polynomial, i.e., when

1 + \frac{i^{α}}{\sqrt{3}}(ω^{k+l} − 1) − (−1)^{α}ω^{k+l} = 0.

Considering separately the cases α = 0, 1, 2, 3 we find that i^{α}A(k, l) is a reflection if and only if (α, k, l) is one of the following:

\begin{matrix}(000), (021), (012), (200), (221), (212), \\ (110), (101), (122), (320), (311), (302). \end{matrix}  (2.1)

Thus we have

Lemma 2.2. The group G possesses 14 reflections. These are

A_{0} = B, A_{1} = A, A_{2} = B^{2}AB, A_{3} = BAB^{2},

A_{4} = −A, A_{5} = −B^{2}AB, A_{6} = −BAB^{2}, A_{7} = iBA,

A_{8} = iAB, A_{9} = iB^{2}AB^{2}, A_{10} = −iB^{2}A, A_{11} = −iBAB,

A_{12} = −iAB^{2}, A_{13} = B^{2}.

The vector ae_{1} + be_{2} ∈ V is invariant under the reflection i^{α}A(k, l) if and only if

(i^{α} − \sqrt{3})a + (i^{α}ω^{l})b = 0.

Hence the reflecting line of i^{α}A(k, l) is given by the linear form

L = (i^{α} − \sqrt{3})x + (i^{α}ω^{l})y.  (2.2)

It is obvious that the reflecting line of both B and B^{2} is given by the linear form L = y.

Denote by H_{i} the reflecting line of A_{i} and by L_{i} the corresponding linear form. Here i = 0, ..., 13. Substituting the triples (α, k, l) from table (2.1) into (2.2) we get the linear forms L_{i} (i = 1, ..., 12). It is easy to see that

H_{0} = H_{13}, H_{7} = H_{12}, H_{8} = H_{10}, H_{9} = H_{11}.

Thus we have

Lemma 2.3. The reflections of G have 10 different reflecting lines determined by the following linear forms:

\begin{matrix}L_{0} = y, & L_{1} = (1 − \sqrt{3})x + y, \\ L_{2} = (1 − \sqrt{3})x + ωy, & L_{3} = (1 − \sqrt{3})x + ω^{2}y, \\ L_{4} = (1 + \sqrt{3})x + y, & L_{5} = (1 + \sqrt{3})x + ωy, \\ L_{6} = (1 + \sqrt{3})x + ω^{2}y, & L_{7} = (i − \sqrt{3})x + iy, \\ L_{8} = (i − \sqrt{3})x + iωy, & L_{9} = (i − \sqrt{3})x + iω^{2}y. \end{matrix}

3. Absolute Invariants of G. To begin with we remark that the group G^{tr} obtained from the group G by transposing its matrices was considered by Gleason when he studied the Hamming weight enumerator of a selfdual linear code over GF (3). (See [1,3].) In particular, he computed the Molien series of this group. Since the transposition does not change the characteristic polynomial of a matrix, we can use his result. Letting Φ denote the Molien series of G we have

Φ(λ) = \frac{1}{(1 − λ^{4})(1 − λ^{12})}.

The series tells us that there are two algebraically independent invariants of degrees 4 and 12.

Lemma 3.1.

(a) The polynomial f = x^{4} + xy^{3} is a unique (up to a nonzero constant multiple) homogeneous invariant of degree 4.

(b) The polynomial g = y^{3}(8x^{3} − y^{3})^{3} is a unique (up to a nonzero constant multiple) homogeneous invariant of degree 12 which does not contain the term x^{12}.

Proof. We remark that a polynomial which is invariant with respect to B must be a linear combination of monomials of the form

x^{i}y^{3j}.

(a) A homogeneous invariant of degree 4 has the form ax^{4} + bxy^{3} where a and b are the complex numbers and at least one of them is not zero. Since this polynomial is invariant with respect to A, we have

f = x(ax^{3} + by^{3}) = \frac{1}{\sqrt{3}}(x + y)h(x, y),  (3.1)

where h(x, y) = A(ax^{3} + by^{3}). Putting y = 1 in (3.1) we get x(ax^{3} + b) = \frac{1}{\sqrt{3}}(x + 1)h(x, 1). It follows that the number −1 is a root of the binomial ax^{3} + b, and so a = b. Taking a = b = 1 we get the polynomial f. Indeed, f is an invariant of A and B. This can be easily checked.

(b) A homogeneous invariant of degree 12 which does not contain x^{12} has the form

g = y^{3}(ax^{9} + bx^{6}y^{3} + cx^{3}y^{6} + dy^{9}),  (3.2)

where a, b, c, d are the complex numbers and at least one of them is not zero. The condition that this is invariant with respect to A implies that

y^{3}(ax^{9} + bx^{6}y^{3} + cx^{3}y^{6} + dy^{9}) = \frac{1}{3\sqrt{3}}(2x − y)^{3}h(x, y),  (3.3)

where h(x, y) = A(ax^{9} + bx^{6}y^{3} + cx^{3}y^{6} + dy^{9}). Putting y = 1 in (3.3) we get

ax^{9} + bx^{6} + cx^{3} + d = \frac{1}{3\sqrt{3}}(2x − 1)^{3}h(x, 1).

We see that the number 1/2 is a root of the polynomial ax^{9} + bx^{6} + cx^{3} + d of multiplicity 3. Hence 1/2 is a root of this polynomial and of its first and second derivatives as well.

We therefore have

\begin{cases}a(1/2)^{9} + b(1/2)^{6} + c(1/2)^{3} + d & = 0, \\ 9a(1/2)^{8} + 6b(1/2)^{5} + 3c(1/2)^{2} & = 0, \\ 72a(1/2)^{7} + 30b(1/2)^{4} + 6c(1/2) & = 0. \end{cases}  (3.4)

Solving this system of linear equations we find that

a = −8^{3}d, b = 3 · 8^{2}d, c = −3 · 8d.

System (3.4) has only one solution (up to a constant factor)

a = 8^{3}, b = −3 · 8^{2}, c = 3 · 8, d = −1.

Substituting these values into (3.2) we get the polynomial g. It is easily checked that g is an invariant.

Lemma 3.2. The polynomials f and g are algebraically independent.

Proof. We recall that the main term of a polynomial is defined to be the first term in its standard representation (see [3], for example.) Let ∑_{i,j} c_{ij}f^{i}g^{j} = 0, where c_{ij} ∈ ℂ. The main term of f is x^{4}, and the main term of g is 8^{3}x^{9}y^{3}. Hence the main term of f^{i}g^{j} is 8^{3j}x^{4i+9j}y^{3j}. It is clear that different summands in the ∑_{i,j} c_{ij}f^{i}g^{j} have different main terms. From this it follows that all c_{ij} are equal to 0.

Applying now Lemma 1.1 we get

Proposition 3.1.

R^{G} = ℂ[f, g].

4. Relative Invariants of G. The determinant clearly induces a character of G. Let χ denote this character. Since det A = −1 and det B = ω, the image of χ is the group μ_{6} = {±1, ±ω, ±ω^{2}}. This is a cyclic group. Let G_{1} be the kernel of χ. Clearly, G/G_{1} is a maximal abelian quotient group of G, and since it is cyclic, we have

Lemma 4.1. The characters of G are χ^{k} (k = 0, …, 5).

Let us describe all R^{G}-modules

R_{k}^{G} = R_{χ^{k}}^{G} = {f ∈ R|Mf = χ^{k}(M)f, ∀M ∈ G} (k = 0, …, 5).

We have

G(H_{0}) = {B, B^{2}, E}, G(H_{i}) = {A_{i}, E} (i = 1, …, 6),

G(H_{7}) = {A_{7}, A_{12}, E}, G(H_{8}) = {A_{8}, A_{10}, E}, G(H_{9}) = {A_{9}, A_{11}, E}.

For any integer k and any positive integer m denote by k (mod m) the least nonnegative residue of k modulo m. Applying (1.1) and Lemma 4.1, it is easy to see that

\begin{matrix}s(χ^{k}, H_{i}) = k (mod 2) (i = 1, …, 6; k = 0, …, 5), \\ s(χ^{k}, H_{i}) = k (mod 3) (i = 0, 7, 8, 9; k = 0, …, 5). \end{matrix}  (4.1)

By (1.2) we have

h_{k} = h_{χ^{k}} = ∏_{i=0}^{9} L_{i}^{s(χ^{k},H_{i})} (k = 0, …, 5).

Applying Lemma 2.3 and (4.1) we find that

h_{k} = φ^{k (mod 2)}ψ^{k (mod 3)} (k = 0, …, 5),

where

φ = − ∏_{j=0}^{2} ((1 − \sqrt{3})x + ω^{j}y)((1 + \sqrt{3})x + ω^{j}y) = 8x^{6} − 20x^{3}y^{3} − y^{6},

ψ = \frac{y}{i} ∏_{j=0}^{2} ((1 − \sqrt{3})x + iω^{j}y) = y(8x^{3} − y^{3}).

So we have

h_{0} = 1, h_{1} = φψ, h_{2} = ψ^{2}, h_{3} = φ, h_{4} = ψ, h_{5} = φψ^{2}.

Applying now Lemma 1.2 we get

Proposition 4.1. For k = 0, …, 5,

R_{k}^{G} = h_{k}ℂ[f, ψ^{3}].

5. Proof of McEliece’s Theorem. Let us introduce new variables

x = x_{0}, y = x_{1} + x_{2}, z = x_{1} − x_{2}.

The matrix α becomes then

\frac{1}{\sqrt{3}} (\begin{matrix}1 & 1 & 0 \\ 2 & −1 & 0 \\ 0 & 0 & \sqrt{3}i \end{matrix}) .

The matrix β does not change. Take any polynomial P ∈ ℂ[x, y, z] and write it as

P = ∑_{k=0}^{∞} p_{k}z^{k}

with p_{k} ∈ ℂ[x, y]. Certainly, for all but finitely many k, p_{k} = 0.

We have

αP = ∑_{k=0}^{∞} αp_{k} · αz^{k} = ∑_{k=0}^{∞} i^{k}(Ap_{k})z^{k},

βP = ∑_{k=0}^{∞} βp_{k} · βz^{k} = ∑_{k=0}^{∞} ω^{k}(Bp_{k})z^{k}.

We see that P is invariant with respect to the transformations α and β if and only if, for all k = 0, 1, 2, …

\begin{cases}p_{k} = i^{k}Ap_{k}, \\ p_{k} = ω^{k}Bp_{k}. \end{cases}  (5.1)

Notice that if p is a nonzero polynomial in ℂ[x, y] such that p = i^{k}Ap for some k, then k must be even. This is because A^{2} = E. Thus system (5.1) takes the form

\begin{cases}p_{k} = i^{2k}Ap_{k}, \\ p_{k} = ω^{2k}Bp_{k}. \end{cases}

This is equivalent to

\begin{cases}Ap_{k} = (−1)^{k}p_{k} = χ^{k (mod 6)}(A)p_{k}, \\ Bp_{k} = ω^{k}p_{k} = χ^{k (mod 6)}(B)p_{k}. \end{cases}  (5.2)

System (5.2) is equivalent to the condition

p_{k} ∈ R_{k (mod 6)}^{G}.

Hence P is an invariant of \overline{G} if and only if

P = ∑_{k=0}^{∞} p_{k}z^{2k},

where p_{k} ∈ ℂ[x, y]. By Proposition 4.1,

p_{k} = h_{k (mod 6)}r_{k}, r_{k} ∈ ℂ[f, ψ^{3}].

Therefore

P = ∑_{k=0}^{∞} h_{k (mod 6)}r_{k}z^{2k} =

= ∑_{k=0}^{5} h_{k}z^{2k}( ∑_{i=0}^{∞} r_{k+6i}z^{12i}) ∈ ⊕_{k=0}^{5}h_{k}z^{2k}ℂ[f, ψ^{3}, z^{12}].

It follows that the ring of invariants of the group \overline{G} is

R\overline{G} = ⊕_{k=0}^{5}h_{k}z^{2k}ℂ[f, ψ^{3}, z^{12}].

References

1. F. J. MacWilliams, C. L. Mallows, and N. J. A. Sloane, Generalizations of Gleason’s theorem on weight enumerators of self-dual codes. IEEE Trans. Inform. Theory 18(1972), 794–805.

2. C. L. Mallows, V. Pless, and N. J. A. Sloane, Self-dual codes over GF(3). SIAM J. Appl. Math. 31(1976), 649–666.

3. F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. North-Holland, Amsterdam, 1977.

4. N. J. A. Sloane, Error-correcting codes and invariant theory: new applications of a nineteenth-century technique, Amer. Math. Monthly 84(1977), 82–107.

5. T. A. Springer, Invariant theory. Lecture Notes in Math. 585, Springer-Verlag, Berlin, 1977.

6. R. P. Stanley, Invariants of finite groups and their applications to combinatorics. Bull. Amer. Math. Soc. (N.S.) 1(1979), 475–511.

(Received 12.09.95)

Author’s address: Georgian Technical University Department of Applied Mathematics 77, Kostava St., Tbilisi 380075 Georgia