2.08. Graham's Number

Introduction

Even a brief discussion of large numbers would be incomplete without a mention of the infamous Graham's number. Even though Graham's number does not have so much significance to googology other than how famous it is, it is so well-known, overshadowing bigger, better numbers, that it would be foolish to just overlook it. Even if you have heard of Graham's number, it's likely that you've heard misconceptions about it or modified versions of the story of Graham's number. So in this article I will explain the real story of Graham's number, and correct the many misconceptions surrounding the number.

Who is Ronald Graham?

Before we discuss Graham's number, we'll first go over who exactly the namesake of Graham's number (Ronald Graham) is. This will help us get a bit of background on Graham's number and its whole story.

Ronald Graham is an American mathematician (born 1935), who, according to Wikipedia^[1], has done important work in fields such as scheduling theory, computational geometry, quasi-randomness, and Ramsey theory, the last of which is the field Graham's number came from. He is quite a prolific writer, having published about 320 papers and five books. Unusually for a mathematician, he is also known for being a world-class juggler, and at one time he was the president of the International Jugglers' Association. He has gotten several awards in mathematics as well. Suffice to say that Graham is not only a prolific mathematician but also an unusual individual.

But on the other hand, Sbiis Saibian has described Graham as "quite modest, approachable, and friendly in interviews"^[2]. That suggests that Graham is perhaps not as much of the stereotypical "uptight mathematician" as you may think! As we will see later, Graham is quite humble about the number he made, and his view on it is, interestingly, reminiscent of googologists!

UPDATE: In July 2020, Ronald Graham passed away. I'd feel a bit strange editing this article to describe him in past tense, since I wrote most of it in 2015 and did mostly only minor edits since. Although Ronald Graham may be deceased, it's safe to say his impact on the field of mathematics won't be forgotten anytime soon.

The Myth of Graham's Number

The story of Graham's number often goes something like this:

Mathematician Ronald Graham was working on a problem in Ramsey theory in 1977, where he proved a surprisingly huge number to be an upper-bound to that solution. The number Graham found captured the attention of math writer Martin Gardner, who published it and shared the number with the world. Graham's number made it to 1980 in Guinness World Records as the largest number used in a mathematical proof, and it's still the largest number to have any use in mathematics to this day.*

* Although nowadays, it's getting more and more common to note that Graham's number is no longer the record holder.

Much of that story is actually inaccurate. For one thing, the original paper was in 1971 which proved a smaller number than what is now known as Graham's number to be an upper-bound, and the things that happened in 1977 with the number we now know as Graham's number were very different in purpose! Also, today Graham's number is no longer anywhere close to being the largest number that has been used in a mathematical proof! Are you confused? That's OK, we're going to examine the history of Graham's number in a lot of detail. But first, we'll first get some background on Graham's number by learning about the field of mathematics where Graham's number came from: Ramsey theory.

Ramsey Theory

What is Ramsey Theory?

Ramsey theory is a field of mathematics named after the short-lived British mathematician Frank P. Ramsey^[3]. He died when he was only 26 years old, but he made some major contributions to mathematics. Although he did not exactly "create" Ramsey theory, he proved a theorem called Ramsey's theorem, which can be considered the foundation of Ramsey theory. Ramsey's theorem is relevant to the origin of Graham's number, but before we discuss it, we need to know what Ramsey theory is.

