3.2.9 - graham

3.2.9

Graham's 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 L. Graham

PREV>> 3.2.8 - The Jubilant Googology of Andre Joyce

Introduction

No discussion of about large numbers would be complete without at least a passing mention of Graham's Number. While for our purposes it's not much more than a tiny shining beacon in a vast shadowy ocean of incomprehensible monsters, and a somewhat arbitrarily placed one at that, it has been the focus of so much of the popular large number discussion that we would be remiss to simply ignore it. Graham's Number, more so than any other value in googology, has captured the popular imagination, and is still prominent even today in large number discussions. So much so in fact, that Graham's Number has overshadowed any other number in the discussion, even much much larger ones, to the chagrin of googologist's. The number is surrounded by a aura of mystique and myth that is difficult to dispell. This article will seek to amend the misunderstandings surrounding this truly enormous value.

Who is Ronald L. Graham

It should be noted that we aren't interested here in any of the particulars of the described situation, like determining the probability of blue and red based on the visible distribution. Instead we want a general solution that would apply regardless of the particulars. It doesn't in fact matter whether the reds and blues are evenly distributed or there is more of one or the other. Why? Because the question isn't interested in which color we get 2 of. It fulfills the condition of the problem whether we get 2 reds or 2 blues. It doesn't matter which.

A naive solution would be 2, since we at least need 2 gumballs to have a pair of any color. But what if we purchase 2 gumballs and get a red and a blue? Then we don't have a pair of either color. However if we purchase 3, you'll always have at least 2 of one color.

If we look at all the possible ways we can get 3 gumballs, it can plainly be seen that no matter what we get, we'll always obtain at least 2 of one color:

We can change the parameters of the problem. We could include more kinds of gumballs in the gumball machine. For example, say we now have red, blue and green gumballs. To obtain at least 2 of a single color we now need to purchase a minimum of 4 gumballs. We could also change the number we are trying to obtain. Say we want a minimum of 3 of the same color between reds and blues. We then need to purchase a minimum of 5 gumballs to ensure that there is at least 3 of one color.

As you can see, these are very elementary kinds of problems that only take a moments reflection to solve. Not all problems in Ramsey theory are so easy however. One common type of Ramsey problem involves the coloring of the lines formed by connecting a set of points. Ramsey's theorem has direct bearing on these kinds of problems, and this type of problem is also very closely related to the question Graham was trying to answer.

To understand something of what Ramsey's theorem is about we're first going to need to learn some terminology. In Ramsey theory a graph is a set of points connected by lines. Here are some examples of such graphs:

For convenience we can think of each of the points as having numerical designations. Any graph can then be described as a set of lines formed by pairs of points. For example the first graph could be encoded as:

{(1,2),(2,3),(3,4),(3,6),(6,5),(3,5)}

Note that the order in which we write the pair of points is unimportant, so that (1,2) and (2,1) refers to the same line. The actual physical arrangement of the points is not relevant to the graph. These can be rearranged at will as long as the lines connect the same pairs of points. Graphs with the same connection structure are considered equivalent graphs.

A Complete Graph is a graph of n points in which every possible pair of points has a connecting line. A complete graph of n points is notated as K_n. Here are some small examples of complete graphs:

One important property of complete graphs is that a complete graph of size n, contains all complete graphs of a smaller size. For example, if you look at any 4 points of K₅ and focus only on the lines connecting these 4 points, you'll see an embedded K₄. This we can call a complete sub-graph.

Now imagine that we could color any of the lines contained in a complete graph. One of the consequences of Ramsey's theorem, and one which is very relevant to Graham's Number, is that given a sufficiently large two-colored complete graph there will always exist complete sub-graphs of any predetermined size which will contain only one color. Such graphs are called monochromatic, meaning one-colored.

A common notation used for this is R(p,q) where R(p,q) is the smallest number, n , such that two colored K_n must contain at least one monochromatic K_p in color 1, and at least one monochromatic K_q in color 2. Numbers of this form are known as Ramsey Numbers. For our purposes, we won't be too interested in specifying what complete graphs are required for each color individually. We are instead going to look for the Ramsey Numbers where p=q. This is equivalent to asking what the minimum two colored complete graph is that contains a one colored complete subgraph of a given order. For this I'll use the notation Ram(n) = R(n,n).

Note: The reason I didn't use R(n) or Ra(n) is because I use R(n) to represent the return function, and Ra(n) to represent Rayo's function.

We can look at the first few trivial values of Ram(n) to get started. Firstly, note that K₀ can be interpreted as the empty graph containing no vertices (points) or edges (lines). So as long as n is a non-negative integer, Z⁺U{0} or Z⁰ for short, then K_n is a meaningful graph. To say a complete graph is monochromatic we only need say that all it's edges are the same color. Since K₀ and K₁ contain no edges, it doesn't seem meaningful to make a statement about the "color" of it's non-existent edges. In order to make the question meaningful we will slightly change the definition of Ram(n) to be the minimum 2-colored complete graph which contains a order n complete graph with no more than 1 color for its edges. Since K₀ and K₁ have no edges, they have "no colors" for their edges, and therefore qualify as having no more than 1 (in fact 0) colors for it's edges. Under this definition we can say that Ram(n) is well defined as long as n is an element of Z⁰.

Firstly let's consider Ram(0). What is the minimum complete graph to include the K₀ sub-structure? Well K₀ of coarse. Any higher structure can be thought of as including a nullary structure by default. It's equivalent to saying that 4 contains 0 since 4+0=4. Thus Ram(0)=0, trivially speaking.

Ram(1) is equally trivial. Again what is the minimum complete graph to include the K₁ sub-structure? K₁ naturally. We can plainly see that any complete graph above order zero, includes K₁ since it is a collection of such vertices. Thus Ram(1)=1.

Ram(2) is the first which considers a sub-structure including an edge. However, regardless of what the color of an edge is connecting two vertices, it is still a monochromatic K₂ by the definitions set up above. So we can say that Ram(2)=2.

So far there is nothing very surprising or interesting about the behavior of the function Ram(n). It is behaving just like the return function. Does Ram(3)=3?

Ram(3) turns out to be the very simplest non-trivial example of such a problem. Here we would want to determine the minimal two-colored complete graph (typically red and blue) such that a monochromatic K₃ is forced (a one-colored triangle must exist). Unlike the above problems for Ram(0), Ram(1), and Ram(2), this problem is not so easy to solve with a moments reflection. Like before we can begin with the naive assumption that the solution must be at least a K₃ (size 3 complete graph), since any smaller graph can't possible contain a K₃ as a sub-graph. Thus 3 would be a lower-bound to the solution, which we'll call N*. We can thus say that:

3=<N*

It's obvious however that N* must be greater than 3 however, because if we have two-colors there is no reason a K₃ must be monochromatic. We could just color two sides red and one side blue, for example. So is 4 the solution? No, but showing that 4 is not the solution takes a little more thought. To prove that a monochromatic K₃ is not forced, it is sufficient to give a single example in which it fails. Here is a simple example case which proves that 4<N*:

As you can see none of the 4 possible K₃ subgraphs is monochromatic. The reason is because they all have two sides which are part of the outer edge and 1 side which is part of the inner cross. Since the outer square is red and the inner cross is blue every K₃ contains both red and blue.

What about N*=5? We can set up a similar counter-example. This time there are 10 K₃ subgraphs to check, but it's still very easy to verify this counter example. Again we color the outer portion red and the inner blue.

