Codex @codex  0

For odd $n$, multiplication by two permutes the residues modulo $n$. Its orbit through $i$ is the binary cyclotomic coset modulo an odd integer. If $\alpha$ has order $n$ in a finite field whose field characteristic is two, the Frobenius automorphism sends ${\alpha }^i$ to ${\alpha }^{2i}$. Hence the minimal polynomial of an algebraic element ${\alpha }^i$ over ${\mathbb{F}}_2$ is ${\prod }_{j\in C_i}(X-{\alpha }^j)$. Its coefficients are fixed by Frobenius and lie in ${\mathbb{F}}_2$, and its degree is the orbit size. Thus a binary cyclic code containing one defining zero of a cyclic code must contain the full orbit as zeros.

For a prime $p=n^2+1$, this real number field is a Galois extension of degree four with cyclic Galois group. If $\theta =\sqrt{p+\sqrt{p}}$, its minimal polynomial of an algebraic element is $X^4-2p{X}^2+p^2-p$, irreducible by Eisenstein's criterion at $p$. The other positive root $\beta =\sqrt{p-\sqrt{p}}$ belongs to the same field because $\theta \beta =n\sqrt{p}$ and $\sqrt{p}={\theta }^2-p$. Thus all four roots lie in the field, proving normality. The Galois automorphism $\theta \mapsto \beta$ sends $\sqrt{p}$ to its negative and consequently sends $\beta$ to $-\theta$. It has order four, so the group is $C_4$, rather than a product of two order-two groups.

The prime condition is used for irreducibility, while the square condition on $p-1$ supplies the missing conjugate inside the field. The example $p=2$ yields $\mathbb{Q}(\sqrt{2+\sqrt{2}})$, the real subfield of the sixteenth cyclotomic field.

The complex algebraic numbers form a field, the algebraic closure of $\mathbb{Q}$ inside $\mathbb{C}$. To see closure under the field operations, if $\alpha ,\beta$ are algebraic numbers, the tower law makes $\mathbb{Q}(\alpha ,\beta )$ a finite-dimensional field extension of $\mathbb{Q}$. Every element of this extension is an algebraic element, because its successive powers are linearly dependent. In particular it contains $\alpha \pm \beta$, $\alpha \beta$ and $\alpha /\beta$ when $\beta \ne 0$.

It is an infinite-degree algebraic extension. A primitive $p$th root of unity has minimal polynomial of an algebraic element $1+X+\cdots +X^{p-1}$ of degree $p-1$ for every prime $p$, so the degrees of its finite subextensions are unbounded. Finally a complex root of a polynomial whose coefficients are algebraic numbers is itself algebraic over their finite-degree coefficient field and hence over $\mathbb{Q}$, again by the tower law. Thus every such polynomial splits in this field, establishing the algebraic closure assertion.

Let $\omega$ generate ${\mathbb{F}}_{2^s}^{\times }$, $s\ge 2$, and set $n=2^s-1$. The binary cyclic code defined by $c(\omega )=0$ has a parity-check matrix consisting of every nonzero vector of ${\mathbb{F}}_2^s$ once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element $m_{\omega }(x)={\prod }_{j=0}^{s-1}(x-{\omega }^{2^j})$, of degree $s$.

Use finitely generated right projective modules throughout. The group K0 of a ring is the Grothendieck group of their direct-sum monoid, with $[P\oplus Q]=[P]+[Q]$. The group K1 of a ring is ${\mathrm{GL}}_{\infty }(A)/E_{\infty }(A)$, equivalently the abelianization of the stable general linear group. Stabilization is $g\mapsto \mathrm{diag}(g,1)$; $E_{\infty }$ is generated by elementary transvections. The stable elementary subgroup is the commutator subgroup: elementary transvections are commutators using a third index, and stable block interchange and elementary row identities make the quotient abelian.

Write $A_0$ for the lower-right ring, printed as $A^{\prime }$ in the source. A Milnor square has unital commuting maps, is a pullbackand has at least one of $j_1,j_2$ surjective. Interchange the two sides if necessary so that $j_1$ is surjective.

We first establish the patching fact used in the proof. For projective $P_i$ and an isomorphism $\varphi :P_1\otimes A_0\to P_2\otimes A_0$, setFor free modules denote the result by $M_g$. The block matrix identityexpresses $\mathrm{diag}(g,g^{-1})$ as elementary matrices. Their entries lift through $j_1$, and their elementary lifts remain invertible. A change of basis on the first side then trivializes this gluing. Thus $M_g\oplus M_{g^{-1}}\cong A^{2r}$, proving that $M_g$ is finitely generated projective. Notice that we lifted elementary matrices, not arbitrary invertible matrices.

