Proof for prime \(q=p.\) This proof is not examinable.

Since \(p\) is a prime, the field \(\F _p\) consists of elements \(0,1,\dots ,p-1\) (residues of integers modulo \(p).\) Being able to explicitly list the field elements — not possible for a general prime power \(q\) — simplifies the proof.

Let \(C\subseteq \F _p^n\) be linear. We fix the complex number \(\omega = e^{2\pi i/p},\) a primitive \(p\)th root of \(1.\) We have \(\omega ^p=1\) and \(\omega ,\omega ^2,\ldots ,\omega ^{p-1}\ne 1.\) We can write \(\omega ^a\) if \(a\in \F _p\) — this complex number is well-defined, even though \(a\) is only defined modulo \(p.\)

Given \(\ul c\in C,\) \(\ul v\in \F _p^n,\) denote

\[ \Phi (\ul c,\ul v)=\omega ^{\ul c \cdot \ul v} x^{n-w(\ul v)} y^{w(\ul v)}. \]

We will compute \(\sum \limits _{\ul c\in C,\ \ul v\in \F _p^n} \Phi (\ul c,\ul v)\) in two different ways.

Way 1. If \(\ul v\in C^\perp ,\) then \(\ul c \cdot \ul v=0\) for all \(\ul c\in C,\) so \(\Phi (\ul c,\ul v)= x^{n-w(\ul v)} y^{w(\ul v)}.\)

If, however, \(\ul v\notin C^\perp ,\) there is a codevector \(\ul d\in C\) such that \(\ul d \cdot \ul v=a\ne 0\) in \(\F _p.\) Observe that \(\Phi (\ul d+\ul c,\ul v)=\omega ^{\ul d \cdot \ul v}\Phi (\ul c,\ul v)=\omega ^a \Phi (\ul c,\ul v).\) We know that \(\ul d+C=C,\) so

\[ \sum _{\ul c\in C}\Phi (\ul c,\ul v) = \sum _{\ul c\in C}\Phi (\ul d+\ul c,\ul v) = \omega ^a \sum _{\ul c\in C}\Phi (\ul c,\ul v) \quad \implies \quad (\omega ^a-1)\sum _{\ul c\in C}\Phi (\ul c,\ul v)=0. \]

Since \(\omega ^a\ne 1,\) we have

\[ \sum _{\ul c\in C}\Phi (\ul c,\ul v)=0 \quad \text {for }\ul v\notin C^\perp . \]

We conclude that

