Weight Enumerators, the MacWilliams Identity, and the Linear-Programming Bound

Intuition Beginner

Every codeword in a linear code has a "weight" — the number of positions where its symbol is not zero. A codeword like $(1,0,1,1,0,0,0)$ has weight 3 because three positions are nonzero. The all-zero codeword has weight 0. Weight measures how far a codeword is from the origin.

For a code with many codewords, listing every individual weight is tedious. Instead, count how many codewords have weight 0, weight 1, weight 2, and so on up to the code length. This count is the weight distribution — a histogram with one entry per possible weight. A code with good error-correcting ability has most nonzero codewords at high weight.

Pack this histogram into a polynomial called the weight enumerator. If three codewords have weight 5, the polynomial contains the term $3z^5$. The coefficient of $z^i$ tells you how many codewords have weight $i$. This single polynomial encodes the entire weight structure of the code.

Here is the surprise: the weight enumerator of a linear code completely determines the weight enumerator of its dual code. This is the MacWilliams identity, discovered by Jessie MacWilliams in 1963. Given one polynomial, you compute the other by a substitution — no need to look at the dual code at all.

The MacWilliams identity produces linear constraints on the weight distribution. Combined with the requirement that weight counts be non-negative, these constraints form a linear program. Solving it gives the tightest known upper bounds on how large a code can be for a given length and minimum distance. This is the linear-programming bound.

Visual Beginner

Figure: two histograms side by side. The left histogram shows the weight distribution of the binary [7,4,3] Hamming code — bars at weights 0, 3, 4, and 7 with heights 1, 7, 7, and 1. The right histogram shows its dual [7,3,4] simplex code — bars at weights 0 and 4 with heights 1 and 7. An arrow between them is labelled "MacWilliams identity" to indicate that the right histogram is computed from the left by the substitution formula.

Code	$z^0$	$z^1$	$z^2$	$z^3$	$z^4$	$z^5$	$z^6$	$z^7$	Total
[7,4,3] Hamming	1	0	0	7	7	0	0	1	16
[7,3,4] Dual	1	0	0	0	7	0	0	0	8

The Hamming code has 16 codewords; its dual has 8. The MacWilliams identity connects these two rows by a single algebraic formula. Notice that the dual has no codewords of weight 1, 2, 3, 5, 6, or 7 — a structural fact that follows from the identity, not from inspecting the dual directly.

Worked example Beginner

The binary [7,4,3] Hamming code has length 7, dimension 4, and minimum distance 3. It contains $2^4=16$ codewords. Its weight distribution is well known: one codeword of weight 0, seven of weight 3, seven of weight 4, and one of weight 7. No codewords have weight 1, 2, 5, or 6.

Step 1. Write the weight enumerator. Each coefficient records the count at that weight:

$$A(z)=1+7z^3+7z^4+z^7.$$

The constant term is 1 (one zero vector). The coefficient of $z^3$ is 7. Setting $z=1$ gives $A(1)=1+7+7+1=16$, the total number of codewords — a useful sanity check.

Step 2. The dual code is a [7,3,4] code with 8 codewords. Its weight distribution has one codeword of weight 0 and seven of weight 4:

$$B(z)=1+7z^4.$$

Step 3. Verify the MacWilliams identity at two test points. For binary codes ($q=2$, $n=7$, $k=4$), the identity reads:

$$B(z)=\frac{1}{2^4}(1+z{)}^{7}A\left(\frac{1-z}{1+z}\right).$$

At $z=0$: the left side is $B(0)=1$. The right side is $(1/16)(1{)}^{7}A(1)=(1/16)(16)=1$. Both sides match.

At $z=1$: the left side is $B(1)=1+7=8$. The right side is $(1/16)(2{)}^{7}A(0)=(1/16)(128)(1)=8$. Both sides match.

Step 4. Check at one more point for confidence. At $z=1/2$, the left side gives $B(1/2)=1+7/16=23/16\approx 1.44$. The right side requires computing $A((1-1/2)/(1+1/2))=A(1/3)$. Working in 2187ths: $A(1/3)=2187/2187+567/2187+189/2187+1/2187=2944/2187$. Then $(1/16)(3/2{)}^7\cdot 2944/2187=(1/16)(2187/128)(2944/2187)=2944/2048=23/16$. Both sides match again.