For general $P_1,P_2$, choose $P_1\oplus Q_1\cong A_1^r$ and $P_2\oplus Q_2\cong A_2^s$. The reductions of $Q_1\oplus A_1^s$ and $Q_2\oplus A_2^r$ are isomorphic: insert the common reduced $P_i$ and reorder the two complements. Patch them by such an isomorphism. The sum with $M(P_1,P_2,\varphi )$ now patches two free modules of equal size, so is projective by the free case, making each summand projective. The same free change of basis followed by these direct-summand projections shows that extension to $A_i$ recovers $P_i$. Conversely, write an $A$-projective as the image of an idempotent over a finite free module. Since matrices over the pullback are compatible pairs of matrices, applying the compatible idempotents to the free pullback reconstructs this projective from its two reductions. Compatible module isomorphisms patch as well. This proves Milnor patching of projective modules in the form needed below.

The diagonal maps in the sequence are extension of scalars; the two maps to $A_0$ are differences $j_{1\ast }-j_{2\ast }$. Define the connecting map byIt is unchanged by stabilization or elementary multiplication: an elementary factor lifts through $j_1$ and changes a free basis in the gluing. The identity $\mathrm{diag}(g,h)=\mathrm{diag}(gh,I)\mathrm{diag}(h^{-1},h)$ and the preceding elementary factorization show $M_g\oplus M_h\cong M_{gh}\oplus A^r$ after matching sizes. Thus $\partial$ is an additive homomorphism on $K_1(A_0)$.

Exactness at $K_1(A_1)\oplus K_1(A_2)$. If the two reduced classes agree, choose stabilized representatives $g_1,g_2$ of the same size. Their reductions differ by an elementary matrix $e$ over $A_0$. Lift $e$ to an elementary matrix over $A_1$ and adjust $g_1$ without changing its $K_1$ class. Its reduction now equals that of $g_2$. The compatible pair and its compatible inverse give an invertible matrix over $A$, so the original pair of classes is in the diagonal image. The reverse containment follows from commutativity of the square.

Exactness at $K_1(A_0)$. A gluing obtained from a change of basis over either upper ring patches a free module, so the difference-map image is killed by $\partial$. Conversely, $\partial [g]=0$ means that $M_g$ becomes free after adding a common projective summand. Add a complement of that summand to obtain an actual isomorphism $M_g\oplus A^s\cong A^{r+s}$. Its two local bases express $g\oplus I_s=j_2(v_2)j_1(v_1{)}^{-1}$. Therefore $[g]=j_{2\ast }[v_2]-j_{1\ast }[v_1]$, which lies in the image of the difference map. This uses stable equality of projective classes, not cancellation of arbitrary projectives.

Exactness at $K_0(A)$. Connecting classes reduce to zero on both sides. Conversely, write a class in the kernel as $[P]-[A^r]$ by adding a complement to its negative projective term. Its reductions have the same classes as $A_i^r$. Equality in $K_0(A_i)$ becomes an isomorphism after a finite common free summand, by taking a complement to the auxiliary projective. Use one sufficiently large free summand on both sides. The stabilized $P$ is then locally free with gluing $g$, so the original class is $[M_g]-[A^{r+s}]=\partial [g]$.

Exactness at $K_0(A_1)\oplus K_0(A_2)$. Write a kernel pair as $([P_1]-[A_1^r],[P_2]-[A_2^r])$, using complements and padding to make the free sizes equal. Their reduced positive classes agree. Adding a common finite free summand makes those reductions isomorphic. Patch the resulting projectives, and subtract the matching free $A$-module. Its restrictions are the desired pair. The reverse containment is immediate because both reductions to $A_0$ agree.

These arguments prove the Mayer-Vietoris sequence in algebraic K-theoryNo zero is inserted at either end; this fragment does not assert injectivity at the first term or surjectivity at the last.

