What’s the Biggest Number?

Time for a little fun again. Most of us played this game when we were kids. It fairly quickly degenerates into “infinity plus one” or the even more preemptive “whatever you say next plus one”. But if you’re not allowed to use infinity and you have to name the number and demonstrate how you get to it, is this still interesting? For mathematicians this falls within a very active area of mathematics called combinatorics. Better yet, you can understand interesting aspects of this area with no more than high-school math, which makes it appealing to math geeks like me.

Benchmarks for sizing very large numbers

Start with a hierarchy of operations on how to build big numbers. First you can add (1+1+…+1), then you can multiply (repeated addition: a+a+…+a), then you can exponentiate (repeated multiplication (a*a*…*a). Repeated exponentiation should be next (a^a^…^a); this is called quadration, usually written as [SUP]n[/SUP]a (for “n” a’s in the list). Then you can go to pentation and further, but notation quickly becomes a problem. Knuth’s (yes, that Knuth) up-arrow notation resolves this: a↑n is just a[SUP]n[/SUP], a↑↑n is [SUP]n[/SUP]a, a↑↑↑n is pentation, a↑↑↑↑n is hexation and so on. You can simplify the notation further: a↑[SUP]k[/SUP]n is a followed by k ↑’s followed by n.

These numbers grow reallyfast. 2↑↑2 is 4 but 3↑↑3 (3[SUP]27[/SUP]) is over 7 trillion, 3↑↑↑3 is 3 to the power of over 7 trillion, and 3↑↑↑↑3 is 3 quadratedto over 7 trillion, or 3 with a tower of over 7 trillion exponentiations by 3. The normal question to ask at this point is what these look like as a power of 10. I’m glad you asked. Apart from the very lowest cases, these numbers are so massive that there is no reasonable way to represent them as powers of 10, unless the power is also a number in up-arrow form. By comparison, the number of atoms in the universe (~10[SUP]80[/SUP]), Shannon’s number (yes, that Shannon – this is a lower bound on the game-tree complexity of chess – is ~10^120), even googleplexes (10^10^100) are puny, entirely negligible compared to these numbers.

The Knuth notation is useful but those arrows are awkward, so there’s a different animal called the Ackermann function. One version with two arguments, A(m,n), has a simple recursive definition and extends the Knuth method, in fact A(m,n) = 2↑[SUP]m-2[/SUP](n+3)-3. So A(4,2) is ~ 10[SUP]19,729[/SUP]. But the single argument version is a doozy. A(n) is an abbreviation for A(n,n) – this grows faster than almost all other functions. A(3) is 61, but A(4) is ~ 2^2^2^65,536 and each step beyond grows the number of up-arrows, putting these far beyond any possibility of representing them in repeated exponentiation.

By the way, when you get up to these levels, in a[SUP]n[/SUP] the value of n dominates and the value a (the base) becomes increasingly unimportant. So if you’re thinking that you could give these functions a big boost by changing the base from 2 to 10 – don’t bother. That simply multiplies the value of the exponent by between 3 and 4, a completely negligible change when the exponent is at these sizes and the next number up in the sequence is super-exponentiation levels larger. Put another way, yes, replacing 2 by 10 in the base makes the number bigger, but only in an uninteresting way.

The next step with the Ackermann function is to recursively nest – define A[SUP]2[/SUP](n) as A(A(n)), A[SUP]3[/SUP](n) as A(A(A(n))) and so on. At each step, you evaluate the inner function in the nesting, which gives you an incredibly huge value, which becomes the argument to the next function in the nesting. Graham’s number, once thought to be the largest number ever encountered in a math proof, is thought to be ~ A[SUP]64[/SUP](4).

Things this size can really be found (in math)

Building these gigantic numbers is temporarily entertaining, but their real point is to provide benchmarks against which large numbers found in math problems, like Graham’s number, can be measured. I’ll start with an easy example, Goodstein sequences, for which you need to understand “hereditary base-n” notation. This is very similar to conventional base-n notation (like binary) except that powers also have to be represented in base-n. For example, 16 in base 2 is 2^4 and 4 in base 2 is 2^2, so 16 in hereditary base 2 is 2^2^2. To generate a sequence starting from n, represent n first in hereditary base-2. To get the next value in the sequence, increase all instances of the base (in exponents also) by 1, then subtract 1 from the number. If we start with 4, we get:

[TABLE] align=”center” class=”cms_table_grid” style=”width: 500px”
|- class=”cms_table_grid_tr”
| class=”cms_table_grid_td” | Increase Base
| class=”cms_table_grid_td” | Subtract 1
| class=”cms_table_grid_td” | Value
|- class=”cms_table_grid_tr”
| class=”cms_table_grid_td” |
| class=”cms_table_grid_td” |
| class=”cms_table_grid_td” | 4 (=2[SUP]2[/SUP])
|- class=”cms_table_grid_tr”
| class=”cms_table_grid_td” | 3[SUP]3[/SUP]
| class=”cms_table_grid_td” | 2.3[SUP]2[/SUP]+ 2.3 + 2
| class=”cms_table_grid_td” | 26
|- class=”cms_table_grid_tr”
| class=”cms_table_grid_td” | 2.4[SUP]2[/SUP]+ 2.4 + 2
| class=”cms_table_grid_td” | 2.4[SUP]2[/SUP]+ 2.4 + 1
| class=”cms_table_grid_td” | 41
|- class=”cms_table_grid_tr”
| class=”cms_table_grid_td” | …
| class=”cms_table_grid_td” | …
| class=”cms_table_grid_td” | …
|-

It’s not obvious, but this series always terminates (returns to 0) no matter what starting number you choose. But I suggest you don’t try to complete the table above. The length of the sequence for 4 is 3*2^402,653,211 – 2. For 5 it is >A(4) and for 7 >A(8). For 8 it is ~ A[SUP]3[/SUP](3). From 12 you have to switch to an entirely new notation (and incidentally this number is also bigger than Graham’s number). This is an easily-defined sequence whose length (as a function of the starting value) very quickly becomes incredibly huge and continues to grow even more stupefyingly huge. But to make you the unbeatable champion of the biggest number battle, I want to introduce you to TREE(3).

Explaining the TREE function in detail is not incredibly difficult but would make this blog too long, so I’ll just give an abbreviated version. The idea is to build a tree with a single root according to certain rules. The argument to the function defines the maximum number of branches allowed at any node. And you cannot extend the tree in such a way that an upper part of the tree (nearer the root) can be mapped into an embedding on a lower part (this is where I’ll skip details, but they’re really not too hard). It has been shown that for any argument k, there is a maximum possible size for that tree, called TREE(k).

TREE(1) is trivially 1 (just a single branch between root and one child), TREE(2) is easily shown to be 4, but TREE(3), which doesn’t seem like it should be unusual, rockets to a size which makes everything we’ve seen up to this point completely unnoticeable. A very weaklower bound for TREE(3) is A[SUP]A(187,196)[/SUP](1). A(187,196) is already an inconceivably large number. TREE(3) is probably very much bigger than that many recursive nestings of A on the initial argument. Don’t worry about the starting argument of 1 not letting this get off the ground; A(1)=2 so the final number is far, far beyond any intuitive conception. And yet it’s a very weak lower bound for TREE(3). And TREE(3) is still finite.

To summarize:[INDENT=2]TREE(3) >>> A[SUP]A(187,196)[/SUP](1)
A[SUP]A(187,196)[/SUP](1) >>> A[SUP]3[/SUP](3)
A[SUP]3[/SUP](3) >>> Goodstein(4)
Goodstein(4) ~ 3*2[SUP]402,653,211[/SUP]
…which is ~ 10[SUP]100,000,000[/SUP] times bigger than big numbers in the physical world

So now you know how to win the biggest number game. Just say TREE(3). This number is finite (amazingly) and you can describe how it is constructed. You’ll leave your competitors in the dust. If you want to learn more about ridiculously huge numbers, there’s a great YouTube series HERE.

(Of course some opponents will answer TREE(3)+1, slightly more clever opponents will answer TREE(4) or similar, and really clever opponents will apply the recursive nesting trick and reply TREE[SUP]TREE(3)[/SUP](3). So you might want to add a rule that no-one can build on a previous answer.)

More articles by Bernard…