enumerator weight polynomial of Golay code

Question

Let $C$ be a code and let $X_{i}=| \lbrace x\in C : w(x)=i \rbrace|$, where $w(x)$ denotes the weight of $x\in C$. I would like to know how to compute the numbers $X_{i}$, in the particular case where $C=G_{24}$, the extended Golay code.

Any help will be much appreciated. Thank you

Answer 1

In general the question is very difficult. If all you know is the generator matrix of a code, then proving that its minimum distance is below a given number is IIRC NP-hard or something like that.

With the extended Golay code OTOH it is easy. For one it has only $4096$ codewords, so a computer-aided brute force will give you the answer easily. The method I would use depends on how the Golay code was described. If, for example, you have been given a generator matrix, and know that the minimum distance is $8$, then you can first observe that

• The code is self-dual.
• All the generators have weights that are multiples of four.
• Using this you can show easily by induction on the number of generators used that any word has weight divisible by four.
• Also you can tell that the all $1$s word of weight $24$ is there.

At this point we already know that only weights $0,8,12,16$ and $24$ occur, and that as a consequence of complementation the words of respective weight $8$ and $16$ are equal in number. So if we can figure out, $M$, the number of words of weight $8$ we are done.

The weight enumerator is thus $$ W(x,y)=x^{24}+Mx^{16}y^8+(4094-2M)x^{12}y^{12}+Mx^8y^{16}+y^{24}. $$ By MacWilliam's identity we know that the weight enumerator of the dual code is $$ \frac1{4096}W(x+y,x-y). $$ The key is that self-duality imposes the condition that $4096W(x,y)=W(x+y,x-y)$. We can calculate the coefficient of $x^{22}y^2$-term in $W(x+y,x-y)$ (a CAS is handy here, but doing it by hand is not too arduous either), and see that it is $(64M-48576)$. Because the code is self-dual, we know that the dual code has no words of weight two, so we get $$ 64M-48576=0 $$ which implies $M=759$. Thus we get $$ W(x,y)=x^{24} + 759 x^{16} y^8 + 2576 x^{12} y^{12} + 759 x^8 y^{16} + y^{24} $$ telling us that the extended Golay code has $759$ words of weights $8$ and $16$, $2576$ words of weight $12$, and a single word of weight $0$ and $24$.

The same result is immediate from Gleason's theorem on the weight enumerators of doubly even self-dual binary linear codes. That theorem leaves only a single possibility for the weight enumerator of a self-dual doubly even binary linear code of length $24$ and minimum distance $>4$.

There are more combinatorial ways of finding the number of weight 8 words, but may be this will do for now?