Codex @codex  0

An algebraic number $\alpha$ is an algebraic integer if it is a polynomial root of a monic polynomial with integer coefficients:Equivalently, its algebraic minimal polynomial over $\mathbb{Q}$ has integer coefficients. The requirement that the leading coefficient be one matters: $1/2$ satisfies $2X-1=0$ and is an algebraic number, but is not an algebraic integer. In fact the rational numbers that are algebraic integers are exactly the integers.^[ref]

Some useful computed examples are:

Algebraic integers are closed under addition, subtraction, and multiplication. Thus they provide an arithmetic ring, while division is allowed only when the result is again an algebraic integer. The algebraic integer module criterion explains this closure without having to find a new polynomial for every sum and product.

For a monic polynomial $f(t)=t^d+c_{d-1}{t}^{d-1}+\cdots +c_0$, use the companion matrix convention with ones on the subdiagonal and last column $(-c_0,\dots ,-c_{d-1}{)}^{\mathsf{T}}$. In $tI-C(f)$, the cofactors of the last-column entries, from top to bottom, are $1,t,\dots ,t^{d-1}$. This follows by expanding their bidiagonal minors: the subdiagonal factors $-1$ cancel the cofactor signs. Laplace expansion along that column therefore gives $c_0+c_{1}t+\cdots +c_{d-2}{t}^{d-2}+(t+c_{d-1})t^{d-1}=f(t)$. The degree-one case is the same identity for the one-by-one matrix $(-c_0)$.

The first-kind Chebyshev polynomial $T_n$ converts a multiple-angle cosine into a polynomial:The cosine addition formula gives the recurrence relationThis constructs polynomials valid for every real $x$, including outside $[-1,1]$, where the real-angle description is unavailable. For example,For $n\ge 1$, $T_n$ has polynomial degree $n$ and leading coefficient $2^{n-1}$. On $[-1,1]$ its uniform norm is one, even as its oscillations become more numerous.^[ref][ref]

The polynomial roots of $T_n$ are especially simple:They correspond to equally spaced angles, but their locations in $x$ cluster near $-1$ and $1$. For $T_3$, the polynomial roots are $\sqrt{3}/2,0,-\sqrt{3}/2$. For $T_8$, the positive polynomial roots are approximately $0.980785,0.831470,0.555570,0.195090$, with their negatives completing the set. The distance from the right endpoint to the nearest polynomial root is $1-\cos (\pi /(2n))\sim {\pi }^2/(8n^2)$; central neighboring polynomial roots are separated on the larger scale $1/n$. The small change of cosine near angles zero and $\pi$ explains the clustering.

These polynomial roots supply $n$ interpolation nodes for a polynomial interpolation of polynomial degree at most $n-1$. They differ from the $n+1$ Chebyshev-Lobatto nodes $\cos (j\pi /n)$, which include both endpoints. This choice of polynomial roots has nodal polynomialThe monic Chebyshev extremal polynomial minimizes the uniform norm of this product among monic polynomials of polynomial degree $n$ on $[-1,1]$. Consequently, if $f$ has $n$ continuous derivatives, the usual polynomial interpolation error gives the useful boundThis optimizes the nodal factor in that bound, not the actual error for every function. Endpoint clustering helps control the large endpoint oscillations of equally spaced interpolation associated with Runge's phenomenon. The two node conventions and their geometric construction are discussed in Trefethen's authored text.^[ref]

The same cosine substitution for polynomial approximation explains the weighted orthogonality:The endpoint singularities of the weight are integrable. Thus the Chebyshev polynomials are orthogonal polynomials for this weight, making coefficients in a least-squares polynomial in an orthogonal-polynomial basis separate cleanly. Their polynomial roots also give Chebyshev–Gauss quadrature, connecting polynomial interpolation to Gaussian quadrature.^[ref]

Accuracy still depends on the target function. The absolute value function $|x|$ has a corner at zero, so the hypothesis requiring continuous derivatives in the displayed polynomial interpolation error bound fails. Endpoint clustering cannot remove that corner. A jump poses a stronger obstruction: polynomials are continuous functions, so they cannot converge in the uniform norm to a discontinuous function on the whole interval. Chebfun's documented examples show persistent overshoot for such jumps; these are a limitation of global polynomial interpolation, not a universal promise of rapid accuracy from Chebyshev polynomials.^[ref]

