GEORGIAN MATHEMATICAL JOURNAL: Vol. 5, No. 5, 1998, 469-474

A NOTE ON WEIGHT ENUMERATORS OF LINEAR SELF-DUAL CODES

N. LOMADZE

Abstract. A partial description of (complete) weight enumerators of linear self-dual codes is given.

0. Let F = ℤ/pℤ, where p is a prime number. If C is a linear code on F of length n, i.e., a linear subspace in F^{n}, then its (complete) weight enumerator W_{C} is defined to be

∑_{u∈C} ( ∏_{a∈F} x_{a}^{s_{a}(u)}).

Here x_{a}, a ∈ F are indeterminates; s_{a}(u) denotes the number of entries of u in C equal to a. This is a homogeneous polynomial in p indeterminates of degree n. Define the additive character ψ of F by

k ↦ (e^{\frac{2πi}{p}} )^{k}, k ∈ F,

and let

A = \frac{1}{\sqrt{p}}(ψ(ij))_{i,j∈F} .

Further, for each a ∈ F, let U_{a} be the diagonal matrix with ψ(ai^{2}) at the (i, i)th place for each i ∈ F; for each b ∈ F^{∗}, let V_{b} be the matrix with 1 at the (bi, i)th place for each i and 0 elsewhere. One knows well that weight enumerators of linear self–dual codes are invariant relative to A, U_{a}, and V_{b} (see [2]). Therefore, a natural problem is to determine all invariants of these transformations. The problem seems to be difficult. At the moment there are solutions for the case p = 2 (Gleason) and p = 3 (McEliece) (see [2]).

In [3] we have described the invariant ring of A, which is undoubtely the most interesting transformation. The goal of this short paper is to describe

469 the invariants of A and V_{b}, b ∈ F^{∗}. It should be pointed out that the exposition is elementary and uses no technique of invariant theory of finite groups.

1991 Mathematics Subject Classification. 94B05, 13A50.

Key words and phrases. Linear code, character, group, polynomial, invariant, Gaussian sum.

1072-947X/98/0900-0469$15.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1998 Plenum Publishing Corporation

In what follows p ≠ 2. Let R = ℂ[(x_{a})_{a∈F} ] be the ring of polynomials with complex coefficients and let G be the group generated by A and V_{b}, b ∈ F^{∗}.

We remark that the generators of this group satisfy the following relations only:

(1) b ↦ V_{b} is a multiplicative homomorphism;

(2) A^{2} = V_{−1};

(3) V_{b}A = AV_{b^{−1}}.

1. Choose a generator b of the multiplicative group of F, and denote by V the transformation V_{b}. Let G_{0} be the subgroup in G generated by V. Clearly, G_{0} is isomorphic to F^{∗}. It is easy to see that G_{0} is a normal subgroup in G of index 2 and G = G_{0} ∪ AG_{0}.

Let us find the invariants of G_{0}. Denote by χ that multiplicative character of F which takes b to e^{\frac{2πi}{p−1}} . For each k = 0, 1, …, p − 2, put

y_{k} = ∑_{l=0}^{p−2} χ^{k}(b^{l})x_{b^{l}}.

Clearly, R = ℂ[x_{0}, y_{0}, y_{1}, …, y_{p−2}].

Lemma 1.1. One has

(1) V (x_{0}) = x_{0};

(2) V (y_{0}) = y_{0};

(3) V (y_{k}) = e^{− \frac{2πki}{p−1}} y_{k}, k = 1, …, p − 2.

Proof. (1) and (2) are obvious. To prove (3) take any y_{k} with k ≠ 0. We have

V (y_{k}) = ∑_{l=0}^{p−2} χ^{k}(b^{l})x_{b^{l+1}} = ∑_{l=1}^{p−1} χ^{k}(b^{l−1})x_{b^{l}} =

= χ^{−k}(b) ∑_{l=1}^{p−1} χ^{k}(b^{l})x_{b^{l}} = e^{− \frac{2πki}{p−1}} y_{k}.

Denote by I the set of all mappings i : [1, p − 2] → [0, p − 2] which satisfy the congruence

∑_{k=1}^{p−2} ki(k) ≡ 0 mod (p − 1).

For each i ∈ I, put η_{i} = y_{1}^{i(1)} ⋯ y_{p−2}^{i(p−2)}. Let R_{0} denote ℂ[x_{0}, y_{0}, y_{1}^{p−1}, …, y_{p−2}^{p−1}]. This is a subring in R.