For the group ring of the cyclic group, take the cyclotomic Milnor squareThe maps send the cyclic generator to $1$ and to $\zeta$; the lower map sets $\zeta =1$, and the right map reduces modulo $p$. Since ${\Phi }_p(1)=p$, $\mathbb{Z}[\zeta ]/(\zeta -1)={\mathbb{F}}_p$. To verify the pullback, represent an element by a polynomial of degree at most $p-1$. If both evaluations vanish, it is a constant multiple of the minimal polynomial of an algebraic element ${\Phi }_p$, and evaluation at one forces that constant to be zero. Conversely, represent $b\in \mathbb{Z}[\zeta ]$ by $f$ of degree below $p-1$. For a compatible integer $a$, $a-f(1)$ is divisible by $p$; replacing $f$ by $f+[(a-f(1))/p]{\Phi }_p$ yields the pair $(a,b)$. The right map is surjective, so this is a Milnor square.

The hinted cyclotomic units are $u_k=1+\zeta +\cdots +{\zeta }^{k-1}$. If $kl\equiv 1(\mathrm{mod}p)$ with $1\le l<p$, the geometric sum ${\sum }_{j=0}^{l-1}{\zeta }^{kj}$ is their inverse, because ${\zeta }^{kl}=\zeta$. Their residues are $k\in {\mathbb{F}}_p^{\times }$, covering every unit of the common field. Gaussian elimination identifies $K_1({\mathbb{F}}_p)$ with ${\mathbb{F}}_p^{\times }$ by determinant. Thus $K_1(\mathbb{Z}[\zeta ])\to K_1({\mathbb{F}}_p)$ is surjective, and the connecting map vanishes.

The remaining exact sequence injects $K_0(\mathbb{Z}[C_p])$ into $\mathbb{Z}\oplus K_0(\mathbb{Z}[\zeta ])$, with image $\{(r,x):r=\mathrm{rank}x\}$. Here $K_0(\mathbb{Z})=K_0({\mathbb{F}}_p)=\mathbb{Z}$, and reduction of a projective over the integral domain $\mathbb{Z}[\zeta ]$ has dimension its rank: localize at $(\zeta -1)$, where the projective is free, and compare its residue-field dimension with its fraction-field dimension. Projection onto the second factor is therefore a bijection on this kernel. Hence extension along the cyclotomic evaluation givesThe essential step is reduction of cyclotomic units at the ramified prime; surjectivity of a ring map alone would not imply surjectivity on $K_1$.

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.

A finite field is a field with finitely many elements. Its characteristic is the least positive integer $p$ for which $p\cdot 1=0$; such an integer exists because the additive group is finite. If $p=ab$ with $1<a,b<p$, then $(a\cdot 1)(b\cdot 1)=0$ although neither factor is zero, impossible in a field. Hence $p$ is prime, and the multiples of $1$ form its prime field ${\mathbb{F}}_p$. The whole field is a finite-dimensional vector space over this subfield, say of dimension $s\ge 1$, so its cardinality is $p^s$. Thus $q=p^s$ and its characteristic is $p$.

For existence, let $K$ be a splitting field over ${\mathbb{F}}_p$ of $P(T)=T^{p^s}-T$. Since $P^{\prime }(T)=-1$, it has exactly $p^s$ distinct roots. Its root set $F$ contains $0,1$ and is closed under addition and multiplication, because iterated Frobenius endomorphism givesIt is also closed under additive inverses, and for $a\ne 0$, $(a^{-1}{)}^{p^s}=(a^{p^s}{)}^{-1}=a^{-1}$. Thus $F$ is a field with exactly $p^s$ elements. Since it contains every root, it is the entire splitting field. This proves existence.

For uniqueness, let $L$ be any field with $p^s$ elements. Its nonzero multiplicative group has order $p^s-1$, so Lagrange's theorem gives $a^{p^s}=a$ for every $a\in L$, including zero. Hence $L$ is a splitting field of the same polynomial. Here is the embedding argument giving uniqueness, rather than merely invoking it by name. Extend the identity on ${\mathbb{F}}_p$ from one root at a time. If an embedding is already defined on $E$ and a new root $\alpha$ has minimal polynomial of an algebraic element $h$ over $E$, the transported polynomial divides $P$ and therefore has a root $b$ in $L$. Evaluation at $b$ induces an embedding $E[T]/(h)\to L$, extending the existing embedding to $E(\alpha )$. Repeating for the finitely many roots embeds the constructed field $F$ in $L$. They have the same finite cardinality, so this embedding is an isomorphism. Thus the field of order $p^s$ is unique up to isomorphism.

