TREE(3) is a number that turns up easily from just playing a simple mathematical game. Yet, it is so colossally large that it couldn’t conceivably fit in our universe, writes Antonio Padilla.
There are many numbers that fit quite naturally into our everyday lives. For example, the number five counts the founding members of popular UK band One Direction, the number 31 million, how many followers they have on Twitter and the number zero, the number of followers that actually have decent taste in music (sorry!).
But there are also numbers which are important to mathematicians that can never fit into our everyday lives. There are even those that could never fit into the universe. Like TREE(3). Let me explain.
TREE(3) is a colossus, a number so large that it dwarfs some of its gargantuan cousins like a googol (ten to the one hundred), or a googolplex (ten to the googol), or even the dreaded Graham’s number (too big to write). TREE(3) emerges, quite spectacularly, from a mathematical game known as the Games of Trees. The idea of the game is to build a forest of trees from different combinations of seeds. Mathematically, the trees are just coloured blobs (the seeds) connected by lines (the branches). As you build the forest, your first tree must only have at most one seed, your second tree must have at most two seeds, and so on. The forest dies whenever you build a tree that contains one of the older trees. There is a precise mathematical meaning to “contains one of the older trees”, but essentially you aren’t allowed to write down any combinations of blobs and branches that have gone before.
At the turn of the 1960s, the Game of Trees had piqued the interest of the great gossiping Hungarian mathematician Paul Erdős. Erdős is known for being a prolific collaborator, writing papers with over 500 other mathematicians. He was also an eccentric who would show up at the homes of his collaborators without warning. He would expect food and lodging and dismiss their children as “epsilons”, the term mathematicians often use for something infinitesimal. But Erdős would also be armed with a compendium of interesting mathematical problems, and if he had arrived at your door, chances are he thought you could solve it. In this particular story, Erdős was asking anyone who cared to listen if the Game of Trees could last forever. At Princeton University, a young mathematician who had just completed his doctorate was keen to take on Erdős’ latest problem. His name was Joseph Kruskal and he was able to prove that the Games of Trees could never last an eternity, but it could go on for a very long time.
So how long can the game actually last? This depends on how many different types of seed you have. If you only have one seed type, the forest cannot have more than one tree. For two types of seed, you have a maximum of three trees. As soon as we add a third type of seed, the game explodes. The maximum number of trees defies all comprehension, leaping towards a true numerical leviathan known as TREE(3).
Games like the Game of Trees are important. They can often be crucial in understanding processes that involve some sort of branching, such as decision algorithms in computer science, or the evolution of viruses and antibodies in epidemiology. And yet, despite these real-world applications, they can also generate a number that is too big for the universe.
TREE(3) really is that big. To see why, imagine you sit down with a friend and decide to play the Game of Trees with three different types of seed. You know the game can last a while so you play as fast as you can without breaking up the space-time continuum. In other words, you draw a tree every 0.00000000000000000000000000000000000000000005 seconds. That’s equivalent to the Planck time, beyond which the fabric of space and time is overwhelmed by quantum effects.
After a year you will have drawn more than a trillion trillion trillion trillion trees, but you will be nowhere near the end of the game. You play for a lifetime before each of you is replaced by state-of-the-art artificial intelligence that shares your thoughts and personality. The game goes on. The AI mind-clones, powered using solar technology, continue playing long after humanity has destroyed itself through war or climate change or some other madness we haven’t even thought of yet.
After 300 million years, with the world’s continents now merged into one supercontinent and the sun noticeably brighter than before, AI you and your AI friend continue to play at breakneck speed. After 600 million years, the brightening sun has destroyed the Earth’s carbon cycle. Trees and forests can no longer grow, and the oxygen level begins to fall. The sun’s deadly ultraviolet radiation begins to break through Earth’s atmosphere, and by 800 million years, all complex life has been destroyed, except for the two AIs, who continue to play the Game of Trees.
After about 1.5 billion years, with Earth gripped by a runaway greenhouse effect, the Milky Way and Andromeda galaxies collide. The two AIs are too engrossed in their game to notice as the solar system is kicked unceremoniously out of the galaxy as a result of the collision. Billions of years pass as the sun runs out of fuel, turning into a red giant that comes dangerously close to swallowing Earth. Its outer layers drift away and the sun ends its life as a feeble white dwarf, barely bigger than Earth is now. The AIs are now struggling for a reliable source of energy but they continue to play. After a quadrillion years, the sun stops shining altogether. The AIs, starved of energy, have been replaced by an even more advanced technology, drawing energy from the bath of photons left over from the big bang, in the cosmic microwave background radiation. This technology continues to play the Game of Trees. The game is far from over, still some way short of its limit, at TREE(3) moves.
Between around 1040 years and the googolannum (a googol years), the game continues against the backdrop of a spectacular era of black hole dominance, in which all matter has been guzzled by an army of black holes that march relentlessly across the universe. Beyond the googolannum, those black holes have decayed via a process known as Hawking radiation, leaving behind a cold and empty universe, warmed ever so slightly by a gentle bath of radiated photons. And yet, despite all that has passed, the Game of Trees continues.
Can it reach the limit of TREE(3) moves?
It cannot.
After 10 to the 10 to the 122 years, long before the Game of Trees is complete, the universe undergoes a Poincaré recurrence. It resets itself. This is because our universe is thought to be a finite system that can only exist in a finite number of quantum states. Poincaré recurrence, named after the celebrated French mathematician Henri Poincaré, is a property of any finite system, whether it’s the universe or a pack of playing cards. It says that as you move through the system at random, you will return, inevitably, to where you began. With a pack of cards, you shuffle and shuffle, and then after a long wait you eventually shuffle the pack so that all the cards are lined up just as they were when you first opened them. With our universe, it shuffles and shuffles between its various quantum states, and after around 10 to the 10 to the 122 years, it finds itself back in its primordial state.
The Game of Trees could never finish but it did demonstrate our ability to comprehend the incomprehensible, to go to places with mathematics that the physical world could never achieve. The truth is TREE(3) wasn’t too big for Erdős or Kruskal or any of the other mathematicians who contemplated it, but it was too big for the universe.
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Antonio Padilla*