I Am a Strange Loop

by Douglas R. Hofstadter

  If it existed, P would be a truly important and interesting number, but if you look at a long list of consecutive primes (the list above of primes up to 100 gives the flavor), you will see that although their rhythm is a bit “bumpy”, with odd gaps here and there, the interprime gaps are always quite small compared to the size of the primes involved. Given this very clear trend, if the primes were to run out all of a sudden, it would almost feel like falling off the edge of the Earth without any warning. It would be a huge shock. Still, how do we know this won’t happen? Or do we know it? Finding, with the help of a computer, that new primes keep on showing up way out into the billions and the trillions is great, but it won’t guarantee in rock-solid fashion that they won’t just stop all of a sudden somewhere out further. We have to rely on reasoning to get us there, because although finite amounts of evidence can be strongly suggestive, they just don’t cut the mustard, because infinity is very different from any finite number.

  Sailing the Ocean of Primes and Falling off the Edge

  You probably have seen Euclid’s proof of the infinitude of the primes somewhere, but if not, you have missed out on one of the most crucial pillars of human knowledge that ever have been found. It would be a gap in your experience of life as sad as never having tasted chocolate or never having heard a piece of music. I can’t tolerate such crucial gaps in my readers’ knowledge, so here goes nothing!

  Let’s suppose that P, the Great Last Prime in the Sky, does exist, and see what that supposition leads to. For P to exist means that there is a Finite, Closed Club of All Primes, of which P itself is the glorious, crowning, final member. Well then, let’s boldly multiply all the primes in the Closed Club together to make a delightfully huge number called Q. This number Q is thus divisible by 2 and also by 3, 5, 7, 11, and so forth. By its definition, Q is divisible by every prime in the Club, which means by every prime in the universe! And now, for a joyous last touch, as in birthday parties, let’s add one candle to grow on, to make Q + 1. So here’s a colossal number that, we are assured, is not prime, since P (which is obviously dwarfed by Q) is the Great Last Prime, the biggest prime of all. All numbers beyond P are, by our initial supposition, composite. Therefore Q + 1, being way beyond P and hence composite, has to have some prime divisor. (Remember this, please.)

  What could that unknown prime divisor be? It can’t be 2, because 2 divides Q itself, which is just one step below Q + 1, and two even numbers are never located at a distance of 1 from each other. It also can’t be 3, because 3 likewise divides Q itself, and numbers divisible by 3 are never next-door neighbors! In fact, whatever prime p that we select from the Club, we find that p can’t divide Q + 1, because p divides its lower neighbor Q (and multiples of p are never next-door neighbors — they come along only once every p numbers). And so reasoning has shown us that none of the members of the Finite, Closed Club of Primes divides Q + 1.

  But above, I observed (and I asked you to remember) that Q + 1, being composite, has to have a prime divisor. Sting! We have been caught in a trap, painted ourselves into a corner. We have concocted a crazy number — a number that on the one hand must be composite (i.e., has some smaller prime divisor) and yet on the other hand has no smaller prime divisor. This contradiction came out of our assumption that there was a Finite, Closed Club of Primes, gloriously crowned by P, and so we have no choice but to go back and erase that whole amusing, suspect vision.

  There cannot be a “Great Last Prime in the Sky”; there cannot be a “Finite, Closed Club of All Primes”. These are fictions. The truth, as we have just demonstrated, is that the list of primes goes on without end. We will never, ever “fall off the Earth”, no matter how far out we go. Of that we now are assured by flawless reasoning, in a way that no finite amount of computational sailing among seas of numbers could ever have assured us.

  If, perchance, coming to understand why there is no last prime (as opposed to merely knowing that it is the case) was a new experience to you, I hope you savored it as much as a piece of chocolate or of music. And just like such experiences, following this proof is a source of pleasure that one can come back to and dip into many times, finding it refreshing each new time. Moreover, this proof is a rich source of other proofs — Variations on a Theme by Euclid (though we will not explore them here).

  The Mathematician’s Credo

  We have just seen up close a lovely example of what I call the “Mathematician’s Credo”, which I will summarize as follows:

  X is true because there is a proof of X;

  X is true and so there is a proof of X.

  Notice that this is a two-way street. The first half of the Credo asserts that proofs are guarantors of truth, and the second half asserts that where there is a regularity, there is a reason. Of course we ourselves may not uncover the hidden reason, but we firmly and unquestioningly believe that it exists and in principle could someday be found by someone.

  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 t
