Editing Irreducible polynomial

{{short description|Polynomial without nontrivial factorization}}
{{about|non-factorizable polynomials|polynomials which are not a composition of polynomials|Indecomposable polynomial}}
{{more footnotes|date=March 2015}}

In [[mathematics]], an '''irreducible polynomial''' is, roughly speaking, a [[polynomial]] that cannot be [[factored]] into the product of two [[Constant polynomial|non-constant polynomials]]. The property of irreducibility depends on the nature of the [[coefficient]]s that are accepted for the possible factors, that is, the [[ring (mathematics)|ring]] to which the [[coefficient]]s of the polynomial and its possible factors are supposed to belong. For example, the polynomial {{math|''x''<sup>2</sup> − 2}} is a polynomial with [[integer]] coefficients, but, as every integer is also a [[real number]], it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as <math>\left(x - \sqrt{2}\right)\left(x + \sqrt{2}\right)</math> if it is considered as a polynomial with real coefficients. One says that the polynomial {{math|''x''<sup>2</sup> − 2}} is irreducible over the integers but not over the reals.

Polynomial irreducibility can be considered for polynomials with coefficients in an [[integral domain]], and there are two common definitions. Most often, a polynomial over an integral domain {{mvar|R}} is said to be ''irreducible'' if it is not the product of two polynomials that have their coefficients in {{mvar|R}}, and that are not [[unit (ring theory)|unit]] in {{mvar|R}}. Equivalently, for this definition, an irreducible polynomial is an [[irreducible element]] in a ring of polynomials over {{mvar|R}}. If {{mvar|R}} is a field, the two definitions of irreducibility are equivalent. For the second definition, a polynomial is irreducible if it cannot be factored into polynomials with coefficients in the same domain that both have a positive degree. Equivalently, a polynomial is irreducible if it is irreducible over the [[field of fractions]] of the integral domain. For example, the polynomial <math>2(x^2-2)\in \Z[x]</math> is irreducible for the second definition, and not for the first one. On the other hand, <math>x^2-2</math> is irreducible in <math>\Z[x]</math> for the two definitions, while it is reducible in <math>\R[x].</math>

A polynomial that is irreducible over any field containing the coefficients is [[absolutely irreducible]]. By the [[fundamental theorem of algebra]], a [[univariate polynomial]] is absolutely irreducible if and only if its degree is one. On the other hand, with several [[indeterminate (variable)|indeterminate]]s, there are absolutely irreducible polynomials of any degree, such as <math>x^2 + y^n - 1,</math> for any positive integer {{math|''n''}}.

A polynomial that is not irreducible is sometimes said to be a '''reducible polynomial'''.<ref>{{harvnb|Gallian|2012|p=311}}</ref><ref>{{harvnb|Mac Lane|Birkhoff|1999}} do not explicitly define "reducible", but they use it in several places. For example: "For the present, we note only that any reducible quadratic or cubic polynomial must have a linear factor." (p. 268).</ref>

Irreducible polynomials appear naturally in the study of [[polynomial factorization]] and [[algebraic field extension]]s.

It is helpful to compare irreducible polynomials to [[prime number]]s: prime numbers (together with the corresponding negative numbers of equal magnitude) are the irreducible [[integer]]s. They exhibit many of the general properties of the concept of "irreducibility" that equally apply to irreducible polynomials, such as the essentially unique factorization into prime or irreducible factors.  When the coefficient ring is a field or other [[unique factorization domain]], an irreducible polynomial is also called a '''prime polynomial''', because it generates a [[prime ideal]].

==Definition==

If ''F'' is a field, a non-constant polynomial is '''irreducible over ''F''''' if its coefficients belong to ''F'' and it cannot be factored into the product of two non-constant polynomials with coefficients in ''F''. 

A polynomial with integer coefficients, or, more generally, with coefficients in a [[unique factorization domain]] ''R'', is sometimes said to be ''irreducible'' (or ''irreducible over R'') if it is an [[irreducible element]] of the [[polynomial ring]], that is, it is not [[unit (ring theory)|invertible]], not zero, and cannot be factored into the product of two non-invertible polynomials with coefficients in ''R''. This definition generalizes the definition given for the case of coefficients in a field, because, over a field, the non-constant polynomials are exactly the polynomials that are non-invertible and non-zero.

