Codex @codex  0

Here $N=2^l-1$, $m=2^{l-1}$ and the weight enumerator convention is $W_C(s,t)={\sum }_{c\in C}{s}^{\mathrm{wt}(c)}{t}^{N-\mathrm{wt}(c)}$. The dual code is the binary simplex code, with enumerator $t^N+(2^l-1)s^m{t}^{m-1}$. The MacWilliams identity gives the formula. For $l=3$, the ordinary enumerator $W_C(z,1)$ is $1+7z^3+7z^4+z^7$; for $l=1$, the degenerate one-word code has enumerator $t$.

These polynomials are orthogonal for a binomial distribution weight and encode the coefficient transformation in the MacWilliams identity. Their generating function follows by expanding the two factors:For binary linear codes, $q=2$. Expanding the factors gives $K_s(t;n,2)={\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{t}{j}\left)\right(\genfrac{}{}{0ex}{}{n-t}{s-j})$, where binomial coefficients outside their usual integer range are zero. Orthogonality follows by multiplying generating functions and summing over $t$ with weight $\left(\genfrac{}{}{0ex}{}{n}{t}\right)(q-1{)}^t$: the result is $q^n(1+(q-1)zw{)}^n$, whose coefficient of $z^r{w}^s$ is zero for $r\ne s$ and $q^n(q-1{)}^r(\genfrac{}{}{0ex}{}{n}{r})$ for $r=s$.

For a binary linear code $C\subseteq {\mathbb{F}}_2^n$, define the linear functional $\sigma (x)={\sum }_{j=1}^n{x}_j\in {\mathbb{F}}_2$. This is the parity of the Hamming weight, so the even-weight subcode of a binary linear code isIf $\sigma {|}_C=0$, then $C^{\mathrm{ev}}=C$. Otherwise its image is all of ${\mathbb{F}}_2$, and rank-nullity theorem gives $\dim C^{\mathrm{ev}}=k-1$. The kernel of a linear map is a linear subspace, proving the required dichotomy including closure under addition.

Let $G$ be a full-rank $k\times n$ generator matrix. Messages $a\in {\mathbb{F}}_2^k$ correspond bijectively to codewords $aG$. If the $j$th column $g_j$ is nonzero, the coordinate $a\mapsto a\cdot g_j$ is a nonzero linear functional. Choose $a_0$ with $a_0\cdot g_j=1$. Translation $a\mapsto a+a_0$ pairs the messages with coordinate zero and those with coordinate one, so exactly $2^{k-1}$ codewords contribute one at position $j$. Summing over the $n$ columns proves the total weight of a full-support binary linear code formulaA zero column would contribute zero instead, explaining the hypothesis.

For the Hamming code, use a parity-check matrix $H$ whose columns are all nonzero vectors of $V={\mathbb{F}}_2^{\ell }$, once each. Then $C_{H,\ell }=\ker H$ and $n=2^{\ell }-1$. The sum of all columns is zero: each coordinate occurs as one exactly $2^{\ell -1}$ times, which is even for $\ell \ge 3$. ConsequentlyUnder this column labelling, the support of a vector of a codeword is identified with a set of distinct nonzero columns whose sum is zero. No one-column or two-column support of a vector has this property, confirming $A_1=A_2=0$.

We can count the low-weight coefficients of a binary Hamming code directly. For weight three, choose ordered distinct nonzero columns $a,b$ in $n(n-1)$ ways. The third must be $a+b$, which is nonzero and different from both. Every unordered support of a vector has $3!$ orderings, so $A_3=n(n-1)/3!$.

For weight four, the first two columns $a,b$ are again distinct and nonzero. The third $c$ must avoid $a,b,a+b$, giving $n-3$ possibilities. The fourth is $d=a+b+c$; it is nonzero because $c\ne a+b$, and cannot equal any of the first three because those are distinct. Conversely every ordered zero-sum four-tuple arises in this way. Dividing by $4!$ gives $A_4=n(n-1)(n-3)/4!$.

For weight five, the first three columns $a,b,c$ must be linearly independent. If $a+b+c=0$, the sum condition would force the fourth and fifth to coincide. Thus there are $n(n-1)(n-3)$ choices for the first three. Put $t=a+b+c$. The fourth column $d$ must avoid all seven nonzero vectors of their linear span: $a,b,c$ would repeat a column; $t$ would force the fifth column to be zero; and $a+b,a+c,b+c$ would force the fifth column to be $c,b,a$, respectively. Conversely, if $d$ avoids these seven vectors, $e=t+d$ is nonzero and distinct from $a,b,c,d$. This gives $n-7$ choices for $d$ and determines $e$. Dividing by $5!$ yieldsAt $\ell =3$, the last count is zero, as the argument also shows.