Although we could check all 10 triangles manually, a simple argument can be constructed which shows none of them can be 1-colored. All K₃'s are formed by choosing 3 of the 5 points of our K₅. Any two points chosen must form a line which is either part of the outer pentagon or part of the inner pentagram (5-point star). Let's label these two points "A" and "B". Now we chose a third point, "C". The line connecting B and C must also either be part of the pentagon (outside) or pentagram (inside). Naturally, if we are trying to get a monochromatic K₃ we want both lines AB and BC to be the same color. However, if this is so the third line AC must be of the opposite color. To understand why consider the properties of the red and blue lines. Say we label the points of our K₅ 0,1,2,3, and 4 with 0 at the pinnacle, and the numbers continuing in sequence clock-wise:

Note that the numbers of the points forming the red lines of the pentagon are always 1 apart. The numbers of the points forming the blue lines of the pentagram are always 2 or 3 apart. Using modular arithmetic we can codify this nicely and say that if A and B are two numbers than:

A-B = 1 or 4 indicates that line AB is red

while...

A-B = 2 or 3 indicates that line AB is blue

So we can say that line AB is either red or blue and line BC is the same color. Let's assume AB and BC are both red. We know that A,B, and C must all be distinct and that A and B are one apart, while B and C are also one apart. We also know that:

either A<B or B<A

&

either B<C or C<B

These statements can only agree if either A<B & B<C or B<A & C<B. In either case we would find that the distance between A and C would be 2, and therefore line AC must be blue, thus we would not have a monochromatic K₃.

On the other hand if we assume that lines AB and BC are both blue then it follows that:

either A+2=B or B+2=A

&

either B+2=C or C+2=B

Technically we have 4 possibilities, but again 2 of them aren't possible. For example A+2=B & C+2=B can't both be true because this would imply A=C which contradicts that A,B, and C are distinct. It also can't be true that B+2=A & B+2=C for the same reason that this would imply A=C. Therefore either " A+2=B & B+2=C " or " B+2=A & C+2=B ".

For the first possibility we have:

C= B+2 = (A+2)+2 = A+4

But this means A and C are 4 apart, which also means they are also consecutive, which means line AC is red. For the second possibility we have:

A = B+2 = (C+2)+2 = C+4

So again A and C are 4 apart, which means AC would be red. So again we can't get a monochromatic K₃.

So we reach the result that N*>5. Is N*=6, or can we disprove that too? In a naive search of a counter-example we might again try coloring the outer hexagon red and the inner portion blue:

As you can see in the above diagram however, it contains at least one monochromatic K₃. In fact, out of the 20 possible K₃ subgraphs, only 2 of them are monochromatic. We might think we could easily solve the problem simply by changing one of the sides of these 2 monochromatic K₃'s. The problem is that for all 3 sides in the example K₃ if you change one of them to red, it will then form a monochromatic red K₃ with the outer edges. At this point it may dawn that perhaps N*=6. To prove this however we would have to show that any 2-coloring of K₆ will always contain at least one monochromatic K₃. No problem, we'll just run through all the possibilities and verify that they all contain at least one monochromatic K₃. But how many possibilities are there? It isn't difficult to verify visually that there are in fact 15 connection lines. Since each of these can be either red or blue there are 2¹⁵ possible colorings. That comes out to 32,768 possibilities! This is too many to practically work out by hand, although it could be done theoretically, but it's certainly too many for us to work out here!! A computer program could be written to cycle through the possibilities and quickly confirm N*=6 or not, but perhaps there is a better way than direct verification.

We can in fact verify that N*=6 without having to go through the trouble of checking each coloring. Simply consider the following. Every vertex of a K₆ is the end of 5 edges connecting it to the other 5 vertices. This means that there must be at least 3 of these edges of the same color (red or blue) by the same reasoning used in the gumball problems. Let's say these 3 edges are in the "primary color". We can call the original vertex, V. Let the other 3 vertices forming our 3 edges be called X,Y, and Z. The 3 edges in the primary color are therefore VX, VY, and VZ. Since this is a complete graph, the triangle formed from edges XY, YZ, and ZX must also exist and be one of the two available colors. If any one of these edges is the primary color then a monochromatic triangle is formed with 2 of the edges of the orginal 3 primary colored ones from vertex V. So in order to avoid monochromatacy, XY, YZ, and ZX must all be of the opposite color, but then they themselves form a monochromatic triangle of the opposite color! Since this argument would apply to any two-coloring of K₆ we conclude that Ram(3) = 6.

Interestingly, Ramsey's theorem only states that a values for Ram(n) exist. It doesn't establish how to compute it. Very few nontrivial values of Ram(n) and R(p,q) are actually known, and the difficultly of determining them increases rapidly as n,p, and q increase in size. In general computing Ramsey Numbers is an exceedingly difficult problem!

It is known that Ram(4) = 18. In fact the only known classical Ramsey Numbers[3] are:

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) = Ram(4) = 18

R(4,5) = 25

For cases where n, p and q are larger, there are bounds for Ram(n) and R(p,q) but no exact solutions.

If you've followed the discussion up until this point, then all of this has direct bearing on Graham's Number. Classical Ramsey Theory considered the classical Ramsey Numbers, but around the time of Graham writing his infamous paper, the field was already expanding to include more general kinds of problems. Graham was considering a variant problem of the one presented by classical Ramsey Numbers.

To explain it, I'll first have to explain what a hyper-cube is. In simplest terms, a hyper-cube is a higher dimensional analogy to a cube. To undertand this begin by imagining a point. This is considered a 0-dimensional object. Now imagine letting that point trace out a line by heading off in any direction. A line is considered a 1-dimensional object. Now imagine the line moving perpendicular to itself to trace out a square. The square can be thought of as the 2-dimensional analogy of a cube. Now imagine the square moving perpendicular to it's plane to trace out a cube. A cube is a 3-dimensional object. Our world is 3-dimensional, but ask yourself, is it meaningful and concievable to speak about ... a 4th dimension? Although we can't imagine what that would be like, mathematically we can describe it. First you have to postulate the existence of a 4th "invisible axis" which is perpendicular to all of space. Now imagine a cube traveling along this axis. It would trace out a "hyper-cube" or "tesseract". The diagram below illustrates the idea.

Note that a line contains 2 vertices, a square 4, a cube 8, and a tesseract 16. We can continue into higher dimensions by simply adding more and more hypothetical axes. The result is that an n-dimensional cube always contains 2ⁿ vertices. We can see that despite their dimensionality, the n-dimensional cubes are really just graphs with vertices connected by edges.

This is where Ronald Graham comes in. We can turn any n-dimensional cube into a complete graph simply by connecting all vertices. The remaining edges formed thus, all occur internally, or on one of the faces. We could imagine that these edges are two colored, red and blue, just as we had explored in the previous problems. Graham now devises an interesting varient on the question of classical Ramsey theory:

Graham's Problem

What is the minimum number of dimensions, denoted N*, of a 2-colored k-dimensional cube where all vertex pairs form an edge such that there must exist a monochromatic K₄ where it's 4 vertices rest within the same plane.

This question is related to Ram(4), but has some important differences. It's not asking about the minimum complete graph, but rather the minimum number of dimensions. The complete graph and number of dimensions are related by the fact that the n-dimensional case is technically a 2^n order complete graph. If these were the only conditions of the problem then the answer would simply be 5, since Ram(4)=18 and any complete graph with 18 or more vertices must contain a 1-color K₄. The 5-dimensional case would involve a "pentaract" with 32 vertices. The part that makes the problem exceptionally difficult is that the K₄ must lie flat within a plane in addition to being monochromatic! Recall that a K₄ by definition is formed with 4 vertices. 3 vertices will always form a triangle which rests within one plane or another. 4 vertices however do not necessarily fall within a plane. A tetrahedron, is an example of a K₄ which can not rest within a plane, but occupies space instead.