o 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 Proofs, and for their Nature

  I mentioned above that the question “Which numbers are sums of two primes?”, posed almost 300 years ago, has never been fully solved. Mathematicians are dogged searchers, however, and their search for a proof may go on for centuries, even millennia. They are not discouraged by eons of failure to find a proof of a mathematical pattern that, from numerical trends, seems likely to go on and on forever. Indeed, extensive empirical confirmation of a mathematical conjecture, which would satisfy most people, only makes mathematicians more ardent and more frustrated. They want a proof as good as Euclid’s, not just lots of spot checks! And they are driven by their belief that a proof has to exist — in other words, that if no proof existed, then the pattern in question would have to be false.

  This, then, constitutes the flip side of the Mathematician’s Credo:

  X is false because there is no proof of X;

  X is false and so there is no proof of X.

  In a word, just as provability and truth are the same thing for a mathematician, so are nonprovability and falsity. They are synonymous.

  During the centuries following the Renaissance, mathematics branched out into many subdisciplines, and proofs of many sorts were found in all the different branches. Once in a while, however, results that were clearly absurd seemed to have been rigorously proven, yet no one could pinpoint where things had gone awry. As stranger and stranger results turned up, the uncertainty about the nature of proofs became increasingly disquieting, until finally, in the middle of the nineteenth century, a powerful movement arose whose goal was to specify just what reasoning really was, and to bond it forever with mathematics, fusing the two into one.

  Many philosophers and mathematicians contributed to this noble goal, and around the turn of the twentieth century it appeared that the goal was coming into sight. Mathematical reasoning seemed to have been precisely characterized as the repeated use of certain basic rules of logic, dubbed rules of inference, such as modus ponens: If you have proven a result X and you have also proven X ⇒ Y (where the arrow represents the concept of implication, so that the line means “If X is true, then Y is also true”), then you can toss Y into the bin of proven results. There were a few other fundamental rules of inference, but it was agreed that not very many were needed. About a decade into the twentieth century, Bertrand Russell and Alfred North Whitehead codified these rules in a uniform if rather prickly notation (see facing page), thus apparently allowing all the different branches of mathematics to be folded in with logic, making a seamless, perfect unity.

  Thanks to Russell and Whitehead’s grand work, Principia Mathematica, people no longer needed to fear falling into hidden crevasses of false reasoning. Theorems were now understood as simply being the bottom lines of sequences of symbol-manipulations whose top lines were either axioms or earlier theorems. Mathematical truth was all coming together so elegantly. And as this Holy Grail was emerging into clear view, a young boy was growing up in the town of Brünn, Austro-Hungary.

  CHAPTER 10

  Gödel’s Quintessential Strange Loop

  Gödel Encounters Fibonacci

  BY HIS early twenties, the boy from Brünn was already a superb mathematician and, like all mathematicians, he knew whole numbers come in limitless varieties. Aside from squares, cubes, primes, powers of ten, sums of two squares, and all the other usual suspects, he was familiar with many other types of integers. Most crucially for his future, young Kurt knew, thanks to Leonardo di Pisa (more often known as “Fibonacci”), that one could define classes of integers recursively.

  In the 1300’s, Fibonacci had concocted and explored what are now known as the “Fibonacci numbers”:

  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, . . .

  In this rapidly growing infinite sequence, whose members I will henceforth refer to as the F numbers, each new element is created by summing the two previous ones (except for the first pair, 1 and 2, which we simply declare by fiat to be F numbers).

  This almost-but-not-quite-circular fashion of defining a sequence of numbers in terms of itself is called a “recursive definition”. This means there is some kind of precise calculational rule for making new elements out of previous ones. The rule might involve adding, multiplying, dividing, whatever — as long as it’s well-defined. The opening gambit of a recursive sequence (in this case, the numbers 1 and 2) can be thought of as a packet of seeds from which a gigantic plant — all of its branches and leaves, infinite in number — grows in a predetermined manner, based on the fixed rule.

  The Caspian Gemstones: An Allegory

  Leonardo di Pisa’s sequence is brimming with amazing patterns, but unfortunately going into that would throw us far off course. Still, I cannot resist mentioning that 144 jumps out in this list of the first few F numbers because it is a salient perfect square. Aside from 8, which is a cube, and 1, which is a rather degenerate case, no other perfect square, cube, or any other exact power appears in the first few hundred terms of the F sequence.

  Several decades ago, people started wondering if the presence of 8 and 144 in the F sequence was due to a reason, or if it was just a “random accident”. Therefore, as computational tools started becoming more and more powerful, they undertook searches. Curiously enough, even with the advent of supercomputers, allowing millions and even billions of F numbers to be churned out, no one ever came across any other perfect powers in Fibonacci’s sequence. The chance of a power turning up very soon in the F sequence was looking slim, but why would a perfect mutual avoidance occur? What do nth powers for arbitrary n have to do with adding up pairs of numbers in Fibonacci’s peculiar recursive fashion? Couldn’t 8 and 144 just be little random glitches? Why couldn’t other little glitches take place?

  To cast allegorical light on this, imagine someone chanced one day to fish up a giant diamond, a magnificent ruby, and a tiny pearl at the bottom of the great green Caspian Sea in central Asia, and other seekers of fortune, spurred on by these stunning finds, then started madly dredging the bottom of the world’s largest lake to seek more diamonds, rubies, pearls, emeralds, topazes, etc., but none was found, no matter how much dredging was done. One would naturally wonder if more gems might be hidden down there, but how could one ever know? (Caveat: my allegory is slightly flawed, because we can imagine, at least in principle, a richly financed scientific team someday dredging the lake’s bottom completely, since, though huge, it is finite. For my analogy to be “perfect”, we would have to conceive of the Caspian Sea as infinite. Just stretch your imagination a bit, reader!)

  Now the twist. Suppose some mathematically-minded geologist set out to prove that the two exquisite Caspian gems, plus the tiny round pearl, were sui generis — in other words, that there was a precise reason that no other gemstone or pearl of any type or size would ever again, or could ever again, be found in the Caspian Sea. Does seeking such a proof make any sense? How could there be a watertight scientific reason absolutely forbidding any gems — except for one pearl, one ruby, and one diamond — from ever being found on the floor of the Caspian Sea? It sounds absurd.

  This is typical of how we think about the physical world — we think of it as being filled with contingent events, facts that could be otherwise, situations that have no fundamental reason for their being as they are. But let me remind you that mathematicians see their pristine, abstract world as the antithesis to the random, accident-filled physical world we all inhabit. Things that happen in the mathematical world strike mathemati