The identity holds at all test points, and a full symbolic expansion confirms it for every $z$. From the primal weight enumerator alone, we recovered the dual's entire weight distribution — this is the power of the MacWilliams identity.

Check your understanding Beginner

Formal definition Intermediate+

Let $C$ be a linear $[n,k,d]$ code over the finite field ${\mathbb{F}}_q$.

Definition (Hamming weight). The Hamming weight of a vector $\mathbf{v}=(v_1,\dots ,v_n)\in {\mathbb{F}}_q^n$ is the number of nonzero coordinates:

$$\mathrm{wt}(\mathbf{v})=|\{i\in \{1,\dots ,n\}:v_i\ne 0\}|.$$

Definition (Weight distribution). The weight distribution of $C$ is the sequence $(A_0,A_1,\dots ,A_n)$ where

$$A_i=|\{\mathbf{c}\in C:\mathrm{wt}(\mathbf{c})=i\}|.$$

By convention, $A_0=1$ since the zero vector is always a codeword. For an $[n,k,d]$ code, $A_i=0$ for $1\le i<d$ because the minimum weight of any nonzero codeword equals the minimum distance $d$ (see 40.06.06).

Definition (Weight enumerator). The weight enumerator of $C$ is the polynomial

$$A(z)=\sum _{i=0}^n{A}_i{z}^i=\sum _{\mathbf{c}\in C}{z}^{\mathrm{wt}(\mathbf{c})}.$$

This is a polynomial of degree at most $n$ with non-negative integer coefficients, satisfying $A(0)=1$ and $A(1)=|C|=q^k$.

Definition (Dual weight enumerator). If $C^{\perp }$ is the dual code of $C$, its weight enumerator is

$$A^{\perp }(z)=\sum _{j=0}^n{B}_j{z}^j$$

where $B_j=|\{\mathbf{c}\in C^{\perp }:\mathrm{wt}(\mathbf{c})=j\}|$.

Counterexamples to common slips

• The weight enumerator does not determine the code. Two non-equivalent codes can share the same weight distribution. The enumerator records the histogram of weights but not the geometric arrangement of codewords in ${\mathbb{F}}_q^n$. Knowing $A(z)$ tells you how many codewords sit at each distance from the origin, but not which subspaces they span.

• The MacWilliams identity requires linearity. For a nonlinear code, there is no dual code in the usual sense, and the identity does not apply directly. Delsarte's association-scheme theory extends MacWilliams-type inequalities to certain nonlinear codes, but the formulation uses the distance distribution rather than the weight distribution.

• $A^{\perp }(z)$ is the dual code's enumerator, not the reciprocal. The notation $A^{\perp }(z)$ refers to the weight enumerator of the entirely separate code $C^{\perp }$. It does not mean $1/A(z)$ or $A(1/z)$.

Key theorem with proof Intermediate+

Theorem (MacWilliams identity). Let $C$ be an $[n,k]$ linear code over ${\mathbb{F}}_q$ with weight enumerator $A(z)$. The weight enumerator of the dual code $C^{\perp }$ is

$$A^{\perp }(z)=\frac{1}{q^k}(1+(q-1)z{)}^{n}A\left(\frac{1-z}{1+(q-1)z}\right).$$

Proof. The proof uses additive characters on ${\mathbb{F}}_q^n$ and the Poisson summation formula.

Characters. Let $p$ be the characteristic of ${\mathbb{F}}_q$. Define the additive character $\chi :{\mathbb{F}}_q\to {\mathbb{C}}^{\ast }$ by $\chi (a)=e^{2\pi i\mathrm{Tr}(a)/p}$ where $\mathrm{Tr}$ is the trace from ${\mathbb{F}}_q$ to ${\mathbb{F}}_p$. For vectors $\mathbf{y}\in {\mathbb{F}}_q^n$, define ${\chi }_{\mathbf{y}}(\mathbf{x})={\prod }_{i=1}^n\chi (y_i{x}_i)$. The key properties are: ${\chi }_0(\mathbf{x})=1$ for all $\mathbf{x}$, and for $\mathbf{y}\ne 0$, ${\sum }_{\mathbf{x}\in {\mathbb{F}}_q^n}{\chi }_{\mathbf{y}}(\mathbf{x})=0$.

