Proof for prime $q=p.$ This proof is not examinable.

Since $p$ is a prime, the field ${\mathbb{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 {\mathbb{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,\dots ,{\omega }^{p-1}\ne 1.$ We can write ${\omega }^a$ if $a\in {\mathbb{F}}_p$ — this complex number is well-defined, even though $a$ is only defined modulo $p.$

Given $\underset{―}{c}\in C,$ $\underset{―}{v}\in {\mathbb{F}}_p^n,$ denote

$$\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})={\omega }^{\underset{―}{c}\cdot \underset{―}{v}}{x}^{n-w(\underset{―}{v})}{y}^{w(\underset{―}{v})}.$$

We will compute $\sum _{\underset{―}{c}\in C,\underset{―}{v}\in {\mathbb{F}}_p^n}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})$ in two different ways.

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

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

$$\sum _{\underset{―}{c}\in C}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})=\sum _{\underset{―}{c}\in C}\mathrm{\Phi }(\underset{―}{d}+\underset{―}{c},\underset{―}{v})={\omega }^a\sum _{\underset{―}{c}\in C}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})⟹({\omega }^a-1)\sum _{\underset{―}{c}\in C}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})=0.$$

Since ${\omega }^a\ne 1,$ we have

$$\sum _{\underset{―}{c}\in C}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})=0\text{for }\underset{―}{v}\notin C^{\perp }.$$

We conclude that

$$\sum _{\underset{―}{c}\in C,\underset{―}{v}\in {\mathbb{F}}_p^n}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})=\sum _{\underset{―}{c}\in C,\underset{―}{v}\in C^{\perp }}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})=\mathrm{\#}C\sum _{\underset{―}{v}\in C^{\perp }}{x}^{n-w(\underset{―}{v})}{y}^{w(\underset{―}{v})}=(\mathrm{\#}C)W_{C^{\perp }}(x,y).$$

Way 2. If $v$ is a symbol, $v\in {\mathbb{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 $\underset{―}{v}\in {\mathbb{F}}_p^n$ we have $w(\underset{―}{v})=w(v_1)+\cdots +w(v_n).$ We then rewrite

$$\begin{array}{rl}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})& ={\omega }^{c_1{v}_1+\cdots +c_n{v}_n}{x}^{1-w(v_1)}{y}^{w(v_1)}\dots x^{1-w(v_n)}{y}^{w(v_n)}\\ & ={\omega }^{c_1{v}_1}{x}^{1-w(v_1)}{y}^{w(v_1)}\dots {\omega }^{c_n{v}_n}{x}^{1-w(v_n)}{y}^{w(v_n)}.\end{array}$$ We now sum over $\underset{―}{v}\in {\mathbb{F}}_p^n$ first: each coordinate of $\underset{―}{v}$ runs over ${\mathbb{F}}_p=\{0,1,\dots ,p-1\}.$ So, for a fixed $\underset{―}{c}\in C,$

$$\begin{array}{rl}\sum _{\underset{―}{v}\in {\mathbb{F}}_p^n}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})& =\sum _{v_1=0}^{p-1}\dots \sum _{v_n=0}^{p-1}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})\\ \text{(*)}& & =\sum _{v_1=0}^{p-1}{\omega }^{c_1{v}_1}{x}^{1-w(v_1)}{y}^{w(v_1)}\dots \sum _{v_n=0}^{p-1}{\omega }^{c_n{v}_n}{x}^{1-w(v_n)}{y}^{w(v_n)}.\end{array}$$ Let us analyse the first factor in the product on the right-hand side of (*):

$$\sum _{v_1=0}^{p-1}{\omega }^{c_1{v}_1}{x}^{1-w(v_1)}{y}^{w(v_1)}=x+(\sum _{v_1=1}^{p-1}{\omega }^{c_1{v}_1})y.$$

If $c_1=0,$ the coefficient of $y$ is clearly $1+1+\cdots +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_1{v}_1}=-1+\sum _{v_1=0}^{p-1}{\omega }^{c_1{v}_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

$$\{\begin{array}{rl}x+(p-1)y,& \text{ if }{c}_1=0,\\ x-y,& \text{ if }{c}_1\ne 0.\end{array}$$

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

$$\sum _{\underset{―}{c}\in C}\sum _{\underset{―}{v}\in {\mathbb{F}}_p^n}\mathrm{\Phi }(\underset{―}{c},\underset{―}{v})=\sum _{\underset{―}{c}\in C}(x+(p-1)y{)}^{n-w(\underset{―}{c})}(x-y{)}^{w(\underset{―}{c})}=W_C(x+(p-1)y,x-y).$$

Comparing Way 2 and Way 1, we conclude that $W_C(x+(p-1)y,x-y)=(\mathrm{\#}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, $\underset{―}{v}\in C^{\perp }$ iff $\underset{―}{v}{G}^T=\underset{―}{0}$ where $G$ is a generator matrix of $C.$ If $\underset{―}{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{array}{}\text{(8.1)}& \frac{1}{\mathrm{\#}C}{W}_C(x+(q-1)y,x-y)=\frac{1}{\mathrm{\#}C}\sum _{\underset{―}{v}\in C}(x+(q-1)y{)}^{n-w(\underset{―}{v})}(x-y{)}^{w(\underset{―}{v})}.\end{array}$$

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

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

$$(n-w(\underset{―}{v}))(q-1)-w(\underset{―}{v})=n(q-1)-qw(\underset{―}{v}).$$

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

$$z(q-1)=n(q-1)-q\frac{1}{\mathrm{\#}C}\sum _{\underset{―}{v}\in C}w(\underset{―}{v}),$$

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

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

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

By linear algebra, there is a basis of $\mathrm{\Sigma }(r,q)$ which contains $\underset{―}{v},$ hence $\underset{―}{v}$ is the first row of some generator matrix $H^{\prime }$ of $\mathrm{\Sigma }(r,q).$

Since $H^{\prime }$ is a check matrix for $\mathrm{Ham}(r,q)$ and $d(\mathrm{Ham}(r,q))=3,$ by Distance Theorem 7.2 no two columns of $H^{\prime }$ are proportional, hence the columns of $H^{\prime }$ represent distinct lines in ${\mathbb{F}}_q^r.$ Therefore, the weight of $\underset{―}{v}$ (the first row of $H^{\prime })$ 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(\underset{―}{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}{\mathrm{\#}C}{W}_C(x+y,x-y).$ We put $C=\mathrm{\Sigma }(r,2)$ so that $C^{\perp }=\mathrm{Ham}(r,2).$ By Theorem 7.3, $n=2^r-1$ so that $\mathrm{\#}C=2^r=n+1$ and the weight of each non-zero codevector in $\mathrm{\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_{\mathrm{Ham}(r,2)}$ as stated. □

Proof. Let $M=\mathrm{\#}C.$ The code $C$ contains the zero vector, $\underset{―}{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}=(1-\frac{1}{M})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)(1-\frac{1}{2})\ge (1-\frac{1}{M})d⟹\frac{n}{2}\ge (1-\frac{1}{M})d⟺\frac{n}{2d}\ge 1-\frac{1}{M}$$

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