## Tuesday, May 28, 2013

### Heuristic ideas about bounded prime gaps

Why Yitang Zhang's proof is probably far less fundamental than the claim

Yitang Zhang worked at Subway before he would land a mathematics job. And when he did, he wasn't publishing almost anything for years before he would offer a proof of something rather important weeks ago. That turned the name of the popular math instructor in New Hampshire into one of the most well-known names of number theorists in the world. Bounded gaps between primes (Zhang's technical paper)
Philosophy behind the proof (Math Overflow)

First proof that... (Nature)

Prime number breakthrough by unknown professor (Telegraph)
If $$p_1,p_2,p_3,\dots =2,3,5,\dots$$ denotes the $$n$$-th prime, the statement proven by Zhang may be phrased in a very simple way:$\liminf_{n\to\infty} (p_{n+1}-p_n) \lt 70,000,000.$ The operator above is called the limit inferior which is just$\liminf_{n\to\infty}x_n := \lim_{n\to\infty}\Big(\inf_{m\geq n}x_m\Big)$ If you think about this limit of the infimum for a while, you will understand that the limit inferior in the claim proved by Zhang is just the smallest gap between the adjacent primes that is realized infinitely many times (for infinitely many pairs). In other words, there exists at least one number – a potential gap between adjacent primes – that is realized infinitely many times.

Because of some technical properties that probably depended on many personal choices that Zhang has made while attacking the problem, the upper bound in the inequality turns out to be a high number, namely 70 million. It is such a high number that for all practical purposes, the proposition proven by Zhang is de facto equivalent to$\liminf_{n\to\infty} (p_{n+1}-p_n) \lt \infty$ i.e. to the claim that there exists a finite number that is realized as the gap between adjacent primes in infinitely many pairs.

On the other hand, as I will argue, the actually correct (but rigorously unproven) claim stronger than Zhang's theorem says$\liminf_{n\to\infty} (p_{n+1}-p_n) = 2$ which means that even twin primes – pairs of primes that differ by two – are realized infinitely many times: there are infinitely many pairs of twin primes. This claim is the famous twin prime conjecture. In some sense, the assertion proven by Zhang is 35 million times weaker than the twin prime conjecture. Note that the first twin primes are$(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), \\ (71, 73), (101, 103), (107, 109), (137, 139), \dots$ and there doesn't seem to be the tiniest reason to think that the list should terminate at some point. The largest currently known twin prime pair is $$2,003,663,613\cdot 2^{195,000}\pm 1$$, two similar numbers that have 58,711 digits (each).

I don't plan to study the proof in detail because it looks very complicated and "non-unique" to me. The proven statement is slightly interesting but the proof is probably less interesting – there's just a small chance that I am wrong – and there's less "profound message" to learn from it. It's like if you are interested in the Moon and someone asks you to study O-rings in the Apollo spacecraft.

