next up previous
Next: The Nordstrom Robinson Code Up: Bounds on the size Previous: and

Plotkin Bound

.

Theorem 2.2.1   Let $ r = 1 - \frac1q$. Then,

$\displaystyle A_q(n,d) \leq \left\lfloor \frac{d}{d-rn} \right\rfloor $

if $ n \leq d \leq rn$.

Proof. Let $ M = A_q(n,d)$. Let $ \mathcal{C}$ be an $ (n,M,\geq d)_q$ code. Let

% latex2html id marker 11775
$\displaystyle S = \sum_{\textbf x \in \mathcal{C}} \sum_{\textbf y \in \mathcal{C}} d(x,y) $

We will find an upper bound and a lower bound for $ S$.
Lower Bound:

% latex2html id marker 11779
$\displaystyle d(x,y) = 0, \, \textbf x = \textbf y $

$\displaystyle d(x,y) \geq d,$   otherwise$\displaystyle $

$\displaystyle S \geq M(M-1)d. $

Upper Bound:
For $ 1 \leq i \leq n$ and $ \alpha \in \mathbb{F}_q$, set

% latex2html id marker 11790
$\displaystyle n_{i,\alpha} = \char93  \{ \textbf x \in \mathcal{C}: x_i = \alpha \} \in \mathbb{Z}$

$\displaystyle S = \sum_{i=1}^n \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha} (M - n_{i,\alpha}) $

$\displaystyle = M \sum_{i=1}^n \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha} - \sum_{i=1}^n \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha}^2 $

$\displaystyle = n M^2 - \sum_{i=1}^n \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha}^2 $

From Cauchy-Schwarz, with

% latex2html id marker 11798
$\displaystyle \textbf a = (n_{i,\alpha})_{\alpha \in \mathbb{F}_q} $

% latex2html id marker 11800
$\displaystyle \textbf b = (1, \ldots, 1) \in \mathbb{R}^q $

$\displaystyle \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha} \leq \left( \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha}^2 \right)^{1/2} \sqrt{q} $

So,

$\displaystyle \frac1q \left(\sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha} \right)^2 \leq \sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha}^2 $

Returning to our original equality,

$\displaystyle S \leq nM^2 - \frac{n}{q} \left(\sum_{\alpha \in \mathbb{F}_q} n_{i,\alpha} \right)^2 $

Putting everything together,

$\displaystyle dM(M-1) \leq S \leq nM^2 - \frac{n}q M^2 $

$\displaystyle dM - d \leq nM - \frac{n}q M = nM(1-\frac1q) = nrM $

$\displaystyle M \leq \left\lfloor \frac{d}{d-rn} \right\rfloor $

$ \qedsymbol$

Remarks:

  1. If $ q = 2$, the Plotkin bound can be improved (p. 59). If $ n < 2d$, then

    $\displaystyle A_2(n,d) \leq 2 \left\lfloor \frac{d}{2d - n} \right\rfloor $

  2. Asymptotic Plotkin Bound says: Let $ r = 1 - \frac1q$. Then,

    $\displaystyle \alpha_q(\delta) \leq 1 - \frac{\delta}q, \,$    if $\displaystyle 0 \leq \delta \leq r $

    $\displaystyle \alpha_q(\delta) = 0, \,$    if $\displaystyle r < \delta \leq 1 $

    The proof, for $ r < \delta \leq 1$ is to apply the usual Plotkin Bound. For $ 0 \leq \delta \leq r$, shorten enough so that usual Plotkin applies.
  3. $ A_2(2d,d) \leq 4d$ if $ d$ is even. $ A_2(2d,d) \leq 2d + 2$ if $ d$ is odd. $ A_2(2d+1,d) \leq 4d + 4$ if $ d$ is odd. These can be shown by stretching the Plotkin Bound with the simple facts learned in the previous section.


next up previous
Next: The Nordstrom Robinson Code Up: Bounds on the size Previous: and
Brian Bockelman 2005-06-29