GUESSING THE PRIME NUMBER THEOREM AND TREACHEROUS LOGIC

August 19, 1999

 

The Prime Number theorem says that the probability P(x) that a large integer x is prime is about 1/log x. At about age 16 Gauss apparently conjectured this estimate after studying tables of primes. Greg Martin suggested to me the following heuristic way to approach the same conjecture.

Suppose that there is a nice probability function P(x) that a large integer x is prime. As x increases by  x = 1, the new potential divisor x is prime with probability P(x) and divides future numbers with probability 1/x. Hence P gets multiplied by (1 – P/x),  P = – P2/x, or roughly

P’ = – P2/x.

The general solution to this differential equation is P(x) = 1/log cx.

OLD CHALLENGE (via Charles Chace). Consider a statement of the form

(P and Q) => R if and only if (P => R) or (Q => R).

Is this a logical truth? What if

P is “ai is monotone”

Q is “ai is bounded”

R is “ai is convergent”

(where ai represents a sequence of real numbers).

ANSWER. As best explained by Mario Bourgoin, technically this IS a logical truth, which holds for any particular P, Q, R. Logically, P => R means that if P is true, then R is true; i.e., either R is true or P is false. Of course both sides of the given statement are true if R is true. Suppose R is false. Then each side holds precisely when P is false or Q is false.

For any particular nonconvergent sequence ai, either monotonicity implies convergence (because the sequence is not monotone) or boundedness implies convergence (because the sequence is not bounded). (Peter Hegarty points out that what is not true is the more common type of statement with “for all” through it: “for all sequences monotonicity implies convergence or for all sequences boundedness implies convergence.”)

The logic that a false statement implies anything is well illustrated by Ed Brahinsky’s response to a piano student’s claim to have practiced 200 hours one week: “If you practiced 200 hours this week, then I’m a monkey’s uncle.”

NEW CHALLENGE. Estimate the life span of the human race.

Send answers, comments, and new questions by email to [email protected], to be eligible for Flatland and other book awards. Winning answers will appear in the next Math Chat. Math Chat appears on the first and third Thursdays of each month. Prof. Morgan’s homepage is at www.williams.edu/Mathematics/fmorgan.

Copyright 1999, Frank Morgan.