Moreover, I am not too interested in the claim that has been proved. But there is one more key reason: I feel certain that the proposition is true. The reason behind this certainty is the validity of a much stronger claim – a not quite rigorously defined one – that implies the twin prime conjecture, Zhang's proof, and many and many other much weaker corollaries. The claim is that
except for patterns that may be easily proved, the prime integers are distributed randomly and independently with $$1/ \ln n$$ being the probability that a random number close to $$n$$ is a prime.
This general – somewhat vague but still very important – claim has many consequences, including the Riemann Hypothesis. In fact, the character of the proposition above is more or less a special case of Gell-Mann's totalitarian principle in physics:
Everything that isn't forbidden is mandatory.
By this quote that generalizes the experience of the people suffering under totalitarian regimes such as communism and Nazism (there's no freedom: they tell you what to do and what not to do) to all of physics, Gell-Mann meant that the coefficient of every interaction in a Lagrangian or the probability of any resulting complicated process is nonzero unless one may use a symmetry or another rock-solid principle to prove that the coefficient is zero (because it violates the symmetry or another sacred principle).

In this analogy, "patterns that are easy to prove" are analogous to the "symmetries or other principles forbidding certain things". May I explain what I mean in the case of primes?

A pattern that is easy to prove is, for example, that if $$n$$ is a prime, then $$n+1$$ and $$n-1$$ are not primes, assuming that $$n\gt 3$$. It's because except for $$n=2$$, only odd numbers may be prime. Similarly, among six consecutive integers greater than $$12$$, just to be sure, at most two numbers may be primes. It's because only three numbers among the six are odd; and one of them is a multiple of three. One could continue with many examples of this kind.

Similarly, using the Gell-Mann totalitarian principle, one may demonstrate that the twin prime conjecture and its generalizations hold. There doesn't seem to be any reason why the difference between primes shouldn't be equal to two (or some other allowed even numbers) – there are many examples in which it is two, in fact – so there must exist infinitely many examples for the probability that $$n$$ and $$n+2$$ are both primes to be nonzero. Of course, it's hard to prove that "there is no reason why twin primes should stop at some point", either, but at least, one may prove that there exist no "reasons of the well-known types".

A TRF-based heuristic proof of the prime number theorem

Now, the density of primes around $$n$$ asymptotically goes like $$1/ \ln n$$. This is the right estimate for $$n\to\infty$$, including the right numerical prefactor (the relative error goes to zero in the limit). This statement is known as the prime number theorem and it is a severely weakened sibling of the Riemann Hypothesis which may be equivalently stated as the (easy-to-prove) assertion that the roots of $$\zeta(s)$$ only exist for $$s\in\RR$$ or in the critical strip $$0\leq {\rm Re}(s)\leq 1$$.

I can offer you a supersimple, Lumoesque argument why the density of primes goes like $$1/\ln(n)$$. Call the functional dependence of the density $$\rho(n)$$; it's really the probability that the number around $$n$$ is prime. A number $$n$$ is prime if it is not divisible by any prime smaller than or equal to $$\sqrt{n}$$. These are statistically independent conditions. So$\rho(n) = P_{n\in{\rm primes}} = \prod_{p\leq \sqrt{n}}^{p\in{\rm primes}} (1-1/p)=\dots$ because the probability that a random large $$n$$ isn't a multiple of $$p$$ equals $$1-1/p$$. But the product may be written as the exponential of the sum of logarithms$\dots = \exp\sum_{p\leq \sqrt{n}}^{p\in{\rm primes}} \ln (1-1/p) = \dots$ and the sum over primes $$p$$ may be approximated by the sum over all integers $$i$$ weighted by the probability $$\rho(i)$$ that $$i$$ is prime:$\rho(n) = \dots = \exp \sum_{i\leq\sqrt{n}} \rho(i) \ln (1-1/i).$ Now, the sum over $$i$$ may be approximated by an integral when $$\rho(i)$$ is smoothened. Take the logarithm of the identity above (with the sum replaced by the integral)$\ln\rho(n) = \dots = \int_1^{\sqrt{n}} \dd i\, \rho(i) \ln (1-1/i)$ and differentiate it with respect to $$n$$ to get$\frac{\rho'(n)}{\rho(n)} = \frac{1}{2\sqrt{n}} \rho(\sqrt{n}) \ln(1-1/ \sqrt{n})\sim -\frac{\rho(\sqrt{n})}{2n}$ where $$1/2\sqrt{n}$$ came from $$\dd(\sqrt{n})/\dd n$$ and where $$\ln(1-x)\sim -x$$ because $$x\to 0^+$$. One may easily verify that $$\rho(n)\sim 1 / \ln(n)$$ satisfies the identity above; both sides are equal to $$-1/ n\ln(n)$$ in that case. Among uniformly, nicely decreasing functions $$\rho(n)$$, this solution may be seen to be unique. Even the coefficient in front of the logarithm or, equivalently, the base of the logarithm ($$e$$) may be seen to be determined by the (nonlinear) condition above.

You may check how Terence Tao imagines a heuristic proof of the prime number theorem. I leave you to decide who among the two of us is the cumbersome overworked craftsman and who is the seer. ;-)

At any rate, the heuristic proofs above aren't rigorous but one may rigorously prove the prime number theorem. One may also prove other things. As you can see by comparing various proofs sketched by various people – or the same people at various moments – there are many strategies that may be used to attack similar problems. When we're rigorously proving something like that in mathematics, we often work with lots of inequalities – not only the final one that e.g. Zhang has proved; but also with many inequalities in the intermediate steps. And the inequalities are usually ad hoc. We want to find an object that is "good enough to achieve a certain next step" but how good this good enough object has to be isn't quite determined. What the next step has to be isn't quite determined, either. There's simply a lot of freedom when one designs a proof.

It's very likely that some other mathematicians will improve Zhang's proof so that they will reduce the constant 70 million to something smaller. Such proofs may be perhaps obtained as "modest mutations" of Zhang's machinery. However, it's unlikely that someone will reduce the constant 70 million to a constant smaller than 6 while keeping the bulk of Zhang's proof intact because certain tools become inapplicable for such small gaps (see the Math Overflow summary of the proof).

The proof of the actual twin prime conjecture will probably have to be completely different than Zhang's proof. It's nice that he has achieved a rigorous proof of a theorem that is a weaker version of the twin prime conjecture but I doubt that one can learn a lot by studying the details of his proof. There had to be so much freedom when he designed it. So it's like a NASA rocket engineer's decision to study every detail of a Soyuz aircraft. I don't think that this is the most important activity needed to conquer the outer space. Much like the Soyuz spaceships, Zhang's proof probably have many idiosyncrasies reflect the Russians' and the Chinese-American man's suboptimal approach to problems.

In mathematics and theoretical physics, when something is just being proved, we often encounter two different situations: in one subclass, the methods needed to prove something give us such new insights that these insights – methods, auxiliary structures that were used to complete the proof, and so on – are actually more valuable than the statement that has been proven. But I tend to think that Zhang's proof belongs to the opposite class of situations – in which the proof is less important than the assertion because it's composed of many idiosyncratic steps and tricks that are probably inapplicable elsewhere and that may be replaced by completely different "building blocks" to prove even the desired proposition.

Of course that I can't be quite sure about this pessimistic appraisal of the proof's methodology if I haven't actually mastered the proof. But because of general reasons and experience, I believe it's the case, anyway. Moreover, I tend to believe that the theorem proved by Zhang – and even the twin prime conjecture that may be proved in the future – is extremely weak relatively to some rigorous formulations of Gell-Mann's totalitarian principle applied here which says something like "the distribution of primes is random except for [simple divisibility-based] patterns that may be easily demonstrated". I tend to believe that such a principle will ultimately be formulated in a rigorous way and proved by a rather simple yet ingenious method, too.

You should understand that if I believe that this elegant goal is a legitimate, finite, $${\mathcal O}(1)$$ task for some future mathematicians, it's also reasonable for me to believe that the assertion by Zhang and its seemingly cumbersome proof is a nearly infinitesimal fraction of what mathematicians will achieve sometime in the future. Zhang's proof represents a kind of the cutting edge that the mathematicians are able to prove about similar propositions today. But do I really care about the cutting edge? This cutting edge, much like most cutting edges in mathematics, is made terribly modest by the mathematicians' uncompromising insistence on complete rigor. If one is actually interested in the truth and is satisfied with arguments suggesting that something is true at the 5-sigma or 10-sigma confidence level, in some counting, the cutting edge is elsewhere – it's much further.

So of course that the hunt for strictly rigorous proofs that has defined mathematics after its divorce with physics is a legitimate goal – a constraint worshiped by a large group of professionals, the mathematicians in the modern sense. However, the strict rules of this hunt inevitably imply that in many cases, these professionals place themselves miles beneath the actual cutting edge of knowledge as I understand it.

And that's the memo.

1. cue dozens of papers by unknown mathematicians tediously reducing the gap size little by little down to some few thousands.

Congratulations to Zhang though - this is a genuine new result. A little disappointing that it only uses well-known techniques and nothing fundamentally new - a similar situation to the recent proof that prime testing is in P by Agrawal et al, and perhaps Apery's proof of the irrationality of the zeta function evaluated at 3 (Apery was even older than Zhang)

2. Stephen Paul KingMay 29, 2013, 4:03:00 AM

"Everything that isn't forbidden is mandatory" is not totalitarian! It is Libertarian! That which is forbidden must be at least recursively enumerable, after all. What is free, from constraint for example, is mandatory by Gell-Mann's principle. Ordinary sets are totalitarian as they assume that all is forbidden *except* what is allowed. Jon Barwise had this all nailed down in his work.

3. Stephen Paul KingMay 29, 2013, 6:37:00 AM

Nature does not coerce.

4. Thanks for this nice article :-)

