Twin Prime conjecture still not proven...

[Tez]

Tez-"Some guy here (Bell Labs) ..."

You work at Bellcore or is the "here" generic for "in the U.S."? (Just curious).

Hmm - no idea what Bellcore is.

I work at the Bell Labs which is attached to Lucent technologies - the place which brought you the laser, the transistor and the navel hair fluff remover...

www.bell-labs.com

T

 

[American]

One of the cool things about all of these problems is that the proof itself is not really that important, but it is assumed that the methods used to find the solutions will yield huge mathematical breakthroughs.

You might be the one to ask then-

Why can't we take all of the known mathematical concepts and model them (whatever that means) as computer algorithms. How many proven "concepts" are there? I have no clue, so I'll pick a number. 300.

That's a lot of coding, but let's assume this is a huge effort.

So then we apply each of those concepts in progressively longer combinations (as steps of a potential proof to some problem).

Is that a fesible way to prove conjectures? It's brute force searching, using all known principles. Sounds simple to me, can you tell me why it wouldn't work?

 

[to.by]

Because Kurt Gödel proved that in any axiomatic system of a certain complexity there will be at least one theorem that is not provable, that is you can't prove or disprove it.

 

[LW]

It's brute force searching, using all known principles. Sounds simple to me, can you tell me why it wouldn't work?

It has been tried, starting from the early 60s. The main reason why it doesn't really work is that the search space is way too large. For a rough estimate, if there are n different possible "proof steps" and the shortest proof is m steps long, then there are n^m possible proof candidates (this figure is very simplistic and only to give some rough idea about the sizes involved).

There are few mathematical theorems that have been proved automatically. The most well-known example is the 4-colorability of a planar graph (= "it is possible to color a map with only 4 colors so that no two adjacent countries have the same color"). However, that particular example is not clean in the sense that it was done by going through all possible structures that a planar graph may have and systematically finding a 4-coloring for each of them. The reason why this proof is not clean is that it is conceivable that some possible uncolorable planar structure was left out of the search (nobody has managed to find a counter example and it is probable that the search was really complete).

The first important theorem that was proven automatically was one showing that all Robbin algebras are boolean algebras that was proven in 1997. A number of heavy-weight mathematicians (including Tarski) had tried to prove it by hand, but all failed.

In general, automated theorem provers are not yet effective enough that they could find the proofs without help from a human. A mathematician has to choose what proof methods are used and often has to insert some lemmas into the problem encoding that guide the search of the prover to the right direction. The whole process is much like black magic.

 

[Tez]

There are few mathematical theorems that have been proved automatically. The most well-known example is the 4-colorability of a planar graph (= "it is possible to color a map with only 4 colors so that no two adjacent countries have the same color"). However, that particular example is not clean in the sense that it was done by going through all possible structures that a planar graph may have and systematically finding a 4-coloring for each of them. The reason why this proof is not clean is that it is conceivable that some possible uncolorable planar structure was left out of the search (nobody has managed to find a counter example and it is probable that the search was really complete).

Actually, the classification of all possible planar structures was done analytically with good old pen and paper proofs, and was checked many times by other humans. It just turned out there were too many of them to check their colorability by hand. So your objection that "something may have been missed" is not an objection specific to autmated proving - it applies to any mathematical proof....

 

[Dymanic]

I've discovered something about twin primes that puzzles me. If you count the intervening terms between sets of twin primes (not including the primes themselves) the resulting number is always divisible by three (that is, once you get beyond 2,3,5,7). I can't seem to put my finger on an explanation for this, and haven't been able to google up a reference to this specific phenomenon.

I suppose it's possible that I've made a mistake somewhere (it happens).

 

[xouper]

Dymanic: I've discovered something about twin primes that puzzles me. If you count the intervening terms between sets of twin primes (not including the primes themselves) the resulting number is always divisible by three (that is, once you get beyond 2,3,5,7). I can't seem to put my finger on an explanation for this, and haven't been able to google up a reference to this specific phenomenon. I suppose it's possible that I've made a mistake somewhere (it happens).

Assuming I understood your puzzle correctly, perhaps the explanation you are looking for is related to the following:

For any prime P larger than three, there exists an N such that either P=6N-1 or P=6N+1, and thus twin primes are always the pair 6N-1 and 6N+1. Obviously then, the middle number (6N) between any twin primes is always divisible by 6, or also as you noticed, 3.

Examples:

for N=2 we get 11,13
for N=3 we get 17,19
for N=17 we get 101,103
for N=135 we get 809, 811
etc

Example: 809 - 101 = 708 which is divisible by both 2 and 3.

Thus, for M>N, the count of numbers between any upper prime (6N+1) and any lower prime (6M-1) is divisible by three.

Of course, this is absolutely of no use as a test for primeness.

Does this help, or have I misundetstood your question?

 

[JesFine]

I've discovered something about twin primes that puzzles me. If you count the intervening terms between sets of twin primes (not including the primes themselves) the resulting number is always divisible by three (that is, once you get beyond 2,3,5,7). I can't seem to put my finger on an explanation for this, and haven't been able to google up a reference to this specific phenomenon.

I suppose it's possible that I've made a mistake somewhere (it happens).

All primes are of the form 6k +/- 1 (but not for all values of k). Twin primes would be a pair of primes described by 6k+1 and 6k-1. The distance between two such primes would also be divisible by 6 and that is probably what you are seeing. Obviously, if it is divisible by 6 it is also divisble by 3.

I couldn't find any impressive links but this one has some info near the end: http://www.sciencenews.org/20010602/mathtrek.asp

Marek Wolf of the Institute of Theoretical Physics at the University of Wroclaw in Poland, has been studying gaps between consecutive twin primes, typically measured as the arithmetical distance between the last primes constituting consecutive twins. For example, the distance between the twins (29, 31) and (17, 19) is 31 – 19, or 12. The distances are multiples of 6 because all twins are of the form 6k +/–1.

Edited to add: xouper snuck in while I was looking for a link. He also explained things better than I did. That is all.

 

[jj]

Tez-"Some guy here (Bell Labs) ..."

You work at Bellcore or is the "here" generic for "in the U.S."? (Just curious).

He's one of the few remaining labbies (At Lucent Bell Labs). He started just after I retired, I think.

 

[Diamond]

There's no mention of Goldbach's conjecture. Is there a prize for solving that one?

 

[JesFine]

There's no mention of Goldbach's conjecture. Is there a prize for solving that one?

There was a million dollar prize for anyone who could prove the Goldbach conjecture, but there was a deadline and I think it has passed. I bet if you solved it though, you would get some kind of prize... like a Fields Medal.

 

[Diamond]

There was a million dollar prize for anyone who could prove the Goldbach conjecture, but there was a deadline and I think it has passed. I bet if you solved it though, you would get some kind of prize... like a Fields Medal.

Probably somebody would find the glaring mistake on Page 1....