Understanding Graham's Number: A Comprehensive Guide

  • Thread starter jobsism
  • Start date
In summary: The function tree(k) is again extremely fast growing! Much faster than Ackermann's function, Graham's number, or Conway arrows. However, it is not faster than Ackermann's function or Conway arrows when k is very large.
  • #1
jobsism
117
0
Can anyone please explain the largeness of Graham's number? I tried looking it up in google, but didn't quite understand it.
 
Physics news on Phys.org
  • #2
Hello, jobsism. To understand Graham's number, first you need to understand Knuth's up-arrow notation.

Observe that

a*b = a+a+a...+a with b a's.
a^b = a*a*a...*a with b a's.

Continuing in that fashion, define

a^^b = a^(a^(a^(...(a^a)...))) with b a's.
a^^^b = a^^(a^^(a^^(...(a^^a)...))) with b a's.
a^^^^b = a^^^(a^^^(a^^^(...(a^^^a)...))) with b a's,
and so on.

So, for example,

3^^3 = 3^(3^3) = 3^27 = 7625597484987
4^^4 = 4^(4^(4^4)) = 4^(4^256) ~ 4^(1.34 * 10^154) > googolplex
9^^9 = 9^(9^(9^(9^(9^(9^(9^(9^9)))))))

3^^^3 = 3^^(3^^3) = 3^^7625597484987
= 3^(3^(3^(...(3^3)...)) with 7625597484987 3's.
4^^^3 = 4^^(4^^4) > googolplex^^googolplex
= googolplex^(googolplex^(...(googolplex^googolplex)...)) with a googolplex googolplexes.

As you can see, the numbers grow large VERY quickly in up-arrow notation. Four arrows is even more monstrous.

To define 3^^^^3, start with N = 3^^^3 = 3^^7625597484987
= 3^(3^(3^(...(3^3)...)) with 7625597484987 3's. Next, define the sequence

x_1 = 3
x_2 = 3^(3^3) = 7625597484987
x_3 = 3^(3^(3^(...(3^3)...))) with x_2 3's
x_4 = 3^(3^(3^(...(3^3)...))) with x_3 3's
...
x_N = 3^(3^(3^(...(3^3)...))) with x_(N-1) 3's

3^^^^3 is x_N.

Now we are ready to define Graham's Number. Define

g_1 = 3^^^^3
g_2 = 3^^^...^^^3 with g_1 many up-arrows.
g_3 = 3^^^...^^^3 with g_2 many up-arrows.
...
g_64 = 3^^^...^^^3 with g_63 many up-arrows.

Graham's number is g_64. Note that, although we were able to define g_1 in terms of exponents (in a fashion), we cannot describe g_2 and higher without defining up-arrow notation or something similar.

Graham's number is very big.
 
  • #3
Thanks a lot, Deedlit! Wow! It's amazing how huge this number really is!
 
  • #4
Sorry for bothering, but could you please explain Friedman's tree sequence as well? It's just that I have this craze for huge numbers...:D...it started with a googolplex, and then Skewe's number, then graham's and now I'm at the tree sequence! And you explain really well too! :D
 
  • #5
Sorry for taking so long to reply.

the tree sequence is derived from Kruskal's tree theorem, which says that, for an infinite sequence of rooted trees T_i, there exist integers i and j with i < j such that there is an inf-preserving embedding of T_i into T_j. An embedding is a map from the vertices of T_i into the vertices of T_j such that each edge in T_i is mapped to a path of edges in T_j. The term inf-preserving is a little more complicated. For every two vertices A and B, there is a least common ancestor inf(A,B) - it's the lowest vertex that lies above both A and B. An embedding f:T_i -> T_j is inf-preserving if, for any vertices A and B of T_i, f(inf(A,B)) = inf(f(A), f(B)). That is, if A and B map to f(A) and f(B) respectively, then the inf of A and B must map to the inf of f(A) and f(B).

By the way, another way of saying Kruskal's tree theorem is that rooted trees are "well quasi-ordered" undering the ordering of inf-preserving embeddings.

Call a sequence of rooted trees "bad" if there does not exist i,j with i < j and an inf-preserving embedding of T_i into T_j. Kruskal's Theorem proves that there is no infinite bad sequence. However, we can construct arbitrarily long finite bad sequences by simply starting with a tree with n vertices, then subtracting a vertex each step. So, to get a finite number, we need to bound the number of trees we can use.

For a fixed k, let us only consider sequences of rooted trees where the ith tree has at most k+i vertices. Then, we have only a finite number of choices for rooted trees at each step, and Kruskal's tree theorem says that there are no infinite bad sequences. Therefore, by Konig's tree lemma, the number of bad sequences is finite. Let tree(k) be the length of the longest one.

This function tree(k) is extremely fast growing! Much faster than Ackermann's function, or the function used in Graham's number, or even Conway arrows. To describe the rate of growth, you need the extend the fast-growing hierarchy to the level of the small Veblen ordinal. (I can go more into this if you want.)

We can go a little farther by considering labeled trees. Consider rooted trees where the vertices are labeled with some integer from 1 to k, for some fixed k. The the labeled Kruskal tree theorem says that for any infinite sequence of labeled rooted trees, there exists i,j with i<j and an inf-preserving, label-preserving embedding from T_i into T_j. (Here label-preserving means each vertex gets mapped to a vertex with the same label.) To get a finite version, consider only sequences of trees where the ith tree has at most i vertices. Then, as before, Konig's tree lemma proves that there are only finitely many bad sequences. Let TREE(k) be the length of the longest one. Then TREE(k) grows a bit faster than tree(k).

Note that TREE(1) = 1, TREE(2) = 3, and TREE(3) > tree(7000), which is positvely enormous. The jump is quite striking!

If you are interested in big numbers, you may also want to take a look at

Ackermann function
Conway chained arrow notation
Bird's array notation
Goodstein sequences
Paris-Harrington theorem
Hercules and the Hydra game
fast-growing hierarchy (and then look up ordinals!)

and take a look at the informative thread

http://forums.xkcd.com/viewtopic.php?t=7469"

although there is a lot to sift through...
 
Last edited by a moderator:
  • #6
nice nice "))
 

1. What is Graham's Number?

Graham's Number is a very large number that was first described by mathematician Ronald Graham in 1977. It is an upper bound on the solution to a problem in the field of Ramsey theory, and is often used as an example of a number that is too large to be meaningfully comprehended.

2. How many digits does Graham's Number have?

The exact number of digits in Graham's Number is unknown, but it is estimated to be around 107 digits long. This makes it significantly larger than other well-known large numbers, such as a googol (1 followed by 100 zeros) or a googolplex (1 followed by a googol zeros).

3. Can Graham's Number ever be written out in its entirety?

No, it is physically impossible to write out Graham's Number in its entirety, even if you had all the paper and ink in the world. This is due to the size of the number and the limitations of the physical universe.

4. How is Graham's Number used in mathematics?

Graham's Number is used in mathematical proofs and research related to Ramsey theory, a branch of mathematics that studies patterns in large sets of objects. It is also used as an example of a number that is too large to be practically comprehended or calculated.

5. Is there any practical application for Graham's Number?

Currently, there are no known practical applications for Graham's Number. However, it has sparked interest and discussion in the mathematical community and has been used as a benchmark for large numbers in fields such as computer science and cryptography.

Similar threads

  • General Math
Replies
11
Views
1K
  • Science Fiction and Fantasy Media
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
23
Views
24K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
294
  • General Math
Replies
12
Views
3K
  • Biology and Chemistry Homework Help
Replies
4
Views
947
  • Other Physics Topics
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
14
Views
493
  • Sci-Fi Writing and World Building
2
Replies
41
Views
3K
  • Programming and Computer Science
Replies
2
Views
630
Back
Top