Another definition is frequently used, saying that a polynomial is ''irreducible over R'' if it is irreducible over the [[field of fractions]] of ''R'' (the field of [[rational number]]s, if ''R'' is the integers). This second definition is not used in this article.  The equivalence of the two definitions depends on ''R''.

== Simple examples ==

The following six polynomials demonstrate some elementary properties of reducible and irreducible polynomials:

:<math>\begin{align}
  p_1(x) &= x^2 + 4x + 4\, = {(x + 2)^2}\\
  p_2(x) &= x^2 - 4\, = {(x - 2)(x + 2)}\\
  p_3(x) &= 9x^2 - 3\, = 3\left(3x^2 - 1\right)\, = 3\left(x\sqrt{3} - 1\right)\left(x\sqrt{3} + 1\right)\\
  p_4(x) &= x^2 - \frac{4}{9}\, = \left(x - \frac{2}{3}\right)\left(x + \frac{2}{3}\right)\\
  p_5(x) &= x^2 - 2\, = \left(x - \sqrt{2}\right)\left(x + \sqrt{2}\right)\\
  p_6(x) &= x^2 + 1\, = {(x - i)(x + i)}
\end{align}</math>

Over the [[integer]]s, the first three polynomials are reducible (the third one is reducible because the factor 3 is not invertible in the integers); the last two are irreducible. (The fourth, of course, is not a polynomial over the integers.)

Over the [[rational number]]s, the first two and the fourth polynomials are reducible, but the other three polynomials are irreducible (as a polynomial over the rationals, 3 is a [[unit (ring theory)|unit]], and, therefore, does not count as a factor).

Over the [[real number]]s, the first five polynomials are reducible, but <math>p_6(x)</math> is irreducible.

Over the [[complex number]]s, all six polynomials are reducible.

==Over the complex numbers==

Over the [[complex field]], and, more generally, over an [[algebraically closed field]], a [[univariate polynomial]] is irreducible if and only if its [[degree of a polynomial|degree]] is one. This fact is known as the [[fundamental theorem of algebra]] in the case of the complex numbers and, in general, as the condition of being algebraically closed.

It follows that every nonconstant univariate polynomial can be factored as

:<math>a\left(x - z_1\right) \cdots \left(x - z_n\right)</math>

where <math>n</math> is the degree, <math>a</math> is the leading coefficient and <math>z_1, \dots, z_n</math> are the zeros of the polynomial (not necessarily distinct, and not necessarily having explicit [[algebraic expression]]s).

There are irreducible [[multivariate polynomial]]s of every degree over the complex numbers. For example, the polynomial 
:<math>x^n + y^n - 1,</math> 

which defines a [[Fermat curve]], is irreducible for every positive ''n''.

== Over the reals ==

Over the [[real number|field of reals]], the [[degree of a polynomial|degree]] of an irreducible univariate polynomial is either one or two. More precisely, the irreducible polynomials are the polynomials of degree one and the [[quadratic polynomial]]s <math>ax^2 + bx + c</math> that have a negative [[discriminant]] <math>b^2 - 4ac.</math> It follows that every non-constant univariate polynomial can be factored as a product of polynomials of degree at most two. For example, <math>x^4 + 1</math> factors over the real numbers as <math>\left(x^2 + \sqrt{2}x + 1\right)\left(x^2 - \sqrt{2}x + 1\right),</math> and it cannot be factored further, as both factors have a negative discriminant: <math>\left(\pm\sqrt{2}\right)^2 - 4 = -2 < 0.</math>

==Unique factorization property==
{{main|Unique factorization domain}}

Every polynomial over a field {{math|''F''}} may be factored into a product of a non-zero constant and a finite number of irreducible (over {{math|''F''}}) polynomials. This decomposition is unique [[up to]] the order of the factors and the multiplication of the factors by non-zero constants whose product is 1.

Over a [[unique factorization domain]]  the same theorem is true, but is more accurately formulated by using the notion of primitive polynomial. A [[primitive polynomial (ring theory)|primitive polynomial]] is a polynomial over a unique factorization domain, such that 1 is a [[greatest common divisor]] of its coefficients. 

