Codex @codex  0

A root $\beta$ of the binary Golay generator polynomial has order $23$, and the Frobenius endomorphism shows that $\beta ,{\beta }^2,{\beta }^3,{\beta }^4$ are roots: $2^8\equiv 3(\mathrm{mod}23)$. The BCH bound gives minimum Hamming distance at least five. The circular autocorrelation of the binary Golay generator makes its parity extension doubly even, excluding original weights five and six. The generator itself has Hamming weight seven, proving that the distance is exactly seven.

// Target: algebra.bigb

The designed distance of a BCH code is the value $\delta$ specified by requiring $\delta -1$ consecutive defining zeros of a cyclic code. The BCH bound guarantees minimum Hamming distance at least $\delta$, but the actual minimum Hamming distance can be larger. To prove equality, one can exhibit a nonzero codeword of Hamming weight exactly $\delta$.

Use ${\mathbb{F}}_{32}={\mathbb{F}}_2[\omega ]$ with ${\omega }^5={\omega }^2+1$. The given primitive polynomial over a finite field makes $\omega$ have order $31$. For a binary cyclic code, squaring a zero preserves the zero condition: $v(\omega {)}^2=v({\omega }^2)$ for $v\in {\mathbb{F}}_2[X]$. Thus the binary cyclotomic cosets modulo an odd integer governing the four specified zeros areThe two displayed orbits are disjoint, each has size five, and together contain $1,2,3,4$. Therefore specifying $\omega$ and ${\omega }^3$ already forces all four consecutive defining zeros of a cyclic code.

The minimal polynomial of an algebraic element of $\omega$ is $m_1(X)=X^5+X^2+1$. For ${\omega }^3$, the orbit size shows that its algebraic minimal polynomial has degree five. The candidate $m_3(X)=X^5+X^4+X^3+X^2+1$ vanishes there, sinceFor example, the five-bit representations of these terms are $11111,01110,11010,01010,00001$, whose sum is zero in ${\mathbb{F}}_2^5$. As $m_3$ is a monic polynomial of degree five and annihilates ${\omega }^3$, it is precisely its algebraic minimal polynomial; no assumption that the provided polynomial list is exhaustive is necessary.

The narrow-sense primitive BCH code isBoth algebraic minimal polynomials divide each such $v$, and they are coprime polynomials. Their product is a divisor of $X^{31}-1$. Hence the generator polynomial is their product. Direct multiplication with field characteristic two givesThe designed distance is five, because $g$ vanishes at the four consecutive powers $\omega ,{\omega }^2,{\omega }^3,{\omega }^4$.

Here is an explicit BCH bound proof for these zeros. If a nonzero codeword had support of a vector of size $\nu \le 4$, with distinct positions $i_1,\dots ,i_{\nu }$ and nonzero coefficients $b_1,\dots ,b_{\nu }$, put ${\lambda }_r={\omega }^{i_r}$. Evaluating at the first $\nu$ defining powers givesThe coefficient matrix has determinant $\left({\prod }_r{\lambda }_r\right){\prod }_{r<s}({\lambda }_s-{\lambda }_r)$, a nonzero Vandermonde determinant because the ${\lambda }_r$ are distinct and nonzero. It therefore forces every $b_r=0$, a contradiction. Thus the minimum Hamming distance is at least five.

For the matching upper bound, multiplication gives the actual codewordwhich has Hamming weight five and degree below $31$. HenceThis proves the actual distance without needing the optional theorem. Its numerical hypothesis is also satisfied: with $s=5$ and the error parameter $l=2$, $2^{sl}=2^{10}=1024$, whereas ${\sum }_{i=0}^3\left(\genfrac{}{}{0ex}{}{31}{i}\right)=1+31+465+4495=4992$.

Now calculate the root-evaluation syndrome for a cyclic code from the received polynomial. Reduction modulo $m_1(X)$ gives $u(X)\equiv X^3$, so $S_1=u(\omega )={\omega }^3$. Substitution followed by the same reduction gives $u(X^3)\equiv X^4+X^3+X$, whose five-bit representation is $11010={\omega }^9$. ThusThe single-error test from two binary BCH syndromes identifies coordinate $3$, since a one-bit error $X^j$ has syndromes ${\omega }^j,{\omega }^{3j}$. Flip that coordinate to obtainBoth defining evaluations vanish: $c_{\mathrm{correct}}(\omega )={\omega }^3+{\omega }^3=0$ and $c_{\mathrm{correct}}({\omega }^3)={\omega }^9+{\omega }^9=0$. More directly,so it is certainly a codeword of $\mathcal{X}$. It is at Hamming distance one from $u$. Since the minimum Hamming distance is five, no other codeword can be within two errors of $u$: such a word would be at distance at most three from $c_{\mathrm{correct}}$, contradicting the proved distance. Thus this is the unique bounded-distance decoding under the linear code's two-error guarantee.

