Polynomial ring

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) 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 ring theory and algebraic geometry. 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.

The polynomial ring, K[X], in X over a field (or, more generally, a commutative ring) K can be defined[1] (there are other equivalent definitions that are commonly used) as the set of expressions, called polynomials in X, of the form

Two polynomials are equal when the corresponding coefficients of each Xk 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 may be used for defining 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

In these formulas, the polynomials p and q are extended by adding "dummy terms" with zero coefficients, so that all pi and qi that appear in the formulas are defined. Specifically, if m < n, then pi = 0 for m < in.

The scalar multiplication is the special case of the multiplication where p = p0 is reduced to its constant term (the term that is independent of X); that is

It is straightforward to verify that these three operations satisfy the axioms of a commutative algebra over K. Therefore, polynomial rings are also called polynomial algebras.

Another equivalent definition is often preferred, although less intuitive, because it is easier to make it completely rigorous, which consists in defining a polynomial as an infinite sequence (p0, p1, p2, ...) of elements of K, having the property that only a finite number of the elements are nonzero, or equivalently, a sequence for which there is some m so that pn = 0 for n > m. In this case, p0 and X are considered as alternate notations for the sequences (p0, 0, 0, ...) and (0, 1, 0, 0, ...), respectively. A straightforward use of the operation rules shows that the expression

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,[6] defined to be –1,[7] or defined to be a –∞.[8]

A constant polynomial is either the zero polynomial, or a polynomial of degree zero.

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

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.

Over a field, every nonzero polynomial is associated to a unique monic polynomial.

Given two polynomials, p and q, one says that p divides q, p is a divisor of q, or q is a multiple of p, if there is a polynomial r such that q = pr.

