Prime generating polynomials that stop?

[S485122]

Oops I made a mistake : 34 should not be in the list 34 * 34 + 34 + 17 = is obviously a multiple of 17 :-(

(Nobody seems to read what I post ;-)

[jinydu]

Originally Posted by jinydu

(irreducible over what field, by the way?)

bump

And to ask a more general (but less well-defined) question: Does there exist a closed-form function that generates infinitely many primes the density of which does not tend to zero?

[R.D. Silverman]

Originally Posted by jinydu

bump

And to ask a more general (but less well-defined) question: Does there exist a closed-form function that generates infinitely many primes the density of which does not tend to zero?

Density within the primes? Yes. try f(x) = ax + b, with (a,b) = 1. Its
density is 1/phi(a).

Density within the integers? TRIVIALLY, NO.

[Jushi]

Originally Posted by jinydu

And to ask a more general (but less well-defined) question: Does there exist a closed-form function that generates infinitely many primes the density of which does not tend to zero?

As you say, this is not really a well-defined question. What do you mean with a ``closed-form function''?

[ewmayer]

Thanks to Jens A. for the additional links regarding the Jacobson-Montgomery paper.

So, by way of a brief recap:

The usual kind of statement about this topic which one sees is e.g. "no polynomial can generate only primes." But one can in fact make several much stronger and more precise statements about this:

(a) One can construct polynomials which generate arbitrarily (but finitely) many primes for successive integer values of their argument. Among these, the Euler-form quadratic f(x) = x^2 + x + p with p = 41 is provably the one yielding the largest successive number of values for which f(x) is prime for x =0, ... , p-2.

However, in addition to the necessary finiteness of such consecutive-prime (or the corollary "prime density among the values of f(x) in a finite interval a < x < b arbitrarily close to unity") constructions, one in fact has the following very strong result about asymptotic density:

(b) No polynomial can produce a prime density asymptotically better than that prescribed for the primes at large by the Prime Number Theorem.

(In other words, no matter how fast you are out of the starting gate, in the end the PNT always wins).

In my post of Friday I cited the Bateman-Horn conjecture (BHC) by way of support for (b). But since this in fact requires only a very specialized single-function version of BHC, I had hoped that there would in fact be a rigorous proof along these lines. Is there? (And if so: Bob, is this the "trivially, yes" reference in your post above?)

[R.D. Silverman]

Originally Posted by ewmayer

Thanks to Jens A. for the additional links regarding the Jacobson-Montgomery paper.

So, by way of a brief recap:

The usual kind of statement about this topic which one sees is e.g. "no polynomial can generate only primes." But one can in fact make several much stronger and more precise statements about this:

(a) One can construct polynomials which generate arbitrarily (but finitely) many primes for successive integer values of their argument. Among these, the Euler-form quadratic f(x) = x^2 + x + p with p = 41 is provably the one yielding the largest successive number of values for which f(x) is prime for x =0, ... , p-2.

However, in addition to the necessary finiteness of such consecutive-prime (or the corollary "prime density among the values of f(x) in a finite interval a < x < b arbitrarily close to unity") constructions, one in fact has the following very strong result about asymptotic density:

(b) No polynomial can produce a prime density asymptotically better than that prescribed for the primes at large by the Prime Number Theorem.

(In other words, no matter how fast you are out of the starting gate, in the end the PNT always wins).

In my post of Friday I cited the Bateman-Horn conjecture (BHC) by way of support for (b). But since this in fact requires only a very specialized single-function version of BHC, I had hoped that there would in fact be a rigorous proof along these lines. Is there? (And if so: Bob, is this the "trivially, yes" reference in your post above?)

Suppose P(x) generates some subset of the primes for some specified
values of x. Whetver set is generated is still only a SUBSET of the the
primes and can never have positive density. I was referring only to
the question about a function that yielded a positive density.
One can can have a function that generates a positive density *within*
the primes.

[Jens K Andersen]

Originally Posted by jinydu

Does there exist a closed-form function that generates infinitely many primes the density of which does not tend to zero?

Originally Posted by R.D. Silverman

Density within the primes? Yes. try f(x) = ax + b, with (a,b) = 1. Its
density is 1/phi(a).

Density within the integers? TRIVIALLY, NO.

There appears to be some talking past eachother. I think jinydu and ewmayer are talking about the density of x values which produce primes, while Silverman thinks they mean the density of the produced primes.

http://en.wikipedia.org/wiki/Formula_for_primes

[brunoparga]

Originally Posted by R.D. Silverman

Suppose P(x) generates some subset of the primes for some specified
values of x. Whetver set is generated is still only a SUBSET of the the
primes and can never have positive density. I was referring only to
the question about a function that yielded a positive density.

Dr. Silverman, your explanation seems very clear. I'd like to put it in other terms, perhaps less technically precise but easier (for me) to understand:

what you said is something like, no polynomial (other than f(n) = n) can have as its results all the primes, it will always miss many of them. Is it something like that?

Originally Posted by R.D. Silverman

One can can have a function that generates a positive density *within*
the primes.

Now, this I was less able to understand (although it's probably as clear as the other part for someone more knowleadgeable). Does it mean something like, you can have a polynomial f(n) which, for a given range of n, generates more primes than those up to n? Are you referring to facts like,
a polynomial like P(n) = n^2 + n + 17 has more prime values for 0 < n < 16 than P(n) = n ? I know this is not the only case, but would it be an example of the function you mentioned above?

[xilman]

Perhaps these explanations will help.

That the primes are not dense in the integers means that the ratio pi(x)/x, where pi(x) is the number of primes less than x, becomes arbitrarily close to zero as x increases.

A polynomial that generates primes can not possibly generate prime values that are dense in the integers because the primes themselves are not dense in the integers.

If, instead of considering all integers, one considers only primes and then asks the question: can the number of prime values less than x generated by a polynomial be a non-zero fraction of all the primes less than x, you get his second statement: it is indeed possible for that ratio to tend to a non-zero value, no matter how large x becomes.

Is that clearer?

Perhaps these two simpler arithmetic statements may help.

The odd numbers are dense in the integers. They have density 0.5 because half of all integers less than N are odd, no matter how big you take N.

On the other hand, the squares are not dense in the integers because only 1/N integers less than N are perfect squares, and the ratio 1/N can be made as close to zero as you like by taking N correspondingly large.


Paul

[Wacky]

There is, perhaps, a related statement about which we might inquire:

Is there some polynomial such that the primes are dense in the range of the polynomial?

I guess that this is trivially, "yes" because P(x) = 13 is a polynomial and ALL values in the range of that polynomial, in particular the only one, namely 13, are indeed prime.

However, I am really looking for a polymomial that has an infinite number of values in its range.

:embarassed: Ignore the above as "Already Answered".