Extended Golay Code - Vectors of Odd Weight

Question

In V(24,2) every vector of odd weight is at distance at most 3 from some code-word in $G_{24}$, the extended binary golay code.

This seems to be a known result appearing in many texts and papers, stated perhaps differently - "The extended binary golay code is a semi\quasi-perfect code", however I could not find any proof of it.

Trying to prove it on my own, I relied on the fact that $G_{23}$ is a perfect code, and that it is enough to prove it for odd weights lesser than $12$, as $G_{24}$ has the codeword 1, so the complementary weights and code-words complete the proof immediately.

For vectors of weight $1,3$ it is obvious as $G_{24}$ has the codeword 0. For vectors of weight 5, I claimed that in $G_{23}$ there is a codeword either of weight 8 with distance 3 from said vector, and then extending both the vector of weight 5 and the codeword of weight 8 by adding a 0 component will get me to a codeword in $G_{24}$ and a vector of weight 5 in V(24,2), or a codeword of weight 7 with distance 2 from said vector, and then extending the vector of weight 5 by a component 0 and the vector of weight 7 by a component 1 will lead me to a codeword of weight 8 in $G_{24}$ in distance $\le3$ from the vector of weight 5 in V(24,2).

Following the same logic, it can be shown for weights 7,9 and 11. This proof would be valid if the mapping of the vectors of weight $i$ from V(23,2) to V(24,2) was a bijection, sadly it obviously isn't so - there are far more words of weight $i$ in V(24,2), so the proof is obviously lacking. I assume it is possible to overcome this issue with the fact that $G_{23}$ can be reached from $G_{24}$ by puncturing any fixed point, yet I can't see how.

Any hints on how to overcome this issue or any other methods of proof will be extremely appreciated!

Answer 1

Summary of the comments (the question already described good ideas):

We shall use heavily the facts that

1. The Golay code $G_{23}$ is a perfect 3-error correcting code. In other words any binary vector of length 23 is at a Hamming distance $\le3$ from a uniquely determined codeword.
2. We get a code equivalent to $G_{23}$ by puncturing the extended Golay code $G_{24}$ at any of the 24 positions. This follows for example from the fact that the group of automorphisms of $G_{24}$ is transitive (it is in fact the 5-tuply transitive Mathieu group $M_{24}$, but that is overkill for the purposes of this question).

The claim is that given an odd weight binary vector $v$ of length $24$ there is a word $w\in G_{24}$ such that $d(v,w)\le3$.

Proof. Because $v$ is of an odd weight at least one of its components is $0$. Let us fix such a bit position, and puncture $G_{24}$ at that position. Let $v'$ be the resulting vector of $23$ bits. By fact 2 above the code $G_{24}'$ that we get by puncturing $G_{24}$ at this position is equivalent to $G_{23}$. By fact 1 there is a word $w'\in G_{24}'$ such that $d(v',w')\le 3$.

Let $w\in G_{24}$ be the word gotten from $w'$ by extending it (at the punctured position) with an overall parity check bit. I claim that $w$ works. Recall that all the words of $G_{24}$ have even weight. There are two cases according to the parity of the weight of $w'$.

1. If $w'$ has an even weight, then the punctured bits of both $w$ and $v$ are zero, so $$ d(v,w)=d(v',w')\le3. $$
2. If $w'$ has an odd weight, then the puncture bit of $w$ is a one, so $$ d(v,w)=1+d(v',w'). $$ At first sight it may look like we have a problem in that this Hamming distance may be too large. But recall that in this case both $v'$ and $w'$ have an odd weight, so their Hamming distance must be even. Thus $d(v',w')\le2$, and the claim follows in this case as well. Q.E.D.

---

It is good to play with arguments like above so that they become second nature. This type of reasoning involving extending/puncturing/shortening a binary code comes up frequently.