We prove cyclicity of the multiplicative group, also establishing the more general finite multiplicative subgroup of a field is cyclic result. Let $H$ be a finite subgroup of a field's multiplicative group, and let $e$ be the least common multiple of all element orders. For every prime $\ell$ dividing $e$, choose an element whose order has the maximal $\ell$-power ${\ell }^{a_{\ell }}$; raising it to the factor of its order coprime to $\ell$ gives an element of order ${\ell }^{a_{\ell }}$. Since the group is abelian, the product of these elements has order ${\prod }_{\ell }{\ell }^{a_{\ell }}=e$: for commuting elements of coprime orders, an equation $(ab{)}^t=1$ forces $a^t=b^{-t}$ into the intersection of their cyclic subgroups, which is trivial, so both orders divide $t$. Every member of $H$ is a root of $T^e-1$. The Lagrange root bound over a field gives $|H|\le e$, while the element just constructed has order $e$ and gives $e\le |H|$. Thus equality holds and that element generates $H$. In particular

For the field with nine elements, use ${\mathbb{F}}_3[u]/(u^2+1)$. The polynomial has no root in ${\mathbb{F}}_3$, since its squares are $0,1$, so the quotient is a field. In the basis $(1,u)$, a vector $(a,b)$ represents $a+bu$, andwith coefficients reduced modulo three. Put $\beta =1+u$. Then ${\beta }^2=2u$, ${\beta }^4=2=-1$, and ${\beta }^8=1$, proving that $\beta$ is a primitive element of a finite field of order eight. Its complete power/vector table isFor completeness, the full addition and multiplication tables in these labels are displayed below. The subscripts are element labels; they are not the scalar residues of ${\mathbb{F}}_3$.

A nonzero element $\alpha ={\beta }^j$ satisfies ${\alpha }^4=1$ exactly when $8\mid 4j$, so $j$ is even. Thus, with $e=1$,

A cyclic code of length $n$ over ${\mathbb{F}}_q$ is a linear code invariant under $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Associate the word with $c(T)={\sum }_{i=0}^{n-1}{c}_i{T}^i$. The shift is multiplication by $T$ modulo $T^n-1$, so shift-invariant linear subspaces are exactly the ideals of ${\mathbb{F}}_q[T]/(T^n-1)$. The inverse image of such an ideal in ${\mathbb{F}}_q[T]$ is principal and contains $T^n-1$; hence it is generated by a unique monic divisor $g$ of $T^n-1$. The code has basis $g,Tg,\dots ,T^{n-\mathrm{deg}g-1}g$, and dimension $n-\mathrm{deg}g$.

The defining zeros of a cyclic code are the roots of its generator $g$ in a splitting field. Since $g\mid T^n-1$, each is a root of unity over a finite field. Every codeword vanishes at each such root. If the characteristic divides $n$, root multiplicities must additionally be retained; in the Hamming construction below the modulus has no repeated roots.

The unrestricted ternary cyclic-equivalence assertion is false. At $s=2$ it would give a cyclic $[4,2,3{]}_3$ code. Butover ${\mathbb{F}}_3$, with the quadratic irreducible. A dimension-two cyclic code needs a degree-two generator, so its only possibilities are $T^2-1$ and $T^2+1$. Each is a weight-two codeword. Therefore neither has minimum distance three, and no code equivalent to the ternary $[4,2,3]$ Hamming code can be cyclic. A valid general version of the asserted construction assumes odd $s$. The usual distance-three Hamming parameters also require $s\ge 2$; when $s=1$ the code is the length-one zero code.

Here is the construction with its precise qualification. A ternary Hamming code has a parity-check matrix whose columns represent each one-dimensional subspace of ${\mathbb{F}}_3^s$ once. There are $n=(3^s-1)/2$ such subspaces. Its rank is $s$, because the coordinate lines are included. Its minimum distance is at least three, because no column is zero and no two are proportional. For $s\ge 2$, two independent vectors and their sum determine three distinct columns, and, after adjusting their nonzero representative scalars, give a weight-three linear relation. Thus its parameters are $[n,n-s,3{]}_3$. Permuting columns and changing their nonzero representatives produces a monomial equivalence of linear codes.

Take odd $s\ge 3$ and choose $\alpha \in {\mathbb{F}}_{3^s}^{\times }$ of order $n$. Since $n$ is odd, $-1$ is not in the cyclic subgroup generated by $\alpha$. Hence $1,\alpha ,\dots ,{\alpha }^{n-1}$ lie in distinct one-dimensional ${\mathbb{F}}_3$-subspaces: a proportional pair would have ratio $1$ or $-1$, neither possible for two distinct powers in this list. By their number they represent all projective points. Consequentlyis monomially equivalent to the ternary Hamming code. Since ${\alpha }^n=1$, evaluation at $\alpha$ descends to ${\mathbb{F}}_3[T]/(T^n-1)$ and its kernel is an ideal, so $C$ is cyclic.

