Mind sufficiently blown.
I like really big numbers. When I say “really big” I don’t mean numbers like a million or a billion, I mean numbers like Graham’s number which is so big that if you were try to store every digit in your brain it would sooner turn into a black hole before you could get it all in there. Or said another way, a black hole the size of your brain stores less information than there are digits in Graham’s number. Graham’s number and numbers like it are so big that if you were to write one digit on each atom in the entire known universe you would run out of atoms before making a dent in the number. Mind blown.
These simple comparisons are just scraping the surface of why big numbers are so interesting to me. The study of big numbers is sort of like studying the boundaries our universe and what lies beyond. The digits that make up these numbers cannot all be known because our universe isn’t big enough to express them all. Still, mathematicians are able to study these numbers and more importantly the functions that create them.
In order to create these ginormous numbers you need to create fast growing functions which generate them in an efficient manner. Many of these functions are already familiar to you like addition, multiplication and exponentiation. Mathematicians created new functions which scale much faster to larger numbers and its these functions which I find so interesting.
Before jumping in, I need to first warn you that I’m not a mathematician so please don’t take the content in this post as anything but a topical rant from someone interested in the subject. I don’t have any deep knowledge or expertise in these subjects (which should be obvious to anyone who does.)
Pretend there is a contest to see who could write the largest number on a whiteboard. If you went first what would you write?
You could write 999999999 and fill up the entire white board with 9’s. You would end up with a really big number. However if you were to write a bunch of 1’s instead of 9’s you would end up with an even bigger number because 1’s take less space than 9’s do so you would fit more digits on the board.
A similar contest actually happened at MIT on January 26th in 2007. The event was created to get undergraduates interested in computational theory and it got me interested in big numbers. I actually blogged about it in an article that became one of the more popular articles on my blog but I digress.
http://web.mit.edu/arayo/www/bignums.html
To understand the TREE function you have to first understand some of the functions that create big numbers. One of my favorite functions is Knuth’s up arrow notation. This function does iterated exponentiation and allows you to very quickly build big numbers. If you aren’t familiar with how it works I recommend taking a look at the Wikipedia article.
https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem
Here is a simple progression of Knuth’s up arrow notation:
Changing the 2 to a 3 will produce an even bigger number:
Adding one more to make it a 4 makes this ungodly big number:
With up arrow notation you should get a sense for how quickly these numbers can grow. Add a extra arrow and the wheels come off the bus. Here is it is with three arrows:
Lets add one more to the 2 to make it a 3 and see what we get:
That number should knock your socks off. The amazing thing about this sequence is that with only three up arrows and the number 3 we’ve created this monster of a number. However this number isn’t even close to Graham’s number. To get to Graham’s number we need to add more arrows. You saw in the previous example what happened when we added more arrows. The number grew much bigger much faster. That happens because of the recursive nature of the function. It puts the answer to the previous calculation in the most powerful slot in the equation. In this case the exponent.
To get to Graham’s number we need more arrows:
So Graham’s number requires four up arrows to get started. But that only gives us the first of 64 levels. Then we take the answer from each level and use it to define the number of arrows on the next level:
Now we are talking about an insanely large number. The first level G1 is already so big we can’t possibly write it down. G2 takes G1’s answer and adds that many up arrows to make G2. Then G2 becomes the number of up arrows for G3 and we keep going until we get to G64. Wow.
Up arrow notation grows fast and it can create some very big numbers. There are however functions which grow faster than Knuth’s up arrow notation. For example, Conways Chained Arrow notation:
https://en.wikipedia.org/wiki/Conway_chained_arrow_notation
Conways chained arrow notation allow you to build chains which through recursion grow faster than up arrow notation. You should take a look at the Wiki article I linked before reading through the rest of this article if you don’t understand how it works. I’d try to explain it in this article but I couldn’t possibly do it justice.
In Knuth’s up arrow notation we saw that Graham’s number couldn’t actually be represented because we were dealing with so many arrows that we couldn’t ever use that notation to write it all down. Even if we started writing arrows at the beginning of the universe we wouldn’t have made a dent — and that’s just with the arrows. We haven’t even started evaluating the actual number yet. With Conways chained arrow notation on the other hand we can write down a number that is a pretty close approximation to Graham’s number:
So Graham’s number G sits between these two chained numbers.
Graham’s number is actually a really small number compared to TREE(3). I mean it is so small, it might as well be 1. It took me a couple of months of studying before I started to understand how the TREE function worked. The video series from mathematician and professor David Metzler on YouTube helped me understand the progression of big numbers:
I recommend watching this video series. There are about 21 videos and each one is about 20 to 30 minutes long. David goes through each function demonstrating how it works and why it produces big numbers. Eventually he tackles TREE(3).
What is the TREE function?
The TREE function is complicated. The gist is that the function returns the largest sequence of trees that you can build given an input of the number of different types of seeds you can use to build them. It also has some rules that describe how you build these tree sequences.
https://cp4space.wordpress.com/2012/12/19/fast-growing-2/
TREE grows very quickly. Looking at 1 and 2 as inputs shows nothing impressive but plug in a 3 and boom!
When I saw how fast it grew I wanted to understand how it worked. I needed help so I turned to Stack Exchange. I posted an article asking for help:
https://math.stackexchange.com/questions/313134/how-does-tree3-grow-to-get-so-big-laymen-explanation
This was the first time I’ve ever posted a question on Math.Stack Exchange so I was surprised to get a response — a fantastic response — and so quickly. The response came from Deedlit who I believe is a professor who devotes his time to Graph Theory. His response was detailed, long and helped me come to grips on the function. For a few moments I understood the power of TREE.
The really laymen explanation for why TREE(3) is so big goes like this. The TREE(n) function returns the longest possible tree made with N elements that follow very specific rules. These rules guarantee that the resulting longest tree sequence is finite. When the input is 1 or 2, the length of the longest possible tree is small. When it is 3, the length is VERY VERY VERY long. TREE(3) dwarfs big numbers like Graham’s number.
Big numbers like Graham’s number are impossibly big, bigger than our universe. In a way that means that understanding these numbers will help us understand something that goes beyond our universe. There is a godly quality to the study of big numbers. There are very few things in the world that blow my mind like getting a glimpse of the scale and size of these large numbers. You can’t really know how big they are but when you get a taste, oh boy is it sweet.
If you are interested in big numbers a great place to get started is the Googology wiki:
https://googology.wikia.org/wiki/TREE_sequence
The worlds brightest mathematicians hang out there crafting articles and discussions around big numbers and the functions that produce them. Hopefully this article inspired you to learn more about big numbers. If you find this article interesting please recommend it and leave me feedback.
