Friday, December 11, 2009

Unsolved: Goldbach conjecture

The Goldbach conjecture is one of the oldest and easiest-to-understand math problems that remains unsolved. The problem was originally posed to Leonhard Euler in a letter from amateur mathematician Christian Goldbach in 1742. The original form of the conjecture, now known as the weak Goldbach conjecture says:
Every whole number greater than five is the sum of three prime numbers.

Euler restated the problem in an equivalent form, the strong Goldbach conjecture (or just the Goldbach conjecture):
Every even number greater than two is the sum of two primes.

So,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
...
100 = 47 + 53
...


Progress

In 1966, Chinese mathematician Chén Jǐngrùn showed that every sufficiently large even integer is the sum of a prime and semiprime (a number that has at most two prime factors).

Brute force methods have been used to show that the Goldbach conjecture is true for even integers up to about 1.5 * 1018* (1,500,000,000,000,000,000 or 1.5 billion billion).


Notes:


* Brute force results are as of July 24, 2009. See Goldbach conjecture verification for up-to-date results.

13 comments:

Troy said...

There is a class of conjectures of the form "for every N greater than (some small number), P(N) is true" which have been verified for N up to some very large number M.

When M gets large enough, most people will expect that the conjecture is true, even if there isn't a formal proof. Does anybody know which conjectures like this have been proven true for large M, and then proven to in fact be incorrect for sufficiently large N?

Bill the Lizard said...

Troy,
Excellent question. I don't know of any examples right off, but I'll certainly be on the lookout as I investigate other unsolved problems. It seems like there should at least be a few examples from the pre-computer age.

Niyaz said...

Troy,

Yes. I remember reading about some conjectures that were proved to be false for extremely large N.

eg: http://en.wikipedia.org/wiki/P%C3%B3lya_conjecture

The conjecture was disproved by a counter-example of value approximately 1.8 × 10^361. (Later smaller counter-examples were found)


Another false conjecture:
http://en.wikipedia.org/wiki/Mertens_conjecture

Don said...

simple proof of Goldbach Conjecture. If p is a prime number then p+1 and p-1 must be divisible by 2 since multiples of 2 vary by 2 and p+1 and p-1 vary by 2 and p is not divisible by 2. therefore
p(1) + p(2)= p(1)-1+p(2)+1. both
p(1)-1 and p(2)+1 are even therefore their sum is even.
Don Beck

Bill the Lizard said...

Don,
That proves that the sum of any two odd primes is even. It does not prove that every even number greater than two is the sum of two primes. These are two very different statements.

Don said...

yes i realilized that just after i posted the "simple" proof

Bill the Lizard said...

Don,
Don't feel bad. There have been countless times that I've thought I had a line on one of these problems and it turned out to be a dead end. Some of the greatest mathematicians in history have beat their heads against this particular wall, so we're in good company. :)

Bill the Lizard said...

Niyaz,
Thanks a lot for the links you provided. Once I get a few more entries in the "Unsolved" series, I plan to write a post addressing Troy's question in more detail. Those links look like a good starting point for my research.

Don said...

Bill re Goldbach conjecture, tell me where I am wrong. as shown earlier u+v=2N where u and v are any two prime numbers and N is either prime or even.
An even number can be expressed an E= 2M where M is either prime or even. If we choose any E then M is determined and we chose to make M equal to N or E=2M=2N=u+v: or any E is equal to sum of two prime numbers.
Don Beck

Troy said...

Don:

What was shown earlier was that u+v=2N where N is an integer, but not necessarily prime or even.

As a counterexample, take u=7, v=11. u+v=18=2*9. 9 is neither prime nor even.

Bill the Lizard said...

Don,
You said "An even number can be expressed an E= 2M where M is either prime or even."

Troy's counter-example is correct in showing that this is not always true. M can be any number at all and E will still be even. M doesn't have to be prime or even.

Another problem is in the statement "If we choose any E then M is determined and we chose to make M equal to N..." By choosing to make M equal to N, you're saying that you're choosing to define M as prime, which is what you're trying to prove. It ignores the fact that M might be even or an odd non-prime. If I understand you right, this is a form of common logical fallacy known as begging the question.

These types of traps are easy to fall into with problems like the Goldbach conjecture. With no counter-examples in sight, it's very easy to assume something is true.

Don said...

further re goldbach conjecture
anothe way of saying it. we know that a number N12 exists such that the sum of two primes
P1+P2=2*N12. 2*N12 is an even number say E12.but
E12+2 = 2*N12+2 =2*(N12+1).Since
N12 exists, 2*(N12+1) must also exist or E12 +2 exists. Therefore any even number can be expressed as the sum of two primes.
Don Beck
Don Beck

Bill the Lizard said...

Don,
That is another way of saying the same thing. But again, proving that the sum of two odd primes is even is not the same as proving every even number is the sum of two primes.