Polynomial ring

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates (traditionally also called variables) with coefficients in another ring, often a field.

Often, the term "polynomial ring" refers implicitly to the special case of a polynomial ring in one indeterminate over a field. The importance of such polynomial rings relies on the high number of properties that they have in common with the ring of the integers.

Polynomial rings occur and are often fundamental in many parts of mathematics such as number theory, commutative algebra, and algebraic geometry. In ring theory, many classes of rings, such as unique factorization domains, regular rings, group rings, rings of formal power series, Ore polynomials, graded rings, have been introduced for generalizing some properties of polynomial rings.

A closely related notion is that of the ring of polynomial functions on a vector space, and, more generally, ring of regular functions on an algebraic variety.

Let K be a field or (more generally) a commutative ring.

The polynomial ring in X over K, which is denoted K[X], can be defined in several equivalent ways. One of them is to define K[X] as the set of expressions, called polynomials in X, of the form

\(p = p_0 + p_1 X + p_2 X^2 + \cdots + p_{m - 1} X^{m - 1} + p_m X^m,\)

where m is a nonnegative integer, the coefficients p₀, p₁, ..., p_m of p are elements of K, and X, X, …, are symbols called "powers" of X that follow the usual rules of exponents: X = 1, X = X, and \(X^k \cdot X^l = X^{k+l}\) for any nonnegative integers k and l. The symbol X is called an indeterminate or variable. (The term of "variable" comes from the terminology of polynomial functions. However, here, X has no value (other than itself), and cannot vary, being a constant in the polynomial ring.)

Two polynomials are equal when the corresponding coefficients of each X are equal.

One can think of the ring K[X] as arising from K by adding one new element X that is external to K, commutes with all elements of K, and has no other specific properties. This can be used for an equivalent definition of polynomial rings.

The polynomial ring in X over K is equipped with an addition, a multiplication and a scalar multiplication that make it a commutative algebra. These operations are defined according to the ordinary rules for manipulating algebraic expressions. Specifically, if

\(p = p_0 + p_1 X + p_2 X^2 + \cdots + p_m X^m,\)

and

\(q = q_0 + q_1 X + q_2 X^2 + \cdots + q_n X^n,\)

\(p + q = r_0 + r_1 X + r_2 X^2 + \cdots + r_k X^k,\)

\(pq = s_0 + s_1 X + s_2 X^2 + \cdots + s_l X^l,\)

\(r_i = p_i + q_i\)

\(s_i = p_0 q_i + p_1 q_{i-1} + \cdots + p_i q_0.\)

\(p_0\left(q_0 + q_1 X + \dots + q_n X^n\right) = p_0 q_0 + \left(p_0 q_1\right)X + \cdots + \left(p_0 q_n\right)X^n\)

\(p_0 + p_1 X + p_2 X^2 + \cdots + p_m X^m\)

(p₀, p₁, p₂, …, p_m, 0, 0, …).

Condensed: the full section is in Wikipedia.

Let

\(p = p_0 + p_1 X + p_2 X^2 + \cdots + p_{m - 1} X^{m - 1} + p_m X^m,\)

be a nonzero polynomial with \(p_m\ne 0\).

• The constant term of p is \(p_0.\) It is zero in the case of the zero polynomial.
• The degree of p, written deg(p), is the largest number k such that the coefficient of X is not zero.
• The leading coefficient of p is \(p_m.\)
• In the special case of the zero polynomial, all of whose coefficients are zero, the leading coefficient is undefined, and the degree has been variously left undefined, defined to be −1, or defined to be a −∞.
• A constant polynomial is either the zero polynomial, or a polynomial of degree zero.
• A nonzero polynomial is monic if its leading coefficient is \(1.\)

Given two polynomials p and q, if the degree of the zero polynomial is defined to be \(-\infty,\) one has

\(\deg(p+q) \le \max (\deg(p), \deg (q)),\)

and, over a field, or more generally an integral domain,

\(\deg(pq) = \deg(p) + \deg(q).\)

It follows immediately that, if K is an integral domain, then so is K[X].

