Hacker News Reader

Comment by ColinWright | Hacker News Reader

Briefly ...

To a large extent the primes appear to be distributed in a manner indistinguishable from randomly. There seems underneath to be no reason to believe that there are results like this. If they were random then there might be numbers that cannot be expressed as the sum of 3 primes, but somehow every number ends up so expressible.

Why should that be true? Indeed, is it true? This result says it is true, but we really don't see why.

Understanding how the primes are distributed may have far-reaching implications for cryptography, and possibly even for solving things like the TSP. We just don't know, just as we initially never suspected that public-key cryptosystems were possible, and would involved primes.

Random matrices is another area where a lot of research was done just because people found it an interesting problem, and now there appear to be deep connections with practical physics that may allow us to further bend the world to our will.

Sometimes it's the chase that's exciting, never knowing what may turn out to have world-changing implications.

View on HN

If I'm understanding correctly, you suggest that this is an example of the prime numbers not behaving randomly. I disagree.

Here's (more or less) the simplest possible random model of the primes. (It's called the Cramer model.) Take P to be a random subset of the natural numbers that includes each n>1 independently with probability 1/log(n). Then P is kinda like the prime numbers, though it lacks some structure it should have (e.g., it doesn't have the property that almost all elements are odd).

If you do this, then the expected number of ways to write a large n as the sum of two elements of P is on the order of n/log(n)^2, which is far enough from 0 that I bet (though I haven't checked) that Pr(every number >= 4 is the sum of two elements of P) is positive, and in fact probably quite big. This is kinda analogous to the Goldbach conjecture; note that it isn't only about even n, since in this model there can be lots of even "prime numbers".

I did a quick computer experiment, and it looks as if the probability is about 20%. In other words, if the primes were chosen at random according to the Cramer model, then about 1/5 of the time the appropriately mangled Goldbach conjecture would be true. (And the "odd Goldbach conjecture", which is what Helfgott has just proved, would be true substantially more often than that.)

Now, of course the Cramer model is way too simple. In particular, it doesn't know that almost all prime numbers are odd. So let's make it just a little smarter by declaring that 2 is always in P, the other elements of P are always odd, and that any odd n>1 is in P with probability 2/log(n). And now we should switch back to the original form of the Goldbach conjecture, looking only at even n. Well, according to my computer experiment the probability that the Goldbach conjecture holds if we use P instead of the primes is about 96%!

[EDITED to add: and if we force P to get 2 and 3 "right" instead of just 2, the probability goes up to about 99.5%. I fixed a few other things in this edit too.]

In other words: if the primes are basically random, then we should expect the Goldbach conjecture to be true.

Of course, your computer simulation completely disregards the possibility of some very large (but rare) numbers (possibly of density zero) not being expressible as such a sum. You merely verified it for low finite integers. I am very unconvinced your percentages are accurate. In fact, they may be completely wrong, as this issue is the entire crux of the Goldbach problem!

My simulation disregards it, but I don't. In this sort of random model, the probability of any (specific) large number not being the sum of two "primes" is extremely small (and decreasing rapidly as the number increases), which means that the total probability of any (at all) large number not being the sum of two "primes" is also extremely small.

In other words: in this model, with probability very close to 1 all large enough even numbers are sums of two "primes".

Let's put a little flesh on those bones. I'll stick with the unmodified Cramer model for simplicity; the tweaked versions are fiddlier but not fundamentally different. The probability that n=a+b is a "good" decomposition is 1/log(a)log(b); this is smallest, for fixed n, when a=b; so the probability that any given decomposition "works" is at least 1/log(n/2)^2. There are n/2-2 of these, and they're all independent, so the probability that none of them works is at most (1-1/log(n/2)^2)^(n/2-2), which is approximately exp(-n/(2 log(n/2)^2)). So the expected number of n beyond, say, 1000 for which that happens is the sum of this for n from 1000 up. Unfortunately neither the sum nor the obvious approximation as an integral has a closed form, but we can compute it numerically; it's about 0.000279. That's the expected number of failures above n=1000, and of course that's an upper bound on the probability of at least one such failure.

So, the probability (in this model) of any Goldbach failures above n=1000 is at most about 0.0003, and therefore the probability of any Goldbach failures at all is at most that much bigger than the probability of any Goldbach failures up to n=1000.

Note that although this is a statement with probabilities in, the probabilities aren't fractions of the integers for which Goldbach fails.

The situation is analogous to the following. Suppose you flip a coin 10 times, then 20 times, then 40 times, then 80 times, etc., and for each group of flips you "win" if you get at least one head. Then, with probability about 99.9%, you always win: the probability of failure in successive groups drops so fast that the contribution to the overall failure probability from all groups other than the first is tiny.

Similarly, with the Cramer-model analogue of Goldbach's conjecture, the probability that the conjecture fails "at n" decreases so rapidly with n that almost all the probability of there being any failure at all comes from the possibility of failures for small n.

And that's why you can get good estimates of the failure probability from computer simulations that look only at finitely many n.

Taking the Cramer model, the probability that a number N is not expressible as the sum of two primes is

product(x=1...N-1) (1 - 1/log(x)log(N-x))

< product(x=1...N-1) (1 - 1/log(N))

= (1 - 1/log(N)) ^ (N-1)

Which is eventually below

(1 - 1/log(N)) ^ log(N) ^ sqrt(N)

Which converges to

(1/e) ^ sqrt(N)

And so is eventually below

(1/2) ^ sqrt(N)

The -log of the probability that a number is expressible as the sum of two Cramer numbers is thus at most

-log(1 - (1/2) ^ sqrt(N))

Which is eventually below

2 * (1/2) ^ sqrt(N)

You can show that this is a convergent series, and if the -log of the probability converges then the probability that ALL integers (minus perhaps the first few) have this property must converge, to something above zero. Thus, there is a nonzero chance that a set of Cramer numbers will have the property that all a finite number of positive integers will be expressible as the sum of two of them. Thus, prime numbers do not need any magical properties for some version of the Goldbach conjecture to be correct on them - the magical properties are only necessary to actually prove it.

This is really interesting. Have any theorems been proved or at least conjectured based on a probabilistic model for primes? Do you have any suggested resources for learning more about the Cramer model?

You've argued that if the the primes were basically random, we would expect Goldbach to hold, but as I understand it, we would expect to not be able to prove that it holds.

The fact that we can prove the ternary Goldbach conjecture is (necessarily) at least as surprising as it being true: in this case it seems to be significantly more surprising. Is the significance of this result in fact the techniques used, rather than the result itself?

> We don't really see why.

Huh? if the proof holds, that's precisely what it does. The proof might be delicate enough to not apply in other settings, so our wider intuition about prime numbers might not be enriched (at least not immediately). Still, a correct proof is very much a formal explanation?

And, what's the connection between TSP and prime numbers? I thought the current consensus in complexity is that the factoring is likely not NP-hard, but not in P either.

No, the proof will show us that it's true, but that's not the same as understanding why it's true. There's a difference that most mathematicians grok, but can be hard to see from the outside.

And I don't know if there's a connection between primes and TSP, but people never suspected a connection between modular forms and elliptic curves, either. And this result may have nothing to do with factoring, but the techniques may give better approximation algorithms for things that are NP Hard.

That's the point, we really don't yet know what this result, but more particularly, what these proof techniques will yield.

I'm a mathematician, and I don't grok the difference. Unless you're using the Axiom of Choice, which enables non-constructive proofs, a proof should tell you exactly why something happens, albeit sometimes it's a bit hard to understand, since it's too abstract.

Unless, of course, you're referring to the underlying philosophical reasons why it's true, to which my usual answer would be: math is a game with certain simple rules that play well together and have long-reaching consequences. It's a game we choose to play.

Some popular methods of proofs are non-constructive. For example you can take a look at the probabilistic method used by Paul Erdős and others.

Have you never followed a proof all the way through, got to the end, and said to yourself - "OK, it's true, and I believe it, and I understand the proof, but I really don't get why it works."

If not, then you think about math differently from how I, my supervisor (from 30 years ago) and most of my PhD siblings do.

That's OK, of course, it's just interesting.

Sure, that happens :) but it doesn't mean that the proof is non-constructive, it just means that it's too abstract for me to understand. Sometimes, however, rereading it does wonders (e.g. I can't really visualize the Inverse Function Theorem (for functions R^2 -> R^2), but if I try to squeeze it into 3D space, I can almost visualize it, and the proof becomes logical).

I'm not speaking (only) of non-constructive proofs, I'm just saying that sometimes a proof will leave you with no real sense of why a result is true (or "inevitable"). That sense sometimes comes much later, after further results are known.

There's a notorious proof of Heron's formula (computing the area of a triangle from the lengths of the three sides without trig) that proceeds by proving three things that seem to have nothing to with one another or with the goal, and then through a flourish of algebra the result falls out. There are much more straightforward ways to prove the theorem that do not abuse the reader, and modern mathematics frowns on such indirectness unless it is totally necessary. Unfortunately it was the style to write gimmicky proofs like that for a while in IIRC the 18th and 19th centuries, and sometimes they persist.

There is no finite field of size 6. It's very easy to prove this constructively just by showing exhaustively that any attempt to define multiplication on the unique abelian group of size 6 will fail some of the axioms.

However, such a proof will not be a good answer to the question _why_ this is true. A good answer why it's true that there's no finite field of size 6 is that a finite field is a vector space on its prime subfield and so must be of size p^n, where n is the dimension of the vector space and p, a prime, the size of the prime subfield.

My Logics professor said once to em that even though there are many proofs for a given theorem, there's generally only one that feels like the "natural" explanation of why a thing is how it is, the one that really explains why. I think many mathematicians believe this is so, and it's good to reach these proofs and not just any proof when we are trying to understand something.

For example, let's look at Euclides proof of the pythagorean theorem. It's true that it show's that the theorem holds, and therefore it shows why it holds. But it just feels awfully convoluted and round-away. It's talking about triangles, but it's going through seemingly unrelated constructions to do so. The proof by similar triangles is, to me at least, much more intuitive, and after reading it I feel I understand and not just know why the theorem is true.

The four-colour theorem is a good example of a simple result which doesn't have a "natural" explanation - the only known proof is a computerized check of hundreds of cases. I remember Imre Leader saying some people think it's just an "accident of nature", that doesn't "mean" anything (insofar as any mathematics has meaning).

Oddly enough that doesn't bother me; in fact, it seems natural that some parts of mathematics are just "like that" with no underlying reason. It makes the world of mathematics seem all the richer if not all things are simple and logical consequences of other things.

Exactly so. For the record, Imre is one of my PhD siblings, and it's perfectly reasonable that we came to this point of view as a by-product of working with our supervisor (and "grandparents", Erdős and Adams)

Colin, on days like this, I'm very glad you have not given up on HN entirely.

For problems like that, I can't help but wonder if some day we'll discover that we are just not searching for the solution in the proper "language". Maybe some day someone will find a problem isomorphic the the for-color problem in a different field, and that problem will have a simple and natural explanation. Probably in a field we don't know today.

To me, that feels more like a limit on human cognition than a fundamental quality of the proof or the program. After all, you can summarize--or, perhaps compress--the proof into a program which checks the cases. It's simply a level removed from how mathematicians normally work.

On the other hand, if a proof could not be reduced at all--and, given my very limited understanding of information theory, this is possible--then I would certainly agree that it's inherently more complex.

Put another way, I think that using a computer to check cases like this is morally similar to using induction. It still exposes and exploits a certain simplicity in the domain.

There was no induction; the proof was essentially: a) all planar graphs can be reduced to these several hundred cases (this part is ordinary mathematics) b) observe that it's possible to four-colour each of these several hundred cases (and a computer program was used to verify it). To my mind the proof is as complex as that set of cases; the fact that we can write a relatively simple program to check them all doesn't really reduce the complexity or tell us anything about why they're all 4-colourable, in the same way that using a computer to check the riemann hypothesis up to some limit tells us nothing about why it holds.

