# Proving that $A_2(13,7) = 8$

It is not too difficult to find a binary code consisting of $8$ words, each $13$ bits long, keeping the distance between every pair of words at least $7$. I know it is not possible to find $9$ words with that property, but I could not prove it. Can anybody please help me?

-
Can you prove that the 8 word code is unique up to equivalence, i.e. linear? Then the claim would follow from Griesmer bound, because 3 is obviously a maximum dimension of a code of length 13 and minimum distance 7 (and the existence of a 9 word code would actually imply the existence of a 16 word code). What does the linear programming bound (=McEliece-Rodemich-Rumsey-Welch bound) tell in this case? – Jyrki Lahtonen Aug 7 '12 at 17:46

## 1 Answer

You can use the Plotkin bound.

ii) If $d$ is odd and $2d+1>n$, then $$A_2(n,d) \le 2 \left\lfloor \frac{d+1}{2d+1-n} \right\rfloor.$$

$d=7$ is odd and $2d+1 = 2 \cdot 7 + 1 = 15 > 13$, so

$$A_2(13,7) \le 2 \left\lfloor \frac{7+1}{2 \cdot 7 + 1 - 13} \right\rfloor = 8.$$

You said you already have an example of a binary code of size 8, length 13, and minimum distance 7, so this proves that $A_2(13,7) = 8$.

-
+1 Well done! Criminal of me to forget about Plotkin. My excuse is that all my coding theory books were in moving crates, but... – Jyrki Lahtonen Aug 30 '12 at 15:23