A motivated proof of the MacWilliams Identity

March 11, 2018

Fix n \in \mathbb{N} and let V = \mathbb{F}_2^n. Let \mathrm{wt}(u) denote the weight of u \in V, defined by \mathrm{wt}(u) = |\{i : u_i = 1\}|. Given a subset S of V, we define its weight enumerator W_S(x,y) by

W_S(x,y) = \sum_{u \in S} x^{\mathrm{wt}(u)} y^{n-\mathrm{wt}(u)}.

The MacWilliams Identity states that if C is a linear subspace of V, and C^\perp is its orthogonal complement with respect to the dot product u \cdot v = \sum_{i=1}^n u_i v_i then

\displaystyle W_{C^\perp}(x,y) = \frac{1}{|C|} W_C(-x+y,x+y).

The MacWilliams Identity is important in coding theory. It was first proved by the coding theorist Jessie MacWilliams, yet another alumnus of Bell Labs. To my mind, the best motivation for its proof comes from certain related identities in binomial coefficients and the generating function techniques used to prove them, which, in turn, are best understood in terms of the characters of cyclic groups.

Binomial coefficients

The Binomial Theorem states that (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}. It has a one-line combinatorial proof: expand (x+y)(x+y) \cdots (x+y), by choosing x from k of the n brackets and y from the other n-k brackets; there are \binom{n}{k} ways to do this, so \binom{n}{k} is the coefficient of x^k y^{n-k}.