Hadamard transform. For any function $f:{\mathbb{F}}_q^n\to \mathbb{C}$, the Hadamard transform is $\hat{f}(\mathbf{y})={\sum }_{\mathbf{x}\in {\mathbb{F}}_q^n}f(\mathbf{x}){\chi }_{\mathbf{y}}(\mathbf{x})$.

Poisson summation. For any subspace $C\le {\mathbb{F}}_q^n$:

$$\sum _{\mathbf{x}\in C}f(\mathbf{x})=\frac{1}{|C^{\perp }|}\sum _{\mathbf{y}\in C^{\perp }}\hat{f}(\mathbf{y}).$$

This follows from the character orthogonality: the left side equals ${\sum }_{\mathbf{x}\in {\mathbb{F}}_q^n}f(\mathbf{x})\cdot |C^{\perp }{|}^{-1}{\sum }_{\mathbf{y}\in C^{\perp }}{\chi }_{\mathbf{y}}(\mathbf{x})$ because the inner sum is $|C^{\perp }|$ if $\mathbf{x}\in C$ and $0$ otherwise.

Transform of the weight function. Take $f(\mathbf{x})=z^{\mathrm{wt}(\mathbf{x})}$. For $\mathbf{y}$ with $\mathrm{wt}(\mathbf{y})=j$, separate coordinates by whether $y_i=0$ or $y_i\ne 0$:

• If $y_i=0$: the sum over $x_i\in {\mathbb{F}}_q$ gives $1+(q-1)z$.
• If $y_i\ne 0$: the sum gives $1+z{\sum }_{a\ne 0}\chi (y_{i}a)=1+z(-1)=1-z$, using ${\sum }_{a\in {\mathbb{F}}_q}\chi (y_{i}a)=0$ for $y_i\ne 0$.

Therefore:

$$\hat{f}(\mathbf{y})=(1+(q-1)z{)}^{n-j}(1-z{)}^j\text{when }\mathrm{wt}(\mathbf{y})=j.$$

Combine. Apply Poisson summation with the roles of $C$ and $C^{\perp }$ swapped (using $C=(C^{\perp }{)}^{\perp }$):

$$A^{\perp }(z)=\sum _{\mathbf{y}\in C^{\perp }}{z}^{\mathrm{wt}(\mathbf{y})}=\frac{1}{q^k}\sum _{\mathbf{x}\in C}(1+(q-1)z{)}^{n-\mathrm{wt}(\mathbf{x})}(1-z{)}^{\mathrm{wt}(\mathbf{x})}.$$

Factor out $(1+(q-1)z{)}^n$ and group by weight:

$$A^{\perp }(z)=\frac{1}{q^k}(1+(q-1)z{)}^n\sum _{j=0}^n{A}_j{\left(\frac{1-z}{1+(q-1)z}\right)}^j=\frac{1}{q^k}(1+(q-1)z{)}^{n}A\left(\frac{1-z}{1+(q-1)z}\right).\square$$

Bridge. The MacWilliams identity is the central insight of algebraic coding theory: the weight structures of a code and its dual are not independent but are two views of the same algebraic object, linked by a substitution in the weight enumerator polynomial. This identity builds toward the linear-programming bound developed later in this unit, where the MacWilliams constraints on the dual weight enumerator generate the inequalities that bound $A(n,d)$. It appears again in the theory of association schemes 40.06.06, where Delsarte's inequalities generalise MacWilliams to nonlinear codes. The identity generalises to higher-order weight enumerators for codes over rings and to the split weight enumerator for arbitrary partitions. The foundational reason it works is the Poisson summation formula — the same harmonic-analysis tool that underlies the Fourier inversion theorem. Putting these together, the MacWilliams identity is not a computational convenience but a duality principle with the same structural depth as the Fourier transform. The bridge is that algebraic coding theory gains its power from converting combinatorial questions about code size into algebraic questions about polynomials.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib has VectorSpace, FiniteField, and Subspace for finite-dimensional vector spaces over finite fields, and the Hamming distance on Fin-valued vectors exists in contrib. However, there is no definition of linear code as a Subspace equipped with a minimum-distance field, no weight enumerator polynomial, no dual-code weight enumerator, and no MacWilliams identity. The Krawtchouk polynomials, the Poisson summation formula for finite abelian groups, and the LP bound are entirely absent. A Codex.CodingTheory.WeightEnumerator module defining the weight distribution as a function on a Subspace representation of a code, the weight enumerator as a polynomial over the integers, and the MacWilliams identity as a polynomial identity derived from character theory would be the load-bearing first step. This unit ships without a Lean module.

