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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: