mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-05-07, 01:19   #1
Unregistered
 

10011101010112 Posts
Default Counterexamples needed

I'm guessing that there is always a twin prime between n^3 and (n+1)^3, assuming n is a positive integer. However, I have no idea how to prove whether this is correct or not, so could someone give a counterexample to disprove my theory? I tried finding counterexamples, but I haven't found one yet.
  Reply With Quote
Old 2007-05-07, 16:21   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

Quote:
Originally Posted by Unregistered View Post
I'm guessing that there is always a twin prime between n^3 and (n+1)^3, assuming n is a positive integer. However, I have no idea how to prove whether this is correct or not,
If true, this would both imply the Twin Prime Conjecture (as yet unproven) and in fact make a much stronger statement. Barring an explicit counterexample it may be true, but rigorous proof is a whole different thing. Are you familiar with the large literature (including numerous failed proofs) of the TPC? That's where you should start.

Quote:
so could someone give a counterexample to disprove my theory?
Conjecture, not theory (or more properly in this context, theorem.) In this area, conjecturing stuff is easy, proving it tends to be much harder, and in many cases seemingly impossible.

Quote:
I tried finding counterexamples, but I haven't found one yet.
How high have you searched, and was this using your own program or the published tables of twin primes? Anyway, lack of an explicit counterexample can only hint at the possible truth of such a conjecture.
ewmayer is offline   Reply With Quote
Old 2007-05-07, 23:14   #3
Unregistered
 

3·31·59 Posts
Default

I did a manual search first. I used a calculator to calculate the cube of two consecutive numbers (10^3 and 11^3, for example), and then checked

http://primes.utm.edu/lists/small/1ktwins.txt

to see if there were any twins between those two numbers. I searched until 25^3, and I still couldn't find any counterexamples. So, I wrote a program that searched for counterexamples by checking whether there were any twins between n^3 and (n+1)^3. I stopped the program at n=1500 without finding any counterexamples, because it seemed that the higher n was, the more twins there were between n^3 and (n+1)^3.
  Reply With Quote
Old 2007-05-07, 23:15   #4
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

36210 Posts
Default

I've checked it to n=30000 using a (very) crude algorithm.
fetofs is offline   Reply With Quote
Old 2007-05-08, 19:20   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

In fact, to show just how far number theorists are from proving such a thing (assuming for the purposes of argument that it were true):

1) Chebyshev's theorem (formerly known in a slightly different form as Bertrand's postulate) states that for every n > 1 there is always at least one prime p such that n < p < 2n. As marvelous as Chebyshev's proof (and later ones by the likes of Ramanujan and Erdös) of this fact is, it is an incredibly weak result, especially since the data indicate that the maximum gap between consecutive primes at large n seems to behave as O((log n)2), which is asymptotically miniscule compared to the O(n) maximal gap that is proven by the above theorem. (The formal statement of the alleged log-squared behavior is known Cramér's conjecture; note also that this statement about *relative* gap size is not inconsistent with the proven result that a prime gap may have arbitrarily large *absolute* size)

2) There are some well-known results about the occurrence of multiple primes in intervals - from the above Wikilink:

"Erdös proved that for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n.

Erdös also proved there always exist at least two prime numbers p with n < p < 2n for all n > 6. Moreover, one of them is congruent to 1 modulo 4, and another one is congruent to -1 modulo 4.


However, given that from the Prime Number Theorem (PNT) we expect on average O(n/log(n)) primes between n and 2n for large n, this is still a comparatively weak proven lower bound. And it's even further from saying anything about the occurrence of *twin* primes in such an interval (except in the sense that twin primes would of course satisfy the +-1 modulo 4 requirement), which is moreover asymptotically much larger than your n^3 to n^3+O(n2) conjectured interval.

3) Again quoting from the above page, here is a conjecture in a similar form as yours, but much, much weaker in that it only asks if there is *one* prime in some interval smaller than O(n) - and it's of course unproven:

"A similar and still unsolved Legendre's conjecture asks whether for every n > 1, there is a prime p, such that n2 < p < (n + 1)2. Again we expect from the PNT that there will be not just one but many primes between n2 and (n + 1)2, but in this case the error estimates on the PNT are not (indeed, cannot be) sufficient to prove the existence of even one prime in this interval."

4) Even though it is widely believed to be true, despite centuries of effort by some of the brightest mathematical minds in history, it has not yet been proven that infinitely many twin prime pairs *exist*, much less subject to additional contsraints on their distributional density.

So, in short, we are quite a long way from proving anything along the lines you suggest. Good luck!
ewmayer is offline   Reply With Quote
Old 2007-05-09, 16:52   #6
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Thumbs up Excellent reply!

Quote:
Originally Posted by ewmayer View Post
In fact, to show just how far number theorists are from proving such a thing (assuming for the purposes of argument that it were true):