Advanced results Master

Krawtchouk polynomials

The MacWilliams identity has a natural expansion in terms of the Krawtchouk polynomials, which are the orthogonal polynomials for the binomial distribution on $\{0,1,\dots ,n\}$. For a code over ${\mathbb{F}}_q$, the Krawtchouk polynomial of degree $k$ is

$$P_k(x;n,q)=\sum _{j=0}^k(-1{)}^j(q-1{)}^{k-j}\left(\genfrac{}{}{0ex}{}{x}{j}\right)\left(\genfrac{}{}{0ex}{}{n-x}{k-j}\right).$$

The generating function identity is the key link to MacWilliams:

$$(1+(q-1)z{)}^{n-x}(1-z{)}^x=\sum _{k=0}^n{P}_k(x;n,q)z^k.$$

This identity means that when we expand the Hadamard transform of $z^{\mathrm{wt}(\mathbf{x})}$, the coefficients are exactly the Krawtchouk polynomials evaluated at the weight. The MacWilliams identity in Krawtchouk form becomes

$$B_j=\frac{1}{q^k}\sum _{i=0}^n{A}_i{P}_j(i;n,q),$$

which is a linear system relating the weight distribution of $C$ to that of $C^{\perp }$. By the orthogonality of Krawtchouk polynomials with respect to the weight $\left(\genfrac{}{}{0ex}{}{n}{i}\right)(q-1{)}^i$ on $\{0,\dots ,n\}$, the inverse relation is

$$A_i=\frac{q^k}{q^n}\sum _{j=0}^n{B}_j{P}_i(j;n,q).$$

The Krawtchouk polynomials satisfy a three-term recurrence

$$(k+1)P_{k+1}(x)=(n(q-1)+k-qx)P_k(x)-(q-1)(n-k+1)P_{k-1}(x),$$

starting from $P_0(x)=1$ and $P_1(x)=n(q-1)-qx$. This recurrence provides an efficient way to compute the linear constraints for the LP bound without expanding the full substitution.

The linear-programming bound

The MacWilliams identity generates linear inequalities that bound $A(n,d)$, the maximum number of codewords in any code of length $n$ and minimum distance $d$ over ${\mathbb{F}}_q$. The formulation proceeds as follows.

Consider a linear $[n,k,d]$ code $C$. Its weight distribution satisfies:

1. $A_0=1$.
2. $A_i=0$ for $1\le i<d$.
3. $A_i\ge 0$ for all $i$.
4. $B_j\ge 0$ for all $j$ (since each $B_j$ counts codewords in $C^{\perp }$).

By the Krawtchouk form of MacWilliams, constraint 4 becomes

$$\sum _{i=0}^n{A}_i{P}_j(i;n,q)\ge 0\text{for all }j=0,1,\dots ,n.$$

The LP bound. Maximise $M={\sum }_{i=0}^n{A}_i$ subject to:

$$A_0=1,A_i=0(1\le i<d),A_i\ge 0,\sum _{i=0}^n{A}_i{P}_j(i;n,q)\ge 0(0\le j\le n).$$

The maximum $M^{\ast }$ satisfies $A(n,d)\le M^{\ast }$.

For the general (nonlinear) case, Delsarte showed that the distance distribution of any code satisfies the same MacWilliams-type inequalities through the association-scheme framework. The Delsarte inequalities state that the "inner distribution vector" of any code is positive semidefinite with respect to the Krawtchouk transform, and the LP bound applies to all codes, not just linear ones.

The LP bound dominates the Hamming (sphere-packing) bound and the Singleton bound for most parameter ranges. For example, for binary codes of length $n=10$ and $d=5$: the Hamming (sphere-packing) bound gives $A(10,5)\le 40$ by counting disjoint balls of radius $\lfloor (d-1)/2\rfloor =2$; the Plotkin bound gives $A(10,5)\le 20$; the LP bound gives $A(10,5)\le 12$. The true value is $A(10,5)=12$ (achieved by the nonlinear Nordstrom-Robinson code), so the LP bound is tight here.

