Heuristic Proofs of the Prime Number Theorem

[jstephe...@gmail.com]

HEURISTIC PROOFS
For many of us non-mathematicians (my background is in physics), a real
mathematician's proof of the Prime Number Theorem (PNT) is beyond our
understanding.  As a result, many heuristic proofs can be found on the
internet, meaning that the techniques employ intuitive judgements that
are not necessarily correct.  I developed my heuristic proof for the
PNT in 1977, thinking at the time that it was legitimate.

CONSECUTIVE INTEGER HEURISTIC PROOF
The heuristic proofs that I have found online are probabilistic
arguments that treat the prime numbers as if they were randomly
distributed.  One type of proof begins with the probability P(x) that x
is a prime number and consider the probability P(x+1) that the next
integer x+1 is a prime [1, 2, 3].  The proof therefore depends on the
possibility of having two consecutive integers that are both prime
numbers, which is not realistic, except for the integers 2 and 3.  The
resulting differential equation has the solution P = 1/ln(cx), where
the constant c is undetermined.

CONSECUTIVE PRIME HEURISTIC PROOF
Another heuristic proof considers two large consecutive primes [4].  A
series of heuristic arguments leads to the differential equation  dP/dx
= -P(x) P(sqrt(x))/x  and arrives at the solution P(x) = 0.5 / ln(x).
  (The numerator should be 1.)

MY HEURISTIC PROOF BASED ON THE SQUARES OF CONSECUTIVE PRIMES
I developed this proof in 1977 when I was a mailman, searching for a
job in physics.  At the time, I thought that it was a legitimate proof.
 The proof follows the Sieve of Eratosthenes, but applied to two
consecutive regions between the squares of primes.

Consider two ranges of integers:
    Range A: R_A = (p_n-1)^2 - (p_n)^2
              the number of integers from from (p_n-1)^2   to  (p_n)^2
-1
    Range B: R_B = (p_n)^2 - (p_n+1)^2
              the number of integers from (p_n)^2          to
 (p_n+1)^2 -1