I know it was not induction. My point is that a computer program to consider all the cases is just another mathematical tool morally similar to induction.

The program does tell us something, namely that the problem can be reduced to a bunch of similar cases all of which are colorable. The difference is that the insight is perhaps a level removed from a normal proof.

Essentially, I think that it's the program and not its output that plays the philosophical role of the proof in this case.

Of course, my perception is significantly colored by the fact that I'm mainly interested in programming languages rather than traditional math :P.

i think that's a good notion as long as your prof. didn't demand that you feel the same way s/he did about everything.

also, proofs of older facts using newer techniques can illuminate a new theory rather than the fact at hand. for instance, the topological proof that there are infinitely many primes is nice because it makes you think about what separability means.

> Unless, of course, you're referring to the underlying philosophical reasons why it's true, to which my usual answer would be: math is a game with certain simple rules that play well together and have long-reaching consequences. It's a game we choose to play.

Isn't it interesting that this game we choose to play is so effective at modelling the world around us? I suppose you could argue that we wouldn't have put so much effort into this formulation of the game if it wasn't.

Is a proof by contradiction considered constructive? I just know in my linear algebra class, we used proof by contradiction constantly, but the axiom of choice was only mentioned as necessary once.

Proof by contradiction is not constructive, since it uses the Law of the Excluded Middle.