The LP bound is computed by solving a linear program with $n-d+1$ non-negative unknowns $A_d,A_{d+1},\dots ,A_n$ and roughly $n+1$ inequality constraints. Modern LP solvers handle this in milliseconds even for $n$ in the hundreds. The bound is also useful in the negative: when a code is constructed whose size matches the LP bound, the code is provably optimal and no further search can improve it.

The McEliece-Rodemich-Rumsey-Welch bound

The LP bound gives numerical upper bounds for fixed $(n,d)$. For the asymptotic regime, McEliece, Rodemich, Rumsey, and Welch (1977) solved the LP dual problem analytically to obtain the tightest known asymptotic upper bound on the rate $R=({\log }_{q}A(n,d))/n$ of a binary code with relative distance $\delta =d/n$.

Theorem (MRRW bound). For binary codes with relative distance $\delta \in (0,1/2)$:

$$R(\delta )\le H_2\left(\frac{1}{2}-\sqrt{\delta (1-\delta )}\right),$$

where $H_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$ is the binary entropy function.

The proof constructs an optimal dual feasible solution for the LP by choosing coefficients from a carefully designed polynomial expressed in the Krawtchouk basis. The polynomial satisfies the positivity constraints by construction, and the objective value evaluates to the stated bound via the Christoffel-Darboux formula for orthogonal polynomials. The key technical insight is that the LP dual variables correspond to a polynomial $\alpha (x)$ of bounded degree that is non-negative on $\{0,1,\dots ,n\}$ and whose Krawtchouk expansion coefficients are also non-negative. The MRRW construction picks $\alpha (x)=(P_t(x)+1{)}^2$ for a suitable Krawtchouk polynomial $P_t$, exploiting the squaring trick to enforce both positivity conditions simultaneously.

The MRRW bound sits between the Gilbert-Varshamov lower bound $R\ge 1-H_2(\delta )$ and the McEliece et al. first bound. For $\delta =0.1$, MRRW gives $R\le 0.53$ while the GV bound gives $R\ge 0.53$, so at this point the bounds nearly meet. For larger $\delta$, a gap remains between the GV lower bound and the MRRW upper bound, and closing this gap is one of the central open problems in coding theory.

Synthesis. The weight enumerator compresses the combinatorial weight distribution into a polynomial, and the MacWilliams identity reveals that this polynomial for the dual code is obtained by a substitution — the central insight that one code's structure determines its dual's. The Krawtchouk polynomials are the spectral decomposition of this duality: they diagonalise the MacWilliams transform, the bridge is that the linear constraints $B_j\ge 0$ become inequalities on the primal weight distribution when expanded in the Krawtchouk basis, and the LP bound extracts numerical upper bounds on $A(n,d)$ from these inequalities. This is exactly the operational content of the MacWilliams identity: algebraic structure constrains code size. The identity generalises to the split weight enumerator and to codes over rings, and appears again in the invariant-theory classification of self-dual codes via Gleason's theorem. The foundational reason the LP bound is so powerful is that Delsarte's association-scheme framework extends MacWilliams-type inequalities to all codes, not just linear ones, putting these together into a unified bound that dominates classical combinatorial bounds. The arc from weight distribution to polynomial identity to linear program demonstrates that the deepest bounds in coding theory come not from counting arguments alone but from the algebraic structure of the Hamming scheme.

Full proof set Master

Proposition (Krawtchouk expansion of MacWilliams). Let $C$ be an $[n,k]$ linear code over ${\mathbb{F}}_q$ with weight distribution $(A_0,\dots ,A_n)$ and dual weight distribution $(B_0,\dots ,B_n)$. Then for each $j=0,1,\dots ,n$:

$$B_j=\frac{1}{q^k}\sum _{i=0}^n{A}_i{P}_j(i;n,q).$$

Proof. From the MacWilliams identity:

$$A^{\perp }(z)=\frac{1}{q^k}(1+(q-1)z{)}^{n}A\left(\frac{1-z}{1+(q-1)z}\right).$$

