mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-04-26, 12:58   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Default Variance of the Count of Primes in an Interval

Are there any theoretical or heurisitic results on the variance of the number of primes in an interval? Empirically it's much smaller than a Poisson model would suggest.

Or equivalently, any theoretical or heuristic results on the probability that two randomly chosen numbers in an interval are both prime? The variance could be calculated from that.

Googling around, I have noted that the Twin Prime and related conjectures can be used for the probability that two numbers separated by "k" are both prime, but I haven't found anything more closely related to this question.

Recently I proposed a heuristic based on the Poisson model, and Mark Underwood pointed out that his calculations appeared to have smaller variance than this model. To test this, we created 100 intervals starting with one billion, each interval expected to have 500,000 primes based on the log integral. The average number of primes found was 499,999.4. The Poisson model predicts the variance should equal the mean, but the observed variance , 95661, was smaller by more than a factor 5.
wblipp is offline   Reply With Quote
Old 2005-04-27, 13:41   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by wblipp
Are there any theoretical or heurisitic results on the variance of the number of primes in an interval? Empirically it's much smaller than a Poisson model would suggest.

Or equivalently, any theoretical or heuristic results on the probability that two randomly chosen numbers in an interval are both prime? The variance could be calculated from that.

Googling around, I have noted that the Twin Prime and related conjectures can be used for the probability that two numbers separated by "k" are both prime, but I haven't found anything more closely related to this question.

Recently I proposed a heuristic based on the Poisson model, and Mark Underwood pointed out that his calculations appeared to have smaller variance than this model. To test this, we created 100 intervals starting with one billion, each interval expected to have 500,000 primes based on the log integral. The average number of primes found was 499,999.4. The Poisson model predicts the variance should equal the mean, but the observed variance , 95661, was smaller by more than a factor 5.

There are some heuristical results, but the true answer isn't even known
or conjectured, let alone proven. Work by a variety of number theorists
have hinted at an answer (Goldston, Hildebrand, Maier, others) but we
still don't even know today even whether Cramer's conjecture is correct.

You also need to be precise about your value of 'k' relative to the height
of the primes. When you say "intervals", do you mean very short, short,
medium, long etc. intervals? e.g. [x, x + (log x)^2), (x, x + (log x)^k),
(x, x + x^epsilon), (x, x + O(sqrt(x)), (x, x + epsilon*x) etc.
R.D. Silverman is offline   Reply With Quote
Old 2005-04-29, 18:15   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Default

Do any of these works deal with the typical variation? Cramer's Conjecture, for example, deals with gaps - this is perhaps related to the extreme value statistics, but doesn't have an obvious connection to the typical variation.

As for size of intervals, I gave an example from the numerical investigation - we looked at 100 intervals sized to average 500,000 primes (based on the log integral) starting at 109. I would classify those as medium to long intervals, but it depends on the context. I didn't specify the asymptotic growth of the interval because I was curious about whether anything is known for any method.

A heuristic is known, of course. for the probability that two numbers separated by "k" are both prime - the twin prime heuristic being a special case. I could sum this over all possible separations in the interval, weighted by the probability a random selection would have that separation. If nobody points out a better approach, I'll give that a try and see how well it matches the observations.
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Status page with expected number of Mersenne primes in each interval? CRGreathouse PrimeNet 2 2018-01-10 06:13
Distribution of relations over the sieving interval in SIQS mickfrancis Factoring 3 2014-05-20 15:45
feature request : interval for stage1_norm firejuggler Msieve 2 2013-07-11 00:15
PrimeNet logout interval? Xyzzy PrimeNet 4 2010-12-11 20:24
Interval calculations with a given alpha CRGreathouse Math 10 2010-04-09 06:23

All times are UTC. The time now is 20:55.


Sat Dec 4 20:55:33 UTC 2021 up 134 days, 15:24, 1 user, load averages: 0.93, 1.10, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.