Consequences of Legendre's conjecture

Question

I am looking for a list/reference which explores the consequences of Legendre's conjecture, which states that one can always find a prime number between $n^2$ and $(n+1)^2$.

Answer 1

In the absence of much other contributions yet this still being open, I promote my slightly expanded comments to an answer:

The Legendre conjecture, while of historical relevance, nowadays does not seem to play too much of a role in research, it is thus unlikely to have many things that are specifically consequences of this conjecture.

On should think of this conjecture of a bound on maximal gaps between consecutive primes. On the one hand it yields directly a bound of size about $4 \sqrt{p} +4$ for the bound between a prime $p$ and the next largest one. On the other hand, would one know that the gap between a prime $p$ and the next one is always at most $2 \sqrt{p} + 1$ the Legendre conjecture would follow.

Now, the study of the maximal size of gaps between primes is an important subject and actively persued and knowledge there has certain implications and consequences. See http://en.wikipedia.org/wiki/Prime_gap for a start.

However, what is known at least conditionally on the Riemann Hypothesis is somewhat close to Legenerdre's conjecture, namely a bound on the gap of order $\sqrt{p} \log p $; and to get a bound just slightly larger than $\sqrt{p}$ say $p^{1/2+\varepsilon}$ is immediate under RH.

Also, unconditionally one knows (by result of Baker, Harman, and Pintz from 2001) that for large $x$ every interval $[x,x + x^{0.525}]$ contains a prime, which in some sense is not too far away from Legendre's conjecture.

This reinforeces the idea that Legendre's conjecture specifically does not have that many consequences, as the margin between what one knows (possibly admitting RH) and Legendre's conjecture is not that large.

Moreover, all the above is far from the expected truth. It is believed that the size of the gaps is bounded by something of the order of $(\log p)^2$, which is a lot smaller than $\sqrt{p}$. A relevant key-word here is 'Cramér conjecture'.

So, in brief results and conjectures on bounds on gaps between primes are relevant, but Legendre's conjecture specifically seems mainly (only?) of historical value.

To also give an example of something where bounds on gaps would have consequences:

Given a prime $p$, can one find the next largest prime in polynomial time (of course, polynomial in $\log p$)?

Admitting a bound of size $O((\log p)^2)$, or any bound polynomial in $\log p$, on prime gaps this would be a direct consequence of the fact that prime-testing can be done in polynomial time (AKS-test) and progressively checking the numbers. However, without this, this is not known. There was a recent Polymath-project on this, see the paper "Deterministic methods to find primes", Math. Comp. 2012

Answer 2

I am given credit here for a conjecture that I did not make (on the maximal gaps between consecutive primes). This is also wrong in Wikipedia (can someone please correct that?).

What I noted, on page 24 of my paper, "Harold Cramér and the distribution of prime numbers, Scandanavian Actuarial J., 1 (1995) 12- 28" is that if one includes in Cramér's model the fact that every pth integer is divisible by $p$, for small primes $p$, then

$\limsup_{n\to \infty} (p_{n+1}-p_n)/ (\log p_n)^2 \geq 2e^{-\gamma} .$

Cramér's conjecture is that the limsup equals 1 (which is smaller than $2e^{-\gamma}$) and so is likely to be false (even if there is not enough computational evidence yet to say that). I have not made a conjecture as to the correct value of the limsup.