Write $u=(1-z)/(1+(q-1)z)$. Then $A(u)={\sum }_{i=0}^n{A}_i{u}^i$, so:

$$A^{\perp }(z)=\frac{1}{q^k}\sum _{i=0}^n{A}_i(1+(q-1)z{)}^{n-i}(1-z{)}^i.$$

Apply the generating function identity $(1+(q-1)z{)}^{n-i}(1-z{)}^i={\sum }_{j=0}^n{P}_j(i)z^j$:

$$A^{\perp }(z)=\frac{1}{q^k}\sum _{i=0}^n{A}_i\sum _{j=0}^n{P}_j(i)z^j=\sum _{j=0}^n\left(\frac{1}{q^k}\sum _{i=0}^n{A}_i{P}_j(i)\right)z^j.$$

Comparing coefficients of $z^j$ on both sides gives $B_j=\frac{1}{q^k}{\sum }_{i=0}^n{A}_i{P}_j(i)$. $\square$

Proposition (LP constraint from MacWilliams). For a binary $[n,k,d]$ code, the weight distribution satisfies

$$\sum _{i=d}^n{A}_i{P}_j(i;n,2)\ge -P_j(0;n,2)$$

for each $j=0,1,\dots ,n$.

Proof. By the Krawtchouk expansion, $q^k{B}_j={\sum }_{i=0}^n{A}_i{P}_j(i)$. Since $A_i=0$ for $0<i<d$ and $A_0=1$:

$$2^k{B}_j=A_0{P}_j(0)+\sum _{i=d}^n{A}_i{P}_j(i)=P_j(0)+\sum _{i=d}^n{A}_i{P}_j(i).$$

Since $B_j\ge 0$ (it counts codewords in the dual) and $2^k>0$:

$$P_j(0)+\sum _{i=d}^n{A}_i{P}_j(i)\ge 0.$$

Rearranging: ${\sum }_{i=d}^n{A}_i{P}_j(i)\ge -P_j(0)$. For $j=0$, $P_0(i)=1$ and the constraint is $\sum A_i\ge -1$, which is automatically satisfied. For $j=1$, $P_1(i)=n-2i$, giving ${\sum }_{i\ge d}{A}_i(n-2i)\ge -(n)$, a nontrivial inequality relating the weight distribution to the code parameters. $\square$

Proposition (MacWilliams for the binary simplex code). The binary simplex code of dimension $r$ has parameters $[2^r-1,r,2^{r-1}]$ and every nonzero codeword has weight $2^{r-1}$. Its dual is the $[2^r-1,2^r-1-r,3]$ Hamming code. Verify the MacWilliams identity connects their weight enumerators.

Proof. The simplex code $S_r$ has weight enumerator

$$A(z)=1+(2^r-1)z^{2^{r-1}}.$$

Its dual is the Hamming code $\mathrm{Ham}(r,2)$ with parameters $[n,k]=[2^r-1,2^r-1-r]$. By MacWilliams:

$$A^{\perp }(z)=\frac{1}{2^r}(1+z{)}^{2^r-1}\left[1+(2^r-1){\left(\frac{1-z}{1+z}\right)}^{2^{r-1}}\right].$$

For $r=3$ ($n=7$): $A(z)=1+7z^4$ and

$$A^{\perp }(z)=\frac{1}{8}(1+z{)}^7\left[1+7{\left(\frac{1-z}{1+z}\right)}^4\right]=1+7z^3+7z^4+z^7,$$

recovering the weight enumerator of the [7,4,3] Hamming code. The general case is verified by the same substitution. $\square$

Connections Master

• 40.06.06 — Linear codes, the Hamming/Singleton/Gilbert-Varshamov bounds; this unit extends that material by using the algebraic structure of the dual code to obtain tighter bounds via the MacWilliams identity.
• 46.01.01 — Entropy and the chain rule; the MRRW bound is expressed in terms of the binary entropy function $H_2$, and the asymptotic GV bound $R\ge 1-H_2(\delta )$ is the information-theoretic lower bound that the LP upper bound constrains from above.
• 01.01.01 — Vector spaces over fields; the entire theory rests on $C$ and $C^{\perp }$ being complementary subspaces of ${\mathbb{F}}_q^n$.
• 46.07.02 — Future unit on algebraic-geometry codes, whose weight enumerators are the primary examples where the LP bound is tested and sometimes beaten.
• 37.07.02 — Cramer's theorem and large deviations; the GV bound has a large-deviations interpretation (random codes achieve distance $d$ with high probability when $k$ is below the GV threshold), complementing the deterministic LP upper bound.
• 40.06.07 — Future unit on BCH and Reed-Solomon codes; their weight enumerators are special cases where MacWilliams can be computed in closed form.