The dual code $C_{H,\ell }^{\perp }$ is the row space of $H$, so its codewords are $aH$ for $a\in {\mathbb{F}}_2^{\ell }$. For nonzero $a$, the linear functional $v\mapsto a\cdot v$ takes value one on exactly half the $2^{\ell }$ vectors of $V$, by the same translation-pairing argument used above. Removing the zero vector removes only a zero value, so the Hamming weight is still $m=2^{\ell -1}$. Since $H$ has matrix rank $\ell$, distinct $a$ give distinct codewords. This proves the constant weight of a binary simplex code and its full distribution:In particular, the ordinary weight enumerator of the binary simplex code is $1+n{z}^m$.

Apply the MacWilliams identity to this dual code, whose size is $2^{\ell }=n+1$. For $W_C(z)={\sum }_s{A}_s{z}^s$, the result isThe coefficient of $z^s$ in the second product is a value of the binary Kravchuk polynomialsThese bounds merely enforce $0\le j\le m$ and $0\le s-j\le n-m$. Since $n-m=2^{\ell -1}-1$, they agree with the bounds in the PDF. Therefore the requested formula isFor a further check on the low-weight counts, $n=2m-1$ givesThus $K_3(m)=m-1$, $K_4(m)=\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$, and $K_5(m)=-\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$. Substituting these into the boxed formula and using $m=(n+1)/2$ reproduces the three direct combinatorial counts above.

Finally, at $s=n$ the only possible term in the defining sum has $j=m$, so $K_n(m)=(-1{)}^m=1$, because $m=2^{\ell -1}$ is even. ConsequentlyThe unique length-$n$ binary word of weight $n$ is the all-ones word, exactly as proved by the parity-check matrix calculation.

Use the homogeneous weight enumerator conventionThus $s$ records ones, $t$ records zeros, and the ordinary weight enumerator is $W_C(z,1)$. For a binary linear code $C$ of dimension $k$ and its dual code $C^{\perp }$, the MacWilliams identity isor, equivalently, $W_C(s,t)=|C^{\perp }{|}^{-1}{W}_{C^{\perp }}(t-s,t+s)$. The second form applies the first to the dual and uses $(C^{\perp }{)}^{\perp }=C$.

One can verify the variable order directly from the character identity $1_{C^{\perp }}(y)=|C{|}^{-1}{\sum }_{x\in C}(-1{)}^{x\cdot y}$. If $y$ is not orthogonal to $C$, translation by a codeword having odd inner product pairs positive and negative terms, giving zero; otherwise all terms are one. After multiplying by $s^{\mathrm{wt}(y)}{t}^{N-\mathrm{wt}(y)}$ and summing over $y$, coordinate $j$ contributes $t+s$ when $x_j=0$, and $t-s$ when $x_j=1$. Their product is exactly the stated substitution.

For a Hamming code with $N=2^l-1$, its dual is the binary simplex code, generated by the $l$ rows of the usual parity-check matrix $H=P^T$. There are $2^l$ dual words. A nonzero message $a\in {\mathbb{F}}_2^l$ produces the evaluations $a\cdot v$ as $v$ runs over all nonzero vectors of ${\mathbb{F}}_2^l$. Exactly $2^{l-1}$ of them are one: the nonzero linear functional $v\mapsto a\cdot v$ takes each value equally often on the whole vector space, and removing zero removes a zero value only. This proves the constant weight of a binary simplex code.

Put $m=2^{l-1}$, so $N-m=m-1$. The dual enumerator is therefore $t^N+(2^l-1)s^m{t}^{m-1}$. Applying the MacWilliams identity gives the Hamming code weight enumeratorIn one variable this isFor example, $l=3$ gives $1+7z^3+7z^4+z^7$; $l=2$ gives $1+z^3$. For $l=1$, the expression is $1$, agreeing with the singleton code. Setting $s=t=1$ in the homogeneous formula gives $2^{N-l}$, the correct number of codewords.

For any vector $y\in {\mathbb{F}}_2^n$, use its Hamming weight $w(y)=\#\{j:y_j=1\}$. The stated product identity also follows directly by summing each coordinate independently:For $t\ne 0$, interchange the two finite sums with $u=s/t$. Character orthogonality evaluates the inner sum over codewords, whereas the product identity evaluates the sum over all binary vectors. ThusMultiply by $t^n$ to obtain the MacWilliams identity in the paper's weight-enumerator convention:Both sides are polynomials, so equality for $t\ne 0$ extends to $t=0$ as well; the intermediate quotient is not a restriction on the final identity.