"Erdös proved that for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n.

Erdös also proved there always exist at least two prime numbers p with n < p < 2n for all n > 6. Moreover, one of them is congruent to 1 modulo 4, and another one is congruent to -1 modulo 4.


.

3) Again quoting from the above page, here is a conjecture in a similar form as yours, but much, much weaker in that it only asks if there is *one* prime in some interval smaller than O(n) - and it's of course unproven:

4) Even though it is widely believed to be true, despite centuries of effort by some of the brightest mathematical minds in history, it has not yet been proven that infinitely many twin prime pairs *exist*, much less subject to additional contsraints on their distributional density.

So, in short, we are quite a long way from proving anything along the lines you suggest. Good luck!


Thanks Ernst! That was an excellent up to date reply indeed.

I often re read Paul Hoffman's book 'Archimedes' Revenge' [pub.year 1990] for the elaborate section he gives on primes.

I quote a para which may be of some relevance for this thread.

" A mammoth treatise could be given about what is known and not known about primes. ....

It has been proved that there is at least one prime between any number greater then one and its double. ( A surprising consequence of this proof is that there are at least three primes having exactly n digits where n is any positive integer whatever.) [Get a load of that; its not as simple as it sounds]

[I have not come across that in a cursory scan of your post though I may have overlooked it in which case I am sorry]

To continue [ from the book] what you have already stated

" No one knows whether a prime lies between the square of any number greater than one and the square of its successor"

Mally

Last fiddled with by mfgoode on 2007-05-09 at 16:58 Reason: Adding bracket
mfgoode is offline   Reply With Quote
Old 2007-05-09, 19:30   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5×593 Posts
Default

Looking at the number of twin primes between n^3 and (n+1)^3 up to n=5000:

twintest.txt

The number is raising all the time, it seems unlikely there should be 0 in any interval above n=5000, but thats far from a proof.
ATH is online now   Reply With Quote
Old 2007-05-10, 10:56   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by ewmayer View Post
If true, this would both imply the Twin Prime Conjecture (as yet unproven) and in fact make a much stronger statement. Barring an explicit counterexample it may be true, but rigorous proof is a whole different thing. Are you familiar with the large literature (including numerous failed proofs) of the TPC? That's where you should start.



Conjecture, not theory (or more properly in this context, theorem.) In this area, conjecturing stuff is easy, proving it tends to be much harder, and in many cases seemingly impossible.



How high have you searched, and was this using your own program or the published tables of twin primes? Anyway, lack of an explicit counterexample can only hint at the possible truth of such a conjecture.


HUH?? No! No! No!

There is always a prime between n^3 and (n+1)^3. A proof exists.
This has nothing to do with the twin prime conjecture. See, for example,
Richard Guy's book "Unsolved Problems in NUmber Theory"

Let M = n^3. Then (n+1)^3 = n ^3 + 3n^2 + 3n + 1 = M+ O(M^2/3).
But a proof exists that there is always a prime between M and M^(11/20 + e) for any e > 0. I also think that the exponent 11/20 may have been lowered slightly. Note that 3M^2/3 is greater than M^(11/20 + e).
The Riemann Hypothesis would allow us to have M^(1/2 + e), but no
proof yet exists that allows the exponent to be lowered to 1/2.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-10, 12:20   #9
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
HUH?? No! No! No!
HUH?? Yes! Yes! Yes!
Reread the original post which ewmayer quoted: "I'm guessing that there is always a twin prime ... "
Jens K Andersen is offline   Reply With Quote
Old 2007-05-10, 12:42   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
HUH?? Yes! Yes! Yes!
Reread the original post which ewmayer quoted: "I'm guessing that there is always a twin prime ... "
Aha!. Clearly I missed the word "twin". Mea Culpa.

I think that this question does not even merit the word "conjecture"
because the evidence is too scant. I would call it an "open question".
I don't even know of any work on the expected gap between successive
twin primes. They are much rarer than primes themselves. We don't
even know if there is always a twin prime between (sufficiently large)
n and 2n.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-25, 17:18   #11
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

I have verified the statement for n up to 3,300,000.
No counterexamples exist in this range.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Goldbach's Conjecture: Hunting Counterexamples Christenson Math 19 2011-09-07 01:44
Serious help needed with Linux... gd_barnes No Prime Left Behind 6 2008-05-10 06:28
not needed zeit PrimeNet 3 2008-04-25 08:03
Help needed AntonVrba Math 3 2007-03-06 10:55
V24.12 QA help needed Prime95 Software 5 2005-06-17 15:54

All times are UTC. The time now is 12:30.

Tue Oct 20 12:30:31 UTC 2020 up 40 days, 9:41, 1 user, load averages: 3.40, 3.34, 3.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.