Why doesnt Bertrand's postulate imply Legendre's conjecture?

  • Thread starter camilus
  • Start date
  • Tags
    Conjecture
In summary, Bertrand's Postulate has been proven by various mathematicians, including Ramanujan and Paul Erdos, using different methods. Ramanujan's proof, using an alternate formulation of Legendre's conjecture, is particularly advanced and short. While there is a belief that Bertrand's Postulate implies Legendre's conjecture, it has been shown that it does not, as the intervals for Bertrand's Postulate and Legendre's conjecture are not equivalent. Additionally, Mathematician M. El Bachraoui proved in 2006 that for n > 2 there is a prime p satisfying 2n < p < 3n. This result is weaker than Legendre's conject
  • #1
camilus
146
0
I mean, according to my knowledge, Bertrand's postulate has already been proved, I've already read and understood one, but Paul Erdos, and a few other mathematicians have proved it using various methods. I just finished reading Ramanujan's proof. Its amazingly advanced, and really short. The porblem of the inequality that Ramanujan uses to prove Bertrand's postulate is amazingly similar to an alternate formulation of Legendre's conjecture.

Well, I played a little bit with other representations of the Prime Counting Function and Ramanujan's inequality of the alternate formulation of Legendre's, and just assuming Bertrand's postulate to be true (which it has already been proved as I mentioned), I found a rather elementary (and obvious) proof of Legendre's.

Can anyone explain why they say that Bertrand's postulate doesn't imply Legendre's conjecture? I read about the supposed error ratio of the Prime Number Theorem, so if anyone knows about this would they be so kind to elaborate why BT doesn't imply LC?
 
Physics news on Phys.org
  • #2
camilus said:
Can anyone explain why they say that Bertrand's postulate doesn't imply Legendre's conjecture?

Yes. Bertrand's Postulate shows that there is a prime between n^2 and 2n^2, not in the far shorter interval n^2 to (n+1)^2. You'd need something just slightly stronger than the Riemann Hypothesis to get that.
 
  • #3
CRGreathouse said:
Yes. Bertrand's Postulate shows that there is a prime between n^2 and 2n^2, not in the far shorter interval n^2 to (n+1)^2. You'd need something just slightly stronger than the Riemann Hypothesis to get that.

Wow, I think you got your definition of Bertrand's incorrect.

wiki said:
Bertrand's postulate (actually a theorem) states that if n > 3 is an integer, then there always exists at least one prime number p with n < p < 2n − 2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2n.
 
  • #4
So in fact, your argument about the shorter interval is completely incorrect. In the opposite.

BP says that there is atleast one prime p that n<p<2n. Any by analyzing the interval between n and 2n for all n is simple:

2n - n = n.

the interval between any 2n and n will always be n. If n=100, than 2n=200. the interval between 2n and n is 2n-n=200-100=100=n.

now, the interval between between n^2 and (n+1)^2 is actually bigger than the interval between n and 2n.
 
  • #5
camilus said:
So in fact, your argument about the shorter interval is completely incorrect. In the opposite.

Nope.

camilus said:
now, the interval between between n^2 and (n+1)^2 is actually bigger than the interval between n and 2n.

Yes, but you need to use n^2 not n. If you use the 2n-2 version, this gives you a prime between n^2 and 2n^2 - 2.

If this doesn't make sense, you don't understand Bertrand's Postulate.
 
  • #6
pardon me, you're right I just analyzed the interval substituting n=x2 and saw that the interval is much much tighter. Just compare the graphs of y=x and y=2√(x)+1.

I apologize, I see what you're talking about now. Thanks.

And it's regardless of which version you use, the n<p<2n version gave me the same result. It's a theorem, it has to.
 
  • #7
camilus said:
I apologize, I see what you're talking about now. Thanks.

No problem, I just thought I needed to write something to get you to look over it again yourself. I was tempted to write [itex]2\sqrt x+1[/itex] myself, but it's a lot better when you can find it on your own. :smile:
 
  • #8
Bertrand's Postulate states: For n > 1, there is a prime p satisfying n < p < 2n.

M. El Bachraoui proved in 2006: For n > 2, there is always a prime p satisfying 2n < p < 3n.

In general, if you were to prove: For all n >= k >= 1, there is always a prime p satisfying kn < p < (k+1)n, then you would have shown Legendre, since if you allow k = n, then you have that prime p satisfies n^2 < p < n^2 + n < (n+1)^2.