Historical & philosophical context Master

Jessie MacWilliams discovered the identity bearing her name in 1963, while working as a graduate student at Harvard under the supervision of Andrew Gleason. Her original proof appeared in "A theorem on the distribution of weights in a systematic code" (Bell System Technical Journal 42, 1485-1505). The result was striking because it showed that the weight distribution of a linear code and its dual are not independent — knowing one determines the other completely. At the time, this was one of the deepest results in algebraic coding theory, connecting the combinatorial structure of codes to polynomial algebra.

The generalisation to non-binary alphabets and to higher-order weight enumerators followed quickly, with MacWilliams herself extending the result to codes over ${\mathbb{F}}_q$ in her 1969 monograph with Neil Sloane. The connection to characters and the Poisson summation formula (the proof presented in this unit) is due to several authors, with the cleanest formulation appearing in MacWilliams and Sloane's 1977 book The Theory of Error-Correcting Codes (North-Holland), which remains the standard reference.

Philippe Delsarte's 1973 thesis "An Algebraic Approach to the Association Schemes of Coding Theory" (Philips Research Reports Supplement 10) placed the MacWilliams identity in a far more general framework. Delsarte showed that the Hamming scheme $H(n,q)$ — the association scheme on ${\mathbb{F}}_q^n$ where two vectors are in relation $i$ if their Hamming distance is $i$ — carries enough algebraic structure to derive MacWilliams-type inequalities for any code, not just linear ones. The "inner distribution" of a code (the distance histogram, not the weight histogram) satisfies the same positivity constraints under the Krawtchouk transform, giving the Delsarte inequalities. This was a conceptual breakthrough: it showed that the MacWilliams identity is not really about duality of subspaces but about the algebraic structure of the ambient space itself.

Delsarte's framework also unified several previously disconnected results. The sphere-packing bound and the Singleton bound become special cases of the LP bound obtained by choosing particular feasible solutions. The Johnson bound, which improves on the Hamming bound by considering the distance distribution rather than just disjoint balls, is another specialisation. This unification gave coding theorists a single optimisation problem that subsumed all known combinatorial bounds.

The linear-programming bound is a direct consequence of Delsarte's framework. The bound was first applied numerically in the 1970s, but the crowning achievement came in 1977 when McEliece, Rodemich, Rumsey, and Welch solved the LP dual analytically to obtain the MRRW bound. Their result $R(\delta )\le H_2(1/2-\sqrt{\delta (1-\delta )})$ remains the tightest known asymptotic upper bound for binary codes for most values of $\delta$, and closing the gap between the MRRW upper bound and the Gilbert-Varshamov lower bound remains one of the central open problems in information theory.

Bibliography Master

@book{macwilliams-sloane1977,
  author    = {MacWilliams, F. J. and Sloane, N. J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{mceliece-rodemich-rumsey-welch1977,
  author  = {McEliece, R. J. and Rodemich, E. R. and Rumsey, H. and Welch, L. R.},
  title   = {New Upper Bounds on the Rate of a Code via the Delsarte-{M}ac{W}illiams Inequalities},
  journal = {IEEE Trans. Inform. Theory},
  volume  = {IT-23},
  pages   = {157--166},
  year    = {1977},
}
@phdthesis{delsarte1973,
  author = {Delsarte, P.},
  title  = {An Algebraic Approach to the Association Schemes of Coding Theory},
  school = {Universit\'e Catholique de Louvain},
  year   = {1973},
  note   = {Philips Res. Rep. Suppl. 10},
}
@article{macwilliams1963,
  author  = {MacWilliams, F. J.},
  title   = {A Theorem on the Distribution of Weights in a Systematic Code},
  journal = {Bell System Technical Journal},
  volume  = {42},
  pages   = {1485--1505},
  year    = {1963},
}