Ramsey can be concisely described as the field of mathematics that deals with the minimal conditions in which certain forms must necessarily arise. Here is a very simple example (given by Sbiis Saibian in his Graham's number article^[2]) of a Ramsey theory problem:

Suppose you have a gumball machine with red and blue gumballs. What is the minimum number of gumballs you need to buy to ensure that at least two gumballs will be the same color?

You may think the answer is two, but if you buy two gumballs, there might be one red and one blue, meaning that there wolud not be two of the same color. However, with three gumballs, the color combinations are:

red/red/red

red/red/blue

red/blue/red

red/blue/blue

blue/red/red

blue/red/blue

blue/blue/red

blue/blue/blue

and all of those combinations have at least two of the same color. Therefore the answer to the problem is three.

So that's just a very simple example of the kind of problem that people work with in Ramsey theory. Of course, other problems, such as Graham's problem, are a lot harder. In fact, Ramsey theory problems are famously difficult to solve, and Graham's problem is a great example.

NOTE: If you're reading this, you might be thinking, "why are we learning about Ramsey theory and Graham's problem, isn't it just some boring math?" Many online articles on Graham's number don't bother explaining Graham's problem, largely due to the common impression that it's something really complicated, which is not true. Even if it was really complicated, an explanation of Graham's number wouldn't be complete without at least giving the gist of its context. That said, let's move on to learning about Ramsey's theorem and how it relates to Graham's problem.

Ramsey's Theorem

Before we learn about Ramsey's theorem, we'll need to know what a complete graph is. A complete graph is simply a set of n points, with every pair of points connected with a line. A complete graph of n vertices is often denoted K_n, which is a nice compact notation we'll use from now on.

To make a K_n, you take a set of n points, and connect every single pair of points with a line. For example, to make a K₄, you start with four points:

. .

Then, you connect each pair of points to get the K₄:

____

|\ /|

| X |

|/_\|

I think you get the general idea. For a bit more understanding here's what a K_n looks like for n = 1 to n = 12 (image taken from source ^[2]):

A notable property of all complete graphs is that if you focus on any number of points in a complete graph, those points will themselves form a complete graph. To see what this means, focus on any four points of a K₅ and you will see that they form a K₄ complete graph. Those complete graphs found within complete graphs are called complete subgraphs.

Now Ramsey's theorem involves coloring the lines of a complete graph one of two colors, let's say red or blue. This is called two-coloring a complete graph. For example, here's one way to two-color a K₅:

Ramsey's theorem states that for any x and y, for a sufficiently large K_n all two-colorings of the graph will have a red complete subgraph of x vertices and/or a blue complete subgraph of y vertices.

This is a bit of a mouthful. Ramsey's theorem can also be explained with a function R(x,y). R(x,y) is the smallest number n such that all two-colorings of a K_n will have a red complete subgraph of x vertices and/or a blue complete subgraph of y vertices. As a consequence of Ramsey's theorem, R(x,y) is well-defined for all positive integers x and y.

All the numbers of the form R(x,y) are known as Ramsey numbers. To get a better idea of what they are, we'll look at an example Ramsey number, R(3,3).

Example of Ramsey's Theorem: R(3,3)

To find what R(3,3) is, we need to take a K_n and consider all the ways to two-color it (color its lines red and blue). If all ways to color the K_n have a red K₃ and/or a blue K₃, and that is not true for any smaller complete graph, then n is the value of R(3,3).

So what is R(3,3)? We know that it can't be 1, 2, or 3, since it's not possible to color a K₁ or K₂ such that we have a monochromatic K₃ (a monochromatic complete graph is one where all its lines are the same color) because there aren't enough vertices, and not all colorings of a K₃ will themselves have a monochromatic K₃ of course. For example, you can color one of the K₃'s lines red and the other two blue.

By counterexample we can show that it isn't 4 or 5. Take this two-colored K₄:

and this two-colored K₅:

Neither of those have a monochromatic K₃ subgraph; to see why, focus on any three corners in them, and you'll find that no three corners will form a complete graph where all the lines are the same color.

Can we find a counterexample to show that R(3,3) is more than 6? You might try doing what we did above (coloring the edges blue and the other lines red), and that would give us:

This K₆ does have a monochromatic K₃ subgraph. In fact, it has two. The top left, right, and bottom left corners form a red K₃, as do the top right, bottom right, and left corners. In fact, every way to two-color a K₆ will have at least one red or blue K₃ subgraph^[4]. This means that R(3,3) is equal to 6.

Other Ramsey Numbers

Now that we've gone through an example of Ramsey numbers, let's look at the other Ramsey numbers now.

Very few of the Ramsey numbers have their exact value known, not counting the trivial cases, which are:

R(1,y) = 1

R(2,y) = y

Additionally R(y,1) = 1 and R(y,2) = y, since R(x,y) is always equal to R(y,x). This is because R(x,y) is just R(y,x) with the colors swapped, and swapping colors doesn't make a difference here any more than changing the colors from red and blue to green and orange does.

As of this writing, the only known non-trivial Ramsey numbers (not counting R(x,y) and R(y,x) as distinct) are^[4]:

R(3,3) = 6

R(3,4) = 9

R(3,5) = 14

R(3,6) = 18

R(3,7) = 23

R(3,8) = 28

R(3,9) = 36

R(4,4) = 18

R(4,5) = 25

That's it, only nine known non-trivial Ramsey numbers. The rest only have known lower and upper bounds: for example, R(5,5) is known to be between 43 and 48 inclusive, and R(7,7) is known to be between 205 and 540 inclusive^[4].

Now, you may be asking yourself: wouldn't it be possible for a computer to iterate through every coloring of a K₄₃ complete graph and see whether all of them have a red K₅ or blue K₅? 43 isn't a very big number, is it? Well, the bad news is, the number of ways to color a K₄₃ with two colors is quite a staggering number. It's not nearly as big as some of the numbers we've gone through in previous articles, but it's still far too big for even a supercomputer to iterate through. The number of lines in a K₄₃ is the 42nd triangular number: (42 + 43) / 2 = 903. Then, the number of two-colorings of the graph is 2 to the 903rd power, which is equal to approximately 6.76216999854 * 10²⁷¹. This 272-digit number is more than a googol squared, and we've already established long ago that a googol is more than even the estimated number of atoms in the observable universe. Although some of the colorings are effectively equivalent to each other by swapping colors or rotating the graph or swapping locations of points, there are still far too many for computers to be able to iterate through them all. An immense amount of mathematical research needs to be done to prove the values of Ramsey numbers this big, and I won't go over what sort of research is needed in this article. Not until 2017 was R(5,5) proven to be at most 48! When I had initially written this article, it was known to be at most 49.

Hopefully, you now have an idea of how deceptively challenging it is to prove problems in Ramsey theory. As such, we are now ready to move on to Graham's problem.

Graham's Problem

Graham's number, which I described briefly in the previous article, is very huge by any reasonable standard, so huge that its size easily blows people's minds. It blasts way past the googol and googolplex and anything you can express with power towers—which themselves easily blast through the roof of most people's conception of infinity at light speed—but even those are nowhere close to Graham's number. With its magnitude that easily impresses the layman, Graham's number gives people the impression that it must have arrived from some incredibly complicated field of mathematics which no layman could hope to understand. When people write online articles about Graham's number, they often do not bother explaining what exactly Graham's problem is, due to that impression. They instead usually say that it's something too complicated for them to be able to explain.

Is that true, is Graham's problem really something from the strange cryptic corners of mathematics nobody without eleven PhDs in mathematics could have any hope of understanding? Nope, not at all. In this article I will prove those people wrong. Believe it or not, Graham's problem isn't esoteric at all; it's easier to understand than the number itself! Wait, how can that be?! That's the beauty of mathematics, complicated and intricate things arising from elementary concepts. So without further ado, let's examine Graham's problem.

Here is the problem (wording taken from Sbiis Saibian's site but reworded for clarity):

What is the minimum number of dimensions of a n-dimensional hypercube, where all vertex pairs form lines that all are colored with one of two colors, such that there must exist a monochromatic complete graph of four coplanar vertices?^[2][5]

Woah now, that does indeed sound pretty complicated! But trust me, it's not. Let's look at the problem a little further to understand what it means. To gain an understanding of the problem, we first need to know what hypercubes are (if you're familiar with them you can skip this next subheading).

Hypercubes

Many people are familiar with hypercubes, analogizing the cube to the mind-wrenching world of higher dimensions. If you aren't familiar with them, here's a quick rundown.

First consider that a point is 0 dimensions, which looks like this:

A line is 1 dimension, which looks like this:

_____

A square is 2 dimensions, which looks like this:

_____

| |

|____|

And a cube is 3 dimensions, which looks like this:

_____

/| /|

/_|__/ |

| |_|__/

| / | /

|/___|/

How would we work with 4 or more dimensions? 4 dimensions and beyond don't actually exist in the physical world like the familiar three dimensions do (unless you consider things like time as a fourth dimension), but if we allow there to be a fourth axis besides the three needed to form a cube, we can imagine there being a fourth dimension. A tesseract (name comes from Greek tessera meaning four), which is the 4-dimensional version of a cube, would look something like this:

Note of passing interest: Jonathan Bowers, who is known for pioneering work in googology and his array notation, is also known for his work with higher dimensions, having discovered many 4-, 5-, and even higher dimensional figures with special properties. In fact, Bowers considers multidimensional shapes his "primary interest" and large numbers only one of his secondary areas of interest^[6]!

Why exactly does a tesseract look like that? Let's go back a few dimensions and consider how we can get to a square from a line.

First we took the 1-dimensional line:

_____

then we made a copy by moving it perpendicular to itself:

_____

and finally we connected the endpoints:

_____

| |

|____|

Likewise, to get to a cube from a square, we take the square, and move it across an axis perpendicular to the plane the square lies in. But to get that axis, we need to move from the second dimension up to the third dimension. Once we have that we connect the corresponding corners of the two squares, to get a cube:

_____

/| /|

/_|__/ |

| |_|__/

| / | /

|/___|/

So to get to a tesseract from a cube, we need to go up to the fourth dimension. You'll need to imagine an axis through which we can translate the cube, and then connect the vertices of both cubes. With that we can get from a cube to a tesseract:

You can imagine the red lines as the first cube, the blue lines as the second translated cube, and the gray lines as the lines connecting the two.

By going up to even higher dimensions, we can get to the 5-dimensional version of a cube (known as a 5-cube or as I prefer a penteract from Greek "pente" meaning five):

and the 6-dimensional version of a cube (6-cube or as I prefer a hexeract from Greek hexa- meaning 6):

and so on.

Now these hypercubes (hypercube refers to a cube of any number of dimensions) are now getting quite complicated! Although they definitely require more than a little imagination, hopefully you now understand the concept of hypercubes. That said, we can now move on to Graham's problem itself.

Graham's Problem

Consider a hypercube with a number of dimensions N (for example, if N is 4 then the hypercube is a tesseract). Now, you connect each vertex pair of that hypercube with a line. This is the same thing we did to get a complete graph from a set of points.

For example, when you take a cube (3 dimensions) and connect all the vertex pairs, you end up with this:

Next, we color all those lines in the hypercube one of two colors, let's say red or blue. Here's one way we can do that for a cube (3 dimensions):

Now what are we looking for in these colorings? We are looking for the smallest number of dimensions of the hypercube such that all possible colorings we can make that way will contain a monochromatic K₄ with four coplanar vertices. In other words, we are looking for the smallest number of dimensions of a hypercube where all colorings will have at least one occurrence of

____

|\ /|

| X |

|/_\|

____

|\ /|

| X |

|/_\|

where all vertices of the K₄ lie in the same plane.

Now how does this connect to the Ramsey numbers? This problem is closely related to finding R(4,4), but it has some differences. To find R(4,4), you just need to find the lowest complete graph that matches the aforementioned conditions, and the requirement that the vertices lie in the same plane is irrelevant. But with Graham's number, we are working with a complete graph formed from a hypercube, and we have the requirement that the four vertices lie in the same plane. This condition makes Graham's problem particularly difficult to solve.

And that's the problem where Graham's number came up. How hard was that? I told you it wouldn't be something confusing and complicated like so many people think! But you may be able to tell that although Graham's problem is pretty easy to explain, it definitely isn't an easy problem to answer. That is where Ronald Graham comes in to find an upper-bound to the solution.

Graham's Proof

Ronald Graham and another mathematician named Bruce Rothschild (pronounced /roat-shild/), who, like Graham, is known for contributions to Ramsey theory, published a Ramsey theory paper in 1971^[7] where they found (among other things) an upper-bound to the solution of the problem I discussed.

Now it's important to note that contrary to popular belief, this problem was not the main focus of the paper. It was used merely as an illustration of one of the corollaries in the paper (Corollary 12), more specifically to illustrate just how hard it is to find an exact value of a case of Corollary 12. This is shown in the paragraph towards the end of the paper:

We point out that even though the techniques of the proof are constructive so that upper bounds on the various N's of the corollaries are given, these bounds are usually enormous, to say the least. To illustrate this, we consider the first nontrivial case of Corollary 12, the determination of an upper bound on N(1, 2, 2). We recall that by definition N(1, 2, 2) is an integer such that if N ≥ N(1, 2, 2) and the (²ⁿ₂) straight line segments joining all possible pairs of vertices of a unit n-cube are arbitrarily 2-colored, then there always exists a set of four coplanar vertices which determines six line segments of the same color. Let N* denote the least possible value N(1, 2, 2) can assume. We introduce a calibration function F(m, n) with which we may compare our estimate of N*. This is defined recursively as follows:

F(1, n) = 2ⁿ, F(m, 2) = 4, m ≥ 1, n ≥ 2,

F(m, n) = F(m - 1, F(m, n - 1)), m ≥ 2, n ≥ 3

It is recommended that the reader calculate a few small values of F to get a feeling for its rate of growth, e.g., F(5, 5) or F(10, 3).

If the bounds generated by the recursive functions needed for the proof of Corollary 12 are explicitly tabulated, the best estimate for N* we obtain this way is roughly

N* ≤ F(F(F(F(F(F(F(12, 3), 3), 3), 3), 3), 3), 3)

On the other hand, it is only known that N* ≥ 6. Clearly, there is room for improvement here.

—Graham and Rothschild, 1971

When you look at it that way—note the words that I colored red—it seems weird to call the problem with hypercubes and monochromatic K₄'s "Graham's problem". Graham's problem was not so much a problem that a paper intends to solve as it was an illustration of a very weak upper-bounding scheme.

So what about that number shown at the end of the paragraph, the upper-bound for N* (the solution to the "problem")?

The two-argument F function used to define the number is similar to the Ackermann function, which we looked at a few articles ago. It translates to up-arrows more nicely than the Ackermann function does. F(a,b) translates into up-arrows as 2^^ab (see source ^[2] for proof of this). We saw earlier how up-arrows work, but to recap they are defined like so:

x^^y = x^x^x ... ^x with y x's

x^^^y = x^^x^^x ... ^^x with y x's

x^^^^y = x^^^x^^^x ... ^^^x with y x's

etc.

(you must solve these expressions right to left)

Therefore Graham and Rothschild's upper-bound is equal to:

2^^^ ... ... ... ^^^3

w/ 2^^^ ... ... ... ^^^3 ^s

w/ 2^^^^^^^^^^^^3 ^s

Wait a minute, this isn't Graham's number! That's a whole different smaller number, what's up with that? This is the most curious part of the tale of Graham's number, though I'll discuss that a bit later.

Sbiis Saibian gives this number, the original Graham's number, the name "Little Graham" to avoid confusion with Graham's number^[2]. Robert Munafo, on the other hand, calls this number the Graham-Rothschild number^[8]. In any case, Graham showed that the solution to the problem is somewhere between 6 and Little Graham, inclusive.

How big is Little Graham?

We now know about the original genuine Little Graham, so now we can get a feel of how big this number is:

First, just consider F(12,3). That's equal to 2^^^^^^^^^^^^3 in up-arrows. This is far bigger than the mega and megiston we encountered earlier, bigger than 4^^^^4, 5^^^^^5, 6^^^^^^6 (the largest number I visually represented in my up-arrow article), and even bigger than 10^¹⁰10, the horrifyingly gigantic tridecal. That's already a SUPER-HYPER-FREAKY-INTENSE-SCARY number, but it's tiny in comparison to the monster:

F(F(12,3),3)

That's 2^^{2^^^^^^^^^^^^3}3, aka 2^^^ ... ... ... ^^^3 with 2^^^^^^^^^^^^3 ^s! We saw how much of an increase adding one up-arrow was, so how can we even comprehend getting an unfathomable number of up-arrows? While the Moser uses approximately a mega up-arrows, this number uses 2^¹²3 up-arrows, an UNFATHOMABLY bigger number of up-arrows, and therefore an undescribably bigger number.

But remember the first law of googology: it only gets worse. Consider F(F(F(12,3),3),3) now: that's 2^^{2^}^{2^^^^^^^^^^^^3}³3, which you can imagine as:

2^^^ ... ... ... ^^^3

w/ 2^^^ ... ... ... ^^^3 ^s

w/ 2^^^^^^^^^^^^3 ^'s

And the next number, F(F(F(F(12,3),3),3),3) is:

2^^^ ... ... ... ^^^3

w/ 2^^^ ... ... ... ^^^3 ^s

w/ 2^^^^^^^^^^^^3 ^'s

... and so on ...

The number Graham and Rothschild proved to be an upper-bound to the problem is equal to:

2^^^ ... ... ... ^^^3

w/ 2^^^ ... ... ... ^^^3 ^s

w/ 2^^^^^^^^^^^^3 ^s

Another way to think of it is with a g-function defined as g(1) = 2^¹²3, g(x) = 2^^g(x-1)3, and have Little Graham be g(7). Then we can think of how hard it is to get your head around Little Graham.

g(1) is "only" twelve up-arrows, so we can sort of imagine the feeding-in of the number of up-arrows to get g(2) and maybe g(3). But once we reach g(4), the iteration is tricky to get straight, and g(5) and beyond have so many iterations that it's virtually impossible to get all the iteration in your head. So Little Graham is already a mind-bogglingly huge number! In fact, Ronald Graham admits that the number is too large, as indicated by his amusing remark, "Clearly, there is room for improvement here."

Now now we know what Little Graham is, how it came to be, and how big it is. But what about the number usually described as Graham's number? This is what we'll look at next.

The New Graham's Number

Six years after Graham and Rothschild's paper, enter a figure named Martin Gardner. Gardner, according to Wikipedia^[9], was a popular mathematics and popular science writer, who was also interested in philosophy, religion, myth debunking, and literature. He was born 1914 and died at the age of 95 in 2010. He was an extremely prolific writer, having shared interesting things in science and mathematics in very many different magazines, and he published over a hundred books in his lifetime!

In 1977 Gardner found out about Graham and Rothschild's paper, and was fascinated by the size of the number proved as an upper-bound. He was quick to declare that number the largest number used in a mathematical proof (at that time he was probably right), and so he wanted to share that gigantic number with the world. However, he found the number rather tricky to explain. So Gardner and Graham devised a larger but easier-to-explain number to share with the world. That number is the number now known as Graham's number, but Robert Munafo prefers calling it the Graham-Gardner number^[8] since, really, Gardner is to whom this number is attributable.

The Graham-Gardner number, the number Graham's number now refers to, is defined as:

G₆₄ where G₁ = 3^^^^3 and when x > 1, G_x = 3^^G_x3

Note: the G_n notation was not used by Martin Gardner himself in the article where he introduced Graham's number, but it has later become the standard notation for expressing Graham's number.

Graham's number can be visualized as:

3^^^ ... ... ... ^^^3

: : :

3^^^ ... ... ... ^^^3

3^^^^3

with 64 layers

Gardner published this number in Scientific American in a November 1977 article^[10], where he discussed several problems in Ramsey theory (including Graham's problem and some closely-related problems) and large numbers that arose from those problems. He first discussed a few other problems in Ramsey theory and then the context of Graham's problem, and after that the size of Graham's number.

Now that we know how the number we know as Graham's number came to be, we are now ready to try to get a hold of its size. That is by far the most popular thing about Graham's number, with its magnitude that easily blows the mind of basically anyone who is not a googologist. If you see an article about Graham's number and it only bothers explaining one thing about it, it'll be the size of the number.

The most common way to explain the size of Graham's number goes something like this:

3^3 = 3 to the power of 3, which is 27. Nothing very big or complicated.

3^^3 = 3^(3^3) = 3^27, equal to 7,625,597,484,987, or 7.6 trillion. That's way bigger than previous, and certainly not something that we can easily wrap our head around, but still easy to write out in full.

3^^^3 = 3^^(3^^3) = 3^^(7,625,597,484,987) = 3^3^3^3^3^3^3 ... ... ... 3^3^3^3^3 with 7,625,597,484,987 threes. Unlike the previous number, this is incredibly big, as just the top five threes in this tower of 3's already create a number bigger than a googolplex. Then imagine how big the whole tower of 7.6 trillion threes is!

3^^^^3 = 3^^^(3^^^3), which is incredibly bigger than 3^^^3. It evaluates to (((...(((3^^3)^^3)^^3) ... ^^3), where there are 3^^^3 3's. To get an idea of this number's size we need to use an idea of stages. Stage 1 is just 3, stage 2 is 3^3^3 = 7,625,597,484,987, but stage 3 is a huge step up with 3^3^3^3......^3 with 7,625,597,484,987 3's: the utterly unfathomable number we encountered previously, unimaginably bigger than a googolplex! Stage 4, however, is much worse, being 3^3^3^3......^3 with stage 3 3's. Continue to stage 5, stage 6, stage 7 ... stage 100, stage 1000, the millionth, billionth, trillionth stage ... the googolth stage, the googolplexth stage ... until you get to the stage 3'th stage! That's a HUGE number!

And that number, 3^^^^3, is G₁. But G₁ is just the number of up-arrows in G₂, which is equal to 3^^^... ... ...^^^3 with 3^^^^3 ^'s: an utterly incredible number! Likewise, G₃ is 3^^^... ... ... ... ...^^^3 with G₂ ^s, and G₄ has G₃ ^s/ Continue with G₅, G₆, and so on ... G₆₄ is the number we're talking about here! Mind-blowing!!!

As you can see, that number is far easier to explain than Little Graham, and in an unpublished 1977 paper (remember that it's later than the paper where Little Graham was introduced!) Graham proved this number to be an upper-bound. But still, Graham did that proof only because of the larger number Gardner devised. Therefore, the number we now know as Graham's number is more attributable to Gardner than to Graham!

Nonetheless, Graham's number is a decently believable number, considering its usage of 64, which itself has relevance to Graham's problems since it is the number of ways to color all the lines in a K₄ red or blue. However, if you think about it, basing Graham's number on 3's is a lot less natural than basing it on 2's (as in Little Graham), because the problem deals with coloring a cube with two colors and not three or anything like that! Most people would not even notice that peculiarity; I myself only noticed it when I really thought about it and skimmed Graham and Rothschild's paper. This goes to show how little effort is needed to make a "believable" number. If you think about it, Graham's number almost looks like it was designed to be just the right balance between easy to explain and mind-blowingly big.

The number Gardner devised is now usually considered to be the real Graham's number (rather than Little Graham), and the number even made it to Guinness World Records as the largest number used in a mathematical proof in 1980^[2]! As I will discuss in a little bit, it's no longer even close to being the largest number in a mathematical proof, though many people think it is, much to the chagrin of googologists.

Gardner's number is not quite the end of the story. There's yet another particularly mysterious version of the number ...

The Graham-Conway Number

Now let's switch focus to John Conway and Richard K. Guy's Book of Numbers. It is a 1996 book about recreational mathematics of all sorts, the same book which introduces Conway and Guy's illion system. Here, we'll be focusing on four pages of the book, pages 59 through 62. Those pages are a section titled "Some Very Large Numbers". Those pages are short, but LEGENDARY. In only four pages, Conway describes Knuth's up-arrows, the so-called Ackermann numbers, his own extension to up-arrows called chained arrow notation (we'll discuss it in the next article), Skewes' number, and Graham's number itself. I think the length of this section gives a pretty good indication of how little attention mathematicians give to very large numbers. But by mathematicians' standards, Conway's coverage of large numbers is quite generous.

Conway describes Graham's number as so:

4^^^^...^^^^4 where the number of arrows is...

...

4^^^^...^^^^4 where the number of arrows is...

4^^^^4

where there are 64 lines (including 4^^^^4)

Robert Munafo calls this version of Graham's number the Graham-Conway number^[8].

Suddenly Graham's number is defined with 4's now—what is that all about? Isn't Graham's number defined using threes and not fours? It is often believed that the fours are just a typo, but then again, doesn't using fours make a lot more sense than using 3's? Robert Munafo says that Conway's version of Graham's number has a particular elegance, since it's entirely based on fours, starting with 4^^^^4 (note the four arrows) and having 64 (4*4*4) layers. Plus, using fours matches better with things relating to the hypercubes like the K₄'s! To me, this number is certainly the most elegant of Graham's numbers, and less artificial than Gardner's version (albeit definitely more artificial than Little Graham). But still, the usage of fours in contrast with the usual threes is something unusual, especially since the book was published 20 years after the Graham-Gardner number, when the threes version had already become the most prevalent.

What's even weirder is that Conway bounds Graham's number with his chained arrow notation in terms of threes. He says:

3->3->64->2 < Graham's number < 3->3->65->2

That's weird. Either the threes are a mistake, or the fours are? It's quite hard to say.

For a while people could only believe Conway's version of Graham's number was simply an erroneous version that doesn't really matter much ... until a large number enthusiast and amateur mathematician who identifies online by the pseudonym "Sbiis Saibian" got an opportunity to speak with Conway himself about the number^[2]!

It was in 2012, where Conway was giving a casual lecture on surreal numbers in Sbiis Saibian's college campus. Since Conway, being the inventor of chained arrows, is a relevant figure to googology, Saibian took the opportunity to attend the lecture, and meet Conway in person. He notes that it was a rather low-key event, which was both relieving and an indicator of how little attention the public gives to mathematics.

The moment of truth came after the lecture, when people got turns to speak with Conway. When Sbiis Saibian got his turn, he first asked Conway if he was the inventor of chain arrows, and he confirmed this. Then, he asked Conway about his version of Graham's number. Conway told him that "Ronald Graham had originally used fours". Sbiis said "really?", and Conway said "yes ... well it doesn't really matter". By this Conway meant that the numbers have almost no difference. But still ... they are definitely different integers ... VERY DISTINCT INTEGERS. In fact, the real difference between the numbers is impossible to appreciate, especially since you start with 4^^^^4, which as we saw in the up-arrow article, is far larger than 3^^^^3. On the other hand, you can clearly say that Graham's number and Conway's version are constructed similarly, and googologically they are definitely in the same neighborhood of numbers. Of course, what I said doesn't matter so much for our purposes, and let's continue with Sbiis Saibian's conversation with Conway.

The conversation continued with Saibian asking Conway if he knew of the work of Jonathan Bowers. Conway said no, but he seemed interested, and so Saibian briefly explained that Bowers created a notation that was on par with the fast-growing hierarchy (we'll examine both of those in section 3 and later). Conway was in a hurry to go, but he made a closing remark to Saibian: "I have nothing against amateurs working in mathematics". To him, that was an endorsement to amateur mathematicians (and googologists!) that it's OK for them to explore the world of mathematics.

This brief yet significant conversation gave us a new clue about Conway's version of Graham's number. It wasn't a typo at all, but rather the "original version". So Conway's 4-based variant of Graham's number is more significant than we originally thought. But how? This additional hint opens up a whole new world of questions, changing Conway's version of Graham's number from merely being thought of as an error to a strange mystery. What did Conway mean with "Graham had originally used fours"? He could not have referred to the original proof with Rothschild, since that number was quite different from either Gardner's or Conway's version. Perhaps it was suggested that Graham's number, the one Gardner devised, used fours but they changed it to threes? I suspect that Graham used fours in his 1977 proof (the one with the Graham-Gardner number), before editing it to use threes instead. But even that theory is uncertain since Graham kind of had a choice to use threes or fours or whatever else when proving the larger relative of Little Graham as the upper-bound.

There are so many mysteries and theories about the Graham-Conway number to juggle that it's almost more satisfying to believe it was just an error ... or is it? Actually not. Because it clearly was more than just an error, and it's always better in my opinion to know the truth than to believe information that is false, knowingly or not ... it is more satisfying to be mystified by the truth than satisfied by believing a false yet plausible statement, because knowing truth is part of the goal of mathematics, and science, and everything ...

Before we get carried away with philosophical discussion, let's review and think back to the other two Graham's numbers. Now we're well aware that there's not just one Graham's number, but actually three different Graham's numbers! There's the original authentic Graham's number, used as the real serious "purposeful" Graham's number. Then there's Gardner's version, used as a device to popularize the math of Graham's number. Then there's Conway's version, once believed to be an error, but with an additional clue now turned into a particular mystery.

Graham's Numbers Today

How have Graham's numbers changed from what they were in 1977? Are 6 and Little Graham still the best-known bounds for Graham's problem? Is Graham's number (really Little Graham) still the largest number used in a mathematical proof? In this section we'll find out.

Improved bounds to the solution of Graham's problem

First off, we now do indeed have a better lower bound for the solution to Graham's problem than just 6. Even though in 1977 mathematicians believed the solution to be 6 (and known to be no greater than Little Graham), the lower bound was raised to 11 in 2003, and then to 13 in 2008^[5]. So is the solution now known to be between 13 and Little Graham? Actually, recently the upper-bound has been improved.

It is difficult to find what the next upper-bound to be found after Little Graham was, since there are many (some disputable) sources. One improved upper-bound was from a Googology Wiki user by the name of Deedlit11 in March 2013^[11], equal to 2^^^2^^^262,153. Note that this number is somewhat larger than G₁ but far less than G₂, let alone Little Graham or Graham's number. There has been talk of other better upper-bounds on Wikipedia (for example look here, here, and here), but many of these have not been recognized, largely since Wikipedia has strict standards on what mathematical proofs, or sources of any sort for that matter, are reliable enough for their standards.

Fortunately, now we know for sure of a bound that is now recognized on Wikipedia's page on Graham's number^[5] That bound was proven by Mikhail Lavrov, Mitchell Lee, and John Mackey in an online published paper^[12] in April 2013, titled "Graham's number is less than 2^^^6" (in the title Graham's number refers to the solution of Graham's problem). The number they proved to be a bound is 2^^2^^2^^9 in terms of Knuth's up-arrows. It can be visualized using power towers as:

2^2^2^2 ... ... ...^2

w/ 2^2^2^2 ... ... ...^2 2's

w/ 2^2^2^2^2^65,536 2's

That's still quite a big pentational number, but it's not even close to as big as G₁. In terms of pentation and threes it falls somewhere between 3^^^4 (that's a power tower of "a power tower of 3^27 threes" threes) and 3^^^5 (that's a power tower of 3^^^4 threes). I should point out that the 2013 bound is quite a liberal bound, but it still works quite well as one.

So now we can say that the solution to Graham's problem is at least 13, but less than 2^^2^^2^^9.

Now for our next question: Is Graham's number still the largest number used in a mathematical proof?

Is Graham's number still the "record holder"?

Zillions and zillions and zillions of people think that Graham's number is to this day the largest number ever used in serious mathematics, so it's got to be the largest, right? ABSOLUTELY NOT!

The best-known example of a number bigger than Graham's number that was used in a mathematical proof is a number known as TREE(3). It's a number that was discovered by a mathematician by the name of Harvey Friedman, who has studied fast-growing sequences in mathematics that lead to some VERY large numbers. I have met Harvey Friedman in person before. At the time, I was in fourth grade and I was invited to some sort of math conference at a nearby university. I remember it quite well, and to this day in my bedroom I have a picture of fourth-grade me, Harvey Friedman, and the university's president at the time, with both of their signatures.

What is TREE(3)? It's the answer to the problem:

What is the longest possible length of a sequence of 3-labeled trees such that no tree is homeomorphically embeddable into a later tree?

Here, 3-labeled trees refer to graphs of connected dots with three colors. Homeomorphically embeddable is more advanced of a concept (which I can't really explain briefly here), but hopefully you get the idea that it's a pretty simple problem.

But there's a huge difference between this problem and Graham's problem: unlike the solution to Graham's problem, TREE(3) is not an upper-bound. It is known to be indeed be extremely huge, meaning that it won't collapse like the solution to Graham's problem! TREE(3) is so enormous that it would laugh at Graham's number. It would laugh just as hard at things like G_G₆₄, or even things like G_G_G_G_G...64 with Graham's number of G's. I'm not kidding, that kind of thing can't take you anywhere close to TREE(3)! Even anything you could write out even in John Conway's chained arrow notation wouldn't hold a candle to this monster!

A lower bound for TREE(3) is f_{ψ(Ω^(Ω^w*w))}(3), using the fast-growing hierarchy. Graham's number, by contrast, is only about f_w+1(64). It's OK if TREE(3)'s bound looks complicated. That makes the point that notations powerful enough to express TREE(3) are very complicated, and unlike with Graham's number it's quite difficult to devise a number that's bigger than TREE(3). We'll only get to numbers as big as TREE(3) much later, while exploring some MUCH more complicated numbers with far more advanced recursion ...

Incredibly, TREE(3) is still not the largest number used in serious mathematics. There's a still bigger number discovered by Harvey Friedman known as SCG(13), and his finite promise games can take us even further, saying nothing of the legendary busy beaver function and the vast numbers it can generate. Nowadays the question of "what is the largest number used in a mathematical proof?" is no longer easy to answer, with the variety of large numbers that have cropped up in serious mathematics that make the endlessly praised "record holder" Graham's number look trivial!!!

In my opinion more people should hear of numbers like TREE(3) and SCG(13). They are numbers that are both more significant to mathematics than Graham's number and larger than Graham's number. But the one bad thing about those—perhaps why they aren't as publicly known—is that they aren't as easy to explain as Graham's number, both with their context and their size. Therefore, Graham's number's popularity is not entirely a bad thing. It easily draws people to the wonderful world of googology. In that sense Graham's number can be seen as an eye-opener, something fairly basic to spark one's interest in very large numbers.

The Digits of Graham's Number

Before we conclude this article, let's have a bit of fun here and discuss something that might sound completely unknowable for a number so huge: its digits.

The Last Digits of Graham's Number

The last digits of Graham's number, amazingly enough, are something that's possible to calculate! It's all thanks to the fact that Graham's number is a very, very, very large power tower of threes. While there's complex modular arithmetic involved in calculating those last digits, I'll walk you through how to deduce the very last digit of Graham's number. What could that last digit be? Is it 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9?

How exactly is it possible to know the digits that end Graham's number? One thing is obvious right away: since Graham's number is a very, very, very large power of three, it is an odd number, meaning its last digit must be 1, 3, 5, 7, or 9. We've eliminated half the possibilities already, but there's more we can find out based on the fact that it is a power of three.

The last digits of the powers of three follow a cyclical pattern as you go through them. If you look at the last digits of the numbers 3, 9, 27, 81, 243, 729, 2187, and 6561, there's a pattern you may notice: the last digits cycle between 3, 9, 7, and 1. This eliminates 5, narrowing the last digit of Graham's number down to four possibilities. In fact, we know the following about the last digit of powers of three: for any number 3^x, you can calculate its last digit through the remainder of dividing x by 4. If x mod 4 = 0, the last digit is 1; if x mod 4 = 1, the last digit is 3; if x mod 4 = 2, the last digit is 9; and if x mod 4 = 3, the last digit is 7.

Since Graham's number is a huge power tower of threes, this means that it is equal to 3 to the power of some huge power of 3, or alternatively, 3 to the power of an odd number. This allows us to narrow down the last digit of Graham's number even further. We know that the number x where 3^x = Graham's number is odd, which means that x mod 4 is not 0 or 2, which in turn means the last digit of Graham's number is not 1 or 9. This means that we can narrow this fabled last digit down to two possibilities: it's either 3 or 7.

So now the question is as follows: is x mod 4 equal to 1 or 3? To find out, let's see what the powers look like in the quaternary base, or base 4. The first few powers of 3 in quaternary look like this: 3, 21, 123, 1101, 3303. There's a simple pattern you can see: in quaternary, 3 to the power of an odd number ends in 3, and 3 to the power of an even number ends in 1. This means that 3 to the power of any odd number in quaternary ends in 3, which in turn means that x mod 4 = 3 (remember, x is the number where 3^x = Graham's number). And this means we've found out the last digit of Graham's number: it's 7!

But people have been able to calculate more ending digits of Graham's number by calculating patterns in more ending digits of powers of 3. The last two digits of powers of 3 break into a steady cycle, but a longer one than the single last digit. If x mod 20 = 0, then the last two digits of 3^x are 01. For instance, 3^0 = 1 and 3^20 = 3,486,784,401. I won't go into detail about how to calculate the second last digit; this kind of recursive calculation is better fit for a computer than for a human. So I'll just skip to the last 500 digits of Graham's number:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

These aren't just the last 500 digits of Graham's number. They're also the last digits of G(1), G(2), G(3), and so on. In fact, they're the last 500 digits of any power tower of 501 or more threes, and thus they're the last digits of all sorts of different googolisms made involving threes. Still, Graham's number is without a doubt the main motivation behind those digits; there is tons of allure in figuring out at least some of the digits that make up this number.

The First Digits of Graham's Number

No one knows what the first digit of Graham's number is—we only know that it can't be 0. It is possible to calculate the first digits of some googolisms whose full decimal expansions are out of reach, such as the so-called Tritet Jr, equal to 4^^4. The number has over 10^153 digits, but its decimal logarithm has been calculated down to the ones place and a little beyond that. To see what I mean, here are the first few digits of 10^0.5:

3.162277660168379

and here are the first few digits of 10^1.5:

31.62277660168379

and here are the first few digits of 10^2.5:

316.2277660168379

As you can see, no matter what the integer part of the number you raise 10 to the power of is, as long as the digits after the decimal point of x are the same, the digits of 10^x will be the same. The only difference is the placement of the decimal point, which depends on the integer part of x. With enough digits of the fractional part of log_10(4^^4), it's similarly possible to calculate the first several digits of this number, which are 23610226714597313206.

But Graham's number is far, far, far too big for that strategy to work. In fact, the largest power tower of threes where such digit calculations are feasible would be 3^^4, a number that's about 3.63 trillion digits long. Maybe 3^^5, where the number of digits is itself 3.63 trillion digits long, but that's severely pushing the limits of what computers are capable of. Computers have been able to calculate trillions of digits of pi, so the question lies in if anyone would be willing to use such advanced technology to calculate the first digits of 3^^5.

The first digits of Graham's number are indeed hopelessly out of reach. Or at least they are in the decimal base. In one of several videos on the Numberphile YouTube channel about Graham's number, Ronald Graham quips that in binary, the first digit of Graham's number is 1.[13] While this remark was obviously meant in jest, it does show us that "no one knows the first digit of Graham's number" is a very decimal-normative statement. Why not give other bases some love?

In the binary base, any positive number's first digit is 1; that was the joke Ronald Graham was getting at here. But binary isn't the only base where we know the first digit of Graham's number! What about ternary, base 3? In ternary, powers of three look like 10, 100, 1000, 10000, and so on, just like how powers of ten look in decimal. Therefore, in ternary the first digit of Graham's number is also 1! While the full decimal expansion of Graham's number is mysterious, the ternary expansion is just one followed by a whole bunch of zeroes.

We can go further. How about the nonary base, or base 9? In nonary, the powers of three look like 3, 10, 30, 100, 300, 1000, 3000, and so on. Three to the power of an odd number starts with 3, and three to the power of an even number starts with 1. Therefore, the first digit of Graham's number in nonary is 3, and the rest of the digits are all a bunch of zeroes. The nonary expansion of Graham's number has exactly half as many digits as the ternary expansion, and almost exactly half as many zeroes.

With tricks such as this, it might be possible to know the first digit of Graham's number in any base that's a power of three; the hard part is deciding which system of digits to use for any base beyond decimal. In base 27 (trinonary in jan Misali's base-neutral naming system for bases),[14] Graham's number once again is 1 followed by a bunch of zeroes. As for higher powers of three, I'll leave you to find that out. So while the first digits of Graham's number in decimal are shrouded in mystery, there are some bases where it's possible to know them. And besides, in base Graham's number—a hypothetical base that you might call "grahamal"—Graham's number is simply written as 10.

Conclusion

To review, a lot of the conventional wisdom on Graham's number is a myth. There are in fact three distinct versions of the number: the original one, the one used to popularize Graham's problem, and one that was once believed to be an error but is actually something more than that. To add on, hopefully you now realize that Graham's number is not by any means the "largest number", unless you count misguided conventional wisdom!

That being said, if you're new to googology, take these words: Don't stop once you hit Graham's number if you ever start coming up with large numbers. Graham's number, as we will see, is just the beginning of a land of amazing and epic large numbers, which will themselves make Graham's number look tiny, to the point where Graham's number is a horrifyingly early place to stop! Graham's number may be an eye-opener to the world of googology, but you shouldn't act as though it's the "king of the numbers". I will end with this quote Graham said about his number:

"Graham's Number is not really any closer to infinity than the number one. You just didn't really get started yet, even though you took a lot of steps to get to Graham's Number, it takes so many more, infinitely more, to get to infinity."

—Ronald Graham^[2]

So up next we'll discuss the most popular way to crush Graham's number: Conway's chain arrow notation.

Sources

[1] Wikipedia's article on Ronald Graham (link)

[2] Sbiis Saibian's article on Graham's number (link), this is an article that goes into even more detail on Graham's number than I do

[3] Wikipedia's article on Frank P. Ramsey (link)

[4] Wikipedia's article on Ramsey's theorem (link)

[5] Wikipedia's article on Graham's number (link)

[6] Jonathan Bowers' homepage (link)

[7] Graham and Rothschild's paper with the proof involving "Little Graham" (link)

[8] Robert Munafo's page on the various Graham's numbers (link)

[9] Wikipedia's article on Martin Gardner (link)

[10] Martin Gardner's article on Graham's number viewed online by the Big Psi project (link)

[11] Deedlit11's Googology Wiki blog with a better bound to the Graham's number problem (link)

[12] The paper where the 2^^2^^2^^9 bound was proven for Graham's problem (link)

[13] How Big is Graham's Number (feat Ron Graham), video by Numberphile (link)

[14] a base-neutral system for naming numbering systems, video by jan Misali (link)

2.09. Conway's Chain Arrows