*Mark Herkommer
April, 2014
*

The Conjecture...

This conjecture dates from 1742 and was discovered in correspondence between Goldbach and Euler. It falls under the general heading of partitioning problems in additive number theory. Goldbach made the conjecture that every odd number > 6 is equal to the sum of three primes. Euler replied that Goldbach's conjecture was equivalent to the statement that every even number > 4 is equal to the sum of two primes. Because proving the second implies the first, but not the converse, most attention has been focused on the second representation.

The smallest numbers can be verified easily by hand:

6 = 3 + 3 | 8 = 3 + 5 | 10 = 3 + 7 | 12 = 5 + 7 |

14 = 3 + 11 | 16 = 3 + 13 | 18 = 5 + 13 | 20 = 3 + 17 |

22 = 3 + 19 | 24 = 5 + 19 | 26 = 3 + 23 | 28 = 5 + 23 |

30 = 7 + 23 | 32 = 3 + 29 | 34 = 3 + 31 | 36 = 5 + 31 |

38 = 7 + 31 | 40 = 3 + 37 | 42 = 5 + 37 | 44 = 3 + 41 |

46 = 3 + 43 | 48 = 5 + 43 | 50 = 3 + 47 | 52 = 5 + 47 |

Of course all the examples in the world do not a proof make.

Research On The Conjecture...

As a partitioning problem it is worth noting that as the numbers get larger
the number of representations grows as well:

12 = 5 + 7 |

24 = 5 + 19 = 7 + 17 = 11 + 13 |

48 = 5 + 43 = 7 + 41 = 11 + 37 = 17 + 31 = 19 + 29 |

This would suggest that the likelihood of finding that exceptional even number that is not the sum of two primes diminishes as one searches in ever larger even numbers.

Euler was convinced that Goldbach's conjecture was true but was unable to find any proof (Ore, 1948). The first conjecture has been proved for sufficiently large odd numbers by Hardy and Littlewood (1923) using an "asymptotic" proof. They proved that there exists an n0 such that every odd number n > n0 is the sum of three primes. In 1937 the Russian mathematician Vingradov (1937, 1954) again proved the first conjecture for a sufficiently large, (but indeterminate) odd numbers using analytic methods. Calculations of n0 suggest a value of 3^3^15, a number having 6,846,169 digits (Ribenboim, 1988, 1995a).

In 1966 Chen Jing-Run (1966) proved that every sufficiently large even number can be expressed as the sum of a prime and a number with no more than two prime factors (reprinted in Chen, 1973, 1978).

One can verify Goldbach's conjecture by brute force, up to a point. By using about 130 CPU-hours on an IBM 3083 Sinisalo (1993) verified the conjecture up to 4*10^11. Although Sinisalo used a bit array and Eratosthenes sieve, the QBASIC program that follows the similar strategy while employing trial division. The procedure is to take an odd number and then find small primes starting with 3, up to n/2. If p is prime then the difference n - p is tested for primality. If the difference is prime then we are done we have found a pair. The first pair found is the minimal Goldbach partition value.

To use the program, copy the following program to your clipboard. Next, open a text editor like Notepad and paste it in. Save it with the filename GOLDBACH.BAS. Then run it using QBASIC.

`
DECLARE FUNCTION IsPrime& (p&)
DEFLNG I-Z
CLS
INPUT "enter number to test: ", n
m = 0 ' number of pairs
PRINT : PRINT n;
FOR p = 3 TO n / 2 STEP 2
IF IsPrime(p) AND IsPrime(n - p) THEN
PRINT TAB(10); "="; p; "+"; n - p
m = m + 1
END IF
NEXT
PRINT : PRINT m; "distinct representations"
FUNCTION IsPrime (p)
IF p MOD 2 = 0 THEN
IsPrime = 0
ELSE
IsPrime = 1
FOR i = 3 TO SQR(p) STEP 2
IF p MOD i = 0 THEN IsPrime = 0: EXIT FOR
NEXT
END IF
END FUNCTION
`

If the Goldbach conjecture is true, then for a any even n there exists a prime p for which the complementary number q = n - p is also prime. The Goldbach partition shall be denoted by the representation n = p + q, where p and q are prime. The smallest prime in the Goldbach partition is indicated by partition function g(n).

