Consequences of Legendre's conjecture - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T07:45:38Z http://mathoverflow.net/feeds/question/114399 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114399/consequences-of-legendres-conjecture Consequences of Legendre's conjecture Nirakar Neo 2012-11-25T07:20:19Z 2013-02-26T11:31:37Z <p>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$.</p> http://mathoverflow.net/questions/114399/consequences-of-legendres-conjecture/121301#121301 Answer by Barış Can Tayiz for Consequences of Legendre's conjecture Barış Can Tayiz 2013-02-09T13:02:53Z 2013-02-09T13:10:43Z <p>I search the prime gap problem which is finding primes between n^2+n,n^2.If it is true than this will be.First easy way is considering prime number theorem while solving that. (n^2+n )/(lnn^2+n ) - (n^2)/ln⁡〖n^2〗 that is the equation which shows roughly number of primes.It can be transformed to (n^2+n )/(lnn^2+n ) - ((n+1)^2)/ln⁡〖(n+1)^2〗 because lim n→∞ ((n+1)^2)/(ln⁡(n+1)^2)>(n^2)/ln⁡〖n^2〗.That will narrow the gap.Then ıt can be shown as n/2.ln(n+1).Therefore there should be a prime number between n^2+n,n^2.(?).</p> http://mathoverflow.net/questions/114399/consequences-of-legendres-conjecture/121316#121316 Answer by quid for Consequences of Legendre's conjecture quid 2013-02-09T14:59:53Z 2013-02-26T11:31:37Z <p>In the absence of much other contributions yet this still being open, I promote my slightly expanded comments to an answer:</p> <p>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. </p> <p>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. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">http://en.wikipedia.org/wiki/Prime_gap</a> for a start. </p> <p>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. </p> <p>Also, <em>unconditionally</em> 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. </p> <p>This reinforeces the idea that Legendre's conjecture <em>specifically</em> does not have that many consequences, as the margin between what one knows (possibly admitting RH) and Legendre's conjecture is not that large. </p> <p>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 <em>a lot</em> smaller than $\sqrt{p}$. A relevant key-word here is 'Cramér conjecture'. </p> <p>So, in brief results and conjectures on bounds on gaps between primes are relevant, but Legendre's conjecture <em>specifically</em> seems mainly (only?) of historical value. </p> <p>To also give an example of something where bounds on gaps would have consequences: </p> <blockquote> <p>Given a prime $p$, can one find the next largest prime in polynomial time (of course, polynomial in $\log p$)? </p> </blockquote> <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 <a href="http://www.ams.org/journals/mcom/2012-81-278/S0025-5718-2011-02542-1/" rel="nofollow">"Deterministic methods to find primes", Math. Comp. 2012</a></p> http://mathoverflow.net/questions/114399/consequences-of-legendres-conjecture/122939#122939 Answer by Andrew Granville for Consequences of Legendre's conjecture Andrew Granville 2013-02-26T01:58:44Z 2013-02-26T01:58:44Z <p>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?). </p> <p>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</p> <p>$\limsup_{n\to \infty} (p_{n+1}-p_n)/ (\log p_n)^2 \geq 2e^{-\gamma} .$</p> <p>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.</p>