Goldbach’s Conjecture and Goldbach’s Variation

Goldbach’s Conjecture is one of the great unresolved problems of number theory. It simply states that every even natural number greater than two is the sum of two prime numbers. It is easily confirmed for even numbers of small magnitude.

The conjecture first appeared in a letter dated 1742 from German mathematician Christian Goldbach to Leonhard Euler. The truth of the conjecture for all even numbers up to four million million million ( ${4\times 10^{18}}$ ) has been demonstrated. There is essentially no doubt about its validity, but no proof has been found.

The conjecture can never by verified by examining all the even numbers in turn: since this search is infinite, it can never be completed. However, if we consider a specific even number ${2N}$ , we can check, for every prime ${p}$ less than ${N}$ , whether ${2N-p}$ is also prime. If so, ${N}$ is the sum of these two primes. If not, then ${2N}$ is a counter-example that disproves the conjecture.

For any specific even number, this process must terminate in a finite number of steps. Of course, for an enormous number — such as a googol, ${10^{100}}$ — the search may be very long, but it must end after a finite number of trials.

Variation on a Theme

In his book Gödel, Escher, Bach: an Eternal Golden Braid, published in 1979, Douglas Hofstadter discussed an interesting modification of Goldbach’s Conjecture that he called Goldbach’s Variation. He wondered if any even number can be expressed as the difference of two odd primes.

Let us say that an even number has the Goldbach Sum (GS) property if ${2N = p_1 + p_2}$ for some pair of primes ${(p_1, p_2)}$ . And let us say that an even number has the Goldbach Difference (GD) property if ${2N = p_1 - p_2}$ for some pair of primes ${(p_1, p_2)}$ . Clearly the Goldbach Sum property can be established with a finite number of trials. However, for the Goldbach Difference property, the primes may be arbitrarily large: there is no guarantee that they can be found in any reasonable time.

The GS property is decidable: the answer can be found by a finite search. But the GD property appears to be undecidable: the answer may never be found, either because the relevant primes are huge or because they do not exist. A brute force search may never yield the answer. Worse still, if a number does not have the GD property, the search for a pair of primes whose difference yields the number is bound to fail, but we will never know.

Hofstadter concludes that “Searching through infinite spaces is always a tricky matter”.

Sources

${\bullet}$ Hofstadter, Douglas, 1979: Gödel, Escher, Bach: an Eternal Golden Braid. The Harvester Press, 777pp.

ThatsMaths