There are some subtleties there. Andrej Bauer covers them well: http://math.andrej.com/2010/03/29/proof-of-negation-and-proo...

Well, what if the proof is just an exhaustive search of the space? Say 'all even numbers between 4 and 2^10' can be written as the sum of two primes. Say the proof is just listing out of these numbers and the primes that compose them. The proof tells you it is true. But it doesn't tell you anything about a natural underlying truth that causes this. Do you not find something wanting in such a proof?

You mean this? http://en.wikipedia.org/wiki/Proof_by_exhaustion

Many proofs are in some sense proofs by exhaustion. For example, to prove that no square of an integer ends in a digit '3', the typical proof I) makes the search space smaller by working modulo 10, and II) exhausts all possibilities.

In the end, it all boils down to aesthetics: going from infinitely many cases to a small finite number, as given above, is acceptable because the number is low, and because mathematicians are convinced the remainder is about as simple as it gets.

Going to about 2000, as in the four color theorem, is not, because 2000 is a lot, and, I think more so, because mathematicians aren't convinced that it is necessary to handle each of these cases individually.

And of course, mathematicians would agree that using 5 instead of 10 in step I above leads to a nicer proof. It requires less tedious work in step II and leads to a stronger result (squares never end in 3 or 8).

Here is a challenge for you.

