<![CDATA[Enormous Integers]]>

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

$\displaystyle{ \int_0^\infty \cos(2x) \cos(x) \cos(x/2) \cos(x/3) \cos(x/4) \cdots \, dx }$

The answer matches $\pi/8$ up to its 43rd digit. But it’s not actually $\pi/8.$ 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 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:

$A_1(n) = 2n$

The second Ackermann function of n is 2 to the nth power:

$A_2(n) = 2^n$

To calculate the third Ackermann function of n, you write down a tower of n 2’s. For example:

$A_3(4) = 2^{2^{2^{2}}} = 65536$

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:

$A_{k+1}(n) = A_k A_k \cdots A_k(1)$

where there are n of these $A_k$ ‘s.

For example, with a little work you can show

$A_4(4) = 2^{2^{2^{2^{\cdot^{\cdot^\cdot}}}}}$

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₇(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₇(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₇(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₇₁₉₈(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), where n = A₅(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 $A_{7198}(158386)$ and $A_{A_5(5)}(A_5(5)).$ 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.

]]>