Now consider the sum s = \binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots of binomial coefficients with even `denominator’. This can be evaluated using the binomial theorem, using the two sums below to cancel out the unwanted binomial coefficients with odd denominator:

\displaystyle s = \frac{1}{2} \sum_{k=0}^n \binom{n}{k} + \frac{1}{2} \sum_{k=0}^n (-1)^k \binom{n}{k}.

For n \in \mathbb{N} the sums are (1+1)^n = 2^n and (-1+1)^n = 0, respectively. Therefore s = 2^{n-1}. More generally, this trick shows that

\displaystyle \sum_{j \in \mathbb{N}_0} \binom{n}{2j} x^{2j} y^{n-2j} = \frac{1}{2} (x+y)^n + \frac{1}{2}(-x+y)^n

which already has some of the appearance of the MacWilliams Identity.
How about s' = \binom{n}{0} + \binom{n}{4} + \binom{n}{8} + \cdots ? Since powers of -1 worked for the two-step identity, it is reasonable to try powers of \mathrm{i}. This gives

\begin{aligned} s' = \frac{1}{4} \sum_{k=0}^n \binom{n}{k} &+ \frac{1}{4} \sum_{k=0}^n \binom{n}{k} \mathrm{i}^k \\&\, + \frac{1}{4} \sum_{k=0}^n \binom{n}{k} (-1)^k + \frac{1}{4} \sum_{k=0}^n \binom{n}{k} (\mathrm{-i})^k.\end{aligned}

By the Binomial Theorem, the sums are 2^n, (1+i)^n, 0 and (1-i)^n. For example, if n = 4m where m \in \mathbb{N} then (1+i)^{4m} = (1-i)^{4m} = 2^{2m} (-1)^m, so we have s' = 2^{4m-2} + 2^{2m-1} (-1)^m. Similar formulae can be obtained for the other cases for n modulo 4.

Character theory

Consider the cyclic group \mathbb{Z} / 4\mathbb{Z}. It has four irreducible complex characters, taking values (1,1,1,1), (1,\mathrm{i},-1,\mathrm{-i}), (1,-1,1,-1) and (1, \mathrm{-i},-1,\mathrm{i}). The previous displayed equation comes from expressing the indicator function (1,0,0,0) as a linear combination of irreducible characters

\begin{aligned} (1,0,0,0) = &\frac{1}{4} (1,1,1,1) + \frac{1}{4} + (1,i,-1,-i) \\ &\qquad + \frac{1}{4} (1,-1,1,-1) + \frac{1}{4}(1,i,-1,i).\end{aligned}

As an exercise, the reader might use the characters of \mathbb{Z} / 3\mathbb{Z} to decompose the indicator function (1,0,0) of 0 \in \mathbb{Z}/3\mathbb{Z} and so prove the related identity \binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \cdots = \frac{2^{n}}{3} + \frac{2}{3} \cos \frac{n\pi}{3} for n \in \mathbb{N}.

MacWilliams’ Identity for the repetition code

Let C = \langle 1\ldots 1 \rangle. In this case the left-hand side of the MacWilliams’ Identity is sum of all x^{\mathrm{wt}(u)} y^{n - \mathrm{wt}(u)} over u \in V of even weight. By analogy with the binomial sum, we write

W_{C^\perp}(x,y) = \frac{1}{2} \sum_{v \in V} x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} + \frac{1}{2} \sum_{v \in V} (-x)^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}.

The first summand is the generating function enumerating all v \in V by their weight. Since there are \binom{n}{k} elements of V of weight k, it is \sum_{k =0}^n \binom{n}{k} x^k y^{n-k}, which is (x+y)^n by the Binomial Theorem. Replacing x with -x we see that the second summand is (-x+y)^n. Therefore

W_{C^\perp}(x,y) = \frac{1}{2} (x+y)^n + \frac{1}{2} (-x+y)^n.

Since W_C(x,y) = x^n + y^n, this agrees with the MacWilliams’ Identity. Note that the second sum could be written as

\displaystyle \sum_{v \in V} (-1)^{1\ldots 1 \cdot v} x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}.

MacWilliams Identity for a larger code

Take n=4 and C = \langle 1100, 0011 \rangle. Then

W_C(x,y) = x^4 + 2x^2y^2 + y^4.

We can describe C^\perp as the intersection of the two codimension 1 hyperplanes U, U', with ‘normals’ 1100 and 0011. Thus

\displaystyle W_{C^\perp}(x,y) = \sum_{v} [v \in U \cap U'] x^{\mathrm{wt}(v)}y^{n-\mathrm{wt}(v)}.

For each b \in V, we define \chi_b(v) = (-1)^{b \cdot v}; these are the irreducible complex characters of V. Using them to decompose the indicator function [v \in U \cap U'] : V \rightarrow \mathbb{C} we get

[v \in U \cap U'] = \frac{1}{4} \chi_{0}(v) + \frac{1}{4} \chi_{1100}(v) + \frac{1}{4} \chi_{0011}(v) + \frac{1}{4} \chi_{1111}(v).

It now suffices to find \sum_{v \in V} \chi_{b}(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}. If \mathrm{wt}(b) = t then, by symmetry, we may assume that b = 1\ldots 10\ldots 0, where there are exactly t ones. Now (-1)^{b \cdot v} records the parity of the number of ones in the first t positions of v, so writing v \in V as the concatenated vector (u | w) where u \in \mathbb{F}_2^t and w \in \mathbb{F}_2^{n-t}, we have

\begin{aligned} \sum_{v \in V} &\chi_{b}(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}\\ &= \sum_{u \in U} (-1)^{\mathrm{wt}(u)} x^{\mathrm{wt}(u)} y^{t-\mathrm{wt}(v)} \sum_{w \in W} x^{\mathrm{wt}(w)} y^{n-t-\mathrm{wt}(w)} \\ &= (-x+y)^t (x+y)^{n-t} \end{aligned}.

Therefore

\begin{aligned} W_{C^\perp}(x,y) &= \frac{1}{4} (x\!+\!y)^4 \!+\! \frac{2}{4} (-x\!+\!y)^2 (x\!+\!y)^2 \!+\! \frac{1}{4} (-x\!+\!y)^4 \\ &= W_C(-x+y,x+y) \end{aligned}

as required. (In this case, since C is self-dual, we even have W_{C^\perp}(x,y) = W_C(x,y).)

MacWilliams Identity in general

The general proof needs no more ideas than those seen in the previous example. The indicator function decomposition is

\displaystyle [v \in C^\perp] = \frac{1}{|C|} \sum_{b \in C} \chi_b(v)

and so

\begin{aligned}\sum_{v \in C^\perp} x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} &=\sum_{v \in V} \frac{1}{|C|} \sum_{b \in C} \chi_b(v) x^{\mathrm{wt}(v)}y^{n-\mathrm{wt}(v)} \\ &= \frac{1}{|C|} \sum_{b \in C} \sum_{v \in V} \chi_b(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} \\ &= \frac{1}{|C|} \sum_{t=0}^n \sum_{b \in C : \mathrm{wt}(b) = t}(-x+y)^t (x+y)^{n-t} \\&= \frac{1}{|C|} W_C(-x+y,x+y) \end{aligned}

as required.

Leave a Comment » | Binomial coefficients, Coding theory, Combinatorics | Permalink
Posted by mwildon

Runups and cycles

March 3, 2018

Let xs be a stream of values that can be compared for equality. Let ++ denote concatenation of lists. Assuming that xs is of the form runUp ++ cyc ++ cyc ++ ..., what is a good way to find the decomposition (runUp, cyc)?

The problem is more subtle than it might seem. If xs is produced by iterating a function, so the entries are [x, f x, f f x, ...] then there are several cycle finding algorithms that can be used. In general, an algorithmic solution is impossible, because the stream may be of the form fakecycle ++ rest, where fakecycle has arbitrary length n+1 and agrees with rest for n positions. In practice, we might know that any cycle has some bounded length, or be prepared to accept a small chance of misidentification.

In this case, the following Haskell code finds the first decomposition (runUp, guessedCycle) such that the stream is runUp ++ rest and rest, which has length at least t, is of the form guessedCycle ++ guessedCycle ++ rest'.

runupAndCycle t xs = 
         runupAndCycleAux t xs (zip [1..] (tail xs))

runupAndCycleAux t xs [] = error $ show (t, xs)
runupAndCycleAux t xs qxs@((q, x) : _)
    = case lookup (map snd $ take t qxs) (take q tailsPositions) of
        Nothing -> runupAndCycleAux t xs (tail qxs)
        Just p  -> -- the t entries starting in positions q and p agree;
                   -- test if taking guessedCycle to be all entries
                   -- between positions q and p-1 gives a decomposition 
                   -- of the required form
                   let xsFirst  = take (q-p) $ drop p xs
                       xsSecond = take (q-p) $ map snd qxs
                   in  if and (zipWith (==) xsFirst xsSecond) 
                          then (take p xs, xsSecond) 
                          else runupAndCycleAux t xs (tail qxs)
    where tailsPositions 
              = [(take t ys, p) | (ys, p) <- zip (tails xs) [0..]]

For example

  • runupAndCycle 4 [1,2,3,1,2,3,4,5,1,2,3,4,5] evaluates to ([1,2,3],[1,2,3,4,5]);
  • runupAndCycle 4 [1,2,3,1,2,3,4,6,1,2,3,4,5] raises an exception, because while there is agreement for four positions, this is shown by the if ... then ... else ... test not to correspond to a cycle (and the bistream is then exhausted without finding anything better);
  • runUpAndCycle 4 [1,2,3,1,2,3,4,5,1,2,3,4,6] raises an exception for the same reason;
  • runUpAndCycle 4 [1,2,3,1,2,3,4,5,1,2,3,4,5,6] evaluates to ([1,2,3],[1,2,3,4,5]), as the first example, wrongly suggesting a 5-cycle. Replacing the first argument 4 with 6 we get an exception instead.

The algorithm may use O(tn^2) work to exhaust n bits without finding a suitable decomposition. For example with t = 3, the stream [0,0,0,1,0,0,0,2,0,0,0,3,0,0,0,4, ...] finds possible cycle starts in every fourth position; by position 4m, these require work 4m to investigate.

I’d like to know if there is a faster or more elegant algorithm—ideally both of course—but some searching only found hits for the deterministic version of the problem.

Leave a Comment » | Algorithms, Haskell | Permalink
Posted by mwildon