After the Second World War, there was a boom in the study of transmitting encoded data. In likelihood, I imagine the boom started earlier, and the boom was more about the declassified publication of papers on this topic than about a sudden increase in productivity.

This month’s mathematical hero, Jessie MacWilliams, played a relatively late part in this boom - the identity that bears her name was in her early-1960s thesis - and relates to linear codes. It needs a bit of setting up, though.

First up, we need to say what we mean by a code: in this context, it’s a collection of codewords. A codeword is a list of 1s and 0s (“bits”) of a given length, $n$

A linear code is one where any combination of two codewords gives a codeword - and “combination” here means taking the XOR of the two codewords ((Adam points out: in general, for alphabets of prime size $k$, the operation is “sum modulo $k$”, which reduces to XOR when $k=2$. It is possible, but ill-advised, to extend this to alphabets whose sizes are other powers of primes.)). That means, if the bits in position $i$ of the two original codewords are the same, the bit in position $i$ of the result will be 0; if the two bits were different, the $i$th bit of the result would be 1. For example, in a code with $n=4$, combining 0101 and 1100 would give a result of 1001.

Such a code also has a dual code – all of the possible words that are orthogonal to every codeword in the original code. Two words are orthogonal if, when you multiply their bits together, one at a time, and add up the results modulo 2, you get zero. For example, 0101 and 1111 are orthogonal: you get $0\times1 = 0$ for the first bit, $1\times 1 = 1$ for the second, then 0 and 1 again for the third and fourth bits. Adding up $0+1+0+1$ modulo 2 gives you 0.

For more example, the four-bit code above, with codewords 0000, 0101, 1001 and 1100 has a dual code with the codewords 0000, 0010, 1101 and 1111 ((You may want to check this)). If the original code is called $C$, its dual code is called $C^\perp$.

We also need to define the weight of a codeword, which is simply “how many 1s it has in it” ((in general, how many of its digits are non-zero)) - the weight of 0101 is 2. The number of codewords with a particular weight of $w$ is denoted $A_w$.

And lastly, for now, we’re going to define the weight enumerator function:

\[W(C; x, y) = \\sum\_0^n A\_w x^w y^{n-w}\]

The code we called $C$ earlier has a weight enumerator of $y^4 + 3x^2y^2$; its dual code’s weight enumerator is $y^4 + xy^3 + x^3y + x^4$.

The weight enumerator can be used to find the probability of incorrectly decoding a codeword due to errors - in particular for a binary linear code, if the probability of a bit being flipped is $p$, the function $W(C; p, 1-p)$ gives the probability of the wrong codeword arriving.

What is the MacWilliams Identity?

The MacWilliams identity relates the weight enumerators of a code and its dual: it states $W(C^{\perp}; x,y) = \frac{1}{|C|}W(C; y-x, y+x)$

Let’s check it with our example: $|C|$ is the number of codewords in $|C|$, 4, so we get $\frac{1}{4} \left( (y-x)^4 + 3(y-x)^2(y+x)^2\right)$.

If we expand that out, we get $\frac{1}{4}\left(\left(y^4 - 4y^3x + 6y^2x^2 - 4yx^3 + x^4\right) + 3\left(y^4 - 2x^2y^2 + x^4\right)\right)$.

Keep going: $\frac{1}{4}\left( 4y^4 - 4y^3x - 4yx^3 + 4x^4\right)$ - it works! Magic!

Why is it important?

The MacWilliams identity isn’t restricted to binary linear codes (it works on codes over any field, which could be significantly more complicated).

It allows us, among other things, to determine the number of codewords in the dual code without necessarily knowing what any of them are (except for the one that’s all zeroes), and to work out the probability of incorrectly decoding a message sent in the dual code.

Who was Jessie MacWilliams?

Florence Jessie Collinson was born in Stoke-on-Trent, England, in 1917. She studied at Cambridge, receiving her BA and MA in the late 1930s. She worked with Oscar Zariski at Johns Hopkins and at Harvard, before marrying Walter MacWilliams in 1941. She raised a family before joining Bell Labs in 1958; then in 1960, she took leave for postgraduate studies, and completed her PhD in one year under Andrew Gleason. She spend the next decades working on algebraic constructions and combinatorial properties of codes, publishing The Theory of Error-Correcting Codes with Neil Sloane ((Yes, the OEIS one)) in 1977.

In 1980, MacWilliams gave the first Emmy Noether Lecture for the Association for Women in Mathematics. She retired from Bell Labs in 1983, and died in 1990 in New Jersey.

* Updated 2020-01-06 to clarify the more general case, and 2020-01-07 to fix an error. Thanks to Adam Atkinson both for gently putting me right and for guiding me towards the identity in the first place.