Graham's number - big numbers blow my mind!

One of the most famous big numbers in mathematics is Graham's number. For a while it was the largest number ever used in a legit mathematical proof. That isn't the case anymore but it is still a legend. The number is the upper bound to a problem in Ramsey's theory. To define this number it is recommended that you understand Knuth up arrow notation which I previously wrote about here.

According to Numberphile (linked below)

If you were to try to memorize each digit of Graham's number, your head would sooner turn into a blackhole before you were done. This happens because a blackhole the size of your head stores less information than what it would take to store all of the digits of Graham's number.

How do we define Graham's number?

We will use Knuth's up arrow notation to define Graham's number. It is just too big to use ordinary ones and zeros. We will use iterations of hyperoperations to build levels which will continue until we arrive at the final number^[1]. If you follow along you'll get a glimpse of how infinitely large this number is.

To build Graham's number we start at level 1:

$$ G1 = 3\uparrow\uparrow\uparrow\uparrow 3 $$

G1 is leveraging hyperoperation to generate a massive sequence of numbers. G1 has four up arrows which we call hexation. To give you a sense for how big this number is we can look at the sequence that builds to hexation.

Exponentiation \( 3\uparrow3 \)

No big deal.

\( 3\uparrow3 = 3^3 = 27 \)

Next up is tetration. This is where things start to get interesting.

Tetration \( 3\uparrow\uparrow3 \)

Tetration is a power tower of of exponents. It looks like this: \(3^{3^3}\). If we expand it:

\( 3\uparrow\uparrow3 = 3\uparrow3\uparrow3 = 3^{3^3} = 7,625,597,484,987 \)

Now we are getting a really big number. Next up is pentation:

Pentation \(3\uparrow\uparrow\uparrow3 \)

Pentation is iterated tetration. It is a series of power towers. Expanded it looks like this:

$$ 3\uparrow\uparrow\uparrow3 = \begin{array}{l} \underbrace{3^{3^{3^{⋰^3}}}} \\ \underbrace{3^{3^3}} \\ 3^3 \end{array} \Biggr\rbrace_{} pentation $$

Starting at the bottom each level of the power tower is multiplied out and then becomes the height of the next level. So with pentation what we've got is a massive tower:

$$ 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(7,625,597,484,987) $$

$$
\left.\begin{aligned}
3^{3^{3^{3^{⋰^{3}}}}}
\end{aligned}\right\}
\text{ height = 7,625,597,484,987}
$$

Just take a moment and think about how big this number is. We've already reached a number so big that we can't ever write it down because there isn't enough matter in the Universe. (There is only \(10^{80}\) particles and this number is way bigger. If you were to simply count out loud each 3 in the stack it would take you tens of thousands of years to get through it. Wow.

If we add another arrow we get hexation. As you can imagine from what we saw with three arrows, this is an insanely powerful hyperoperation.

Hexation \(3\uparrow\uparrow\uparrow\uparrow 3 \)

Hexation is an iterated series of pentation operations. The product of the first pentation tower determines how many towers need to be computed for the second. This keeps going until we have this massive number:

$$ 3\uparrow\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow\uparrow(3\uparrow\uparrow(7,625,597,484,987)) $$

which would look something like this:

$$
\underbrace{
\Biggr\{3^3\Biggr\}L1 \rightarrow
\Biggr\{3^{3^3}\Biggr\}L2 \rightarrow \Biggr\{3^{3^{3^{3^{⋰^{3}}}}}\Biggr\}L3 \rightarrow
... \Biggr\{3^{3^{3^{3^{⋰^{3}}}}}\Biggr\}}_{\text{7,625,597,484,987 power towers}}
$$

The result of L1 determines the height of L2. The result of L2 determines the height of L3, etc.. This continues all the way up to L7625597484987. At this point you an insane power tower.

This is also G1.

$$ G1 = 3\uparrow\uparrow\uparrow\uparrow 3 $$

Now that we have G1 we will use it to define the number of up arrows for G2. So the definition of G2 would look like this:

$$ G2 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G1 \text{ up arrows}} $$

Remember that each up arrow we tack on creates a very large increase in the number. You can visualize it like this:

Another up arrow would look like this:

And another would look like this:

Think about that for a second. G1 is a monster of a number. HUGE. To build G2 we input G1 as the number of up arrows. That makes G2 infinitely bigger. But Graham's number still a long way off. Let's create G3:

$$ G3 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G2 \text{ up arrows}} $$

Given that G2 is already a huge monster, now that becomes the input for G3.

This keeps going:

$$ G4 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G3 \text{ up arrows}} $$

$$ G5 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G4 \text{ up arrows}} $$

$$ G6 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G5 \text{ up arrows}} $$

$$ G7 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G6 \text{ up arrows}} $$

... for a while until we finally get to Graham's number which is:

$$ G64 = \underbrace{3\uparrow\uparrow ... \uparrow\uparrow 3}_{G63 \text{ up arrows}} $$

That should give you a little taste for how big Graham's number is.

If you plotted Graham's number on the fast growing hierarchy you would see that it sits somewhere around here:

$$ \text{Graham's Number} < f_{\omega+1}(64) $$

Wow.

There are some good videos on YouTube covering Graham's number. In particular, I love the Videophile segment:

Ramsey Theory

Graham's number is the upper bound to a problem in Ramsey Theory that asks:

Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2n vertices. 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 four coplanar vertices?

In 1971 Ronald Graham and Bruce Less Rothschild proved that this problem has a solution with an upper bound equal to Graham's number. In 2014 the upper bound was proven to be lower:

$$ 2\uparrow\uparrow\uparrow 6 $$

Still a big number but nowhere near as big as Graham's.

In 1980 the Guinness Book of World Records added Graham's number as the largest number ever used in a serious mathematical proof.

What we know about this number

We don't know too much about Graham's number because we can't expand it. There isn't enough matter in the Universe to store all of the digits. We do however know a thing or two about the number.

Graham's number is a power tower of the form \( 3\uparrow\uparrow n \), so its right most decimals must satisfy certain properties. One of these properties is that all towers of a height greater than d have the same sequence of d rightmost decimal digits.

We know that the rightmost 500 digits on Graham's number are:

.....02425950695064738395657479136519351798334535362521430035401260267716226721604198106522631693551887803881448314065252616878509555264605107117200099709291249544378887496062882911725063001303622934916080254594614945788714278323508292421020918258967535604308699380168924988926809951016905591995119502788717830837018340236474548882222161573228010132974509273445945043433009010969280253527518332898844615089404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387

I find it interesting that we can know the first 500 digits of a number that goes beyond our Universe in size.