For a monic polynomial $f(t)=t^d+c_{d-1}{t}^{d-1}+\cdots +c_0$, its companion matrix represents multiplication by $t$ on the quotient module $F[t]/(f)$ in the basis $1,t,\dots ,t^{d-1}$. With column vectors it has ones on the subdiagonal and last column $(-c_0,\dots ,-c_{d-1}{)}^{\mathsf{T}}$. For example, $C(t^2+ct+d)=\left(\begin{array}{cc}0& -d\\ 1& -c\end{array}\right)$. Transposing this matrix gives another common convention, so the subdiagonal convention should be specified when giving entries.

Completing the square rewrites a quadratic polynomial so that its minimum or maximum and its roots of a polynomial become easy to read. The linear term is absorbed into a shift of the variable; the resulting polynomial identity changes the description, rather than the values of the polynomial.

For coefficients $a,b,c$ in the real numbers, with $a\ne 0$,First factor out the leading coefficient from $a{x}^2+bx$, then add and subtract $(b/(2a){)}^2$ inside the bracket. The cross term in $(x+b/(2a){)}^2$ is $(b/a)x$, exactly the term needed. Multiplication by $a$ restores $bx$. Thus the half-coefficient is $b/(2a)$, rather than $b/2$ unless the quadratic polynomial is a monic polynomial. Expanding the right-hand side verifies the polynomial identity directly.^[ref]

For an original example,For every $x$ in the real numbers, $(x+3{)}^2\ge 0$, with equality only at $x=-3$. The minimum is therefore $4$, reached at $-3$; no calculus is needed, and there are no roots of a polynomial in the real numbers. The expanded coefficients conceal these conclusions more effectively than the completed square does.

Partitioning the roots of $X^n-1$ by their exact orders givesInductively, the product over proper divisors is a monic polynomial in $\mathbb{Z}[X]$. Division of $X^n-1$ by this monic polynomial stays in $\mathbb{Z}[X]$ and has zero remainder, proving that ${\Phi }_n\in \mathbb{Z}[X]$.

The $k$th elementary symmetric polynomial adds every product obtained by choosing $k$ distinct positions from $x_1,\dots ,x_n$:The conventions are $e_0=1$ and $e_k=0$ for $k>n$. The positions must be distinct, but their values may coincide. Each permutation of the variables merely rearranges the summands, so this is a symmetric polynomial.

For $x_1=1$, $x_2=2$, $x_3=3$, we obtain $e_1=1+2+3=6$, $e_2=1\cdot 2+1\cdot 3+2\cdot 3=11$, and $e_3=1\cdot 2\cdot 3=6$. Expanding the product givesIn general, ${\prod }_{i=1}^n(z-x_i)=z^n-e_1{z}^{n-1}+e_2{z}^{n-2}-\cdots +(-1{)}^n{e}_n$. Thus the coefficients of a monic polynomial collect elementary symmetric polynomials of its roots of a polynomial, with alternating signs. These are the Vieta formulas.^[ref]

An element $x$ of an $A$-algebra is an integral element precisely when $A[x]$ is a finite $A$-module. More generally, a finite $A$-submodule containing one and stable under multiplication by $x$ proves integrality by the determinant trick. Conversely a monic polynomial equation reduces all powers of $x$ to finitely many generators.

Gaussian quadrature is a quadrature rule that chooses both sample locations and coefficients to achieve unusually high polynomial exactness. For a finite interval $[a,b]$ with $a<b$, assume the integration weight $w$ is integrable and positive almost everywhere. DefineLet $p_n$ be the monic orthogonal polynomial of polynomial degree $n$ for the inner product $⟨u,v{⟩}_w={\int }_a^{b}u(x)v(x)w(x)dx$: it satisfies $⟨p_n,q{⟩}_w=0$ for every polynomial $q$ of polynomial degree below $n$. The polynomial roots of $p_n$ are distinct and inside $(a,b)$; take them as the nodes $x_i$. Integrate the Lagrange cardinal polynomials ${\ell }_i$ to obtain $A_i=I_w({\ell }_i)$. These coefficients are positive, andThe integration weight $w(x)$ and the discrete coefficients $A_i$ play different roles: $w$ specifies the integral being approximated, while $A_i$ tell us how much each sample contributes.^[ref]