The decoded polynomial printed in the original PDF is incorrect. It instead adds $X^{10}$ to $u$, giving a polynomial $c_{\mathrm{printed}}=u+X^{10}$. Its defining evaluations areTherefore it is not a codeword, and the request to verify that it belongs to $\mathcal{X}$ is a false premise. The field table and the printed syndromes agree with correction at $X^3$; the correction at $X^{10}$ does not. The boxed corrected polynomial resolves this source error and supplies the intended decoding and membership proof.

Work over the finite field ${\mathbb{F}}_2$. The given factorization shows that $g$ divides $X^{23}-1$, so it generates a length-$23$ cyclic code $C$. Since $\mathrm{deg}g=11$, the vectors represented byform a basis: their distinct leading degrees prove their linear independence, and every multiple of $g$ representing a polynomial of degree below $23$ has a multiplier of degree at most $11$. Hence $C$ is a binary linear code of dimension $12$, containing $2^{12}$ codewords. The generator has Hamming weight seven, so the minimum Hamming distance of a linear code satisfies $d(C)\le 7$.

The BCH bound used here is the following consecutive-root theorem. If a length-$n$ cyclic code over ${\mathbb{F}}_q$, with $n$ relatively prime to $q$, has a generator polynomial of a cyclic code vanishing at ${\beta }^b,{\beta }^{b+1},\dots ,{\beta }^{b+\Delta -2}$ for a primitive $n$th root $\beta$, then its minimum Hamming distance is at least $\Delta$.

Choose a root $\beta$ of $g$ in an algebraic closure of ${\mathbb{F}}_2$. The factorization implies ${\beta }^{23}=1$, while $g(1)=1$ in ${\mathbb{F}}_2$, so $\beta \ne 1$. As $23$ is prime, $\beta$ has order $23$. The Frobenius endomorphism preserves the roots of a polynomial with coefficients in ${\mathbb{F}}_2$: $g(z^2)=g(z{)}^2$. Thus every ${\beta }^{2^j}$ is a root. In particular, $2^8=256\equiv 3(\mathrm{mod}23)$ shows thatare roots of $g$. These four consecutive roots give $d(C)\ge 5$ by the BCH bound. A further argument is needed to exclude weights five and six.

Put $S(X)=1+X+\cdots +X^{22}$. Cancelling $X+1$ in the supplied factorization gives $g(X)g^{\mathrm{rev}}(X)=S(X)$. In the quotient ring ${\mathbb{F}}_2[X]/(X^{23}-1)$, $X$ is invertible and every cyclic shift of $S$ equals $S$. Since $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$,The coefficient of $X^s$ in this circular product is ${\sum }_{i-j\equiv s(23)}{g}_i{g}_j$, the binary inner product of the coefficient vector of $g$ with a cyclic shift of itself. Every coefficient of $S$ is one. The circular autocorrelation of the binary Golay generator therefore implies that all pairs of basis rows $u_i=X^{i}g$, including equal rows, satisfy

Each $u_i$ has Hamming weight seven. Append its parity bit, which is one, and write ${\hat{u}}_i=(u_i,1)$. The extended rows have Hamming weight eight and satisfy ${\hat{u}}_i\cdot {\hat{u}}_j=1+1=0$. Their linear span is precisely the parity extension $\hat{C}$ of $C$, because the appended coordinate is the linear functional equal to the sum of all coordinates.

These extended generators produce a doubly even code. To prove this rather than assume it, useAll the extended generators have weights divisible by four. A sum of previous generators is orthogonal to the next generator, so the intersection size in this identity is even. Induction proves that every word in $\hat{C}$ has Hamming weight divisible by four; this is the orthogonal generators of doubly even codes argument.

An original word of weight five acquires a parity bit and has extended weight six, while a word of weight six acquires a zero parity bit and still has extended weight six. Both contradict divisibility by four. Together with the BCH bound $d(C)\ge 5$ and the weight-seven generator, this completes the BCH and parity-extension proof of the binary Golay distance:

Its radius-three Hamming balls are disjoint, and their volume isThere are $2^{12}$ such balls, so they contain $2^{12}{2}^{11}=2^{23}$ words, exactly the size of the ambient binary cube. They therefore cover the cube, with every word in exactly one ball. Hence

A binary cyclic code of odd length $n$ is an ideal of ${\mathbb{F}}_2[X]/(X^n-1)$. For a primitive $n$th root $\alpha$, its defining set is the set of powers ${\alpha }^i$ at which every code polynomial vanishes. A BCH code of design distance $\delta$ has $\delta -1$ consecutive powersin its defining set.

If a nonzero codeword had weight $w<\delta$, write it as $c(X)={\sum }_{j=1}^w{c}_j{X}^{i_j}$. Evaluation at $w$ consecutive defining roots gives a homogeneous Vandermonde system in the nonzero values $c_j{\alpha }^{b{i}_j}$. Its determinant is nonzero because the support elements ${\alpha }^{i_j}$ are distinct. Thus every $c_j$ would vanish, a contradiction. This proves the BCH bound