It is easy to prove that the 2-player version of the game of hex on an nxn board is a win for the first player. The proof involves a finite game, so no axiom of choice involved.

I invite you to find and master the proof, then when you think you understand it demonstrate your knowledge by playing me a game of hex. We can play on wargear, my user account there is http://www.wargear.net/players/info/btilly and you can challenge me to a 19x19 pure or 2nd player choose on the board http://www.wargear.net/boards/view/Hex.

If I win, then I submit to you that your comprehension of the proof did not truly extend to understanding why it was true.

Coming back to this, consider the following.

[Warning: read like math ...]

Let p be a prime of the form 4k+1. It's easy to show that there exists u such that u^2=-1 (mod p). Indeed, simply using (2k)! works.

Consider all number of the form a+b.u (mod p) where a and b are in the range 0 <= a,b < sqrt(p). There are more than p of these, so by the pigeon-hole principle we have a0, b0, a1, b1 such that a0+b0.u = a1+b1.u (mod p).

Rearrange to give a0-a1 = (b1-b0).u (mod p) and square both sides. Remembering that u^2=-1 (mod p) we get

(a0-a1)^2 + (b1-b0)^2 = 0 (mod p)

A little checking shows that (a0-a1)^2 + (b1-b0)^2 < 2p, so that means

(a0-a1)^2 + (b1-b0)^2 = p

Thus we have shown that p is the sum of two squares.

I can reproduce this proof at will. I see how the proof works, I am convinced it's correct and valid. I still don't really understand why every prime of the form 4k+1 is the sum of two squares, especially since every argument someone tries to give to show somehow it's inevitable also works for 4k+3, where it's not true.

> It's a game we choose to play.

as i recall, paul cohen would disagree. i don't know what to say as i am not a mathematician, but doesn't saying such a thing seem awfully depressing? like, doesn't it kinda trivialize what you do to write it off as a game?

What? A brute force computer simulation can show you that some finite conjecture holds...but an axiomatic proof surely is the only real concept of "why" we have. Because if it is not true, then 1+1 != 2, or some such result.

