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 !
[Math] Graham’s Number : Why so big
big numbersramsey-theory
Related Solutions
I'm about to prove that Graham's number is a number that is so big there is no way of intuitively grasping the magnitude of it, but in order to do this we must start with the very small and work our way up.
We will start with the number 9 which can represented as 3+3+3. This isn't so bad when you only have three 3's to write down, but what happens if I pick a number that isn't practical to be represented by +3's, like 729, I would need the sum of 243 3's, so now let's use multiplication. 729 can now be represented as 3*3*3*3*3*3 now I can represent larger numbers than before, but I run into the same problem. I can pick a number that isn't practical to be represented by the repetition of the same operator of multiplication.
7,625,597,484,987, for example, is the multiplication of 27 3's. That isn't good way to represent this number so now let's use powers to represent this number which is $3^{3^3}$, another way to represent this is $3 \uparrow 3 \uparrow 3$ where each single arrow is "to the power of operator".
Mathematicians realized when dealing with numbers that aren't practical to write down in one operator, a new operator is required that is more powerful the previous one. Arrow notation is a way of going from one operator to another with ease. $\uparrow \uparrow$ is the next operator up from $\uparrow$, just as $\uparrow$ is the next operator up from multiplication, and just as multiplication is one operator up from addition. So increasing the number of consecutive arrows will increase the ability to work with larger and larger numbers.
So we saw how the size of numbers that were created when using $\uparrow$. Now let's look at the $\uparrow \uparrow$. $3\uparrow \uparrow3\uparrow \uparrow3$ = $3\uparrow \uparrow(3\uparrow3\uparrow3)$=$3\uparrow \uparrow7,625,597,484,987$. Which means this is $\uparrow3$ is used on 3, 7,625,597,484,987 times!
${{{{{{{{{{3}^3}^3}^3}^3}^3}^3}^3}^3}^\cdot\Rightarrow}$ a stack of threes 7,625,597,484,987 high!
To calculate this value start with the top 3 and move downward.
$3^3 = 27$
$3^{27}=7,625,597,484,987$
$3^{7,625,597,484,987}$ is 3,638,334,640,024 digits long.
The fourth 3 is very large, but googolplex is 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 digits long. So still somewhat in our comprehension, but the fifth 3 is way out of our comprehension.
3 is raised to the power of a number that is 3,638,334,640,024 digits long.
Googolplex is 10 raised to the power of a number that is 101 digits long.
So we have used only 5 of the 3's on the 7,625,597,484,987 stack and it already becomes difficult to imagine, but this process is repeated over 7.6 trillion times. Doing this process 5 times took us from 3 to a number that makes googolplex look tiny. So the answer to the stack of 7,625,597,484,987 3's is a stupidly big number. This number is so big that if you memorized all the digits of this number your head would turn into a black hole. The maximum amount of entropy that can be stored in your head carries less information than the information of this stack of 3's.
[ http://m.youtube.com/watch?v=XTeJ64KD5cg ]
$$ \begin{array}{c|l|c|r} \text{operator representation} & \text{value} & \text{number of previous operator equivalent} \\ \hline 3*3*3 & 27 &\text{9 (+3)'s or 3+3+3+3+3+3+3+3+3}\\ 3\uparrow3\uparrow3& 7,625,597,484,987 &\text{27 (x3)'s or $3^{27}$} \\ 3\uparrow\uparrow3\uparrow\uparrow3 & \text {stupidly big} & \text{7,625,597,484,987 ($\uparrow$ 3)'s}\\ 3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3 & G_1 & \text {stupidly big ($\uparrow\uparrow3$)'s} \\ \end{array} $$
If you look at the table above you will notice that $3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3=G_1$.
Why is $G_1$ important? Well I'll get to that in a minute. But first I have to explain that each change from one operation to the next is unimaginably bigger than previous change so you would think that adding a few arrows would quickly get us to Graham's number, but it doesn't. It doesn't even come close.
So what if I were to put a subscript on the arrows to indicate how many arrows I have. So $3\uparrow_{1000000}3$ is one million arrows, so I am one million operations above multiplication and 999998 operations above "stupid big" and the value of each operation is unimaginably bigger than the previous one. So, surely I must have hit Graham's number by now. The answer is no.
Remember $G_1$? Well, I'm going to write this, $3\uparrow_{G_1}3$.
So let's see if I can break this down.
"stupidly big" made googolplex look tiny after 5 of 7,625,597,484,987 iterations. Applying $\uparrow\uparrow3$ to 3 "stupidly big" times gives me $G_1$ and $G_1$ is now going to be the number of times the operator is increased. Where each operation is unimaginably bigger in comparison to the previous one. So how well do I stand against Graham's number at this point? Not even close.
Finally,
$G_2$=$3\uparrow_{G_1}3$
$G_3$=$3\uparrow_{G_2}3$
$G_4$=$3\uparrow_{G_3}3$
$\vdots$
$\vdots$
$G_{64}$=$3\uparrow_{G_{63}}3=\text{Graham's number}$
Basically you want to construct a chain of inequalities that links the smaller expression to the larger expression. Induction is often helpful in these cases.
A useful theorem for Knuth arrows is $(a \uparrow^n b) \uparrow^n c < a \uparrow^n (b+c)$, proven in this paper. It is also proven that $a \uparrow^n c$ is monotonic in $a,n$, and $c$ when $a,c \ge 3$, which is useful as well.
For example, one can easily see that $S < 3 \uparrow\uparrow 6$, so
$$S^{S^{S^\cdots}} = S \uparrow \uparrow S < (3\uparrow\uparrow 6)\uparrow\uparrow(3 \uparrow\uparrow 6) < 3\uparrow\uparrow (6 + 3\uparrow\uparrow 6) < 3 \uparrow\uparrow (3 \uparrow\uparrow 7) < 3 \uparrow\uparrow (3\uparrow\uparrow 3^{3^3}) = 3 \uparrow\uparrow (3\uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow 4 < 3\uparrow\uparrow\uparrow (3 \uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow\uparrow 3 = G_1$$
To address your harder question, first we need to know what $G(0,y)$ is. Since we need $G(0,3) =4$ so that $G(64,3)$ is Graham's number, I will assume that $G(0,y)=4$.
Theorem: $G(n,S) < G(n+1,3)$
We will prove this by induction. First, observe that $G(0,S) = 4 < 3\uparrow\uparrow\uparrow\uparrow 3 = G(1,3)$.
Observe that for $n \ge 3$,
$$S \uparrow^n S < (3\uparrow\uparrow 6)\uparrow^n (3\uparrow\uparrow 6) < (3\uparrow^n 6)\uparrow^n (3\uparrow\uparrow 6) < 3\uparrow^n (6+3\uparrow\uparrow 6) < 3\uparrow^n (3\uparrow\uparrow\uparrow 3) \le 3\uparrow^n (3\uparrow^n 3) = 3\uparrow^{n+1} 3$$
So if we have $G(n,S) < G(n+1,3)$, then $G(n,S)+1 \le G(n+1,3)$, so
$$G(n+1,S) = S \uparrow^{G(n,S)} S < 3 \uparrow^{G(n,S)+1} 3 \le 3 \uparrow^{G(n+1,3)} 3 = G(n+2,3)$$
and the theorem follows by induction.
So in particular, $G(60,S) < G(61,3) < G(64,3)$.
Best Answer
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]:
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.
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”.
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:
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.
“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 authors continue with an understatement that I imagine made them chuckle:
A remark a little later says
but Sbiis Saibian's excellent discussion of this claims, unfortunately without citation:
I will be glad to elaborate on any part of this that is not clear.