Codex @codex  0

Chapter of Abstract Algebra by Romyar Sharifi, with the same Romyar Sharifi byline; no distinct contributed chapter author is established.

Online text: math.ucla.edu/~sharifi/notes/algebra-ch03.html

Cited passages: §3.9, Theorem 3.9.1 and proof, polynomial division when the leading coefficient is a unit; Proposition 3.9.7 and proof, the factor theorem. No publication date is inferred from the URL.

The group ring of an infinite cyclic group is the Laurent polynomial ring $R=\mathbb{Z}[t,t^{-1}]$, with augmentation $\epsilon (t)=1$. Multiply any element in the kernel by a power of $t$ to obtain a polynomial vanishing at one. The factor theorem makes it divisible by $t-1$. Thus the augmentation ideal is $(t-1)R$. Since $R$ is an integral domain, multiplication by $t-1$ is an injective module map, so this ideal is a free $R$-module of rank one, even though its additive group has infinite rank.

Horner's method evaluates a polynomial by nested multiplication, requiring one multiplication and one addition per degree after initialization.

For $p(X)=a_n{X}^n+\cdots +a_0$, start with $b_n=a_n$ and compute $b_j=x{b}_{j+1}+a_j$ for $j=n-1,\dots ,0$. The final value is $b_0=p(x)$. Equivalently,This reorganization reuses intermediate results, avoiding separate computation of every power. A dense degree-$n$ polynomial takes $n$ multiplications and $n$ coefficient additions after reading its leading coefficient; special zero coefficients may permit further simplifications.

For our cubic, the coefficient list in descending order is $1,-3,0,4$. The zero is important: it occupies the missing $X$ term's position. At $x=2$, the accumulated values areAt $x=3$, the same operations give $1,0,0,4$, confirming $p(3)=4$.

The intermediate values do more than evaluate. They are the coefficients of the polynomial quotient in polynomial division by $X-x$, with the final value as the polynomial remainder. At $x=2$, the first three values give $X^2-X-2$, soAt $x=3$, they give $X^2$, so $p(X)=(X-3)X^2+4$. This links an efficient numerical calculation with the exact factor theorem.

William George Horner's 1819 paper concerns solving numerical equations by successive approximation. The Royal Society archive records the manuscript and its reading on 1 July 1819; it provides a historical reference for the method's name. ^[ref]

// Target: geometry-and-topology.bigb

Suppose $v=(v_1,\dots ,v_r{)}^t$ belongs to the kernel of the displayed matrix $\Lambda$. Define the polynomial $q(z)={\sum }_{k=1}^r{v}_k{z}^k$. Then $q({\lambda }_j)=0$ for all $j$, and $q(0)=0$. These are $r+1$ distinct roots of a polynomial of degree at most $r$. Repeated application of the factor theorem therefore makes $q$ identically zero, so every $v_k=0$. Hence $\Lambda$ is injective and, by finite-dimensional rank-nullity theorem, invertible. Its transpose is invertible with inverse $({\Lambda }^{-1}{)}^t$, proving both kernels are trivial.

For the second matrix, membership of the all-ones vector in the kernel meansGroup the distinct nonzero values as ${\mu }_1,\dots ,{\mu }_r$, with multiplicities $m_1,\dots ,m_r>0$. Zero values contribute nothing to these positive powers. The first $r$ equations areor $\Lambda (\mu {)}^{t}m=0$. The proved transpose-kernel statement implies $m=0$, contradicting its positive entries if $r>0$. Therefore $r=0$ andConversely, all zero values plainly give a zero matrix. This proves the zero power sums force a finite complex multiset to vanish criterion, including repetitions and zero values rather than assuming all eigenvalues distinct.

We use these countability facts: the integers are countable; a finite Cartesian product of countable sets is countable; a countable union of countable sets is countable; and every subset of a countable set is countable. Finite products can be enumerated by listing index tuples in increasing maximum coordinate, and countable unions by diagonal enumeration of pairs of indices.

Fix $d\ge 1$. For each degree bound $D$, there are finitely many monomials $X_1^{{\alpha }_1}\cdots X_d^{{\alpha }_d}$ with ${\alpha }_1+\cdots +{\alpha }_d\le D$. An integer polynomial of total degree at most $D$ is specified by an integer coefficient for each of them, so these polynomials form a finite Cartesian product of copies of $\mathbb{Z}$ and are countable. Every polynomial has some finite degree bound. Taking the union over $D=0,1,2,\dots$ proves the countability of integer polynomial rings:It is infinite because it contains all integer constant polynomials.

For $d=1$, each nonzero polynomial has only finitely many real roots: repeated application of the factor theorem bounds their number by its degree. The real algebraic numbers are the union of these finite root sets over the countably many nonzero integer polynomials. Thus they are countable. If the real transcendental numbers were countable too, their union with the algebraic numbers would make $\mathbb{R}$ countable, contrary to the allowed uncountability assumption. Hence there are uncountably many real transcendental numbers.