Looking at the Goldbach partition graphically for n < 100,000

Be sure to note the scaling on the graph; there is a tremendous amount of vertical exaggeration. Each dark band in the graph represents a prime number: 3, 5, 7, 11, ... . This is a little bit confusing to understand, so lets look at a strictly increasing sequence of minimal values for n.

The table below shows the minimal values for n < 1,000,000,000 (It took
more than a *month* of 586 CPU time to create). The last column in the
table is the ratio g(n) / n. The ratio is particularly interesting because is
shows largest values of g(n) and we can see that it in almost every case is
less than its predecessor. It therefore strictly bounds above the minimal
Goldbach partition.

Table of minimal Goldbach partition values for n < 1,000,000,000:

n
g(n)
n - g(n)
g(n) / n
6
3
3
0.500000000
12
5
7
0.416666667
30
7
23
0.233333333
98
19
79
0.193877551
220
23
197
0.104545455
308
31
277
0.100649351
556
47
509
0.084532374
992
73
919
0.073588710
2642
103
2539
0.038985617
5372
139
5233
0.025874907
7426
173
7253
0.023296526
43532
211
43321
0.004847009
54244
233
54011
0.004295406
63274
293
62981
0.004630654
113672
313
113359
0.002753536
128168
331
127837
0.002582548
194428
359
194069
0.001846442
194470
383
194087
0.001969455
413572
389
413183
0.000940586
503222
523
502699
0.001039303
1077422
601
1076821
0.000557813
3526958
727
3526231
0.000206127
3807404
751
3806653
0.000197247
10759922
829
10759093
0.000077045
24106882
929
24105953
0.000038537
27789878
997
27788881
0.000035876
37998938
1039
37997899
0.000027343
60119912
1093
60118819
0.000018180
113632822
1163
113631659
0.000010235
187852862
1321
187851541
0.000007032
335070838
1427
335069411
0.000004259
419911924
1583
419910341
0.000003770
721013438
1789
721011649
0.000002481

Looking at the minimal Goldbach partition graphically for n <
1,000,000,000 we can observe an interesting relationship. For convenience and
to aid in the interpretation, the X axis is log10(n), while the Y axis is
g(n):

What the graph illustrates is what the data in the table assert, that the larger the number, the smaller the ratio between minimum g(n) and n. If this trend could be inviolably bounded below by some function, the conjecture would be proved.

Looking at the Goldbach partition a different way, we can look at the
number of distinct representations that exist for n. For example, as noted
at the beginning of this discussion:

12 = 5 + 7 (1 distinct representation)
24 = 5 + 19 = 7 + 17 = 11 + 13 (3 distinct representations)
48 = 5 + 43 = 7 + 41 = 11 + 37 = 17 + 31 = 19 + 29 (5 distinct representations)

The diagram that follows is sometimes called the "Goldbach Comet". It
shows that generally the number of distinct representations increases with
increasing n. If ever there was an n which had 0 distinct representations,
the conjecture would be false. However, the graph, at least for n < 100,000,
suggests the opposite.

An asymptotic approach appears to provide a possible avenue for
success in proving out the Goldbach Conjecture. This is the approach that I
am taking in my analysis of this problem.

A "Proof" That Goldbach's Conjecture Is True...

Pursuing this line of attack, let's start with an arbitrary even number n[0]:

Let

n[0] = p[0] + q[0]

and

n[1] = q[0] - p[0]

where p[0] and q[0] are distinct odd prime numbers, p[0] < q[0].

Now let

n[1] = p[1] + q[1]

and

n[2] = q[1] - p[1]

where p[1] and q[1] are distinct odd prime numbers, p[1] < q[1].

We continue in this manner until we arrive at

n[m] = p[m] + q[m]

and

n[m+1] = q[m] - p[m]

where p[m] and q[m] are not necessarily distinct odd prime numbers, p[m]
<= q[m], and n[m+1] = 0, 2, or 4.

We may reconstitute n[0] as

n[0] = 2*p[0] + 2*p[1] + 2*p[2] + ... + 2*p[m] + (0 or 2 or 4)

Therefore n[0]/2 is sum of a finite series of prime numbers, plus arbitrarily 0, 1, or 2.

Since 2 itself is prime, we can say

n[0]/2 = p[0] + p[1] + p[2] + ... + p[m] + (0 or 1)

