Skip to content

Goldbach: A Curious Conjecture

November 11, 2019

Models of the primes

[ Montreal ]

Andrew Granville writes brilliant papers that explain hard results in number theory. He also proves hard results in number theory.

Today, Ken and I use the famous Goldbach conjecture to discuss a third rail: how to identify which results “should be” true even though they have been too hard to prove.

Granville has just recently published a graphic novel, Prime Suspects: The Anatomy of Integers and Permutations, with his sister Jennifer Granville and illustrator Robert Lewis. It features constables named Green and Tao, a detective Jack von Neumann, and students named Emmy Germain and Sergei Langer among other allusions to real (and complex) mathematicians. It grew out of a 2009 musical play that premiered at IAS.

The driver of the plot is a deep connection between the frequency of primes below a number {x} and that of permutations in {S_N} that are “prime” in the sense of having only one cycle. Substituting {\log(x)} for {N} and vice-versa tends to create correspondences of known results in number theory vis-à-vis permutation group theory. See this MAA review. Going beyond the known theorems described in the novel, we wonder how far such heuristic sleuthing methods can go on long-unsolved cases.

The Goldbach Reminder

The statement we know as the (Strong) Goldbach Conjecture is that every even number {n \ge 4} can be written as the sum of two prime numbers. It was made in 1742 by Christian Goldbach. He wrote to Leonhard Euler:

“Every integer that can be written as the sum of two primes can also be written as the sum of as many primes as desired, until all terms are {1}.”

Well, that is not what we call Goldbach’s conjecture. He and many others at the time considered {1} to be a prime number. What he’s getting at can be seen from this snippet of his letter:

Above his sums, Goldbach put an asterisk * to the note in the margin, in which he asserts his conjecture:

“Every integer greater than 2 can be written as the sum of three primes.”

Wait—that is not the Goldbach conjecture either. It is the “Weak” one and was apparently proved in 2013 by Harald Helfgott. We discussed this in a 2014 post whose larger theme we are continuing here. It also proves the first conjecture, but not the strong conjecture.

But what Goldbach seems to be driving at with his drawing of sums is having one of the “primes” be {1}. Then the strong conjecture is needed. Euler pointed this out in his reply to Goldbach’s letter. But Euler, who was a saint in many ways, charitably reminded Goldbach of a communication earlier that year when Goldbach had observed that his first conjecture followed from the strong statement. Euler went on to say:

“That every even number should be a sum of two primes I hold to be a completely certain theorem, irrespective of my not being able to prove it.”

Ken has translated this a little differently from Wikipedia’s article and its source, reading into Euler’s words the stance of truth shining apart from proof. How one can justify this stance is what we want to discuss.

A Curious Conjecture

The conjecture is curious on several fronts. For one it is usually said to be “obviously correct.” It has been checked to about {10^{18}} or so by computation. There are many open conjectures in number theory that are likely to be true. But few are claimed to be “true” with such a strong bias. Many other conjectures are likely to be true, but none as likely as the Goldbach.

In 1975, Hugh Montgomery and Robert Vaughan proved that the Goldbach is true for most even numbers. That is that the number of possible even numbers {x} less than some {N} are not sums of two primes grows like {o(N)}. Thus if one picks a random even number {x} it is likely to be the sum of two primes. Here the “likely” is a mathematical certainty.

How do we “know” that it is likely to be true? One source is the method of prime models. Primes are quite mysterious and hard to understand. So there are heuristic models that suggest we think of the primes as “random”. Of course this is silly, since the primes are a deterministic fixed sequence of numbers. But the hope is that the following is true.

If {\Gamma} is a statement about the primes that is with high probability in the random model, then it is true.

Of course this is nonsense.

But it is interesting nonsense. Harald Cramér has a model that is simple. Granville add some refinements to this model here and here. More recently William Banks and Kevin Ford and Terence Tao have a new model for the primes here.

These models are useful for making and thinking about number theory conjectures. Perhaps one day they will be able to really be used to determine truth. They are certainly good heuristics to have when studying the prime numbers. We are jealous. In complexity theory it would be wonderful to have anything like these models. Perhaps {\dots}

A Model Example

