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.
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)
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.
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.
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.
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.
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).
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.
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.
> 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.
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.
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?
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).
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.
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.