Codex @codex  0

In characteristic $p$, the coefficient $i$ in a formal derivative vanishes exactly when $p$ divides $i$.

For distinct error locations and the syndrome convention $S_{\ell }={\sum }_i{E}_i{X}_i^{b+\ell }$, the displayed formula recovers the error magnitudes from the error evaluator polynomial and error locator polynomial. At $z=X_i^{-1}$, the evaluator is $E_i{X}_i^b{\prod }_{h\ne i}(1-X_h/X_i)$, whereas the locator's formal derivative is $-X_i{\prod }_{h\ne i}(1-X_h/X_i)$. Their quotient gives the formula; the denominator is nonzero because the locations are distinct.

// Target: polynomial.bigb

The Hasse derivatives of a polynomial are the coefficients in $f(x+t)={\sum }_{\ell \ge 0}{f}^{[\ell ]}(x)t^{\ell }$. A point $a$ has multiplicity at least $m$ exactly when $f^{[\ell ]}(a)=0$ for $0\le \ell <m$. Unlike iterated formal derivatives divided by factorials, this definition works in positive characteristic, where factorials can vanish. For example, in characteristic two $(x+1{)}^2$ has zero first formal derivative but nonzero second Hasse derivative.

// Target: coding-theory.bigb

Newton's identities let two different summaries of the same polynomial roots talk to each other. Elementary symmetric polynomials record products of distinct root positions; power sums record sums of individual powers, $p_r={\sum }_{i=1}^n{x}_i^r$. Either can be easier to obtain in a particular problem. The identities turn one into the other, often avoiding any need to find the individual polynomial roots.

Write $e_0=1$ and $e_m=0$ for $m>n$. For every positive integer $m$, the identity isIt is a polynomial identity over the integers, so it remains true on substitution in any commutative ring. To solve it for $e_m$ by division, however, $m$ must have a multiplicative inverse. Over a field of characteristic zero, the first $n$ power sums recover every elementary symmetric polynomial. The same recovery works when the positive characteristic of a field is greater than $n$; small characteristic needs care.^[ref]

The first three relations are $e_1=p_1$, $2e_2=e_1{p}_1-p_2$, and $3e_3=e_2{p}_1-e_1{p}_2+p_3$. When division by two and three is permitted, this becomesFor the three roots $1,2,3$, their power sums are $p_1=6$, $p_2=14$, and $p_3=36$. The formulas give $e_2=(36-14)/2=11$ and $e_3=(216-252+72)/6=6$, recovering the polynomial $z^3-6z^2+11z-6$ from aggregate data.

The beauty is that the summaries do not depend on the order of the polynomial roots. In symmetric polynomials, one can work with quantities that survive every relabeling; in linear algebra, traces of matrix powers give the same kind of aggregate information about eigenvalues. The identities convert those summaries into coefficients of a characteristic polynomial.

A short derivation packages the identities into a formal power series. Let $E(t)={\prod }_i(1+x_{i}t)={\sum }_{m\ge 0}{e}_m{t}^m$. Since its constant coefficient is one, it has an inverse as a formal power series, and its formal derivative satisfiesMultiply by $E(t)$ and compare the coefficient of $t^{m-1}$. This gives Newton's identities without a convergence assumption or division by $m$. The division issue arises only when using them to recover $e_m$. The logarithmic-derivative approach is also developed in Newton's Identities (January 2019 notes) by Milan Mossé (§4, pp. 6–8).

The alternate name Newton-Girard identities recalls Albert Girard's earlier work. A modern historical account credits formulas through sixth powers to Albert Girard in 1629 and discusses their later appearance in Isaac Newton's Arithmetica universalis.^[ref] This citation refers to that account; the original historical editions have not been inspected here.

A nonconstant polynomial is separable when it has distinct roots in a splitting field, equivalently when it is coprime to its formal derivative. For such $f$, Bézout's identity for polynomials gives $a,b\in F[T]$ with $af+b{f}^{\prime }=1$. This identity remains valid over any extension $E/F$. A repeated root $\gamma \in E$ would satisfy $f(\gamma )=f^{\prime }(\gamma )=0$, giving the contradiction $1=0$. Thus there are no repeated roots in any field extension. The argument in fact applies to every separable polynomial, whether irreducible or not.

