Can a mathematician explain the significance of this result please?
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
[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 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.
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).
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?
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".
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.
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? :(
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
The reason why this problem is important, is that in the grand scheme of things, it'a more about the math and less about the applications. People have already assumed it to be true, and still not applied it to anything practical like cryptography, as far as I know. Please correct if not.
Except prime numbers.
> People have already assumed it to be true, and still not applied it to anything practical like cryptography
How can you use something that you didn't prove?
For example, we have not proven that are current construction of mathematics contains no contradictions (indeed, we have proved that such a proof is impossible), however, we continue to act as if it does.
We have also not proved that factoring numbers is hard, or that NP/=P, but we still act as if these are true.
This is what I meant. Bugs are never introduced intentionally in this manner. Though I suppose we can say that most encryption is used based on an unproven assumption, so I see your and dmvaldman's point!
But in general, it's common for mathematicians to assume a conjecture is true and go on from there, because if they arrive at a contradiction, then they can conclude the conjecture false (or that another interesting fact may be logically equivalent to the conjecture).
Pure mathematics consists entirely of such assertions as that, if such and such a proposition is true of anything, then such and such another proposition is true of that thing. It is essential not to discuss whether the first proposition is really true…. Thus mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. - Bertrand Russell
All is number!
/s