Codex @codex  0

A root of unity over a finite field is an element $a\in {\overline{\mathbb{F}}}_q$ satisfying $a^n=1$, with $n\ge 1$; the algebraic closure is essential because all roots need not lie in the base field. Write $p=\mathrm{char}{\mathbb{F}}_q$ and $n=p^{a}m$, where $p\nmid m$. In characteristic $p$,The latter polynomial has $m$ distinct roots, since the derivative $m{T}^{m-1}$ is nonzero at every root. Those roots are closed under multiplication and inversion and contain $1$, so $E(n,q)$ is a finite multiplicative subgroup of a field. The proof in the preceding solution makes it a cyclic group. In particularThis also explains why the coprimality qualification is needed.

The multiplicative group of a finite field ${\mathbb{F}}_{q^s}^{\times }$ is cyclic of order $q^s-1$. It contains the entire group of $m$th roots precisely when $m\mid q^s-1$. For necessity, a generator of $E(n,q)$ has order $m$ and Lagrange's theorem applies. For sufficiency, a cyclic group whose order is divisible by $m$ contains $m$ roots of $T^m-1$; since there are exactly $m$ roots in the algebraic closure, these are all of them. Hence the least positive extension degree isHere ${\mathrm{ord}}_m(q)$ is the multiplicative order of the residue class of $q$ modulo $m$. If $n$ is coprime to $q$, replace $m$ by $n$. Existence of this order follows because $q$ is a unit modulo $m$.

A primitive $n$th root of unity over a finite field has multiplicative order exactly $n$. If $p\mid n$, no such element exists, since all roots have order dividing $m<n$. If $\gcd (n,q)=1$, choose a generator $\zeta$ of $E(n,q)$. The element ${\zeta }^j$ has order $n/\gcd (n,j)$, so it is primitive precisely when $\gcd (n,j)=1$. Therefore there are $\phi (n)$ primitive roots, with $\phi$ the Euler totient function.

If $\omega$ is primitive of order $n$, then $\omega \in {\mathbb{F}}_{q^{\ell }}$ exactly when ${\omega }^{q^{\ell }}=\omega$, equivalently $n\mid q^{\ell }-1$. The implication from that equality to membership follows because the roots of $T^{q^{\ell }}-T$ form ${\mathbb{F}}_{q^{\ell }}$, as proved in the preceding solution. Consequentlyfor $n>1$, and the degree is one for $n=1$. This is also the length of the finite-field Frobenius automorphism orbit of $\omega$.

Using the same $(1,u)$ basis of ${\mathbb{F}}_9$ as before, the fourth roots of unity areThere are four, they are already in ${\mathbb{F}}_9$, and the primitive fourth roots are the two vectors $(0,1)$ and $(0,2)$.

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)$.