It follows also that, if K is an integral domain, a polynomial is a unit (that is, it has a multiplicative inverse) if and only if it is constant and is a unit in K.

Two polynomials are associated if either one is the product of the other by a unit.

Condensed: the full section is in Wikipedia.

Let K be a field or, more generally, a commutative ring, and R a ring containing K. For any polynomial P in K[X] and any element a in R, the substitution of X with a in P defines an element of R, which is denoted P(a). This element is obtained by carrying on in R after the substitution the operations indicated by the expression of the polynomial. This computation is called the evaluation of P at a. For example, if we have

\(P = X^2 - 1,\)

we have

\(\begin{align} P(3) &= 3^2-1 = 8, \\ P(X^2+1) &= \left(X^2 + 1\right)^2 - 1 = X^4 + 2X^2 \end{align}\)

(in the first example R = K, and in the second one R = K[X]). Substituting X for itself results in

\(P = P(X),\)

explaining why the sentences "Let P be a polynomial" and "Let P(X) be a polynomial" are equivalent.

The polynomial function defined by a polynomial P is the function from K into K that is defined by \(x\mapsto P(x).\) If K is an infinite field, two different polynomials define different polynomial functions, but this property is false for finite fields. For example, if K is a field with q elements, then the polynomials 0 and X − X both define the zero function.

For every a in R, the evaluation at a, that is, the map \(P \mapsto P(a)\) defines an algebra homomorphism from K[X] to R, which is the unique homomorphism from K[X] to R that fixes K, and maps X to a. In other words, K[X] has the following universal property:

For every ring R containing K, and every element a of R, there is a unique algebra homomorphism from K[X] to R that fixes K, and maps X to a.

As for all universal properties, this defines the pair (K[X], X) up to a unique isomorphism, and can therefore be taken as a definition of K[X].

Condensed: the full section is in Wikipedia.

If K is a field, the polynomial ring K[X] has many properties that are similar to those of the ring of integers \(\Z.\) Most of these similarities result from the similarity between the long division of integers and the long division of polynomials.

Most of the properties of K[X] that are listed in this section do not remain true if K is not a field, or if one considers polynomials in several indeterminates.

Like for integers, the Euclidean division of polynomials has a property of uniqueness. That is, given two polynomials a and b ≠ 0 in K[X], there is a unique pair (q, r) of polynomials such that a = bq + r, and either r = 0 or deg(r) < deg(b). This makes K[X] a Euclidean domain. However, most other Euclidean domains (except integers) do not have any property of uniqueness for the division nor an easy algorithm (such as long division) for computing the Euclidean division.

The Euclidean division is the basis of the Euclidean algorithm for polynomials that computes a polynomial greatest common divisor of two polynomials. Here, "greatest" means "having a maximal degree" or, equivalently, being maximal for the preorder defined by the degree. Given a greatest common divisor of two polynomials, the other greatest common divisors are obtained by multiplication by a nonzero constant (that is, all greatest common divisors of a and b are associated). In particular, two polynomials that are not both zero have a unique greatest common divisor that is monic (leading coefficient equal to 1).

The extended Euclidean algorithm allows computing (and proving) Bézout's identity. In the case of K[X], it may be stated as follows. Given two polynomials p and q of respective degrees m and n, if their monic greatest common divisor g has the degree d, then there is a unique pair (a, b) of polynomials such that

\(ap + bq = g,\)

and

\(\deg (a) \le n-d, \quad \deg(b) < m-d.\)

(For making this true in the limiting case where m = d or n = d, one has to define as negative the degree of the zero polynomial. Moreover, the equality \(\deg (a)= n-d\) can occur only if p and q are associated.) The uniqueness property is rather specific to K[X]. In the case of the integers the same property is true, if degrees are replaced by absolute values, but, for having uniqueness, one must require a > 0.

Condensed: the full section is in Wikipedia.

The (formal) derivative of the polynomial

\(a_0+a_1X+a_2X^2+\cdots+a_nX^n\)

is the polynomial

\(a_1+2a_2X+\cdots+na_nX^{n-1}.\)

