Sometimes math problems have unexpected answers. For example, consider the integral of this infinite product:

The answer matches up to its 43rd digit. But it’s not actually Weird, huh? But it’s not a coincidence; there’s an explanation.

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 *n*th letter to the 2*n*th, is allowed to appear as a subsequence of a bigger block from the *m*th letter to the 2*m*th?

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 *n*th 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 *k*th Ackermann function *n* times to the number 1:

where there are *n* of these ‘s.

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 A _{7}(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, A_{7}(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 A_{7}(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 Ramdall Dougherty, Friedman shows that a lower bound is A

_{7198}(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, A

_{n}(n), wheren= A_{5}(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 and That’s an impressively large spread. I wonder how accurately we will ever know this number.

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, 2007.

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.

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

lookingfor 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

askingfor trouble: it’s a famous source of insanely large numbers.The problem was:

For a while the best upper bound on this

nwas Graham’s number, namelywhere

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

lowerbounds on answers to math problems, instead ofupperbounds. 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 Mindis 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,the smallest countable ordinal that cannot be defined without self-reference.roughlyIndeed I’d like to take that as the

definitionof 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

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.as above, so below• Hilbert Levitz, Transfinite ordinals and their notations: for the uninitiated.

(What a great first name for a logician!)

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

anycomputer 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.

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

thatwould 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’?)

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.

Hey, that’s nice, Tom. Let me show it here:

Or for that matter…

[…] 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!

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

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. […]