I've been working on exercises from various textbooks to get a better understading about perfect codes. There is a theorem that states:
Theorem: The only nontrivial perfect multiple error-correcting codes that have the same length, number of codewords, and minimum distance are either the $[23, 12, 7]$ binary Golay code or the $[11, 6, 5]$ ternary Golay code.
In order to help the reader prove this theorem, the book breaks the theorem into 4 parts. They are as follows:
Let $\mathcal{C}$ be an $[n, k, 7]$ perfect binary code:
(1) Using the Sphere Packing Bound, show that
$$(n+1)[(n+1)^2 – 3(n+1) + 8] = 3 \cdot 2^{n – k + 1}.$$
(2) Show that $n+1$ is either $2^b$ or $3 \cdot 2^b$, where in either case, $b \leq n – k + 1.$(3) Show that $b < 4$.
(4) Show that $n = 23$ or $n = 7$.
I am able to show (1), but I am having difficulty showing (2) – (4). I have a feeling that there is some number theory involved with prime numbers, but I'm not seeing it. Furthermore, since this is an $[n, k, 7]$ code, I know that $n \geq 7$
I would love to finish the proof to this theorem since it's stated in many textbooks without proof. Any help would be greatly appreciated!
EDIT
With the help of Gerry from the comments, (2) and (4) work out easily. For (2), it follows from (1) that $(n+1) | 3 \cdot 2^{n – k + 1}$. Therefore, $(n+1)$ must be of the form $2^b$ or $3 \cdot 2^b$, and since these powers of 2 cannot be bigger than the power of 2 on the right hand side, it follows that $b \leq n – k + 1$. For (4), it follows from (3), and the fact that $n \geq 7$ that $n = 7, 11,$ or $23$. If we plug these values into (1) it follows that: $n = 7 \Rightarrow 2^k = 2 \Rightarrow k = 1$, $n = 11 \Rightarrow 2^k = 8.827\ldots, $ $n = 23 \Rightarrow 2^k = 4096 \Rightarrow k = 12$. Therefore, $n = 7$ or $n = 23$.
Any help with (3) be greatly appreciated!!!
Best Answer
Let's see if this works for (3). If $b\ge4$, then $(n+1)^2-3(n+1)+8$ is divisible by $2^3$ but not by any higher power of 2. On the other hand, it's at least $16^2-(3)(16)+8=216$ so when you divide it by 8 you get an odd number that's at least 27. But the right side of (1) isn't divisible by any odd number exceeding 3, contradiction.