# Consequences of Legendre's conjecture

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$.

-
Since in my opinion Legendre's conjecture is mainly of historical value, as opposed to having in itself a proper prominent place in current research, the motivation for this seems unclear. Voting to close. –  quid Nov 25 '12 at 8:51
may be interesting to look at KConrad answer mathoverflow.net/questions/17209/… Item c) briefly discusses Legendre conjecture and GRH, etc. –  Alexander Chervov Nov 26 '12 at 6:23
May be it's now of historical value, but still it's unsolved. I was discussing with my friend on its implications. On the wiki, we just found that its truth allows to have stricter bound on gaps of primes (as mentioned at the wikipedia page). So I was looking if there is some literature on this. –  Nirakar Neo Nov 26 '12 at 8:45
Are you looking on literature on gaps between primes or consequence of Legendre's conjecture? I mean Legendre's conjecture implies a bound on gaps between primes, is direct, indeed IMO it essentially is a conjecture on gaps between primes, or primes in short intervals, stated in an (by nowadays standards) unnatural way, which is my point: What is the worst case for two consecutive primes $p,q$ if LC is true $n^2$ and $(n+2)^2$ (well one could save a bot but let us ignore this). So the difference is max $4n + 4$ and $\sqrt{p}$ being at least $n$ you get a bound of $4\sqrt{p} + 4$ for $q-p$. –  quid Nov 27 '12 at 9:38
Conversely if you knew the gap between consecutive primes was always at most $2 \sqrt{p} + 1$ you would get LC. To repeat my point: LC todays seems like quite an arbitrary conjectue; very very likely it is true since much stronger things are believed to be true. See here en.wikipedia.org/wiki/Prime_gap –  quid Nov 27 '12 at 9:47

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

-
In case you didn't see it: there is a comment by Granville below –  Yemon Choi Feb 26 '13 at 8:11
@Yemon Choi: thank you for the notification (though in this case I would have noticed it without). –  quid Feb 26 '13 at 11:35

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.

-
Welcome to MathOverflow, Prof. Granville At the moment (assuming you are indeed Andrew Granville), the best we can do is make references to this post; we can't assume any influence over Wikipedia. However, it is likely the community can help make the changes you request. If you also register at tea.mathoverflow.net, you can make a post asking for assistance in making such corrections. In any case, I am confident the MathOverflow community can help. Gerhard "Ask Me About System Design" Paseman, 2013.02.25 –  Gerhard Paseman Feb 26 '13 at 2:54
Thank you for bringing this to my (or our) attention! As you mention this (mis)attribution is wider-spread (and does not originate with me). On "Cramér-Granville conjecture": it is also mentioned in a different form on MathWorld mathworld.wolfram.com/Cramer-GranvilleConjecture.html (there is is just the O((log p_n)^2) conjecture with some constant strictly greater than 1. It is now not clear to me if you are comfortable this weaker conjecture being attributed to you, so I mention it. Also, if I may ask: do you just not conjecture the limsup is this or do you not believe it? –  quid Feb 26 '13 at 11:27
In this answer I now simply removed the mention of this more precise form, as it is not crucial; I believe however to be aware of some other places on MO where this comes up, and as far as I oversee it will try to correct these over a shorter period of time. (I am however not active on Wikipedia.) –  quid Feb 26 '13 at 11:39
Somebody already changed the Wikipedia page, but I am not completely convinced this change fully addresses the problem. –  quid Feb 26 '13 at 12:27
Thanks for getting those changes made! I am not keen on making conjectures if we have little or no evidence for any particular answer. What is evident from calculations is that $\max_{n\leq N} (p_{n+1}−p_n)/(\log p_n)^2$ grows slowly to its limit. It is possible that the limit is $2e^{-\gamma}$, but perhaps it is $\infty$? Who knows? There is no convincing heuristic, and it is evident that this is a delicate question. –  Andrew Granville Apr 2 '13 at 20:23