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

A cubic polynomial over a field is reducible if and only if it has a root in that field: a nontrivial factorization of degree three has a linear polynomial factor, and conversely a root supplies one by the factor theorem.

The rational root theorem, or part (b), shows that a rational root of this monic polynomial must be an integer. Such an integer must divide the constant coefficient $4$, so the only candidates are $\pm 1,\pm 2,\pm 4$. Direct evaluation givesNone vanishes. Hence there is no rational root, provingThe same no-root argument alone would not decide a quartic polynomial, which could factor as two quadratic polynomials; its sufficiency here uses degree three.

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 factor theorem gives a factor $x-1$. Polynomial division and then factorization giveConsequently all three roots of a polynomial are

The factor theorem supplies the factor $x-3$. Polynomial division givesThe quadratic formula then gives the other two roots of a polynomial:

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

List the roots with their multiplicities. By the factor theorem, $Q(z)=a{\prod }_{k=1}^n(z-{\alpha }_k)$ with $a\ne 0$. The product rule, followed by division where $Q(z)\ne 0$, gives its logarithmic derivative:Let $Q^{\prime }(\beta )=0$. If $Q(\beta )=0$ too, then $\beta$ is already one of the roots, so either desired location conclusion follows immediately. Otherwise the displayed sum vanishes at $\beta$. If all roots have positive imaginary parts but $\mathrm{Im}\beta \le 0$, thenfor every $k$. Their sum cannot be zero. Thus $\mathrm{Im}\beta >0$.

For the unit disk conclusion, the same sum gives an especially transparent convex combination. Taking complex conjugates and setting $w_k=|\beta -{\alpha }_k{|}^{-2}>0$ givesTherefore, if every $|{\alpha }_k|<1$,The strict inequality follows because this is a finite weighted average of numbers strictly below one. This also proves the Gauss-Lucas theorem: every critical point of a nonconstant polynomial lies in the convex hull of its roots. The common-root case, handled before division, is essential when multiplicities occur.

For the distinct interpolation nodes, define the Lagrange cardinal polynomialsEvery denominator is nonzero, each $L_i$ has polynomial degree at most $n$, and $L_i(x_j)={\delta }_{ij}$. Hence the Lagrange interpolation polynomialbelongs to ${\Pi }_n$ and has $p_n(x_j)=f_j$. This proves existence.

If $p_n$ and ${\tilde{p}}_n$ both fit the data, their difference has polynomial degree at most $n$ but vanishes at the $n+1$ distinct interpolation nodes. Repeated application of the factor theorem implies that ${\prod }_{j=0}^n(x-x_j)$ divides that difference. A nonzero polynomial of degree at most $n$ cannot have such a divisor of degree $n+1$. Thus $p_n-{\tilde{p}}_n=0$, proving uniqueness. When $n=0$, the empty product defining $L_0$ is $1$, so the argument includes the constant case.

If $p$ and $q$ both interpolate the data and have degree at most $n$, the polynomial $r=p-q$ has the $n+1$ distinct roots $x_0,\dots ,x_n$. A nonzero polynomial of degree at most $n$ has at most $n$ roots: repeated use of the factor theorem would otherwise make a product of $n+1$ linear factors divide it. Hence $r=0$, proving the interpolating polynomial is unique.

A splitting field of $f$ over $F$ is an extension field in which $f$ factors into linear factors and which is generated over $F$ by those roots. The generation requirement excludes unnecessary extra elements.

For existence, induct on the degree. An irreducible factor $p$ of $f$ gives a field $F_1=F[X]/(p)$, since an irreducible polynomial generates a maximal ideal in the polynomial ring over a field. The class $\alpha$ of $X$ is a root of $p$ and hence of $f$. By the factor theorem, $f=(X-\alpha )g$ over $F_1$, with $\mathrm{deg}g=\mathrm{deg}f-1$. Induction gives a splitting field of $g$ over $F_1$. It contains all roots of $f$; taking the subfield generated by these roots over $F$ gives exactly a splitting field of $f$. The degree-one case is immediate. Thus

Write $q=|\mathbb{F}|$. The unit group $U(\mathbb{F})=\mathbb{F}\setminus \{0\}$ is a finite abelian group of group order $q-1$, since multiplication in a field satisfies commutativity. The structure theorem for finitely generated abelian groups, applied to this finite group, gives invariant factors of a finitely generated moduleafter omitting trivial factors. If there are no factors, the unit group is trivial and hence a cyclic group.

Otherwise put $D=d_r$. Every element $u\in U(\mathbb{F})$ satisfies $u^D=1$, because the order of a group element in each coordinate divides $D$. Hence all $q-1$ distinct nonzero elements of $\mathbb{F}$ are roots of a polynomial $X^D-1$. The root bound for a polynomial over a field givesFor completeness, that bound follows by induction from the factor theorem: if a nonzero polynomial $f$ vanishes at $a$, write $f=(X-a)g$; every other root of a polynomial is a root of $g$, because a field has no zero divisors. Each new distinct root therefore uses one unit of polynomial degree.

On the other hand, the group order in the decomposition isEquality is forced, so $d_1\cdots d_{r-1}=1$. As every retained factor is greater than $1$, there can be only one. ConsequentlyThe same proof establishes the more general result finite multiplicative subgroup of a field is cyclic. The square-free integer result in part (c)(i) alone would not suffice, since $q-1$ need not be a square-free integer; the root bound for a polynomial rules out multiple invariant factors of a finitely generated module even then.