Editing Polynomial ring (section)

== Univariate polynomials over a field ==
If {{mvar|K}} is a [[field (mathematics)|field]], the polynomial ring {{math|''K''[''X'']}} has many properties that are similar to those of the [[ring (mathematics)|ring]] of integers <math>\Z.</math> Most of these similarities result from the similarity between the [[long division|long division of integers]] and the [[polynomial long division|long division of polynomials]].

Most of the properties of {{math|''K''[''X'']}} that are listed in this section do not remain true if {{mvar|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 {{mvar|a}} and {{math|''b'' ≠ 0}} in {{math|''K''[''X'']}}, there is a unique pair {{math|(''q'', ''r'')}} of polynomials such that {{math|1=''a'' = ''bq'' + ''r''}}, and either {{math|1=''r'' = 0}} or {{math|deg(''r'') < deg(''b'')}}. This makes {{math|''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 {{mvar|a}} and {{mvar|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 {{val|1}}).

The [[extended Euclidean algorithm]] allows computing (and proving) [[Bézout's identity]]. In the case of {{math|''K''[''X'']}}, it may be stated as follows. Given two polynomials {{mvar|p}} and {{mvar|q}} of respective degrees {{mvar|m}} and {{mvar|n}}, if their monic greatest common divisor {{mvar|g}} has the degree {{mvar|d}}, then there is a unique pair {{math|(''a'', ''b'')}} of polynomials such that
:<math>ap + bq = g,</math>
and
:<math>\deg (a) \le n-d, \quad \deg(b) < m-d.</math>
(For making this true in the limiting case where {{math|1=''m'' = ''d''}} or {{math|1=''n'' = ''d''}}, one has to define as negative the degree of the zero polynomial. Moreover, the equality <math>\deg (a)= n-d</math> can occur only if {{mvar|p}} and {{math|q}} are associated.) The uniqueness property is rather specific to {{math|''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 {{math|''a'' > 0}}.

[[Euclid's lemma]] applies to {{math|''K''[''X'']}}. That is, if {{mvar|a}} divides {{mvar|bc}}, and is [[coprime]] with {{mvar|b}}, then {{mvar|a}} divides {{mvar|c}}. Here, ''coprime'' means that the monic greatest common divisor is {{val|1}}. ''Proof:'' By hypothesis and Bézout's identity, there are {{mvar|e}}, {{mvar|p}}, and {{mvar|q}} such that {{math|1=''ae'' = ''bc''}} and {{math|1=1 = ''ap'' + ''bq''}}. So 
<math>c=c(ap+bq)=cap+aeq=a(cp+eq).</math>

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 {{math|''K''[''X'']}}, it may be stated as: ''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.'' In other terms {{math|''K''[''X'']}} is a [[unique factorization domain]]. If {{mvar|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: ''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'' {{math|''X'' − ''r''}}; ''this decomposition is unique up to the order of the factors.'' For each factor, {{mvar|r}} is a [[root of a function|root]] of the polynomial, and the number of occurrences of a factor is the [[multiplicity (mathematics)|multiplicity]] of the corresponding root.

===Derivation===
{{main|Formal derivative|Derivation (differential algebra)}}
The [[formal derivative|(formal) derivative]] of the polynomial
:<math>a_0+a_1X+a_2X^2+\cdots+a_nX^n</math>
is the polynomial
:<math>a_1+2a_2X+\cdots+na_nX^{n-1}.</math>
In the case of polynomials with [[real number|real]] or [[complex number|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 (mathematics)|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.

====Square-free factorization====
{{main|Square-free polynomial}}

A polynomial with coefficients in a field or integral domain is ''square-free'' if it does not have a [[multiple root]] in the [[algebraically closed field]] containing its coefficients. In particular, a polynomial of degree {{mvar|n}} with real or complex coefficients is square-free if it has {{mvar|n}} distinct complex roots. Equivalently, a polynomial over a field is square-free if and only if the [[Polynomial greatest common divisor|greatest common divisor]] of the polynomial and its derivative is {{math|1}}.

A ''square-free factorization'' of a polynomial is an expression for that polynomial as a product of powers of [[pairwise relatively prime]] square-free factors. Over the real numbers (or any other field of [[characteristic 0]]), such a factorization can be computed efficiently by [[Yun's algorithm]]. Less efficient algorithms are known for [[Factorization_of_polynomials_over_finite_fields#Square-free_factorization|square-free factorization of polynomials over finite fields]].

====Lagrange interpolation====
{{main|Lagrange polynomial}}

Given a finite set of ordered pairs <math>(x_j, y_j)</math> with entries in a field and distinct values <math>x_j</math>, among the polynomials <math>f(x)</math> that interpolate these points (so that <math>f(x_j) = y_j</math> for all <math>j</math>), there is a unique polynomial of smallest degree.  This is the ''Lagrange interpolation polynomial'' <math>L(x)</math>. If there are <math>k</math> ordered pairs, the degree of <math>L(x)</math> is at most <math>k - 1</math>.  The polynomial <math>L(x)</math> can be computed explicitly in terms of the input data <math>(x_j, y_j)</math>.

====Polynomial decomposition====
{{main|Polynomial decomposition}}

A ''decomposition'' of a polynomial is a way of expressing it as a [[function composition|composition]] of other polynomials of degree larger than 1. A polynomial that cannot be decomposed is ''indecomposable''. [[Ritt's polynomial decomposition theorem]] asserts that if <math>f = g_1 \circ g_2 \circ \cdots \circ g_m = h_1 \circ h_2 \circ \cdots\circ h_n</math> are two different decompositions of the polynomial <math>f</math>, then <math>m = n</math> and the degrees of the indecomposables in one decomposition are the same as the degrees of the indecomposables in the other decomposition (though not necessarily in the same order).

=== Factorization ===
{{main|Polynomial factorization}}

Except for factorization, all previous properties of {{math|''K''[''X'']}} are [[effective proof|effective]], since their proofs, as sketched above, are associated with [[algorithm]]s for testing the property and computing the polynomials whose existence are asserted. Moreover these algorithms are efficient, as their [[computational complexity]] is a [[quadratic time|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 {{math|''K''[''X'']}}, the factors, and the methods for computing them, depend strongly on {{mvar|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 number]]s, there are irreducible polynomials of any degree. For example, the polynomial <math>X^4-2</math> is irreducible over the rational numbers, is factored as <math>(X - \sqrt[4]2)(X+\sqrt[4]2)(X^2+\sqrt 2)</math> over the real numbers and, and as <math>(X-\sqrt[4]2)(X+\sqrt[4]2)(X-i\sqrt[4]2)(X+i\sqrt[4]2)</math> 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 {{math|''K''}} such that there exist exact algorithms for the arithmetic operations of {{math|''K''}}, but there cannot exist any algorithm for deciding whether a polynomial of the form <math>X^p - a</math> is [[irreducible polynomial|irreducible]] or is a product of polynomials of lower degree.<ref>{{citation |author1=Fröhlich, A.|author2=Shepherson, J. C.|title = On the factorisation of polynomials in a finite number of steps|journal = Mathematische Zeitschrift|volume = 62|issue=1|year = 1955|issn = 0025-5874|doi=10.1007/BF01180640|pages=331–334|s2cid=119955899 }}</ref>

On the other hand, over the rational numbers and over finite fields, the situation is better than for [[integer factorization]], as there are [[factorization of polynomials|factorization algorithm]]s that have a [[polynomial complexity]]. They are implemented in most general purpose [[computer algebra system]]s.

===Minimal polynomial===
{{main|Minimal polynomial (field theory)}}

If {{math|''θ''}} is an element of an [[associative algebra|associative {{mvar|K}}-algebra]] {{math|''L''}}, the [[#Polynomial evaluation|polynomial evaluation]] at {{math|''θ''}} is the unique [[algebra homomorphism]] {{math|''φ''}} from {{math|''K''[''X'']}} into {{math|''L''}} that maps {{math|''X''}} to {{math|''θ''}} and does not affect the elements of {{math|''K''}} itself (it is the [[identity function|identity map]] on {{math|''K''}}). It consists of ''substituting'' {{math|''X''}} with {{math|''θ''}} in every polynomial. That is,  
: <math>
  \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.
</math>

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

{{anchor|minimal polynomial}}
If the evaluation homomorphism is not injective, this means that its [[kernel (algebra)|kernel]] is a nonzero [[ideal (ring theory)|ideal]], consisting of all polynomials that become zero when {{mvar|X}} is substituted with {{mvar|θ}}. This ideal consists of all multiples of some monic polynomial, that is called the '''minimal polynomial''' of {{mvar|θ}}. 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 (mathematics)|field theory]] and [[number theory]], an element {{mvar|θ}} of an [[extension field]] {{mvar|L}} of {{mvar|K}} is [[algebraic element|algebraic]] over {{mvar|K}} if it is  a root of some polynomial with coefficients in {{mvar|K}}. The [[minimal polynomial (field theory)|minimal polynomial]] over {{mvar|K}} of {{mvar|θ}} is thus the monic polynomial of minimal degree that has {{mvar|θ}} as a root. Because {{mvar|L}} is a field, this minimal polynomial is necessarily [[irreducible polynomial|irreducible]] over {{mvar|K}}. For example, the minimal polynomial (over the reals as well as over the rationals) of the [[complex number]] {{mvar|i}} is <math>X^2 + 1</math>. The [[cyclotomic polynomial]]s are the minimal polynomials of the [[roots of unity]].

In [[linear algebra]], the {{math|''n''×''n''}} [[square matrices]] over {{mvar|K}} form an [[associative algebra|associative {{mvar|K}}-algebra]] of finite dimension (as a vector space). Therefore the evaluation homomorphism cannot be injective, and every matrix has a [[minimal polynomial (linear algebra)|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 {{mvar|n}}.

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

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

The ring <math>K[X]/(p)</math> is a field if and only if {{mvar|p}} is an [[irreducible polynomial]]. In fact, if {{mvar|p}} is irreducible, every nonzero polynomial {{mvar|q}} of lower degree is coprime with {{mvar|p}}, and [[Bézout's identity]] allows computing {{mvar|r}} and {{mvar|s}} such that {{math|1=''sp'' + ''qr'' = 1}}; so, {{mvar|r}} is the [[multiplicative inverse]] of {{mvar|q}} modulo {{mvar|p}}. Conversely, if {{mvar|p}} is reducible, then there exist polynomials {{mvar|a, b}} of degrees lower than {{math|deg(''p'')}} such that {{math|1=''ab'' = ''p''}}&thinsp;; so {{mvar|a, b}} are nonzero [[zero divisor]]s modulo {{mvar|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 
:<math>\mathbb C =\mathbb R[X]/(X^2+1),</math> 
and that the image of {{mvar|X}} in <math>\mathbb C</math> is denoted by {{mvar|i}}. In fact, by the above description, this quotient consists of all polynomials of degree one in {{mvar|i}}, which have the form {{math|''a'' + ''bi''}}, with {{mvar|a}} and {{mvar|b}} in <math>\mathbb R.</math> The remainder of the Euclidean division that is needed for multiplying two elements of the quotient ring is obtained by replacing {{math|''i''{{sup|2}}}} by {{math|−1}} in their product as polynomials (this is exactly the usual definition of the product of complex numbers).

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

=== Modules ===

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 <math>K[X]/\left\langle P^k \right\rangle</math>, where ''P'' is an [[irreducible polynomial]] over ''K'' and ''k'' a positive integer.