An Introduction to Pless Moments through the MacWilliams Identity

One of the fundamental theorems in coding theory is the MacWilliams identity. Let $E$ be the coordinate set, let $n = \card{E}$, and let $C \leq \F_{q}^{E}$ be a linear code over the finite field $\F_{q}$. For $C$, consider its dual code

where

is the standard inner product. In this note, for a word $c \in \F_q^E$, write

Define the weight enumerator of the linear code $C$ by

The MacWilliams identity is the formula saying that the weight enumerator of the dual code can be computed from the weight enumerator of $C$ as follows:

This is the MacWilliams identity.

In this series, I use proofs of the MacWilliams identity as a guide to an introduction to neighbouring areas and concepts. Accordingly, this series is aimed at readers who already know the following basic material in coding theory:

We assume familiarity, at least at a basic level, with

• what a (finite) field is,

• what a linear code over a finite field is,

• what the Hamming weight is,

• what the dual code is.

(There is no problem if you do not know a proof of the MacWilliams identity.)

This note does not assume Parts 1–5. Krawtchouk polynomials and association schemes appear in the background at some points, but this note does not use their theory. The only tools needed here are weight distributions, moments, binomial coefficients, double counting, and finite-dimensional linear algebra.

In this series, I look at proof methods for the MacWilliams identity under the following five broad families.

1. Fourier, character, and Poisson methods.

2. Möbius inversion, lattice-theoretic, and shortening/puncturing methods.

3. Orthogonal-polynomial and association-scheme methods.

4. Matroid and Tutte-polynomial methods.

5. Moment and double-counting methods.

In this note, I focus on the last of these: the moment and double-counting approach. The aim of this note is to use a proof of the MacWilliams identity as a guide to an introduction to Pless moments, especially moments of the weight distribution and double counting.

Write the weight distribution as

Then the weight enumerator is

From another point of view, using Krawtchouk polynomials and Hamming schemes, one can regard the MacWilliams identity as a transform of the weight distribution itself. Here a Hamming scheme is, roughly speaking, the combinatorial structure obtained by classifying two words according to their Hamming distance. However, this note does not use its theoretical definition or general theory. Here, instead of transforming the weight distribution directly, we first look at

as moments.

In probability theory, one studies means, variances, and higher moments in order to understand a distribution. We shall do the same here. However, the moments used in this note are not expectations obtained by normalising to a probability distribution. They are moments as sums over all codewords. If one wants to view them as probabilistic means or expectations, one should divide these quantities by $\card{C}$. That said, in coding theory, moments involving binomial coefficients $\binom{w}{r}$ are more natural than moments involving ordinary powers $w^{h}$. The reason is that $\binom{\wt(c)}{r}$ is the number of ways to choose $r$ coordinates from the non-zero coordinates of the codeword $c$. Therefore

counts pairs consisting of a codeword and a coordinate set. By counting this quantity in two ways, Pless moment identities appear.

The flow of this note is as follows.

In Pless's classical paper [Ple63], power moment identities are derived from the MacWilliams identity, and applications are also given. In this note, I do not take the MacWilliams identity as known. Instead, I compute the binomial moments directly by double counting and explain how the MacWilliams identity can be recovered from sufficiently many moments. For the classical treatment of the weight distribution of the dual code and the MacWilliams equations, see MacWilliams–Sloane [MS77, Chapter 5]. For equivalent formulations including the MacWilliams equations and Pless moments, Huffman–Pless [HP03, Sections 7.1–7.2] is a standard reference. For a textbook treatment of Pless moments, see also Pless [Ple98, Chapter 8].

First, view the weight distribution as a sequence. Let $C \leq \F_{q}^{E}$ be a linear code, and write

This sequence $(A_{0}, A_{1}, \dots, A_{n})$ is the weight distribution of $C$.

In order to collect the weight distribution into a one-variable polynomial, set

This $P_{C}(t)$ is the dehomogenisation of the weight enumerator $W_{C}(X,Y)$. Indeed, we may read

Here $Y/X$ is a formal substitution, and in the end both sides are compared as polynomials.

When $h = 0$, we use the convention $0^{0} = 1$, and hence