Cramér’s model is simple to state. Imagine that the primes {\cal P} are replaced by a random set {\cal R} by placing {n} in with probability {1/\ln n}. And we make these choices independently. The Fermat numbers are those

\displaystyle  2^{2^{n}} + 1.

The first of these

\displaystyle  3, 5, 17, 257, 65537

are prime. Fermat thought this continued but it is not true. Euler showed that the next is not a prime

\displaystyle  641 \times 6,700,417.

An interesting problem is are there any more prime Fermat numbers? Many believe that there are no more, or art most there are a finite number in total. Let’s look at using the model to understand the Fermat numbers:

\displaystyle\sum_{n=0}^{\infty} \frac{1}{\ln F_{n}} = \frac{1}{\ln 2} \sum_{n=0}^{\infty} \frac{1}{\log_{2}\left(2^{2^{n}}+1 \right)} = \frac{1}{\ln 2} \sum_{n=0}^{\infty} 2^{-n}  = \frac{2}{\ln 2}.

Therefore, the total expected number of Fermat primes is at most finite. Of course this is assuming the model is predictive.


Our friends at Wikipedia say:

As with many famous conjectures in mathematics, there are a number of purported proofs of the Goldbach conjecture, none of which are accepted by the mathematical community.

Try a Google search yourself for “Goldbach conjecture proved”. The top hits include several “proofs” that the conjecture is true. The proofs are all short and simple. All are believed to be wrong. I find it interesting that the proofs, in many cases, use a random like argument in there “proofs”. The trouble is that the above models are only heuristics. So the proofs seem to be incomplete.

Open Problems

Can we imagine getting heuristic models for complexity theory? For quantum algorithms perhaps. What would such heuristic models even look like? We wonder.

18 Comments leave one →
  1. November 11, 2019 11:40 am

    Re: Can we imagine getting heuristic models for complexity theory?

    On a related note, here’s one measure of complexity on the natural numbers, OEIS • A062537, the number of nodes in the “Riff” of n.

  2. November 11, 2019 4:16 pm

    Isn’t the analogous thing in complexity theory random oracle models?

  3. Kodlu permalink
    November 12, 2019 2:51 am

    I seem to have a hazy memory of work by Arratia et al (Barbour? Tavare?) on the connection between prime factorisation and cycle structure of permutations, from 15+ years ago, though I cannot recall the details.

  4. November 13, 2019 6:43 am

    You should post more on ML and deep L.

    • November 13, 2019 7:53 am

      Thanks for the feedback. In fact, another post on statistical ML—not specific to chess—is in the works.

  5. none permalink
    November 15, 2019 1:15 am

    There are heuristics for complexity, like P!=NP with a random oracle.

  6. none permalink
    November 15, 2019 1:18 am

    Another complexity heuristic: the simplex method has worst case exponential running time, but is P-time on almost all inputs (i.e. except for a set of measure 0). This was evidence that LP was in P and that was eventually proved. BPP=P (conjectured) is another thing like that.

    • rjlipton permalink*
      November 15, 2019 11:45 am

      Dear none:

      I think once met…am I right?

      Any way good point. The oracle idea is a kind of heuristic. I like that analogy.



  7. Yuly Shipilevsky permalink
    November 19, 2019 7:43 am

    Unknown series:

    • rjlipton permalink*
      November 19, 2019 10:28 am

      Dear Yuly Shipilevsky:

      These do look like they could be tough. Is there an application of any of these sums?



      • Yuly Shipilevsky permalink
        November 19, 2019 2:35 pm

        Dear Richard,

        Thank you for your response.

        I even didn’t think yet about possible applications.

        It would be interesting first to find
        the corresponding formulas for these sums, especially
        for series.

        Best regards,

  8. Pete permalink
    November 26, 2019 7:15 am

    With ‘none as likely as the Goldbach..’ – isn’t it true that numerical verification of Collatz is (by a factor 10 or so) ahead of Goldbach?

    • rjlipton permalink*
      November 27, 2019 3:39 pm

      Dear Pete:

      Sounds correct. But I might argue that one needs to check more. But I am not sure. Interesting question.




  1. Goldbach: A Curious Conjecture -
  2. Predicting When P=NP is Resolved | Gödel's Lost Letter and P=NP
  3. Our Thoughts on P=NP | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s