Expand Messages
• ... 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
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
• ... 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
--- 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
• ... 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
<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
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
• 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
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
• 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
method which I term 'differentiation' (with apostrophes).

Regards...MCW

>From: "Dick" <richard042@...>
>Date: Wed, 29 Mar 2006 19:36:26 -0000
>
><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
>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
>
>
>
>
• ... 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
--- 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.
• ... 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
--- 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
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).
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
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.
• ... 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
--- 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.
• 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
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.
• ... 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
--- 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

> 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.