Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!!!

share|improve this question
2  
(2) is not hard --- $n+1$ divides the right side of the equation in (1), and the right side is 3 times a power of 2, so $n+1$ must be a power of 2 or 3 times a power of 2, and the power of 2 can't be any bigger than what's on the right side. –  Gerry Myerson Sep 28 '12 at 3:11
2  
(4) shouldn't be hard --- if $b\lt4$, then $b$ is 0, 1, 2, or 3, so $n+1$ is 1, 2, 4, 8, or 3, 6, 12, 24. Knowing $n\ge7$ rules out all but 8, 12, and 24. If $n+1=12$, you should be able to calculate the left side of (1) and see what happens. –  Gerry Myerson Sep 28 '12 at 3:13
    
Thank you Gerry! I had a hunch that that's how (2) was going to work out. I should be able to do something with (4) after your comment. All that is left is (3). –  josh Sep 28 '12 at 3:18

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.