A proof on the minimum distance of Golay code

313 Views Asked by At

I was trying to prove the minimum distance of binary Golay code generated by the polynomial

$$P(x)=x^{11}+x^{10}+x^6+x^5+x^4+x^2+1$$

over $\mathbb{F}_2$ is $\geq 7$, and I figured out a proof below.

Proof. Let $\alpha$ be a root of $P$ over its splitting field. We know that $\alpha^{23}=1$. If a code word with weight $<7$ exists, then the polynomial defined over $\mathbb{F}_2$

$$Q(x)=x\prod_{0\leq i\leq 22}(x-\alpha^i)\prod_{0\leq i<j\leq 22}(x-(\alpha^i+\alpha^j))\prod_{0\leq i<j<k\leq 22}(x-(\alpha^i+\alpha^j+\alpha^k))$$

must have a multiple root.

The splitting field of $P$ is a field with characteristic $2$. So each root of $Q$ is a root of polynomial $$R(x)=x^{2^{11}}-x.$$

Both $Q$ and $R$ are defined over $\mathbb{F}_2$, and $R$ contains all the roots of $Q$(counting multiplicities?) over the splitting field of $P$. The degree of $Q$ is $${23\choose 0}+{23\choose 1}+{23\choose 2}+{23\choose 3}=2^{11},$$ which leads to $Q=R$. $R$ does not have a root with multiplicity $>1$, and we are done.

Question: I don't think I have ever seen such a proof in the textbooks, and I am not sure if this proof is flawless. Is there any gap in this proof? Thank you for your help.

1

There are 1 best solutions below

0
On

I realized that the proof can be completed with the same technique in the comment. I will outline a proof below.

  1. The coefficients of the polynomial $Q$ are symmetrical functions of the 23 roots of the equation $x^{23}=1$ over $\mathbb {F}_{2^{11}},$ so $Q$ is defined on $\mathbb{F}_2$.
  2. $Q(x)/x$ is invariant under the transformation $x\mapsto \alpha x$, suggesting $Q=xT(x^{23})$ where $T$ is a polynomial over $\mathbb{F}_2$ of degree $89$.
  3. $T(x)$ vanishes at $x=1,(1+\alpha)^{23},(1+\alpha+\alpha^2)^{23},\\(1+\alpha+\alpha^3)^{23},(1+\alpha+\alpha^4)^{23},\\(1+\alpha+\alpha^5)^{23},(1+\alpha^2+\alpha^3)^{23},\\(1+\alpha^2+\alpha^5)^{23},(1+\alpha^3+\alpha^4)^{23}.$

Minimal polynomials (over $\mathbb{F}_2$) of these zeros are the 9 different irreducible factors of $x^{89}-1$ over $\mathbb{F}_2$, which forces $T(x)=x^{89}-1$, and we are done.