Not for me, and not for many of the mathematicians I have worked with. Sometimes with a theorem there is a sense of knowing why something is true, and in those cases the proof emerges fairly naturally from that. Sometimes, on the other hand, you have a proof, you know it's true[0], and yet there is no enlightenment, no sense of what's happening, no real understanding of why it's true.

Some mathematicians don't have this point of view, but I always felt that sometimes, even when I really knew the proof, I still hadn't grokked a sense of the why. It just all felt like unmotivated symbol manipulation.

[0] For some value of "true".

"Why it works" is a very subjective notion. A very good example of the difference between proving something is true and showing why it's true comes in the undergraduate Real Analysis textbooks by Walter Rudin and Charles Pugh.

If you look at reviews for Rudin's books, the word "magic" is used quite frequently. Rudin will cover the minimum amount of theory necessary and prove each theorem in a highly specific way. He tends to achieve the minimum number of words necessary for a proof.

In contrast, Pugh focuses on building up the surrounding constructs and techniques to the point where you can apply the same tactics to a wide variety of problems. To me, this gives more of a sense of "why" each theorem is true.

I see this as backwards. Based on the prime number distribution we can actually predict the probability that a given number will be a counter example. And the sum over all positive integers of those probabilities is a miniscule number, so we're quite certain that the statement is true. We just don't know why.

The primes are distributed to a first approximation randomly with independent probabilities 1/log(n) for n being prime. You can refine this with obvious divisibility criteria. (For example odd numbers appear randomly prime with probability 2/log(n). And so on.)

If you first refine these statements for all the small primes that you care to, then make any prediction that you like, that prediction tends to hold up very well.

For example consider the even form of Goldbach's conjecture, which says that every even greater than 2 is the sum of 2 primes. Well, 4 is a special case, so it really is that every even greater than 4 is the sum of 2 odd primes. Does this seem unlikely?

If n is even, it is the sum of 2 smaller odd numbers in n/4 + O(1) ways. On average those have independent probabilities around 4/log(n/2)^2 of being the sum of 2 primes. Therefore it tends to be the sum of 2 primes in O(4n/log(n)2) ways, with the exact distribution being close to a Poisson distribution around the projected number, which for large n is well approximated by a normal distribution. (There are various minor quibbles and corrections that you can easily use to refine this basic prediction.) From this the probability of being a sum of two odd primes in 0 ways can be estimated, and turns out to go to 0 fast enough that we expect only a finite number of counter-examples. (2 and 4 are indeed counterexamples to the stronger statement, but we know of no others.)

This basic projection can be verified for small n by computer analysis, and indeed works out to be remarkably accurate. Therefore we have great confidence that Goldbach's conjecture is likely to be true, but absolutely no idea why.

The hope, some day, is to be able to close this gap. To not just make assertions based on known statistical facts about the distribution of primes, but to be able to prove them.

The best known example of a statement which should be true that we have not yet proven is the Riemann Hypothesis. It should be noted that Louis de Branges does claim to have proven it, nobody has investigated his claims depth, and he was right about the Bieberbach conjecture.

My favorite example of a statement which looks reasonable on the numerical evidence, cannot be supported by this kind of argument, which later proved false is Mertens conjecture.

Colin,

At the risk of sounding very stupid I've never understood what was actually meant by statements of the type "the primes appear to be distributed in a manner indistinguishable from randomly". I say this because I imagine that the definition of what makes a prime a prime determines whether any particular number is prime or not. So what don't I get when people make statements like this? :(

There's a classic experiment where you get people firstly to generate a length 50 "random" string of heads and tails by making it up. Then they genuinely flip a coin 50 times and write down the result.

You can almost always tell the difference. there are statistical tests that you can apply that almost invariably identify which is which.

So there are statistical tests that let us ask whether a particular collection is "random" (whatever that means) When we have the right model (the Cramer model is one) we can produce sequences of numbers which are genuinely created at random, but which the statistical tests cannot decide which sequences are the random ones, and which one is the primes.

You can read a little here: http://www.solipsys.co.uk/new/RandomEratosthenes.html?HN1

Reply on news.ycombinator.com