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.

## Proved?

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.

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

• November 11, 2019 12:34 pm

For the connection with computational complexity, see OEIS • A050924.

• November 12, 2019 7:40 am

There are definitions, discussion, and a motley assortment of examples here:

2. November 11, 2019 4:16 pm

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

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.

November 15, 2019 1:15 am

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

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.

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.

Best

Dick

November 19, 2019 7:43 am

Unknown series:

http://vixra.org/abs/1911.0317

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?

Best

Dick

November 19, 2019 2:35 pm

Dear Richard,

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,
Yuly

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?

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.

Best

Dick

February 6, 2020 3:18 pm

Dear Frank:

I like the idea trying to relate complexity theorem to number theory.

I think however that your proof fails. The point is your argument would show that the same is true for three primes: p+q+r = 2n+1. The same conclusion then follows. But that is not true since this is true for all n large enough. That is for all n large enough there always are primes p,q,r so that p+q+r = 2n+1.

Best

Dick

February 8, 2020 11:46 pm

https://zenodo.org/record/3660155

were erased in this post.

Why?

February 9, 2020 1:05 pm

https://zenodo.org/record/3660553

12. February 9, 2020 5:54 pm

The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity classes are P and NSPACE(S(n)) for some S(n). We prove if the complexity class P is equal to NSPACE(S(n)) for some S(n) = o(log n), then the weak Goldbach’s conjecture is false. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then we obtain that P is not equal to NSPACE(S(n)) for all S(n) = o(log n).

https://zenodo.org/record/3660671

February 12, 2020 9:30 pm

The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true as well.

https://zenodo.org/record/3665870

14. February 13, 2020 1:03 pm

The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples, where the contains of infinite number of counterexamples is statistically less unlike it.

https://zenodo.org/record/3666725