In the case of polynomials with real or complex coefficients, this is the standard derivative. The above formula defines the derivative of a polynomial even if the coefficients belong to a ring on which no notion of limit is defined. The derivative makes the polynomial ring a differential algebra.

The existence of the derivative is one of the main properties of a polynomial ring that is not shared with integers, and makes some computations easier on a polynomial ring than on integers.

Except for factorization, all previous properties of K[X] are effective, since their proofs, as sketched above, are associated with algorithms for testing the property and computing the polynomials whose existence are asserted. Moreover these algorithms are efficient, as their computational complexity is a quadratic function of the input size.

The situation is completely different for factorization: the proof of the unique factorization does not give any hint for a method for factorizing. Already for the integers, there is no known algorithm running on a classical (non-quantum) computer for factorizing them in polynomial time. This is the basis of the RSA cryptosystem, widely used for secure Internet communications.

In the case of K[X], the factors, and the methods for computing them, depend strongly on K. Over the complex numbers, the irreducible factors (those that cannot be factorized further) are all of degree one, while, over the real numbers, there are irreducible polynomials of degree 2, and, over the rational numbers, there are irreducible polynomials of any degree. For example, the polynomial \(X^4-2\) is irreducible over the rational numbers, but is factored as \((X - \sqrt[4]2)(X+\sqrt[4]2)(X^2+\sqrt 2)\) over the real numbers and as \((X-\sqrt[4]2)(X+\sqrt[4]2)(X-i\sqrt[4]2)(X+i\sqrt[4]2)\) over the complex numbers.

The existence of a factorization algorithm depends also on the ground field. In the case of the real or complex numbers, Abel-Ruffini theorem shows that the roots of some polynomials, and thus the irreducible factors, cannot be computed exactly. Therefore, a factorization algorithm can compute only approximations of the factors. Various algorithms have been designed for computing such approximations, see Root finding of polynomials.

There is an example of a field K such that there exist exact algorithms for the arithmetic operations of K, but there cannot exist any algorithm for deciding whether a polynomial of the form \(X^p - a\) is irreducible or is a product of polynomials of lower degree.

On the other hand, over the rational numbers and over finite fields, the situation is better than for integer factorization, as there are factorization algorithms that have a polynomial complexity. They are implemented in most general purpose computer algebra systems.

If θ is an element of an associative K-algebra L, the polynomial evaluation at θ is the unique algebra homomorphism φ from K[X] into L that maps X to θ and does not affect the elements of K itself (it is the identity map on K). It consists of substituting X with θ in every polynomial. That is,

\(\varphi\left(a_m X^m + a_{m - 1} X^{m - 1} + \cdots + a_1 X + a_0\right) = a_m \theta^m + a_{m - 1} \theta^{m - 1} + \cdots + a_1 \theta + a_0.\)

The image of this evaluation homomorphism is the subalgebra generated by θ, which is necessarily commutative. If φ is injective, the subalgebra generated by θ is isomorphic to K[X]. In this case, this subalgebra is often denoted by K[θ]. The notation ambiguity is generally harmless, because of the isomorphism.

If the evaluation homomorphism is not injective, this means that its kernel is a nonzero ideal, consisting of all polynomials that become zero when X is substituted with θ. This ideal consists of all multiples of some monic polynomial, that is called the minimal polynomial of θ. The term minimal is motivated by the fact that its degree is minimal among the degrees of the elements of the ideal.

There are two main cases where minimal polynomials are considered.

In field theory and number theory, an element θ of an extension field L of K is algebraic over K if it is a root of some polynomial with coefficients in K. The minimal polynomial over K of θ is thus the monic polynomial of minimal degree that has θ as a root. Because L is a field, this minimal polynomial is necessarily irreducible over K. For example, the minimal polynomial (over the reals as well as over the rationals) of the complex number i is \(X^2 + 1\). The cyclotomic polynomials are the minimal polynomials of the roots of unity.

In linear algebra, the n×n square matrices over K form an associative K-algebra of finite dimension (as a vector space). Therefore the evaluation homomorphism cannot be injective, and every matrix has a minimal polynomial (not necessarily irreducible). By Cayley-Hamilton theorem, the evaluation homomorphism maps to zero the characteristic polynomial of a matrix. It follows that the minimal polynomial divides the characteristic polynomial, and therefore that the degree of the minimal polynomial is at most n.

In the case of K[X], the quotient ring by an ideal can be built, as in the general case, as a set of equivalence classes. However, as each equivalence class contains exactly one polynomial of minimal degree, another construction is often more convenient.

Given a polynomial p of degree d, the quotient ring of K[X] by the ideal generated by p can be identified with the vector space of the polynomials of degrees less than d, with the "multiplication modulo p" as a multiplication, the multiplication modulo p consisting of the remainder under the division by p of the (usual) product of polynomials. This quotient ring is variously denoted as \(K[X]/pK[X],\) \(K[X]/\langle p \rangle,\) \(K[X]/(p),\) or simply \(K[X]/p.\)

The ring \(K[X]/(p)\) is a field if and only if p is an irreducible polynomial. In fact, if p is irreducible, every nonzero polynomial q of lower degree is coprime with p, and Bézout's identity allows computing r and s such that sp + qr = 1; so, r is the multiplicative inverse of q modulo p. Conversely, if p is reducible, then there exist polynomials a, b of degrees lower than deg(p) such that ab = p ; so a, b are nonzero zero divisors modulo p, and cannot be invertible.

For example, the standard definition of the field of the complex numbers can be summarized by saying that it is the quotient ring

\(\mathbb C =\mathbb R[X]/(X^2+1),\)

and that the image of X in \(\mathbb C\) is denoted by i. In fact, by the above description, this quotient consists of all polynomials of degree one in i, which have the form a + bi, with a and b in \(\mathbb R.\) The remainder of the Euclidean division that is needed for multiplying two elements of the quotient ring is obtained by replacing i by −1 in their product as polynomials (this is exactly the usual definition of the product of complex numbers). This construction of \(\C\) illustrates the more general construction of quadratic algebras as quotient rings over a monic, quadratic polynomial.

Let θ be an algebraic element in a K-algebra A. By algebraic, one means that θ has a minimal polynomial p. The first ring isomorphism theorem asserts that the substitution homomorphism induces an isomorphism of \(K[X]/(p)\) onto the image K[θ] of the substitution homomorphism. In particular, if A is a simple extension of K generated by θ, this allows identifying A and \(K[X]/(p).\) This identification is widely used in algebraic number theory.

The structure theorem for finitely generated modules over a principal ideal domain applies to K[X], when K is a field. This means that every finitely generated module over K[X] may be decomposed into a direct sum of a free module and finitely many modules of the form \(K[X]/\left\langle P^k \right\rangle\), where P is an irreducible polynomial over K and k a positive integer.

Given n symbols \(X_1, \dots, X_n,\) called indeterminates, a monomial (also called power product)

\(X_1^{\alpha_1}\cdots X_n^{\alpha_n}\)

is a formal product of these indeterminates, possibly raised to a nonnegative power. As usual, exponents equal to one and factors with a zero exponent can be omitted. In particular, \(X_1^0\cdots X_n^0 =1.\)

The tuple of exponents α = (α₁, …, α_n) is called the multidegree or exponent vector of the monomial. For a less cumbersome notation, the abbreviation

\(X^\alpha=X_1^{\alpha_1}\cdots X_n^{\alpha_n}\)

is often used. The degree of a monomial X, frequently denoted deg α or |α|, is the sum of its exponents:

\(\deg \alpha = \sum_{i=1}^n \alpha_i.\)

A polynomial in these indeterminates, with coefficients in a field K, or more generally a ring, is a finite linear combination of monomials

\(p = \sum_\alpha p_\alpha X^\alpha,\)

where the coefficients \(p_{\alpha}\) are elements of K. The degree of a nonzero polynomial is the maximum of the degrees of its monomials with nonzero coefficients.

The set of polynomials in \(X_1, \dots, X_n,\) denoted \(K[X_1,\dots, X_n],\) is thus a vector space (or a free module, if K is a ring) that has the monomials as a basis.

