Loading ...
Sorry, an error occurred while loading the content.

[PrimeNumbers] Re: prime generating quadratic conjecture

Expand Messages
  • Jens Kruse Andersen
    ... You may have misunderstood this limit . If c = 2, 3, 5, 11, 17, or 41, then x^2-x+c is prime for x = 0..c-1. It has been proved there are no other such c
    Message 1 of 14 , Mar 28, 2006
    • 0 Attachment
      Patrick Capelle wrote:

      > It would better to ask :
      > Do all the prime-generating polynomials of degree 3 (without absolute
      > value) give less than 40 positive and distinct prime numbers ?
      >
      > This question is related to the problem of the eventual existence of a
      > limit.
      > There is already a limit for the quadratic polynomials of Euler's form.

      You may have misunderstood this "limit".
      If c = 2, 3, 5, 11, 17, or 41, then x^2-x+c is prime for x = 0..c-1.
      It has been proved there are no other such c values.
      See http://mathworld.wolfram.com/LuckyNumberofEuler.html
      (That page incorrectly says x = 0..c-2 but it makes no
      difference for the solutions).
      However, there may be large c for which x^2-x+c is prime
      for x = 0..41 or longer. Finding such a c is infeasible.

      > If we do an extension for the degree n, we could ask :
      > is there a limit, for each degree n, in the number of positive and
      > distinct prime numbers given by the prime-generating polynomials of
      > degree n ?

      Probably not. Heuristics support this plausible conjecture:
      For any n>0 and k, there is a polynomial of degree n which
      gives distinct positive primes for the first k integers.

      It is trivial to show that for any n and p, there are infinitely many
      polynomials of degree n which never have a prime factor <= p.
      Consider x^n-x+c. x=0 and x=1 give the same value.
      Then for any prime q, there must be at least one value x^n-x
      cannot take modulo q.
      Choose c (mod q) to ensure that q never divides x^n-x+c.

      There is no polynomial which gives primes for infinitely many
      consecutive integers - except for a constant polynomial f(x) = p ;-)

      --
      Jens Kruse Andersen
    • Mark Underwood
      ... Well of course I had to check this out, and it seems to bear out. However the coefficients are forced out of the whole numbers and into the fractional
      Message 2 of 14 , Mar 28, 2006
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "Dick" <richard042@...> wrote:
        >
        >
        > Clearly, this cannot be so as one can take n consecutive distinct,
        > positive primes and solve for the (n-1)th degree polynomial that
        > describes the sequence.
        >
        > -Dick Boland
        >

        Well of course I had to check this out, and it seems to bear out.
        However the coefficients are forced out of the whole numbers and into
        the fractional domain.

        Here are a few polys yielding the first primes.

        x+2
        yields 2,3 for x=0,1.

        (1/2)x^2 + (1/2)x + 2
        yields 2,3,5 for x=0,1,2.

        -(1/6)x^3 + x^2 + (1/6)x + 2
        yields 2,3,5,7 for x=0,1,2,3.

        (1/8)x^4 - (11/12)x^3 + (19/8)x^2 - (7/12)x + 2
        yields 2,3,5,7,11 for x=0,1,2,3,4.

        Interestingly, these polys are pretty bad at getting subsequent
        primes! For instance, for x=0 to x=10,

        x+2
        yields 2,3,4,5,6,7,8,9,10,11,12.

        (1/2)x^2 + (1/2)x + 2
        yields 2,3,5,8,12,17,23,30,38,47,57.

        -(1/6)x^3 + x^2 + (1/6)x + 2
        yields 2,3,5,7,8,7,3,-5,-18,-37.

        (1/8)x^4 - (11/12)x^3 + (19/8)x^2 - (7/12)x + 2
        yields 2,3,5,7,11,22,48,100,192,341,567.

        Well at least they yield all integer values! Even that is something
        which is not self evident to this novice...

        Mark
      • Dick
        ... It becomes self evident when you look at the sequences using the difference of differences method, basically form the triangle with a top row of n
        Message 3 of 14 , Mar 29, 2006
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "Mark Underwood"
          <mark.underwood@...> wrote:
          >
          > Well at least they yield all integer values! Even that is something
          > which is not self evident to this novice...
          >

          It becomes self evident when you look at the sequences using the
          "difference of differences" method, basically form the triangle with a
          top row of n ordered elements, then the n-1 differences in a new row
          below, n-2 difference below that, etc. The kth row is a sequence
          defined by an (n-k)th degree polynomial. The nth row has just one
          element and it must be an integer, as must all numbers in the triangle
          when the original top sequence is made up of all integers.

          That all other numbers in the extended sequences must be integer is
          obvious because one does not even have to solve for the polynomial.
          Simply take the nth row element and repeat it on the left or right and
          mechanically add your way back up the diagonal of the triangle, adding
          one more integer to each sequence. Extend the bottom row into a
          repeating sequence of the same constant for as long as you like left
          and right and you will always be dealing with addition and subtraction
          of integer values, fractions cannot form. Since the nth row is simply
          a repeating constant, it is in essence a polynomial of degree 0.
          Obviously, the row above that will be an arithmetic progression
          (degree 1), etc. back up to your original (n-1)th degree sequence.

          It becomes clear that the (n-1)th derivative of the top sequence will
          always equal that initial bottom constant and the nth derivative will
          always be 0 (the (n+1)th row of differences must all be zeroes).

          If, instead of repeating a constant across the bottom row, one chooses
          a different value, the (n+1)th row can not be zero, so generally, when
          the new triangle is completed, the new top sequence of n+1 numbers can
          only be described by an nth degree polynomial.

          It's really a nice way to view polynomials in general and gives an
          alternate angle on describing behaviour and properties as opposed to
          focusing on roots as the universal defining property. You can
          actually look at, see and visualize the buggers and free them from
          their obscuring abstraction. There are relations, variations and
          generalizations to be expounded upon and researched. Taking sums
          instead of differences, alternating sums and differences by row,
          alternating between sum and differences across each element in a row,
          etc. is very insightful. I recall David Broadhurst's post not too
          long ago where he used (Leibniz's?) law of signs (not sines!) and
          recall catching that flash glimpse of how it could be demonstrated and
          proven using these approaches, but I haven't had time to work on it,
          much less my backlog/wishlist.

          I am a big fan of looking at polynomials as infinite sequences as each
          nth degree polynomial can always be fully described by *any* n+1
          consecutive solutions of *any* of it's standard form representations.
          Each unique segment of n+1 consecutive solutions will yield different
          coefficients in standard form because basically you're translating the
          index of the standard forms. And it's rather fascinating to consider,
          as one translates the index (i.e. slides the n+1 defining "seeds"
          along the solution set), that the resulting co-efficients in standard
          form will themselves form progressions of a degree determined by the
          degree of the univariate variable it multiplies and the degree of the
          progression one uses in the translation (or sliding) of the index.
          I have some notes on the rules somewhere from a few years ago, I'll
          try to dig them up.

          We talk of constants and arithmetic progressions all the time, but
          rarely do we think in terms of quadratic progressions, cubic
          progressions, etc. In fact, I recall a thread started not too long
          ago called "quadratic progressions", but it did not deal with
          quadratic progressions in the sense I speak of them here, which to me,
          is the only natural and correct definition of a quadratic progression.

          Gotta get back to work or I'll really have plenty of time to study.

          -Dick Boland
        • Mark Underwood
          Thank you Dick and Jose. Dick that looks fascinating, I shall have to contemplate more fully what you have said when I have more time. I had to love what you
          Message 4 of 14 , Mar 29, 2006
          • 0 Attachment
            Thank you Dick and Jose. Dick that looks fascinating, I shall have to
            contemplate more fully what you have said when I have more time. I had
            to love what you said, "You can actually look at, see and visualize
            the buggers and free them from their obscuring abstraction."

            Solving those equations (by hand) reminded me of high school, truly a
            fond and distant memory. I vaguely remember that there was a higher end
            matrix method, but that's about it :o

            Anyways, I am curious how ghastly the coefficients would look for the
            (say) 25th order polynomial which generates the first 26 prime. One
            rainy day when I have nothing better to do, and when I have some more
            GP Pari and theory under my belt I may attempt it.

            Mark
          • Martin Winer
            I happen to be having a conversation about this difference of differences method which I term differentiation (with apostrophes).
            Message 5 of 14 , Mar 29, 2006
            • 0 Attachment
              I happen to be having a conversation about this difference of differences
              method which I term 'differentiation' (with apostrophes).

              http://groups.google.ca/group/sci.math/browse_thread/thread/09811e76012b1f68?hl=en

              Regards...MCW


              >From: "Dick" <richard042@...>
              >To: primenumbers@yahoogroups.com
              >Subject: [PrimeNumbers] Re: prime generating quadratic conjecture
              >Date: Wed, 29 Mar 2006 19:36:26 -0000
              >
              >--- In primenumbers@yahoogroups.com, "Mark Underwood"
              ><mark.underwood@...> wrote:
              > >
              > > Well at least they yield all integer values! Even that is something
              > > which is not self evident to this novice...
              > >
              >
              >It becomes self evident when you look at the sequences using the
              >"difference of differences" method, basically form the triangle with a
              >top row of n ordered elements, then the n-1 differences in a new row
              >below, n-2 difference below that, etc. The kth row is a sequence
              >defined by an (n-k)th degree polynomial. The nth row has just one
              >element and it must be an integer, as must all numbers in the triangle
              >when the original top sequence is made up of all integers.
              >
              >That all other numbers in the extended sequences must be integer is
              >obvious because one does not even have to solve for the polynomial.
              >Simply take the nth row element and repeat it on the left or right and
              >mechanically add your way back up the diagonal of the triangle, adding
              >one more integer to each sequence. Extend the bottom row into a
              >repeating sequence of the same constant for as long as you like left
              >and right and you will always be dealing with addition and subtraction
              >of integer values, fractions cannot form. Since the nth row is simply
              >a repeating constant, it is in essence a polynomial of degree 0.
              >Obviously, the row above that will be an arithmetic progression
              >(degree 1), etc. back up to your original (n-1)th degree sequence.
              >
              >It becomes clear that the (n-1)th derivative of the top sequence will
              >always equal that initial bottom constant and the nth derivative will
              >always be 0 (the (n+1)th row of differences must all be zeroes).
              >
              >If, instead of repeating a constant across the bottom row, one chooses
              >a different value, the (n+1)th row can not be zero, so generally, when
              >the new triangle is completed, the new top sequence of n+1 numbers can
              > only be described by an nth degree polynomial.
              >
              >It's really a nice way to view polynomials in general and gives an
              >alternate angle on describing behaviour and properties as opposed to
              >focusing on roots as the universal defining property. You can
              >actually look at, see and visualize the buggers and free them from
              >their obscuring abstraction. There are relations, variations and
              >generalizations to be expounded upon and researched. Taking sums
              >instead of differences, alternating sums and differences by row,
              >alternating between sum and differences across each element in a row,
              >etc. is very insightful. I recall David Broadhurst's post not too
              >long ago where he used (Leibniz's?) law of signs (not sines!) and
              >recall catching that flash glimpse of how it could be demonstrated and
              >proven using these approaches, but I haven't had time to work on it,
              >much less my backlog/wishlist.
              >
              >I am a big fan of looking at polynomials as infinite sequences as each
              >nth degree polynomial can always be fully described by *any* n+1
              >consecutive solutions of *any* of it's standard form representations.
              > Each unique segment of n+1 consecutive solutions will yield different
              >coefficients in standard form because basically you're translating the
              >index of the standard forms. And it's rather fascinating to consider,
              >as one translates the index (i.e. slides the n+1 defining "seeds"
              >along the solution set), that the resulting co-efficients in standard
              >form will themselves form progressions of a degree determined by the
              >degree of the univariate variable it multiplies and the degree of the
              >progression one uses in the translation (or sliding) of the index.
              >I have some notes on the rules somewhere from a few years ago, I'll
              >try to dig them up.
              >
              >We talk of constants and arithmetic progressions all the time, but
              >rarely do we think in terms of quadratic progressions, cubic
              >progressions, etc. In fact, I recall a thread started not too long
              >ago called "quadratic progressions", but it did not deal with
              >quadratic progressions in the sense I speak of them here, which to me,
              >is the only natural and correct definition of a quadratic progression.
              >
              >Gotta get back to work or I'll really have plenty of time to study.
              >
              >-Dick Boland
              >
              >
              >
              >
            • jbrennen
              ... Enter this in GP. It will give you the answer: q=0;for(i=0,25,p=1;for(j=0,25,if(i==j,p*=prime(i+1), p*=(x-j)/(i-j)));q+=p);print(q); Note that this
              Message 6 of 14 , Mar 29, 2006
              • 0 Attachment
                --- Mark Underwood wrote:
                >
                > Anyways, I am curious how ghastly the coefficients would look for the
                > (say) 25th order polynomial which generates the first 26 prime. One
                > rainy day when I have nothing better to do, and when I have some more
                > GP Pari and theory under my belt I may attempt it.

                Enter this in GP. It will give you the answer:

                q=0;for(i=0,25,p=1;for(j=0,25,if(i==j,p*=prime(i+1),\
                p*=(x-j)/(i-j)));q+=p);print(q);

                Note that this polynomial gives primes for x=0 to 25, then not
                again until x = 84.
              • Patrick Capelle
                ... Thank you, Jens, for this contribution. I would like to give here some comments : 1. There is effectively an error in this mathworld s page. I am going to
                Message 7 of 14 , Apr 1, 2006
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, Wed Mar 29, 2006, "Jens Kruse
                  Andersen" <jens.k.a@...> wrote:
                  > You may have misunderstood this "limit".
                  > If c = 2, 3, 5, 11, 17, or 41, then x^2-x+c is prime for x = 0..c-1.
                  > It has been proved there are no other such c values.
                  > See http://mathworld.wolfram.com/LuckyNumberofEuler.html
                  > (That page incorrectly says x = 0..c-2 but it makes no
                  > difference for the solutions).
                  > However, there may be large c for which x^2-x+c is prime
                  > for x = 0..41 or longer. Finding such a c is infeasible.
                  --------------------------------------------------------------------

                  Thank you, Jens, for this contribution.
                  I would like to give here some comments :

                  1. There is effectively an error in this mathworld's page.
                  I am going to write a short e-mail to the team of Eric W. Weisstein.
                  The polynomials x^2 - x + c are often sources of confusion, and it
                  could be also the case here about this definition of the lucky numbers
                  of Euler. We don't know if the author wanted to write x = 0 ... c-1
                  (because he wanted all the primes, repeated or not) or x = 1 ... c-1
                  (because he wanted only the different prime numbers and didn't care to
                  begin with x = 1) or x = 0 ... c-2 (because he wanted the same range
                  as for the Euler-like polynomials x^2 + x + c).
                  But there is another possibility, more plausible : this page correctly
                  says that " n = 0 ... p-2 ", but the author put wrongly n^2 - n + p
                  instead of n^2 + n + p, whereas he put this last Euler-like
                  polynomial in the following link :
                  http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
                  Note also the following prime curio given by Le Lionnais for the
                  number 41 (see http://primes.utm.edu/curios/page.php ) : it's one of
                  the numbers p (or "Lucky Numbers of Euler") such that a Euler-like
                  polynomial is prime for n = 0, 1, ..., p-2.
                  Anyway, the lucky numbers of Euler are concerning the two families of
                  polynomials, even if the reference to the mathematician Euler in the
                  definition should privilege the Euler-like polynomials n^2 + n + p.
                  Do they have to be mentioned both in the definition of the lucky
                  numbers of Euler ?

                  2. Your idea concerning this "limit" is interesting.
                  In the message 17837 (about polynomials of the form (m.x - k)^2 + (m.x
                  - k) + p ) i wrote this : " My contribution was not concerning
                  quadratic polynomials givning less than p-1 distinct primes. An open
                  problem is to find out polynomials of degree 2 giving L distinct
                  primes when p > 41 and 40 < L < p-1 ".
                  But what you are saying here, about polynomials of the form ax^2 - bx
                  + c, is more general. You consider that the "limitation" of the lucky
                  numbers of Euler will not concern the other quadratic polynomials (of
                  the form ax^2 -bx + c) with more than 40 (i.e., the highest lucky
                  number of Euler - 1) distinct positive prime numbers.
                  So, by transforming my sentence above and using the polynomials ax^2 +
                  bx+ c (to avoid any risk of confusion with ax^2 - bx + c), we could
                  simply say : " an open problem is to find out polynomials of degree 2
                  giving L distinct primes, with L > 40 ". In a first approach, this
                  situation seems to be more general than mine : starting with your
                  interpretation and the polynomials ax^2 + bx + c, with c = p prime, p
                  > 41, L > 40 and x = 0 ... L-1, we have three possibilities :
                  A. L < p-1
                  B. L = p-1
                  C. L > p-1
                  The case A corresponds to my description above.
                  The case B is impossible because p will never be a lucky number of
                  Euler when p > 41.
                  The case C paradoxically brings us to the case B : if a polynomial
                  ax^2 + bx + p, with p > 41, gives more than p-1 distinct prime
                  numbers, it gives already distinct prime numbers when we only consider
                  x = 0 ... p-2.
                  The interest of your proposal, Jens, is finally to confirm that the
                  only possible polynomials to be sought are the polynomials included in
                  A, where ax^2 + bx + p gives L distinct positive primes when p > 41
                  and 40 < L < p-1.

                  3. As i wrote above, the polynomials x^2 - x + c are often sources of
                  problems. But the differences between x^2 - x + c and x^2 + x + c
                  (when c is a lucky number of Euler) are not summarized with the fact
                  that they are both giving p-1 distinct positive primes in a different
                  range of the variable x (x = 1 ... c-1 for the first family
                  and x = 0 ... c-2 for the second family).
                  Something else appears when we compare them ...
                  I would like to do a general remark on the nature of the independent
                  term c when we look at general polynomials ax^2 + bx + c (with integer
                  coefficients) giving any number of distinct positive prime numbers.
                  We know that if we want a sequence of distinct and positive prime
                  numbers, such that this sequence begins with x = 0, then we require
                  that c is positive and prime. If it is not the case, then we have to
                  change our way of presentation and begin all the sequences with x = 1
                  (which is more logical in the sense that the FIRST value of x gives
                  the FIRST value of the sequence). By the only fact that we are
                  starting with x = 0, we artificially create a constraint on the nature
                  of c, which must be prime in any case (i mean in all the polynomials
                  giving any number of distinct positive primes). We do not have
                  necessarily such a constraint when we decide that all the sequences
                  must be counted from x = 1, and in this case we could imagine that c
                  is not systematically a prime number.
                  For instance, when i discussed about the polynomials (m.x - k)^2 +
                  (m.x - k) + c, with m > 0 and k = 0, c-1, c-2, 2c-3 (see
                  http://groups.yahoo.com/group/primenumbers/message/17841 ), i was
                  obliged to consider that c is prime in each case of production of
                  sequences of primes. Only because we require to start with w = 0. So
                  all the families of polynomials giving p-1 prime numbers present
                  consequently a prime independent term (a lucky number of Euler or
                  'derivated' from it). Hence, the search for polynomials giving more
                  than 40 positive distinct numbers could be strongly influenced by the
                  initial conditions of counting.
                  I don't know if this situation needs to do an adaptation of the
                  definition of the prime-generating polynomials (perhaps the best is to
                  continue not to precise how we are counting) or to be more interested
                  in polynomials ax^2 - bx + c with an only aim of widening the
                  possibilities for c (anyway i am not sure that they will give more
                  good polynomials than ax^2 + bx +c).
                  The attitude depends finally on what we are searching for : sequences
                  with repeated prime numbers or ... or sequences with distinct positive
                  prime numbers. For this last kind of search for instance, the
                  polynomials x^2 - x + c , with c prime, are excluded when we count
                  from x = 0 because they give a repeated prime number in the begin of
                  the sequence.
                  In conclusion, i would say that by starting the sequences at x = 1, it
                  is not excluded that we enlarge the field of possibilities and give
                  more chance to find out quadratic polynomials giving more than 40
                  positive distinct prime numbers.

                  Patrick Capelle.
                • Patrick Capelle
                  ... The zoo of prime numbers did not accustom us to so much simplicity and absence of special constraints. In spite of similar formal aspects, we are far here
                  Message 8 of 14 , Apr 1, 2006
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, Wed March 29, 2006, "Jens Kruse
                    Andersen" <jens.k.a@...> wrote:
                    > Heuristics support this plausible conjecture:
                    > For any n>0 and k, there is a polynomial of degree n which
                    > gives distinct positive primes for the first k integers.
                    -------------------------------------------------------------------

                    The zoo of prime numbers did not accustom us to so much simplicity and
                    absence of special constraints.

                    In spite of similar formal aspects, we are far here from the idea that
                    for any k, there is a polynomial of degree n which gives distinct
                    positive primes for the first k integers.

                    Paradoxical situation : we have a lot of difficulties to find out one
                    quadratic polynomial giving more than 40 distinct positive prime
                    numbers , and during this time one can imagine the existence of a
                    quadratic polynomial P(x) giving distinct and positive prime numbers
                    when x goes from 0 to 10^10 ...

                    Regards,
                    Patrick Capelle.
                  • gordon_as_number
                    Only a comment. If you want to prove a polynomials P(x) is prime, isnt enough to determine the assoiated roots. E.g. P(x)=x^2+2 The number N is P(x) which can
                    Message 9 of 14 , Apr 2, 2006
                    • 0 Attachment
                      Only a comment.

                      If you want to prove a polynomials P(x) is prime,
                      isnt enough to determine the assoiated roots.

                      E.g. P(x)=x^2+2

                      The number N is P(x) which can base expanded in
                      some base b as

                      N=\sum_{i=0}^m c_i b^i .

                      Determining the roots and the coefficients I claim
                      is order \ln^3(N), which is a rough estimate here
                      because I didnt let N vary and I didnt include what
                      the value of m is. So you have to polynomials evaluated
                      in the different bases b with the same coefficients c_i.
                      The number of real c.c. pairs (x-\alpha_i)*(x-\alpha_j)^\star
                      = integer or (x-\alpha_i) an integer span the prime factors.
                      Arent there theorems that tell you when polynomials have
                      non-integer root pairs so that you can make a statement
                      towards their construction. I think there are. There
                      should be large classes of integers N of the same degree
                      and with the same coefficients c_j but with varying base;
                      I think these can be constructed in ln^3 N_{max} time with
                      N_{max} being the largest integer considered.

                      The construction I refer to is given in Fast Factoring
                      by Dr. Gordon Chalmers.
                    • Phil Carmody
                      ... First you need to specify the ring in which you re working. You do not do so. One cannot assume Z[x] given that many of the examples we ve seen have been
                      Message 10 of 14 , Apr 2, 2006
                      • 0 Attachment
                        --- gordon_as_number <gordon_as_number@...> wrote:
                        > Only a comment.
                        >
                        > If you want to prove a polynomials P(x) is prime,

                        First you need to specify the ring in which you're working.
                        You do not do so.
                        One cannot assume Z[x] given that many of the examples we've seen have
                        been instead in Q[x].

                        > isnt enough to determine the assoiated roots.
                        >
                        > E.g. P(x)=x^2+2
                        >
                        > The number N is P(x) which can base expanded in
                        > some base b as
                        >
                        > N=\sum_{i=0}^m c_i b^i .

                        Bases ought to be irrelevant. If they're not, you're doing something wrong.

                        > Determining the roots and the coefficients I claim
                        > is order \ln^3(N), which is a rough estimate here
                        > because I didnt let N vary

                        Order(funtion(N)) only makes sense if you let N vary.
                        You've reached that level of illucidity again...

                        > and I didnt include what
                        > the value of m is. So you have to polynomials evaluated
                        > in the different bases b

                        Yup - illucid. Polynomials can be evaluated, but their value is
                        independent of any base.

                        > with the same coefficients c_i.

                        The c_i, as you introduced them, are not coefficients.

                        > The number of real c.c. pairs (x-\alpha_i)*(x-\alpha_j)^\star
                        > = integer or (x-\alpha_i) an integer span the prime factors.

                        With no firm foundation to build on, you've completely lost me now.
                        No point in continuing.

                        Phil

                        () ASCII ribbon campaign () Hopeless ribbon campaign
                        /\ against HTML mail /\ against gratuitous bloodshed

                        [stolen with permission from Daniel B. Cristofani]

                        __________________________________________________
                        Do You Yahoo!?
                        Tired of spam? Yahoo! Mail has the best spam protection around
                        http://mail.yahoo.com
                      Your message has been successfully submitted and would be delivered to recipients shortly.