7 ms·

> 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 wi

by 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.
        gchpaco 13y ago
        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.
      - anatoly 13y ago
        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.
  - Fargren 13y ago
    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.
    - lmm 13y ago
      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.
      - ColinWright 13y ago
        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)
        scott_s 13y ago
        Colin, on days like this, I'm very glad you have not given up on HN entirely.
      - Fargren 13y ago
        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.
  - JabavuAdams 13y ago
    > 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.
  - andrewflnr 13y ago
    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.
    - jonsterling 13y ago
      Proof by contradiction is not constructive, since it uses the Law of the Excluded Middle.
      - prutschman 13y ago
        There are some subtleties there. Andrej Bauer covers them well: http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ http://math.andrej.com/2010/03/29/proof-of-negation-and-proo...
  - arjie 13y ago
    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?
    - Heliosmaster 13y ago
      You mean this? http://en.wikipedia.org/wiki/Proof_by_exhaustion http://en.wikipedia.org/wiki/Proof_by_exhaustion
      - Someone 13y ago
        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).
  - btilly 13y ago
    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 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 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.
  - ColinWright 13y ago
    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.
  - auvrw 13y ago
    > 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?
- smegel 13y ago
  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.
  - ColinWright 13y ago
    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".
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.

by cscheid 13y ago

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.
      - gchpaco 13y ago
        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.
    - anatoly 13y ago
      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.
- Fargren 13y ago
  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.
  - lmm 13y ago
    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.
    - ColinWright 13y ago
      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)
      - scott_s 13y ago
        Colin, on days like this, I'm very glad you have not given up on HN entirely.
    - Fargren 13y ago
      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.
- JabavuAdams 13y ago
  > 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.
- andrewflnr 13y ago
  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.
  - jonsterling 13y ago
    Proof by contradiction is not constructive, since it uses the Law of the Excluded Middle.
    - prutschman 13y ago
      There are some subtleties there. Andrej Bauer covers them well: http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ http://math.andrej.com/2010/03/29/proof-of-negation-and-proo...
- arjie 13y ago
  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?
  - Heliosmaster 13y ago
    You mean this? http://en.wikipedia.org/wiki/Proof_by_exhaustion http://en.wikipedia.org/wiki/Proof_by_exhaustion
    - Someone 13y ago
      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).
- btilly 13y ago
  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 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 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.
- ColinWright 13y ago
  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.
- auvrw 13y ago
  > 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?
smegel 13y ago
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.
- ColinWright 13y ago
  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".

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.