Saturday, July 26, 2014

Bertrand's "postulate" and Legendre's Conjecture

Bertrand's "postulate" states that for any positive integer $n > 1$, you can always find a prime number $p$ in the interval

$n < p < 2n$.

It use to be called "postulate" until it became a theorem when Chebyshev proved it in 1850.

(I saw this while browsing thru a group theory book and got interested to read up a little more.)

What if instead of looking at $n$ and $2n$ you looked at consecutive squares? So for example you take a positive integer $n$ and you ask whether we can always find at least one prime number between $n^2$ and $(n+1)^2$.

Turns out this is a much harder problem and it's still an open question called:

Legendre's Conjecture. For each positive integer $n$ there is at least one prime $p$ such that

$n^2 < p < (n+1)^2$.

People have used programming to check this for large numbers and have always found such primes, but no proof (or counterexample) is known.

If you compare Legendre's with Bertrand's you will notice that $(n+1)^2$ is a lot less than $2n^2$. (At least for $n > 2$.) In fact, the asymptotic ratio of the latter divided by the former is 2 (not 1) for large $n$'s. This shows that the range of numbers in the Legendre case is much narrower than in Bertrand's.

The late great mathematician Erdos proved similar results by obtaining k primes in certain ranges similar to Bertand's.

A deep theorem related to this is the Prime Number Theorem which gives an asymptotic approximation for the number of primes up to $x$. That approximating function is the well-known $x/\ln(x)$.

Great sources:
[1] Bertrand's "postulate"
[2] Legendre's Conjecture
(See also wiki's entries under these topics.)

No comments:

Post a Comment