An Introduction to Krawtchouk Polynomials through the MacWilliams Identity

In coding theory, one of the basic theorems is the MacWilliams identity. Let $E$ be the coordinate set, let $n=\card{E}$, and let $C \leq \mathbb{F}_{q}^{E}$ be a linear code over the finite field $\mathbb{F}_{q}$. For its dual code

where

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 at least the following basic material:

We assume that the reader already knows, at least at a basic level, the following notions:

• 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.)

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 theory, and shortening/puncturing methods.

3. Orthogonal polynomials and association schemes.

4. Matroids and Tutte polynomials.

5. Moments and double-counting methods.

In this note, I focus on the third of these: the orthogonal-polynomial and association-scheme approach. However, this note does not yet enter the full theory of association schemes. Using character sums only as a minimal tool, we reread the MacWilliams identity as a Krawtchouk transform on weight distributions. This is an entrance to the orthogonal-polynomial and association-scheme viewpoint. The aim of this note is to use a proof of the MacWilliams identity as a guide to an introduction to Krawtchouk polynomials.

The MacWilliams identity is usually written as the polynomial identity

In this note, we look at this identity at the coefficient level. Write the weight distribution of a code $C$ as

Then the weight enumerator is

The MacWilliams identity is also a transform which computes the weight distribution vector

of the dual code from the weight distribution vector

of $C$. The coefficients appearing in this transform are the Krawtchouk polynomials.

The route in this note is as follows.

• Look at weight distributions.

• Define Krawtchouk polynomials by a generating function.

• Become familiar with the explicit formula and small examples.

• See their meaning as character sums.

• Check orthogonality and the Krawtchouk transform.

• Derive the coefficient-level MacWilliams identity.

• Return to the usual polynomial form.

Krawtchouk polynomials are a representative example of discrete orthogonal polynomials. In the classical world of orthogonal polynomials, Hermite polynomials, Laguerre polynomials, Jacobi polynomials, and so on are well known. These have orthogonality with respect to integrals over continuous intervals. On the other hand, Krawtchouk polynomials are orthogonal with respect to sums over the finite set $\{0,1,\dots,n\}$. This feature, being “orthogonal polynomials on a finite set”, fits very well with the Hamming weight.

The original paper on Krawtchouk polynomials is Krawtchouk [Kra29]. For their systematic place as orthogonal polynomials, Koekoek–Lesky–Swarttouw [KLS10, Chapter 9] is a standard reference. For Krawtchouk polynomials and the MacWilliams identity in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is the classical standard reference.

First, we reinterpret the weight enumerator as a coefficient vector. Let $E$ be a finite set and let $n=\card{E}$. For a word $c\in\mathbb{F}_{q}^{E}$, write its Hamming weight as

Using this notation, the weight enumerator can be written as

The weight enumerator packages the weight distribution as a single polynomial in two variables.

In order to write the MacWilliams identity at the coefficient level, write the weight distribution of the dual code as

The aim is to express $B_j$ in terms of the numbers $A_w(C)$. The form will be

Here $\Kraw_j(w)$ is a value of a Krawtchouk polynomial.

Thus, in the proof in this note, we view the MacWilliams identity as

a linear transform on the weight distribution vector.

The entries of the matrix describing this linear transform are the Krawtchouk polynomials.

We now define Krawtchouk polynomials. In this note, we use the normalisation adapted to the $q$-ary Hamming space which naturally appears in coding theory. There are several conventions in the literature for the placement of indices and for normalisation, but here we use the following definition.

Here the subscript $j$ means “which Krawtchouk polynomial”, while the $w$ inside the parentheses means the Hamming weight substituted into that polynomial. Thus $\Kraw_j(w)$ is the value of the $j$-th polynomial $\Kraw_j(x)$ at $x=w$. In coding theory, one mainly uses the values for $w=0,1,\dots,n$.

With this definition, we do not first read the right-hand side with $x$ as a general variable. Instead, we first define the values for the weights $w=0,1,\dots,n$. The next explicit formula shows that $\Kraw_j(x)$ is genuinely a polynomial in $x$ of degree at most $j$, and that substituting the integer $w$ satisfies $$\sum_{j=0}^{n}\Kraw_{j}(w)z^{j} = \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}. \tag{3.1}$$3.1. In coding theory, one mainly uses it by substituting weights $x=w$.