cians as happening, without any exceptions, for statable, understandable reasons.

  This — the Mathematician’s Credo — is the mindset that you have to adopt and embrace if you wish to understand how mathematicians think. And in this particular case, the mystery of the lack of Fibonacci powers, although just a tiny one in most mathematicians’ eyes, was a particularly baffling one, because it seemed to offer no natural route of access. The two phenomena involved — integer powers with arbitrarily large exponents, on the one hand, and Fibonacci numbers on the other — simply seemed (like gemstones and the Caspian Sea) to be too conceptually remote from each other to have any deep, systematic, inevitable interrelationship.

  And then along came a vast team of mathematicians who had set their collective bead on the “big game” of Fermat’s Last Theorem (the notorious claim, originally made by Pierre de Fermat in the middle of the seventeenth century, that no positive integers a, b, c exist such that an + bn equals c n, with the exponent n being an integer greater than 2). This great international relay team, whose final victorious lap was magnificently sprinted by Andrew Wiles (his sprint took him about eight years), was at last able to prove Fermat’s centuries-old claim by using amazing techniques that combined ideas from all over the vast map of contemporary mathematics.

  In the wake of this team’s revolutionary work, new paths were opened up that seemed to leave cracks in many famous old doors, including the tightly-closed door of the small but alluring Fibonacci power mystery. And indeed, roughly ten years after the proof of Fermat’s Last Theorem, a trio of mathematicians, exploiting the techniques of Wiles and others, were able to pinpoint the exact reason for which cubic 8 and square 144 will never have any perfect-power mates in Leonardo di Pisa’s recursive sequence (except for 1). Though extremely recondite, the reason behind the infinite mutual-avoidance dance had been found. This is just one more triumph of the Mathematician’s Credo — one more reason to buy a lot of stock in the idea that in mathematics, where there’s a pattern, there’s a reason.