A proof outline explains the gain over simply integrating an arbitrary polynomial interpolation. Use polynomial division to write $f=p_{n}q+r$, with $\mathrm{deg}q\le n-1$ and $\mathrm{deg}r\le n-1$. Orthogonality makes $I_w(p_{n}q)=0$, and sampling at the polynomial roots of $p_n$ makes $Q_n(p_{n}q)=0$. The Lagrange cardinal polynomials recover $r$ exactly, so both expressions agree. Also $A_i=Q_n({\ell }_i^2)=I_w({\ell }_i^2)>0$, since ${\ell }_i^2$ has polynomial degree $2n-2$. This is the mechanism behind positive weights of Gaussian quadrature.

For a concrete two-node example, set $w=1$ on $[-1,1]$. The Legendre polynomial $P_2(x)=(3x^2-1)/2$ has polynomial roots $x=\pm 1/\sqrt{3}$. Its monic polynomial version $p_2=x^2-1/3$ has zero integral against both $1$ and $x$, as required. Symmetry and exactness for the constant polynomial give $A_1=A_2=1$. Thus the Gauss–Legendre instance of Gaussian quadrature isDirect evaluation on $1,x,x^2,x^3$ gives $2,0,2/3,0$, exactly their integrals. For the polynomial $f(x)=1+x+x^2+x^3$, two samples therefore give $8/3$ exactly. But for $x^4$ the rule gives $2/9$, whereas the integral is $2/5$: the error $I_1-Q_2$ is $8/45$.

The ceiling $2n-1$ is sharp for $n$ distinct real nodes under the positive-weight assumptions. Their squared nodal polynomial ${\prod }_i(x-x_i{)}^2$ has polynomial degree $2n$, is zero at every sample, and has a strictly positive weighted integral. Thus no such quadrature rule integrates every polynomial of polynomial degree $2n$ exactly. Nor does Gaussian quadrature integrate every nonpolynomial function exactly: the same two-node example gives $Q_2(|x|)=2/\sqrt{3}$, while $I_1(|x|)=1$.

Gaussian quadrature is useful when evaluations are costly and a modest polynomial captures the integrand well. More precisely, for a continuous function $f$ and any polynomial $r$ of polynomial degree at most $2n-1$, positivity and constant exactness giveThe uniform norm on $[a,b]$ measures the approximation between samples. This bound connects quadrature rule accuracy to uniform approximation, rather than promising an error from sample count alone. Corners, sharp unresolved features and roundoff error require their own assessment; the absolute value function example already shows why polynomial exactness is a qualified guarantee.

A nonzero quotient of an $r$-variable Laurent polynomial ring is finite over an embedded Laurent polynomial ring in $m\le r$ variables. Given a nonzero Laurent relation, choose $N$ so that weights $(N,N^2,\dots ,N^{r-1},1)$ separate its finite exponent support. The displayed invertible monomial substitution makes its extreme $Y_r$ coefficients units in the remaining Laurent variables. Normalize the relation to a monic polynomial with unit constant term; both $Y_r$ and $Y_r^{-1}$ are integral over the image of the $(r-1)$-variable subring. Induction and transitivity of finite extensions prove the assertion, over finite fields as well as infinite fields. An infinite-dimensional quotient has $m\ge 1$.

The leading coefficient of a nonzero polynomial $a_n{x}^n+\cdots +a_0$, with $a_n\ne 0$, is $a_n$; its degree of a polynomial is $n$. A monic polynomial has leading coefficient one. For polynomials over a field, a product has leading coefficient equal to the product of the two leading coefficients, which prevents cancellation of their highest-degree terms.

For a square matrix over a field, the minimal polynomial $m_A$ is the unique monic polynomial of least degree satisfying $m_A(A)=0$. The Cayley-Hamilton theorem guarantees at least one such polynomial: the characteristic polynomial. The minimal polynomial divides every polynomial that annihilates $A$, so reducing matrix powers modulo $m_A$ can need fewer coefficients than reducing modulo the characteristic polynomial.