I have just noted, that my brain potentially has a sever bug: always whan I see things like n ln(n) somewhere such as in the TRF proof of the distribution of prime numbers for example, I immediatelly think entropy ... darn :-D

5. AmusedMathematicianMay 29, 2013, 2:27:00 PM

Thanks for that trite middle school level discussion of the mathematics behind prime numbers! Why don't you follow that up by proving Fermat, perhaps by counting points in a box? Or that zeta(3) is transcendental because, you know, most numbers are.

6. Your citation of Tao's (very impressive) "heuristic proof" is amusing, because his is clearly much more complex than yours, but of course his proof gives insight into the main difficulty so that a good mathematician reading it can see what needs to be done to turn it into a real proof. Your heuristic proof works as a proof of "if the limit of (p_n)(ln n)/n exists then that limit is 1", and the difficulty is showing that the limit exists.

I found a proof that "if that limit exists it is 1" that is more elementary, and goes as follows: consider the prime factorization of the binomial coefficient (2n)!/(n!n!) . The primes which contribute to it are the ones in the intervals (n,2n], (n/2,2n/3], (n/3,2n/5], (n/4,2n/7],..., while the primes in the complementary intervals (2n/3,n], (2n/5,n/2], (2n/7,n/3],... do not appear since they occur twice as often in (2n)! as in n! (neglecting primes less than sqrt(2n) which contribute negligibly in the limit). Taking logs, we see that if the limit exists then the fraction of primes captured had better be 1 - (1/2) + (1/3) - (1/4) + (1/5) - ... = ln(2) but this is exactly right because the binomial coefficient is asymptotic to (2^(2n))/sqrt(pi*n) by Stirling's formula so its log is asymptotic to ln(2) * ln((2n)!).

