Is Eisenstein all powerful?
in [Math]
|
Prev: would neutrinos be already coded digit messages rather than photons #262 Atom Totality #33 Brain Locus theory
Next: How small must the chance of error be before we accept something as true and certain?
From: Arturo Magidin on 4 Aug 2010 14:09 On Aug 4, 1:07 pm, quasi <qu...(a)null.set> wrote: > On Wed, 04 Aug 2010 01:07:43 -0500, quasi <qu...(a)null.set> wrote: > >On Tue, 03 Aug 2010 16:27:52 -0500, Robert Israel > ><isr...(a)math.MyUniversitysInitials.ca> wrote: > > >>quasi <qu...(a)null.set> writes: > > >>> On Tue, 03 Aug 2010 13:04:31 -0500, quasi <qu...(a)null.set> wrote: > > >>> >Prove or disprove: > > >>> >If f in Z[x] with deg(f) > 1 is irreducible then there exists g in > >>> >Z[x] with deg(g) >= 1 such that the polynomial f(g(x)) is irreducible > >>> >by the Eisenstein criterion. > > >>> To clarify ... > > >>> It's immediate that if f(g(x)) is irreducible and deg(g)>=1, then f(x) > >>> is also irreducible. > > >>> But the problem asks, for irreducible f with deg(f) > 1, is there > >>> always such a g for which the Eisenstein criterion could be _directly_ > >>> applied to prove the irreducibility of f(g(x)) (and thus indirectly > >>> establish the irreducibility of f). > > >>> quasi > > >>Try f(x) = x^2 + 4. Suppose Eisenstein worked for > >>g(x) = sum_{j=0}^n a_j x^j, > >>f(g(x)) = (a_0^2 + 4) > >> + sum_{k=1}^{2n} sum_{i=max(0,k-n)}^{min(k,n)} a_i a_{k-i} x^k > > >>Since a0^2 + 4 == 0 or 1 mod 4, p can't be 2. > >>Now p does not divide a_n, but (considering the case k=2n-1) does divide > >>a_{n-1}, and (similarly by looking at k=2n-2, ..., k=n) must divide > >>a_{n-2}, ..., a_0. But then p can't divide a_0^2 + 4, contradiction. > > >A nice, simple counterexample. > > >Thanks. > > At this point, it appears that the Eisenstein criterion can only be > regarded as a special case method. It works beautifully when it works, > but its lack of general power is exposed by its apparent inability to > establish the irreducibility of x^2 + 4. > > However, let's boost the power of Eisenstein and try again ... > > An amplified Eisenstein criterion: > > Let f in Z[x] with deg(f) = n > 1 be given by > > f(x) = a_n x^n + a_(n-1) x^(n-1) + ... + a_0 > > Suppose there is a prime p, and a positive integer k such that > > (1) p does not divide a_n > (2) p^k divides a_i for i = 0 ... (n-1) > (3) p^(k+1) does not divide a_0 > > Then f is irreducible. > > Proof: Omitted for now, but almost line by line (I think) the same as > the proof of the ordinary Eisenstein criterion. I hope it's correct. Seems hard to claim that the proof will work line for line, given that one of the first things one does in the usual proof is note that since p^2 does not divide a_0, then p does not divide the constant term of one of the putative factors of f... How will that be translated here? Or, one works by going to Z/pZ[x] via reduction, in which case you have that if f(x)=g(x)h(x), then reducing modulo p you have a_nx^n = G(x)H(x), and from the fact that Z/pZ is an integral domain you conclude that G(x) and H(x) both have zero constant term, giving a contradiction; this does not work in Z/p^kZ. Perhaps you ought to try to write it out carefully first. -- Arturo Magidin
From: Robert Israel on 4 Aug 2010 15:28 quasi <quasi(a)null.set> writes: > On Wed, 04 Aug 2010 01:07:43 -0500, quasi <quasi(a)null.set> wrote: > > >On Tue, 03 Aug 2010 16:27:52 -0500, Robert Israel > ><israel(a)math.MyUniversitysInitials.ca> wrote: > > > >>quasi <quasi(a)null.set> writes: > >> > >>> On Tue, 03 Aug 2010 13:04:31 -0500, quasi <quasi(a)null.set> wrote: > >>> > >>> >Prove or disprove: > >>> > > >>> >If f in Z[x] with deg(f) > 1 is irreducible then there exists g in > >>> >Z[x] with deg(g) >= 1 such that the polynomial f(g(x)) is irreducible > >>> >by the Eisenstein criterion. > >>> > >>> To clarify ... > >>> > >>> It's immediate that if f(g(x)) is irreducible and deg(g)>=1, then f(x) > >>> is also irreducible. > >>> > >>> But the problem asks, for irreducible f with deg(f) > 1, is there > >>> always such a g for which the Eisenstein criterion could be _directly_ > >>> applied to prove the irreducibility of f(g(x)) (and thus indirectly > >>> establish the irreducibility of f). > >>> > >>> quasi > >> > >>Try f(x) = x^2 + 4. Suppose Eisenstein worked for > >>g(x) = sum_{j=0}^n a_j x^j, > >>f(g(x)) = (a_0^2 + 4) > >> + sum_{k=1}^{2n} sum_{i=max(0,k-n)}^{min(k,n)} a_i a_{k-i} x^k > >> > >>Since a0^2 + 4 == 0 or 1 mod 4, p can't be 2. > >>Now p does not divide a_n, but (considering the case k=2n-1) does divide > >>a_{n-1}, and (similarly by looking at k=2n-2, ..., k=n) must divide > >>a_{n-2}, ..., a_0. But then p can't divide a_0^2 + 4, contradiction. > > > >A nice, simple counterexample. > > > >Thanks. > > At this point, it appears that the Eisenstein criterion can only be > regarded as a special case method. It works beautifully when it works, > but its lack of general power is exposed by its apparent inability to > establish the irreducibility of x^2 + 4. > > However, let's boost the power of Eisenstein and try again ... > > An amplified Eisenstein criterion: > > Let f in Z[x] with deg(f) = n > 1 be given by > > f(x) = a_n x^n + a_(n-1) x^(n-1) + ... + a_0 > > Suppose there is a prime p, and a positive integer k such that > > (1) p does not divide a_n > (2) p^k divides a_i for i = 0 ... (n-1) > (3) p^(k+1) does not divide a_0 > > Then f is irreducible. > > Proof: Omitted for now, but almost line by line (I think) the same as > the proof of the ordinary Eisenstein criterion. I hope it's correct. > > With this amplified criterion, x^2 + 4 is proved irreducible without > the need for transformation by composition (use p=2, k=2). But x^2 - 4 would also satisfy this case, and it is reducible. -- Robert Israel israel(a)math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada
From: Gerry Myerson on 4 Aug 2010 20:20 In article <rbisrael.20100804192633$6f41(a)news.acm.uiuc.edu>, Robert Israel <israel(a)math.MyUniversitysInitials.ca> wrote: > quasi <quasi(a)null.set> writes: > > > An amplified Eisenstein criterion: > > > > Let f in Z[x] with deg(f) = n > 1 be given by > > > > f(x) = a_n x^n + a_(n-1) x^(n-1) + ... + a_0 > > > > Suppose there is a prime p, and a positive integer k such that > > > > (1) p does not divide a_n > > (2) p^k divides a_i for i = 0 ... (n-1) > > (3) p^(k+1) does not divide a_0 > > > > Then f is irreducible. > > > > Proof: Omitted for now, but almost line by line (I think) the same as > > the proof of the ordinary Eisenstein criterion. I hope it's correct. > > > > With this amplified criterion, x^2 + 4 is proved irreducible without > > the need for transformation by composition (use p=2, k=2). > > But x^2 - 4 would also satisfy this case, and it is reducible. Another beautiful theory, killed by an ugly fact. -- Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: quasi on 5 Aug 2010 01:35 On Wed, 04 Aug 2010 14:28:13 -0500, Robert Israel <israel(a)math.MyUniversitysInitials.ca> wrote: >quasi <quasi(a)null.set> writes: > >> On Wed, 04 Aug 2010 01:07:43 -0500, quasi <quasi(a)null.set> wrote: >> >> >On Tue, 03 Aug 2010 16:27:52 -0500, Robert Israel >> ><israel(a)math.MyUniversitysInitials.ca> wrote: >> > >> >>quasi <quasi(a)null.set> writes: >> >> >> >>> On Tue, 03 Aug 2010 13:04:31 -0500, quasi <quasi(a)null.set> wrote: >> >>> >> >>> >Prove or disprove: >> >>> > >> >>> >If f in Z[x] with deg(f) > 1 is irreducible then there exists g in >> >>> >Z[x] with deg(g) >= 1 such that the polynomial f(g(x)) is irreducible >> >>> >by the Eisenstein criterion. >> >>> >> >>> To clarify ... >> >>> >> >>> It's immediate that if f(g(x)) is irreducible and deg(g)>=1, then f(x) >> >>> is also irreducible. >> >>> >> >>> But the problem asks, for irreducible f with deg(f) > 1, is there >> >>> always such a g for which the Eisenstein criterion could be _directly_ >> >>> applied to prove the irreducibility of f(g(x)) (and thus indirectly >> >>> establish the irreducibility of f). >> >>> >> >>> quasi >> >> >> >>Try f(x) = x^2 + 4. Suppose Eisenstein worked for >> >>g(x) = sum_{j=0}^n a_j x^j, >> >>f(g(x)) = (a_0^2 + 4) >> >> + sum_{k=1}^{2n} sum_{i=max(0,k-n)}^{min(k,n)} a_i a_{k-i} x^k >> >> >> >>Since a0^2 + 4 == 0 or 1 mod 4, p can't be 2. >> >>Now p does not divide a_n, but (considering the case k=2n-1) does divide >> >>a_{n-1}, and (similarly by looking at k=2n-2, ..., k=n) must divide >> >>a_{n-2}, ..., a_0. But then p can't divide a_0^2 + 4, contradiction. >> > >> >A nice, simple counterexample. >> > >> >Thanks. >> >> At this point, it appears that the Eisenstein criterion can only be >> regarded as a special case method. It works beautifully when it works, >> but its lack of general power is exposed by its apparent inability to >> establish the irreducibility of x^2 + 4. >> >> However, let's boost the power of Eisenstein and try again ... >> >> An amplified Eisenstein criterion: >> >> Let f in Z[x] with deg(f) = n > 1 be given by >> >> f(x) = a_n x^n + a_(n-1) x^(n-1) + ... + a_0 >> >> Suppose there is a prime p, and a positive integer k such that >> >> (1) p does not divide a_n >> (2) p^k divides a_i for i = 0 ... (n-1) >> (3) p^(k+1) does not divide a_0 >> >> Then f is irreducible. >> >> Proof: Omitted for now, but almost line by line (I think) the same as >> the proof of the ordinary Eisenstein criterion. I hope it's correct. >> >> With this amplified criterion, x^2 + 4 is proved irreducible without >> the need for transformation by composition (use p=2, k=2). > >But x^2 - 4 would also satisfy this case, and it is reducible. Yep -- I definitely must have hallucinated the proof of my "amplified" version. What's more, I should have seen in advance that pure divisibility conditions on the coefficients couldn't possibly prove the irreducibility of x^2 + 4 when x^2 - 4 would satisfy the same conditions. I saw the dilemma shortly after my post, but I had already left for the day. In any case, thanks for dispatching it so quickly. quasi
From: quasi on 5 Aug 2010 01:44
On Wed, 4 Aug 2010 11:09:18 -0700 (PDT), Arturo Magidin <magidin(a)member.ams.org> wrote: >On Aug 4, 1:07 pm, quasi <qu...(a)null.set> wrote: >> On Wed, 04 Aug 2010 01:07:43 -0500, quasi <qu...(a)null.set> wrote: >> >On Tue, 03 Aug 2010 16:27:52 -0500, Robert Israel >> ><isr...(a)math.MyUniversitysInitials.ca> wrote: >> >> >>quasi <qu...(a)null.set> writes: >> >> >>> On Tue, 03 Aug 2010 13:04:31 -0500, quasi <qu...(a)null.set> wrote: >> >> >>> >Prove or disprove: >> >> >>> >If f in Z[x] with deg(f) > 1 is irreducible then there exists g in >> >>> >Z[x] with deg(g) >= 1 such that the polynomial f(g(x)) is irreducible >> >>> >by the Eisenstein criterion. >> >> >>> To clarify ... >> >> >>> It's immediate that if f(g(x)) is irreducible and deg(g)>=1, then f(x) >> >>> is also irreducible. >> >> >>> But the problem asks, for irreducible f with deg(f) > 1, is there >> >>> always such a g for which the Eisenstein criterion could be _directly_ >> >>> applied to prove the irreducibility of f(g(x)) (and thus indirectly >> >>> establish the irreducibility of f). >> >> >>> quasi >> >> >>Try f(x) = x^2 + 4. Suppose Eisenstein worked for >> >>g(x) = sum_{j=0}^n a_j x^j, >> >>f(g(x)) = (a_0^2 + 4) >> >> + sum_{k=1}^{2n} sum_{i=max(0,k-n)}^{min(k,n)} a_i a_{k-i} x^k >> >> >>Since a0^2 + 4 == 0 or 1 mod 4, p can't be 2. >> >>Now p does not divide a_n, but (considering the case k=2n-1) does divide >> >>a_{n-1}, and (similarly by looking at k=2n-2, ..., k=n) must divide >> >>a_{n-2}, ..., a_0. But then p can't divide a_0^2 + 4, contradiction. >> >> >A nice, simple counterexample. >> >> >Thanks. >> >> At this point, it appears that the Eisenstein criterion can only be >> regarded as a special case method. It works beautifully when it works, >> but its lack of general power is exposed by its apparent inability to >> establish the irreducibility of x^2 + 4. >> >> However, let's boost the power of Eisenstein and try again ... >> >> An amplified Eisenstein criterion: >> >> Let f in Z[x] with deg(f) = n > 1 be given by >> >> f(x) = a_n x^n + a_(n-1) x^(n-1) + ... + a_0 >> >> Suppose there is a prime p, and a positive integer k such that >> >> (1) p does not divide a_n >> (2) p^k divides a_i for i = 0 ... (n-1) >> (3) p^(k+1) does not divide a_0 >> >> Then f is irreducible. >> >> Proof: Omitted for now, but almost line by line (I think) the same as >> the proof of the ordinary Eisenstein criterion. I hope it's correct. > >Seems hard to claim that the proof will work line for line, given that >one of the first things one does in the usual proof is note that since >p^2 does not divide a_0, then p does not divide the constant term of >one of the putative factors of f... How will that be translated here? > >Or, one works by going to Z/pZ[x] via reduction, in which case you >have that if f(x)=g(x)h(x), then reducing modulo p you have a_nx^n = >G(x)H(x), and from the fact that Z/pZ is an integral domain you >conclude that G(x) and H(x) both have zero constant term, giving a >contradiction; this does not work in Z/p^kZ. Yes, I see the issue clearly now. My error was a trivial arithmetic one (a failure to divide by 2), resulting in inflated divisors. >Perhaps you ought to try to write it out carefully first. No point now, since the result is false. But yes, I posted too quickly based on a visualized proof, done all in my head. Sorry. quasi |