The degree of $\alpha$ over ${\mathbb{F}}_3$ is $s$. If it were $d<s$, its generated field would have $3^d$ elements and its element order would givea contradiction. Its minimal polynomial of an algebraic element therefore has degree $s$. Applying Frobenius to a polynomial relation shows that $\alpha ,{\alpha }^3,\dots ,{\alpha }^{3^{s-1}}$ are its roots; they are distinct by the same field-degree argument. Their product polynomial is the monic minimal polynomial of an algebraic element, and it divides $T^n-1$. ThusThis identifies all the defining zeros. For $s=3$, $n=13$, the defining exponents are $1,3,9$ modulo $13$.

There is also a uniform construction for all $s\ge 2$, explaining the missing qualification. Let $\beta$ generate ${\mathbb{F}}_{3^s}^{\times }$, which has order $2n$. The powers $1,\beta ,\dots ,{\beta }^{n-1}$ represent all projective points, since proportional powers differ by exponent $0$ or $n$ modulo $2n$. But ${\beta }^n=-1$, so the kernel of $c\mapsto c(\beta )$ is an ideal modulo $T^n+1$, a negacyclic code. Multiplication by $T$ gives $(-c_{n-1},c_0,\dots ,c_{n-2})$, preserving its kernel. This code is always equivalent to the ternary Hamming code. If $s$ is odd, $n$ is odd too, and the substitution $T\mapsto -T$, or coordinate scaling $c_i\mapsto (-1{)}^i{c}_i$, changes this negacyclic construction into the cyclic one. In fact $\alpha =-\beta$ then has order $n$. These explicit constructions prove the qualified assertion rather than relying on a theorem name.

For decoding, use the printed $13\times 3$ matrix $H$ with received words as row vectors; the conventional $3\times 13$ parity-check matrix is $H^T$. The received word's syndrome isA single-symbol error of value $a$ at position $i$ has syndrome $a{h}_i$, where $h_i$ is row $i$ of the printed matrix. HereTherefore subtract $2$ at the sixth coordinate, changing its received value $1$ to $2$ modulo three. The decoded codeword isIts syndrome is zero. The thirteen projective rows and the two nonzero scalars give all $26$ nonzero syndromes exactly once, so this is the unique codeword at distance one. It is the transmitted word under the usual assumption of at most one symbol error. If positions $1,2,5$ are designated check positions, their independent unit rows make the other ten symbols systematic data, namely $(2,0,2,0,0,2,1,1,2,0)$.

Represent a word $(c_0,\dots ,c_{n-1})$ in the Hamming space $H_{n,q}$ by the polynomial $c(x)={\sum }_{j=0}^{n-1}{c}_j{x}^j$. A cyclic code is a linear code invariant under the cyclic coordinate shift $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Under this identification the shift is multiplication by $x$ modulo $x^n-1$. A shift-invariant vector subspace is closed under multiplication by every polynomial, since such multiplication is a linear combination of shifts. It is therefore an ideal ofConversely every ideal of $R$ is a vector subspace closed under multiplication by $x$, hence a cyclic code. Invariance means equality under the shift, since applying it $n$ times is the identity.

Let $J$ be the inverse image of the code ideal under the quotient map ${\mathbb{F}}_q[x]\to R$. It contains $(x^n-1)$ and is nonzero. Choose a nonzero element of $J$ of smallest degree and scale it to a monic polynomial $g$. For any $f\in J$, polynomial division gives $f=ag+r$ with $\mathrm{deg}r<\mathrm{deg}g$. Since $r=f-ag\in J$, minimality forces $r=0$. Thus $J=(g)$ and in particularThis is the required generator polynomial of a cyclic code; the divisibility direction in the printed formula is reversed. The quotient-ring modulus is $x^n-1$, with $1$ denoting the multiplicative identity of the finite field. If $r=\mathrm{deg}g$, every codeword has a unique representative $ag$ with $\mathrm{deg}a<n-r$. Indeed reduction of $a$ modulo $(x^n-1)/g$ gives this form, and two such products cannot differ by a nonzero multiple of $x^n-1$ because their difference has degree less than $n$. ThereforeFor the zero code the convention is $g=x^n-1$ and this basis is empty; for the full word space $g=1$.

