Large integers. Really large.
John David Stone
Department of Computer Science, Grinnell College
Today I'll talk about some integers that are mind-bogglingly huge. Over the history of mathematics, the requirements for boggling people's minds have varied. My plan today is to start with some numbers whose magnitudes were mind-boggling in ancient times, and work up to some that will boggle even the minds of people who have fully assimilated and comprehended the concept of the national debt of the United States.
In the third century BC, according to Archimedes, one of the conventional examples of a mind-bogglingly huge number was the number of grains of sand in the world. In his essay The sand-reckoner, he says that “There are some ...who think that the number of the sand is infinite in multitude ... Again there are some who, without regarding it as infinite, yet think that no number has been named which is great enough to exceed its multitude.” Archimedes knew, of course, that the number of grains of sand, though large, is not infinite; the people who claim that it is are confusing the impracticability of actually counting them with the impossibility in principle of doing so. He also took the limitations of the Greek system of numeration of that era as a challenge. Perhaps no number had been named yet whose magnitude would exceed the number of grains of sand in the world, but Archimedes determined to construct, within the Greek language, a system of naming that would include such huge numbers, and thereby enable people to think of them without boggling.
Archimedes undertook to calculate an upper bound on the number of grains of sand in the world by getting an estimate for the volume of a grain of sand (a deliberate underestimate, more like the volume of one-fourth of a poppy seed), which he took as a unit of measurement, and an estimate for the volume of the observable universe (what he considered to be a vast overestimate, at any rate a volume enormously greater than that of the earth) as a multiple of this unit. In other words, he calculated how many of these mini-grains of sand it would take to fill up the entire observable universe. The techniques he used to obtain these estimates, using the science and technology of that era, are interesting in their own right, but I want instead to look at the way in which he extended the system of numeration so as to express the results of his computations.
Ancient Greek provided individual words for the whole numbers from one to nine, for the multiples of ten from ten to ninety, and distinct words for hundred and thousand. It also had a single word, rendered in English as “myriad,” which could mean “an indefinitely large number,” but could also refer specifically to the number ten thousand. There were conventional ways of combining these words to form names for all the integers up to ten thousand, and beyond, since one could also modify the word “myriad” with another numeral--“three myriads,” “fifty-two myriads,” even “a myriad of myriads.” This last phrase designated the number that we call “one hundred million” or, in exponential notation, “ten to the eighth”--ten thousand units of ten thousand each.
Clearly, Archimedes had to push beyond this. A hundred million of his tiny grains of sand would not even fill up a cube six inches on a side. His idea was to take the largest conventionally nameable number, a myriad of myriads, and to make this the unit for a second “order” of numbers, similar in structure to the first order (the numbers from one to a hundred million), but with each number of the second order being a multiple of the second-order unit. By adding a number of the second order (a multiple of one hundred million) to a number of the first order (a multiple of 1), or simply by concatenating their names, he could name any positive integer in a much larger range--all the way up to a myriad of myriads of second-order units, that is, a hundred million hundred-millions. This is ten to the sixteenth, the number for which the English name is “ten quadrillion.”
This was good, but still not good enough. Archimedes continued by taking a myriad of myriads of second-order units and calling that the unit of the third order. The third order comprised multiples of this unit, ranging up to a myriad of myriads of them--a hundred million ten-quadrillion-sized units, i.e., one septillion, which became the unit of the fourth order, a myriad of myriads of which constituted the unit of the fifth order, and so on, and so on, up to the myriad-of-myriadth order.
This, however left him with no good name for the next order, in which the unit would be a myriad of myriads of units of the myriad-of-myriadth order. So, instead of continuing with more orders, Archimedes looked at the range of positive integers, from one up to the unit of the myriad-of-myriadth order (which is ten to the eight-hundred-millionth power), and declared that those were the numbers of the first period, and the largest of them would count also as the unit of the second period of numbers. The second period is similar in structure to the first period, but each number in it would be a multiple of the second-period unit.
The numbers of the second period would also have orders, corresponding to the orders of the first period; by adding a number from the second period to a number from the first period (adding a number from each applicable order within each period along the way), one could assemble any desired number less than or equal to ten to the sixteen-hundred-millionth power--which is the unit of the third period. And so on, up to the myriad-of-myriadth period, in which the highest number is ten to the eighty quadrillionth power. This, Archimedes felt, would be more than sufficient for his purposes. His calculations actually resulted in an upper bound of ten to the sixty-third power, or, in his system, one thousand myriad units of the eighth order. Oddly enough, when I was a high-school student, one of my teachers gave this same number as the best available estimate of the number of elementary particles in the universe.
Whatever its value to Archimedes and the specialists who read his essay, this ingenious system did not catch on. The exact numerical sense of the word “myriad” eventually died out, except in Greek; instead, we counted by thousands in the same way that ancient Greeks counted with myriad--three thousand, fifty-two thousand, and so on, up to a thousand thousands. In the fourteenth century, someone started using the Latin word from which “million” is derived to denote a thousand thousand. Etymologically, a “million” is a “big thousand”--its root is the Latin word for “thousand,” but with an augmentative suffix attached.
In the seventeenth century, the word “billion” appeared, originally meaning “one million million.” The “bi-” prefix was meant to suggest the twofold iteration of the word “million,” and immediately suggested the extension to “trillion” (a million million millons, ten to the eighteenth power), “quadrillion” (a million million million millions, ten to the twenty-fourth power), and so on, for as long as your knowledge of the appropriate Latin prefixes holds out.
It turned out that this nomenclature, though potentially helpful, didn't really keep people's minds from boggling at the size of the numbers. One sign of this lingering confusion is that an alternative convention quickly appeared, in which the terms in this series, instead of denoting successive powers of one million, denoted successive powers of a thousand, so that a billion is a thousand millions, a trillion a thousand billions, and so on.
This alternative convention has become universal in the United States and France, and frequent in Canada and the United Kingdom, while the original powers-of-one-million convention is still used in most other countries. The result is that, when speaking for an international audience, you can't use this terminology at all, because you would have to give a long, tedious explanation that would dissatisfy some fraction of the listeners anyway; you might just as well use the exponential forms (“ten to the eighteenth power” or “nine followed by twenty-three zeroes”) and be done with it.
Even in reference books, the “-illion” series was allowed to peter out after no more than twenty terms, of which the last was “vigintillion” (ten to the hundred-twentieth power by the original convention, ten to the sixty-third one by the Franco-American alternative). Archimedes's sand-number, by the way, would be one thousand decillion by the original convention, or one vigintillion in the United States and France.
In the mid-1930s, the mathematician Edward Kasner was writing a popular article on large numbers and found that he needed a name for ten to the hundredth power. Dissatisfied with the conventional names, which didn't reach as far as ten to the hundredth anyway, he asked his nine-year-old nephew to suggest one. The kid came up with the name “googol,” and this coinage did catch on, at least among Kasner's readers. His nephew also suggested the name “googolplex,” originally for the number denoted by "one, followed by writing zeroes until you get tired." Kasner liked the name but overruled the definition, using it instead to refer to ten to the googolth power--“one, followed by a googol of zeroes.”
A googol can be expressed in Archimedes's terminology; it's a myriad units of the seventeenth order. A googolplex, on the other hand, outruns his orders and his periods alike. It's much, much larger than the largest number of his myriad-of-myriadth period. Fortunately, we can use the exponential notation for it, but with the googolplex even writing out the exponent is kind of tiresome, since the exponent itself is a number of a hundred and one digits. To keep from bogging down, we start using two layers of exponentiation: a googolplex is ten to the power of ten to the hundredth power.
Once you start using two layers of exponentiation, you can extend the idea to any finite number of layers. When I was in high school, my best friend gave me a book called Excursions in number theory. One of the many memorable passages in that book dealt with Skewes's number, which was supposedly the largest exact number that had appeared in a serious mathematical publication up to that time. In 1933, Skewes proved a result relating to the Prime Number Theorem, which says that, as n increases without limit, the ratio of the number of prime numbers less than n to integers less than n asymptotically approaches the reciprocal of the natural logarithm of n.
Some years before, Littlewood had proposed a refinement of this theorem that gave even more accurate estimates of the number of prime numbers less than n, and had shown that this refinement sometimes overestimated the correct tally of prime numbers and sometimes underestimated it, alternating back and forth infinitely many times as n increases without limit. However, in Littlewood's day, exact counts of prime numbers were known only up to about ten million, and in that range Littlewood's refinement was always an overestimate.
Skewes determined an upper bound on the value of n by which Littlewood's refinement would underestimate the correct value at least once. Skewes' upper bound was e to the power of e to the power of e to the seventy-ninth power, which is (very, very, very approximately) ten to the ten to the ten to the thirty-fourth power--a one, followed by ten to the ten-decillionth power zeroes. When I was fifteen, this boggled my mind.
Skewes's number is much, much larger than a googolplex--so large that there is no reasonable or intelligible use for it in describing the physical world, at least so far as I know. The largest number that I have ever seen used to describe a physical phenomenon of any sort occurs in Roger Penrose's recent book The road to reality, which purports to explain the nature of the universe as physicists see it to an average reader who is willing to invest a lot of preliminary work trying to pick up the rudiments of tensor calculus and the theory of manifolds. In Archimedean fashion, Penrose calculates an upper bound for the volume of the phase space of the universe, that is, the number of different possible states of the universe: ten to the ten to the one hundred twenty-third power. This number lies between the googolplex and Skewes's number, but is much closer to the googolplex.
One of the limitations of Archimedes's numeration system, and even more of the million-billion-trillion series, is that it doesn't always make the most efficient use of one set of names before adding another. Whether a trillion is a thousand billion or a million billion, it's not really necessary to start using a new name so soon; we could go all the way up to a billion billion before we really needed a new unit. The computer scientist Donald E. Knuth has made this idea systematic, in a paper called “Supernatural numbers.”
Knuth begins with the prose numerals from one to nine and the multiples of ten from ten to ninety. English provides combination rules for these, so we can name the numbers from one to ninety-nine before needing a new unit name, “hundred.” By counting hundreds from one to ninety-nine, we can name the numbers from one to ninety-nine hundred and ninety-nine before needing a new unit name. So we don't need the word “thousand”; a thousand is just ten hundreds, and five thousand (for example) is just fifty hundreds.
The next unit we need is for ten to the fourth, and Knuth proposes to revive the name “myriad” for this purpose. By counting myriads and combining, we can name the numbers from one to ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine before needing a new unit name--all but the last of Archimedes's numbers of the first order.
For the next number, which is Archimedes's unit of the second order, Knuth proposes the name “myllion.” By counting myllions and combining, we can name the numbers from one to ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine myllion ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine--all but the last of Archimedes's numbers of the second order.
For the next number, which is Archimedes's unit of the third order, Knuth proposes the name “byllion.” By counting byllions and combining, we can name the numbers from one to ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine myllion ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine byllion ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine myllion ninety-nine hundred ninety-nine myriad ninety-nine hundred ninety-nine--all but the last of Archimedes's numbers of the fourth order (not the third). Note that Archimedes did not use his own numbers efficiently as multipliers, instead starting a new order every time he got up to a myriad of myriads of the unit of the current order.
A hundred is ten squared; a myriad is ten to the fourth; a myllion is ten to the eighth; a byllion is ten to the sixteenth. In Knuth's system, a new name is needed only when the exponent is a power of two, reflecting the fact that he's essentially solving the problem of naming large numbers by the method known in computer science as “divide and conquer” or “bisection.” To provide the new names for larger and larger units in this series, he borrows the million-billion-trillion nomenclature, with the substitution of a y for the i at the beginning of “illion”: a tryllion is ten to the thirty-second; a quadryllion is ten to the sixty-fourth, and so on.
If we stick with Latinate names, however, they will eventually give out. Besides, not many people know Latin, and even those who do tend to mess up the numerals occasionally when their minds begin to boggle. So Knuth proposes alternative names for the myllion, the byllion, and so on: One myllion can also be called “one latinoneyllion,” one byllion can also be called “one latintwoyllion,” and so forth. In general, for any positive integer k, one can place the name of k between the prefix “latin” and the suffix “yllion” to get the kth term in the sequence, denoting ten to the power of two to the (k + 2)nd power.
One can construct the name of a power of ten, in this system, by expressing the exponent as a sum of powers of two and then concatenating the corresponding Knuthian prose numerals, in ascending order of magnitude. A googol, in this system, is one myriad tryllion quadryllion, or alternatively one myriad latinthreeyillion latinfouryillion, since the exponent, one hundred, is the sum of four, thirty-two, and sixty-four, and ten to the fourth is a myriad, ten to the thirty-second is a tryllion, and ten to the sixty-fourth is a quadryllion. The googolplex also has a name, but since you have to add together a hundred and five different powers of two in order to obtain one googol, which is the exponent in this case, it would take me more than a minute to read the Knuthian prose numeral for a googolplex aloud, and I am afraid that it would not be very edifying. However, since two to the three-hundred-thirty-third power is more than one googol, one latinthreehundredthirtyoneyllion is considerably more than one googolplex.
Being a computer scientist, Knuth naturally allows the “latin-k-yllion” construction to proceed recursively, so that a latinlatinoneyillionyillion (or latinmyllionyllion) is ten to the two to the hundred million and second power. Here's another illustration of the use of this nesting: It would again be tedious to try to express Skewes's number even very approximately, but I have calculated that it is less (much less) than a latinonehundredlatinthreeyllionyllion.
Since 1933, there has been a lot of progress in mathematics and in computer science, and Skewes's number is no longer the largest number to appear “naturally” in a serious work in the field, still less in a frivolous one. I thought that I might see a new candidate for the title in 1983 when the computer scientist Douglas Hofstadter, who was then writing a monthly column for Scientific American, announced an interesting lottery, with the following terms:
The prize of this lottery is $1,000,000/N, where N is the number of entries submitted. Just think: If you are the only entrant (and if you submit only one entry), a cool million is yours! Perhaps, though, you doubt this will come about. It does seem a trifle iffy. If you'd like to increase your chances of winning, you are encouraged to send in multiple entries--no limit! Just send in one postcard per entry. If you send in 100 entries, you'll have 100 times the chance of some poor slob who sends in just one. Come to think of it, why should you have to send in multiple entries separately? Just send one postcard with your name and address and a positive integer (telling how many entries you're making) to [a real address at Scientific American].
As Hofstadter expected, many Scientific American readers took this as a challenge to come up with the largest positive integer that could be named on a postcard. Entries were received from about two thousand people. Nine entrants wrote the (exponential-form) numeral for a googol on their postcards; fourteen relatively advanced thinkers wrote a googolplex instead. Some of them filled up the postcard with tiny nines; those people were pikers. Others wrote only one nine, followed by a series of exclamation points, each presumably taking the factorial of the number that preceded it. Hofstadter continues:
A handful of people carried this game much further, recognizing that the optimal solution avoids all pattern ... and consists simply of a “dense pack” of definitions built on definitions, followed by one final line in which the “fanciest” of the definitions is applied to a relatively small number such as 2, or better yet, 9.
I received, as I say, a few such entries. Some of them exploited such powerful concepts of mathematical logic and set theory that to evaluate which one was the largest became a very serious problem, and in fact it is not even clear that I, or for that matter anyone else, would be able to determine which is the largest integer submitted. I was strongly reminded of the lunacy and pointlessness of the current arms race, in which two sides vie against each other to produce arsenals so huge that not even teams of experts can meaningfully say which one is larger--and meanwhile, all this monumental effort is to the detriment of everyone. ...
As it turns out, I don't know who won, and it doesn't matter, since the prize is zero to such a good approximation that even God wouldn't know the difference.
Hofstadter didn't publish any of the “dense pack” postcards that he received, so I don't know exactly how large they got, and in any case none of them qualifies for the record of largest number mentioned exactly in a published paper. But you can get some sense of what the lottery judges were facing by looking my candidate for the record: the largest integer I have ever seen mentioned in print. It comes from a 1970 paper by Ronald Graham and Bruce Rothschild that dealt with the following problem.
Imagine a unit hypercube in n dimensions. It has two to the nth power corners (a square has four, a cube has eight, a four-dimensional hypercube has sixteen, and so on). Connect each pair of corners of the hypercube with a line segment that is colored either red or blue. Is it always possible to do this in such a way that no four corners in the hypercube, all lying in the same plane, are connected among themselves by lines of the same color?
When n is 2 or 3, the answer is yes: there is a way of coloring all the connecting lines so that every set of four corners that lie in the same plane is connected up with lines of both colors. Graham and Rothschild were able to prove that, when n is sufficiently large, the answer is no; no matter what coloring system you use, there will always be some set of four corners lying in a plane that are monochromatically connected. They were even able to deduce an upper bound on n. That upper bound is the number I'm talking about.
I'll need special notation to describe it. Even for much smaller numbers, we've needed the operations of addition, multiplication, and exponentiation to identify the values we have in mind, and we've even been driven to use a kind of super-exponentiation. It will be helpful to have a notation for exponentiation and super-exponentiation that doesn't involve shrinking superscripts, so let's use the symbol ↑ to stand for exponentiation, so that, say, “5↑4” means five to the fourth power, or 625, and the symbol ↑↑ to stand for super-exponentiation, so that “5↑↑4” means “5↑(5↑(5↑5))”, or five to the power of five to the power of five to the fifth–the number to the right of the ↑↑ symbol indicates how many times the number 5 occurs in the repeated exponentiation. 5↑↑4, incidentally, is already much larger than a googolplex, though much smaller than Skewes's number.
Once we have the notion of repeated exponentiation, however, we can iterate that as well, writing, say, “5↑↑↑4” for “5↑↑(5↑↑(5↑↑5)))”, where the number to the right of the ↑↑↑ symbol indicates how many times 5 occurs in the super-hyper-exponentiation. And, having gone so far, we can proceed with a series of operators of higher and higher potency: ↑↑↑↑, ↑↑↑↑↑, and so on indefinitely.
To get to Graham and Rothschild's upper bound, we start with the number 3↑↑↑↑3, which is 3↑↑↑(3↑↑↑3), or 3↑↑(3↑↑(3↑↑(3↑↑(...(3↑↑3)...))), where the number of nested pairs of parentheses is 3↑↑↑3 (minus one). Now, 3↑3 is 27, so 3↑↑3 is three to the twenty-seventh power, which is seven trillion and change. 3↑↑↑3 describes a repeated exponentiation in which the tower of exponents contains 7625597484987 occurrences of the number 3. The value of that number is the number of times you need to repeat the ↑↑ operation.
Now, 3↑↑↑↑3 isn't yet the number; it's only the first of a sequence of sixty-four numbers, the last of which is the upper bound on the solution to the coloring problem. Given one number k in this sequence, we can get the next one by writing a 3, then k occurrences of the ↑ symbol, and then another 3. So the second number in the sequence contains a super-hyper-meta-exponentiation operator whose “potency” is measured by the first number, the one that we tried to get a grip on above. If we apply that unbelievably potent operator to 3 (as the base) and 3 again (as the super-hyper-meta-exponent), we get the second number. Then, if we write out the number of ↑ symbols expressed by the second number and apply the operator with that potency to 3 (as the base) and 3 again (as the supersuper-hyperhyper-metameta-exponent), we get the third number. And so on, until we get to the sixty-fourth number in the sequence.
Graham and Rothschild are sure that, in a hypercube of this many dimensions at most, there will be enough corners to ensure that four of them, lying in the same plane, will be monochromatically connected no matter how the lines connecting the corners are colored. This is just an upper bound, and it may be a rather loose one. Some of the people who have studied the question think that a smaller number of dimensions would actually suffice. When Graham and Rothschild wrote their paper, the best known lower bound was 6; subsequent work by Geoffrey Exoo has narrowed the gap by finding colorings in which every four coplanar vertices are connected by edges of both colors in hypercubes of dimensions 7, 8, 9, and 10. So we now know that the crucial number of dimensions is somewhere between 11 and Graham and Rothschild's number.
We have now reached a point at which my mind is beginning to boggle. This seems like a good stopping point. In conclusion, though, I'd like to remind you that Archimedes's stern rejection of claims of infinitude or innumerability was correct. All of the integers I have mentioned today are finite and can be exactly specified. But it is also true that, in the overall scheme of things, almost all positive integers are larger (much, much larger) than even Graham and Rothschild's number. As positive integers go, these are tiny integers. Really tiny.
September 6, 2007
revised February 6, 2008
This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 United States License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/3.0/us/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
Bibliography
Archimedes of Syracuse. The sand-reckoner. The world of mathematics, vol. 1. Ed. James R. Newman. New York: Simon and Schuster, 1956. 420--429.
Exoo, Geoffrey. “A Ramsey problem on hypercubes.” January 13, 2007. <http://isu.indstate.edu/ge/GEOMETRY/cubes.html>
Gardner, Martin. “Ramsey theory.” Penrose tiles to trapdoor ciphers: ... and the return of Dr. Matrix. Washington, D.C.: The Mathematical Association of America, 1989.
Hofstadter, Douglas R. “Dilemmas for superrational thinkers, leading up to a Luring Lottery.” Metamagical themas: questing for the essence of mind and pattern. New York: Basic Books, Inc., 1985. 739--755.
Hofstadter, Douglas R. “Irrationality is the square root of all evil.” Metamagical themas: questing for the essence of mind and pattern. New York: Basic Books, Inc., 1985. 756--766.
Kasner, Edward, and James R. Newman. “New names for old.” The world of mathematics, vol. 3. Ed. James R. Newman. New York: Simon and Schuster, 1956. 1996--2010.
Knuth, Donald E. “Supernatural numbers.” Mathematical recreations: a collection in honor of Martin Gardner. Ed. David A. Klarner. Mineola, New York: Dover Publications, Inc., 1998 [1981].
Ogilvy, C. Stanley, and John T. Anderson. Excursions in number theory. New York: Oxford University Press, 1966.
Penrose, Roger. The road to reality: a complete guide to the laws of the universe. New York: Knopf, 2007.