tommy's simple irreducibility test
in [Math]
|
Prev: Pens�e erron�e
Next: Uniform points in a simplex
From: master1729 on 9 Aug 2010 12:46 tommy's simple irreducibility test for nonlinear integer polynomials. p(x) is irreducible if - p(x) is. lim x-> oo p(x) = +oo or - oo. let poly(x) be p(x) or - p(x) such that the limit gives +oo. let q be ceiling [max real x for poly'(x) = 0] let P(x) be poly(x) / gcd(poly(q^2+1),poly(q^2+2),...) let d be the degree of P(x). if P(x) produces d^2 + q^2 + P^2[d^2 + q^2] primes beyond q^2 then P(x) is irreducible.
From: Bill Dubuque on 9 Aug 2010 17:10 master1729 <tommy1729(a)gmail.com> wrote: > > tommy's simple irreducibility test for nonlinear integer polynomials. > > p(x) is irreducible if - p(x) is. > > lim x-> oo p(x) = +oo or - oo. > > let poly(x) be p(x) or - p(x) such that the limit gives +oo. > > let q be ceiling [max real x for poly'(x) = 0] > > let P(x) be poly(x) / gcd(poly(q^2+1),poly(q^2+2),...) > > let d be the degree of P(x). > > if P(x) produces d^2 + q^2 + P^2[d^2 + q^2] primes beyond q^2 then P(x) is irreducible. A polynomial P is prime if P(n) is prime for some large n: Ignacio Larrosa Caestro <ignacio.larr...(a)eresmas.net> wrote on Jan 14 2003: >Elaine Jackson <elainejackson7...(a)home.com> wrote: >> >> If n is odd then n^6+1 is even and so is composite for n>1. >> Apparently the same is true for even n. How to prove this? > > n^6+1 = (n^2 + 1) (n^4 - n^2 + 1) so is composite for all n > 1 More generally, in 1918 Stackel published the following simple THEOREM If p(x) is a composite integer coefficient polynomial then p(n) is composite for all |n| > B, for some bound B in fact p(n) has at most 2d prime values, where d = degree(p). The simple proof can be found online in Mott & Rose [3], p. 8. I highly recommend this delightful and stimulating 27 page paper which discusses prime-producing polynomials and related topics. Contra+, p(x) is prime (irreducible) if it assumes a prime value for large enough |x|. Conversely Bouniakowski conjectured (1857) prime p(x) assume infinitely many prime values (except in trivial case where values of p have a common divisor, e.g. 2 | X(X+1)+2 ). E.g. Polya-Szego popularized A. Cohn's irreduciblity test, which says that an integer coef poly p(x) is irreducible if p(b) yields a prime in radix b representation, i.e. 0 <= p_i < b. E.g. f(x) = x^4 + 6 x^2 + 1 factors (mod p) for all primes p, yet f(x) is prime since f(8) = 10601 octal = 4481 is prime. Note: Cohn's test fails if, in radix b, negative digits are allowed: f(x) = x^3 - 9 x^2 + x-9 = (x-9)(x^2 + 1) but f(10) = 101 is prime. For more see my prior post [1], along with Murty's online paper [2]. --Bill Dubuque [1] Dubuque, sci.math 2002-11-12, On prime producing polynomials http://groups.google.com/groups?selm=y8zvg4m9yhm.fsf%40nestle.ai.mit.edu [2] Murty, Ram. Prime numbers and irreducible polynomials. Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458. http://www.mast.queensu.ca/~murty/polya4.dvi [3] Mott, Joe L.; Rose, Kermit Prime producing cubic polynomials Ideal theoretic methods in commutative algebra, 281-317 Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001. http://web.math.fsu.edu/~aluffi/archive/paper134.ps
From: quasi on 9 Aug 2010 17:14 On Mon, 09 Aug 2010 16:46:27 EDT, master1729 <tommy1729(a)gmail.com> wrote: >tommy's simple irreducibility test for nonlinear integer polynomials. > >p(x) is irreducible if - p(x) is. > >lim x-> oo p(x) = +oo or - oo. > >let poly(x) be p(x) or - p(x) such that the limit gives +oo. If you choose p with positive leading coefficient, then there's no need for poly -- you can just use p(x) > >let q be ceiling [max real x for poly'(x) = 0] So q is an integer? >let P(x) be poly(x) / gcd(poly(q^2+1),poly(q^2+2),...) But if q is an integer, what is poly(q^2+1)? >let d be the degree of P(x). > >if P(x) produces d^2 + q^2 + P^2[d^2 + q^2] primes beyond q^2 then P(x) is irreducible. Ok, I get the idea. For a given P, if P has too many prime values, then P must be irreducible. The critical number for the number of such prime values depends only on the degree. The basic idea being that if P is reducible, the values +- 1 can be assumed only so many times by a given nonconstant factor of P. However while the idea may work theoretically, it may be too inefficient to be of practical use -- I'm not sure. I think it would be much more interesting if there was a probability distribution on the number of prime factors of P(a) for integers a in a given interval [-m,m] such that, as m approaches infinity, the limiting distribution could distinguish reducibility from irreducibility. Then an appropriate choice of m together with a sufficiently large random sample of values of a could yield a cool probabilistic irreducibility test. quasi
From: quasi on 9 Aug 2010 17:33 On Mon, 09 Aug 2010 16:14:02 -0500, quasi <quasi(a)null.set> wrote: >On Mon, 09 Aug 2010 16:46:27 EDT, master1729 <tommy1729(a)gmail.com> >wrote: > >>tommy's simple irreducibility test for nonlinear integer polynomials. >> >>p(x) is irreducible if - p(x) is. >> >>lim x-> oo p(x) = +oo or - oo. >> >>let poly(x) be p(x) or - p(x) such that the limit gives +oo. > >If you choose p with positive leading coefficient, then there's no >need for poly -- you can just use p(x) > >> >>let q be ceiling [max real x for poly'(x) = 0] > >So q is an integer? > >>let P(x) be poly(x) / gcd(poly(q^2+1),poly(q^2+2),...) > >But if q is an integer, what is poly(q^2+1)? > >>let d be the degree of P(x). >> >>if P(x) produces d^2 + q^2 + P^2[d^2 + q^2] primes beyond q^2 then P(x) is irreducible. > >Ok, I get the idea. > >For a given P, if P has too many prime values, then P must be >irreducible. The critical number for the number of such prime values >depends only on the degree. The basic idea being that if P is >reducible, the values +- 1 can be assumed only so many times by a >given nonconstant factor of P. > >However while the idea may work theoretically, it may be too >inefficient to be of practical use -- I'm not sure. > >I think it would be much more interesting if there was a probability >distribution on the number of prime factors of P(a) for integers a in >a given interval [-m,m] such that, as m approaches infinity, the >limiting distribution could distinguish reducibility from >irreducibility. Then an appropriate choice of m together with a >sufficiently large random sample of values of a could yield a cool >probabilistic irreducibility test. A possible obstacle for my probabilistic approach is the difficulty, in general, of determining the number of prime factors of big numbers. Determining primality is not a problem, but as for determining the number of prime factors, I'm not sure if there is a quick test (either deterministic or probabilistic). quasi
From: master1729 on 9 Aug 2010 13:36 quasi wrote : > On Mon, 09 Aug 2010 16:46:27 EDT, master1729 > <tommy1729(a)gmail.com> > wrote: > > >tommy's simple irreducibility test for nonlinear > integer polynomials. > > > >p(x) is irreducible if - p(x) is. > > > >lim x-> oo p(x) = +oo or - oo. > > > >let poly(x) be p(x) or - p(x) such that the limit > gives +oo. > > If you choose p with positive leading coefficient, > then there's no > need for poly -- you can just use p(x) > > > > >let q be ceiling [max real x for poly'(x) = 0] > > So q is an integer? yes. > > >let P(x) be poly(x) / > gcd(poly(q^2+1),poly(q^2+2),...) > > But if q is an integer, what is poly(q^2+1)? also an integer. > > >let d be the degree of P(x). > > > >if P(x) produces d^2 + q^2 + P^2[d^2 + q^2] primes > beyond q^2 then P(x) is irreducible. > > Ok, I get the idea. then why ask if q is an integer ? :) > > For a given P, if P has too many prime values, then P > must be > irreducible. The critical number for the number of > such prime values > depends only on the degree. The basic idea being that > if P is > reducible, the values +- 1 can be assumed only so > many times by a > given nonconstant factor of P. > > However while the idea may work theoretically, it may > be too > inefficient to be of practical use -- I'm not sure. i said 'simple' , simple is fast sometimes ... but not always , often depends on imput too e.g. trial division is 'simple' but factoring is not necc. simple/fast/trivial. however testing primality is in P ... nowadays :) if all other irreducibility tests are slow , this might be faster with some luck. > > I think it would be much more interesting if there > was a probability > distribution on the number of prime factors of P(a) > for integers a in > a given interval [-m,m] such that, as m approaches > infinity, the > limiting distribution could distinguish reducibility > from > irreducibility. Then an appropriate choice of m > together with a > sufficiently large random sample of values of a could > yield a cool > probabilistic irreducibility test. > > quasi yes sure. i will do that right after i proved generalized collatz , generalized poincare conjecture , generalized beal conjecture , the irrationality of eulers gamma and GRH. i mean , that seems too complicated what you propose. it might depend on GRH since you are considering if polynomials are prime and then you ADD statistics and irreducibility !!?!! maybe its simpler , but im skeptical. btw do me a favor and read about my generalized moebius equation. regards tommy1729
|
Pages: 1 Prev: Pens�e erron�e Next: Uniform points in a simplex |