Let {{math|''F''}} be a unique factorization domain. A non-constant irreducible polynomial over {{math|''F''}} is primitive. A primitive polynomial over {{math|''F''}} is irreducible over {{math|''F''}} if and only if it is irreducible over the [[field of fractions]] of {{math|''F''}}. Every polynomial over {{math|''F''}} may be decomposed into the product of a non-zero constant and a finite number of non-constant irreducible primitive polynomials. The non-zero constant may itself be decomposed into the product of a [[unit (ring theory)|unit]] of {{math|''F''}} and a finite number of [[irreducible element]]s of {{math|''F''}}. Both factorizations are unique up to the order of the factors and the multiplication of the factors by a unit of {{math|''F''}}.

This is this theorem which motivates that the definition of ''irreducible polynomial over a unique factorization domain'' often supposes that the polynomial is non-constant. 

All [[algorithm]]s which are presently [[Implementation#Computer science|implemented]] for factoring polynomials over the [[integer]]s and over the [[rational number]]s use this result (see [[Factorization of polynomials]]).

== Over the integers and finite fields==
The irreducibility of a polynomial over the integers <math>\mathbb{Z}</math> is related to that over the field <math>\mathbb{F}_p</math> of <math>p</math> elements (for a prime <math>p</math>). In particular, if a univariate polynomial {{mvar|''f''}} over <math>\mathbb Z</math> is irreducible over <math>\mathbb{F}_p</math> for some prime <math>p</math> that does not divide the leading coefficient of {{math|''f''}} (the coefficient of the highest power of the variable), then {{math|''f''}} is irreducible over <math>\mathbb{Z}</math> (that is, it is not the product of two non-constant polynomials with integer coefficients). [[Eisenstein's criterion]] is a variant of this property where irreducibility over <math>p^2</math> is also involved.

The converse, however, is not true: there are polynomials of arbitrarily large degree that are irreducible over the integers and reducible over every finite field.<ref>{{cite book|title=Abstract Algebra|url=https://archive.org/details/abstractalgebra00dumm_304|url-access=limited|year=2004|publisher=Wiley |isbn=0-471-43334-9|page=[https://archive.org/details/abstractalgebra00dumm_304/page/n322 309]|author=David Dummit|author2=Richard Foote|chapter=ch. 9, Proposition 12}}</ref> A simple example of such a polynomial is <math>x^4 + 1.</math>

The relationship between irreducibility over the integers and irreducibility modulo ''p'' is deeper than the previous result: to date, all implemented algorithms for factorization and irreducibility over the integers and over the rational numbers use the factorization over finite fields as a [[subroutine]].

The number of degree {{math|''n''}} irreducible [[monic polynomial]]s over a field <math>\mathbb{F}_q</math> for {{math|''q''}} a prime power is given by [[Necklace polynomial|Moreau's necklace-counting function]]:<ref>{{cite book |last=Jacobson |first=Nathan |author-link=Nathan Jacobson |date=1985 |title=Basic Algebra I |url=http://www.math.toronto.edu/~ila/Jacobson-Basic_algebra_I%20(1).pdf |location=New York |publisher=W. H. Freeman and Company |section=4.13 Finite Fields |isbn=0-7167-1480-9}}</ref><ref>{{cite journal |last1=Chebolu |first1=Sunil |last2=Mináč |first2=Ján |date=2011 |title=Counting Irreducible Polynomials over Finite Fields Using the Inclusion-Exclusion Principle |url=https://www.maa.org/sites/default/files/Chebolu11739.pdf |journal=Mathematics Magazine |volume=84 |issue=5 |pages=369–371 |doi=10.4169/math.mag.84.5.369 |access-date=2023-04-03}}</ref>
:<math>M(q, n) = \frac{1}{n}\sum_{d\mid n} \mu(d)q^\frac{n}{d},</math>

where {{math|''μ''}} is the [[Möbius function]]. For {{math|1=''q'' = 2}}, such polynomials are commonly used to generate [[pseudorandom binary sequence]]s. 

In some sense, almost all polynomials with coefficients zero or one are irreducible over the integers. More precisely, if a version of the [[Riemann hypothesis]] for [[Dedekind zeta function|Dedekind zeta functions]] is assumed, the probability of being irreducible over the integers for a polynomial with [[Independent and identically distributed random variables|random]] coefficients in {{math|{0, 1} }} tends to one when the degree increases.<ref>{{Cite journal|arxiv=1810.13360|first1=Emmanuel|last1=Breuillard|first2=Péter P.|last2=Varjú|title=Irreducibility of random polynomials of large degree|journal=Acta Mathematica |year=2018|volume=223 |issue=2 |pages=195–249 |doi=10.4310/ACTA.2019.v223.n2.a1 |s2cid=119173838 }}</ref><ref>{{Cite web|url=https://www.quantamagazine.org/in-the-universe-of-equations-virtually-all-are-prime-20181210/|title=In the Universe of Equations, Virtually All Are Prime|last=Hartnett|first=Kevin|website=Quanta Magazine|date=10 December 2018 |access-date=2019-01-13}}</ref>

==Algorithms==
{{main|Factorization of polynomials}}
The unique factorization property of polynomials does not mean that the factorization of a given polynomial may always be computed. Even the irreducibility of a polynomial may not always be proved by a computation: there are fields over which no [[algorithm]] can exist for [[decision procedure|deciding]] the irreducibility of arbitrary polynomials.<ref>
{{citation
 |last1=Fröhlich |first1=A.
 |last2=Shepherson |first2=J.C.
 |title = On the factorisation of polynomials in a finite number of steps
 |journal = Mathematische Zeitschrift
 |volume = 62 |issue=1 |year = 1955
 |pages = 331–4
 |issn = 0025-5874
 |doi = 10.1007/BF01180640
 |s2cid = 119955899
}}</ref> 

Algorithms for factoring polynomials and deciding irreducibility are known and implemented in [[computer algebra system]]s for polynomials over the integers, the rational numbers, [[finite field]]s and [[finitely generated field extension]] of these fields. All these algorithms use the algorithms for [[factorization of polynomials over finite fields]].

==Field extension==
{{main|Algebraic extension}}
The notions of irreducible polynomial and of [[algebraic field extension]] are strongly related, in the following way.

Let ''x'' be an element of an [[field extension|extension]] ''L'' of a field ''K''. This element is said to be ''algebraic'' if it is a [[zero of a function|root]] of a nonzero polynomial with coefficients in ''K''. Among the polynomials of which ''x'' is a root, there is exactly one which is [[monic polynomial|monic]] and of minimal degree, called the [[minimal polynomial (field theory)|minimal polynomial]] of ''x''. The minimal polynomial of an algebraic element ''x'' of ''L'' is irreducible, and is the unique monic irreducible polynomial of which ''x'' is a root. The minimal polynomial of ''x'' divides every polynomial which has ''x'' as a root (this is [[Abel's irreducibility theorem]]). 

Conversely, if <math>P(X) \in K[X]</math> is a univariate polynomial over a field ''K'', let <math>L = K[X]/P(X)</math> be the [[quotient ring]] of the polynomial ring <math>K[X]</math> by the [[ideal (ring theory)#Ideal generated by a set|ideal generated]] by {{math|''P''}}. Then {{math|''L''}} is a field if and only if {{math|''P''}} is irreducible over {{math|''K''}}. In this case, if {{math|''x''}} is the image of {{math|''X''}} in {{math|''L''}}, the minimal polynomial of {{math|''x''}} is the quotient of {{math|''P''}} by its [[leading coefficient]].

An example of the above is the standard definition of the [[complex number]]s as <math>\mathbb{C} = \mathbb{R}[X]\;/\left(X^2 + 1\right).</math>

If a polynomial {{math|''P''}} has an irreducible factor {{math|''Q''}} over {{math|''K''}}, which has a degree greater than one, one may apply to {{math|''Q''}} the preceding construction of an algebraic extension, to get an extension in which {{math|''P''}} has at least one more root than in {{math|''K''}}. Iterating this construction, one gets eventually a field over which {{math|''P''}} factors into linear factors. This field, unique [[up to]] a [[ring isomorphism|field isomorphism]], is called the [[splitting field]] of {{math|''P''}}.

==Over an integral domain ==
If ''R'' is an [[integral domain]], an element ''f'' of ''R'' that is neither zero nor a unit is called [[irreducible element|irreducible]] if there are no non-units ''g'' and ''h'' with ''f'' = ''gh''. One can show that every [[prime element]] is irreducible;<ref>Consider ''p'' a prime that is reducible: ''p'' = ''ab''. Then ''p'' | ''ab'' ⇒ ''p'' | ''a'' or ''p'' | ''b''. Say ''p'' | ''a'' ⇒ ''a'' = ''pc'', then we have: ''p'' = ''ab'' = ''pcb'' ⇒ ''p''(1 − ''cb'') = 0. Because ''R'' is a domain, we have ''cb'' = 1. So ''b'' is a unit, and ''p'' is irreducible.</ref> the converse is not true in general but holds in [[unique factorization domain]]s. The [[polynomial ring]] ''F''[''x''] over a field ''F'' (or any unique-factorization domain) is again a unique factorization domain. Inductively, this means that the polynomial ring in ''n'' indeterminates (over a ring ''R'') is a unique factorization domain if the same is true for ''R''.

== See also ==
* [[Gauss's lemma (polynomial)]]
* [[Rational root theorem]], a method of finding whether a polynomial has a linear factor with rational coefficients
* [[Eisenstein's criterion]]
* [[Perron's irreducibility criterion]]
* [[Hilbert's irreducibility theorem]]
* [[Cohn's irreducibility criterion]]
* [[Irreducible component]] of a [[topological space]]
* [[Factorization of polynomials over finite fields]]
* {{section link|Quartic function|Reducible quartics}}
* {{section link|Cubic function|Factorization}}
* [[Casus irreducibilis]], the irreducible cubic with three real roots
* {{section link|Quadratic equation|Quadratic factorization}}

== Notes ==
{{reflist}}

== References ==
* {{Lang Algebra}}. This classical book covers most of the content of this article.
* {{Citation |last=Gallian |first=Joseph |author-link=Joseph Gallian |year=2012 |title=Contemporary Abstract Algebra |edition=8th |publisher=Cengage Learning |isbn=978-1285402734 |url=https://books.google.com/books?id=Ef4KAAAAQBAJ&q=%22reducible+polynomial%22&pg=PA311 }}
* {{citation | first1 = Rudolf | last1 = Lidl | first2 = Harald | last2 = Niederreiter | author2-link = Harald Niederreiter | title = Finite fields | edition = 2nd | publisher = [[Cambridge University Press]] | year = 1997 | isbn = 978-0-521-39231-0 | url-access = registration | url = https://archive.org/details/finitefields0000lidl_a8r3 }}, [https://books.google.com/books?id=xqMqxQTFUkMC&pg=PA91 pp. 91].
* {{Citation |last1=Mac Lane |first1=Saunders | author-link=Saunders Mac Lane |last2=Birkhoff |first2=Garrett |author-link2=Garrett Birkhoff |year=1999 |title=Algebra |edition=3rd |publisher=American Mathematical Society |isbn=9780821816462 |url=https://books.google.com/books?id=L6FENd8GHIUC&q=reducible&pg=PA268 }}
* {{citation | first1 = Alfred J. | last1 = Menezes | author-link1 = Alfred Menezes | first2 = Paul C. | last2 = Van Oorschot | author-link2 = Paul van Oorschot | first3 = Scott A. | last3 = Vanstone | author-link3 = Scott Vanstone | title = Handbook of applied cryptography | publisher = [[CRC Press]] | year = 1997 | isbn = 978-0-8493-8523-0 | url-access = registration | url = https://archive.org/details/handbookofapplie0000mene }}, [https://books.google.com/books?id=nSzoG72E93MC&pg=PA154 pp. 154].

== External links ==
* {{MathWorld | title = Irreducible Polynomial | urlname = IrreduciblePolynomial}}
* {{PlanetMath | urlname = irreduciblepolynomial | title = irreducible polynomial}}
* [https://archive.today/20130101095630/http://theory.cs.uvic.ca/inf/neck/PolyInfo.html Information on Primitive and Irreducible Polynomials], The (Combinatorial) Object Server.

{{Polynomials}}

[[Category:Polynomials]]
[[Category:Abstract algebra]]
[[Category:Algebra]]