This site is supported by donations to The OEIS Foundation.

Goldbach conjecture

From OeisWiki
(Redirected from Goldbach's problem)
Jump to: navigation, search

Goldbach’s conjecture was first posed by Christian Goldbach to Leonhard Euler in a letter dated June 7, 1742.[1]

Conjecture (Goldbach’s conjecture, 1742). (Goldbach)

Every even number greater than or equal to 4 is the sum of two primes,[2] and every odd number greater than or equal to 7 is the sum of three primes.[1] Also, every even number greater than or equal to 6 is the sum of two odd primes, and every odd number greater than or equal to 9 is the sum of three odd primes.

The clause regarding even numbers is sometimes called the binary Goldbach conjecture or strong Goldbach conjecture, while the clause regarding odd numbers is sometimes called the ternary Goldbach conjecture or weak Goldbach conjecture.

Goldbach considered 1 to be prime,[1] as did most mathematicians in that day and age, but our modern exclusion of 1 from the primes[3] and inclusion in the units instead, makes the conjecture neither easier nor harder to prove or disprove.

Goldbach representations

See parts restricted to two primes for even numbers and three primes for odd numbers and parts restricted to two odd primes for even numbers and three odd primes for odd numbers.

Binary Goldbach representations

An odd prime and 2 add up to an odd number. Two odd primes add up to an even number.

Number of binary Goldbach representations

On its face, it makes sense for the conjecture to be true. Given an even number
n
, there are
⌈ n / 4⌉
ways to express it as a sum of two odd numbers (distinct or not), and there are
⌊  n / 4⌋
ways to express it as a sum of two distinct odd numbers. There are only two ways to express 8 as a sum of two distinct odd numbers, and one of those ways is a pair of odd primes (3 + 5). There are 8192 ways to express 32768 as a sum of two distinct odd numbers; it seems rather improbable that after examining all 8192 ways we would fail to find at least one that was a pair of primes. In fact, the number crunching that has been done so far suggests that as
n
gets larger there is a slowly rising lower bound for the number of different ways of choosing odd primes
p
and
q
such that
p + q = n
.[4] Henry Fliegel and Douglas Robertson have plotted the number of Goldbach representations for even numbers up to 10000: their graph shows that, for the range reviewed, as
n
gets larger, the minimum number of Goldbach representations for
n
also gets larger.[5] Finding a prime gap from
n
2
+ 1
to
n  −  1
would disprove the conjecture: it almost goes without saying that
p   ≤  
n
2
  ≤   q
(where
p
and
q
may be equal); therefore, if we can’t match any prime
p
up to
n
2
to one prime
q
equal or above (that is, to find a value of
q = n  −  p
that is prime), the conjecture is refuted. But when Pafnuty Chebyshev proved that there is always a prime between
n
2
and
n
(see Bertrand’s postulate), that did not automatically prove the Goldbach conjecture: that proof does not rule out the possibility that there is an
n
such that every
q = n  −  p
, for every prime
p   ≤  
n
2
, is either 1 or a composite number. This mismatch is farther reduced by the observation of Ramanujan primes which effectively states that there is more than one prime between
n
2
and
n
for
n > 10
.

The exclusion of 1 from the primes for the purposes of this conjecture only affects those even numbers that are one more than a prime. Requiring the primes to be distinct affects singly even numbers that are twice a prime. But given a large singly even number with millions of potential Goldbach representations, discarding one or two possibilities makes very little difference. Considering only odd primes also makes very little difference.

Expected number of binary Goldbach representations


This section of the article is under construction.            

Please do not rely on any information it contains.            


The number of odd primes in the upper half
[ 
n
2
, n  −  1]
is asymptotically equal to the number of odd primes in the lower half
[1,
n
2
]
, i.e.
n
log n
n / 2
log (n / 2)
 = 
n
log n
n
2 (log n − log 2)
n
2 log n
 ,
n / 2
log (n / 2)
 = 
n
2 (log n − log 2)
n
2 log n
 .
Since we consider even
n
, it means that
n
is congruent to 0, 2 or 4 modulo 6. Except for 2 and 3, all the primes are congruent to 1 or 5 modulo 6. Asymptotically, for each of the
n
2 log n
odd primes (essentially all congruent to 1 or 5 modulo 6) in the lower half, the probability of matching an odd prime in the odd numbers of the upper half is
3
log n
 ,
if
n
is congruent to 0 modulo 6, and
1
2
 ⋅  
3
log n
 = 
3
2
 ⋅  
1
log n
 ,
if
n
is congruent to 2 or 4 modulo 6, assuming a random distribution for the odd prime numbers, since, knowing that the first number is chosen to be prime (most likely congruent to 1 or 5 modulo 6),
  • if
    n
    is congruent to 0 modulo 6, it is the sum of a prime and an odd number congruent to 1 and 5 modulo 6 or 5 and 1 modulo 6;
  • if
    n
    is congruent to 2 modulo 6, it is the sum of a prime and an odd number congruent to 1 and 1 modulo 6; or 5 and 3 modulo 6 (however, the only prime of the form 3 modulo 6 is 3);
  • if
    n
    is congruent to 4 modulo 6, it is the sum of a prime and an odd number congruent to 5 and 5 modulo 6; or 1 and 3 modulo 6 (however, the only prime of the form 3 modulo 6 is 3);

and the probability of finding a prime among numbers congruent to 1 or 5 modulo 6 is 3 times higher than among all the congruences modulo 6.

Therefore the expected number of Goldbach representations is asymptotically

n
2 log n
3
log n
 = 
3
2
n
(log n) 2
 ,
if
n
is congruent to 0 modulo 6, and
n
2 log n
3
2 log n
 = 
3
4
n
(log n) 2
 ,
if
n
is congruent to 2 or 4 modulo 6, assuming a random distribution for the odd prime numbers.
Expected versus actual number of binary Goldbach representations
A002375 From Goldbach conjecture: number of decompositions of
2 n
into an unordered sum of two odd primes.
Expected versus actual number of binary Goldbach representations
n
A002375
(n)
2 n
2 n mod 6
Expected
990 164 1980 0
3
2
1980
(log 1980) 2
= 51.543675852525
991 59 1982 2
3
4
1982
(log 1982) 2
= 25.791009167649
992 64 1984 4
3
4
1984
(log 1984) 2
= 25.810176224539
993 116 1986 0
3
2
1986
(log 1986) 2
= 51.658678204902
994 60 1988 2
3
4
1988
(log 1988) 2
= 25.848497806895
995 84 1990 4
3
4
1990
(log 1990) 2
= 25.867652343366
996 118 1992 0
3
2
1992
(log 1992) 2
= 51.773605434694
997 53 1994 2
3
4
1994
(log 1994) 2
= 25.905948934307
998 56 1996 4
3
4
1996
(log 1996) 2
= 25.925090999703
999 112 1998 0
3
2
1998
(log 1998) 2
= 51.888457837959
1000 74 2000 2
3
4
2000
(log 2000) 2
= 25.963362697568
 
n
A002375
(n)
2 n
2 n mod 6
Expected
9990 906 19980 0
3
2
19980
(log 19980) 2
= 305.63154475796
9991 328 19982 2
3
4
19982
(log 19982) 2
= 152.82797964385
9992 326 19984 4
3
4
19984
(log 19984) 2
= 152.84018669318
9993 670 19986 0
3
2
19986
(log 19986) 2
= 305.704787054
9994 360 19988 2
3
4
19988
(log 19988) 2
= 152.86460014533
9995 438 19990 4
3
4
19990
(log 19990) 2
= 152.8768065482
9996 868 19992 0
3
2
19992
(log 19992) 2
= 305.77802547127
9997 382 19994 2
3
4
19994
(log 19994) 2
= 152.90121870767
9998 334 19996 4
3
4
19996
(log 19996) 2
= 152.91342446433
9999 730 19998 0
3
2
19998
(log 19998) 2
= 305.85126001126
10000 462 20000 2
3
4
20000
(log 20000) 2
= 152.93783533161
Why is the actual number of Goldbach representations 2 to 3 times the [calculated] expected number of Goldbach representations!?
3
2
n
(log n) 2
not equal to
3
2
1980
(log 1980) 2
when
n = 990
.

Where is the flaw in the above reasoning? Is this due to the fact that the prime numbers are not actually randomly distributed? The actual numbers are 2 to 3 times higher...!? See “(however, the only prime of the form 3 modulo 6 is 3)” above.

==> WOULD SOMEONE PLEASE VERIFY THE ABOVE REASONING!

If we investigate Goldbach’s comet (see A002372/graph) we effectively observe that there are two similar parts to the comet, the values of the upper part being typically double the values of the lower part.

Scrutinizing the b-file, we can see that the number of Goldbach representations for even numbers
2 n
congruent to 0 modulo 6} have approximately twice as many representations as their neighbors (
2 n
congruent to 2 or 4, modulo 6). Also, if you look at A002372/graph (Goldbach’s comet), it seems to have two parts, the lower third of the comet being similar to its upper two thirds, for which the above reasoning would suggest that the lower third (related to partitions into two primes for even numbers congruent to 2 or 4 modulo 6) has twice the number of points of the upper two thirds (related to partitions into two primes for even numbers congruent to 0 modulo 6, with probabilistically twice the number of representations as for the lower third, hence the upper part is
2
1 + 2
of the whole comet, if the [lower and upper] parts don't overlap and are contiguous), which means that the lower third has four times the density of the upper two thirds (again, assuming no overlap).

Goldbach’s comet for the number of binary Goldbach representations

See Goldbach’s comet in A045917/graph (number of decompositions of
2 n
into unordered sums of two primes).

Ternary Goldbach representations

Number of ternary Goldbach representations

A068307 From Goldbach problem: number of decompositions of
n
into a sum of three primes (
n   ≥   1
).
{0, 0, 0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 2, 1, 3, 2, 4, 2, 3, 2, 5, 2, 5, 3, 5, 3, 7, 3, 7, 2, 6, 3, 9, 2, 8, 4, 9, 4, 10, 2, 11, 3, 10, 4, 12, 3, 13, 4, 12, 5, 15, 4, 16, 3, 14, 5, 17, 3, 16, 4, 16, 6, 19, 3, 21, 5, 20, ...}
A007963 Number of (unordered) ways of writing
2 n + 1
as a sum of 3 odd primes (
n   ≥   0
).
{0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 6, 8, 7, 9, 10, 10, 10, 11, 12, 12, 14, 16, 14, 16, 16, 16, 18, 20, 20, 20, 21, 21, 21, 27, 24, 25, 28, 27, 28, 33, 29, 32, 35, 34, 30, 37, 36, 34, 42, 38, 36, 46, ...}

Expected number of ternary Goldbach representations

(...)

Goldbach's comet for the number of ternary Goldbach representations

(...)

Proof of the ternary Goldbach conjecture

H. A. Helfgott claims to have proved the ternary Goldbach conjecture. In a 2012 paper, he expounds on “minor arcs” for the Goldbach conjecture. This he followed up with a paper almost exactly a year later on “major arcs,” which builds on the previous paper. Helfgott’s proof has not yet been verified by others.

See also

Notes

  1. 1.0 1.1 1.2 Clawson (1996): p. 236.
  2. Thomas Koshy, Elementary Number Theory with Applications. Harcourt Academic Press (2002): p. 116.
  3. It is now considered as the empty product of primes, thus 1 has no prime factors.
  4. Clawson (1996): p. 238.
  5. Clawson (1996): p. 242.

References

  • Calvin C. Clawson, Mathematical Mysteries: The Beauty and Magic of Numbers, New York and London: Plenum Press (1996).
  • H. A. Helfgott, Minor arcs for Goldbach’s theorem, arXiv:1205.5252 [math.NT] (Submitted on 23 May 2012)
  • H. A. Helfgott, Major arcs for Goldbach’s theorem, arXiv:1305.2897 [math.NT] (Submitted on 13 May 2013)

External links