Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

OK, let's attempt a sorting of the names having at most three operands. I'll make several observations, and then use them to assemble the order section by section, beginning with the part below googol stack.

• googol bang bang bang $\lt$ googol stack. It seems clear that we shall be able to iterated bangs many times before exceeding googol stack. Since googol bang bang bang is the largest three-operand name using only plex and bang, this means that all such names will interact only with each below googol stack.

• plex $\lt$ bang. This was established in the question.

• plex bang $\lt$ bang plex. This was established in the question, and it allows us to make many comparisons in terms involving only plex and bang, but not quite all of them.

• googol bang bang $\lt$ googol plex plex plex. This is because $g!!\lt (g^g)^{g^g}=g^{gg^g}=10^{100\cdot gg^g}$, which is less than $10^{10^{10^g}}$, since $100\cdot gg^g=10^{102\cdot 10^{100}}\lt 10^{10^g}$. Since googol bang bang is the largest two-operand name using only plex and bang and googol plex plex plex is the smallest three-operand name, this means that the two-operand names using only plex and bang will all come before all the three-operand names.

• googol plex bang bang $\lt$ googol bang plex plex. This is because $(10^g)!!\lt ((10^g)^{10^g})!=(10^{g10^g})!=(10^{10^{g+100}})!\lt (10^{10^{g+100}})^{10^{10^{g+100}}}=10^{10^{g+100}10^{10^{g+100}}}= 10^{10^{(g+100)10^{g+100}}}\lt 10^{10^{g!}}$.

Combining the previous observations leads to the following order of the three-operand names below googol stack:

  googol
  googol plex
  googol bang
  googol plex plex
  googol plex bang
  googol bang plex
  googol bang bang
  googol bang bang
  googol plex plex plex
  googol plex plex bang
  googol plex bang plex
  googol plex bang bang
  googol bang plex plex
  googol bang plex bang
  googol bang bang plex
  googol bang bang bang
  googol stack

Perhaps someone can generalize the methods into a general comparison algorithm for larger smallish terms using only plex and bang? This is related to the topic of the Velleman article linked to by J. M. in the comments.

Meanwhile, let us now turn to the interaction with stack. Using the observations of the two-operand case in the question, we may continue as follows:

  googol stack plex
  googol stack bang
  googol stack plex plex
  googol stack plex bang
  googol stack bang plex
  googol stack bang bang

Now we use the following fact:

• stack bang bang $\lt$ plex stack. This is established as in the question, since $(10\uparrow\uparrow x)!!\lt (10\uparrow\uparrow x)^{10\uparrow\uparrow x}!\lt$ $(10\uparrow\uparrow x)^{(10\uparrow\uparrow x)(10\uparrow\uparrow x)^{10\uparrow\uparrow x}}=$ $(10\uparrow\uparrow x)^{(10\uparrow\uparrow x)^{1+10\uparrow\uparrow x}} 10\uparrow\uparrow 4x\lt 10\uparrow\uparrow 10^x$. In fact, it seems that we will be able to absorb many more iterated bangs after stack into plex stack.

The order therefore continues with:

  googol plex stack
  googol plex stack plex
  googol plex stack bang

• plex stack bang $\lt$ bang stack. To see this, observe that $(10\uparrow\uparrow 10^x)!\lt (10\uparrow\uparrow 10^x)^{10\uparrow\uparrow 10^x}\lt 10\uparrow\uparrow 2\cdot10^x$, since associating upwards is greater, and this is less than $10\uparrow\uparrow x!$. Again, we will be able to absorb many operands after plex stack into bang stack.

The order therefore continues with:

  googol bang stack
  googol bang stack plex
  googol bang stack bang

• bang stack bang $\lt$ plex plex stack. This is because $(10\uparrow\uparrow x!)!\lt (10\uparrow\uparrow x!)^{10\uparrow\uparrow x!}\lt 10\uparrow\uparrow 2x!\lt 10\uparrow 10^{10^x}$.

Thus, the order continues with:

  googol plex plex stack
  googol plex bang stack
  googol bang plex stack
  googol bang bang stack

This last item is clearly less than googol stack stack, and so, using all the pairwise operations we already know, we continue with:

  googol stack stack
  googol stack stack plex
  googol stack stack bang
  googol stack plex stack
  googol stack bang stack
  googol plex stack stack
  googol bang stack stack
  googol stack stack stack

Which seems to complete the list for three-operand names. If I have made any mistakes, please comment below.

Meanwhile, this answer is just partial progress, since we have the four-operand names, which will fit into the hierarchy, and I don't think the observations above are fully sufficient for the four-operand comparisons, although many of them will now be settled by these criteria. And of course, I am nowhere near a general comparison algorithm.

Sorry for the length of this answer. Please post comments if I've made any errors.

The following describes a comparison algorithm that will work for expressions where the number of terms is less than googol - 2.

First, consider the situation with only bangs and plexes. To compare two numbers, first count the total number of bangs and plexes in each. If one has more than the other, that number is bigger. If the two numbers have the same number of bangs and plexes, compare the terms lexicographically, setting bang > plex. So googol plex bang plex plex > googol plex plex bang bang, since the first terms are equal, and the second term favors the first.

To prove this, first note that x bang > x plex for $x \ge 25$. To show that the higher number of terms always wins, it suffices to show that googol plex$^{k+1} >$ googol bang$^k$. We will instead show that $x$ plex$^{k+1} > x$ bang $^k$ for $x \ge 100$. Set $x = 10^y$.

$10^y$ bang $< (10^y)^{10^y} = 10^{y*10^y} < 10^{10^{10^y}} = 10^y$ plex plex

$10^y$ bang bang $< (10^{y*10^y})^{10^{y*10^y}} $

$= 10^{10^{y*10^y + y + \log_{10} y}}$

$= 10^{10^{10^{y + \log_{10} y} (1 + \frac{y + \log_{10} y}{10^{y + \log_{10} y}})}}$

$< 10^{10^{10^{y + \log_{10} y} (1 + \frac{y}{10^{y}})}}$

(We use the fact that x/10^x is decreasing for large x.)

$= 10^{10^{10^{y + \log_{10} y + \log_{10}(1 + \frac{y}{10^{y}})}}}$

$< 10^{10^{10^{y + \log_{10} y + \frac{y}{10^{y}}}}}$

(We use the fact that ln(1+x) < x, so log_10 (1+x) < x)

$< 10^{10^{10^{2y}}} < 10^{10^{10^{10^y}}} = 10^y$ plex plex plex

$10^y$ bang bang bang < $(10^{10^{10^{y + \log_{10} y + \frac{y}{10^y}}}})^{10^{10^{10^{y + \log_{10} y + \frac{y}{10^y}}}}} $

$= 10^{10^{(10^{10^{y + \log_{10} y + \frac{y}{10^y}}} + 10^{y + \log_{10} y + \frac{y}{10^y}})}}$

$= 10^{10^{(10^{10^{y + \log_{10} y + \frac{y}{10^y}}}(1 + \frac{10^{y + \log_{10} y + \frac{y}{10^y}}}{10^{10^{y + \log_{10} y + \frac{y}{10^y}}}})}}$

$< 10^{10^{(10^{10^{y + \log_{10} y + \frac{y}{10^y}}}(1 + \frac{10^{y }}{10^{10^{y}}})}}$

$= 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} + \log_{10}(1+\frac{10^{y }}{10^{10^{y}}}))}}}$

$< 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} + \frac{10^{y }}{10^{10^{y}}})}}}$

$= 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} (1 + \frac{10^{y }}{10^{10^{y}} * (10^{y + \log_{10} y + \frac{y}{10^y}})}))}}}$

$< 10^{10^{10^{(10^{y + \log_{10} y + \frac{y}{10^y}} (1 + \frac{1}{10^{10^{y}} }))}}}$

$= 10^{10^{10^{10^{y + \log_{10} y + \frac{y}{10^y} + \frac{1}{10^{10^{y}} }} }}}$