\[ \sum \limits _{\ul c\in C,\ \ul v\in \F _p^n} \Phi (\ul c,\ul v) =\sum \limits _{\ul c\in C,\ \ul v\in C^\perp } \Phi (\ul c,\ul v) =\#C \sum _{\ul v\in C^\perp } x^{n-w(\ul v)} y^{w(\ul v)} =(\#C)W_{C^\perp }(x,y). \]

Way 2. If \(v\) is a symbol, \(v\in \F _p,\) we introduce the “weight of \(v\)”, \(w(v),\) as follows: \(w(v)=1\) if \(v\ne 0\) and \(w(v)=0\) if \(v=0.\) Surely, for a vector \(\ul v\in \F _p^n\) we have \(w(\ul v)=w(v_1)+\dots +w(v_n).\) We then rewrite

\begin{align*} \Phi (\ul c,\ul v) & = \omega ^{c_1v_1+\dots +c_nv_n} x^{1-w(v_1)}y^{w(v_1)}\dots x^{1-w(v_n)}y^{w(v_n)} \\ & = \omega ^{c_1v_1}x^{1-w(v_1)}y^{w(v_1)}\dots \omega ^{c_nv_n}x^{1-w(v_n)}y^{w(v_n)}. \end{align*} We now sum over \(\ul v\in \F _p^n\) first: each coordinate of \(\ul v\) runs over \(\F _p=\{0,1,\ldots ,p-1\}.\) So, for a fixed \(\ul c\in C,\)

\begin{align*} \sum _{\ul v\in \F _p^n} \Phi (\ul c,\ul v) & = \sum _{v_1=0}^{p-1} \dots \sum _{v_n=0}^{p-1} \Phi (\ul c,\ul v) \\ & =\sum _{v_1=0}^{p-1} \omega ^{c_1v_1}x^{1-w(v_1)}y^{w(v_1)} \dots \sum _{v_n=0}^{p-1}\omega ^{c_nv_n}x^{1-w(v_n)}y^{w(v_n)}. \tag {*} \end{align*} Let us analyse the first factor in the product on the right-hand side of (*):

\begin{equation*} \sum _{v_1=0}^{p-1}\omega ^{c_1v_1}x^{1-w(v_1)}y^{w(v_1)} = x+\bigl (\sum _{v_1=1}^{p-1} \omega ^{c_1v_1} \bigr )y. \end{equation*}

If \(c_1=0,\) the coefficient of \(y\) is clearly \(1+1+\dots +1=p-1,\) whereas if \(c_1\ne 0,\) the coefficient of \(y\) is the sum of a geometric progression

\[ \sum _{v_1=1}^{p-1} \omega ^{c_1v_1} = -1 + \sum _{v_1=0}^{p-1} \omega ^{c_1v_1} =-1+\frac {1-(\omega ^{c_1})^p}{1-\omega ^{c_1}} = -1+ \frac {0}{1-\omega ^{c_1}} = -1 \]

since \((\omega ^{c_1})^p=1.\) Hence the first factor on the right-hand side of (*) is

\[ \left \{ \begin {array}{rl} x+(p-1)y, & \text { if }c_1=0, \\ x-y, & \text { if }c_1\ne 0. \end {array} \right . \]

The same applies to the second, ..., \(n\)th factor in (*), hence (*) has \(w(\ul c)\) factors equal to \(x-y\) and \(n-w(\ul c)\) factors equal to \(x+(p-1)y.\) In other words, (*) evaluates as \((x+(p-1)y)^{n-w(\ul c)}(x-y)^{w(\ul c)}.\) Therefore,

\begin{equation*} \sum _{\ul c\in C}\sum _{\ul v\in \F _p^n} \Phi (\ul c,\ul v) = \sum _{\ul c\in C} (x+(p-1)y)^{n-w(\ul c)}(x-y)^{w(\ul c)} =W_C(x+(p-1)y,\, x-y). \end{equation*}

Comparing Way 2 and Way 1, we conclude that \(W_C(x+(p-1)y,\, x-y)=(\#C)W_{C^\perp }(x,y).\) This is the MacWilliams identity for \(q=p.\) □

Proof. We count codevectors of weight \(1\) in the dual code \(C^\perp .\) By Theorem 5.1, \(\ul v\in C^\perp \) iff \(\ul vG^T=\ul 0\) where \(G\) is a generator matrix of \(C.\) If \(\ul v\) is of weight \(1\) with \(v_i\ne 0,\) then the \(i\)th column of \(G\) is zero. The non-zero \(v_i\) can be chosen in \(q-1\) ways, so each zero column of \(G\) gives rise to \(q-1\) vectors of weight \(1\) in \(C^\perp ,\) and there are \(z(q-1)\) such vectors in total.

We must get the same number as the coefficient of \(x^{n-1}y\) in the weight enumerator \(W_{C^\perp }(x,y),\) which by the MacWilliams identity equals

\begin{equation} \label {eq:awe1} \frac 1{\#C}W_C(x+(q-1)y,x-y) = \frac 1{\#C} \sum _{\ul v\in C} (x+(q-1)y)^{n-w(\ul v)} (x-y)^{w(\ul v)}. \end{equation}

We put \(x=1\) and work out the coefficient of \(y.\) By the Binomial Theorem,

\begin{align*} (1+(q-1)y)^{n-w(\ul v)} &= 1+ (n-w(\ul v))(q-1)y && +\text {higher powers of $y$}, \\ (1-y)^{w(\ul v)} &= 1 - w(\ul v)y && + \text {higher powers of $y$}, \end{align*} and so the coefficient of \(y\) in the product of these two expressions is

\[ (n-w(\ul v))(q-1)-w(\ul v) = n(q-1)-q w(\ul v). \]

Summing over \(\ul v\in C\) then dividing by \(\#C\) gives the coefficient of \(y\) in (8.1) as \(n(q-1) - q \frac 1{\#C}\sum _{\ul v\in C} w(\ul v).\) We thus get the equation

\[ z(q-1) = n(q-1) - q \frac 1{\#C} \sum _{\ul v\in C} w(\ul v), \]

hence the average of all weights, \(\frac 1{\#C} \sum _{\ul v\in C} w(\ul v),\) is \((n-z)\frac {q-1}q\) as claimed. □

Proof. The length and dimension of \(\Sigma (r,q)=\Ham (r,q)^\perp \) are dictated by the parameters of the Hamming code, see Theorem 7.3. It remains to calculate the distances.

Since \(\Sigma (r,q)\) is linear, it suffices to show that every non-zero \(\ul v\in \Sigma (r,q)\) has weight \(q^{r-1}.\)

By linear algebra, there is a basis of \(\Sigma (r,q)\) which contains \(\ul v,\) hence \(\ul v\) is the first row of some generator matrix \(H'\) of \(\Sigma (r,q).\)

Since \(H'\) is a check matrix for \(\Ham (r,q)\) and \(d(\Ham (r,q))=3,\) by Distance Theorem 7.2 no two columns of \(H'\) are proportional, hence the columns of \(H'\) represent distinct lines in \(\F _q^r.\) Therefore, the weight of \(\ul v\) (the first row of \(H')\) is the number of lines where the first entry of a representative vector is not zero.

The total number of possible columns of size \(r\) with non-zero top entry is \((q-1)\) (choices for the top entry) \(\times q^{r-1}\) (choices for the other entries which are unrestricted). But \((q-1)\) non-zero columns form a line, hence the number of required lines is \((q-1)q^{r-1}/(q-1)=q^{r-1}.\) Hence \(w(\ul v)=q^{r-1}\) as claimed. □

Proof. The MacWilliams identity, Theorem 8.1, in the case of binary codes gives \(W_{C^\perp }(x,y)=\frac {1}{\#C}W_C(x+y,x-y).\) We put \(C=\Sigma (r,2)\) so that \(C^\perp =\Ham (r,2).\) By Theorem 7.3, \(n=2^r-1\) so that \(\#C=2^r=n+1\) and the weight of each non-zero codevector in \(\Sigma (r,2)\) is \(q^{r-1}=2^{r-1}=\frac {n+1}2.\) We also have \(n-q^{r-1} = n-\frac {n+1}{2}=\frac {n-1}{2}.\)

Substituting these in the MacWilliams identity, we obtain \(W_{\Ham (r,2)}\) as stated. □

Proof. Let \(M=\#C.\) The code \(C\) contains the zero vector, \(\ul 0,\) and \(M-1\) vectors of weight at least \(d.\) Then the average weight of a codevector of \(C\) is at least

\[ \frac {1\times 0 + (M-1)\times d}{M} = \bigl (1-\frac {1}{M}\bigr )d. \]

So from the Average Weight Equation (where \(z\) is the number of zero columns in a generator matrix of \(C)\) we obtain

\[ (n-z)\bigl (1-\frac 12\bigr ) \ge \bigl (1-\frac 1M\bigr )d \quad \implies \quad \frac n2\ge \bigl (1-\frac 1M\bigr )d \quad \iff \quad \frac {n}{2d} \ge 1-\frac 1M \]

so that \(1/M\ge 1-n/(2d)=(2d-n)/(2d)\) and \(M\le 2d/(2d-n),\) as claimed. □