. They’re all around us, but we don’t usually see them, because they don’t quite play by the rules.

### 56 Responses to Enormous Integers

1. glorkspangle says:

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.

• John Baez says:

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…

2. dave tweed says:

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

3. David says:

Think it’s a typo, but in

So, we have a well-defined enormous integer, and we know—or at least Friedman claims—that it’s somewhere between $A_{7189}(158386)$ and $A_{A_5(5)}(5)$

Shouldn’t the upper bound be much larger: A_{A_5(5)}(A_5(5))?

• David says:

(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)

• John Baez says:

Thanks, I fixed that typo! And yes, the subscript matters more.

4. What is the largest finite number which has turned up in a “real” problem?

• glorkspangle says:

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!

• John Baez says:

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 $x$ where the number of primes less than $x$ exceeds

$\displaystyle{ \int_0^x \frac{d t}{\ln t} }$

Namely, in 1955 Skewes showed this has to happen before

$\displaystyle{ 10^{10^{10^{963}}} }$

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:

Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on 2n vertices. Then colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on 4 coplanar vertices?

For a while the best upper bound on this n was Graham’s number, namely

$g_{64}$

where

$g_1 = 3 \uparrow^4 3$

$g_{k+1} = 3 \uparrow^{g_k} 3$

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

$2 \uparrow^1 3 = 2 \times (2 \times 2) = 2^3$

is exponentiation but

$2 \uparrow^2 3 = 2 \uparrow^1 (2 \uparrow^1 2) = 2^{2^2}$

is tetration and

$2 \uparrow^3 3 = 2 \uparrow^2 (2 \uparrow^2 2)$

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!

• Tom Leinster says:

John, I think your finger slipped: the n-dimensional hypercube has $2^n$ vertices, not $2n$, as of course you know.

• John Baez says:

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.

• Klaus Draeger says:

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

5. Peter Suter says:

You first quote Andrés Caicaido:

A_{n}(n), where n = A_5(5)

Then you write

it’s somewhere between $A_{7198}(158386)$ and $A_{A_5(5)}(5)$.

shouldn’t that be

it’s somewhere between $A_{7198}(158386)$ and $A_{A_5(5)}(A_5(5))$.

?

6. grlcowan says:

The answer matches pi over eight up to its 43rd digit? Presumably you mean tau over 16!

• John Baez says:

Whoops, sorry! I’m a tauist, but a closet tauist.

7. John Baez says:

Over on Google+, Philip Thrift linked us to this video on Graham’s number:

A number so epic it will collapse your brain into a black hole!

(TREE numbers are mentioned at the end.)

Maybe mathematicians have a biggest number envy. :)﻿

• John Baez says:

I replied to Philip:

Most mathematicians don’t really care much about big numbers. For example, I don’t actually care about them at all, except as part of ‘life’s rich pageant’ along with 4-dimensional Platonic solids, the African caracal and 16 phases of ice. But there are a few mathematicians who really get into them—and then an interesting one-upsmanship develops.

We see the quest for really big numbers play out in three arenas: the natural numbers, the countable ordinals and the uncountable cardinals. The same people tend to get involved in all three.﻿

8. John Baez says:

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

• John Baez says:

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