MathLabs

Arithmetic and number theory

Goldbach's conjecture

The unproven claim that every even integer greater than 2 is the sum of two primes.

IntuitionEvery even number, split into two primes?

Try it by hand: 4=2+24=2+2, 6=3+36=3+3, 8=3+58=3+5, 10=3+7=5+510=3+7=5+5, 100=3+97=11+89=17+83=29+71=41+59=47+53100=3+97=11+89=17+83=29+71=41+59=47+53. Every even number anyone has ever checked — trillions of them — splits into two primes, usually in several ways. The claim that this always works, for every even n>2n>2, is Goldbach's conjecture; nobody has ever found a counterexample, and nobody has ever proved there isn't one.

Graph of primes below n with edges highlighting pairs summing to n, illustrating Goldbach representations.
Primes up to 6060 highlighted in green via the Sieve of Eratosthenes: verify Goldbach's conjecture on the grid by expressing any even number 2k≤602k \le 60 as the sum of two green prime cells.

UndergraduatePrecise statement and variants

Definition: Goldbach representation count

For even nn, let r(n)=#{(p,q):p,q prime, p≤q, p+q=n}r(n) = \#\{(p,q) : p,q \text{ prime},\, p\le q,\, p+q=n\} count the unordered representations of nn as a sum of two primes. The strong (binary) Goldbach conjecture states that n=p1+p2n = p_1 + p_2 has a solution in primes p1,p2p_1,p_2 for every even n>2n>2, i.e. r(n)≥1r(n)\ge1.

r(n)=#{(p,q):p,q prime, p≤q, p+q=n}r(n) = \#\{(p,q) : p,q \text{ prime},\, p\le q,\, p+q=n\}

A different, weaker statement is the ternary (or "weak") Goldbach conjecture: every odd n>5n>5 is a sum of three primes, n=p1+p2+p3n = p_1+p_2+p_3. Historically Goldbach's 1742 letter to Euler proposed a version of the ternary statement (counting 11 as prime, as was then customary); Euler reformulated the now-standard binary statement. The two conjectures have very different status today, summarized in the table below.

n=p1+p2+p3,n odd, n>5n = p_1+p_2+p_3, \qquad n \text{ odd},\ n>5
Binary vs. ternary Goldbach: status today
CriterionBinary (strong)Ternary (weak)
Statementn=p1+p2n = p_1 + p_2n=p1+p2+p3n = p_1+p_2+p_3
StatusOpenProved (Helfgott, 2013)
Best unconditional partial resultChen's theorem (1973): prime + semiprimeFully resolved for all n>5n>5

UndergraduateTwo proved theorems on the way to Goldbach

There is N0N_0 such that for every even n>N0n>N_0, n=p+mn = p + m where pp is prime and mm is either prime or a product of exactly two primes (a semiprime).

Why is it true?

This is the closest anyone has come to proving binary Goldbach with a fully rigorous, unconditional argument: it relaxes 'prime' to 'prime or semiprime' on one side, which sieve methods can handle even though they cannot isolate primes exactly.

Proof

