I Am a Strange Loop - Douglas R. Hofstadter [78]
To doubt either half of the Credo would be unthinkable to a mathematician. To doubt the first line would be to imagine that a proved statement could nonetheless be false, which would make a mockery of the notion of “proof ”, while to doubt the second line would be to imagine that within mathematics there could be perfect, exceptionless patterns that go on forever, yet that do so with no rhyme or reason. To mathematicians, this idea of flawless but reasonless structure makes no sense at all. In that regard, mathematicians are all cousins of Albert Einstein, who famously declared, “God does not play dice.” What Einstein meant is that nothing in nature happens without a cause, and for mathematicians, that there is always one unifying, underlying cause is an unshakable article of faith.
No Such Thing as an Infinite Coincidence
We now return to Class A versus Class B primes, because we had not quite reached our revelation, had not yet experienced that mystical frisson I spoke of. To refresh your memory, we had noticed that each line was characterized by differences of the form 4n — that is, 4, 8, 12, and so forth. We didn’t prove this fact, but we observed it often enough that we conjectured it.
The lower line in our display starts out with 3, so our conjecture would imply that all the other numbers in that line are gotten by adding various multiples of 4 to 3, and consequently, that every number in that line is of the form 4n + 3. Likewise (if we ignore the initial misfit of 2), the first number in the upper line is 5, so if our conjecture is true, then every subsequent number in that line is of the form 4n + 1.
Well, well — our conjecture has suggested a remarkably simple pattern to us: Primes of the form 4n + 1 can be represented as sums of two squares, while primes of the form 4n + 3 cannot. If this guess is correct, it establishes a beautiful, spectacular link between primes and squares (two classes of numbers that a priori would seem to have nothing to do with each other), one that catches us completely off guard. This is a glimpse of pure magic — the kind of magic that mathematicians live for.
And yet for a mathematician, this flash of joy is only the beginning of the story. It is like a murder mystery: we have found out someone is dead, but whodunnit? There always has to be an explanation. It may not be easy to find or easy to understand, but it has to exist.
Here, we know (or at least we strongly suspect) that there is a beautiful infinite pattern, but for what reason? The bedrock assumption is that there is a reason here — that our pattern, far from being an “infinite coincidence”, comes from one single compelling, underlying reason; that behind all these infinitely many “independent” facts lies just one phenomenon.
As it happens, there is actually much more to the pattern we have glimpsed. Not only are primes of the form 4n + 3 never the sum of two squares (proving this is easy), but also it turns out that every prime number of the form 4n + 1 has one and only one way of being the sum of two squares. Take 101, for example. Not only does 101 equal 100 + 1, but there is no other sum of two squares that yields 101. Finally, it turns out that in the limit, as one goes further and further out, the ratio of the number of Class A primes to the number of Class B primes grows ever closer to 1. This means that the delicate balance that we observed in the primes below 100 and conjectured would continue ad infinitum is rigorously provable.
Although I will not go further into this particular case study, I will state that many textbooks of number theory prove this theorem (it is far from trivial), thus supplementing a pattern with a proof. As I said earlier, X is true because X has a proof, and conversely, X is true and so X has a proof.
The Long Search for