When $h = 1$, this is the total weight of all codewords,

When $h=2$, it is the sum of the squares of the weights.

In coding theory, however, the following binomial moments are easier to handle than power moments.

Here we use the convention $\binom{w}{r}=0$ for $w < r$. The meaning of a binomial moment is very concrete. If we fix a codeword $c \in C$, then $\binom{\wt(c)}{r}$ is the number of ways to choose $r$ coordinates from $\supp(c)$. Thus the $r$-th binomial moment $M_{r}(C)$ counts pairs of the following form:

This viewpoint of counting pairs is the entrance to the Pless moment identity.

Binomial moments appear as the coefficients when the polynomial $P_{C}(t)$ is expanded around $t = 1$.

This theorem shows that the binomial moments determine the distribution completely.

This theorem is important in the proof in this note. The MacWilliams identity is a formula relating entire weight distributions. However, even without handling the whole weight distribution directly, one can recover the weight distribution once all binomial moments are known. Therefore, to find the weight distribution of the dual code, it is enough to find all binomial moments of the dual code.

We now count binomial moments. Let $C$ be an $[n,k]$ linear code over $\F_{q}$, that is, let $\dim_{\F_{q}} C = k$. Thus $\card{C} = q^{k}$. We write the number of dual codewords of weight $j$ simply as $A_{j}(C^{\perp})$.

The binomial moment $\displaystyle M_{r}(C) = \sum_{w = 0}^{n} A_{w}(C) \binom{w}{r}$ counts pairs

We first count these pairs with $S$ fixed.

With this notation,

For fixed $S$, the number $N_{C}(S)$ is the number of codewords for which all coordinates in $S$ are non-zero. Notice that no condition is imposed on the coordinates outside $S$. Thus $N_{C}(S)$ is not the number of codewords whose support is exactly $S$; it is the number of codewords which are non-zero at least on $S$. The condition of being non-zero is not a linear condition, so we first rewrite it in terms of the linear condition of specifying which coordinates are zero.

For $T \subseteq S$, consider all codewords whose coordinates in $T$ are all zero. This is a linear subspace. Consider the restriction map to the coordinates in $T$,

Its kernel is

If $Z_{e} = \{ c \in C : c_{e} = 0\}$, then $N_{C}(S)$ is the number of codewords which do not belong to any of the $Z_{e}$ with $e \in S$. Therefore, by inclusion–exclusion,

Next, we write $\card{\Ker(\rho_{T})}$ using information from the dual code. Let

denote the dual codewords whose support is contained in $T$. This is not the shortened code of $C^{\perp}$ on $T$ itself. It is the subspace consisting of those codewords on $E$ whose support is contained in $T$.

This lemma is the linear-algebraic core of the double counting. The size of the kernel of the coordinate restriction map of $C$ is expressed by the number of codewords in $C^{\perp}$ whose support is contained in $T$. The right-hand side contains $q^{k-\card{T}}$, so when $\card{T} > k$ it may look as if a fraction has appeared. However, this is just a rewriting of $\card{\Ker(\rho_{T})}=\card{C}/\card{\rho_{T}(C)}$ using the size of an orthogonal complement, and in the end it is always an integer. Equivalently, in that case $\card{C^{\perp}(T)}$ contains the missing power of $q$.

From the preparation in the previous section, we obtain a formula for binomial moments. This is the binomial-moment version of the Pless moment identity.

This formula has quite a meaningful form. The left-hand side is the $r$-th binomial moment of $C$. The right-hand side involves only the numbers of codewords in $C^{\perp}$ of weights $0, 1, \dots, r$. Thus the low moments of $C$ are controlled by the low-weight part of the dual code.

For example, when $r = 0$, the formula is

This is simply $\card{C} = q^{k}$. When $r = 1$, we get

If $C^{\perp}$ has no codeword of weight $1$, then

The absence of a dual codeword of weight $1$ means that the map $c \mapsto c_{e}$ to each coordinate is not the zero map. A non-zero linear map $C \to \F_{q}$ is surjective, so at each coordinate $0$ appears $q^{k - 1}$ times, and non-zero values appear altogether $(q - 1)q^{k - 1}$ times. Summing this over all coordinates gives the expression $q^{k - 1}(q - 1)n$ above. This agrees with the intuition that, on average, each coordinate is non-zero in the ratio $q - 1$ to $1$.