Expanding $$\sum_{j=0}^{n}\Kraw_{j}(w)z^{j} = \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}. \tag{3.1}$$3.1 gives the following explicit formula.

Here $\binom{x}{\ell}$ is read as the polynomial in $x$ defined by

Similarly, $\binom{n-x}{j-\ell}$ is also a polynomial in $x$. When an integer $x=w$ is substituted, it agrees with the usual value of the binomial coefficient. In this sense, $$\Kraw_j(x) = \sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{x}{\ell}\binom{n-x}{j-\ell} \tag{3.2}$$(3.2) gives $\Kraw_j(x)$ as a polynomial in $x$.

This formula already shows a coding-theoretic meaning. Fix one word of weight $w$. Among the $n$ coordinates, $w$ coordinates are non-zero and $n-w$ coordinates are zero. When considering another word of weight $j$, one encounters choices in which $\ell$ of its non-zero coordinates overlap with the non-zero coordinates of the fixed word, and the remaining $j-\ell$ lie on the zero-coordinate side. Krawtchouk polynomials arise when a signed sum is inserted into this counting. The point to notice is that this is not merely a sum of cardinalities. We shall explain it later as a character sum using a non-trivial additive character $\psi$: at the positions overlapping with the non-zero coordinates of the fixed word, instead of simply counting the non-zero value in $q-1$ ways, the oscillating sum

appears. Therefore the contribution of the overlapping coordinates is not $(q-1)^{\ell}$ but $(-1)^{\ell}$. Viewing this value as a function of $w$ gives $\Kraw_j(w)$, and the explicit formula expresses it as the polynomial $\Kraw_j(x)$. This signed counting leads to the later interpretation as a character sum.

To become familiar with the definition, let us compute a few low-degree polynomials. The constant term of the generating function

for weight $w$ is $1$, so

Next, looking at the coefficient of $z$, for weight $w$ we get

Written as a polynomial in $x$, this is

Thus $\Kraw_1(x)$ is a linear polynomial in $x$.

In particular, in the binary case, that is, when $q=2$, we have

This is a quantity which appears very often in the binary Hamming space. A word of weight $w$ has $n-w$ zero coordinates and $w$ non-zero coordinates. In the binary case, a non-zero coordinate contributes $-1$ with sign, while a zero coordinate contributes $+1$, so the difference

appears.

We shall use this table later in the example of the binary repetition code. Here, notice that after fixing $j$, we get a function of $x$. For instance, $\Kraw_2(x)$ takes the values $3,-1,-1,3$ at $x=0,1,2,3$.

Krawtchouk polynomials are not merely polynomials defined by a generating function. In the Hamming space, they appear as the following natural sums.

Here, fix one non-trivial additive character of the finite field $\mathbb{F}_{q}$,

That is, $\psi(a+b)=\psi(a)\psi(b)$ holds, and $\psi$ is not identically $1$. Finite fields have such additive characters. Indeed, if $q=p^m$ and $L\colon \mathbb{F}_{q}\to\mathbb{F}_{p}$ is a non-zero $\mathbb{F}_{p}$-linear map, then

is a non-trivial additive character. Here $L(a)\in\mathbb{F}_{p}$ is read through the representative $0,1,\dots,p-1$. Character theory is not the main subject of this note, but in order to see how Krawtchouk polynomials arise from the Hamming space, we use just this one tool. We do not assume the general theory of characters, and prove only the properties needed below. Concretely, we use only the one-coordinate character sum proved here and the formula used later to extract the indicator function of the dual code. Thus the proof in this section is arranged so that it can be followed without systematic knowledge of character theory.

The needed property of character sums is the following single fact.

This theorem expresses well the coding-theoretic meaning of Krawtchouk polynomials. $\Kraw_j(w)$ is the sum of the character values $\psi(u\cdot c)$ over the words $u$ of weight $j$, after fixing a word $c$ of weight $w$. In other words, Krawtchouk polynomials are

oscillating sums obtained by viewing the weight-$j$ layer of the Hamming space from a word of weight $w$.

Here we have explained this using character sums, but if one only looks at $$\Kraw_j(x) = \sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{x}{\ell}\binom{n-x}{j-\ell} \tag{3.2}$$(3.2), it is also a sum of binomial coefficients counting the ways in which coordinates overlap. Krawtchouk polynomials as orthogonal polynomials bridge these two viewpoints.