Lemma 1.2. The invariant ring of G_{0} is R^{G_{0}} = ⊕_{i∈I}η_{i}R_{0}.

Proof. Let i run over all the mappings of [1, p − 2] into [0, p − 2]. Then, every element in R can be written uniquely as a sum

∑_{i} ( ∏_{k=1}^{p−2} y_{k}^{i(k)})f_{i},

where f_{i} ∈ R_{0}. Notice that V f = f for each f ∈ R_{0}. So letting c_{i} denote

(e^{− \frac{2πi}{p−1}} )^{∑_{k=1}^{p−2} ki(k)}, we have

V ( ∑_{i} ( ∏_{k=1}^{p−2} y_{k}^{i(k)})f_{i}) = ∑_{i} ( ∏_{k=1}^{p−2} y_{k}^{i(k)})c_{i}f_{i}.

One can therefore see that

V ( ∑_{i} ( ∏_{k=1}^{p−2} y_{k}^{i(k)})f_{i}) = ∑_{i} ( ∏_{k=1}^{p−2} y_{k}^{i(k)})f_{i}

if and only if, for each i, either c_{i} = 1 or f_{i} = 0. Certainly, c_{i} = 1 ⟺ i ∈ I.

2. For each k = 1, …, p − 2 put

τ(k) = \frac{1}{\sqrt{p}} ∑_{l=0}^{p−2} χ^{k}(b^{l})ψ(b^{l}).

These are the so-called Gaussian sums. They satisfy the relations

τ(k)τ(p − 1 − k) = χ^{k}(−1), k = 1, …, r − 1.

Here and below r = \frac{p−1}{2}. These relations are immediate consequences of Theorem 4 in [1, Ch. I, §2] and the fact that \overline{τ}(k) = χ^{k}(−1)τ(p − 1 − k). One has also

τ(r) = \begin{cases}1 if p ≡ 1mod 4, \\ i if p ≡ 3mod 4 \end{cases}

(see Theorem 7 in [1, Ch. V, §4]).

Lemma 2.1. One has

Ax_{0} = \frac{1}{\sqrt{p}}(x_{0} + y_{0}),
Ay_{0} = \frac{1}{\sqrt{p}}((p − 1)x_{0} − y_{0}),
Ay_{k} = τ(k)y_{p−1−k}, k = 1, …, p − 2.

Proof. This can easily be checked. See also [1, Ch. V, §4, Exercise 17]. From the above lemma follows in particular that

AR_{0} ⊆ R_{0}.

We want now to find the absolute and relative invariants of A belonging to R_{0}, in other words, those polynomials f, g ∈ R_{0} which satisfy the conditions

Af = f, Ag = −g.

Put

z_{01} = (1 + \sqrt{p})x_{0} + y_{0};
z_{02} = (1 − \sqrt{p})x_{0} + y_{0};
z_{k1} = y_{k}^{p−1} + τ(k)^{p−1}y_{p−1−k}^{p−1}, k = 1, …, r − 1;
z_{k2} = y_{k}^{p−1} − τ(k)^{p−1}y_{p−1−k}^{p−1}, k = 1, …, r − 1;
z_{r} = y_{r}^{p−1}.

Certainly, R_{0} = ℂ[z_{01}, z_{02}, z_{11}, z_{12}, …, z_{r−1,1}, z_{r−1,2}, z_{r}].

Lemma 2.2. One has

Az_{01} = z_{01}, Az_{02} = −z_{02},
Az_{k1} = z_{k1}, Az_{k2} = −z_{k2}, k = 1, …, r − 1;
Az_{r} = (−1)^{r}z_{r}.

Proof. Follows easily from the preceding lemma. One should have in mind the relations τ(k)^{p−1}τ(p − 1 − k)^{p−1} = 1 (k = 1, …, r − 1) and τ(r)^{p−1} = (−1)^{r}.

Consider two cases.

(1) p ≡ 1(mod 4). Let α, β run over all the mappings [0, r − 1] → {0, 1} satisfying the conditions

∑_{k=0}^{r−1} α(k) ≡ 0 mod 2, ∑_{k=0}^{r−1} β(k) ≡ 1 mod 2

respectively. Put

f_{α} = z_{02}^{α(0)} ⋯ z_{r−1,2}^{α(r−1)}, g_{β} = z_{02}^{β(0)} ⋯ z_{r−1,2}^{β(r−1)}.

Set