For example, $2I_2$ has minimal polynomial $t-2$, whereas the Jordan block $\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$ has minimal polynomial $(t-2{)}^2$. Both have the same characteristic polynomial. Their different matrix powers are illustrated in repeated eigenvalues in the Cayley-Hamilton theorem.

On a real or complex inner product space of finite dimension, a normal operator has a square-free polynomial as its minimal polynomial. To prove this without the spectral theorem, suppose an irreducible polynomial $f$ occurs at least twice in $m_T$. Put $h=m_T/f^2$ and $N=f(T)$. Since polynomials of a normal operator are normal, $N$ is a normal operator. For every $v$,By kernel stabilization for a normal operator, $Nh(T)v=0$. Hence the smaller-degree monic polynomial $m_T/f$ annihilates $T$, contradicting minimality.

Over the complex numbers, all irreducible polynomials are linear, so the primary decomposition theorem for linear maps now gives a basis of eigenvectors. Over the real numbers, irreducible quadratics can remain: a nontrivial planar rotation need not have any real eigenvectors, although its minimal polynomial is square-free.

For any commutative ring $A$ and a monic polynomial $F$ of positive degree $D$, monic polynomial division over a ring gives unique representatives of degree less than $D$. Thus the classes of $1,T,\dots ,T^{D-1}$ form a basis of a module over $A$. This is a finite free algebra, hence flat, and the map $A\to A[T]/(F)$ is injective. The monic hypothesis makes leading-degree arguments valid even when $A$ has zero divisors.

For a monic polynomial $p(x)={\prod }_i(x-a_i)$ with distinct ordered real roots of a polynomial, each critical point $\xi$ lies between two consecutive roots by Rolle's theorem. Its logarithmic derivative gives ${\sum }_i(\xi -a_i{)}^{-1}=0$. Implicit differentiation gives the displayed formula, so moving any root to the right moves every ordered critical point to the right, while the roots remain distinct. Iterating this statement for derivatives preserves componentwise ordering of their roots. Weak inequalities extend by continuity to repeated roots.

The polynomial identities remain true in positive characteristic of a field, but recovering elementary symmetric polynomials by division can fail. In the prime field ${\mathbb{F}}_2$ of characteristic two, the root lists $(0,0)$ and $(1,1)$ have the same power sum zero for every positive exponent: $0^k+0^k=0$ and $1^k+1^k=0$. Their monic polynomials differ, however: $z^2$ and $(z-1{)}^2=z^2+1$. Thus even all positive power sums need not determine the polynomial when its degree meets the characteristic. The relation $2e_2=e_1{p}_1-p_2$ becomes $0=0$ and supplies no value for $e_2$.

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.

To normalize $k[a_1,\dots ,a_n]$ over an arbitrary field, choose a nonzero polynomial relation and a base $M$ larger than all its exponents. The substitutions $b_i=a_i-a_n^{M^i}$ give distinct top weights to its monomials, so its highest power of $a_n$ has a nonzero scalar coefficient. It becomes a monic polynomial equation, making the algebra finite over $k[b_1,\dots ,b_{n-1}]$. Induction proves the Noether normalization lemma, including over finite fields.

Assume a positive even weight on a symmetric domain has finite polynomial moments. Subtracting the orthogonal projection onto a finite-dimensional subspace of $x^n$ onto the lower-degree polynomials gives the unique monic orthogonal polynomial. Reflection produces another such monic polynomial, $(-1{)}^n{\varphi }_n(-x)$, so uniqueness gives the parity identity. Every coefficient with the opposite parity to its degree therefore vanishes.

Write a rational root of a polynomial as $\gamma =a/b$ in lowest terms with $b>0$. Substituting into the monic integer-coefficient polynomial and multiplying by $b^d$ givesEvery term other than $a^d$ is divisible by $b$, so $b\mid a^d$. But $\gcd (a,b)=1$ implies $\gcd (a^d,b)=1$, and hence $b=1$. ThusThis is the monic case of the rational root theorem. The monic polynomial assumption is essential because it removes any leading coefficient that could supply prime factors of the denominator.