March 28, 2009 2:00 am

Legendre's Conjecture

Bertrand’s postulate states that for every positive integer n, there is always at least one prime p such that n < p < 2n This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.

Legendre’s conjecture states that there is a prime number between n² and (n+1)² for every positive integer n. It is one of the four Landau’s problems, considered as four basic problems about prime numbers. The other three problems are (i) Goldbach’s conjecture : can every even integer n > 2 be written as the sum of two primes ? (ii) Twin prime conjecture : are there infinitely many primes p such that p+2 is prime ? (iii) are there infinitely many primes p such that p-1 is a perfect square ? All these problems are open till date.

How about the following generalization of the Bertrand’s postulate :

• Does there exist a prime number p, such that kn < p < (k+1)n for all integer n>1 and k <= n ?

A positive answer for k = n would prove Legendre’s conjecture.
I proved the following theorem :

• Theorem : For any integer 1 < k < n, there exists a number N(k) such that for all n >= N(k), there is at least one prime between kn and (k+1)n.

My proof is based on Erdos’s proof of Bertrand-Chebyshev theorem and uses elementary combinatorial techniques without appealing to the prime number theorem. You can find a preprint on my homepage.