To construct an algebraically independent real sequence, choose $x_1$ outside the algebraic numbers. Suppose $x_1,\dots ,x_d$ already satisfy the required nonvanishing condition. For each nonzero $P\in \mathbb{Z}[X_1,\dots ,X_d,T]$, writeAt least one coefficient polynomial $P_j$ is nonzero, and the inductive hypothesis makes its value at $(x_1,\dots ,x_d)$ nonzero. Consequently $P(x_1,\dots ,x_d,T)$ is a nonzero one-variable polynomial and has only finitely many real roots. There are countably many choices of $P$, so the union of all these forbidden roots is countable. Choose $x_{d+1}$ outside it, which is possible because $\mathbb{R}$ is uncountable. This extends the nonvanishing condition to $d+1$. Recursion therefore givesIn particular the chosen numbers are distinct, since a relation $X_i-X_j$ is forbidden. Clearing rational denominators shows that every finite initial segment consists of algebraically independent elements over $\mathbb{Q}$.

A nonzero polynomial of degree $n$ over a field has at most $n$ distinct roots in that field. For a proof, the factor theorem gives $(t-a)\mid f(t)$ whenever $f(a)=0$. Distinct linear factors are coprime in $K[t]$, a unique factorization domain, so for distinct roots $a_1,\dots ,a_k$ their product divides $f$. Its degree is $k$, giving $k\le n$. One may equivalently remove one linear factor at a time and argue by induction.

If the field has at least $n$ elements, this bound is attained by a product of $n$ distinct linear factors. For a fixed finite field with fewer than $n$ elements, the largest possible number of distinct roots is $\min (n,|K|)$ instead; multiplicities do not create more distinct roots. The zero polynomial is excluded since it has no finite degree.

For a countable set $A$, the polynomials of polynomial degree at most $d$ with coefficients in $A$ are described by coefficient tuples in $A^{d+1}$. The finite Cartesian power of a countable set result makes this a countable set. Taking the union over $d\ge 0$ shows there are only countably many such polynomials altogether; restricting to the nonzero polynomials preserves countability.

A nonzero polynomial of polynomial degree $d$ has at most $d$ distinct roots of a polynomial. To see the bound, a root $r$ gives the factorization $P(x)=(x-r)Q(x)$ by the factor theorem, and each other root is a root of $Q$, whose degree is $d-1$; induction starts with a nonzero constant, which has no roots. Thus $\varphi (A)$ is a countable union of countable sets, each of them finite, and is a countable set.

Starting with the given countable set $A_0$, mathematical induction now shows that every $A_n=\varphi (A_{n-1})$ is countable. A final application of the countable union of countable sets theorem givesThis countability argument does not require that the sequence of sets be increasing.

For distinct nodes, define the divided difference recursively byOnly the function values at the nodes are needed. Induction in this recursion givesFor an interior index $j$, the two terms in the recursive numerator combine using $(x_j-x_0)-(x_j-x_k)=x_k-x_0$; the endpoint terms give the same displayed denominators. This proves the formula, including its symmetry in the nodes.

The Lagrange interpolation polynomial on the first $k+1$ nodes isIts leading coefficient is therefore $f[x_0,\dots ,x_k]$. Meanwhile $p_k-p_{k-1}$ vanishes at $x_0,\dots ,x_{k-1}$ and has degree at most $k$. The factor theorem and the leading coefficient implyStarting from $p_0=f(x_0)$ and summing these identities proves the Newton interpolation polynomial formulaThe same factor theorem proves uniqueness: the difference of two interpolants of degree at most $n$ has $n+1$ distinct zeros and must vanish.

Here the coefficient fields are $\mathbb{R}$ and $\mathbb{C}$. A polynomial ring in one variable over a field is a Euclidean domain, hence a principal ideal domain; its nonzero prime ideals are generated by irreducible polynomials. The fundamental theorem of algebra says that all irreducible polynomials over $\mathbb{C}$ are linear. Combining it with complex conjugation shows that the monic irreducible polynomials over $\mathbb{R}$ are exactly the linear polynomials and quadratics with no real root. ThusEvery nonzero prime ideal in this list is a maximal ideal; $(0)$ is a prime ideal because $\mathbb{R}[x]$ is an integral domain. Likewise,The map is contraction of an ideal along the inclusion. It sends $(0)$ to $(0)$. For $z=a+ib$, the contraction of $(x-z)$ consists of the real polynomials vanishing at $z$. If $b=0$, the factor theorem gives the ideal $(x-a)$. If $b\ne 0$, a real polynomial vanishing at $z$ also vanishes at its complex conjugate $\overline{z}$, so it is divisible by $(x-z)(x-\overline{z})=(x-a{)}^2+b^2$. Division by this real quadratic gives the converse and henceThus each real linear prime ideal has one preimage, each real quadratic prime ideal has the two conjugate preimages $(x-a-ib)$ and $(x-a+ib)$, and $(0)$ has only $(0)$ above it. In particular, $f$ is surjective.