7. Nice.

Erdos used the key fact that no prime p in (2n/3,n] divides the binomial coefficient to deduce Bertrand's Postulate http://www3.nd.edu/~dgalvin1/pdf/bertrand.pdf

btw it's incredibly frustrating to try to derive a proof of bertrand's postulate from scratch - I was really impressed to discover that Erdos worked out his "simple" proof at age 19.

8. Of course, this is is true if you define "easily proved" properly, but if you consider things such as the Ulam spiral (http://en.wikipedia.org/wiki/Ulam_spiral), you need to use a very broad definition of "easily".

9. AmusedMathematicianMay 31, 2013, 3:53:00 AM

Really? The number of triples x,y,z with x^n, y^n, and z^n in [-N..N] is roughly O(N^(3/n)). Hence the expected number of solutions to x^n+y^n=z^n in this range is O(N^(3/n-1)), which is finite if n > 3. Exactly as in your post above, this is a simple heuristic to explain to high school students; it moreover correctly predicts (suitably generalized) that curves of genus more than 1 have only finitely many rational points, which is a theorem of Faltings. The reader can decide whether these trite observations are a suitable substitute for the actual mathematics. But perhaps you are upset because you're proud of your little computation above? That would indeed be amusing.

10. I have never said that the distribution of Fermat-like equations is uniform. I have said that the distribution of primes is uniform except for easily provable patterns.

My statement is right and verifiably right and I used the statement to quantify the density of primes as a function of N; your statement that you pretend to be analogous is just rubbish and everything that you would derive from that would be rubbish, too.

Quite generally, you seem to be just a screwed parody of mine.

11. Provisionally 51,526. They're improving it quickly.

http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes