Graham's Number : Why so big?

Can someone give me an idea of how R.Graham reached Graham's Number as an upper bound on the solution of the related problem ? Thanks !

Solution 1:

This post appears long and frightening, but I hope you will not be put off, because the topic is not actually hard to understand. It is long because I explained a lot of things from first principles. I did this because I thought the answer would be of interest to a general audience and because the branch of mathematics is not that well-known. So there is a lot of explanation, but not much is difficult.

First, a disclaimer. Graham's Number is usually cited as the largest number ever to appear in a mathematical proof. There is no evidence for this, and in fact the claim is false on its face, because Graham's Number does not actually appear in the proof that it is claimed to appear in. (It can't be the largest number ever to appear in a mathematical proof if it doesn't actually appear in a mathematical proof.) According to these posts by John Baez [1] [2]:

I asked Graham. And the answer was interesting. He said he made up Graham's number when talking to Martin Gardner! Why? Because it was simpler to explain than his actual upper bound - and bigger, so it's still an upper bound!

Martin Gardner then wrote about the number that Graham described, which is not the number from the proof, and the rest is history.

Now what is the number from the proof? Here there is some interesting mathematics.

The question addressed by Graham's Number belongs to the branch of mathematics known as Ramsey theory, which is not at all hard to understand. It can roughly be described as the study of whether a sufficiently large structure, chopped into pieces, must still contain smaller structures. This is a rather vague explanation, so I will give two of the canonical examples.

1. Ramsey's theorem. Let $n$ and $k$ be given. Then there exists a number $R(n;k)$ such that, if you take a complete graph of at least $R(n;k)$ vertices, and color its edges in $k$ different colors, then there must be a complete subgraph of $n$ vertices whose edges are all the same color.

   A frequently-cited special case of this theorem says that $R(3;2) = 6$: if you have a party with at least 6 guests, then there must be 3 guests who have all met one another before, or 3 people who have never met; it is impossible that every subset of three guests has both a pair of people who have met and a pair of people who have not. (With only five guests, this is possible.) Here the two “colors” are “have met before” and “have not met before”.

2. Van der Waerden's theorem. Let $n$ and $k$ be given. Then there exists a number $W(n;k)$ such that, if you take an arithmetic progression of length $W(n;k)$, and color its elements in $k$ different colors, it must contain an arithmetic progression of $n$ elements that are all the same color.

In both these examples you can see the general pattern: we have some large structure (a graph of $R(n;k)$ vertices in one case, an arithmetic progression of $W(n;k)$ elements in the other) and we divide the structure into $k$ parts and ask if one of the parts still contains a sub-structure of size $n$.

The proofs of these theorems are constructive. For example, the proof of van der Waerden's theorem allows one to calculate that for $W(3;2) \ge 325$ suffices: if you color the integers $\{1, \ldots, 325\}$ with $k=2$ colors, then there must be an $n=3$-term arithmetic progression whose elements are all one color, and the proof shows you how to take an arbitrary coloring of $\{1, \ldots, 325\}$ and explicitly find the $3$-term subprogression of all one color.

But the $\{1, \ldots, 325\}$ is rather silly, because in fact the same is true of $\{1, \ldots, 9\}$, as is easily shown. So the proof gives an upper bound of $325$ when the correct answer is $9$. This is typical of theorems in Ramsey theorem: the proof tells you that the number exists and is at most some large number, but then closer investigation reveals that it is really some considerably smaller number. The corresponding overestimate for $W(3;3)$ is that the proof tells you that $$W(3;3) \le 7\cdot\left(2\cdot3^7+1\right)\left(2\cdot3^{\left(2\cdot3^7+1\right)}+1\right),$$

a number with $2095$ digits, but exhaustive computer search quickly reveals that actually $W(3;3)=27$.

The reason for these rapidly-growing bounds is that typically the proofs proceed by induction, and one shows that if there are sufficiently many size-$n-1$ structures, then two of them must have their subcomponents colored exactly the same, and this allows one to find sub-parts of those size-$n-1$ structures that work together to form a size-$n$ structure of all one color. But a size-$n-1$ structure with $S(n-1)$ subcomponents will have something like $k^{S(n-1)}$ ways its components can be colored, so “sufficiently many” means something like $k^{S(n-1)}$, and the number required looks something like an exponential tower of $k$'s of height $n$, that is something like $\left.k^{k^{⋰^k}}\right\} \text{height $n$}$; you can see this happening in the $W(3;3)$ example above, where the third factor is an embellished version of $3^{3^3}$. When the structures one is forming are more complicated, then instead of needing only two size-$n-1$ structures colored the same, one might need an increasingly large number of such structures, and so perhaps you can imagine how the number required increases even faster than an exponential tower.

(That was the crucial paragraph that really answers your question, so I apologize for being so vague; please let me know if you want me to elaborate or provide a specific example.)

Enormous numbers are quite commonplace in Ramsey theory, and so the Graham's Number might have some competition even in its own field.

The particular problem discussed in the Graham's Number paper, “Ramsey's theorem for $n$-parameter sets” is rather general, but the enormous number (not the one described by Gardner) is an upper bound for a problem very similar to the ones I described above:

We recall that by definition $N(1, 2, 2)$ is an integer such that if $n\ge N(1, 2, 2)$ and the $\binom{2^n}{2}$ 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.

That is, Graham and Rothschild are investigating a problem that, in this special case, involves taking a certain $n$-dimensional object, coloring its 1-dimensional subobjects with 2 colors, and looking for a single-colored 2-dimensional subobject; $N(1,2,2)$ is the smallest number of dimensions that such an object must have in order to guarantee a single-colored 2-dimensional subobject.

Let $N^*$ denote the least possible value $N(1,2,2)$ can assume. We introduce a calibration function $F(m,n)$ with which me may compare our estimate of $N^*$. This is defined recursively as follows: $$\begin{align} F(1,n)=2^n \qquad F(m,2)=4 &\qquad m\ge 1, n\ge 2, \\ F(m,n) = F(m-1, F(m,n-1)) & \qquad m\ge2, n\ge 3. \end{align} $$ 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)$.

“A few small values” here is a joke. $F(3,3)$ is already $2^{16}=65536$. $F(3,4)$ is a tower $2^{2^{⋰^2}}$ of height $65536$. $F(3,5)$ is a similar tower of height $F(3,4)$.

Finally, the bound:

The best estimate we obtain this way is roughly $$N^* \le F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).$$

The authors continue with an understatement that I imagine made them chuckle:

On the other hand, it is known only that $N^*\ge 6$. Clearly, there is some room for improvement here.

A remark a little later says

in fact, the exact bound is probably $<10$.

but Sbiis Saibian's excellent discussion of this claims, unfortunately without citation:

It was recently proved that the solution could not be smaller than $11$.

I will be glad to elaborate on any part of this that is not clear.