The proof is a weighted sieve argument. Fix large even nn and consider, for each prime p≤np\le n, whether n−pn-p has few prime factors. A naive sieve (Selberg's upper-bound sieve) can show that the count of p≤np\le n for which n−pn-p has at most two prime factors is not too small — but a plain sieve alone cannot distinguish "n−pn-p prime" from "n−pn-p has 3,4,…3,4,\dots prime factors" strongly enough to conclude anything.

Chen's key device, the weighted (or "switching principle") sieve, assigns each candidate pp a weight built from two different sieve levels: an upper-bound sieve for the "bad" event that n−pn-p has three or more prime factors below a threshold z≈n1/3z\approx n^{1/3}, and a lower-bound sieve for the total count of p≤np\le n with n−pn-p coprime to all primes below zz. Subtracting a suitably weighted multiple of the first from the second produces a combinatorial sum that is provably positive once nn is large — showing that some pp survives with n−pn-p having at most 22 prime factors above the threshold, i.e. n−pn-p is prime or a semiprime.

Making "provably positive" work requires estimating a bilinear form coming from the sieve remainder terms, using results of Bombieri–Vinogradov type on the distribution of primes in arithmetic progressions to large moduli (on average over moduli up to about n1/2−εn^{1/2-\varepsilon}); this is the deepest analytic input, and it is why the theorem needs nn "sufficiently large" rather than holding for all nn from the start.

The theorem stops at "prime or semiprime" and not "prime or prime" because sieve methods suffer from the parity problem: standard sieve weights cannot, by their construction, tell numbers with an even number of prime factors apart from numbers with an odd number, so they can never sieve down to primes alone from this kind of argument — semiprime is the sharpest target sieve theory can currently reach.

Every odd n>5n>5 satisfies n=p1+p2+p3n = p_1+p_2+p_3 for some primes p1,p2,p3p_1,p_2,p_3. I.M. Vinogradov proved this in 1937 for all sufficiently large odd nn; H. Helfgott completed the proof in 2013, removing the "sufficiently large" restriction and establishing it for every odd n>5n>5.

Why is it true?

This is the deepest unconditional success of the circle method applied directly to the primes, and it turns the binary Goldbach conjecture from a completely open problem into one where at least the odd-sum analogue is fully settled.

Proof

The proof follows the circle method exactly as sketched earlier in this branch of number theory, applied to the von Mangoldt-weighted exponential sum F(α)=∑p≤nlog⁡p  e(pα)F(\alpha)=\sum_{p\le n}\log p\; e(p\alpha), with representation count weighted by ∫01F(α)3e(−nα) dα\int_0^1 F(\alpha)^3 e(-n\alpha)\,d\alpha.

On the major arcs (short intervals around rationals a/qa/q with qq small), the Siegel–Walfisz theorem on primes in arithmetic progressions — uniform for moduli qq up to any fixed power of log⁡n\log n — lets one evaluate the integral there explicitly, producing a main term 12S(n) n2\tfrac12\mathfrak S(n)\,n^2 where S(n)\mathfrak S(n), the "singular series," is a product of local densities, one for each prime, measuring how often nn is solvable as p1+p2+p3p_1+p_2+p_3 modulo that prime. For odd nn, every local condition is solvable (there is no obstruction analogous to the parity obstruction that plagues the binary case), so S(n)\mathfrak S(n) is bounded away from 00, and the main term is genuinely positive and of size n2n^2.

On the minor arcs, Vinogradov's exponential-sum estimate for primes — a highly nontrivial bound ∣F(α)∣≪n(log⁡n)4/q1/2|F(\alpha)|\ll n(\log n)^4/q^{1/2} valid there — shows the contribution is o(n2)o(n^2), strictly smaller than the main term, so it cannot cancel the positive contribution from the major arcs. Combining the two gives a representation count that is positive once nn is large enough, which is Vinogradov's 1937 theorem.

Helfgott's 2013 completion made every step above fully explicit rather than merely "sufficiently large": sharper major-arc and minor-arc estimates (including explicit, computer-verified bounds on zeros of Dirichlet LL-functions up to a specific height) closed the gap between the explicit threshold where the analytic argument works and the range that had already been checked by direct computer search, yielding an unconditional proof for literally every odd n>5n>5.

UndergraduateReal-World Applications and Worked Examples

Goldbach-type prime-sum structures appear as sanity checks in cryptographic key generation (large numbers built from prime combinations should not accidentally simplify), and segmented-sieve algorithms developed to hunt for Goldbach representations feed directly into the same computational-number-theory toolbox used to search for large primes for RSA-style cryptosystems. The verification of the conjecture by computer for every even number up to 4×10184\times10^{18} is itself a landmark achievement in algorithm engineering and distributed computing, requiring carefully parallelized segmented sieves across many machines.

Example: Counting representations of 100

Find r(100)r(100), the number of ways to write 100100 as an unordered sum of two primes.

Solution

Scan primes p≤50p\le50 and check whether 100−p100-p is also prime. p=3p=3: 9797 is prime. p=11p=11: 8989 is prime. p=17p=17: 8383 is prime. p=29p=29: 7171 is prime. p=41p=41: 5959 is prime. p=47p=47: 5353 is prime. Checking the remaining primes below 5050 (2,5,7,13,19,23,31,37,432,5,7,13,19,23,31,37,43) gives composite partners (98,95,93,87,81,77,69,63,5798,95,93,87,81,77,69,63,57 respectively).

Collecting the successes: 100=3+97=11+89=17+83=29+71=41+59=47+53100=3+97=11+89=17+83=29+71=41+59=47+53.

Counting these unordered pairs gives r(100)r(100) = 66, matching the well-known value for n=100n=100.

Example: Chen's theorem in action

Illustrate Chen's theorem for n=98n=98: find a prime pp such that 98−p98-p is prime or a semiprime, and identify which case occurs.

Solution

Try p=19p=19: 98−19=7998-19=79, which is prime, so this already satisfies the stronger binary Goldbach statement (a bonus, since 9898 is small enough that both conjectures are verified directly by search, not just Chen's weaker guarantee).

To see the "prime or semiprime" alternative that Chen's theorem specifically guarantees in general, try p=7p=7: 98−7=91=7×1398-7=91=7\times13, a product of exactly two primes — a semiprime. So p=7p=7 exhibits the semiprime branch of Chen's theorem: 98=7+9198=7+91 with 9191 a semiprime, not itself prime.

This distinction matters: Chen's theorem only guarantees that some such pp exists with n−pn-p prime or semiprime; it does not by itself guarantee the stronger "prime or prime" outcome. For n=98n=98 we happen to find both a genuine Goldbach pair (19+7919+79) and a genuine semiprime witness (7+917+91), but Chen's proof method alone would only have delivered the latter kind of guarantee for astronomically large nn where direct search is infeasible.

Which statement is the strong (binary) Goldbach conjecture?

What is r(100)r(100), the number of ways to write 100100 as an unordered sum of two primes?

Which of the following is what Chen's theorem actually proves?

What does the computer verification of Goldbach's conjecture for every even number up to 4×10184\times10^{18} illustrate in computer science?

References

  1. H. A. Helfgott (2013). The ternary Goldbach conjecture is true · arXiv:1312.7748
  2. J. R. Chen (1973). On the representation of a larger even integer as the sum of a prime and the product of at most two primes · DOI:10.1360/ya1973-16-2-157
  3. T. Oliveira e Silva, S. Herzog, S. Pardi (2014). Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4×10184\times10^{18} · DOI:10.1090/S0025-5718-2013-02787-1