The question now is:

Does a number n[0]/2 exist that cannot be represented as the sum of a
finite series of primes, plus 0 or 1?

Because we know that twin primes exist (two primes whose difference is 2),

and

because we may add 0, 1 arbitrarily,

and

because every interval (p, 2*p) contains at least one prime number,

we must conclude that the answer is NO.

Therefore has Goldbach's Conjecture been proved TRUE?.

... well no, not really. But we appear to be close ... just a little more work is needed ...

If we can show that for any given n we can go in the reverse direction,
*always being able to pick the correct primes to make the sum*, and
*ultimately reaching n*, then we are truly done.

The Algorithm In Action...

30 = 7 + 23 |

16 = 3 + 13 |

10 = 3 + 7 |

4 = 2 + 2 |

98 = 19 + 79 |

60 = 7 + 53 |

46 = 3 + 43 |

40 = 3 + 37 |

34 = 3 + 31 |

28 = 5 + 23 |

18 = 5 + 13 |

8 = 3 + 5 |

2 |

Another "Proof" That Goldbach's Conjecture Is True...

This is a slightly different line of attack, but it too has possibilities. This approach was first brought to my attention by Metin Aktay (May 22, 2000).

Let's start with a simple arithmetic partition of an arbitrary even number n (say, n = 30). This is the complete partition, primes are shown in bold italic.

3 |
27 |

5 |
25 |

7 |
23 |

9 | 21 |

11 |
19 |

13 |
17 |

15 | 15 |

You may think of the left column and right column as gears that are
meshing. Whenever you have two primes on the same row, the number n can be
partitioned. A number that would prove Goldbach's conjecture false would not
have a single row where both entries are prime. In this procedure we wish to
show that there will *always* be at least one row where both entries are
prime.

Here is where I depart from Mr. Aktay's method. Owing to the density of the primes (c.f. the Prime Number Theorem), from a probabilistic view, finding a partition can be shown to be "virtually" certain. Consider the partitioning of n = 100 using intervals of 10 numbers (5 odd numbers) to establish probabilities for prime number occurrence within the interval:

interval | % prime | matching interval | % prime | probability prime pair |
probability neither prime pair |
---|---|---|---|---|---|

0 - 10 | 60 | 90 - 100 | 20 | 0.12 | 0.88 |

10 - 20 | 80 | 80 - 90 | 40 | 0.32 | 0.68 |

20 - 30 | 40 | 70 - 80 | 60 | 0.24 | 0.76 |

30 - 40 | 40 | 60 - 70 | 40 | 0.16 | 0.84 |

40 - 50 | 60 | 50 - 60 | 40 | 0.24 | 0.76 |

The probability 100 can be partitioned = 0.7097. Of course we know that 100 can be partitioned, as can all the numbers in the table that follows. Its also easy to see why the probability rapidly increases as n increases. You simply have more intervals that could match up to produce a prime pair:

n | probability |
---|---|

1000 | 0.996208045988 |

2000 | 0.999838315754 |

3000 | 0.999999069064 |

4000 | 0.999999693974 |

5000 | 0.999999983603 |

6000 | 0.999999999995 |

7000 | 0.999999999875 |

8000 | 0.999999999978 |

9000 | 1.000000000000 |

10000 | 1.000000000000 |

Note that in these examples I explicity counted the primes in the interval. In this example the interval size is 10 for every n being partitioned. Larger interval sizes will product lower probabilities, but in all cases the probabilities converge toward 1. Also, the value 1.000... is actually a fraction less than 1.000...; it is only that the precision of the computer has been exceeded and the number has been rounded. It is therefore NOT absolute certainty as a probability of 1.000... would suggest. For large numbers the logarithmic integral can be used to achieve the same calculation without enumerating the primes.

With respect to this series, the probability increases so quickly that for any number greater than 10,000, a partition existing is a "virtual" certainty. Unless we can achieve 1.0 probability, there may yet be that one odd-ball number that does not produce a prime pair over any paired intervals.

Therefore (sadly), this too is not a proof. But it does afford us more
evidence that the conjecture is probably true.

Comments? Send them to: Mark Herkommer

*© Copyright, 1998 - 2014. All Rights Reserved.*
*Mark A. Herkommer*