If you are a keen-ish recreational mathematician then you may be aware that the world's largest number - short of infinity, naturally - is Graham's Number, an astoundingly large integer used as the upper bound of a proof in graph theory.
Specifically, Graham's Number is the largest number to have found a mathematical use. Naturally, any number you can describe can simply be increased by 1 to get a larger one.
What you may not be aware of is just how much closer to infinity mathematicians have managed to get.
Jonathan Bowers' "Exploding Array Function" is a highly recursive system of notation capable of expressing numbers unimaginably larger than anything found in Donald Knuth's up-arrow notation, John Conway's chained arrow notation or Steinhaus-Moser notation.
Bowers' notation is extremely versatile and powerful and, in the main, logically constructed. It serves as a good extension to existing mathematical functions for generating large numbers. Unfortunately, the web pages on which Bowers himself explains his notation are exceptionally poorly designed and his mathematical explanations - invariably and inexplicably presented in-line - are more or less incoherent. They take some interpretation.
Because I feel Bowers' notation is not without merit, I have spent some time deciphering his writings in order to present them to a wider audience.
The array notation Bowers has devised has several distinct layers of complexity. To deal with all these layers at once would be too tedious to do in a single article, so here we will only deal with the simplest variety of array notation, linear arrays.
In other words, what you are about to read is part one. Of four.
- A "Bowers array", A, is a finite sequence of "entries". The default value of an entry in an array is 1. Trailing ones can always be safely ignored - or, alternatively, arrays which are too short can always be padded out with additional ones if necessary. Array entries are separated by commas and the array as a whole is surrounded by angle brackets: technically we should use 〈 and 〉 (HTML codes: ⟨ and ⟩) for these, but since they are not fixed-width, I am settling for < and >.
- The first entry of an array is the "base", b. An array always evaluates to a (usually very, very, very large) power of this base.
- The second entry of an array is the "prime entry", p. If an array is a single entry, <b>, then we pad it out with a one to give <b>=<b,1>, and p=1.
- Following this, the array will contain a sequence of zero or more ones, followed by the first non-1 entry, which is called the "pilot", d. Note that the pilot may be simply the third entry in the array.
- The entry immediately before the pilot is the "copilot". If the pilot is the third entry, the copilot and the prime entry are the same entry. The rest of the time, the copilot is equal to 1.
- The rest of the array's entries are unnamed. We will use a # as a variable to signify the remainder of the array when necessary.
- The "airplane" consists of the pilot and all its previous entries, including the copilot, the prime entry and the base.
- The "passengers" are all the entries in the airplane except the pilot and the copilot. This will always include the prime entry and the base.
In other words
copilot/prime entry | base | pilot | | | | | | A = <b,p,d,#> | passenger prime entry | | copilot | | base | | pilot | | | | | | | | A = <b,p,1,d,#> \_/ | passengers prime entry copilot | | base | | pilot | | | | | | | | A = <b,p,1,...,1,1,d,#> \_________/ | passengers
Rules for evaluating an array
Let v(A) be the value expressed by an array A once fully evaluated.
- If p=1 then v(A)=b, regardless of what comes after p.
- If there is no pilot, then v(A)=bp.
- Otherwise, p>1 and the pilot exists. In this case:
- Decrement the pilot.
- Let all passengers take on the base value. Note that the prime entry is among the passengers, and the base value remains unchanged.
- Replace the copilot with v(A'), where A' is the original array, except with the prime entry decremented.
- Leave the remainder of array unchanged.
<b,1,#> = b, for any # <b> = <b,1> = b <b,p> = bp <b,p,d,#> = <b,v(<b,p-1,d,#>),d-1,#> = ... <b,p,1,d,#> = <b,b,v(<b,p-1,1,d,#>),d-1,#> = ... <b,p,1,1,d,#> = <b,b,b,v(<b,p-1,1,1,d,#>),d-1,#> = ... <b,p,1,1,1,d,#> = <b,b,b,b,v(<b,p-1,1,1,1,d,#>),d-1,#> = ... ... <b,p,1,...,1,1,d,#> = <b,b,b,...,b,v(<b,p-1,1,...,1,1,d,#>),d-1,#> = ... \_____/ \_____/ \_____/ n n n
This is all pretty abstract at the moment. How would this work for, say, the smallest non-trivial arrays? Let's start with
<b,p,2> = <b,v(<b,p-1,2>)> = b^<b,p-1,2> = ... = b^^p <b,p,3> = <b,v(<b,p-1,3>),2> = b^^<b,p-1,3> = ... = b^^^p <b,p,d> = <b,v(<b,p-1,d>),d-1> = b^^^...^<b,p-1,d> = ... = b^^^...^p = hyper(b,d+2,p) \_____/ \_____/ d-1 d
So far, so good. This is exactly the same recursive relation as you'll find used in Knuth's up-arrow notation and with the hyper operator, both of which should be fairly familiar to you.
The real question is where we go from here to generate larger numbers. This question does not have an obvious answer; many are equally plausible. Linear array notation's answer is this: we will generate the number of arrows (d here) using arrow notation again.
The simplest non-trivial four-entry array is:
<b,2,1,2> = <b,b,v(<b,1,1,2>),1> = <b,b,b> = b^^^...^b \_____/ b
In other words, we take b and substitute it in as the number of arrows we use. Call this number X. Next:
<b,3,1,2> = <b,b,v(<b,2,1,2>),1> = b^^^...^b \_____/ b^^^...^b \_____/ b
Here, we have used X as the number of arrows to create a third tier in our construction and a new number, Y. Even with b=3 this is a fairly large number.
<b,p,1,2> = b^^^...^b \ \_____/ | . | . |p . | \_____/ | b /
Each increment of p increments the number of tiers in our construction and makes the final result that much bigger. As a pertinent example:
3^^^...^3 \ \_____/ | . | <3,64,1,2> = . |64 . | \_____/ | 3 / 3^^^...^3 \ \_____/ | . | Graham's number = . |64 . | \_____/ | 4 / 3^^^...^3 \ \_____/ | 3^^^...^3 \ . | \_____/ | . | . | <3,65,1,2> = . |65 = . |64 \_____/ | . | 3^^^3 | \_____/ | \_/ | 7,625,597,484,987 / 3 /
Therefore, though Graham's number - which is the largest integer to have yet found a mathematical use, remember - cannot be conveniently expressed in linear array notation, we have established at least that <3,64,1,2> < Graham's number < <3,65,1,2>.
Already, then, we are moving beyond the largest useful numbers, and already another key point is driven home to us: if we wish to keep our notation concise, we are strictly limited in the number of different integers we can describe. The gulf between <3,64,1,2> and <3,65,1,2> is gigantic, but almost none of the numbers in that interval can be expressed using linear array notation. We are sacrificing precision for scope, here.
Anyway. The next step linear array notation makes is to begin concisely expressing the number of tiers in the tower we just constructed.
<b,2,2,2> = <b,<b,1,2,2>,1,2> = <b,b,1,2> b^^^...^b \ \_____/ | . | = . |b . | \_____/ | b /
Skip to the end:
<b,p,2,2> = <b,<b,p-1,2,2>,1,2> b^^^...^b \ \_____/ | . | = . |<b,p-1,2,2> . | \_____/ | b / = ... b^^^...^b \ \ \_____/ | | . | | = . | ... |b . | | \_____/ | | b / / \_________________/ p
Pretty intimidating, hmm? We can now construct a tower of b tiers, take the number that tower represents, construct a new tower of that many tiers, take that number, and keep going... more or less forever!
I'll just go one more step here so you get the idea. We can now take the number of towers - the length of our street, metaphorically speaking - and use linear array notation to generate that number.
<3,3,3,2> = <3,<3,2,3,2>,2,2> = <3,<3,<3,1,3,2>,2,2>,2,2> = <3,<3,3,2,2>,2,2> = 3^^^...^3 \ \ \_____/ | | . | | . | ... | 3 . | | \_____/ | | 3 / / \__________________/ 3^^^...^3 \ \_____/ | . | . | 3^^^...^3 . | \_____/ \_____/ | 3^^^3 3 /
Get the idea now? The third entry in the array expresses the number of levels of recursion we undergo. A 1 means we just do tiers. A 2 means we do towers of tiers. A 3 means we do tiers of towers of tiers. A 4 means towers of tiers of towers of tiers. You get the idea. The p in the second entry is just the "coarse focus" for the top level of recursion.
Now, observe that all this time we have still only been dealing with four-entry arrays, and all this time the last entry in that four-entry array has been a 2.
By increasing that fourth entry to a 3, we can now use linear array notation to express... you guessed it... the number of levels of recursion in the above construction.
<b,2,1,3> = <b,b,v(<b,1,1,3>),2> = <b,b,b,2>
That's b levels of recursion.
<b,3,1,3> = <b,b,v(<b,2,1,3>),2>
That's <b,2,1,3> levels of recursion.
Getting lost yet? As the second entry increases, we can now control the number of times we back-substitute the number of times we recurse the process of constructing the number of arrows between the two bs in the final answer. Which, if you know the hyper operator or arrow notation, is a pretty recursive thing in itself.
The number of levels of the number of levels of recursion going on here rapidly becomes dizzyingly large. And we are still only dealing with four-entry arrays. For five-entry arrays and larger, it's pointless to even try to begin fully evaluating them.
Named integers in this range
The other major part of Bowers' efforts towards generating big numbers is naming them. He isn't going to win any awards for what he's come up with - not only do NONE of these numbers have mathematical uses (and it would take a brave mathematician indeed to find any), the naming system itself is pretty silly and somewhat inconsistent. Nevertheless, you may find them to be some helpful points of reference in the wilderness.
(Note that some numbers have more than one name and these are not in increasing size order, though it would be fairly simple to rearrange them as such. Also "group" is not used in the mathematical sense.)
- corporal = <10,100,1,2>
- corporalplex = <10,corporal,1,2>
- general = <10,10,10,10>
- generalplex = <10,10,10,general>
- googol = <10,100> (not Bowers' invention)
- googolplex = <10,googol> (not Bowers' invention)
- giggol = <10,100,2>
- gaggol = <10,100,3>
- geegol = <10,100,4>
- gigol = <10,100,5>
- goggol = <10,100,6>
- gagol = <10,100,7>
- boogol = <10,10,100>
- boogolplex = <10,10,boogol>
- biggol = <10,10,100,2>
- biggolplex = <10,10,biggol,2>
- baggol = <10,10,100,3>
- baggolplex = <10,10,baggol,3>
- beegol = <10,10,100,4>
- beegolplex = <10,10,beegol,4>
- bigol = <10,10,100,5>
- boggol = <10,10,100,6>
- bagol = <10,10,100,7>
- troogol = <10,10,10,100>
- troogolplex = <10,10,10,troogol>
- triggol = <10,10,10,100,2>
- triggolplex = <10,10,10,triggol,2>
- traggol = <10,10,10,100,3>
- traggolplex = <10,10,10,traggol,3>
- treegol = <10,10,10,100,4>
- trigol = <10,10,10,100,5>
- troggol = <10,10,10,100,6>
- tragol = <10,10,10,100,7>
- quadroogol = <10,10,10,10,100>
- quadroogolplex = <10,10,10,10,quadroogol>
- quadriggol = <10,10,10,10,100,2>
- quadriggolplex = <10,10,10,10,quadriggol,2>
- quadraggol = <10,10,10,10,100,3>
- quadreegol = <10,10,10,10,100,4>
- quadrigol = <10,10,10,10,100,5>
- quadroggol = <10,10,10,10,100,6>
- quadragol = <10,10,10,10,100,7>
- quintoogol = <10,10,10,10,10,100>
- quintoogolplex = <10,10,10,10,10,quintoogol>
- quintiggol = <10,10,10,10,10,100,2>
- quintaggol = <10,10,10,10,10,100,3>
- quinteegol = <10,10,10,10,10,100,4>
- quintigol = <10,10,10,10,10,100,5>
- sextoogol = <10,10,10,10,10,10,100>
- septoogol = <10,10,10,10,10,10,10,100>
- octoogol = <10,10,10,10,10,10,10,10,100>
- tritri = <3,3,3>
- tetratri = <3,3,3,3>
- pentatri = <3,3,3,3,3>
- hexatri = <3,3,3,3,3,3>
- heptatri = <3,3,3,3,3,3,3>
- ultatri [sic] = <3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3> (27 3s)
- supertet = <4,4,4,4>
- superpent = <5,5,5,5,5>
- superhex = <6,6,6,6,6,6>
- supersept = <7,7,7,7,7,7,7>
- superoct = <8,8,8,8,8,8,8,8>
- superenn = <9,9,9,9,9,9,9,9,9>
- superdec = <10,10,10,10,10,10,10,10,10,10>
- tridecal = <10,10,10>
- grand tridecal = <10,10,10,2>
- tetradecal = <10,10,10,10>
- pentadecal = <10,10,10,10,10>
- pentadecalplex = <10,10,10,10,pentadecal>
- hexadecal = <10,10,10,10,10,10>
- hexadecalplex = <10,10,10,10,10,hexadecal>
- heptadecal = <10,10,10,10,10,10,10>
- octadecal = <10,10,10,10,10,10,10,10>
- ennadecal = <10,10,10,10,10,10,10,10,10>
- duperdecal = <10,10,10,10,10,10,10,10,10,10>
Okay. For the sake of morbid interest, what's next?
Next? Two-dimensional arrays.