The zeros of a cyclic code are the polynomial roots of $g$ in a splitting field $E$ of $x^n-1$. Suppose first that the characteristic $p$ of ${\mathbb{F}}_q$ does not divide $n$. The formal derivative of $x^n-1$ is $n{x}^{n-1}$, which has no common root with $x^n-1$; all roots of $g$ are therefore simple. If they are ${\alpha }_1,\dots ,{\alpha }_r$, then $g\mid c$ is equivalent to $c({\alpha }_i)=0$ for all $i$. A root-evaluation parity-check matrix of a cyclic code, written with checks as rows, is consequentlyIts entries may lie in $E$, rather than in the original finite field. To obtain a parity-check matrix over ${\mathbb{F}}_q$, choose a basis of $E$ over ${\mathbb{F}}_q$ and replace each equation by the equations for all of its field coordinates. The resulting matrix has the same kernel $C$, hence rank $r=n-\dim C$; retain any $r$ independent rows. More economically, choose one root from each Frobenius conjugate orbit. For $c\in {\mathbb{F}}_q[x]$, $c({\alpha }^q)=c(\alpha {)}^q$, so checking one representative checks its whole orbit. Expanding that representative's equation in a basis of ${\mathbb{F}}_q(\alpha )$ gives precisely the number of checks equal to its orbit length.

No coprimality hypothesis is stated in the question, so the repeated-root cyclic code case must also be distinguished. Distinct roots alone cannot determine these codes: in ${\mathbb{F}}_2[x]/(x^2-1)$, the generators $x+1$ and $(x+1{)}^2$ have the same zero, but generate codes of dimensions one and zero. In general write $g={\prod }_i(x-{\alpha }_i{)}^{m_i}$ in $E[x]$. The correct checks areusing Hasse derivatives. Indeed $c({\alpha }_i+z)={\sum }_{\ell }{c}^{[\ell ]}({\alpha }_i)z^{\ell }$, so vanishing of the first $m_i$ coefficients is equivalent to divisibility by $(x-{\alpha }_i{)}^{m_i}$. A repeated-root parity-check matrix over $E$ thus has rows indexed by $(i,\ell )$ and entriesAs before, expand to equations over ${\mathbb{F}}_q$ and retain $\mathrm{deg}g={\sum }_i{m}_i$ independent rows. The ordinary root-evaluation matrix is exactly the special case $m_i=1$.

For the binary Hamming code, let $s\ge 2$, $n=2^s-1$, and let $\omega$ generate the multiplicative group of a finite field ${\mathbb{F}}_{2^s}^{\times }$. This is possible because that group is a cyclic group. Choose a basis of ${\mathbb{F}}_{2^s}$ over ${\mathbb{F}}_2$. The coordinate columns of $1,\omega ,\dots ,{\omega }^{n-1}$ then run through every nonzero vector of ${\mathbb{F}}_2^s$ exactly once. They are a parity-check matrix $H$ for a Hamming code, possibly after permuting the columns of a given Hamming matrix. Thusis equivalent to the Hamming code. Multiplication by $x$ modulo $x^n-1$ multiplies its evaluation at $\omega$ by $\omega$, so $C$ is a cyclic code.

The parity-check matrix has rank $s$ because its columns contain a basis. It has no zero column or repeated column, so no nonzero word of weight one or two is in its kernel. Two distinct nonzero columns have a nonzero sum, which is a third distinct column; these three columns give a word of weight three. Hence $C$ has parameters $[2^s-1,2^s-s-1,3]$.

A polynomial over ${\mathbb{F}}_2$ vanishes at $\omega$ exactly when it is divisible by its minimal polynomial of an algebraic element $m_{\omega }$. The finite-field Frobenius automorphism gives all conjugates of $\omega$ as ${\omega }^{2^j}$. Their orbit length is $s$: if ${\omega }^{2^d}=\omega$ with $0<d<s$, then the order $2^s-1$ of $\omega$ would divide $2^d-1$, which is a smaller positive integer. Therefore the Hamming code as a cyclic code hasThe last exponent here is $2^{s-1}$. The printed exponent $2^s-1$ would give ${\omega }^{2^s-1}=1$, which is not a root of the degree-$s$ irreducible minimal polynomial of an algebraic element for $s\ge 2$.