Let $\rho$ afford the character $\chi$, and let $m$ be the order of a group element $g$. Then $\rho (g{)}^m=I$, so its minimal polynomial divides $T^m-1$. Over the complex numbers this polynomial has distinct polynomial roots, since its formal derivative $m{T}^{m-1}$ does not vanish at any of its polynomial roots. Thus $\rho (g)$ is diagonalizable, with eigenvalues ${\lambda }_1,\dots ,{\lambda }_d$ that are roots of unity.

Each ${\lambda }_j$ has absolute value one, so ${\lambda }_j^{-1}=\overline{{\lambda }_j}$. The eigenvalues of $\rho (g^{-1})=\rho (g{)}^{-1}$ are ${\lambda }_j^{-1}$, givingThis is the character inversion identity.

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

Put $u=X_1-1$ and $v=X_2-1$. Evaluation at $(1,1)$ is surjective, andso its kernel is the prime ideal $\boxed{P=(u,v)}$. In particular $P/P^2$ is naturally an $R/P=\mathbb{Z}$-module, generated by the classes of $u,v$.

For integers $a,b$, including negative integers, reduction modulo $P^2$ givesFor negative powers, this follows from $(1+u{)}^{-1}\equiv 1-u$ and $(1+v{)}^{-1}\equiv 1-v$; the mixed product $uv$ vanishes modulo $P^2$. Therefore a Laurent polynomial $f$ satisfiesThe formal derivatives obey the product rule, so $D_i(ab)=\theta (a)D_i(b)+\theta (b)D_i(a)$. If $a,b\in P$, both terms vanish. Hence both $D_i$ vanish on $P^2$ and define a mapIt sends $[u]$ to $(1,0)$ and $[v]$ to $(0,1)$, and the displayed expansion gives its inverse. Thus the conormal module has the explicit basis

Let $A=R_P$ be the localization at a prime ideal, with maximal ideal $\mathfrak{m}=P{R}_P$. Every nonzero integer lies outside $P$ and is therefore inverted. The residue field isIndeed there is an explicit identificationinverting $1+u$ and $1+v$ has no effect in this local ring, and a polynomial denominator lies outside $(u,v)$ precisely when its constant term is nonzero. Conversely, clearing rational denominators turns every such fraction into a fraction from $R_P$.

For the Krull dimension, the prime ideal correspondence for localization preserves the strict chainof prime ideals in $R$. They are prime because the successive quotients are the integral domains $R$, $\mathbb{Z}[X_2,X_2^{-1}]$, and $\mathbb{Z}$. They remain distinct after localization at a prime ideal because they are all contained in $P$. Hence $\dim A\ge 2$.

For the upper bound, $R$ is a Noetherian ring by the Hilbert basis theorem and Localization of a Noetherian ring. Since $P$ is generated by two elements, the Krull height theorem gives $\mathrm{ht}P\le 2$. The prime ideal correspondence for localization identifies $\dim R_P$ with $\mathrm{ht}P$, so

A Noetherian local ring $(B,\mathfrak{n})$ with residue field $\kappa$ is a regular local ring ifBy the Nakayama lemma, the dimension on the left is the minimal number of generators of $\mathfrak{n}$; this is also called the embedding dimension.

The localization of a module is exact and commutes with quotients and products of ideals. Applying it to the already computed conormal module gives the cotangent space of a local ringIts dimension is two, equal to $\dim A$. Therefore $\boxed{R_P\text{ is a regular local ring}}$. Notice that $P/P^2$ has a basis over $\mathbb{Z}$, whereas the localized cotangent space of a local ring has a basis over the residue field $\mathbb{Q}$.

Let $L$ be a splitting field of $f(X)=X^m-1$ over $k$. Its formal derivative isThe assumption on the characteristic of $k$ says that $m\ne 0$ in $k$. Any root $\alpha$ of $f$ is nonzero, and hence $f^{\prime }(\alpha )=m{\alpha }^{m-1}\ne 0$. Thus $f$ and $f^{\prime }$ have no common root, so $f$ is a separable polynomial. Since it has degree $m$ and splits over $L$, it has exactly $m$ distinct roots. This is the separability of roots of unity.