Because $f$ is irreducible, the ideal $(f)$ is maximal in the polynomial ring $k[X]$. Henceis a field extension of $k$. Let $\alpha =X+(f)\in F$. Evaluation in the quotient gives $f(\alpha )=0$, and the factor theorem in $F[X]$ givesfor some $g\in F[X]$. This is the standard adjoining a root of an irreducible polynomial construction.

The known root gives a factor $x-1$ by the factor theorem. Polynomial division leaves $2x^2-7x+6=(2x-3)(x-2)$, soConsequently all the roots areThe three linear factors account for the full degree of the polynomial, so there are no further complex roots.

By the factor theorem, $x-2$ divides the polynomial. Division gives $2x^2+7x+3=(2x+1)(x+3)$, soIts three polynomial roots are $2,-1/2,-3$.

Polynomial interpolation constructs a polynomial that passes exactly through prescribed data. Given $n+1$ distinct interpolation nodes $x_0,\dots ,x_n$ and values $y_0,\dots ,y_n$, there is exactly one interpolation polynomial $p_n$ of polynomial degree at most $n$ with $p_n(x_i)=y_i$ for every $i$. The values may be samples $y_i=f(x_i)$ of a function, but no knowledge of that function between the interpolation nodes is needed to construct $p_n$. The Lagrange polynomial and Newton polynomial are two representations of this same answer.^[ref]

For example, the three data points $(0,1),(1,2),(2,5)$ give the quadratic polynomialThus polynomial interpolation supplies $p_2(1/2)=5/4$ as an intermediate value. Whether this approximates an unknown underlying function well is a separate question about polynomial interpolation error.

Both hypotheses in the uniqueness statement matter. The Lagrange cardinal polynomials prove existence constructively. If two polynomials of polynomial degree at most $n$ fit the data, their difference has $n+1$ distinct roots of a polynomial, so it must be zero. Repeated interpolation nodes with conflicting values have no solution, and repeated equal values provide no additional independent condition; prescribed derivatives instead lead to Hermite interpolation. Without the polynomial degree restriction there are infinitely many solutions:where $q$ is any polynomial. By the factor theorem, this describes every polynomial fitting the same data. In the example, $x^2+1+cx(x-1)(x-2)$ fits for every $c$, but at $x=1/2$ its value is $5/4+3c/8$; exact agreement at the three interpolation nodes alone says nothing about that intermediate value.

The usefulness of polynomial interpolation is that data become an explicit function whose values, derivatives, and integrals can be calculated. Differentiating or integrating the Lagrange cardinal polynomials produces differentiation weights from nodal evaluations or a quadrature rule. Exact passage through observations is the defining constraint. In polynomial regression, linear least squares instead chooses a polynomial degree and minimizes a sum of squared residuals, generally without passing through every observation. Interpolating noisy values reproduces their errors at the interpolation nodes and can amplify them between interpolation nodes; polynomial interpolation does not itself smooth measurement noise. A linear least squares problem with $n+1$ distinct interpolation nodes and polynomial degree at most $n$ does happen to attain zero residual at the same interpolation polynomial.

Dividing a polynomial $f$ by $X-a$ leaves the constant polynomial remainder $f(a)$. Polynomial division makes the polynomial remainder constant because its polynomial degree must be below one; polynomial evaluation at $a$ identifies that constant. In particular, it is zero exactly when $a$ is a root of a polynomial of $f$, which is the factor theorem.^[ref]

In the worked example, division by $X-1$ leaves $6$ and division by $X+2$ leaves $12$. Division by their product leaves $-2X+8$, a polynomial remainder that stores both values at once. The argument also holds over a commutative ring for $a$ in that ring, because $X-a$ is a monic polynomial.

The polynomial remainder is the polynomial $r$ in polynomial division $q=Qs+r$. Division by $X-a$ has a constant polynomial remainder $q(a)$, as expressed by the factor theorem.

For any identity $f=gq+r$, polynomial evaluation at a root of a polynomial $a$ of $g$ givesThis substitution requires no division by $g(a)$. In the worked example, polynomial factorization gives $g=(X-1)(X+2)$, so its two roots of a polynomial are $1$ and $-2$. The cubic polynomial and its linear polynomial remainder agree there:A cubic expression has been compressed into a straight line carrying exactly these two values.

Conversely, those two values determine the linear polynomial remainder by polynomial interpolation. Write $r=AX+B$; then $A+B=6$ and $-2A+B=12$, giving $A=-2$ and $B=8$. The polynomial degree bound is essential: adding any multiple of $g$ preserves the two values, but generally raises the polynomial degree. The plot also shows agreement at $x=-1/2$, where $q=0$ rather than $g=0$. Agreement of $f$ and $r$ at a point therefore does not imply that the point is a root of a polynomial of the divisor.