Goldbach Conjecture Research

by

Mark Herkommer
July 2024

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...

n = 30
30 = 7 + 23
16 = 3 + 13
10 = 3 + 7
4 = 2 + 2


n = 98
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.

n = 30
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:

n = 100
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:

probability n can be partitioned
nprobability
10000.996208045988
20000.999838315754
30000.999999069064
40000.999999693974
50000.999999983603
60000.999999999995
70000.999999999875
80000.999999999978
90001.000000000000
100001.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.

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

Return to the Herkommer Site