S_{1} = ⊕_{α}f_{α}ℂ[z_{01}, …, z_{r−1,1}, z_{02}^{2}, …, z_{r−1,2}^{2}, z_{r}],
S_{2} = ⊕_{β}g_{β}ℂ[z_{01}, …, z_{r−1,1}, z_{02}^{2}, …, z_{r−1,2}^{2}, z_{r}].

(2) p ≡ 3(mod 4). Let α, β run over all the mappings [0, r] → {0, 1} satisfying the conditions

∑_{k=0}^{r} α(k) ≡ 0 mod 2, ∑_{k=0}^{r} β(k) ≡ 1 mod 2,

respectively. Put

f_{α} = z_{02}^{α(0)} ⋯ z_{r−1,2}^{α(r−1)}z_{r}^{α(r)}, g_{β} = z_{02}^{β(0)} ⋯ z_{r−1,2}^{β(r−1)}z_{r}^{β(r)}.

Set

S_{1} = ⊕_{α}f_{α}ℂ[z_{01}, …, z_{r−1,1}, z_{02}^{2}, …, z_{r−1,2}^{2}, z_{r}^{2}],
S_{2} = ⊕_{β}g_{β}ℂ[z_{01}, …, z_{r−1,1}, z_{02}^{2}, …, z_{r−1,2}^{2}, z_{r}^{2}].

In both cases there holds the following

Lemma 2.3.

(a) S_{1} = {f ∈ R_{0}|Af = f} and S_{2} = {g ∈ R_{0}|Ag = −g};

(b) R_{0} = S_{1} ⊕ S_{2}.

Proof. Left to the reader.

3. We are now ready to describe the invariants of G.

For each i ∈ I, put

a_{i} = ∏_{k=1}^{p−2} τ(k)^{i(k)}.

For each i ∈ I, let \overline{i} be the function defined by the formula

\overline{i}(k) = i(p − 1 − k) k = 1, …, p − 2.

It is clear that \overline{i} ∈ I and \overline{\overline{i}} = i. Let I_{0} = \{i ∈ I|\overline{i} = i\}. The complement to I_{0} in I breaks into two parts I_{1} and I_{2} so that i ∈ I_{1} ⇒ \overline{i} ∈ I_{2} and i ∈ I_{2} ⇒ \overline{i} ∈ I_{1}.

Lemma 3.1. For each i ∈ I a_{i}a\overline{i} = 1.

Proof. We have

a_{i}a\overline{i} = ∏_{k=1}^{p−2} τ(k)^{i(k)} ∏_{k=1}^{p−2} τ(p − 1 − k)^{i(k)} =

= ∏_{k=1}^{p−2}(χ^{k}(−1))^{i(k)} = χ(−1)^{∑_{k=1}^{p−2} ki(k)} = 1.

Lemma 3.2. For each i ∈ I Aη_{i} = a_{i}η\overline{i}.

Proof. It is obvious.

Lemma 3.3. Suppose we are given a polynomial

∑_{i∈I} η_{i}h_{i} ∈ R^{G_{0}}

with h_{i} ∈ R_{0}. It is invariant under A if and only if, for each i, Ah_{i} = a\overline{i}h\overline{i}.

Proof. We have

A( ∑_{i∈I} η_{i}h_{i}) = ∑_{i∈I} η\overline{i}(a_{i}Ah_{i}).

From this and from the fact that AR_{0} ⊆ R_{0} follows the assertion. By Lemma 3.1, if i ∈ I_{0}, then a_{i} = ±1. Put

I_{01} = {i ∈ I_{0}|a_{i} = 1} and I_{02} = {i ∈ I_{0}|a_{i} = −1}.

Theorem. Every polynomial which is invariant relative to the action of G can be written uniquely as

∑_{i∈I_{01}} f_{i} + ∑_{i∈I_{02}} g_{i} + ∑_{i∈I_{1}}(η_{i}h_{i} + a_{i}η\overline{i}Ah_{i}),

where f_{i} ∈ S_{1}, g_{i} ∈ S_{2}, h_{i} ∈ R_{0}.

Proof. Follows from Lemmas 2.3 and 3.2.

References

1. Z. Borevich and I. Shafarevich, Number theory, 3rd ed. (Russian) Nauka, Moscow, 1985.

2. 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.

3. N. G. Lomadze, Formally self-dual polynomials. Problemy Peredachi Informatsii 24(1988), 22–30.

(Received 27.06.1996)

Author’s address:

Department of Applied Mathematics

Georgian Technical University

77, Kostava St., Tbilisi 380075

Georgia