Summary of "TREE vs Graham's Number - Numberphile"

Purpose and conclusion

Compare the growth rates of two famously enormous constructions — Graham’s number (built from Knuth up-arrows) and the TREE sequence (from a graph/tree-growth game) — and answer which is larger: TREE(Graham’s number) or Graham(TREE(64)). Conclusion: the TREE sequence has far greater growth power, so TREE(Graham’s number) is larger than Graham(TREE(64)).

Final comparison: TREE(g(64)) > g(TREE(64)). TREE grows faster than the standard fast-growing hierarchy levels discussed, while Graham’s sequence does not.

Quick review of the two constructions

Graham’s sequence g(n)

Built using Knuth’s up-arrow notation:
- A single arrow a↑b = a^b.
- Double arrow = repeated exponentiation (tetration), triple arrow = repeated double-arrow, etc.
Recursive definition (high level):
- g(1) is already extremely large (e.g., 3 with several up-arrows to 3).
- g(n+1) is defined using g(n) as the number of up-arrows in the expression.
- Continue up to g(64) to obtain Graham’s number, an astronomically huge value.

TREE(n)

Comes from a finite “tree-growing” game with labeled seed types and rules that force certain patterns.
Definition (high level):
- Play the tree-growing game with n different labels; grow finite trees until a forbidden/inevitable configuration appears.
- The maximal length (or bound) before such a configuration must appear defines TREE(n).
Known values:
- TREE(1) = 1, TREE(2) = 3.
- TREE(3) is unimaginably large — vastly bigger than Graham’s number.
The TREE sequence grows extremely fast and dwarfs many other fast-growing constructions.

Order-of-operations principle (illustrative example)

General observation: when composing two growth operators of different strengths, applying the more powerful operator last typically produces a vastly larger result.
Simple example:
- Let p(n) = 2^n (exponential) and q(n) = n^2 (quadratic). For sufficiently large inputs, composing so the exponential is applied last yields larger outputs.
Applied to our problem:
- Because TREE is the more powerful growth operator than the process that builds Graham’s sequence, composing so that TREE is the outer operator (i.e., TREE(g(64))) produces the larger value. The presenter confirms this intuition.

Measuring “growth power”: fast-growing hierarchies and ordinals

Fast-growing hierarchies give a disciplined framework for comparing rates of growth.
Construction idea:
- Start with the successor function s(n) = n + 1 (smallest growth).
- Define a sequence of functions by iterated application:
  - f1(n): iterate s on n, n times (roughly linear).
  - f2(n): iterate f1 on n, n times (multiplicative/exponential behavior).
  - f3, f4, … each step moves to higher operations (exponentiation, tetration, pentation, …).
- Iterating “one more time” dramatically increases growth.
Ordinal indices:
- Finite indices 0, 1, 2, … correspond to the finite ladder above.
- To escape all finite levels use ordinal indices:
  - Define f_ω(n) = f_n(n) (diagonalization). f_ω dominates every f_k for finite k.
  - Then define f_{ω+1}, f_{ω+2}, …, f_{ω·2}, f_{ω^2}, …, moving through larger ordinals.
- This continues through ε0, the Veblen hierarchy, up to ordinals like the Feferman–Schütte ordinal (Γ0) and beyond.
Each larger ordinal index defines a function that outpaces all earlier ones; this provides a formal way to compare very large constructions.

Where Graham’s sequence and TREE sit in that framework

Graham’s sequence:
- Extremely large but placeable fairly early in the transfinite-indexed fast-growing hierarchy.
- It is “tame” compared to many transfinite constructions — it can be matched by functions indexed at relatively small transfinite levels (for example at levels like ω+1-style constructions).
TREE sequence:
- Grows far faster than the standard hierarchy levels described (including those reached by typical constructive ordinal methods such as the Veblen hierarchy up to Γ0).
- TREE outruns the system of functions built by the ordinary iterative/ordinal-indexed recursion discussed; it is effectively “off the scale” relative to those canonical fast-growing functions.
Consequence:
- Since TREE occupies a strictly higher growth-power position in the hierarchy than Graham’s sequence, applying TREE to Graham’s number yields a larger value than applying Graham’s sequence to TREE(64).

Key lessons and takeaways

Composition order matters: to maximize the result from two growth mechanisms, apply the stronger (faster-growing) mechanism last.
Fast-growing hierarchies and ordinal indexing provide a formal way to compare extremely fast-growing sequences and functions.
While Graham’s number is astronomically large, it is still small relative to many transfinite-indexed fast-growing functions; TREE(3) and the TREE sequence exceed essentially all of those and produce numbers unimaginably larger than Graham’s number.
Final answer: TREE(g(64)) > g(TREE(64)).

Methodologies / procedures described

How Graham’s sequence is built (high level):
- Start with a very large base using up-arrow notation (g(1) uses multiple up-arrows).
- Let g(n+1) use g(n) as the number of up-arrows in the next expression.
- Continue to g(64) to obtain Graham’s number.
How TREE(n) is defined (high level):
- Play the finite tree-growing game with n different labels.
- Grow trees under the game’s rules until a forbidden/inevitable configuration appears.
- The maximal play length or bound before that inevitable configuration defines TREE(n).
- Known values: TREE(1) = 1, TREE(2) = 3, TREE(3) is astronomically huge.
How to build fast-growing functions and compare growth:
- Start from s(n) = n + 1 and iteratively define f1, f2, f3, … by repeated self-iteration.
- Use ordinal indices to step beyond all finite iterations: f_ω, f_{ω+1}, etc., continuing through ordinal constructions (ω·2, ω^2, ε0, Veblen, Γ0, …).
- Compare any given sequence by identifying how high in the ordinal-indexed hierarchy it must be placed to match its growth.

Speakers / sources featured

Presenter / main speaker (unnamed in the transcript; Numberphile’s presenting mathematician)
Brady (interviewer, named in the subtitles)

(Other names mentioned were references or topics — e.g., Graham, Feferman–Schütte ordinal (Γ0), ε0, Veblen hierarchies — but the identifiable speakers in the transcript are the Presenter and Brady.)