Polynomials - Revision history

Khanh: /* Univariate polynomials over a field */

2021-12-20T00:08:26Z

Univariate polynomials over a field

Khanh: /* Several indeterminates over a field */

2021-12-20T00:06:51Z

Several indeterminates over a field

Khanh: /* Differential and skew-polynomial rings */

2021-12-20T00:05:25Z

Differential and skew-polynomial rings

Khanh: /* Definition (multivariate case) */

2021-12-20T00:04:17Z

Definition (multivariate case)

Khanh: /* Univariate polynomials over a field */

2021-12-19T23:55:03Z

Univariate polynomials over a field

Khanh: /* Definition (univariate case) */

2021-12-19T23:45:51Z

Definition (univariate case)

Khanh at 23:35, 19 December 2021

2021-12-19T23:35:52Z

Show changes

Khanh: Created page with "In mathematics, especially in the field of algebra, a '''polynomial ring''' or '''polynomial algebra''' is a ring (which is also a commutative..."

2021-12-19T22:50:15Z

Created page with "In mathematics, especially in the field of algebra, a '''polynomial ring''' or '''polynomial algebra''' is a ring (which is also a commutative..."

Show changes

@@ Line 129: / Line 129: @@
 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.
 === Factorization ===
 Except for factorization, all previous properties of {{math|''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.

@@ Line 283: / Line 283: @@
 === Hilbert's Nullstellensatz ===
-The Nullstellensatz (German for "zero-locus theorem") is a theorem, first proved by David Hilbert, which extends to the multivariate case some aspects of the [[fundamental theorem of algebra]]. It is foundational for algebraic geometry, as establishing a strong link between the algebraic properties of <math>K[X_1, \ldots, X_n]</math> and the geometric properties of algebraic varieties, that are (roughly speaking) set of points defined by implicit polynomial equations.
+The Nullstellensatz (German for "zero-locus theorem") is a theorem, first proved by David Hilbert, which extends to the multivariate case some aspects of the fundamental theorem of algebra. It is foundational for algebraic geometry, as establishing a strong link between the algebraic properties of <math>K[X_1, \ldots, X_n]</math> and the geometric properties of algebraic varieties, that are (roughly speaking) set of points defined by implicit polynomial equations.
 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.
@@ Line 299: / Line 299: @@
 Then, Bézout's theorem states: Given {{mvar|n}} homogeneous polynomials of degrees <math>d_1, \ldots, d_n</math> in {{math|''n'' + 1}} indeterminates, which have only a finite number of common projective zeros in an algebraically closed extension of {{mvar|K}}, the sum of the multiplicities of these zeros is the product <math>d_1 \cdots d_n.</math>
 ==Generalizations==

@@ Line 345: / Line 345: @@
 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 {{nowrap|1=''δ''(''ab'') = ''aδ''(''b'') + ''δ''(''a'')''b''}} may be rewritten
+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'') = ''aδ''(''b'') + ''δ''(''a'')''b'' may be rewritten
 as
 : <math>X\cdot a = a\cdot X +\delta(a).</math>

@@ Line 199: / Line 199: @@
 The tuple of exponents {{math|1=''α'' = (''α''<sub>1</sub>, …, ''α''<sub>''n''</sub>)}} is called the ''multidegree'' or ''exponent vector'' of the monomial. For a less cumbersome notation, the abbreviation
 :<math>X^\alpha=X_1^{\alpha_1}\cdots X_n^{\alpha_n}</math>
-is often used. The ''degree'' of a monomial {{math|''X''<sup>''α''</sup>}}, frequently denoted {{math|deg ''α''}} or {{math|{{abs|''α''}}}}, is the sum of its exponents:
+is often used. The ''degree'' of a monomial {{math|''X''<sup>''α''</sup>}}, frequently denoted {{math|deg ''α''}} or |''α''|, is the sum of its exponents:
 :<math> \deg \alpha = \sum_{i=1}^n \alpha_i. </math>
@@ Line 210: / Line 210: @@
 <math>K[X_1,\dots, X_n]</math> is naturally equipped (see below) with a multiplication that makes a ring, and an associative algebra over {{mvar|K}}, called ''the polynomial ring in {{mvar|n}} indeterminates'' over {{mvar|K}} (the definite article ''the'' reflects that it is uniquely defined up to the name and the order of the indeterminates. If the ring {{mvar|K}} is commutative, <math>K[X_1,\dots, X_n]</math> is also a commutative ring.
-===Operations in {{math|''K''[''X''{{sub|1}}, ..., ''X''{{sub|''n''}}]}}===
+===Operations in {{math|''K''[''X''<sub>1</sub>, ..., ''X''<sub>''n''</sub>]}}===
 ''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
@@ Line 248: / Line 248: @@
 :<math>\operatorname{Hom}_{\mathrm {SET}}(X,\operatorname{F}(A))\cong \operatorname{Hom}_{\mathrm {ALG}}(K[X], A). </math>
-This may be expressed also by saying that polynomial rings are '''free commutative algebras''', since they are [[free object]]s 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.
+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.
 == Univariate over a ring vs. multivariate ==

@@ Line 107: / Line 107: @@
 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 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 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
@@ Line 115: / Line 115: @@
 (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
+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 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>
@@ Line 169: / Line 169: @@
 There are two main cases where minimal polynomials are considered.
-In field theory and number theory, an element {{mvar|θ}} of an extension field {{mvar|L}} of {{mvar|K}} is 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 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 polynomials are the minimal polynomials of the roots of unity.
+In field theory and number theory, an element {{mvar|θ}} of an extension field {{mvar|L}} of {{mvar|K}} is algebraic over {{mvar|K}} if it is  a root of some polynomial with coefficients in {{mvar|K}}. The 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 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 polynomials are the minimal polynomials of the roots of unity.
-In [[linear algebra]], the {{math|''n''×''n''}} square matrices over {{mvar|K}} form an 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 (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}}.
+In linear algebra, the {{math|''n''×''n''}} square matrices over {{mvar|K}} form an 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 (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===
@@ Line 178: / Line 178: @@
 Given a polynomial {{mvar|p}} of degree {{mvar|d}}, the ''quotient ring'' of {{math|''K''[''X'']}} by the 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 divisors modulo {{mvar|p}}, and cannot be invertible.
+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 divisors 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).
+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</sup>}} 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.