Condensed: the full section is in Wikipedia.

Addition and scalar multiplication of polynomials are those of a vector space or free module equipped by a specific basis (here the basis of the monomials). Explicitly, let \(p=\sum_{\alpha\in I}p_\alpha X^\alpha,\quad q=\sum_{\beta\in J}q_\beta X^\beta,\) where I and J are finite sets of exponent vectors.

The scalar multiplication of p and a scalar \(c\in K\) is

\(cp = \sum_{\alpha\in I}cp_\alpha X^\alpha.\)

The addition of p and q is

\(p+q = \sum_{\alpha\in I\cup J}(p_\alpha+q_\alpha) X^\alpha,\)

where \(p_\alpha=0\) if \(\alpha \not\in I,\) and \(q_\beta=0\) if \(\beta \not\in J.\) Moreover, if one has \(p_\alpha+q_\alpha=0\) for some \(\alpha \in I \cap J,\) the corresponding zero term is removed from the result.

The multiplication is

\(pq = \sum_{\gamma\in I+J}\left(\sum_{\alpha, \beta\mid \alpha+\beta=\gamma} p_\alpha q_\beta\right) X^\gamma,\)

where \(I+J\) is the set of the sums of one exponent vector in I and one other in J (usual sum of vectors). In particular, the product of two monomials is a monomial whose exponent vector is the sum of the exponent vectors of the factors.

The verification of the axioms of an associative algebra is straightforward.

A polynomial expression is an expression built with scalars (elements of K), indeterminates, and the operators of addition, multiplication, and exponentiation to nonnegative integer powers.

As all these operations are defined in \(K[X_1,\dots, X_n]\) a polynomial expression represents a polynomial, that is an element of \(K[X_1,\dots, X_n].\) The definition of a polynomial as a linear combination of monomials is a particular polynomial expression, which is often called the canonical form, normal form, or expanded form of the polynomial. Given a polynomial expression, one can compute the expanded form of the represented polynomial by expanding with the distributive law all the products that have a sum among their factors, and then using commutativity (except for the product of two scalars), and associativity for transforming the terms of the resulting sum into products of a scalar and a monomial; then one gets the canonical form by regrouping the like terms.

The distinction between a polynomial expression and the polynomial that it represents is relatively recent, and mainly motivated by the rise of computer algebra, where, for example, the test whether two polynomial expressions represent the same polynomial may be a nontrivial computation.

If K is a commutative ring, the polynomial ring K[X₁, …, X_n] has the following universal property: for every commutative K-algebra A, and every n-tuple (x₁, …, x_n) of elements of A, there is a unique algebra homomorphism from K[X₁, …, X_n] to A that maps each \(X_i\) to the corresponding \(x_i.\) This homomorphism is the evaluation homomorphism that consists in substituting \(X_i\) with \(x_i\) in every polynomial.

As it is the case for every universal property, this characterizes the pair \((K[X_1, \dots, X_n], (X_1, \dots, X_n))\) up to a unique isomorphism.

This may also be interpreted in terms of adjoint functors. More precisely, let SET and ALG be respectively the categories of sets and commutative K-algebras (here, and in the following, the morphisms are trivially defined). There is a forgetful functor \(\mathrm F: \mathrm{ALG}\to \mathrm{SET}\) that maps algebras to their underlying sets. On the other hand, the map \(X\mapsto K[X]\) defines a functor \(\mathrm{POL}: \mathrm{SET}\to \mathrm{ALG}\) in the other direction. (If X is infinite, K[X] is the set of all polynomials in a finite number of elements of X.)

The universal property of the polynomial ring means that F and POL are adjoint functors. That is, there is a bijection

\(\operatorname{Hom}_{\mathrm {SET}}(X,\operatorname{F}(A))\cong \operatorname{Hom}_{\mathrm {ALG}}(K[X], A).\)

This may be expressed also by saying that polynomial rings are free commutative algebras, since they are free objects in the category of commutative algebras. Similarly, a polynomial ring with integer coefficients is the free commutative ring over its set of variables, since commutative rings and commutative algebras over the integers are the same thing.