7 ms·

Can a mathematician explain the significance of this result please?

by lquist 13y ago

ColinWright 13y ago
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.
- cscheid 13y ago
  > 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.
  - ColinWright 13y ago
    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.
    - tomp 13y ago
      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.
      - JacobiX 13y ago
        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.
      - ColinWright 13y ago
        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.
        tomp 13y ago
        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).
        ColinWright 13y ago
        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.
  - boboblong 13y ago
    > Huh? if the proof holds, that's precisely what it does. That's very debatable. Haven't you ever heard the phrase, "I follow, but I don't understand"?
  - SatvikBeri 13y ago
    "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.
- gjm11 13y ago
  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.
  - robertk 13y ago
    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!
- btilly 13y ago
  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. 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.
- igravious 13y ago
  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? :(
  - ColinWright 13y ago
    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 http://www.solipsys.co.uk/new/RandomEratosthenes.html?HN1
dmvaldman 13y ago
The reason why this problem is difficult is because primes have everything to do with multiplication (every number is the product of primes), and summing numbers have everything to do with...well, addition. To give additive properties of numbers in terms of primes is like putting a round peg in a square hole. 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.
- surement 13y ago
  > every number is the product of primes 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?
  - esrauch 13y ago
    Can you explain your question? It seems obvious that you can take something that is not proven as an axiom and try to use it in some practical applications. Maybe to disastrous results if it ends up being wrong, but no worse than what is already a risk with bugs in implementation.
    - surement 13y ago
      > Maybe to disastrous results if it ends up being wrong 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!
      - dmvaldman 13y ago
        Also, Golbach's conjecture has been verified up from 5 to 4000000000000000000 computationally. 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

Can a mathematician explain the significance of this result please?

by lquist 13y ago

Can a mathematician explain the significance of this result please?

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.

cscheid 13y ago
> 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.
- ColinWright 13y ago
  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.
  - tomp 13y ago
    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.
    - JacobiX 13y ago
      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.
    - ColinWright 13y ago
      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.
      - tomp 13y ago
        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).
        ColinWright 13y ago
        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.
- boboblong 13y ago
  > Huh? if the proof holds, that's precisely what it does. That's very debatable. Haven't you ever heard the phrase, "I follow, but I don't understand"?
- SatvikBeri 13y ago
  "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.
gjm11 13y ago
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.
- robertk 13y ago
  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!
btilly 13y ago
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. 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.
igravious 13y ago
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? :(
- ColinWright 13y ago
  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 http://www.solipsys.co.uk/new/RandomEratosthenes.html?HN1

dmvaldman 13y ago

The reason why this problem is difficult is because primes have everything to do with multiplication (every number is the product of primes), and summing numbers have everything to do with...well, addition. To give additive properties of numbers in terms of primes is like putting a round peg in a square hole. 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.

surement 13y ago
> every number is the product of primes 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?
- esrauch 13y ago
  Can you explain your question? It seems obvious that you can take something that is not proven as an axiom and try to use it in some practical applications. Maybe to disastrous results if it ends up being wrong, but no worse than what is already a risk with bugs in implementation.
  - surement 13y ago
    > Maybe to disastrous results if it ends up being wrong 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!
    - dmvaldman 13y ago
      Also, Golbach's conjecture has been verified up from 5 to 4000000000000000000 computationally. 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