20050426, 12:58  #1 
"William"
May 2003
New Haven
23×103 Posts 
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. 
20050427, 13:41  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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. 

20050429, 18:15  #3 
"William"
May 2003
New Haven
23×103 Posts 
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 10^{9}. 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. 
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  20180110 06:13 
Distribution of relations over the sieving interval in SIQS  mickfrancis  Factoring  3  20140520 15:45 
feature request : interval for stage1_norm  firejuggler  Msieve  2  20130711 00:15 
PrimeNet logout interval?  Xyzzy  PrimeNet  4  20101211 20:24 
Interval calculations with a given alpha  CRGreathouse  Math  10  20100409 06:23 