$< 10^{10^{10^{10^{2y}}}} < 10^{10^{10^{10^{10^y}}}} = 10^y$ plex plex plex plex

We can see that the third bang added less than $\frac{1}{10^{10^y}}$ to the top exponent. Similarly, adding a fourth bang will add less than $\frac{1}{10^{10^{10^y}}}$, adding a fifth bang will add less than $\frac{1}{10^{10^{10^{10^y}}}}$, and so on. It's clear that all the fractions will add up to less than 1, so in general,

$10^y$ bang$^{k} < 10^{10^{10^{\cdot^{\cdot^{10^{y + \log_{10} y + 1}}}}}}{\large\rbrace} k+1\text{ 10's} < 10^{10^{10^{\cdot^{\cdot^{10^{10^y}}}}}}{\large\rbrace} k+2\text{ 10's} = 10^y$ plex$^{k+1}$.

Next, we have to show that the lexicographic order works. We will show that it works for all $x \ge 100$. Suppose our procedure failed; take two numbers with the fewest number of terms for which it fails, e.g. $x s_1 ... s_n$ and $x t_1 ... t_n$. It cannot be that $s_1$ and $t_1$ are both plex or both bang, since then $(x s_1) s_2 ... s_n$ and $(x s_1) t_2 ... t_n$ would be a failure of the procedure with one fewer term. So set $s_1 =$ bang and $t_1 =$ plex. Since our procedure tells us that $x s_1 ... s_n$ > $x t_1 ... t_n$, and our procedure fails, it must be that $x s_1 ... s_n$ < $x t_1 ... t_n$. Then

$x$ bang plex ... plex $< x$ bang $s_2 ... s_n < x$ plex $t_2 ... t_n < x$ plex bang ... bang.

So to show our procedure works, it suffices to show that x bang plex$^k$ > x plex bang$^k$. Set x = 10^y.

$10^y$ bang > $(\frac{10^y}{e})^{10^y} > (10^{y - \frac{1}{2}})^{10^y} = 10^{(y-\frac{1}{2})10^y}$

