Sometimes math problems have unexpected answers. For example, consider the integral of this infinite product:
The answer matches 
Here’s a puzzle due to the logician Harvey Friedman. It too has an unexpected answer.
Say you have a finite alphabet to write with. How long can a word be if no block of letters in this word, from the nth letter to the 2nth, is allowed to appear as a subsequence of a bigger block from the mth letter to the 2mth?
If you have just one letter, this is the longest it can be:
AAA
If you have two, this is the longest it can be:
ABBBAAAAAAA
Puzzle: How long can the word be if you have three letters in your alphabet?
Friedman showed there’s still a finite upper bound on how long it can be. But, he showed it’s incomprehensibly huge!
Now Friedman is one of the world’s experts on large cardinals—large infinite numbers. So when he says a finite number is incomprehensibly huge, you sit up and listen. It’s like seeing a seasoned tiger hunter running through the jungle with his shotgun, yelling “Help! It’s a giant ant!”
The answer to the puzzle involves the 7th Ackermann function. The first Ackermann function is just doubling:
The second Ackermann function of n is 2 to the nth power:
To calculate the third Ackermann function of n, you write down a tower of n 2’s. For example:
And so on: to calculate the (k+1)st Ackermann function applied to n, you apply the kth Ackermann function n times to the number 1:
where there are n of these 
For example, with a little work you can show
where the number of 2’s in the tower is 65,536.
But this is still puny, compared to the answer to the puzzle!
In 1998 Friedman show that the longest word you can write with 3 letters, following the rule I described, is at least A7(184) letters long.
As he notes, when we reach numbers this large:
… a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another.
I don’t understand his proof, but you can see it here:
• Harvey M. Friedman, Long finite sequences, 8 October 1998.
When I posted about this on Google+, Andrés Caicedo helped me notice that later in the paper, Friedman goes further. In fact, A7(184) is a ridiculous underestimate of the true answer! And apparently now there’s an upper bound on the answer, too.
When Andrés Caicaido heard me say the word could be at least A7(184) letters long, he wrote:
Much much longer!
I wrote a bit on this:
• A lower bound for n(3), 14 February 2012.
Using some computer assistance from Randall Dougherty, Friedman shows that a lower bound is A7198(158386). I asked Dougherty, and got a copy of his files. I am hoping to find some decent time in the not too distant future to examine them in detail and see how far this can be pushed.
Friedman also found an upper bound, An(n), where n = A5(5). He mentions this in a note from 2001, but the note is a series of announcements with no proofs. Actually, it is exciting stuff, in spite of the lack of proofs. He discusses some other simply defined combinatorial constructions that give numbers much much longer than this one:
• Harvey M. Friedman, Lecture notes on enormous integers, 22 November 2011.
So, we have a well-defined enormous integer, and we know—or at least Friedman claims—that it’s somewhere between 
I should add that beside the sheer shock value of seeing such a huge number show up as the answer to a simply stated puzzle, there’s some deep math lurking in these games. It gets rather scary. Near the end of his lecture notes, Friedman mentions a number so big that any proof of its existence—in a certain system of mathematics—has an incomprehensibly large number of symbols.
But if all this talk of enormous integers isn’t scary enough for you, just wait until you read about dark integers:
• Greg Egan, Dark integers, in Dark Integers and Other Stories.
Dark matter, dark energy . . . dark integers. They’re all around us, but we don’t usually see them, because they don’t quite play by the rules.
Azimuth 
Friedman’s proof concerns subsequences, not consecutive subsequences. He shows n(2)=11 with the example ABBBAAAAAAA: of the [i,2i] consecutive subsequences of this {AB, BBB, BBAA, BAAAA, AAAAAA}, none is a subsequence of another. I don’t believe (but can’t show) that his theorem works for consecutive subsequences.
Thanks, I fixed that mistake. I make no claims to understanding this stuff, not even slightly! But I don’t want my blog post to spread misinformation…
Related to the first linked paper, which discusses the potential for errors in mathematical statements derived in one way or another from computer output, this page (with links two more formal publications half way down) describes the use of computer systems to aid in determining when mathematical statements derived from “human output” contain errors. (This isn’t via the approach of starting the theorem in a logical system and then producing an automatic proof tree.)
Think it’s a typo, but in
Shouldn’t the upper bound be much larger: A_{A_5(5)}(A_5(5)) ?
(and when I say “much larger” – in this context, although it’s unimaginably larger, it’s actually not that different: the size of the subscript far outweighing the operand)
Thanks, I fixed that typo! And yes, the subscript matters more.
What is the largest finite number which has turned up in a “real” problem?
What is a “real” problem? To a mathematician, the problems producing the numbers described in this blog post are quite real. Such finite numbers include things like n(4), or TREE(4), or BB(10), all of which are huge beyond any comprehension. Quite possibly there are “real” problems which combine these into monsters such as BB(n(6)) or TREE(BB(5)), just as Friedman’s sequence problem creates things like A_{A_5(5)}(A_5(5)).
Yes, these problems are quite real; I wasn’t implying that they aren’t!
While the problems described in this post are “real”, and so are the related ones alluded to by Herr Glorkspangle, I believe they’ve all been designed by mathematicians who are looking for problems with enormous answers. If we include problems like this, it becomes very hard to point to an integer and say it’s the largest one that’s come up in a real problem—because doing that will instantly make some mathematician find a much larger one!
You probably know some of this stuff, but…
Skewes’ number came up as an upper bound on the first number
where the number of primes less than 
exceeds
Namely, in 1955 Skewes showed this has to happen before
Later the bound was vastly decreased.
Graham’s number is famous because in 1977, Martin Gardner wrote that “in an unpublished proof, Graham has recently established … a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.” It’s vastly larger than Skewes’ number. However, it shows up in Ramsey theory, and as far as I can tell, people who work on Ramsey theory are sort of asking for trouble: it’s a famous source of insanely large numbers.
The problem was:
For a while the best upper bound on this n was Graham’s number, namely
where
and Knuth’s up-arrow notation is a way of talking about the operations that come after addition, multiplication, exponentiation, tetration, and so on. For example
is exponentiation but
is tetration and
Later Graham’s upper bound was much improved, but it’s still insanely large. The lower bound is, err, umm… 13.
So, one advantage of Friedman’s enormous integers over Skewes’ number and Graham’s number is that they’re showing up as lower bounds on answers to math problems, instead of upper bounds. Clearly you can get very high upper bounds just by being very stupid… though I’m certainly not accusing Skewes or Graham of that!
John, I think your finger slipped: the n-dimensional hypercube has
vertices, not 
, as of course you know.
I enjoyed your post!
Cut-and-paste loses superscripts. Will fix!
“You probably know some of this stuff, but…”
I remember an essay by Isaac Asimov called “Skewered”. :-)
For large infinite numbers, Rudy Rucker’s Infinity and the Mind is a nice read.
Many “real” problems are actually parametric, so that the question perhaps should be about naturally occurring rapidly growing sequences, rather than huge individual numbers.
One area where such problems can occur is formal verification, see for example Philippe Schnoebelen’s paper on Ackermann-hardness of (among others) reachability in lossy counter machines: http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/phs-mfcs10.pdf
You first quote Andrés Caicaido:
Then you write
shouldn’t that be
?
Yes, thanks. Fixed!
The answer matches pi over eight up to its 43rd digit? Presumably you mean tau over 16!
Whoops, sorry! I’m a tauist, but a closet tauist.
Over on Google+, Philip Thrift linked us to this video on Graham’s number:
I replied to Philip:
Puzzle. Put an upper or lower bound on this number:
“The smallest natural number that cannot be specified in seventeen English words without use of self reference.”
The above puzzle is my attempt to find a finite analogue of the Feferman-Schütte ordinal. This is roughly, roughly the smallest countable ordinal that cannot be defined without self-reference.
Indeed I’d like to take that as the definition of the Feferman-Schütte ordinal: since this definition is self-referential we don’t fall into Berry’s paradox. Unfortunately it’s hard to define ‘self-reference’ in a formal mathematical way.
The Feferman-Schütte ordinal is often described as the smallest ordinal that can only be defined impredicatively: an impredicative definition is one that mentions the thing being defined, or a set that contains the thing being defined.
However, even this way of describing the Feferman-Schütte ordinal is vague and controversial. The really precise definition of the Feferman-Schütte ordinal is that it’s the smallest ordinal
with
Here
is the Veblen function, a fairly powerful way of generating large countable ordinals. The idea is that we start by setting
where
is the first infinite ordinal, and then for 
we define 
to be the κth fixed point of the functions 
for all 
(Here we count starting at
, so what you’d normally call the first fixed point, meaning the smallest one, we’re calling the 0th.)
For example, we have
and so on… but eventually we hit the smallest fixed point of
which is usually called 
It’s the smallest ordinal such that
so heuristically speaking we may say
Since this is the smallest fixed point of
we have
Then we define
and so on, until we hit the smallest fixed point of
which is 
So, heuristically, we may say
And this goes on and on, giving larger and larger countable ordinals, but we’ll never reach the Feferman-Schütte ordinal this way. It’s the first one we won’t get this way…
…and it’s the start of another hierarchy of even larger countable ordinals defined using the Γ function.
There’s something very strange about this business: it’s like you’re running away from your own shadow, but the faster you run the faster it does do, so you can never escape. Any systematic notation for indexing ordinals gives out when it hits a fixed point: the existence of all these fixed points follows from the usual axioms of set theory. But then we can make a new notation that takes this into account and gives even larger ordinals. The game goes on until we hit the Church–Kleene ordinal, which I’m not at liberty to discuss here.
Any word on n(4) and higher, and whether or not they’re finite?
Ah, good question! I was hoping someone would ask. Since I didn’t quite define n(k), I should come out and do so now:
Definition. Given an alphabet with k letters, n(k) is the maximum length a word can have if no block of letters in this word, from the ith letter to the 2ith, is allowed to appear as a subsequence of a bigger block from the jth letter to the 2jth.
If you read Harvey Friedman’s paper—even, like me, without truly understanding it—you’ll see that all these n(k)’s are finite. And in his Lecture notes on enormous integers he says (and I paraphrase for clarity):
So n(4) makes n(3) look like a pathetic runt of a number.
But later come some fairly large numbers like n(n(4)), and so on…
John wrote:
And I think that’s a major point. I admit that my brain fogs out when I see things like that lower bound given for
— it really means nothing to me, and part of me thinks that it’s all so much mental masturbation. However, I somewhere got the idea that what drives a lot of Friedman’s research here is something more serious, along the lines that within ordinary mathematics accessible to graduate students, there lurk numbers so large that to even prove them finite requires something equivalent in strength to super-large cardinal axioms in set theory. In effect, these super-large finite numbers are produced by taking advantage of the underlying combinatorics of super-large cardinals, but now Friedman’s point is that this same type of combinatorics is hidden, in disguise, amongst items that you and I as ordinary mathematicians (NB: not set theorists) might be actually seriously interested in, like: trees, vector spaces, Hilbert spaces, etc. Thus, statements in ordinary mathematics are shot through with set theory considerations in some fairly unexpected ways.
(I’m not sure I’ve said this right — this is just the idea I got.)
It’s certainly true that these people know a bunch of tricks like: how to use large countable ordinals to produce large integers (see for example here.
Todd wrote:
I don’t understand that yet but Friedman alludes to it in his Lecture notes on enormous integers, and that’s the sort of thing I want to understand better. I’m imagining an as above, so below kind of thing where some of the same structures appear in the world of large large natural numbers, large countable ordinals and large cardinals. Another example might be how Bachmann uses uncountable cardinals to index large countable ordinals! It’s mentioned near the end of the following very gentle introductory paper. However, now I’m trying to reach the point of understanding these issues in a bit more detail.
• Hilbert Levitz, Transfinite ordinals and their notations: for the uninitiated.
(What a great first name for a logician!)
Off-topic, but from my salad days as a chessplayer, I remember there was a fellow in the local club whose name was Hilbert (“Hibby”) Bernstein. I’ve always thought that would have been a great name for a mathematician, if only he was one!
It must only be math fans who name their kids ‘Hilbert’, right? It’s not usually a first name, is it?
(And does anyone really name their kid ‘Dilbert’?)
That indexing by cardinals is at the heart of Goodstein Sequences. Goodstein’s theorem (1944) proves using elementary set theory, that all these sequences are finite (they get back to zero in finitely many steps).
Later on (1982) Paris and Kirby have shown that Goodstein’s theorem is unprovable in Peano arithmetic.
Otherwise these are rather ordinary sequences, I remember writing a short and elegant bc script that calculated them. The catch, of course, is the script could barely run, because after the first few steps it stops on any computer with a memory overflow.
Members of Goodstein Sequences grow pretty fast (before they start to decrease), there is simply not enough space in the physical world to hold their representation (not even an ideal storage device with some 10⁷⁰ bit/m² information density).
Proving that Goodstein sequences go to zero uses induction on ordinals up to
… not using uncountable cardinals to index countable ordinals. I explained this in week236 of This Week’s Finds. In the Addendum there, Kevin Buzzard shows that the Goodstein sequence starting with the number 4 takes
steps to reach zero.
Thanks, Hendrik! Fixed!
Your link to Hilbert Levitz’s paper, Transfinite ordinals and their notations: for the uninitiated, is broken. If I chop off several parts at the start of the URL it works. So I suspect the software generating this web page is prefixing something to the URL that it shouldn’t.
Indeed, one may well view the whole study of ordinal notations as the study of exotic-yet-manageable well-orderings on
. One can then consider huge collections of disjoint families corresponding to 
for notable — er, notatable — limit ordinals 
; of necessity, most of these will tend to become large rather quickly as 
increases.
TEST. Unimportant comment/story lost 2nd time. Giving up.
Or for that matter…
Hey, that’s nice, Tom. Let me show it here:
[…] Bird submitted a link to Enormous Integers, saying, “It’s still a common enough misconception that pure mathematics research must be about larger and larger numbers, but it’s still nice to sometimes play up to this stereotype, as John Baez’s blogpost on Azimuth about ‘Enormous Integers’ does. Comments are worth a look too.” […]
I don’t understand the statement of the puzzle. What are n and m?
n is any natural number and m is any larger natural number. That’s implicit in this statement:
By saying “no block” we mean n can be anything, and by saying “no bigger block” we mean m can be anything bigger than m.
The URL for Greg Egan’s “Dark Integers” story doesn’t work. Try http://www.asimovs.com/_issue_0710/Dark.shtml
Thanks! Fixed!
The new URL is now broken, too. Is this the correct new one? http://will.tip.dhappy.org/blog/Compression%20Trees/…/book/by/Greg%20Egan/Dark%20Integers/Greg%20Egan%20-%20Dark%20Integers.html
That’s the story “Dark Integers”, anyway.
This URL appears to have had “…” inserted into it. Anyway, it doesn’t work (although it perhaps used to). I may remember reading the story — is it the one where our computational world was being invaded by a different set of integers; the invasion becoming evident starting with the huge integers used in cryptography?
“Luminous” and “Dark Integers” are two short stories by Greg Egan about a different mathematical universe and its interaction with ours. The best way to read them now seems to be this book:
• Greg Egan, Dark Integers and Other Stories.
When looking at large numbers constructed differently, like n(3), Graham’s number, or the “Moser”, how do you even approach determining which is larger?
I’m not an expert on this subject, so I don’t know. If anyone knows a good example of a proof like this, please point us to it!
I imagine some sort of inductive argument could work, showing that some sort of construction will beat some other one at each step.
It should help that if you take any two of the numbers, one is usually much, much larger than the other, so an argument can make lots of approximations and still succeed.
Tim Chow has proved that Graham’s Number is larger than the Moser;
http://www-users.cs.york.ac.uk/susan/cyc/b/gmproof.htm
I think Todd Cesere has too.
By the way, the upper bound on the problem Graham was considering has—it seems—been dramatically reduced by Royce Peng!
(I say “it seems” because I’m not enough of an expert to understand the argument.)
J. E. Littlewood acknowledged the difficulty in the chapter Large Numbers of his book “Littlewood’s Miscellany.” Here’s his comment (plus a bit of the rest of the chapter, to give you a taste)-
“We can now say: scrap the existing definitions, as scaffolding, and define this to be
, and carry on as before. We can scrap again, and so on: here I decide to stop. Once we stop we may take 
, or 
(what we take does not matter provided only 
).
The reader will agree that the numbers mentioned are large: it is not possible to say how large; all that can be said about them is that they are defined as they are defined. If it were desired to compare terms in two rival systems a considerable technique would have to be developed.”
By the way, this post is a kind of followup to my post on enormous integers. Insanely long proofs are related to enormous integers: if you know a quick way to describe an enormous integer, you can write down a short theorem with an enormous proof.
n(x) grows as fast as linear arrays with arbitrary length in Jonathan Bowers’ array notation…
I’m pretty sure Tiger hunters don’t use shotguns.
Good point — as you can see, I don’t hunt for big game myself, unless you count enormous integers.
This wonderful posting reminds me of one of the most enjoyable chapters in the delightful “Littlewood’s Miscellany,” which concludes with a Littlewoodian riff on large-number construction. A teaser from its last paragraph:
“We can now say: scrap the existing definitions, as scaffolding, and define this to be Fi(n) and carry on as before. We can scrap again, and so on: here I decide to stop…The reader will agree that the numbers mentioned are large: it is not possible to say how large; all that can be said about them is that they are defined as they are defined. If it were desired to compare terms in two rival systems a considerable technique would have to be developed.”
Nice! I’d forgotten that Littlewood was interested in constructing large numbers, probably to compensate for the teasing he received as a child due to his name.
I forgot to mention the chapter title: Large Numbers
[…] Există un puzzle matematica al cărui răspuns este un număr foarte foarte mare. Cum imens? Potrivit Harvey Friedman, e incomprehensibly imens. Acum Friedman este un expert pe numere infinite enorme și cum existența lor afectează matematica obișnuită. Deci, când spune un număr finit este incomprehensibil imens, e înfricoșător. E ca și cum vedea un vânător tigru experimentat care trece prin jungla cu pusca lui, striga “Ajutor! E o furnică gigant!” Pentru mai multe, citiți acest lucru. […]
[…] sorts of numbers count as “big” these days, check out John Baez’s blog post on enormous integers (but ignore the first half-dozen lines, which treat a different topic). Baez describes a […]
I remember in the 1970’s playing with lambda-expressions for Church numerals, and experimenting with
(1) how large a Church numeral one could get with a lambda-expression of limited size
(2) how small an expression was sufficient t express particular integers.
And I was interested in integers that were the simpler than the others in their neighbourhood.
It didn’t take long before I realized that passing an integer as a parameter to another gave me exponentiation, which was thus a lot simpler than using addition of multiplication.
Nor did it take long to realize that actually comparing the large integers represented by these lambda expressions quickly became infeasible.
I assigned a cost of 1 for each application and each lambda.
I did tinker with a computer program that would generate typed lambda expressions of the proper type (T->T)->(T->T), but it didn’t produce anything interesting in practical time.
At some point I figured that I’d really have to impose some information-theoretic cost to the use of variables, perhaps a logarithm depending on how many contextually bound variables were available to choose from… this got inconveniently complicated and the project was laid to rest.