Distribution of primes among values of polynomials
Ronald Bruck
prove the (false) result that n^2 + n + 1 is always either prime or
divisible by 3:
Given a polynomial p(x), define
\pi_p(n) = number of integers 1 <= k <= n such that p(k) is prime.
For some polynomials, e.g. p(x) = 4x or (x+1)(x+2), this is trivial to
solve. But it's not just factoring which makes \pi_p trivial; e.g.
p(x) = x^2 + x + 2 is always even, despite the fact that p(x) doesn't
factor over Q. So factorization in Z_q[x] seems to be needed too.
What puzzles me is p(x) = x^2 + x + 1. \pi_p(n) appears to be
asymptotic to a constant times n/log n, with a constant NOT 1 (at
least, up to n about 10000).
Can anybody apprise me of what's known about such functions \pi_p? Or
is this obvious and I'm just missing it?
--Ron Bruck
Jan Kristian Haugland
Hardy & Littlewood considered this problem among their many
conjectures, so the problem is not new. For a given polynomial
p(x) and a given prime q it should be possible to find the
number of solutions to
p(x) == 0 (mod q)
for x = 0, 1, ..., q - 1, and you can then estimate the
constant. For example, for the polyominal p(x) = x^2 + 1, we
find that there is one solution for q = 2, two solutions for
q == 1 (mod 4) and none for q == 3 (mod 4). So multiply over
(q - #solutions) / (q - 1): This gives
1/1 * 3/2 * 3/4 * 7/6 * 11/10 * 11/12 * ...
corresponding to
q = 2, 3, 5, 7, 11, 13, ...
This will converge, most likely to some irrational number.
Also, we have to take the size of p(x) into consideration:
Divide by the degree of p. I hope I got that more or less
right.
--
- o - o -
- - x - - Jan K Haugland, D Phil
- - - - -
- - o - - http://hjem.sol.no/neutreeko
- x - x -
Paul Pollack
Here is a rough heuristic which predicts the value of the constant out front
that you observed. (This is a special case of a conjecture of Bateman and
Horn, if I am remembering correctly.)
Let f(t) be a polynomial in Z[t] with positive leading coefficient. If f(t)
is to assume infinitely many prime values, then f(t) should be irreducible
over Q. But as you note this isn't sufficient -- we also need to require
that there is no prime p which always divides f(t). It is convenient for
later use to let w(p) denote the number of roots of f(t) mod p, so that our
condition becomes w(p) < p for all primes p.
Then under these conditions on f, if we treat the f(t) as "random integers"
which are prime with a "probability" of 1/log f(t), then we might guess
\pi_f(n) ~ integral(1/log f(t), t= something..n)
(where the something in the lower limit is a constant depending on f chosen
so that the integral makes sense). This leads to an estimate of (1/d)*n/log
n, where d is the degree of f.
This isn't quite correct, because the numbers f(t) don't have the same
probability of being prime as random integers: we can see this if we look at
the probability that f(t) is not divisible by a prime p. This is (1-w(p)/p),
whereas for a random integer this is simply (1-1/p). This suggests that
instead of looking at 1/log f(t) as the probability that f(t) is prime, we
instead consider this probability to be P/log f(t), where P is the infinite
product
product((1-w(p)/p)/(1-1/p)) = product((p-w(p))/(p-1)) = product(1 +
(1-w(p))/(p-1)).
(One might think it better to consider the product only up to some finite
point depending on t, but since the infinite product converges -- a
consequence of the prime ideal theorem -- it turns out not to matter.)
Then we get a predicted estimate of
P/d * n/log n.
In the case of f(t) = t^2 + t + 1, we get a prediction of
pi_f(n) ~ product((1-(-3|p))/(p-1), p>3) * n/log n.
where ( . | . ) is the Legendre symbol. Note that (-3 | p) = 1 iff there is
a primitive cube root of unity in Z/pZ*, so exactly when p == 1 mod 3.
As for what is provably known about \pi_f, we don't know of any nonlinear f
for which \pi_f -> oo. :-(
From sieve methods we do have lower bounds on the number of almost primes
assumed by f up to a given point, as well as good unconditional upper bounds
(good in the sense that they are of the same order of magnitude as the
heuristic suggests is correct).
A nice result of Iwaniec, applicable here, is:
Theorem (Iwaniec, 1978): If G(n) = an^2+bn+c is an irreducible integral
polynomial with a > 0 and c odd, then there infinitely many n such that G(n)
has at most 2 prime factors.
HTH,
Paul
"Ronald Bruck" <br...@math.usc.edu> wrote in message
news:120320021301271592%br...@math.usc.edu...
Virgil
Ronald Bruck <br...@math.usc.edu> wrote:
For p(n) = n^2 - n + 41, \pi_p(n) is unusually large.
Ken Payson
n^2+n+1
if n=3m+1 then n^2+n+1 is divisible by 3 so n=3m or n=3m+2
when n=3m+2 gives (3m+2)^2 + (3m+2) + 1 = 9m^2+15m+7 and it is clear that if
m=7k then 9m^2 + 15m + 7 will be divisible by 7but not by 3
when k= 1 -->m=7-->n=23
23^2+23+1=553
Jan Kristian Haugland
I wrote:
(...)
> For a given polynomial
> p(x) and a given prime q it should be possible to find the
> number of solutions to
>
> p(x) == 0 (mod q)
>
> for x = 0, 1, ..., q - 1, and you can then estimate the
> constant.
I forget to mention that it is assumed that p(x) is irreducible.
--
J K Haugland
http://hjem.sol.no/neutreeko
Nico Benschop
For n>0: n(n+1) = 2 6 12 20 30 42 56 72 90 110 132 ..&c
For some c in Qc(n) = n^2 -n + c all positive n < c yield a prime.
Such sequence stops of course always at Qc(c) = c^2.
And IIRC it has been proven (by Sturm?) there are just 5 values
of c with \pi_Qc = c-1, something like c = 3, 5, 11, 17, 41.
There definitely is 'something quadratic' about the primes,
(can't you smell it?-)...
Q: Describe a minimal set QC of 'quadratic initials' c to cover all
primes as divisors of Qc(n), n>0. Probably |QC| --> inf, but...
-- NB
Nico Benschop
For n>1: n(n-1) = 2 6 12 20 30 42 56 72 90 110 132 ..&c