What number is bigger than Grahams?

Some math conjectures and theorems and proofs can take on a profound, quasi-religious status as examples of the limits of human comprehension. TREE(3) is one of those examples.

"You've got all these physical processes going on in the universe all around you. None of them are anything compared to TREE(3)," says University of Nottingham mathmatics professor Tony Padilla in a new episode of the wonderful YouTube series Numberphile.

This content is imported from youTube. You may be able to find the same content in another format, or you may be able to find more information, at their web site.

The Enormous TREE(3) - Numberphile

What is TREE(3)? It's a number. An enormous number beyond our ability to express with written notation, beyond what we could even begin to comprehend, bigger than the notoriously gargantuan Graham's number. We know TREE(3) exists, and we know it's finite, but we do not know what it is or even how many digits there are.

More From Popular Mechanics

The number comes from a simple game of trees—meaning the charts used in graph theory. In this game, you make a forest of trees using seeds. In other words, you make as many tree graphs as you can with a combination of different colored units referred to as "seeds."

There are only two rules. The first rule is that the first tree must contain no more than one seed, the second a maximum of two seeds, the third a maximum of three, and so on. It will look something like this:

The second rule is this: When you make a tree that a previous tree could be contained within, the game end.d. Ss Padilla says, "the forest dies." What exactly does this mean? To put it another way: If you make a tree graph that contains a previous smaller tree graph, the game ends. A tree is said to be contained within another tree if it has seeds at the ends that share a common seed earlier in the graph, or common ancestor, and that pattern is also present in the larger tree graph. The video above will give you a much better sense with examples, but it looks something like this:

The tree on the left contains the tree on the right.

The point of this game is to make as many trees as you can before you inevitably make one that contains a previous tree, and the forest dies and the game ends. To start, just use one type or color of seed, which is TREE(1). Following the two rules to the game, you can quickly see that after the first tree (which is only one seed), a second tree is built that contains the first, and the game ends after just one step. So TREE(1) = 1.

Using just green seeds, the first tree is a single seed, and the second tree is two green seeds, which contains the first tree. The game ends, and TREE(1) = 1.

Now we play the game with two types of seeds, or TREE(2). Using two colors of seeds, such as green and red, you can play the game out to three steps. You start with a green seed, then you build a tree that is two red seeds (which does not contain the first tree), then for the third tree you build one that is just a single red seed (remember, the third tree is a maximum of three seeds, you can always do fewer). On the fourth tree, however, you will inevitably build one that contains one of the earlier trees. The game ends, and TREE(2) = 3.

With two seed colors, you can build three trees before you build one that contains a previous tree. So TREE(2) = 3.

You might be able to guess where it goes from here. When you play the game with three seed colors, the resulting number, TREE(3), is incomprehensibly enormous. Using just three seed types and the two rules to the game, you could keep building trees for the rest of your life, and every descendant of yours could do the same until the end of humanity, until the end of the universe, and even then you would not have a number of trees that is the maximum number you can build without ending the game. You would not even begin to approach TREE(3).

"This is just way bigger than anything that you could even begin to imagine in physics," says Padilla.

One possible beginning sequence to the tree game playing with three seed types. The maximum number of trees you could build without ending the game is TREE(3).

Numerous mathematicians have discovered intriguing things about TREE(3) and this game of trees. For example, American mathematician Joseph Kruskal proved that any TREE(n) will ultimately result in a tree that contains a previous tree, meaning every number for n in Tree(n) will produce a finite number. Interestingly enough, Kruskal's tree theorem required non-finite mathmatics to prove, using advanced techniques such as transfinite arithmetic and ordinal numbers.

However, if you pick a number for n, such as TREE(3) or TREE(4), it is theoretically possible to solve the proof with finite arithmetic and demonstrate that TREE(3) is not infinite—you just couldn't solve the proof in a lifetime, or even in the lifetime of the universe.

Ohio State mathematician Harvey Friedman came up with a way to determine how many "symbols" it would take to prove TREE(3) is finite, meaning plus signs or minus signs or exponents or any mathematical operation. Even that number, the number of symbols, is virtually beyond comprehension. It is expressed as 2↑↑1000. This notation is a type of recurring exponential function, and in this case, it would be 2 to the 2 to the 2 to the 2 to the 2... one thousand times.

This content is imported from youTube. You may be able to find the same content in another format, or you may be able to find more information, at their web site.

TREE(3) (extra footage) - Numberphile

Numberphile performed a fun little thought experiment using this number. Let's say it takes one "Planck time" to work through each symbol. A Planck time is the time it takes for light to travel in a vacuum a distance of 1 Planck, and that number is about 5.39 × 10−44 s. It serves as a decent approximation for the fastest it would even be physically possible to work through each symbol in the TREE(3) proof.

Even at this lightspeed pace, the universe would collapse before the TREE(3) proof would be solved. If the proof could simply appear in completed form, it would be too big to fit inside the universe.

Make sure to watch Numberphile's extra content for this one (above), which dives into the work of Kruskal and Friedman and demonstrates how you can make numbers that dwarf even the towering TREE(3). And next time you find yourself walking through the forest, make sure to take a moment to admire the trees.

Is a Googleplex bigger than Grahams number?

Is Tree 4 bigger than Graham's number?

Is Graham's number bigger than infinity?

Which is bigger tree 3 or Graham's number?