Although the problem itself is very difficult, the question it poses is not so difficult that the average person couldn't take the time to understand what it's asking. One thing that is rather remarkable about mathematics is that simple questions sometimes have very difficult to obtain answers. So the idea that the question Graham was asking was so esoteric and academic that the average person couldn't approach it is blatantly false. We can at very least appreciate what Graham was asking, even if we don't understand how he arrived at his particular answer.

Let's see if we can make sense of the difficulty of the problem itself before we consider what Graham did next. In a naive search for an answer we might begin by establishing the domain of reasonable answers. Firstly we can say that an n-dimensional cube with all vertices connected is well defined when n is a non-negative integer, but meaningless otherwise.

So the smallest possible solution would be 0. A 0-dimensional cube however is just a vertex or K₁, so it is not possible for it to contain a K₄ of any kind.

The 1-dimensional case would simply be an example of a K₂ so also could not contain a K₄.

The 2-dimensional case would actually be a K₄. Not only that, but by necessity this K₄ would rest within a plane. The problem is that with 2-colors there is no reason this K₄ has to be monochromatic. So we know that the solution must be greater than 2:

N*>2

The next case is much more difficult to consider. Imagine the 3-dimensional case. Here we have an ordinary cube, but it also includes many internal lines. Here is a counter example we'll use to show N*>3:

The 3-dimensional case is in fact a K₈. The first question we might want to ask is just how many K₄'s are even contained within a K₈, and then determine how many of these rest within a plane. To determine the number of K4s we consider the sum of the first 5 tetrahedral numbers:

tet5 + tet4 + tet3 + tet2 + tet1 = (15+10+6+3+1) + (10+6+3+1) + (6+3+1) + (3+1) + 1 = 35+20+10+4+1 = 70

Of these 70 k4s only 12 of them rest within a plane! To understand why, recall that any 3 points rest in a plane. For any set of 3 points, there is either only one choice for a 4th point that will form a planar K4, or there isn't. If the 3 points are all part of one of the six faces of the cube, then obviously the only choice is to chose the remaining vertex of the face to form a planar K4. Thus there is at least 6 planar K4s, one for each of the 6 faces of the cube. Let's say the 3 points do not belong to a single face. If two of these points form an edge of the cube (as opposed to a diagonal), then there is only two possible choices for a third point so that all three don't rest in the same face. In such an instance, the third point is the opposite corner of one of the other two points, and by chosing the 4th point as the opposite corner of the other of the two points we also form a planar K4. There are 12 edges of the cube, however each of these K4s actually uses 2 such edges, so we get an additional 6 planar K4s out of this. We considered the case where the 3 points form two edges of a face, and when they only form one edge. The only possibility left is if no such edges are formed by the 3 points. For any arbitrary chosen point we have 3 choices for a second point to fulfill this requirement. One of those choices is a dead end however. If we choose the opposite corner, then no choice for a third point prevents there being an edge of the cube. Of the two other choices, we get two choices each for a third point. Regardless of how this is chosen we get a triangle which is part of one of two monochromatic blue tetrahedron K4s in the 3-dimensional case. These can't form planar K4s. So we get the total of 12.

The above diagram is probably difficult to see, so I'll separate out the 12 planar K4s to demonstrate that none of them are monochromatic:

This counter-example shows that N*>3. Actually if we know that Ram(4)=18, we already know that N*>3, because the 3-dimensional case is simply a K8, and no monochromatic K4s are forced in this case, planar or not. This objection would also apply to the 4-dimensional case, so we know that N*>4. The smallest reasonable possibility is therefore the 5-dimensional case, since this involves a K32. It is known that N*>5, but this is already a difficult result to prove.

In fact, even Graham doesn't actually "solve" the problem, in that he doesn't find an exact value for N*. What his 1971 paper does do however, is find an upper-bound for N*. We saw how upper-bounds work in the article on the mega. Graham was able to prove that N* had to be no bigger than a certain very very VERY large integer.

At the end of Graham's 1971 paper, "Ramsey's Theorem for n-parameter sets"[4], he arrives at the following result:

N* =< F(F(F(F(F(F(F(12,3),3),3),3),3),3),3)

This is Graham's original number, Little Graham.

After this Graham makes this amusing statement:

"On the other hand it is known only that N*>=6. Clearly, there is some room for improvement." - Graham

In the article in which Gardner introduced the world to Graham's Number he had this to say, speculating as to the actual answer of the problem:

"Ramsey theory experts believe the actual Ramsey Number for this problem is probably 6."

-- Martin Gardner

This is oft repeated as the punchline of many an article on Graham's Number after Gardner introduced it to the world. However this statement is already out of date. It was recently proved that the solution could not be smaller than 11.

But whether it's 6 or 11 it begs the question: if the solution is vastly smaller than Little Graham, then what real significance does the number actually have? The problem with large numbers which act as upper-bounds is that their purpose is tentative. They only exist as a rough solution until a better one is found. A better kind of large number is one which doesn't "deflate". The real question isn't whether we can create a really large upper-bound. Anybody can do that. Just come up with something vastly larger than Little Graham and it's also an upper-bound on Graham's problem. The real question is can we come up with a problem whose actual solution is a tremendously huge number? It turns out ... we can.

One of the other things that is often missed with Graham's Number is that it's NO LONGER the "largest number ever used in a serious mathematical proof". Further work in Ramsey theory by mathematicians such as Joseph Kruskal and Harvey Friedman has resulted in even more mind bogglingly massive values cropping up in serious mathematics such as TREE(3). Such a value is incomparably larger! But what makes a value like TREE(3) even more mathematically significant than Little Graham is that even it's solution is larger!!! In fact, no body knows the exact value and even the best available lower-bound is truly massive. What ever TREE(3) turns out to be it won't be 6...

From a googologist's point of view however, it doesn't matter too much what problem a large number is connected to, as long as it leads to a massive number. So as long as there are googologists Little Graham will have a place amongst them.

But what percisely is Little Graham? We'll explore that under the next heading...

Sizing up Little Graham

Graham defines the F fuction 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

The definition as originally presented seems awkward to me, so I'll translate in into the standard instruction format used in googology:

Little Graham's Function

Let F(a,b) be a binary function defined when a,b are positive integers and b>1 as follows:

1. If b=2 ; F(a,2) := 4

2. If a=1 ; F(1,b) := 2^b

3. F(a,b) := F(a-1,F(a,b-1))

The F function is basically a varient on the Ackermann function. We should therefore expect the values to go up by one level of primitive recursion every time "a" increases by 1.

Graham recommends trying some small values to get a feel for how this function works and I agree. He suggests the values F(5,5) and F(10,3). We'll try those out, but first let's begin with some smaller values.

One awkward thing about the F function is that it's not defined for when b=1, so expressions of the form F(a,1) are undefined. The smallest possible legal case is actually F(1,2). Let's see what happens.

Since b=2, condition 1 applies so : F(1,2) = 4.

Rather trivial. What happens if we let b increase? Well, then Rule 2 applies and we obtain:

F(1,3) = 2^3 = 8

F(1,4) = 2^4 = 16

F(1,5) = 2^5 = 32

F(1,6) = 2^6 = 64

F(1,7) = 2^7 = 128

F(1,8) = 2^8 = 256