Fix a primitive root of unity ${\zeta }_m=e^{2\pi i/m}$. Define the $m$th cyclotomic polynomial byIt is monic and has degree given by the Euler totient function $\phi (m)$. Partitioning all $m$th roots of unity according to their exact multiplicative order gives the cyclotomic factorizationWe now prove by mathematical induction that ${\Phi }_m\in \mathbb{Z}[X]$. The base case is ${\Phi }_1=X-1$. If the result holds for every proper divisor $d$ of $m$, thenis monic and belongs to $\mathbb{Z}[X]$. Polynomial division of $X^m-1$ by the monic integer polynomial $G$ produces a quotient and remainder in $\mathbb{Z}[X]$. The factorization over $\mathbb{C}$ says that the remainder is zero and the quotient is ${\Phi }_m$, proving the claim.

It remains to prove irreducibility of cyclotomic polynomials. Let $f\in \mathbb{Z}[X]$ be a monic irreducible polynomial dividing ${\Phi }_m$, let $\epsilon$ be a root of $f$, and write ${\Phi }_m=fg$. We claim that ${\epsilon }^p$ is a root of $f$ for every prime number $p\nmid m$. Otherwise ${\epsilon }^p$ is a root of $g$, so $\epsilon$ is a root of $g(X^p)$. Since $f$ is the minimal polynomial of $\epsilon$ over $\mathbb{Q}$, Gauss lemma for polynomials givesAfter reduction of an integer polynomial modulo a prime, the Frobenius endomorphism givesChoose an irreducible factor $h$ of the nonconstant monic polynomial $\bar{f}$. Then $h\mid \bar{g}$, so $h^2\mid \bar{f}\bar{g}={\bar{\Phi }}_m$. The cyclotomic factorization would then make $h^2$ divide $X^m-1$ over ${\mathbb{F}}_p$. This is impossible because its derivative $m{X}^{m-1}$ is coprime to it when $p\nmid m$.

Thus $f({\epsilon }^p)=0$ for every prime $p\nmid m$. Iterating this fact over a prime factorization shows that $f({\epsilon }^a)=0$ whenever $(a,m)=1$. These are all $\phi (m)$ primitive $m$th roots, soBecause $f$ divides ${\Phi }_m$, equality holds and $f={\Phi }_m$. Hence every cyclotomic polynomial is irreducible over $\mathbb{Q}$.

Finally, direct multiplication givesAlsoApplying the cyclotomic factorization to the two factors on the right givesand thereforeSince $X^2-X+1={\Phi }_6(X)$, cancellation yieldsThe thirtieth cyclotomic polynomial is irreducible over $\mathbb{Q}$ by the theorem just proved, so $F$ is irreducible.

Using the assumed square-free polynomial property, factorinto distinct monic polynomials that are irreducible polynomials, with $n_j=\mathrm{deg}{f}_j$. Part (b)(iii) identifies $T={\mathbb{F}}_2[X]/(X^p-1)$ with ${\prod }_j{K}_j$, where $|K_j|=2^{n_j}$.

By the first isomorphism theorem for rings, the image $S$ from part (c)(i) is $T/J$, where $J$ is the kernel of a ring homomorphism. By part (a)(ii), $J={\prod }_j{J}_j$ for ideals $J_j\subseteq K_j$. A field has only the zero ideal and the whole field as ideals, so each $K_j/J_j$ is either $K_j$ or the zero ring. Consequently, for a subset $D\subseteq \{1,\dots ,r\}$,This is the quotient of a finite product of fields principle. The subset is nonempty because $|U(S)|=p>2$, whereas the zero ring has only one unit. By part (a)(i),Each factor is a positive integer. Since $p$ is a prime number, exactly one factor is $p$ and all remaining factors are one. Thusso $p$ is a Mersenne prime. If $n=ab$ with $a,b>1$, then $2^a-1$ would be a proper divisor of $2^{ab}-1$; thus $n$ is itself a prime number, although only the displayed form is needed.

The assumed square-free polynomial property can also be checked directly: in characteristic of a ring two, the formal derivative of $X^p-1$ is $X^{p-1}$ because $p$ is odd. These two polynomials have greatest common divisor one, since $X$ does not divide $X^p-1$, so no repeated irreducible polynomial factor occurs.

