## A proof of a Plotkin bound

Let $d \in \mathbf{N}$. One of the Plotkin bounds states that a code $C \subseteq \mathbf{F}_2^{2d}$ with minimum distance $d$ has at most $4d$ codewords. One nice proof (that actually gives a stronger result) uses some elementary geometry; the inequality in the following result is Exercise 2 in the linked notes.

Lemma. Suppose that $u_1, u_2, \ldots, u_m$ are vectors in $\mathbf{R}$
such that $\left< u_i, u_j \right> \le 0$ for all $i \not= j$. Then $m \le 2n$ with equality if and only if $\{u_1, u_2, \ldots, u_{2n}\} = \{ \pm v_1, \pm v_2, \ldots, \pm v_n \}$ where the $v_i$ are orthogonal vectors.

Proof. We may assume that $m > n$ and that $n \ge 2$. Let $\{w_1,\ldots,w_r\}$ be a minimal subset of linearly dependent vectors chosen from the $u_i$ and let

$\{u_1,\ldots, u_m\} = \{w_1,\ldots,w_r\} \cup \{v_1,\ldots, v_{m-r} \}.$

Choose $\alpha_i \in \mathbf{R}$ such that $\sum_{i=1}^r \alpha_i w_i = 0$. By the first part of the lemma in the previous post, we may assume that $\alpha_i > 0$ for all $i$. For each $v_j$ we have

$0 = \left< v_j, \sum_{i=1}^r \alpha_i w_i \right> = \sum_{i=1}^r \alpha_i \left< v_j, w_i \right>.$

Since $\alpha_i > 0$ and $\left< v_j, w_i \right> \le 0$, we must have $\left< v_j, w_i \right> = 0$ for all $i$. Hence the spaces spanned by the $u_i$ and $v_j$ are orthogonal. The space spanned by the $u_i$ has dimension $r-1$, so the $v_j$ lie in a subspace of dimension $n-r+1$. By induction on the dimension we have

$m-r \le 2(n-r+1) = 2n-2r + 2 \le 2n$.

Moreover, if equality holds then $r=2$ so $w_2 = -w_1$ and continuing inductively with the $v_j$, we see that the $u_i$ are as claimed.

Proof of the Plotkin bound. Let $C \subseteq \mathbf{F}_2^{2d}$ be a code with minimum distance $d$. We can map each codeword to a vector in $\mathbf{R}^{2d}$ by sending $0 \in \mathbf{F}_2$ to $1 \in \mathbf{R}$ and $1 \in \mathbf{F}_2$ to $-1 \in \mathbf{R}$. Since each pair of vectors differs in at least $d$ places, this gives us $|C|$ vectors in $\mathbf{R}^{2d}$, such that if $u, v$ are different vectors then $\left< u, v \right> \le 0$. By the previous lemma, $|C| \le 4d$, with equality if and only if

$C = \{ c_1, \bar{c}_1, c_2, \bar{c}_2, \ldots, c_{2d}, \bar{c}_{2d} \}$

where any two $c_i$ differ in exactly $d$ positions, and $\bar{c}$ denotes the vector obtained from the codeword $c$ by interchanging $0 \in \mathbf{F}_2$ with $1 \in \mathbf{F}_2$.