Range A has been sieved by prime divisors up to p_n-1 so that only
primes remain.  The average density of primes in the range is rho_A
where:

          rho_A = (#primes in the range) / R_A

Now use the same sieve process that was applied to Range A and apply it
to Range B, using the same prime divisors up to p_n-1.

ASSUMPTION 1:  Assume that the sieve for Range A, removes the same
proportion of integers from Range B as it did from Range A.  This means
that Range B now has a proportion rho_A of its original R_B integers
remaining.  The difference is that, in Range A, all the remaining
integers are primes but, in Range B, there are still a few remaining
non-primes, which will be removed by the final pass of the sieve, using
the new prime divisor p_n.

ASSUMPTION 2: Assume that the final pass of the sieve, using prime
divisor p_n, leaves a proportion (1- 1/p_n) of the remaining integers
unscathed and they are all primes, with the result that:

    rho_B = (1-1/p_n) rho_A                              [Eq'n 1]

Let y = p_n and rewrite Eq'n 1 so that the change in density (rho_B -
rho_A) is given by:

    delta rho(y^2) ~  - rho(y^2) / y                     [Eq'n 2]

The prime p_n+1 ~ p_n + 1/rho(p_n) and so the range R_n is given by:

    R_n = d(y^2) ~  2p_n / rho(p_n)                      [Eq'n 3]

    delta(y^2) ~  2y / rho(y)                            [Eq'n 4]


Dividing Eq'n 2 by Eq'n 4, we obtain:

    d rho(y^2) / d(y^2)  ~  -rho(y^2) rho(y) / (2y^2)    [Eq'n 5]


or, letting x = y^2,

    d rho(x) / dx  ~   -rho(x) rho(sqrt(x)) / (2x)      [Eq'n 6]

The solution is:

    rho(x) = 1 / ln(x)                      [Eq'n 7]

1 / ln(cx) is not a solution unless c = 1.

My Consecutive-Squares-of-Primes Heuristic appears to correct the
problems found in some other heuristic proofs, and yet it cannot be
considered a legitimate mathematical proof.  What is wrong with it?
 Let's examine the first equation.  Mertens' Third Theorem says that:

     1/ln(p_n) = 1.781 Prod_n        for large n        [Eq'n 8]   


where Prod_n = (1-1/2) (1-1/3) (1-1/5) ....  (1-1/p_n)

Knowing that the the solution of the PNT is 1/ln(x), that tells us that

    rho((p_n)^2) ~ (1.781/2) Prod_n   and     rho((p_n-1)^2) ~
(1.781/2) Prod_n-1

and therefore

    rho((p_n)^2) / rho((p_n-1)^2)  = (1-1/p_n)

This means that Equation 1 is correct.  Equations 2 to 7, even though
not mathematically very rigorous, are also essentially correct.  So,
what is wrong?  The problem is that Equation 1, even though correct,
was rationalized on the basis of two incorrect assumptions.  That is
deadly in mathematics.  Two wrongs do not make a right, even if they
give you the right answer.

THE FINAL PASS OF THE SIEVE
Looking at Equation 1, it seems obvious that the largest prime divisor
p_n, on the final pass of the sieve, is removing a fraction 1/p_n of
the integers that remain after previous passes of the sieve, which used
smaller prime divisors.  This is Assumption 2, one of the two
assumptions used to derive the equation.

Consider the range of 72 integers from 17^2 to 19^2 -1  (289 to 360).
 There are 11 primes in this range.
In the final pass of the Sieve of Eratosthenes, 17 removes 2 integers:
  17x17 & 17x19.  Therefore there must have been 11 + 2 = 13 integers
left in the range before the final pass.  We have assumed that the
final pass removes a proportion 1/17, but the actual proportion is
 2/13 = 2.615/17.  So, in this example, the final pass removes
approximately 2.6 times as many integers as assumed.

I checked the 18 ranges above the squares of p_481 to p_498 in the same
manner as the previous example (p_481 = 3433; p_481^2 = 11,785,489).
 For these 18 cases, p_n removed either 2 or 3 non-primes in every
case, with an average of 2.5.  The proportion removed was between 1.5
and 8.4 times the expected ratio of 1/p_n, with a weighted average of
2.9 times the expected ratio.  The actual number of integers removed
from the range by the final pass is always at least two.  From Eq'ns 3
and 7, for large n, the number of primes in the range is approximately
p_n so, if k integers are removed on the final pass, the proportion is
k/p_n.  k must be 2 or more and, on average, seems to be approximately
2.5 or a little higher.

In the range from (p_n)^2 to (p_n+1)^2 -1, the prime divisor p_n on the
final pass always removes (p_n)^2 and always removes (p_n)(p_n+1).
 Using reasoning like Eq'n 3, it can be shown that (p_n)(p_n+2) is
approximately the same size as (p_n+1)^2, which is the end of the
range.  So, about half the time, (p_n)(p_n+2) is in the range and half
the time it is in the next range.  The average of 2.5 integers that was
seen in the 18 cases that were checked is therefore quite reasonable.
 From this point of view, it now seems unreasonable to expect the final
pass to remove a proportion 1/p_n of the integers that remained after
previous passes of the sieve, which used prime divisors smaller than
p_n and have nothing to do with removing integers like (p_n)^2,
 (p_n)(p_n+1) or (p_n)(p_n+2), which are the integers that p_n removes.
 So, here is the situation: Equation 1 is correct, but 1/p_n is not the
proportion of integers removed on the final pass, which was Assumption
2.  The conclusion is correct, but one of the two premises is
incorrect.  That means the other premise must also be incorrect.  Both
Assumption 1 and Assumption 2 are wrong, but they were used to derive
Equation 1, which is correct.  This demonstrates how dangerous
heuristic reasoning can be, and nowhere more so than in dealing with
prime numbers.

CONCLUSION
Equation 1 looks deceptively simple and yet, I have no way to
rationalize it.  As demonstrated earlier, if we already know that the
PNT is true and if we use Mertens' Third Theorem, it demonstrates that
Equation 1 is correct.  But, if the PNT is used to prove Equation 1,
then Equation 1 cannot be used to prove the PNT.  Before, I
rationalized Equation 1, based on two assumptions that turned out to be
incorrect.  I would dearly like to know a legitimate rationalization of
Equation 1, but fear that the explanation is buried deep in complicated
number theory that I won't understand.  It is a humorous situation to
have spent considerable effort deriving a fine-looking proof, only to
find out that the satisfying understanding is an illusion, the result
of wrong assumptions conspiring together to tell the truth.  I am not
alone.  Many of you other heuristic-proofers out there are in the same
boat!

[1] Heuristic Derivation of the Prime Number Theorem,by Frank Morgan,
2008
    http://sites.williams.edu/Morgan/2008/10/11/heuristic-derivation-of-
prime-number-theorem/

[2] God Plays Dice, by Michael Lugo, 2008
             http://godplaysdice.blogspot.ca/2008/11/heuristic-derivatio
n-of-prime-number.html

[3] Probabilistic Sieve of Eratosthenes, by Joriki, 2012
   http://math.stackexchange.com/questions/171208/probabilistic-sieve-of-
eratosthenes

[4] Differential Equation Modeling Distribution of Primes, by Babak,
2008       http://mathforum.org/kb/message.jspa?messageID=6295296

[Bhupinder Singh Anand]

On Friday, January 27, 2017 at 6:39:24 PM UTC+5:30,

jstephe...@gmail.com wrote:

> I would dearly like to know a legitimate rationalization of
> Equation 1, but fear that the explanation is buried deep in complicated
> number theory that I won't understand.

============
Dear Stephen,

1. Your 'heuristic' argument is not wrong in any significant sense,
since it can be converted into an elementary proof of the Prime Number
Theorem. See, for instance:

https://foundationalperspectives.wordpress.com/2014/07/07/an-elementary-
residue-based-proof-of-the-prime-number-theorem/

2. Your [Eq'n 1] is correct because the Prod_n = (1-1/2) (1-1/3)
(1-1/5) ....  (1-1/p_n) is, indeed, the non-heuristic probability that
any given integer in the range (p_n)^2 to (p_n+1)^2 is a prime.
Moreover, it yields a binomial probability distribution for the number
(p_n+1)^2.Prod_n of primes leq (p_n+1)^2, with a binomial standard
deviation.

3. The proof of (2) is not immediately obvious, but highly significant.

4. It requires first expressing Eratosthenes sieve explicitly as a
2-dimensional matrix, rather than as a 1-dimensional sequence of
crossed out composites and uncrossed primes; and then
showing---contrary to conventional wisdom---that whether or not a prime
q divides a given integer n is independent of whether or not a prime q
=/= p divides n.

5. Note that, for any n, your method of using the first n primes to
estimate the number of primes in the interval (p_n)^2 to (p_n+1)^2 will
always under-estimate the actual number of primes in the interval;
because the proportion of numbers divisible by p_n in the range (p_n)^2
to (p_n+1)^2  is less than the proportion of integers divisible by p_n
in the range 1 to (p_n+1)^2.

6. This is illustrated graphically in the following comparative values
of actual and non-heuristically estimated number of primes leq 3000
:

https://foundationalperspectives.files.wordpress.com/2017/01/40_pnt_dir_
twin_appendix-ii.pdf

7. Prima facie this suggests, anomalously and heretically, that the
function pi(n).In(n)/n must have a discontinuity in the limit, which is
determined by the Prime Number Theorem!

Kind regards,

Bhup

[barr...@sympatico.ca]

Thank you for your comments, Bhup.
I was particularly interested in your document that you referenced:
Comparative values of actual and non-heuristically estimated numbers of
primes <= 3000.
Under Fig. 13, you note that the difference between the heuristic and
actual prime densities is a factor of ~1.12292

This difference is the reason that I did not base my proof on your
second comment on my post, where you say that  Prod_n = (1-1/2) (1-1/3)

(1-1/5) ....  (1-1/p_n) is, indeed, the non-heuristic probability that
any given integer in the range (p_n)^2 to (p_n+1)^2 is a prime.

I think that you meant to say that Prod_n is the heuristic probability,
whereas the actual probability or density is given by (1.781/2) Prod_n.
 [below my Eqn 8, where (1.781/2) is the inverse of your ~1.12292]  

Prod_n looks like the probability that a number is prime because,
heuristically, one expects that each prime divisor p_k in the Sieve of
Eratosthenes will remove a proportion 1/p_k of the integers that
smaller primes left behind in the range.  But this is wrong by a factor
of 1.12292.  So, that is the reason that I did not want to base my
proof on Prod_n.  Instead, I made two assumptions, the second of which
was that the prime divisor p_n removes a proportion 1/p_n of the
integers left behind by smaller primes.  That turned out to be an even
worse assumption, wrong by a factor of approximately 2.5. My incorrect
Assumption 2 was balanced by my incorrect Assumption 1, leading to a
correct Eqn 1 and a correct expression of the PNT.

All of the heuristic proofs that I have seen, including mine, begin
with assumptions that appear plausible but are actually incorrect.
 That drives me crazy!  If nobody can produce a heuristic proof that is
based on correct assumptions, I think that we need a kind of PNT for
Dummies that explains Selberg¹s or Erdos¹ proof in a way that
non-mathematicians can understand.

[Bhupinder Singh Anand]

Dear Stephen,

1. All proofs of PNT, whether analytic or elementary, only define
pi(n)1 heuristically in terms of other arithmetical functions, and then
show that pi(n)1.log(n)/n tends to 1 as x tends to infinity.

2. They do not prove that the definition pi(n)1 corresponds to pi(n)2
if the latter is defined as the actual number of primes less than or
equal to n for finite values of n.

3. In other words, they all make a heuristic estimate based on
sieves---such as those of Eratosthenes or Brun etc.---for guessing that
x/log(x) estimates the number of primes less than or equal to x for
finite values of x.

4. On the other hand, it can be rigorously proven that the product
considered by you, i.e., Prod_n = (1-1/2) (1-1/3) (1-1/5) ....
 (1-1/p_n) is, indeed, a non-heuristic probability that any given
integer in the range (p_n)^2 to (p_n+1)^2 is a prime; and that it
yields the binomial probability distribution for the number
(p_n+1)^2.Prod_n of primes leq (p_n+1)^2---with a binomial standard
deviation which estimates (and accounts for) the divergence between the
actual values pi(n)2 and the values of the two products that I
considered in Figs 12 and 13 of my note.

5. I suspect that if we enter the actual values of n/log(n) in the
graphs, they will differ even more from the actual values pi(n)2. It
would be interesting to compare since I did not consider this aspect in
my original investigation. See:

https://www.researchgate.net/publication/282905908_The_Curious_Reluctanc
e_to_Define_Prime_Probability_Statistically_An_elementary_probability-ba
sed_approach_to_estimating_prime_counting_functions_statistically

6. What I find curious is that unless we can show---or prove---that the
graph of the product you consider intersects the graph of the actual
values of pi(n)2 at least once, there is no basis for concluding that
n/log(n) actually does estimate pi(n)2 for finite values of n!

Regards,

Bhup