In
mathematics, Eisenstein's criterion gives a
sufficient condition for a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
with
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
coefficients to be
irreducible over the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s – that is, for it to not be factorizable into the product of non-constant polynomials with rational coefficients.
This criterion is not applicable to all polynomials with integer coefficients that are irreducible over the rational numbers, but it does allow in certain important cases for irreducibility to be proved with very little effort. It may apply either directly or after transformation of the original polynomial.
This criterion is named after
Gotthold Eisenstein
Ferdinand Gotthold Max Eisenstein (16 April 1823 – 11 October 1852) was a German mathematician. He specialized in number theory and analysis, and proved several results that eluded even Gauss. Like Galois and Abel before him, Eisenstein died ...
. In the early 20th century, it was also known as the Schönemann–Eisenstein theorem because
Theodor Schönemann was the first to publish it.
Criterion
Suppose we have the following polynomial with integer
coefficients
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
.
:
If there exists a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
such that the following three conditions all apply:
* divides each for ,
* does ''not'' divide , and
* does ''not'' divide ,
then is irreducible over the rational numbers. It will also be irreducible over the integers, unless all its coefficients have a nontrivial factor in common (in which case as integer polynomial will have some prime number, necessarily distinct from , as an irreducible factor). The latter possibility can be avoided by first making
primitive, by dividing it by the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of its coefficients (the
content
Content or contents may refer to:
Media
* Content (media), information or experience provided to audience or end-users by publishers or media producers
** Content industry, an umbrella term that encompasses companies owning and providing mas ...
of ). This division does not change whether is reducible or not over the rational numbers (see
Primitive part–content factorization
Primitive may refer to:
Mathematics
* Primitive element (field theory)
* Primitive element (finite field)
* Primitive cell (crystallography)
* Primitive notion, axiomatic systems
* Primitive polynomial (disambiguation), one of two concepts
* Primi ...
for details), and will not invalidate the hypotheses of the criterion for (on the contrary it could make the criterion hold for some prime, even if it did not before the division).
Examples
Eisenstein's criterion may apply either directly (i.e., using the original polynomial) or after transformation of the original polynomial.
Direct (without transformation)
Consider the polynomial . In order for Eisenstein's criterion to apply for a prime number it must divide both non-leading coefficients and , which means only could work, and indeed it does since does not divide the leading coefficient , and its square does not divide the constant coefficient . One may therefore conclude that is irreducible over (and, since it is primitive, over as well). Note that since is of degree 4, this conclusion could not have been established by only checking that has no rational roots (which eliminates possible factors of degree 1), since a decomposition into two quadratic factors could also be possible.
Indirect (after transformation)
Often Eisenstein's criterion does not apply for any prime number. It may however be that it applies (for some prime number) to the polynomial obtained after substitution (for some integer ) of for . The fact that the polynomial after substitution is irreducible then allows concluding that the original polynomial is as well. This procedure is known as applying a ''shift''.
For example consider , in which the coefficient 1 of is not divisible by any prime, Eisenstein's criterion does not apply to . But if one substitutes for in , one obtains the polynomial , which satisfies Eisenstein's criterion for the prime number . Since the substitution is an
automorphism of the ring , the fact that we obtain an irreducible polynomial after substitution implies that we had an irreducible polynomial originally. In this particular example it would have been simpler to argue that (being monic of degree 2) could only be reducible if it had an integer root, which it obviously does not; however the general principle of trying substitutions in order to make Eisenstein's criterion apply is a useful way to broaden its scope.
Another possibility to transform a polynomial so as to satisfy the criterion, which may be combined with applying a shift, is reversing the order of its coefficients, provided its constant term is nonzero (without which it would be divisible by anyway). This is so because such polynomials are reducible in if and only if they are reducible in (for any integral domain ), and in that ring the substitution of for reverses the order of the coefficients (in a manner symmetric about the constant coefficient, but a following shift in the exponent amounts to multiplication by a unit). As an example satisfies the criterion for after reversing its coefficients, and (being primitive) is therefore irreducible in .
Cyclotomic polynomials
An important class of polynomials whose irreducibility can be established using Eisenstein's criterion is that of the
cyclotomic polynomials for prime numbers . Such a polynomial is obtained by dividing the polynomial by the linear factor , corresponding to its obvious root (which is its only rational root if ):
:
Here, as in the earlier example of , the coefficients prevent Eisenstein's criterion from applying directly. However the polynomial will satisfy the criterion for after substitution of for : this gives
:
all of whose non-leading coefficients are divisible by by properties of
binomial coefficients, and whose constant coefficient is equal to , and therefore not divisible by . An alternative way to arrive at this conclusion is to use the identity which is valid in
characteristic (and which is based on the same properties of binomial coefficients, and gives rise to the
Frobenius endomorphism
In commutative algebra and field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative rings with prime characteristic , an important class which includes finite fields. The endomorphis ...
), to compute the reduction modulo of the quotient of polynomials:
:
which means that the non-leading coefficients of the quotient are all divisible by ; the remaining verification that the constant term of the quotient is can be done by substituting (instead of ) for into the expanded form .
History
Theodor Schönemann was the first to publish a version of the criterion,
[.] in 1846 in
Crelle's Journal, which reads in translation
That will be irreducible to the modulus when to the modulus does not contain a factor .
This formulation already incorporates a shift to in place of ; the condition on means that is not divisible by , and so is divisible by but not by . As stated it is not entirely correct in that it makes no assumptions on the degree of the polynomial , so that the polynomial considered need not be of the degree that its expression suggests; the example , shows the conclusion is not valid without such hypothesis. Assuming that the degree of does not exceed , the criterion is correct however, and somewhat stronger than the formulation given above, since if is irreducible modulo , it certainly cannot decompose in into non-constant factors.
Subsequently Eisenstein published a somewhat different version in 1850, also in Crelle's Journal. This version reads in translation
When in a polynomial in of arbitrary degree the coefficient of the highest term is , and all following coefficients are whole (real, complex) numbers, into which a certain (real resp. complex) prime number divides, and when furthermore the last coefficient is equal to , where denotes a number not divisible by : then it is impossible to bring into the form
:
where , , and all and are ''whole'' (real resp. complex) numbers; the equation is therefore irreducible.
Here "whole real numbers" are ordinary
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s and "whole complex numbers" are
Gaussian integer
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
s; one should similarly interpret "real and complex prime numbers". The application for which Eisenstein developed his criterion was establishing the irreducibility of certain polynomials with coefficients in the Gaussian integers that arise in the study of the division of the
lemniscate
In algebraic geometry, a lemniscate is any of several figure-eight or -shaped curves. The word comes from the Latin "''lēmniscātus''" meaning "decorated with ribbons", from the Greek λημνίσκος meaning "ribbons",. or which alternative ...
into pieces of equal arc-length.
Remarkably Schönemann and Eisenstein, once having formulated their respective criteria for irreducibility, both immediately apply it to give an elementary proof of the irreducibility of the cyclotomic polynomials for prime numbers, a result that Gauss had obtained in his ''
Disquisitiones Arithmeticae
The (Latin for "Arithmetical Investigations") is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24. It is notable for having had a revolutionary impact on th ...
'' with a much more complicated proof. In fact, Eisenstein adds in a footnote that the only proof for this irreducibility known to him, other than that of Gauss, is one given by
Kronecker in 1845. This shows that he was unaware of the two different proofs of this statement that Schönemann had given in his 1846 article, where the second proof was based on the above-mentioned criterion. This is all the more surprising given the fact that two pages further, Eisenstein actually refers (for a different matter) to the first part of Schönemann's article. In a note ("Notiz") that appeared in the following issue of the Journal, Schönemann points this out to Eisenstein, and indicates that the latter's method is not essentially different from the one he used in the second proof.
Basic proof
To prove the validity of the criterion, suppose satisfies the criterion for the prime number , but that it is nevertheless reducible in , from which we wish to obtain a contradiction. From
Gauss' lemma it follows that is reducible in as well, and in fact can be written as the product of two non-constant polynomials (in case is not primitive, one applies the lemma to the primitive polynomial (where the integer is the content of ) to obtain a decomposition for it, and multiplies into one of the factors to obtain a decomposition for ). Now reduce modulo to obtain a decomposition in . But by hypothesis this reduction for leaves its leading term, of the form for a non-zero constant , as the only nonzero term. But then necessarily the reductions modulo of and also make all non-leading terms vanish (and cannot make their leading terms vanish), since no other decompositions of are possible in , which is a
unique factorization domain
In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
. In particular the constant terms of and vanish in the reduction, so they are divisible by , but then the constant term of , which is their product, is divisible by , contrary to the hypothesis, and one has a contradiction.
A second proof of Eisenstein's criterion also starts with the assumption that the polynomial is reducible. It is shown that this assumption entails a contradiction.
The assumption that
:
is reducible means that there are polynomials
:
Such that
:
The coefficient of the polynomial can be divided by the prime but not by . Since , it is possible to divide or by , but not both. One may without loss of generality proceed
*with a coefficient that can be divided by and
*with a coefficient that cannot be divided by .
By the assumption,
does not divide
. Because , neither nor can be divided by . Thus, if
is the
-th coefficient of the reducible polynomial
, then (possibly with
in case
)
:
wherein
cannot be divided by
, because neither
nor
can be divided by
.
We will prove that
are all divisible by . As
is also divisible by (by hypothesis of the criterion), this implies that
:
is divisible by , a contradiction proving the criterion.
It is possible to divide
by
, because
can be divided by
.
By initial assumption, it is possible to divide the coefficient of the polynomial by . Since
:
and since is not a multiple of it must be possible to divide by . Analogously, by induction,
is a multiple of
for all