F(1,9) = 2^9 = 512

F(1,10) = 2^10 = 1024

etc.

So for a=1, we just get the powers of 2. With this we could retroactively define F(1,1) = 2^1 = 2.

Let's now look at a=2:

F(2,2) = 4 [via R1]

F(2,3) = F(1,F(2,2)) [via R3 since c1&c2 don't apply] = F(1,4) [via R1 since b=2 in F(2,2)] = 2^4 [via R2] = 16

F(2,4) = F(1,F(2,3)) = F(1,16) = 2^16 = 65,536 = 2^^4

F(2,5) = F(1,F(2,4)) = F(1,65536) = 2^65,536 = 2^^5

F(2,6) = F(1,F(2,5)) = F(1,2^^5) = 2^2^^5 = 2^^6

...

Inductively...

If F(2,k)=2^^k

then F(2,k+1) = F(1,F(2,k)) = F(1,2^^k) = 2^2^^k = 2^^(k+1)

Therefore F(2,b) = 2^^b

Interesting. Retroactively we can also say that F(2,1) = 2^^1 = 2. Hmm. Noticing a potential pattern here?

Let's look at the case of a=3:

F(3,2) = 4 [via R1]

F(3,3) = F(2,F(3,2)) = F(2,4) = 2^^4 = 65,536

F(3,4) = F(2,F(3,3)) = F(2,65536) = 2^^65536 = 2^^2^^4 = 2^^2^^2^^2 = 2^^^4

F(3,5) = F(2,F(3,4)) = F(2,2^^^4) = 2^^2^^^4 = 2^^^5

...

Inductively...

If F(3,k) = 2^^^k

then F(3,k+1) = F(2,F(3,k)) = F(2,2^^^k) = 2^^2^^^k = 2^^^(k+1)

therefore F(3,b) = 2^^^b

Retroactively we can define F(3,1) = 2^^^1 = 2.

Now the pattern should be fairly obvious. It appears that:

F(a,b) = 2^^...^^b w/a ^s

It isn't difficult to prove this. We just need to use double induction. For convenience I'll use the following operator notation devised by Jonathan Bowers':

a<c>b := a^^^...^^^b w/c ^s

To begin the proof first observe that:

F(a,2) = 4 = 2^2 = 2^^2 = 2^^^2 = 2^^^^2 = ... etc.

therefore

F(a,2) = 2<a>2 [lemma 1]

Next let "j" be any positive integer for which the following holds:

F(j,b) = 2<j>b [lemma 2]

We now perform a double induction. First we know that:

F(j+1,2) = 2<j+1>2

From lemma 1

Next let "k" be any positive integer for which the following holds:

F(j+1,k) = 2<j+1>k

Now comes the first induction:

F(j+1,k+1) = F(j,F(j+1,k)) = F(j,2<j+1>k) = 2<j>2<j+1>k [via lemma 2] = 2<j+1>(k+1) [properties of a<c>b]

So by the first induction we conclude that F(j+1,b) = 2<j+1>b. But this means that F(j,b) = 2<j>b --> F(j+1,b) = 2<j+1>b. By a second level of induction, we conclude that:

F(a,b) = 2<a>b

Now that we understand how Graham's F function works, we can retroactively add the cases F(a,1) and define them as F(a,1) = 2<a>1 = 2. This allows for a nice simplification of the F function:

Modified Little Graham Function

Let F(a,b) be defined when "a" and "b" are positive integers as follows:

1. a=1 ; F(1,b) := 2^b

2. b=1 ; F(a,1) := 2

3. F(a,b) = F(a-1,F(a,b-1))

Little Graham Conversion Theorem

F(a,b) = 2<a>b : Aa,b=Z+

Graham's challenge is now straight forward:

F(5,5) = 2^^^^^5 (Already ridiculously huge!)

F(10,3) = 2<10>3 = 2<9>2<9>2 = 2<9>4 (Incomprehensibly huge!!!)

We are now ready to tackle the definition of Little Graham. Recall:

Little Graham = F(F(F(F(F(F(F(12,3),3),3),3),3),3),3)

To make this easier let's define the function g(n):

g(1) = F(12,3)

g(n) = F(g(n-1),3) : n>1

We can now say that:

Little Graham = g(7)

Let's see if we can wrap our brains around this. Let's start with just g(1):

g(1) = F(12,3) = 2<12>3 = 2^^^^^^^^^^^^3

If you can recall the article on Up-arrow notation you know this number is already incomprehensible! But we are about to totally transcend the stuff we talked about in the up-arrow article. Just consider g(2):

g(2) = F(g(2-1),3) = F(g(1),3) = F(2^^^^^^^^^^^^3,3) =

...o_0!!!...

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

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

What the ... just try to imagine what that means. Just the addition of a single extra up-arrow is phenomenal leap in growth and we have 2^^^^^^^^^^^^3 arrows!!! And that isn't even the worse part ...

g(3) = F(g(2),3) = F(2^^^^^^^^^^^^^^^ ... ... ... ... ... ... ... ... ^^^^^^^^^^^^^^^^^^^^3,3) =

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

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

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

With g(3) everything we thought we knew about numbers goes out the window. The growth rate of g(n) is incomprehensibly fast. It's hard for us to imagine (impossible actually) just the size of g(2) and how all those up-arrows work out ... God forbid ... we should have ... dare I say it ... THAT MANY UP-ARROWS!!! WHAT WOULD THAT MEAN IN TERMS OF GROWTH!?!?!

When I first encountered Graham's Number and understood it, it literally shocked my brain and I got a huge rush of adrenaline. I never thought anyone would dare to go that far! Now that sounds naive but at the time I was really blown away. The irony is that unbeknowst to me at the time I had already contemplated even larger numbers as a kid. I only later realized this as I began to work out the comparison with my childhood large number notation with other notations.

And we aren't even done. Just try to imagine the sequence g(4),g(5),g(6),g(7). Because of our limited number sense, it is not possible for people to imagine more than a handful of recursions simultaneously. So we can sort of imagine g(1),g(2),and g(3) in terms of up-arrows, but g(4) is tricky to get straight, and g(5) and beyond is virtually impossible.

We can however use a simple diagram to get the idea across:

Suffice it to say that even Little Graham is HUGE! It's already bigger than the Moser, the largest number we encountered up until this point. In fact a Moser lies somewhere between g(1) and g(2).

It should be noted that the "problem" that Little Graham is an upper-bound for, was never the entirety of the paper. It was only given as a mere illustration towards the end of the paper of corollary 12. The main purpose of the paper was to apply Ramsey's theorem to n-parameter sets. How did such a large number result? Graham wanted to prove corollary 12, which was simply an existence proof (ie. a solution exists to a certain class of problems). The existence proof is often made easier by making the search boundaries very large. The method by which he proved corollary 12 had the up-shot that if one wished to, one could derive an actual concrete upper-bound for the solution. Graham computed Little Graham as a mere illustration. It was never the main purpose of the article. One would hope that dispells some of the mystique surrounding this number, but undoubtably Graham's Number will continue to capture peoples imaginations and think ... wow, why do mathematicians need such large numbers. If they only knew. Graham himself admits that this number is too large, and a smaller bound should be found for the problem.

It must also be noted that Little Graham is the real upper-bound that was used in a "serious mathematics paper". There is nothing gained, mathematically speaking, by making a larger upper-bound! That's just getting further from the solution. So a paper about an even larger upper-bound is rather dubious, and it's debatable whether that can be thought of as a "serious mathematical paper". Basically anything that was worth saying in the 1977 paper, was already said in the 1971 paper.

So what about the larger version of Graham's Number. We'll look into that next...

Graham's Number and ... another Graham's Number ?!

Now you know how Little Graham came about. Now you know that while the solution is difficult, the question itself is simple enough to understand. What happened next was myth in the making. Martin Gardner was fascinated by Little Graham, and was quick to declare it the largest number in mathematics. Gardner and Graham mentioned the number to a few people, but they found the definition of Little Graham difficult to convey. Together they invented Graham's Number. I am tempted to say it's more Gardner's Number than Graham's, but I'm afraid its too late to change the history books. According to physicist John Baez, Graham invented the number now bearing the moniker Graham's Number in a conversation with Gardner himself[5]. In 1977, six years after Graham had written his infamous 1971 paper, Gardner wrote an article in Mathematical Games titled "In Which Joining sets of points by lines leads into diverse (and diverting) paths"[6]. In it he introduces Graham's Number as we know it today. It differs significantly from Little Graham. Here is the original illustration Gardner used to explain Graham's Number:

It's conventional to use the notation G(n) to define Graham's Number. Here is how it is usually defined:

Let G(1) = 3^^^^3

Let G(n) = 3^^^...^^^3 w/G(n-1) ^s : n>1

Graham's Number = G(64)

Graham's Number is much larger than Little Graham. It turns out that:

Little Graham = g(7) < G(8) << G(64)

(I'll prove this later in the article, but first let's finish the tale of Graham's Number)

Shortly prior to Gardner's article, Graham wrote a revision of his 1971 paper, and in this one the new "improved" Graham's Number, shows up for the first time. Gardner's article caught the attention of the Guinness book of world records, who in 1980 listed Graham's Number, as presented by Gardner, as the "largest number ever used in a serious mathematical proof".

If that was the end of the story, the history of Graham's Number would still be somewhat convoluted, but there is one more twist in the tale...

In 1996 Richard K. Guy and John Horton Conway published "The Book of Numbers", a book of popular mathematics (we'll be talking more about Conway very soon when we get to Conway's Chain arrow notation. This is also the Conway who devised the system of extended -illions). The Book of Numbers devotes a mere 3 pages to the subject of large numbers (this is quite typical. Large Numbers is usually treated as an amusing limerick to mathematics, but rarely treated as a subject in it's own right). Yet these pages are legendary! Not only do they include a simple explanation of the hyper-operators using Knuth's up-arrow notation, but they introduce, the so called Ackermann Numbers, Conway's Chain Arrow Notation, the CG function, ... and a curious anomaly related to Graham's Number. Conway defines Graham's Number this way:

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

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

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

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

...

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

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

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)

Notice a difference? THERE ARE 4s NOW! Even stranger is Conway bounds Graham's Number as follows:

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

Now the 3s are back?! So are the 3's a typo, because it's also true that:

4-->4-->64-->2 < Graham's Number < 4-->4-->65-->2

Or are the 4's in Graham's Number a typo, and the 3s were intended all along. Come to think of it, don't the 4s make more sense seeing as 64 = 4*4*4? What's going on here?

Most people would not even have noticed the discrepancy, but googologist's took notice. The fact is, that while the difference makes very little difference in terms of the relative size of the number, and both numbers serve perfectly well as upper bounds, from a googologist's point of view they are DIFFERENT INTEGERS, and therefore a distinction should be made. Until recently googologist's could only assume it was a typo. Search for Graham's Number online and invariably (with a few erroneous exceptions) the 3s version is used. Conway appears to be the only source of the 4s version. However I was very lucky to get one additional clue into the mystery ... but unfortunately it only deepens the mystery...

Believe it or not, I got an opportunity to speak with John Conway himself recently in 2012. He was giving a casual lecture on the Surreal Numbers on my college campus, and I couldn't miss the opportunity to meet him in person. This was the guy who invented Conway Chain Arrows! So I made it a point to show up to the lecture. It was a surprisingly low key event, which on the one hand I was greatful for, but on the other hand is kind of a sad testament to the lack of awareness of mathematics in the general public. To me, and other math enthusiasts, Conway is a celebrity, just like anyone in holly wood or television.

Conway was very approachable and modest in his manner. He quickly put everyone at ease. After a low key lecture on the connection of surreal numbers to game theory, we all went out to the hall to ask further questions. I waited patiently for my turn to speak. Conway spoke about a few things. He mentioned his disappointment that the surreal numbers had not yet found an application. He also commented that anything that exhibited interesting properties was worthy of mathematical investigation. Given Conway's many curious mathematical creations, Conway Chain Arrows, the game of life, etc. I would say that Conway is far from a stuffy mathematician. Even in professional mathematics, things go in and out of vogue. Not all subjects in mathematics are treated with equal seriousness. There is of coarse the push from outside forces that mathematics should always be about applications. But to some extent, mathematicians are really driven by a fascination with the mathematical world itself. Hence the distinction between abstract mathematics and applied mathematics. What Conway expressed was something like the inner heart of mathematics, the curiosity to explore interesting things for their own sake. Perhaps then, Conway would be somewhat sympathetic and understanding of what drives googologist's. It may be "impractical" but it sure is fascinating. And googology is not without it's theorems too. It's just that they all have to do with comparing numbers ... comparing invented numbers which have little or no practical application in real life. Googology is really just an obscure and tiny branch of abstract mathematics.

Slowly the crowd began to die away, and Conway himself was getting ready to retire (I should mention that Conway is a man in his 70s, but still has a positive and inquisitive demeanor). Finally I got a chance to speak to him personally. I first asked him if he was the inventor of Chain arrows, and he confirmed this. Next I asked him about Graham's Number. What he told me came as a great surprise. He told me that "Ronald Graham had originally used 4s", "really" I said, "yes ... well it doesn't really matter". By this Conway simply meant that the difference was negligible. From a professional standpoint that makes perfect sense, but to a googologist every large number and it's neighbors is it's own little island universe; a fascinating destination for the mind, and truth be told the difference between the 3s version and 4s version would be incomprehensibly enormous! In any case, Conway had confirmed, not only that it wasn't a typo, but that there was a prior Graham's Number before the one that became famous. This confirmed my suspicion about the 64s. I also asked him if he was familiar with the work of Jonathan Bowers'. He very plainly said no, but he seemed interested. So I briefly explained that he had created a notation which was on par with the fast growing hierarchy. Although he was in a hurry to go, he did make this one last closing comment in response: "I have nothing against amateurs working in mathematics". To me, that was kind of like an endorsement that what googologist's do is fine. It's fine for amateurs to explore mathematics. It's not something reserved only for the priesthood of professional mathematics. With that he left with a staff member to be taken to his car. Conway mentioned that he will probably retire from his professorship soon, so there is a very good chance I'll never get another chance to speak with him. Still, it was great none the less to actually meet a famous mathematician, and especially one who had created something, really just in passing, that has inspired many googologist's, myself included, to take things to the next level ...

But this leaves many unanswered questions. Questions that might never be answered. Given Conway's status as a member of the inner circle of professional mathematics, I have to take his word. It's conceivable the Gardner and Graham may have originally used a version involving 4s, that they touted around prior to 1977. Conway must have been privy to this, so that when he wrote his book he used the original version. But this begs the question: why did Gardner/Graham, or both finally decide on 3s? If it is such an insignificant change, why even bother making it? Why is there no record of the 4s version? It is never actually mentioned in any history of Graham's Number to date (well now mine includes it, but as far as I know I'm the first). Why did Conway use the original version in 1996, when the 3s version had already become prevalent? I don't know. But as a googologist the most important thing isn't really where and how these numbers got invented. The most important thing is ... that they exist. They exist independently of each other, and they are all just as real (or unreal) as the number one. Therefore as a googologist, the distinction matters. So in fact, we have not one, not two, but three flavors of Graham's Number!

I hope that the information I have provided here will set the record straight on Graham's Numbers but given that Graham's Number already has 30 years of history behind it, I doubt this will change the general perception of the number. My main hope is that the googologist community will become more aware of the true history of Graham's Number's, and how the number now called Graham's Number actually has very little to do with the original proof.

Now that we have discussed where Graham's Numbers come from, let's consider their enormous size...

Sizing Up Graham's Number

To understand Graham's Number we must begin with an understanding of Knuth's Up-arrow notation. Although I've provided a fairly thorough explanation of them in Ascending with Up-arrows, I'll provide a brief explanation here for the sake of this article being more of a stand-alone.

Recall that:

a^^b = a^a^ ... ^a^a w/b a's

a^^^b = a^^a^^ .. ^^a^^a w/b a's

a^^^^b = a^^^a^^^ ... ^^^a^^^a w/b a's

etc.

and that all of these expressions are always resolved from right to left. We'll begin small and work our way up Graham's hierarchy. We can begin with:

3^3 = 3*3*3 = 3*9 = 27

One up-arrow simply results in plain of vanilla exponents. 3^3 is just 27. Just an ordinary palpable number ... something perfectly imaginable and immediate. What happens when we try a two up-arrows in a row:

3^^3 = 3^3^3 = 3^27 = 3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 = 7,625,597,484,987.

The result is about 7.6 trillion. This number is quite astronomical. It's not something we can totally wrap our heads around, but these kinds of numbers exist in the real world in abundance. It's big, but it's nothing particularly spectacular in our BIG universe. What about three up-arrows:

3^^^3 = 3^^3^^3 = 3^^3^3^3 = 3^^7,625,597,484,987

= 3^3^3^3^3^ ... ^3^3^3^3 w/7,625,597,484,987 3s

3^^^3 is a power tower of 7.6 trillion 3s! This number is WAY WAY WAY beyond astronomical. There is nothing we could compare this number to in known reality. So already we've hit the stage of transcendent number. Yet we've only just begun with Graham's Number. This number is pathetically tiny in comparison. Don't believe me? Just consider four up-arrows:

3^^^^3 = 3^^^3^^^3 = 3^^^3^^3^^3 = 3^^^3^^3^3^3 = 3^^^3^^7,625,597,484,987 =

3^^3^^3^^3^^3^^ ... ^^3^^3^^3^^3 w/3^^7,625,597,484,987 3s

That's a tetra-tower of 3's 3^^7,625,597,484,987 terms high!! This is difficult to wrap the brain around. The best explanation I can offer is to think of it in stages. Let Stage 1 = 3, Stage 2 = 3^3^3 or 7,625,597,484,987, Stage 3 = 3^3^3^ ... ^3^3^3 w/7,625,597,484,987 3s or 3^^^3, Stage 4 = 3^3^3^ ... ^3^3 w/3^^^3 3s, and in general each stage is 3^3^3^ ... ^3^3^3 with as many 3's as the previous stage. 3^^^^3 is Stage 3^^7,625,597,484,987. MIND=BLOWN!!!

And this is all just G(1)!!!

You've seen how quickly the values have grown for 3^3 (palpable), 3^^3 (astonomical), 3^^^3 (unfathomable), 3^^^^3 (more unfathomable still?!?!), ...

You may have already noticed the pattern that the next entry in the sequence takes the previously defined operator, and computes 3 "that operator" to the previous entry. Example:

3^3 (first entry)

3^^3 = 3^(3^3) (3 exponentiated to 3^3 the previous entry)

3^^^3 = 3^^(3^^3) (3 tetrated to 3^^3)

3^^^^3 = 3^^^(3^^^3) (3 pentated to 3^^^3)

Even this however doesn't really help us make sense of this. Why?! Because we really get grasp the increase in power between exponentiation, tetration, pentation and onwards. Just trying to think about how 3^^^^^3 compares to 3^^^^3 basically becomes impossible:

3^^^^^3 = 3^^^^(3^^^^3)

That's 3 hexated to 3^^^^3 or G(1). Not only do we have to remember what 3^^^^3 is, but we also have to understand hexation which is repetitions of pentation which is repetitions of tetration which is repetitions of exponentiation. To even have a chance of seeing this we've got to come up with a much broader picture. Although large power towers are already incomprehensible, I'll show how everything can be reduced back to them a familiar reference point.

Think of a single power tower. For example 3^^3:

Looks pretty small and harmless in this form, but remember even this number is astronomical in size. Pentation we can think of as a row of power towers, where each power tower describes the number of terms in the power tower to its immediate left. In this form 3^^^3 looks like:

Here we have a row of 3 power towers. The leftmost power tower is 3^^^3. Doesn't seem to bad in this form. How about 3^^^^3? We can think of this as a grid of power towers, in which each row of power towers describes the number of terms in the row directly above it. 3^^^^3 becomes:

We can simplify this picture a bit, by just focusing on the top most row:

This is where things start to get interesting. Since we can think of 3^^^^3 as a row of power towers 3^^^3 terms long, we can think of 3^^^^^3 as a grid of power towers 3^^^^3 terms long! Here's what that looks like:

The minus 2 is due to the fact that I'm excluding the first two rows, of "3", and "3^^^3". This allows me to display the grid as if it were uniform. However, understand that every row has more power towers than the row below it. Now you can probably guess what happens next. Now we can have a cube of power towers! At this point some sort hand would be handy so let:

a^(c)b = a^^^...^^^b w/c ^s

So 3^(6)3 would look something like this:

Now things get really crazy ... imagine continuing to any number of dimensions of power towers ...

To imagine just G(2), you have to imagine going all the way to 3^^^^3 - 3 dimensions!!! There is really no understanding a number like that. Now try to imagine going out 3^(5)3 - 3 dimensions, which is much bigger ... then 3^(6)3 - 3 dimensions, 3^(7)3 -3 dimensions ... Now go out 3^(3^^^^3)3 -3 DIMENSIONS!!! That is G(3). Now keep feeding back the number of dimensions into the result until you get to G(64). That is a truly transcendent number.

Note that this idea goes beyond mere dimensions in a sense, because we're using dimensions to describe dimensions. One way we can think of Graham's Number is as a row of dimensions of power towers. But that suggests a way to continue ... why not have a plane of dimensions, a cube of dimensions, a tesseract of dimensions ... a dimension of dimensions, a row of dimensions of dimensions , ... a dimension of dimensions of dimensions of dimensions of dimensions of dimensions ... etc. As you can see, Graham's Number just opens the door, just a crack, and reveals a world seething with numbers, structures, and patterns. But it never actually takes a step out the door. If Graham's Number is a house then it's a house in the middle of a vast nowhere to explore beyond. Step out of that house and a whole new world of recursive functions opens up! Not only will we explore dimensions of dimensions ... but even what lies beyond that!

But for now the discussion has become too vague to continue meaningfully. We will need to develop stronger systems first. Before we do that however, we should make sense of the three different Graham's Numbers and determine the relative sizes, along with their sequence values ...

Comparing Graham's Numbers

We have seen that there is not one Graham's Number, but in fact three. There is Little Graham that showed up in Graham's original 1971 paper on n-parameter sets. There is the Graham/Gardner Number involving 3's now called Graham's Number, and there is a version of Graham's Number in the book of numbers involving 4's which I'll call the Graham-Conway Number.

Using the above notation in which:

a<c>b = a^^^...^^^b w/c ^s

we can define Little Graham as follows:

Little Graham = g(7)

where g(n) is defined for all n=Z+ as follows:

g(1) = 2<12>3

g(n) = 2<g(n-1)>3 for all n>1

We can define Graham's Number as:

Graham's Number = G(64)

where G(n) is defined for all n=Z+ as follows:

G(1) = 3^^^^3

G(n) = 3<G(n-1)>3 for all n>1

Lastly we can define the Graham-Conway Number as:

Graham-Conway Number = Gc(64)

where Gc(n) is defined for all n=Z+ as follows:

Gc(1) = 4^^^^4

Gc(n) = 4<Gc(n-1)>4 for all n>1

With that established the next natural question is, which of the 3 numbers is largest. Without much thought it should be obvious that:

Little Graham < Graham's Number < Graham-Conway Number

How do we demonstrate this rigorously? Proving Graham-Conway is large than Graham's Number is easy. Simply observe that:

3^^^^3 < 4^^^^4 :: G(1) < Gc(1)

Next we set up the following induction:

Let k be a positive integer such that:

G(k) < Gc(k)

G(k+1) = 3^(G(k))3 < 4^(G(k))4 < 4^(Gc(k))4 < Gc(k+1)

:: G(n) < Gc(n) for all n=Z+

This proves that Graham's Number < Graham-Conway since:

Graham's Number = G(64) < Gc(64) = Graham-Conway Number

:: Graham's Number < Graham-Conway Number

You'll note that not only does this prove that Graham's Number is smaller than Graham-Conway, but it gives us the ability to compare numbers in both of their constructed sequences, even beyond Graham's Number and Graham-Conway. We can see that:

G(a) < Gc(b) : b>a or b=a

But what happens when b<a? It turns out that Gc(b) < G(a) whenever b<a. This requires more work to prove however. The problem stems from the fact that Gc(n) uses 4s while G(n) uses 3's. Do the 4s somehow compensate for all the extra up-arrows with the 3s? Surely not. But how do we account for the incremental improvement the 4s must contribute?

We do this through a "base change". The Left Associative Polyates Lemma (LAPL) can be adapted to this purpose (I'll prove this Lemma in chapter 3.3, but for now we'll simply use the result).

The Left Associative Polyates Lemma (LAPL) can be stated as:

(b<k>m)<k>n < b<k>(m+n) : b,m,n,k=Z+ & b,k>1

A "polyate" refers to the general term for an exponent. LAPL basically says that "polyates add" and that the sum is still larger. Here is how we'll use LAPL to prove that Gc(n) lags behind G(n) when G(n) is given the advantage (is allowed to go first):

To prove the conjecture:

Gc(a) < G(b) : a<b

We will need to prove the conjecture:

1+Gc(a) < G(a+1)

The smallest case is a=1:

1+Gc(1) = 1+4^^^^4 < 4^^^^5 * = (2^^^^2)^^^^5 < 2^^^^7 [LAPL]

< 3^^^^7 < 3^^^^27 = 3^^^^3^3 < 3^^^^3^^^^3 = 3<5>3

< 3<27>3 = 3<3^3>3 << 3<3^^^^3>3 = G(2)

(* The reason this works is because 1+4^n < 4^n + 4^n = 2*4^n < 4*4^n = 4^(n+1). It can be further shown that 1+4^^n < 4^^(n+1) and in general 1+4<k>n < 1+4<k>(n+1). This can be generalized to a rule I call the Ascending One (AO). The proof of this will be covered in 3.3)

Now we set up an induction. Let k be a positive integer such that the following holds:

1+Gc(k) < G(k+1)

Next we begin with 1+Gc(k+1):

1+Gc(k+1) = 1+4<Gc(k)>4 < 4<Gc(k)>5 =

(2<Gc(k)>2)<Gc(k)>5 < 2<Gc(k)>7 [LAPL]

< 3<Gc(k)>7 < 3<Gc(k)>27 = 3<Gc(k)>3<1>3 << 3<Gc(k)>3<Gc(k)>3 =

3<1+Gc(k)>3 < 3<G(k+1)>3 = G(k+2)

Thus by induction we've shown that:

1+Gc(n) < G(n+1) : n=Z+

It immediately from this that since:

Gc(n) < 1+Gc(n)

&

G(a) < G(b) : a<b

that:

Gc(a) < G(a+1) < G(a+2) < G(a+3) < ...

:: Gc(a) < G(b) : a<b

When we combine this with the first statement that:

G(a) < Gc(b) : a=b or a<b

We obtain a definite order for the sequence terms:

G(1) < Gc(1) < G(2) < Gc(2) < G(3) < Gc(3) < G(4) < Gc(4) < ... < G(64) < Gc(64) < ...

With this resolved, the only thing left is to find out where Little Graham and the values g(n) fall along the above sequence. We will want to prove that:

Gc(n) < g(n) : n=z+

&

g(a) < G(b) : a<b

Both of these are made very easy to prove with LAPL. This time the second statement is easier to prove. All we need to show is that g(n) < G(n+1). For the case of n=1 we have:

g(1) = 2<12>3 < 3<12>3 < 3<27>3 < 3<3^3>3 << 3<3^^^^3>3 = G(2)

Next assume k such that:

g(k) < G(k+1)

now we look at case n=k+1:

g(k+1) = 2<g(k)>3 < 3<g(k)>3 < 3<G(k+1)>3 = G(k+2)

g(n) < G(n+1) < G(n+2) < G(n+3) < ...

:: g(a) < G(b) : a<b

From this it immediately follows that Graham's Number is much larger than Little Graham:

Little Graham = g(7) < G(8) << G(64) = Graham's Number

:: Little Graham < Graham's Number

Proving the statement Gc(n) < g(n) is more difficult. In order for the proof to work we actually need to show that 2+Gc(n) < g(n). First we look at case n=1:

2+Gc(1) = 2+4^^^^4 < 4^^^^5 = (2^^^^2)^^^^5 < 2^^^^7 [LAPL]

< 2^^^^16 = 2^^^^2^^3 < 2^^^^2^^^3 < 2^^^^2^^^^3 < 2^^^^2^^^^4 = 2<5>4 = 2<6>3

< 2<7>3 < ... < 2<12>3 = g(1)

Next we assume for the case of n=k that:

2+Gc(k) < g(k)

and we next look at the case n=k+1:

2+Gc(k+1) = 2+4<Gc(k)>4 < 4<Gc(k)>5 = (2<Gc(k)>2)<Gc(k)>5 < 2<Gc(k)>7 [LAPL]

< 2<Gc(k)>16 = 2<Gc(k)>2<2>3 < 2<Gc(k)>2<Gc(k)>3 < 2<Gc(k)>2<Gc(k)>4 =

2<1+Gc(k)>4 = 2<2+Gc(k)>3 < 2<g(k)>3 = g(k+1)

Thus:

2+Gc(n) < g(n) : n=Z+

:: Gc(n) < g(n)

Combining all of these results we can now compare any member of any sequence. When these are put in order we have the following result:

Order of Graham's Sequence Numbers

G(1) < Gc(1) < g(1) < G(2) < Gc(2) < g(2) < ... < G(7) < Gc(7) < g(7) [Little Graham] < G(8) < Gc(8) <

g(8) < ... < G(64) [Graham's Number] < Gc(64) [Graham-Conway Number] < g(64) < ...

:: Little Graham < Graham's Number < Graham-Conway Number

So there you have it. We've explored the history and development of Graham's Number, some of the mathematics involved, considered it's significance, tried to conjure up it's size, and tried to put it into order. Is there anything else we can learn about Graham's Number. Yes. It turns out, despite the fact that we will never be able to compute the full decimal expansion of Graham's Number and could never store all the digits even if we could ... we can still do the next best thing: compute some of it's last digits. Despite how massive the number is, it turns out to be pretty easy to find it's last digit ...

The Last Digits of Graham's Number

We can think of Graham's Number as a string of digits:

XXXXXXXXXX ... ... ... ... XXXXXXXXXX

The X's here represent that they are unknowns. If we read them from left to right, there will be a first digit, a second digit, a third, etc. all the way to the rightmost digit, the last digit. The digits beginning from the first and continuing onwards I call the leading digits, and the digits going from the last digit towards the first I call the terminating digits. One unfortunate consequence of large numbers is that once a large number reaches a certain size (roughly 10^10^10^80 or so) it becomes impossible to know any of the leading digits. Graham's Number is so utterly massive that it left numbers that we can know the leading digits of way way way behind! The good news is that it turns out to be pretty easy to get the terminating digits of Graham's Number. In fact, it turns out to be even easier than finding the terminating digits of a mega.

To find them we exploit a useful property of the way Graham's Number is constructed. Despite how massive Graham's Number is, at the end of the day it could still be expressed simply as:

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

where the number of up-arrows is G(63). Furthermore, every hyper-operator, no matter how large, is simply built out of repetitions of the next lower operator. So for example:

3^^^^3 =

3^^^3^^^3

But these operators are themselves defined with the next lower operator so that we can eventually reduce everything back to exponents. In other words, every number involving up-arrow notation eventually reduces to some power tower no matter how large the value, albeit as a mind-numblingly vast power tower in most case, and the same is true of Graham's Number. Eventually it must reduce to a power tower of the form:

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

where the number of 3's is some massive integer. Despite the fact that we don't know what this integer is, it turns out we don't need to in order to determine the terminating digits of Graham's Number. We know that if we we're to evaluate this power tower it would eventually be reduced to the form:

3^3^3^N

where N is some very massive integer. It turns out that even if we don't know what N is, we can still determine the last digit of Graham's Number using this form. First off, we know from this that Graham's Number is really just a super massive power of 3. Powers of 3 can only end in one of 4 possible ways. Consider:

3^0 = 1

3^1 = 3

3^2 = 9

3^3 = 27

3^4 = 81

3^5 = 243

3^6 = 729

3^7 = 2187

3^8 = 6561

As you can see there is an alternating pattern: 1,3,9,7. The reason for this is because when decimal positions overflow, they always overflow to the left. For this reason left digits are effected by right digits, but right digits are not effected by any digits to it's left. Since the ones place is the right most digit, it is unaffected by any other digits. The result is cyclical behavior because of the limited pool of digits (10), each which must return the same value every time it is multiplied by the same value:

...0 x3 = ...0

...1 x3 = ...3

...2 x3 = ...6

...3 x3 = ...9

...4 x3 = ...2

...5 x3 = ...5

...6 x3 = ...8

...7 x3 = ...1

...8 x3 = ...4

...9 x3 = ...7

It is impossible for the one's place digit not to fall into a repeating cycle because eventually it must exhaust the supply of digits, if it doesn't repeat sooner. It is this property which will allow us to compute the last digit of Graham's Number. In fact, we already know the last digit must be a 1,3,9, or 7 since these are the only choices for a power of 3. We can narrow it down futher however when we realize that:

3^N = ...1 whenever N is divisible by 4

3^N = ...3 whenever N has remainder 1 when divided by 4

3^N = ...9 whenever N has remainder 2 when divided by 4

3^N = ...7 whenever N has remainder 3 when divided by 4

For convenience let:

M mod N = R

The next observation is crucial. Let's look what happens with the power's of 3 when we find their remainders when divided by 4 (this is called their modulo 4)

3^0 mod 4 = 1 mod 4 = 1

3^1 mod 4 = 3 mod 4 = 3

3^2 mod 4 = 9 mod 4 = 1

3^3 mod 4 = 27 mod 4 = 3

etc.

We get an alternating sequence of 1,3. Note that when N is odd, the modulo 4 is always 3:

3^1 mod 4 = 3

3^3 mod 4 = 3

3^5 mod 4 = 3

etc.

Thus we can say that:

since 3^N must be odd

3^3^N = 3^odd

Therefore 3^3^N mod 4 = 3

Therefore 3^(3^3^N) = ...7

Thus we have proven that Graham's Number must end in 7. Through modular arithmetic it's possible to obtain many more terminating digits of Graham's Number. Here are the last 500 digits [5]:

...02425950695064738395657479136519351798334535362521

43003540126026771622672160419810652263169355188780

38814483140652526168785095552646051071172000997092

91249544378887496062882911725063001303622934916080

25459461494578871427832350829242102091825896753560

43086993801689249889268099510169055919951195027887

17830837018340236474548882222161573228010132974509

27344594504343300901096928025352751833289884461508

94042482650181938515625357963996189939679054966380

03222348723967018485186439059104575627262464195387

We can do the same thing for the Graham-Conway Number. Simply observe that Graham-Conway, Gc, should be expressible as 4^^N, or 4^4^N.

Next we observe:

4^0 mod 10 = 1 mod 10 = 1

4^1 mod 10 = 4 mod 10 = 4

4^2 mod 10 = 16 mod 10 = 6

4^3 mod 10 = 64 mod 10 = 4

4^4 mod 10 = 256 mod 10 = 6

etc.

So we see that if N is a positive integer, then 4^N ends in 4 if N is odd, and 6 if N is even.

In 4^4^N however, 4^N must be even, so we have:

4^4^N = 4^even = ...6.

Conclusion

Graham's Number will continue to be "the largest number" for the popular imagination probably indefinitely. Just as Graham's Number has not taken away from the googolplexes infamy as a really large number, later numbers such as TREE(3) will only add to the richness of the discussion. Because of it's status, Graham's Number will continue to be the benchmark, the gold standard, by which rookies will set their sights. In a sense this is appropriate. If your number doesn't even reach this far, then it's not a contender. But for rookies, heed this advice ... even if you surpass this number it doesn't mean you've crested all previous attempts at naming a really large number. There is much more to googology than this! So please don't coming boasting "I've got the largest number" if you've "merely" surpassed Graham's Number. Do more research first before assuming your number is the largest. This is not meant as a discouragement. By all means try to come up with the largest number you can muster. That is the most sincere expression of googology. Just don't be too hasty with your proclaimations.

In the next article we will consider many "naive extensions" on the scheme suggested by Graham's Number. We'll see some examples of people claiming to have named the highest number by naming a number "just slightly larger than Graham's Number". In the process we'll eventually be able to look above the fray and see a much more powerful method for surpassing all this stuff ... countably recursive hierarchies ...

Source Material

[1] http://en.wikipedia.org/wiki/Ronald_Graham

[2] http://www.youtube.com/watch?v=MwPVoFuWARw

[3] http://documents.kenyon.edu/math/BuschurKSenEx2011.pdf

[4] http://www.math.ucsd.edu/~ronspubs/71_04_n_ramsey.pdf

[5] http://en.wikipedia.org/wiki/Graham's_number

[6] http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html