11 Johnson Bound
11.1 Overview
This chapter proves the binary Johnson bound: for a binary code \(C\) of length \(n\) with minimum distance \(d\), if every codeword has weight at most \(w \le J_2(n,d)\) where
then \(|C| \le 2n\).
The proof reduces to a Rankin bound from geometry: a set of unit vectors in \(\mathbb {R}^n\) with pairwise non-positive inner products has size at most \(2n\). Codewords are embedded via a shifted \(\{ \pm 1\} \) map so that the distance and weight constraints force the inner-product condition.
11.2 Johnson bound
\(A_0(n,d,w)\) is the maximum size of an \((n,d,w)\)-admissible code.
If \(n \gt 0\), \(1 \le d\), \(2d \le n\), and \(w \le J_2(n,d)\), then
11.3 Additional declarations
The type of binary words of length \(n\), namely functions \(\mathrm{Fin}\, n \to \mathrm{Bool}\).
Abbreviation for the \(n\)-dimensional real Euclidean space \(\mathbb {R}^n\) with the \(\ell ^2\) inner product, i.e. EuclideanSpace \(\mathbb {R}\) \((\mathrm{Fin}\, n)\).
For a binary word \(x\) of length \(n\), its weight is the number of coordinates where \(x\) takes the value true: \(\mathrm{wt}(x) = \left\lvert \{ \, i : x_i = \texttt{true} \, \} \right\rvert \).
For binary words \(x,y\) of length \(n\), the Hamming distance is the number of coordinates on which they differ: \(\mathrm{hdist}(x,y) = \left\lvert \{ \, i : x_i \neq y_i \, \} \right\rvert \).
The map sending a binary word \(x\) to the real vector in \(\mathbb {R}^n\) whose \(i\)-th coordinate is \(-1\) if \(x_i = \texttt{true}\) and \(+1\) otherwise.
The vector in \(\mathbb {R}^n\) all of whose coordinates equal \(1\).
For a real parameter \(\alpha \) and a binary word \(x\), the vector \(\hat{x}^\alpha = \mathrm{pmOne}(x) - \alpha \cdot \mathbf{1} \in \mathbb {R}^n\).
The rescaling \(u \mapsto \lVert u\rVert ^{-1} \cdot u\) of a vector of \(\mathbb {R}^n\).
Every coordinate of \(\mathbf{1} \in \mathbb {R}^n\) equals \(1\): for each \(i\), \(\mathbf{1}_i = 1\).
If \(x_i = \texttt{false}\) then \(\mathrm{pmOne}(x)_i = 1\).
If \(x_i = \texttt{true}\) then \(\mathrm{pmOne}(x)_i = -1\).
The real quantity
The real quantity
A finite set \(C\) of binary words of length \(n\) is \((n,d,w)\)-admissible when any two distinct elements of \(C\) are at Hamming distance at least \(d\) and every element of \(C\) has weight at most \(w\).
For all binary words \(x,y\) and every coordinate \(i\), \(\mathrm{pmOne}(x)_i \cdot \mathrm{pmOne}(y)_i\) equals \(1\) if \(x_i = y_i\) and \(-1\) otherwise.
For all binary words \(x,y\) of length \(n\),
For every binary word \(x\) of length \(n\),
\(\langle \mathbf{1}, \mathbf{1}\rangle = n\) in \(\mathbb {R}^n\).
For all \(\alpha \in \mathbb {R}\) and binary words \(x,y\),
If \(\alpha \ge 0\), \(\mathrm{hdist}(x,y) \ge d\), and \(\mathrm{wt}(x), \mathrm{wt}(y) \le w\), then
For all \(n,d\) one has \(0 \le \alpha (n,d)\).
If \(n \gt 0\) and \(2d \le n\) then \(\alpha (n,d)^2 = (n - 2d)/n\).
If \(n \gt 0\), \(d \ge 1\), and \(2d \le n\), then \(\alpha (n,d) \lt 1\).
If \(n \gt 0\), \(2d \le n\), and \(w \le J_2(n,d)\), then for \(\alpha = \alpha (n,d)\)
Let \(V\) be a real inner product space, \(u \in V\) a unit vector, and \(x,y \in V\) with \(\langle x,u\rangle \le 0\), \(\langle y,u\rangle \le 0\) and \(\langle x,y\rangle \le 0\). Then the components of \(x\) and \(y\) orthogonal to \(u\) satisfy \(\langle x - \langle x,u\rangle u,\ y - \langle y,u\rangle u\rangle \le 0\).
For a unit vector \(u\) and any \(x\) in a real inner product space, \(\lVert x - \langle x,u\rangle u\rVert ^2 = \lVert x\rVert ^2 - \langle x,u\rangle ^2\).
If \(u\) and \(x\) are unit vectors with \(\langle x,u\rangle \le 0\) and \(x \neq u\), \(x \neq -u\), then \(x - \langle x,u\rangle u \neq 0\).
Let \(u\) be a unit vector and \(S\) a set of unit vectors each having non-positive inner product with \(u\). Then \(x \mapsto x - \langle x,u\rangle u\) is injective on \(S\).
For \(u,v\) in a real inner product space, \(\mathrm{orthProj}(u,v) = v - \langle u,v\rangle u\), the projection of \(v\) onto the orthogonal complement of \(\mathrm{span}\{ u\} \).
If \(\lVert u\rVert = 1\) then \(\mathrm{orthProj}(u,v) \in (\mathrm{span}_{\mathbb {R}}\{ u\} )^{\perp }\) for every \(v\).
If \(u\) and \(v\) are unit vectors with \(v \neq u\) and \(v \neq -u\), then \(\mathrm{orthProj}(u,v) \neq 0\).
Let \(\lVert u\rVert = 1\) and let \(v,w\) satisfy \(\langle v,w\rangle \le 0\), \(\langle v,u\rangle \le 0\) and \(\langle w,u\rangle \le 0\). Then \(\langle \mathrm{orthProj}(u,v), \mathrm{orthProj}(u,w)\rangle \le 0\).
Let \(u,v,w\) be unit vectors with \(\langle v,u\rangle \le 0\), \(\langle w,u\rangle \le 0\), \(\langle v,w\rangle \le 0\), with \(v,w \notin \{ u,-u\} \) and \(v \neq w\). Then the normalized projections \(\lVert \mathrm{orthProj}(u,v)\rVert ^{-1}\mathrm{orthProj}(u,v)\) and \(\lVert \mathrm{orthProj}(u,w)\rVert ^{-1}\mathrm{orthProj}(u,w)\) cannot be equal (the statement derives a contradiction from their equality).
If \(u,v\) are unit vectors with \(v \neq u\) and \(v \neq -u\), then \(\lVert \ \lVert \mathrm{orthProj}(u,v)\rVert ^{-1}\, \mathrm{orthProj}(u,v)\ \rVert = 1\).
Under \(\lVert u\rVert = 1\), \(\langle v,w\rangle \le 0\), \(\langle v,u\rangle \le 0\) and \(\langle w,u\rangle \le 0\) (with both projections nonzero), the normalized projections of \(v\) and \(w\) also have non-positive inner product.
For a unit vector \(u\) in a finite-dimensional real inner product space \(V\), \(\dim _{\mathbb {R}} (\mathrm{span}_{\mathbb {R}}\{ u\} )^{\perp } = \dim _{\mathbb {R}} V - 1\).
For a finite subset \(S\) of an additive group and \(u \in S\), \(\left\lvert S\right\rvert \le \left\lvert \{ \, v \in S : v \neq u \text{ and } v \neq -u \, \} \right\rvert + 2\).
Given a unit vector \(u\), this packages the normalized projection \(\lVert \mathrm{orthProj}(u,v)\rVert ^{-1}\mathrm{orthProj}(u,v)\) together with its membership proof as an element of the subspace \((\mathrm{span}_{\mathbb {R}}\{ u\} )^{\perp }\).
The value in \(V\) underlying \(\mathrm{mkProj}(u,v)\) is \(\lVert \mathrm{orthProj}(u,v)\rVert ^{-1}\, \mathrm{orthProj}(u,v)\).
Let \(V\) be a finite-dimensional real inner product space and \(S \subseteq V\) a finite set of unit vectors whose pairwise inner products are non-positive. Then \(\left\lvert S\right\rvert \le 2 \dim _{\mathbb {R}} V\).
A finite set \(S\) of unit vectors in \(\mathbb {R}^n\) with pairwise non-positive inner products satisfies \(\left\lvert S\right\rvert \le 2n\).
If \(n \gt 0\) and \(0 \le \alpha \lt 1\), then \(\hat{x}^\alpha \neq 0\) for every binary word \(x\) of length \(n\).
Let \(n \gt 0\) and let \(C\) be a finite set of binary words of length \(n\) with pairwise Hamming distance at least \(d\) and all weights at most \(w\). If \(\alpha \ge 0\) is such that \(\hat{x}^\alpha \neq 0\) for all \(x \in C\) and \((n - 2d) + \alpha ^2 n + 2\alpha (2w - n) \le 0\), then \(\left\lvert C\right\rvert \le 2n\).
Assume \(n \gt 0\), \(1 \le d\) and \(2d \le n\). If \(C\) is a finite set of binary words of length \(n\) whose distinct elements are at Hamming distance at least \(d\), whose weights are all at most \(w\), and if \(w \le J_2(n,d)\), then \(\left\lvert C\right\rvert \le 2n\).
Assume \(n \gt 0\), \(1 \le d\) and \(2d \le n\). Every \((n,d,w)\)-admissible code \(C\) with \(w \le J_2(n,d)\) satisfies \(\left\lvert C\right\rvert \le 2n\).
If every \((n,d,w)\)-admissible code \(C\) has \(\left\lvert C\right\rvert \le K\), then \(A_0(n,d,w) \le K\).