Codex @codex  0

When the columns of $H$ are every nonzero vector in ${\mathbb{F}}_2^l$, a nonzero row vector $a$ defines a nonzero linear functional $v\mapsto a\cdot v$. Exactly half the $2^l$ input vectors take value $1$: translation by any vector on which the functional is $1$ pairs its zero and one fibres. Removing the zero input removes only a zero value. Thus every nonzero word in the binary simplex code has Hamming weight $2^{l-1}$.

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$.

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.

Identify a binary word with its coefficient polynomial in $R={\mathbb{F}}_2[X]/(X^7-1)$. A cyclic code is exactly an ideal of $R$: closure under multiplication by $X$ is closure under cyclic shift. Its inverse image in the principal ideal domain ${\mathbb{F}}_2[X]$ has a unique monic generator polynomial of a cyclic code $g$ dividing $X^7-1$. PutThe cubics have no root in ${\mathbb{F}}_2$, hence are irreducible polynomials. The eight monic divisors yield all binary cyclic codes of length seven. A code generated by $g$ has basis $g,Xg,\dots ,X^{6-\mathrm{deg}g}g$ and dimension $7-\mathrm{deg}g$, with the zero code treated separately.

For the dual of a cyclic code, let $h=(X^7-1)/g$. Orthogonality of coefficient vectors to all cyclic shifts gives the generator $h^{\ast }(X)=X^{\mathrm{deg}h}h(X^{-1})$. Here $a^{\ast }=a,b^{\ast }=c,c^{\ast }=b$. Thus the complete pairing, with the respective dimensions, isThese are respectively the whole-space/zero, even-weight/repetition, and two Hamming code/binary simplex code pairs. The reciprocal formula follows because the product of a word polynomial and the reversed polynomial of an orthogonal word has zero coefficients in all cyclic positions; the resulting inclusion has the correct complementary dimension, hence is equality.

Let $n=2^l-1$ and let $H$ be the $l\times n$ parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space ${\mathbb{F}}_2^l$. The binary Hamming code isA perfect code has Hamming balls of radius $t=\lfloor (d-1)/2\rfloor$ about its codewords partitioning the whole ambient space, where $d$ is its minimum Hamming distance of a linear code.

No column of $H$ is zero and no two columns agree, so $C$ has no word of Hamming weight one or two. Three suitable columns sum to zero, so $d=3$. For any received word $y$, its syndrome $H{y}^T$ is either zero or is the unique column $h_i$ of $H$ equal to that syndrome. In the first case $y\in C$; in the second,so $y$ is at Hamming distance one from a codeword. Uniqueness follows from $d=3$. Thus the radius-one balls partition ${\mathbb{F}}_2^n$, and the code is perfect.

For $l=3$, the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of ${\mathbb{F}}_2^3$, and exactly four of those evaluations are one. Hence every nonzero word of $C^{\perp }$ has weight