The reason that Bertrand does not imply Legendre is by examining the intervals for Bertrand: [n,2n] and Legendre: [n^2, (n+1)^2] we can see that Legendre is a "tighter" interval.

e.g. Suppose we want the lower bound to be 100, then we allow each intervals lower bound to be the n value that produces 100, so we have

Bertrand (n=100) -> [100, 200] and
Legendre (n=10) -> [100, 121]

e.g. Again, we want our lower bound to be 25, then

Bertrand (n=25) -> [25, 50]
Legendre (n=5) -> [25, 36]

This can be proven, but I am too lazy to do so right now.


I have actually spent the last 8 months on proving that there is always a prime in the interval [kn, (k+1)n] for n >= k >= 1, and it is under review for a journal as we speak... err, I guess as we type. HeH.
 
Last edited:
  • #9
kyleballiet said:
M. El Bachraoui proved in 2006: For n > 2, there is always a prime p satisfying 2n < p < 3n.

Cite?

That sounds like a cute result. Weak (like Bertrand's Postulate), but perhaps sometimes useful -- and probably hard to prove.
 
Last edited:
  • #10
It's interesting to note that Chebyshev was the first to show Bertrand in 1850, and Erdos stated it elementarily in 1932 although it wasn't until 2006 when Bachraoui showed [itex][2n, 3n][/itex].

Another interesting thing is that Erdos checked the values for [itex]n = 1, 2, ..., 96[/itex], and Bachraoui had to check from 2 until 945. It is believed that in order to show each case you need to check exponentially many beginning cases.

You can find Bachraoui's proof via this URL: http://www.m-hikari.com/ijcms-password/ijcms-password13-16-2006/elbachraouiIJCMS13-16-2006.pdf

The worst thing is, both Erdos and Bachraoui's proofs are simplistic by most proof techniques, yet Legendre's conjecture has been around for over 150 years.

Another interesting conjecture is by Dorin Andrica, who stated the following: For all [itex]n>0[/itex], let [itex]p_{n}[/itex] denote the n-th prime number, then [itex]\sqrt{p_{n+1}} - \sqrt{p_{n}} < 1[/itex]. In fact, if Andrica's Conjecture is proven, then Legendre is a direct corollary. I believe the converse is true as well, though I have been unable to find a proof on the internet.
 
Last edited:
  • #11
kyleballiet said:
I have actually spent the last 8 months on proving that there is always a prime in the interval [kn, (k+1)n] for n >= k >= 1, and it is under review for a journal as we speak... err, I guess as we type. HeH.

Any chance you'd send me a preprint? Or is this on the arXiv?
 
  • #12
Throw me an E-mail: my user name on here @gmail.com and I'll be happy to send a pre-print to you.
 
  • #13
camilus said:
I just finished reading Ramanujan's proof. Its amazingly advanced, and really short. The porblem of the inequality that Ramanujan uses to prove Bertrand's postulate is amazingly similar to an alternate formulation of Legendre's conjecture.

Regarding Ramanujan's proof of the Bertrand postulate , I am unable to understand the 2nd equation that he uses ...

He starts the proof like this , let v(x) be the sum of logarithms of all primes less than or equal to x, Now consider :
[tex]\Psi[/tex](x) = v(x) + v (x^[1/2]) + v(x^[1/3]) + ... - eq.1

then he writes :
log ( [x] ! ) = [tex]\Psi[/tex](x) + [tex]\Psi[/tex](x/2) + [tex]\Psi[/tex](x/3) + ... -eq.2

where [x] is the greatest integer <= xWhy is equation 2 valid ... it certainly does not seem to be an obvious statement to me ... Can someone please explain how to derive eq 2 , given eq 1 . I was able to follow the steps of Ramanujan's proof after the 2nd equation ( assuming that there exists some Sterlings approx of which he talks about ... nd that the result of the approx is what he mentions it to be ) ... but please help me with the 2nd step .. Is there something that is very clear to everyone else that I am missing here ??
 
  • #14
Ok ... I was able to show that eq 2 ..i.e :

log ( [x] ! ) = [tex]\Psi[/tex](x) + [tex]\Psi[/tex](x/2) + [tex]\Psi[/tex](x/3) + ...

is indeed valid.

But still this was not at all obvious to me , and only after reading the lemma 2 part in the wikipedia proof of Bertrands postulate ( http://en.wikipedia.org/wiki/Proof_of_Bertrand's_postulate) ... and then thinking for quite some time was i able to see that eq 2 is indeed valid.
In order to prove lemma 2 , wikipedia states that

The exponent of p in n! is
[tex]\sum[/tex] [n/p^j]
where summation is from j=1 to infinity , and [ ] is the greatest integer function.

I see that the above statement which is easily proved (but even to see that this was true ,again took me some time ) , does in fact lead to equation 2 that Ramanujan has used .
I guess I certainly do not have the mental faculty to comprehend such things that are quite obvious to others.
 
  • #15
kyleballiet said:
Another interesting conjecture is by Dorin Andrica, who stated the following: For all [itex]n>0[/itex], let [itex]p_{n}[/itex] denote the n-th prime number, then [itex]\sqrt{p_{n+1}} - \sqrt{p_{n}} < 1[/itex]. In fact, if Andrica's Conjecture is proven, then Legendre is a direct corollary. I believe the converse is true as well, though I have been unable to find a proof on the internet.

I was able to see that Andrica's Conjecture does indeed lead to Legendre's Conjecture .

Regarding the converse - i.e. given Legendre's Conjecture , then Andrica's Conjecture also holds . -- I can see that if Legendre,s Conjecture is stated for real values of n > 1 , and not just integer values of n , then Legendre does indeed imply Andrica.
But did Legendre state the Conjecture for only integers or for all real values as well ? I think it was stated for only integers , because if he wanted to state it for real values he could have said that there exists a prime b/w n & n + 2 * sqrt(n) +1 , instead of n^2 and (n+1)^2

If Legendre only quoted for integers , then I do not see Legendre leading to Andrica ... but I may be wrong.
 
  • #16
srijithju said:
I was able to see that Andrica's Conjecture does indeed lead to Legendre's Conjecture .

Regarding the converse - i.e. given Legendre's Conjecture , then Andrica's Conjecture also holds . -- I can see that if Legendre,s Conjecture is stated for real values of n > 1 , and not just integer values of n , then Legendre does indeed imply Andrica.
But did Legendre state the Conjecture for only integers or for all real values as well ? I think it was stated for only integers , because if he wanted to state it for real values he could have said that there exists a prime b/w n & n + 2 * sqrt(n) +1 , instead of n^2 and (n+1)^2

If Legendre only quoted for integers , then I do not see Legendre leading to Andrica ... but I may be wrong.

I believe a proof of Legendre -> Andrica may go something like the attachment.

Also, if Legendre's Conjecture is proven, it not only guarantees that there's a prime in the interval... it actually gurantees that there are 2 primes satisfying the inequality. This may be easily shown, but I haven't typed up the proof yet.
 

Attachments

  • LegendreAndricaImplication.pdf
    34.9 KB · Views: 376
  • #17
kyleballiet said:
I believe a proof of Legendre -> Andrica may go something like the attachment.

Also, if Legendre's Conjecture is proven, it not only guarantees that there's a prime in the interval... it actually gurantees that there are 2 primes satisfying the inequality. This may be easily shown, but I haven't typed up the proof yet.

It looks to me like your proof that legendre implies andrica , is implicitly assuming that there are 2 primes between n^2 and (n+1)^2 . But Legendre guarantees only the existence of a minimum of one. If there is only 1 prime bw n^2 and (n+1)^2 , then I am unable to follow how you conclude that sq( n^2 + 2n) - sq( n^2 + 1 ) < 1 implies that sq(p(n+1)) -sq(p(n)) < 1
because only one of p(n) or p(n + 1) needs to lie in the interval :
(n^2 + 1 , n^2 + 2n) according to legendre , not both .
 
  • #18
I have to echo srijithju here. Let me give my own reasoning.

Suppose that Legendre's conjecture holds, but only barely: there is a huge prime gap near n^2. In particular, the closest primes to n^2 are
(n-1)^2 + a
and
(n+1)^2 - b
for small a and b. So the prime gap is of length
(n+1)^2 - b - (n-1)^2 - a = 4n - a - b.

Now Andrica's conjecture has the convenient form
p_n+1 - p_n < 2sqrt(p_n) + 1
(this follows naturally from the fact that sqrt(p_n + 2sqrt p_n + 1) - sqrt(p_n) = 1).

So in this case we have
4n - a - b < 2sqrt((n-1)^2 + a) + 1 < 2sqrt((n-1)^2 + a + a^2/4) + 1 = 2(n-1) + a + 1 = 2n + a - 1
that is
2n < 2a + b - 1
which is false for a,b small as assumed.Basically, the gaps allowed in Legendre's conjecture are two times too long for it to imply Andrica's conjecture.

(On an unrelated note, there's a bad error in your pdf relating to the order of quantifiers.)
 
Last edited:
  • #19
i think we can agree that a stronger legendre's conjecture (there is at least 2 primes between consecutive squares) implies andrica's easily.

proof:

if k^2 < pn < p(n+1) <(k+1)^2 than applying sqrt

k< sqrt(pn) < sqrt(p(n+1)) < k+1

the smaller interval must fit in the bigger one so

sqrt(p(n+1)) - sqrt(pn) < k+1 - k = 1

i really don't think legendre's and andrica's are equivalent.
 
  • #20
astroultraman said:
i think we can agree that a stronger legendre's conjecture (there is at least 2 primes between consecutive squares) implies andrica's easily.

No, not really.* You showed that that p(n+1) and pn are not a counterexample to Andrica's conjecture, but this does not rule out all possible counterexamples, only ones between two integer squares.

Just as above: Suppose your strong Legendre conjecture held, but only just barely:
(n-1)^2 + a = p1
(n-1)^2 + b = p2
(n+1)^2 - c = p3
(n+1)^2 - d = p4
are the only primes between (n-1)^2 and (n+1)^2, with a,b,c,d small. Then sqrt(p3) - sqrt(p2) is about 2 - (b+c)/2 or roughly 2, a counterexample to Andrica's conjecture.

* Technical note: I believe that both are true, so that trivially anything implies either one. You can choose to interpret my remark as "you haven't shown that SL implies A" or alternately that a sequence about which we know nothing but that the equivalent of SL holds in it need not have the equivalent of A hold in it. I prefer the latter approach.
 
  • #21
yea man you are right thanks, i forgot to think about the case where the square is between the consecutive primes and using only my previous reasoning i can only conclude that qrt(p3)-sqrt(p2)<2. In order to work the Strong Legendre should read something like this: there is always a prime between K^2 and (K+-1/2)^2 i think that will work.

Reading the forum i came across this
kyleballiet said:
Another interesting conjecture is by Dorin Andrica, who stated the following: For all [itex]n>0[/itex], let [itex]p_{n}[/itex] denote the n-th prime number, then [itex]\sqrt{p_{n+1}} - \sqrt{p_{n}} < 1[/itex]. In fact, if Andrica's Conjecture is proven, then Legendre is a direct corollary.
is this true? i would like to see some proof or reference.
 
Last edited:

1. Why is Bertrand's postulate not enough to prove Legendre's conjecture?

Bertrand's postulate states that for any positive integer n, there exists a prime number between n and 2n. However, this only guarantees the existence of one prime number in that range, not necessarily two consecutive primes.

2. What is the difference between Bertrand's postulate and Legendre's conjecture?

Bertrand's postulate is a weaker statement that only guarantees the existence of a prime number between n and 2n, while Legendre's conjecture states that there is always at least one prime number between two consecutive squares. In other words, Bertrand's postulate deals with a larger range of numbers, while Legendre's conjecture focuses on a specific pattern.

3. Can Bertrand's postulate be used to prove Legendre's conjecture?

No, Bertrand's postulate alone is not sufficient to prove Legendre's conjecture. While it is a useful tool in number theory, it does not provide enough information to prove the conjecture. Additional arguments and theorems are needed to establish the truth of Legendre's conjecture.

4. Are there any other postulates or theorems related to Bertrand's postulate and Legendre's conjecture?

Yes, there are several other related postulates and theorems, such as the Prime Number Theorem and the Bertrand-Chebyshev Theorem. However, none of these can directly prove Legendre's conjecture.

5. Is Legendre's conjecture still an open problem in mathematics?

Yes, Legendre's conjecture has not been proven or disproven, making it an unsolved problem in mathematics. Many mathematicians have attempted to prove it, but so far, no one has been successful. It remains an active area of research and a challenging problem in number theory.

Similar threads

  • General Math
Replies
1
Views
857
  • Linear and Abstract Algebra
Replies
2
Views
3K
  • Linear and Abstract Algebra
Replies
6
Views
3K
  • Linear and Abstract Algebra
Replies
7
Views
4K
  • Linear and Abstract Algebra
Replies
11
Views
2K
  • Linear and Abstract Algebra
Replies
6
Views
7K
Replies
6
Views
2K
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
4K
Replies
33
Views
5K
Back
Top