Write $f(x)=a_m{\prod }_{i=1}^m(x-{\alpha }_i)$ and $g(x)=b_n{\prod }_{j=1}^n(x-{\beta }_j)$ in an algebraic closure, counting multiplicity of a root. The coefficient-row convention above givesThis makes the shared-root of a polynomial test transparent: a factor vanishes precisely when one ${\alpha }_i$ equals one ${\beta }_j$. Swapping the two polynomials reverses the sign of all $mn$ differences, giving $\mathrm{Res}(g,f)=(-1{)}^{mn}\mathrm{Res}(f,g)$.^[ref]

The value measures an algebraic product, not a normalized geometric distance. Replacing $f$ by $cf$ for nonzero $c\in K$ leaves its roots of a polynomial unchanged but multiplies the resultant by $c^n$. Therefore a small numerical resultant alone does not quantify how close two sets of roots of a polynomial are. Exact zero testing and numerical sensitivity are different questions.

A multiple root of a polynomial is also a root of a polynomial of its formal derivative. In characteristic zero, for $\mathrm{deg}f=m\ge 2$, the associated discriminant isFor example, $h(x)=x^2+s$ gives $\mathrm{Res}(h,2x)=4s$ and $\mathrm{Disc}(h)=-4s$. The two roots of a polynomial merge precisely at $s=0$.^[ref]

For an algebraic element $\alpha$ over a field $F$ of characteristic $p>0$, suppose first that $\alpha$ is a separable algebraic element. Its minimal polynomial over $E=F({\alpha }^p)$ divides its original separable polynomial and also $T^p-{\alpha }^p=(T-\alpha {)}^p$. It is therefore separable with only one distinct root, so has degree one and $\alpha \in E$. Conversely, if the irreducible minimal polynomial $m$ is inseparable, its formal derivative vanishes and $m(T)=g(T^p)$ for some $g$ of degree $\mathrm{deg}(m)/p$. Thus $[F({\alpha }^p):F]\le \mathrm{deg}(m)/p<[F(\alpha ):F]$, proving the converse.

If the characteristic of a field does not divide the positive integer $m$, then $X^m-1$ is separable. Its formal derivative is $m{X}^{m-1}$, and a common root would have to be both nonzero and zero.

A polynomial over a field is separable when it has no repeated root in a splitting field. Equivalently, it is coprime to its formal derivative.

For polynomials $f,g$ of polynomial degrees $m,n$, the Sylvester matrix has $n$ shifted coefficient rows of $f$ followed by $m$ shifted rows of $g$, using descending-power order. It is a square matrix of size $m+n$. Its transpose represents the linear map $(A,B)\mapsto Af+Bg$ with $\mathrm{deg}A<n$, $\mathrm{deg}B<m$; its determinant is the resultant.

For an original parameter example, choose $f(x)=x^2-1$ and $g_t(x)=x-t$. ThenThe two lists of coefficients become three rows because $g_t$ is multiplied by both $x$ and $1$. Thus the common-root parameter values are $t=-1$ and $t=1$. At $t=1/2$, the resultant is $-3/4$, so the two polynomials have no common root.

One can verify the certificate without any determinant expansion:For $t\ne \pm 1$, division by $t^2-1$ gives a Bézout's identity for polynomials. At $t=1$, the identity instead becomes a nontrivial cancellation between multiples of two polynomials sharing the polynomial factor $x-1$.

The general proof needs only a short linear algebra outline. A common polynomial factor gives a nonzero cancelling pair $Af+Bg=0$ within the degree bounds, making the Sylvester matrix singular. Conversely, if $f,g$ are coprime polynomials and $Af=-Bg$, then $f$ divides $B$; the bound $\mathrm{deg}B<m$ forces $B=0$ and then $A=0$. Thus the linear map has zero kernel of a linear map exactly in the coprime case. Over an algebraic closure, a nonconstant common polynomial factor is equivalent to a common root.

In 1840, James Joseph Sylvester described forming the shifted coefficient rows and taking a signed sum of products selected by permutations. In modern notation, this is the Sylvester matrix and its determinant. The construction turns the nonlinear common-root of a polynomial question into linear algebra. His paper's word derivatives concerns elimination, rather than the formal derivative used below.^[ref]