@@ Line 10: / Line 10: @@
 The '''polynomial ring''', {{math|''K''[''X'']}}, in {{math|''X''}} over a field (or, more generally, a commutative ring) {{math|''K''}} can be defined in several equivalent ways. One of them is to define {{math|''K''[''X'']}} as the set of expressions, called '''polynomials''' in {{math|''X''}}, of the form
 :<math>p = p_0 + p_1 X + p_2 X^2 + \cdots + p_{m - 1} X^{m - 1} + p_m X^m,</math>
-where {{math|''p''<sub>0</sub>, ''p''<sub>1</sub>, …, ''p''<sub>''m''</sub>}}, the '''coefficients''' of {{math|''p''}}, are elements of {{math|''K''}}, {{math|''p{{sub|m}}'' ≠ 0}} if {{math|''m'' > 0}}, and {{math|''X'', ''X''{{i sup|2}}, …,}} are symbols, which are considered as "powers" of {{math|''X''}}, and follow the usual rules of exponentiation: {{math|1=''X''{{i sup|0}} = 1}}, {{math|1=''X''{{i sup|1}} = ''X''}}, and <math> X^k\, X^l = X^{k+l}</math> for any nonnegative integers {{math|''k''}} and {{math|''l''}}. The symbol {{math|''X''}} is called an indeterminate (The term of "variable" comes from the terminology of polynomial functions. However, here, {{mvar|X}} has not any value (other than itself), and cannot vary, being a ''constant'' in the polynomial ring.)
+where {{math|''p''<sub>0</sub>, ''p''<sub>1</sub>, …, ''p''<sub>''m''</sub>}}, the '''coefficients''' of {{math|''p''}}, are elements of {{math|''K''}}, ''p<sub>m</sub>'' ≠ 0 if {{math|''m'' > 0}}, and {{math|''X'', ''X''<sup>2</sup>, …,}} are symbols, which are considered as "powers" of {{math|''X''}}, and follow the usual rules of exponentiation: {{math|1=''X''<sup>0</sup> = 1}}, {{math|1=''X''<sup>1</sup> = ''X''}}, and <math> X^k\, X^l = X^{k+l}</math> for any nonnegative integers {{math|''k''}} and {{math|''l''}}. The symbol {{math|''X''}} is called an indeterminate (The term of "variable" comes from the terminology of polynomial functions. However, here, {{mvar|X}} has not any value (other than itself), and cannot vary, being a ''constant'' in the polynomial ring.)
-Two polynomials are equal when the corresponding coefficients of each {{math|''X''{{i sup|''k''}}}} are equal.
+Two polynomials are equal when the corresponding coefficients of each {{math|''X''<sup>''k''</sup>}} are equal.
 One can think of the ring {{math|''K''[''X'']}} as arising from {{math|''K''}} by adding one new element {{math|''X''}} that is external to {{math|''K''}}, commutes with all elements of {{math|''K''}}, and has no other specific properties. This can be used for an equivalent definition of polynomial rings.