When $r = 2$, the formula is

Here the codewords of weights $1$ and $2$ in the dual code appear as correction terms for the second moment.

Pless identities are often written not in terms of binomial moments, but in the form of power moments $\sum_{w = 0}^{n} A_{w}(C) w^{h}$. To pass from binomial moments to power moments, we use Stirling numbers.

Since

we have

This is the classical power moment identity originating in Pless [Ple63]. Its appearance is a little complicated, but its structure is simple. First, expand the power $w^{h}$ as a linear combination of binomial coefficients $\binom{w}{r}$. Then compute the binomial moments by double counting.

What is especially important is that only the low-weight distribution of the dual code appears on the right-hand side. When $h \leq n$, it is enough to know the numbers of codewords in $C^{\perp}$ of weights $0, 1, \dots, h$. In general, the required weights are $0, 1, \dots, \min(h,n)$. This property is very useful when determining the weight distribution of concrete codes.

So far, we have proved Pless's binomial moment identity. Next, we recover the MacWilliams identity from this identity. The key point is to collect the binomial moments into a generating function.

If $C$ is an $[n,k]$ code, then $C^{\perp}$ is an $[n,n-k]$ code. Apply Theorem 5.1 (Pless's binomial moment identity)Let $C \leq \F_{q}^{E}$ be an $[n, k]$ linear code. Then, for $0 \leq r \leq n$, $$\sum_{w=0}^{n} A_{w}(C)\binom{w}{r} = q^{k - r} \sum_{j = 0}^{r} (-1)^{j}(q - 1)^{r-j} \binom{n - j}{r - j} A_{j}(C^{\perp}) \tag{5.1}$$ holds.Theorem 5.1 to $C^{\perp}$. Since $(C^{\perp})^{\perp} = C$, if we write $A_{w} = A_{w}(C)$, then the binomial moments of $C^{\perp}$ are

On the other hand, by Theorem 3.1Let $P_{C}(t) = \sum_{w = 0}^{n} A_{w}(C) t^{w}$. Then $$P_{C}(1 + z) = \sum_{r = 0}^{n} M_{r}(C) z^{r}$$ holds.Theorem 3.1,

Substituting $$M_{r}(C^{\perp}) = q^{n - k - r} \sum_{w = 0}^{r} (-1)^{w}(q - 1)^{r - w} \binom{n - w}{r - w} A_{w}. \tag{7.1}$$(7.1), we obtain

Putting $r = w + s$, the inner sum becomes

Therefore

Now set $t \coloneqq 1 + z$. Then

so $$P_{C^{\perp}}(1 + z) = \frac{1}{\card{C}} \sum_{w = 0}^{n} A_{w}(-z)^{w} \bigl( q + (q - 1)z \bigr)^{n - w}. \tag{7.2}$$(7.2) becomes

Finally, we homogenise this one-variable identity. Since $P_{C^{\perp}}(t) = W_{C^{\perp}}(1, t)$, formally putting $t = Y/X$ and multiplying both sides by $X^{n}$ gives

This is a calculation as a polynomial identity. Thus the MacWilliams identity has been obtained.

In this proof, we did not use Krawtchouk polynomials by name. However, in the process of collecting binomial moments into a generating function, essentially the same transform coefficients appear in a different guise. The difference is that, in the present viewpoint, we do not transform the weight distribution all at once. Instead, we first compute all moments and then recover the distribution from them.

Let us recover the weight distribution of a dual code from moments in a small example. Consider the repetition code over $\F_{2}^{3}$

This is a $[3,1]$ code, and its weight distribution is

The dual code $C^{\perp}$ is the set of all words of even weight,

so the answer should be

Here we recover this from Pless moments.

The code $C^{\perp}$ is a $[3,2]$ code. Applying Pless's binomial moment identity to $C^{\perp}$ and using $(C^{\perp})^{\perp} = C$, we get

Here $q = 2$, so $(q - 1)^{r - w} = 1$.

We compute these in order. For $r = 0$,

For $r = 1$,

For $r = 2$,

For $r = 3$,

Therefore

Putting $z = t - 1$, we get

Thus

and the weight distribution is recovered as

In this example, we confirmed the answer by listing the elements of the dual code directly. From the viewpoint of Pless moments, however, we first computed $M_{0}(C^{\perp})$, $M_{1}(C^{\perp})$, $M_{2}(C^{\perp})$, $M_{3}(C^{\perp})$, then recovered $P_{C^{\perp}}(t)$, and finally read off the weight distribution. The flow is not to guess the distribution directly, but to determine it through its moments.

Let us organise the role played by Pless moments in the proof.

First, we introduced the viewpoint of studying the weight distribution through moments. Instead of handling the weight distribution $(A_{0}, A_{1}, \dots, A_{n})$ directly, we looked at

This is the idea of studying a distribution through sum-type quantities which, after normalisation, correspond to means and higher means, and through binomial moments.

Second, binomial moments naturally became counting problems. The quantity $\displaystyle \sum_{w=0}^{n} A_{w}(C) \binom{w}{r}$ counts pairs consisting of a codeword $c \in C$ and an $r$-element subset $S$ contained in its non-zero coordinates. For this reason, binomial moments are well suited to double counting.

Third, during the double counting, the low-weight distribution of the dual code appeared. To count codewords whose coordinates in $S$ are all non-zero, we used inclusion–exclusion, and expressed the kernel of a coordinate restriction map using the part of the dual code with small support. As a result, the $r$-th binomial moment involved only the numbers of codewords in $C^{\perp}$ of weights $0, 1, \dots, r$.

Fourth, collecting all binomial moments allowed us to recover the whole weight distribution. Using the generating function

the moment sequence is precisely the sequence of coefficients in the expansion of the weight distribution polynomial around $t = 1$. Thus sufficiently many moments determine the distribution itself.

The point of the proof in this note can be summarised in the following sentence.

The MacWilliams identity is not only a formula which directly transforms the weight distribution; it is also the generating-function version of the Pless moment identity saying that the low-weight distribution of the dual code controls the moments of the original code.

In this part, while aiming at a proof of the MacWilliams identity, we introduced the basic tools of Pless moments. They may be organised as follows.

Weight distribution

For a code $C$, this is the sequence defined by

$$A_{w}(C) = \card{\{ c \in C : \wt(c) = w \}}.$$

The weight enumerator collects this sequence into a two-variable polynomial.

Power moment

This is a quantity of the form

$$\sum_{w = 0}^{n} A_{w}(C) w^{h}.$$

It measures the weight distribution using the $h$-th powers of the weights.

Binomial moment

This is the quantity defined by

$$M_{r}(C) = \sum_{w = 0}^{n} A_{w}(C) \binom{w}{r}.$$

It counts pairs consisting of a codeword and an $r$-element subset of its non-zero coordinates.

Moment generating function

For the dehomogenised weight enumerator $P_{C}(t) = W_{C}(1, t)$, we have

$$P_{C}(1 + z) = \sum_{r = 0}^{n} M_{r}(C) z^{r}.$$

Binomial moments are the coefficients in the expansion of $P_{C}(t)$ around $t = 1$.

Double counting

We viewed $M_{r}(C)$ in two ways: by counting from codewords, and by first fixing a coordinate set. In the latter method, inclusion–exclusion and coordinate restriction maps appear.

Pless's binomial moment identity

If $C$ is an $[n,k]$ code, then

$$\sum_{w=0}^{n} A_{w}(C)\binom{w}{r} = q^{k-r} \sum_{j=0}^{r} (-1)^{j} (q - 1)^{r - j} \binom{n - j}{r - j} A_{j}(C^{\perp})$$

holds. The $r$-th binomial moment is determined only by the distribution of the dual code from weight $0$ through weight $r$.

Pless power moment identities

By expanding the power $w^{h}$ as a linear combination of binomial coefficients $\binom{w}{r}$, one obtains a formula for power moments from the binomial moment identity. The Stirling numbers of the second kind appear as the conversion coefficients.