$10^y$ bang plex$^k > 10^{10^{10^{\cdot^{\cdot^{10^{(y-\frac{1}{2})10^y}}}}}}{\large\rbrace} k+1\text{ 10's}$

To determine $10^y$ plex bang$^k$, we can use our previous inequality for $10^y$ bang$^k$ and set $x = 10^y$ plex $= 10^{10^y}$, i.e. substitute $10^y$ for $y$. We get

$10^y$ plex bang$^k < 10^{10^{10^{\cdot^{\cdot^{10^{(10^y + \log_{10}(10^y) + 1}}}}}}{\large\rbrace} k+1\text{ 10's} = 10^{10^{10^{\cdot^{\cdot^{10^{10^y + y + 1}}}}}}{\large\rbrace} k+1\text{ 10's}$

$< 10^{10^{10^{\cdot^{\cdot^{10^{(y-\frac{1}{2})10^y}}}}}}{\large\rbrace} k+1\text{ 10's} < 10^y$ bang plex$^k$.

Okay, now for terms with stack. Given two expressions, first compare the number of times stack appears; the number in which stack appears more often is the winner. If stack appears n times for both expressions, then in each expression consider the n+1 groups of plexes and bangs separated by the n stacks. Compare the n+1 groups lexicographically, using the ordering we defined above for plexes and bangs. Whichever expression is greater denotes the larger number.

Now, this procedure clearly does not work all the time, since a googol followed be a googol-2 plexes is greater than googol stack. However, I believe that if the number of terms in the expressions are less than googol-2, then the procedure is correct.

First, observe that $x$ plex stack > $x$ stack plex and $x$ bang stack > $x$ stack bang, since

$x$ stack plex $< x$ stack bang $< (10\uparrow\uparrow x)^{10\uparrow\uparrow x} < 10\uparrow\uparrow (2x) < x$ plex stack $< x$ bang stack.

Thus if googol $s_1 ... s_n$ is some expression with fewer stacks than googol $t_1 ... t_m$, we can move all the plexes and bangs in $s_1 ... s_n$ to the beginning. Let $s_1 ... s_i$ and $t_1 ... t_j$ be the initial bangs and plexes before the first stack. There will be less than googol-2 bangs and plexes, and

googol bang$^{\text{googol}-3} < 10^{10^{10^{\cdot^{\cdot^{10^{100 + \log_{10} 100 + 1}}}}}}{\large\rbrace} \text{googol-2 10's} < 10^{10^{10^{\cdot^{\cdot^{10^{103}}}}}}{\large\rbrace} \text{googol-2 10's}$

$ < 10 \uparrow\uparrow $googol = googol stack

and so googol $s_1 ... s_i$ will be less than googol $t_1 ... t_{j+1}$ ($t_{j+1}$ is a stack). $s_{i+1} ... s_n$ consists of $k$ stacks, and $t_{j+2} ... t_m$ consists of at least $k$ stacks and possibly some plexes and bangs. Thus googol $s_1 ... s_n$ will be less than googol $t_1 ... t_m$.

Now consider $x S_1$ stack $S_2$ stack ... stack $S_n$ versus $x T_1$ stack $T_2$ stack ... stack $T_n$, where the $S_i$ and $T_i$ are sequences of plexes and bangs. Without loss of generality, we can assume that $S_1 > T_1$ in our order. (If $S_1 = T_1$, we can consider ($x S_1$ stack) $S_2$ stack ... stack $S_n$ versus ($x T_1$ stack) $T_2$ stack ... stack $T_n$, and compare $S_2$ versus $T_2$, etc., until we get to an $S_i$ and $T_i$ that are different.) $x S_1$ stack $S_2$ stack ... stack $S_n$ is, at the minimum, $x S_1$ stack ... stack, while $x T_1$ stack $T_2$ stack ... stack $T_n$, is, at the maximum, $x T_1$ stack bang$^{\text{googol}-3}$ stack .... stack. So it is enough to show

x S_1 stack > x T_1 stack bang$^{\text{googol}-3}$

We have seen that $x$ bang$^k < 10^{10^{10^{\cdot^{\cdot^{10^x}}}}}{\large\rbrace} k+1\text{ times}$ so $x$ bang$^{\text{googol}-3} < 10^{10^{10^{\cdot^{\cdot^{10^x}}}}}{\large\rbrace} \text{googol-2 times}$, and $x T_1$ stack bang$^{\text{googol}-3} < ((x T_1) +$ googol) stack. Thus we must show $x S_1 > (x T_1) +$ googol.

We can assume without loss of generality that the first term of $S_1$ and the first term of $T_1$ are different. (Otherwise set $x = x s_1 ... s_{i-1}$ where i is the smallest number such that s_i and t_i are different.) We have seen above that it is enough to consider

x (plex)^(k+1) versus x (bang)^k x bang (plex)^k versus x plex (bang)^k

We have previously examined these two cases. In both cases, adding a googol to the smaller leads to the same inequality.

And with that, we are done.

What are the prospects for a general comparison algorithm, when the number of terms exceeds googol-3? The difficulty can be illustrated by considering the following two expressions:

$x$ $S_1$ stack plex$^k$

$x$ $T_1$ stack

The two expressions are equal precisely when k = $x$ $T_1$ - $x$ $S_1$. So a general comparison algorthm must allow for the calculation of arbitrary expressions, which perhaps makes our endeavor pointless.

In light of this, I believe the following general comparison algorithm is the best that can be done.

We already have a general comparison algorithm for expressions with no appearances of stack. If stack appears in both expressions, let them be $x$ $S_1$ stack $S_2$ and $x$ $T_1$ stack $T_2$, where $S_2$ and $T_2$ have no appearances of stack. Replace $x$ $S_1$ stack with plex$^{(x S_1)}$, and $x$ $T_1$ stack with plex$^{(x T_1)}$, and do our previous comparison algorithm on the two new expressions. This clearly works because $x$ $S_1$ stack = $10^{10}$ plex$^{(x S_1 -2)}$ and $x$ $T_1$ stack = $10^{10}$ plex$^{(x T_1-2)}$.

The remaining case is where one expression has stack and the other does not, i.e. googol $S_1$ stack $S_2$ versus googol $T$, where $S_2$ and $T$ have no appearances of stack. Let $s$ and $t$ be the number of terms in $S_2$ and $T$ respectively. Then googol $T$ is greater than googol $S_1$ stack $S_2$ iff $t \ge $ googol $S_1 + s - 2$.

Indeed, if $t \ge $ googol $S_1 + s - 2$,

googol $T \ge$ googol plex$^{\text{googol} S_1 + s - 2} = 10^{10^{10^{\cdot^{\cdot^{10^{100}}}}}}{\large\rbrace} $ googol $S_1$ $+s-1$ 10's $ > 10^{10^{10^{\cdot^{\cdot^{10^{10} + 10 + 1}}}}}{\large\rbrace} $ googol $S_1 +s-1$ 10's > googol $S_1$ stack bang$^s$

$\ge$ googol $S_1$ stack $S_2$.

If $t \le $ googol $S_1 + s - 3$,

googol $T \le$ googol bang$^{\text{googol} S_1 + s - 3} < 10^{10^{10^{\cdot^{\cdot^{10^{103}}}}}}{\large\rbrace} $ googol $S_1$ $+s-2$ 10's $ < 10^{10^{10^{\cdot^{\cdot^{10^{10^{10}}}}}}}{\large\rbrace} $ googol $S_1 +s$ 10's = googol $S_1$ stack plex$^s$

$\le$ googol $S_1$ stack $S_2$.

So the comparison algorithm, while not particularly clever, works.

In one of the comments, someone raised the question of a polynomial algorithm (presumably as a function of the maximum number of terms). We can implement one as follows. Let n be the maximum number of terms. We use the following lemma.

Lemma. For any two expressions googol $S$ and googol $T$, if googol $S$ > googol $T$, then googol $S$ > 2 googol $T$.

This lemma is not too hard to verify, but for reasons of space I will not do so here.

As before, we have a simple algorithm in O(n) time when both expressions do not contain stack. If exactly one of the expressions has a stack, we compute $x$ $S_1$ as above, but we stop if the calculation exceeds n. If the calculation finishes, then we can do the previous comparison in O(log n) time; if the calculation stops, then we know that $x$ $S_1$ stack $S_2$ is larger, again in O(log n) time.

If both expressions have stack, then from our previous precedure we calculate both $x$ $S_1$ and $x$ $T_1$. Now we stop if either calculation exceeds $2m$, where $m = $the maximum length of $S_2$ and $T_2$ (Clearly, $2m < 2n$). If the caculation finishes, then we can do our previous procedure in O(n) time. If the calculation stops prematurely, than the larger of $x$ $S_1$ or $x$ $T_1$ will determine the larger original expression. indeed, if $y = x$ $S_1$ and $z = x$ $T_1$, and $y > z$, then by the Lemma $y > 2z$, so since $y > 2m$, we have $y > z+m$. In our procedure we replace $x$ $S_1$ stack by plex$^y$ and $x$ $T_1$ stack by plex$^z$; since $y$ is more than $m$ more than $z$, plex$^y$ $S_2$ will be longer than plex$^z$ $T_2$, so the first expression will be larger. So we apply our procedure to $x$ $S_1$ and $x$ $S_2$; this will reduce the sum of the lengths by at least $m+2$, having used O(log m) operations.

So we wind up with an algorithm that takes O(n) operations.

We could extend the notation to have suffixes that apply k -> 10^^^k (Pent), k -> 10^^^^k (Hex), etc. I believe the obvious extension of the above procedure will work, e.g. for expressions with plex, bang, stack, and pent, first count the number of pents; the expression with more pents will be the larger. Otherwise, compare the n+1 groups of plex bang and stack lexicographically by our previously defined procedure. So long as the number of terms is less than googol-2, this procedure should work.