@@ Line 40: / Line 40: @@
 It is straightforward to verify that these three operations satisfy the axioms of a commutative algebra over {{mvar|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 {{math|(''p''<sub>0</sub>, ''p''<sub>1</sub>, ''p''<sub>2</sub>, …)}} of elements of {{math|''K''}}, having the property that only a finite number of the elements are nonzero, or equivalently, a sequence for which there is some {{math|''m''}} so that ''p''<sub>''n''</sub> = 0 for {{math|''n'' > ''m''}}. In this case, {{math|''p''{{sub|0}}}} and {{mvar|X}} are considered as alternate notations for
+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 {{math|(''p''<sub>0</sub>, ''p''<sub>1</sub>, ''p''<sub>2</sub>, …)}} of elements of {{math|''K''}}, having the property that only a finite number of the elements are nonzero, or equivalently, a sequence for which there is some {{math|''m''}} so that ''p''<sub>''n''</sub> = 0 for {{math|''n'' > ''m''}}. In this case, ''p''<sub>0</sub> and {{mvar|X}} are considered as alternate notations for
-the sequences {{math|(''p''{{sub|0}}, 0, 0, …)}} and {{math|(0, 1, 0, 0, …)}}, respectively. A straightforward use of the operation rules shows that the expression
+the sequences (''p''<sub>0</sub>, 0, 0, …) and {{math|(0, 1, 0, 0, …)}}, respectively. A straightforward use of the operation rules shows that the expression
 :<math>p_0 + p_1 X + p_2 X^2 + \cdots + p_m X^m</math>
 is then an alternate notation for the sequence
@@ Line 53: / Line 53: @@
 The ''constant term'' of {{math|''p''}} is <math>p_0.</math> It is zero in the case of the zero polynomial.
-The ''degree'' of {{math|''p''}}, written {{math|deg(''p'')}} is <math>m,</math> the largest {{math|''k''}} such that the coefficient of {{math|''X''{{sup|''k''}}}} is not zero.
+The ''degree'' of {{math|''p''}}, written {{math|deg(''p'')}} is <math>m,</math> the largest {{math|''k''}} such that the coefficient of ''X''<sup>''k''</sup> is not zero.
 The ''leading coefficient'' of {{math|''p''}} is <math>p_m.</math>
@@ Line 81: / Line 81: @@
 === Polynomial evaluation ===
-Let {{mvar|K}} be a field or, more generally, a [[commutative ring]], and {{mvar|R}} a ring containing {{mvar|K}}. For any polynomial {{mvar|p}} in {{math|''K''[''X'']}} and any element {{mvar|a}} in {{mvar|R}}, the substitution of {{mvar|X}} with {{mvar|a}} in {{mvar|p}} defines an element of {{math|''R''}}, which is denoted {{math|''P''(''a'')}}. This element is obtained by carrying on in {{mvar|R}} after the substitution the operations indicated by the expression of the polynomial. This computation is called the '''evaluation''' of {{math|''P''}} at {{math|''a''}}. For example, if we have
+Let {{mvar|K}} be a field or, more generally, a commutative ring, and {{mvar|R}} a ring containing {{mvar|K}}. For any polynomial {{mvar|p}} in {{math|''K''[''X'']}} and any element {{mvar|a}} in {{mvar|R}}, the substitution of {{mvar|X}} with {{mvar|a}} in {{mvar|p}} defines an element of {{math|''R''}}, which is denoted {{math|''P''(''a'')}}. This element is obtained by carrying on in {{mvar|R}} after the substitution the operations indicated by the expression of the polynomial. This computation is called the '''evaluation''' of {{math|''P''}} at {{math|''a''}}. For example, if we have
 :<math>P = X^2 - 1,</math>
 we have