Eisenstein's criterion

Template:Short description In mathematics, Eisenstein's criterion gives a sufficient condition for a polynomial with integer coefficients to be irreducible over the rational numbers – 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. 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.<ref name="Cox"/><ref>Template:Harvp.</ref>

Criterion

Suppose we have the following polynomial with integer coefficients: <math display="block">Q(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0.</math>

If there exists a prime number Template:Mvar such that the following three conditions all apply:

• Template:Mvar divides each Template:Math for Template:Math,
• Template:Mvar does not divide Template:Math, and
• Template:Math does not divide Template:Math,

then Template:Mvar 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 Template:Mvar as integer polynomial will have some prime number, necessarily distinct from Template:Mvar, as an irreducible factor). The latter possibility can be avoided by first making Template:Mvar primitive, by dividing it by the greatest common divisor of its coefficients (the content of Template:Mvar). This division does not change whether Template:Mvar is reducible or not over the rational numbers (see Primitive part–content factorization for details), and will not invalidate the hypotheses of the criterion for Template:Mvar (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 Template:Math. In order for Eisenstein's criterion to apply for a prime number Template:Mvar it must divide both non-leading coefficients Template:Math and Template:Math, which means only Template:Math could work, and indeed it does since Template:Math does not divide the leading coefficient Template:Math, and its square Template:Math does not divide the constant coefficient Template:Math. One may therefore conclude that Template:Mvar is irreducible over Template:Math (and, since it is primitive, over Template:Math as well). Note that since Template:Mvar is of degree 4, this conclusion could not have been established by only checking that Template:Mvar 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 Template:Mvar) of Template:Math for Template:Mvar. 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 Template:Math, in which the coefficient 1 of Template:Mvar is not divisible by any prime, Eisenstein's criterion does not apply to Template:Mvar. But if one substitutes Template:Mvar for Template:Math in Template:Mvar, one obtains the polynomial Template:Math, which satisfies Eisenstein's criterion for the prime number Template:Math. Since the substitution is an automorphism of the ring Template:Math, 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 Template:Mvar (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 Template:Mvar anyway). This is so because such polynomials are reducible in Template:Math if and only if they are reducible in Template:Math (for any integral domain Template:Math), and in that ring the substitution of Template:Math for Template:Mvar 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 Template:Math satisfies the criterion for Template:Math after reversing its coefficients, and (being primitive) is therefore irreducible in Template:Math.

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 Template:Mvar. Such a polynomial is obtained by dividing the polynomial Template:Math by the linear factor Template:Math, corresponding to its obvious root Template:Math (which is its only rational root if Template:Math): <math display="block">\frac{x^p - 1}{x - 1} = x^{p - 1} + x^{p - 2} + \cdots + x + 1.</math>

Here, as in the earlier example of Template:Mvar, the coefficients Template:Math prevent Eisenstein's criterion from applying directly. However the polynomial will satisfy the criterion for Template:Mvar after substitution of Template:Math for Template:Mvar: this gives <math display="block">\frac{(x+1)^p - 1}{x} = x^{p - 1} + \binom{p}{p-1}x^{p - 2} + \cdots + \binom{p}2 x + \binom{p}1,</math> all of whose non-leading coefficients are divisible by Template:Mvar by properties of binomial coefficients, and whose constant coefficient is equal to Template:Mvar, and therefore not divisible by Template:Math. An alternative way to arrive at this conclusion is to use the identity Template:Math which is valid in characteristic Template:Mvar (and which is based on the same properties of binomial coefficients, and gives rise to the Frobenius endomorphism), to compute the reduction modulo Template:Mvar of the quotient of polynomials: <math display="block">\frac{(x+1)^p - 1}{x} \equiv \frac{x^p +1^p-1}{x} = \frac{x^p}{x} = x^{p-1}\pmod p,</math> which means that the non-leading coefficients of the quotient are all divisible by Template:Mvar; the remaining verification that the constant term of the quotient is Template:Mvar can be done by substituting Template:Math (instead of Template:Math) for Template:Mvar into the expanded form Template:Math.

History

Theodor Schönemann was the first to publish a version of the criterion,<ref name="Cox">Template:Harvp.</ref> in 1846 in Crelle's Journal,<ref>Template:Harvp.</ref> which reads in translation

That Template:Math will be irreducible to the modulus Template:Math when Template:Math to the modulus Template:Math does not contain a factor Template:Math.

This formulation already incorporates a shift to Template:Mvar in place of Template:Math; the condition on Template:Math means that Template:Math is not divisible by Template:Mvar, and so Template:Math is divisible by Template:Mvar but not by Template:Math. As stated it is not entirely correct in that it makes no assumptions on the degree of the polynomial Template:Math, so that the polynomial considered need not be of the degree Template:Mvar that its expression suggests; the example Template:Math, shows the conclusion is not valid without such hypothesis. Assuming that the degree of Template:Math does not exceed Template:Mvar, the criterion is correct however, and somewhat stronger than the formulation given above, since if Template:Math is irreducible modulo Template:Math, it certainly cannot decompose in Template:Math into non-constant factors.

Subsequently Eisenstein published a somewhat different version in 1850, also in Crelle's Journal.<ref>Template:Harvp.</ref> This version reads in translation

When in a polynomial Template:Math in Template:Mvar of arbitrary degree the coefficient of the highest term is Template:Math, and all following coefficients are whole (real, complex) numbers, into which a certain (real resp. complex) prime number Template:Mvar divides, and when furthermore the last coefficient is equal to Template:Math, where Template:Math denotes a number not divisible by Template:Mvar: then it is impossible to bring Template:Math into the form <math display="block">\left (x^{\mu} + a_1 x^{\mu-1} + \cdots + a_{\mu} \right) \left (x^{\nu} + b_1 x^{\nu-1} + \cdots + b_{\nu} \right)</math> where Template:Math, Template:Math, and all Template:Mvar and Template:Mvar are whole (real resp. complex) numbers; the equation Template:Math is therefore irreducible.

Here "whole real numbers" are ordinary integers and "whole complex numbers" are Gaussian integers; 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 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 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,<ref>Template:Harvp.</ref> 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 Template:Mvar satisfies the criterion for the prime number Template:Mvar, but that it is nevertheless reducible in Template:Math, from which we wish to obtain a contradiction. From Gauss' lemma it follows that Template:Mvar is reducible in Template:Math as well, and in fact can be written as the product Template:Math of two non-constant polynomials Template:Math (in case Template:Mvar is not primitive, one applies the lemma to the primitive polynomial Template:Math (where the integer Template:Mvar is the content of Template:Mvar) to obtain a decomposition for it, and multiplies Template:Mvar into one of the factors to obtain a decomposition for Template:Mvar). Now reduce Template:Math modulo Template:Mvar to obtain a decomposition in Template:Math. But by hypothesis this reduction for Template:Mvar leaves its leading term, of the form Template:Math for a non-zero constant Template:Math, as the only nonzero term. But then necessarily the reductions modulo Template:Mvar of Template:Mvar and Template:Mvar also make all non-leading terms vanish (and cannot make their leading terms vanish), since no other decompositions of Template:Math are possible in Template:Math, which is a unique factorization domain. In particular the constant terms of Template:Math and Template:Mvar vanish in the reduction, so they are divisible by Template:Mvar, but then the constant term of Template:Mvar, which is their product, is divisible by Template:Math, contrary to the hypothesis, and one has a contradiction.

A second proof of Eisenstein's criterion also starts with the assumption that the polynomial Template:Math is reducible. It is shown that this assumption entails a contradiction.

The assumption that <math display="block">Q(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0</math> is reducible means that there are polynomials <math display="block">\begin{align} G(x) &= c_r x^r + c_{r-1} x^{r-1} + \cdots + c_0 && r \ge 1 \\ H(x) &= d_s x^s + d_{s-1} x^{s-1} + \cdots + d_0 && s \ge 1 \end{align}</math> Such that <math display="block">Q(x) = G(x) \cdot H(x), \qquad n = r+s.</math> The coefficient Template:Math of the polynomial Template:Math can be divided by the prime Template:Mvar but not by Template:Math. Since Template:Math, it is possible to divide Template:Math or Template:Math by Template:Mvar, but not both. One may without loss of generality proceed

• with a coefficient Template:Math that can be divided by Template:Mvar and
• with a coefficient Template:Math that cannot be divided by Template:Mvar.

By the assumption, <math>p</math> does not divide <math>a_n</math>. Because Template:Math, neither Template:Math nor Template:Math can be divided by Template:Mvar. Thus, if <math>a_r</math> is the <math>r</math>-th coefficient of the reducible polynomial <math>Q</math>, then (possibly with <math>d_t = 0</math> in case <math>t>s</math>) <math display="block">a_r=c_r d_0 + c_{r-1}d_1 + \cdots + c_0 d_r</math> wherein <math>c_r d_0</math> cannot be divided by <math>p</math>, because neither <math>d_0</math> nor <math>c_r</math> can be divided by <math>p</math>.

We will prove that <math>c_0, c_1, \ldots, c_{r-1}</math> are all divisible by Template:Mvar. As <math>a_r</math> is also divisible by Template:Mvar (by hypothesis of the criterion), this implies that <math display="block">c_r d_0 = a_r- \left (c_{r-1}d_1 + \cdots + c_0 d_r \right )</math> is divisible by Template:Mvar, a contradiction proving the criterion.

It is possible to divide <math>c_0 d_r</math> by <math>p</math>, because <math>c_0</math> can be divided by <math>p</math>.

By initial assumption, it is possible to divide the coefficient Template:Math of the polynomial Template:Math by Template:Mvar. Since <math display="block">a_1 = c_0 d_1 + c_1 d_0</math> and since Template:Math is not a multiple of Template:Mvar it must be possible to divide Template:Math by Template:Mvar. Analogously, by induction, <math>c_i</math> is a multiple of <math>p</math> for all <math>i<r</math>, which finishes the proof.

Advanced explanation

Applying the theory of the Newton polygon for the [[p-adic number|Template:Mvar-adic number]] field, for an Eisenstein polynomial, we are supposed to take the lower convex envelope of the points

where Template:Math is the [[additive p-adic valuation|Template:Mvar-adic valuation]] of Template:Math (i.e. the highest power of Template:Mvar dividing it). Now the data we are given on the Template:Math for Template:Math, namely that they are at least one, is just what we need to conclude that the lower convex envelope is exactly the single line segment from Template:Math to Template:Math, the slope being Template:Math.

This tells us that each root of Template:Mvar has Template:Mvar-adic valuation Template:Math and hence that Template:Mvar is irreducible over the Template:Mvar-adic field (since, for instance, no product of any proper subset of the roots has integer valuation); and a fortiori over the rational number field.

This argument is much more complicated than the direct argument by reduction mod Template:Mvar. It does however allow one to see, in terms of algebraic number theory, how frequently Eisenstein's criterion might apply, after some change of variable; and so limit severely the possible choices of Template:Mvar with respect to which the polynomial could have an Eisenstein translate (that is, become Eisenstein after an additive change of variables as in the case of the Template:Mvar-th cyclotomic polynomial).

In fact only primes Template:Mvar ramifying in the extension of Template:Math generated by a root of Template:Mvar have any chance of working. These can be found in terms of the discriminant of Template:Mvar. For example, in the case Template:Math given above, the discriminant is Template:Math so that Template:Math is the only prime that has a chance of making it satisfy the criterion. Modulo Template:Math, it becomes Template:Math— a repeated root is inevitable, since the discriminant is Template:Math. Therefore the variable shift is actually something predictable.

Again, for the cyclotomic polynomial, it becomes

the discriminant can be shown to be (up to sign) Template:Math, by linear algebra methods.

More precisely, only totally ramified primes have a chance of being Eisenstein primes for the polynomial. (In quadratic fields, ramification is always total, so the distinction is not seen in the quadratic case like Template:Math above.) In fact, Eisenstein polynomials are directly linked to totally ramified primes, as follows: if a field extension of the rationals is generated by the root of a polynomial that is Eisenstein at Template:Mvar then Template:Mvar is totally ramified in the extension, and conversely if Template:Mvar is totally ramified in a number field then the field is generated by the root of an Eisenstein polynomial at Template:Mvar.<ref>Template:Harvp, "Local fields".</ref>

Generalization

Generalized criterion

Given an integral domain Template:Mvar, let <math display="block">Q = \sum_{i=0}^n a_i x^i</math> be an element of Template:Math, the polynomial ring with coefficients in Template:Mvar.

Suppose there exists a prime ideal Template:Math of Template:Mvar such that

• Template:Math for each Template:Math,
• Template:Math, and
• Template:Math, where Template:Math is the ideal product of Template:Math with itself.

Then Template:Mvar cannot be written as a product of two non-constant polynomials in Template:Math. If in addition Template:Mvar is primitive (i.e., it has no non-trivial constant divisors), then it is irreducible in Template:Math. If Template:Mvar is a unique factorization domain with field of fractions Template:Mvar, then by Gauss's lemma Template:Mvar is irreducible in Template:Math, whether or not it is primitive (since constant factors are invertible in Template:Math); in this case a possible choice of prime ideal is the principal ideal generated by any irreducible element of Template:Mvar. The latter statement gives original theorem for Template:Math or (in Eisenstein's formulation) for Template:Math.

Proof

The proof of this generalization is similar to the one for the original statement, considering the reduction of the coefficients modulo Template:Math; the essential point is that a single-term polynomial over the integral domain Template:Math cannot decompose as a product in which at least one of the factors has more than one term (because in such a product there can be no cancellation in the coefficient either of the highest or the lowest possible degree).

Example

After Template:Math, one of the basic examples of an integral domain is the polynomial ring Template:Math in the variable Template:Mvar over the field Template:Mvar. In this case, the principal ideal generated by Template:Mvar is a prime ideal. Eisenstein's criterion can then be used to prove the irreducibility of a polynomial such as Template:Math in Template:Math. Indeed, Template:Mvar does not divide Template:Math, Template:Math does not divide Template:Math, and Template:Mvar divides Template:Math and Template:Math. This shows that this polynomial satisfies the hypotheses of the generalization of Eisenstein's criterion for the prime ideal Template:Math since, for a principal ideal Template:Math, being an element of Template:Math is equivalent to being divisible by Template:Mvar.

See also

• Cohn's irreducibility criterion
• Perron's irreducibility criterion

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Springer.
• Template:Citation.
• Template:Citation.