A polynomial is irreducible if it is not the product of two non-constant polynomials, or equivalently, if its divisors are either constant polynomials or have the same degree.

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 for 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

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

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

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 consider 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 (excepts 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

The unique factorization property results from Euclid's lemma. In the case of integers, this is the fundamental theorem of arithmetic. In the case of K[X], it may be stated as: In other terms K[X] is a unique factorization domain. If K is the field of complex numbers, the fundamental theorem of algebra asserts that a univariate polynomial is irreducible if and only if its degree is one. In this case the unique factorization property can be restated as: Xr; this decomposition is unique up to the order of the factors. For each factor, r is a root of the polynomial, and the number of occurrences of a factor is the multiplicity of the corresponding root.

every non-constant polynomial can be expressed in a unique way as the product of a constant, and one or several irreducible monic polynomials; this decomposition is unique up to the order of the factors.every non-constant univariate polynomial over the complex numbers can be expressed in a unique way as the product of a constant, and one or several polynomials of the form

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 for factorizing them in polynomial time. This is the basis of the RSA cryptosystem, widely used for secure Internet communications.

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.

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 for θ in every polynomial. That is,

The image of this evaluation homomorphism is the subalgebra generated by x, 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 for θ. This ideal consists of all multiples of some monic polynomial, that is called the minimal polynomial of x. The term minimal is motivated by the fact that its degree is minimal among the degrees of the elements of the ideal.

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.

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

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

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

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

with coefficients in K. The degree of a nonzero polynomial is the maximum of the degrees of its monomials with nonzero coefficients.

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.

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.

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

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.

which results from the distributivity and associativity of ring operations.

that maps each indeterminate to itself. (This isomorphism is often written as an equality, which is justified by the fact that polynomial rings are defined up to a unique isomorphism.)

In other words, a multivariate polynomial ring can be considered as a univariate polynomial over a smaller polynomial ring. This is commonly used for proving properties of multivariate polynomial rings, by induction on the number of indeterminates.

Polynomial rings in several variables over a field are fundamental in invariant theory and algebraic geometry. Some of their properties, such as those described above can be reduced to the case of a single indeterminate, but this is not always the case. In particular, because of the geometric applications, many interesting properties must be invariant under affine or projective transformations of the indeterminates. This often implies that one cannot select one of the indeterminates for a recurrence on the indeterminates.

Bézout's theorem, Hilbert's Nullstellensatz and Jacobian conjecture are among the most famous properties that are specific to multivariate polynomials over a field.

The Nullstellensatz, has three main versions, each being a corollary of any other. Two of these versions are given below. For the third version, the reader is referred to the main article on the Nullstellensatz.

Bézout's theorem may be viewed as a multivariate generalization of the version of the fundamental theorem of algebra that asserts that a univariate polynomial of degree n has n complex roots, if they are counted with their multiplicities.

In the case of bivariate polynomials, it states that two polynomials of degrees d and e in two variables, which have no common factors of positive degree, have exactly de common zeros in an algebraically closed field containing the coefficients, if the zeros are counted with their multiplicity and include the zeros at infinity.

Polynomial rings can be generalized in a great many ways, including polynomial rings with generalized exponents, power series rings, noncommutative polynomial rings, skew polynomial rings, and polynomial rigs.

One slight generalization of polynomial rings is to allow for infinitely many indeterminates. Each monomial still involves only a finite number of indeterminates (so that its degree remains finite), and each polynomial is a still a (finite) linear combination of monomials. Thus, any individual polynomial involves only finitely many indeterminates, and any finite computation involving polynomials remains inside some subring of polynomials in finitely many indeterminates. This generalization has the same property of usual polynomial rings, of being the free commutative algebra, the only difference is that it is a free object over an infinite set.

One can also consider a strictly larger ring, by defining as a generalized polynomial an infinite (or finite) formal sum of monomials with a bounded degree. This ring is larger than the usual polynomial ring, as it includes infinite sums of variables. However, it is smaller than the ring of power series in infinitely many variables. Such a ring is used for constructing the ring of symmetric functions over an infinite set.

A simple generalization only changes the set from which the exponents on the variable are drawn. The formulas for addition and multiplication make sense as long as one can add exponents: Xi · Xj = Xi+j. A set for which addition makes sense (is closed and associative) is called a monoid. The set of functions from a monoid N to a ring R which are nonzero at only finitely many places can be given the structure of a ring known as R[N], the monoid ring of N with coefficients in R. The addition is defined component-wise, so that if c = a + b, then cn = an + bn for every n in N. The multiplication is defined as the Cauchy product, so that if c = a · b, then for each n in N, cn is the sum of all aibj where i, j range over all pairs of elements of N which sum to n.

When N is commutative, it is convenient to denote the function a in R[N] as the formal sum:

and then the formulas for addition and multiplication are the familiar:

Some authors such as (Lang 2002, II,§3) go so far as to take this monoid definition as the starting point, and regular single variable polynomials are the special case where N is the monoid of non-negative integers. Polynomials in several variables simply take N to be the direct product of several copies of the monoid of non-negative integers.

Several interesting examples of rings and groups are formed by taking N to be the additive monoid of non-negative rational numbers, (Osbourne 2000, §4.4). See also Puiseux series.

Power series generalize the choice of exponent in a different direction by allowing infinitely many nonzero terms. This requires various hypotheses on the monoid N used for the exponents, to ensure that the sums in the Cauchy product are finite sums. Alternatively, a topology can be placed on the ring, and then one restricts to convergent infinite sums. For the standard choice of N, the non-negative integers, there is no trouble, and the ring of formal power series is defined as the set of functions from N to a ring R with addition component-wise, and multiplication given by the Cauchy product. The ring of power series can also be seen as the ring completion of the polynomial ring with respect to the ideal generated by x.

For polynomial rings of more than one variable, the products X·Y and Y·X are simply defined to be equal. A more general notion of polynomial ring is obtained when the distinction between these two formal products is maintained. Formally, the polynomial ring in n noncommuting variables with coefficients in the ring R is the monoid ring R[N], where the monoid N is the free monoid on n letters, also known as the set of all strings over an alphabet of n symbols, with multiplication given by concatenation. Neither the coefficients nor the variables need commute amongst themselves, but the coefficients and variables commute with each other.

Just as the polynomial ring in n variables with coefficients in the commutative ring R is the free commutative R-algebra of rank n, the noncommutative polynomial ring in n variables with coefficients in the commutative ring R is the free associative, unital R-algebra on n generators, which is noncommutative when n > 1.

Other generalizations of polynomials are differential and skew-polynomial rings.

A differential polynomial ring is a ring of differential operators formed from a ring R and a derivation δ of R into R. This derivation operates on R, and will be denoted X, when viewed as an operator. The elements of R also operate on R by multiplication. The composition of operators is denoted as the usual multiplication. It follows that the relation δ(ab) = (b) + δ(a)b may be rewritten as

This relation may be extended to define a skew multiplication between two polynomials in X with coefficients in R, which make them a non-commutative ring.

The skew-polynomial ring is defined similarly for a ring R and a ring endomorphism f of R, by extending the multiplication from the relation X·r = f(rX to produce an associative multiplication that distributes over the standard addition. More generally, given a homomorphism F from the monoid N of the positive integers into the endomorphism ring of R, the formula Xn·r = F(n)(rXn allows constructing a skew-polynomial ring.(Lam 2001, §1,ex 1.11) Skew polynomial rings are closely related to crossed product algebras.

The definition of a polynomial ring can be generalised by relaxing the requirement that the algebraic structure R be a field or a ring to the requirement that R only be a semifield or rig; the resulting polynomial structure/extension R[X] is a polynomial rig. For example, the set of all multivariate polynomials with natural number coefficients is a polynomial rig.