What about $[n,k,7]$ binary perfect code? (Exercise from the book Fundamentals of Error Correcting Codes)

Question

I'm trying to solve an exercise from the book Fundamentals of Error Correcting Codes, can somebody help me? The problem is the following:

Let $C$ be an $[n, k, 7]$ perfect binary code.

(a) Using equality in the Sphere Packing Bound, prove that

$$(n+1)[(n+1)^2 −3(n+1)+8]=3·2^{n−k+1}.$$

(b) Prove that $n+1$ is either $2^b$ or $3·2^b$ where, in either case, $b≤n−k+1$.

(c) Prove that $b < 4$.

(d) Prove that $n=23$ or $n=7$.

(e) Name two codes that are perfect $[n, k, 7]$ codes, one with $n = 7$ and the other with $n = 23$.

For part a) I could easily prove the claim :) For part b) I answered in the following way:

From part a) we know $n+1=(3·2^{n−k+1})/(n^2-n+6)$, so since $n$ is a natural number, then so is $n+1$ and thus we can consider three cases:
1) $(n^2-n+6)$ divides $3$ (it does not divide $2^{n-k+1}$) -> $n+1=2^{n-k+1}$ OK

2) $(n^2-n+6)$ divides both $3$ and $2^{n-k+1}$ -> $n+1=2^b$ with $b<=n-k+1$ OK

3) $(n^2-n+6)$ divides $2^{n-k+1}$ (it does not divides $3$) -> $n+1=3·2^b$ with $b<=n-k+1$ OK

I'm really not sure if it's enough to prove the claim or if there is some "more mathematically" proof. any suggestion?

For part c) I'm completely lost. I cannot find a way to prove that $b<4$. (I tried to use the information that $C$ is a perfect code. but I'm stuck!) & also for part d) & e) I need any suggestions.

Answer 1

The starting point is the identity (your part a) gotten by having an equality in the sphere packing bound $$(n+1)[(n+1)^2 −3(n+1)+8]=3·2^{n−k+1}.\qquad(*)$$

• Equation $(*)$ tells us that $n+1$ is a factor of the integer $3\cdot 2^{n-k+1}$. By the uniqueness of integer factorization it follows that $n+1=3^\epsilon\cdot 2^b$ with $\epsilon\in\{0,1\},0\le b\le n-k+1$. This settles part (b).
• Assume that $b\ge4$. It follows that both $(n+1)^2$ and $-3(n+1)$ are divisible by $2^4$. A key observation is that the third term, $+8$, in square brackets is not. This means that the quantity in square brackets is divisible by $8$ but is not divisible by $16$. Let's take advantage by writing $(n+1)=16m$, $m$ a positive integer. Then $$[(n+1)^2-3(n+1)+8]=256m^2-48m+8=8(32m^2-6m+1).$$ Here the factor $32m^2-6m+1$ is an odd integer $\ge27$. But the integer $3\cdot2^{n-k+1}$ has no odd factors larger than $3$, so this contradicts $(*)$. Therefore $b\in\{0,1,2,3\}$.
• If $b=0$ or $b=1$ then $n+1=3^\epsilon\cdot2^b<7$ making it obvious that a code of length $n$ cannot have minimum distance $7$. If $b=2$ then $n+1=4\cdot3^{\epsilon}$ is either $4$ or $12$. The former is similarly impossible. If $n+1=12$ then $(n+1)^2-3(n+1)+8=116=2^2\cdot29$ violating $(*)$. Therefore the only possibility is $b=3$, when either $n+1=2^3=8$ or $n+1=3\cdot2^3=24$.
• It is possible that $n+1=8$ for the repetition code of length $7$ is perfect. Similarly, $n+1=24$ is possible, as the binary Golay code of length $23$ is a perfect code with minimum distance $7$.