Английская Википедия:Eisenstein's criterion

Шаблон: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.^[1]^[2]

Criterion

Suppose we have the following polynomial with integer coefficients:

<math>Q(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0.</math>

If there exists a prime number Шаблон:Mvar such that the following three conditions all apply:

Шаблон:Mvar divides each Шаблон:Math for Шаблон:Math,
Шаблон:Mvar does not divide Шаблон:Math, and
Шаблон:Math does not divide Шаблон:Math,

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

<math>\frac{x^p - 1}{x - 1} = x^{p - 1} + x^{p - 2} + \cdots + x + 1.</math>

Here, as in the earlier example of Шаблон:Mvar, the coefficients Шаблон:Math prevent Eisenstein's criterion from applying directly. However the polynomial will satisfy the criterion for Шаблон:Mvar after substitution of Шаблон:Math for Шаблон:Mvar: this gives

<math>\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 Шаблон:Mvar by properties of binomial coefficients, and whose constant coefficient is equal to Шаблон:Mvar, and therefore not divisible by Шаблон:Math. An alternative way to arrive at this conclusion is to use the identity Шаблон:Math which is valid in characteristic Шаблон:Mvar (and which is based on the same properties of binomial coefficients, and gives rise to the Frobenius endomorphism), to compute the reduction modulo Шаблон:Mvar of the quotient of polynomials:

<math>\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 Шаблон:Mvar; the remaining verification that the constant term of the quotient is Шаблон:Mvar can be done by substituting Шаблон:Math (instead of Шаблон:Math) for Шаблон:Mvar into the expanded form Шаблон:Math.

History

Theodor Schönemann was the first to publish a version of the criterion,^[1] in 1846 in Crelle's Journal,^[3] which reads in translation

That Шаблон:Math will be irreducible to the modulus Шаблон:Math when Шаблон:Math to the modulus Шаблон:Math does not contain a factor Шаблон:Math.

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

Subsequently Eisenstein published a somewhat different version in 1850, also in Crelle's Journal.^[4] This version reads in translation

When in a polynomial Шаблон:Math in Шаблон:Mvar of arbitrary degree the coefficient of the highest term is Шаблон:Math, and all following coefficients are whole (real, complex) numbers, into which a certain (real resp. complex) prime number Шаблон:Mvar divides, and when furthermore the last coefficient is equal to Шаблон:Math, where Шаблон:Math denotes a number not divisible by Шаблон:Mvar: then it is impossible to bring Шаблон:Math into the form
<math>\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 Шаблон:Math, Шаблон:Math, and all Шаблон:Mvar and Шаблон:Mvar are whole (real resp. complex) numbers; the equation Шаблон: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,^[5] 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 Шаблон:Mvar satisfies the criterion for the prime number Шаблон:Mvar, but that it is nevertheless reducible in Шаблон:Math, from which we wish to obtain a contradiction. From Gauss' lemma it follows that Шаблон:Mvar is reducible in Шаблон:Math as well, and in fact can be written as the product Шаблон:Math of two non-constant polynomials Шаблон:Math (in case Шаблон:Mvar is not primitive, one applies the lemma to the primitive polynomial Шаблон:Math (where the integer Шаблон:Mvar is the content of Шаблон:Mvar) to obtain a decomposition for it, and multiplies Шаблон:Mvar into one of the factors to obtain a decomposition for Шаблон:Mvar). Now reduce Шаблон:Math modulo Шаблон:Mvar to obtain a decomposition in Шаблон:Math. But by hypothesis this reduction for Шаблон:Mvar leaves its leading term, of the form Шаблон:Math for a non-zero constant Шаблон:Math, as the only nonzero term. But then necessarily the reductions modulo Шаблон:Mvar of Шаблон:Mvar and Шаблон:Mvar also make all non-leading terms vanish (and cannot make their leading terms vanish), since no other decompositions of Шаблон:Math are possible in Шаблон:Math, which is a unique factorization domain. In particular the constant terms of Шаблон:Math and Шаблон:Mvar vanish in the reduction, so they are divisible by Шаблон:Mvar, but then the constant term of Шаблон:Mvar, which is their product, is divisible by Шаблон: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 Шаблон:Math is reducible. It is shown that this assumption entails a contradiction.

The assumption that

<math>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>\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>Q(x)=G(x)\cdot H(x), \qquad n = r+s.</math>

The coefficient Шаблон:Math of the polynomial Шаблон:Math can be divided by the prime Шаблон:Mvar but not by Шаблон:Math. Since Шаблон:Math, it is possible to divide Шаблон:Math or Шаблон:Math by Шаблон:Mvar, but not both. One may without loss of generality proceed

with a coefficient Шаблон:Math that can be divided by Шаблон:Mvar and

with a coefficient Шаблон:Math that cannot be divided by Шаблон:Mvar.

By the assumption, <math>p</math> does not divide <math>a_n</math>. Because Шаблон:Math, neither Шаблон:Math nor Шаблон:Math can be divided by Шаблон: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>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 Шаблон:Mvar. As <math>a_r</math> is also divisible by Шаблон:Mvar (by hypothesis of the criterion), this implies that

<math>c_r d_0 = a_r- \left (c_{r-1}d_1 + \cdots + c_0 d_r \right )</math>

is divisible by Шаблон: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 Шаблон:Math of the polynomial Шаблон:Math by Шаблон:Mvar. Since

and since Шаблон:Math is not a multiple of Шаблон:Mvar it must be possible to divide Шаблон:Math by Шаблон: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|Шаблон:Mvar-adic number]] field, for an Eisenstein polynomial, we are supposed to take the lower convex envelope of the points

