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