We now see why Krawtchouk polynomials are called “orthogonal polynomials”. Orthogonality means, roughly, that the inner product of polynomials of different degrees is $0$. For Krawtchouk polynomials, the inner product is defined by a sum over the finite set

For $0\leq w\leq n$, put

This is the number of words of weight $w$ in $\mathbb{F}_{q}^{E}$. Indeed, there are $\binom{n}{w}$ ways to choose the $w$ coordinates which are non-zero, and each non-zero coordinate has $q-1$ possible values.

This inner product has as weights the sizes of the weight layers of the Hamming space. Krawtchouk polynomials are orthogonal with respect to this inner product. Since the values of Krawtchouk polynomials are real, the orthogonality formula is the same whether or not one writes complex conjugation.

This theorem shows that $\Kraw_0,\Kraw_1,\dots,\Kraw_n$ form an orthogonal basis for the function space on the finite set $\{0,1,\dots,n\}$. This is the important point. Krawtchouk polynomials are not merely convenient coefficients; they are the orthogonal basis naturally attached to the weight layers of the Hamming space.

Using Krawtchouk polynomials, one can define a transform on vectors of length $n+1$. This is the Krawtchouk transform.

In matrix form, the Krawtchouk transform is the operation of multiplying by the $(n+1)\times(n+1)$ matrix

This matrix is sometimes called the Krawtchouk matrix.

The orthogonality shown just above concerns the inner product with weights

and the sum has the form

On the other hand, the self-inverse property shown here concerns multiplying the Krawtchouk matrix itself twice, and the sum has the form

The two are closely related, but the summation index and the placement of the weights differ, so we keep them separate here. Orthogonality is a formula for the weighted inner product of the functions $\Kraw_r,\Kraw_s$, while self-inverseness is a formula for the product of the Krawtchouk matrix $K=(\Kraw_j(w))$.

The Krawtchouk transform is its own inverse, up to normalisation.

This self-inverse property corresponds to the symmetry of the MacWilliams identity. Indeed, taking the dual of $C$ once more gives $(C^{\perp})^{\perp}=C$. Also, for a linear code over a finite field,

This follows from $\dim C+\dim C^{\perp}=n$. Thus the fact that the transform on weight distributions becomes multiplication by $q^n$ after applying it twice is compatible with returning to the original code after taking the dual twice.

We now prove the MacWilliams identity using Krawtchouk polynomials. First we prove the coefficient-level formula.

In this section too, fix one non-trivial additive character $\psi$ of the finite field $\mathbb{F}_{q}$. We do not develop character theory itself in detail, but use only the following orthogonal-complement extraction formula.

This lemma lets us convert sums over $C^{\perp}$ into sums over $C$. We then substitute the Krawtchouk-polynomial sum $$\sum_{\substack{u\in\mathbb{F}_{q}^{E}\\ \wt(u)=j}} \psi(u\cdot c) = \Kraw_j(w) \tag{5.1}$$(5.1).

This theorem is the coefficient version of the MacWilliams identity through Krawtchouk polynomials. In other words, the weight distribution of the dual code is the Krawtchouk transform of the weight distribution of the original code, divided by $\card{C}$:

From the coefficient-level formula, we derive the usual polynomial form of the MacWilliams identity.

In this proof, the variable substitution in the MacWilliams identity,

appeared from the generating function of the Krawtchouk polynomials. Thus the MacWilliams identity can be viewed as

the Krawtchouk transform repackaged by the generating function called the weight enumerator.

Let us check the coefficient-level formula in a small example. Consider the repetition code over $\mathbb{F}_{2}^{3}$,

Its weight distribution is

The dual code is

namely the set of all words of even weight. Therefore

and its weight distribution is

We check that this comes from the Krawtchouk transform.

By Example 4.1 (The binary case with n=3)Let $q=2$ and $n=3$. The generating function is $$\sum_{j=0}^{3}\Kraw_j(w)z^j = (1+z)^{3-w}(1-z)^w.$$ The values for $x=0,1,2,3$ are as follows: $$\begin{array}{c|rrrr} & x=0 & x=1 & x=2 & x=3 \\ \hline \Kraw_0(x) & 1 & 1 & 1 & 1 \\ \Kraw_1(x) & 3 & 1 & -1 & -3 \\ \Kraw_2(x) & 3 & -1 & -1 & 3 \\ \Kraw_3(x) & 1 & -1 & 1 & -1 \end{array}$$Example 4.1, the Krawtchouk table for $q=2$ and $n=3$ is