Шаблон:Math,

where Шаблон:Math is the [[additive p-adic valuation|Шаблон:Mvar-adic valuation]] of Шаблон:Math (i.e. the highest power of Шаблон:Mvar dividing it). Now the data we are given on the Шаблон:Math for Шаблон: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 Шаблон:Math to Шаблон:Math, the slope being Шаблон:Math.

This tells us that each root of Шаблон:Mvar has Шаблон:Mvar-adic valuation Шаблон:Math and hence that Шаблон:Mvar is irreducible over the Шаблон: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 Шаблон: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 Шаблон: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 Шаблон:Mvar-th cyclotomic polynomial).

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

Again, for the cyclotomic polynomial, it becomes

Шаблон:Math;

the discriminant can be shown to be (up to sign) Шаблон: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 Шаблон: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 Шаблон:Mvar then Шаблон:Mvar is totally ramified in the extension, and conversely if Шаблон:Mvar is totally ramified in a number field then the field is generated by the root of an Eisenstein polynomial at Шаблон:Mvar.^[6]

Generalization

Generalized criterion

Given an integral domain Шаблон:Mvar, let

be an element of Шаблон:Math, the polynomial ring with coefficients in Шаблон:Mvar.

Suppose there exists a prime ideal Шаблон:Math of Шаблон:Mvar such that

Шаблон:Math for each Шаблон:Math,
Шаблон:Math, and
Шаблон:Math, where Шаблон:Math is the ideal product of Шаблон:Math with itself.

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

Proof

The proof of this generalization is similar to the one for the original statement, considering the reduction of the coefficients modulo Шаблон:Math; the essential point is that a single-term polynomial over the integral domain Шаблон: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 Шаблон:Math, one of the basic examples of an integral domain is the polynomial ring Шаблон:Math in the variable Шаблон:Mvar over the field Шаблон:Mvar. In this case, the principal ideal generated by Шаблон:Mvar is a prime ideal. Eisenstein's criterion can then be used to prove the irreducibility of a polynomial such as Шаблон:Math in Шаблон:Math. Indeed, Шаблон:Mvar does not divide Шаблон:Math, Шаблон:Math does not divide Шаблон:Math, and Шаблон:Mvar divides Шаблон:Math and Шаблон:Math. This shows that this polynomial satisfies the hypotheses of the generalization of Eisenstein's criterion for the prime ideal Шаблон:Math since, for a principal ideal Шаблон:Math, being an element of Шаблон:Math is equivalent to being divisible by Шаблон:Mvar.

Notes

Шаблон:Reflist

References

Шаблон:Citation.

Шаблон:Citation.

Шаблон:Citation.

Шаблон:Citation.

Шаблон:Citation.

[Cox-1] 1,0 ^1,1 Шаблон:Harvnb.

[2] Шаблон:Harvnb.

[3] Шаблон:Harvp.

[4] Шаблон:Harvp.

[5] Шаблон:Harvp.

[6] Шаблон:Citation.

[1]

[2]

[3]

[4]

[5]

[6]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.