Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



BIG NUMBERS #3
Posted:
Apr 8, 2002 6:57 PM


I'm still working on an extensive revision of my sci.math post "GRAHAM'S NUMBER AND RAPIDLY GROWING FUNCTIONS" at
http://groups.google.com/groups?selm=28ae5e5e.0203041003.2b10abad%40posting.google.com
However, I thought I'd post a preliminary version of the first three sections now. I'm hoping that some of you can doublecheck my computations and/or give me suggestions for topics that I could discuss in these sections. I would especially like to know of any interesting examples in which large numbers arise that I haven't already dealt with.
My plan is to carefully work up to the HowardBachmann ordinal level of the GrzegorczykWainer Hierarchy, and then touch on some of the constructible ordinal notations that go beyond this. At present I have 10 sections (in various stages of completion), but there may be more than this by the time I'm done.
Dave L. Renfro
*****************************************
3. TETRATION (^^) AND HYPERTETRATION (^^^)
A. DEFINITIONS AND NOTATION B. EVALUATIONS OF 2^^n AND 3^^n C. DESCRIBING LARGE NUMBERS BY REPEATEDLY COUNTING DIGITS D. FACTORIALS AND EXPONENTIATION OF TETRATED NUMBERS E. OBTAINING LARGE NUMBERS BY USING A FEEDBACK METHOD F. ANNOTATED LIST OF NUMBERS UP TO 8#(2, 184) G. REFERENCES FOR SECTION 3
***************************************** *****************************************
A. DEFINITIONS AND NOTATION
Since multiplication is repeated addition and exponentiation is repeated multiplication, it is natural to consider continuing this process. To see how to carry out such a continuation, we formalize this observation about multiplication and exponentiation as a pair of inductive statements.
x*(y+1) = x + (x*y) multiplication
x^(y+1) = x * (x^y) exponentiation
Because + and * are commutative, the order that we used on the right hand sides of these equations does not matter. However, the operations that we get when this process is continued wind up being neither commutative nor associative. The definitions given below conform to the standard practice of evaluating exponent and hyperexponent towers in a topdown manner.
x^^1 = x x^^(y+1) = x ^ (x^^y) tetration
x^^^1 = x x^^^(y+1) = x ^^ (x^^^y) hypertetration
The operations ^^^^, ^^^^^, etc. are defined by continuing this recursive process.
The term tetration seems to originate from Reuben L. Goodstein, "Transfinite ordinals in recursive number theory", Journal of Symbolic Logic 12 (1947), 123129. [At the top of p. 129 Goodstein writes: "... defines successive new processes (which we may call tetration, pentation, hexation, and so on)."]
For each of ^^ and ^^^, I'll refer to the left input number as the "base" and the right input number as the "exponent".
It is standard practice to denote x^^y as x with a left superscript y. [A left superscript is sometimes called a "prescript".] Of course, that option is not available in ASCII format. In fact, as far as I know, that option (i.e. a left superscript) is not available in LaTeX either, at least as an explicit command in the same way that $x^{y}$ and $x_{y}$ represent "x superscript y" and "x subscript y", respectively. However, I've discovered that ${}^{y}x$ represents x^^y fairly well. [That is, use 'y' as a superscript to an empty space and then follow this "exponentiated pair" with 'x'.]
***************************************** *****************************************
B. EVALUATIONS OF 2^^n AND 3^^n
To see tetration growth in action, I've computed some values for base 2 and base 3. These values come in handy from time to time because one often sees base 2 and base 3 used when higher order operations appear. For example, the typical definition of Graham's number uses operations with base 3 and the typical "Ackermann operations" use base 2. In set theory, the finite levels V_n of the cumulative hierarchy of sets have 2^^n elements.
********** EVALUATIONS OF 2^^n **********
2^^2 = 4
2^^3 = 16
2^^4 = 65,536
2^^5 = 2.003529930406846 x 10^(19,728)
2^^6 = 10 ^ (6.031226062630295 x 10^(19,727))
2^^7 = 10 ^ [ 10 ^ (6.031226062630295 x 10^(19,727)) ]
= 6.031226062630295 x 10^(19,727) @ 10^^2
2^^8 = 6.031226062630295 x 10^(19,727) @ 10^^3
* * *
2^^n = 6.031226062630295 x 10^(19,727) @ 10^^(n5) for n > 5
********** EVALUATIONS OF 3^^n **********
3^^2 = 27
3^^3 = 7,625,597,484,987
3^^4 = 1.258 x 10^(3,638,334,640,024)
3^^5 = 10 ^ [ 1.258 x 10^(3,638,334,640,024) ]
3^^6 = 1.258 x 10^(3,638,334,640,024) @ 10^^2
* * *
3^^n = 1.258 x 10^(3,638,334,640,024) @ 10^^(n4) for n > 4
***************************************** *****************************************
C. DESCRIBING LARGE NUMBERS BY REPEATEDLY COUNTING DIGITS
3^^3 = 3^3^3 = 3^27 = 7,625,597,484,987 [Has 13 digits.]
3^^4 = 3^(3^^3) = 3^(3^27) = 3^(7,625,597,484,987) [Has about 3.6 x 10^12 digits.]
3^^5 = 3^(3^^4) [If k is the number of digits that 3^^5 has, then the number k has about 3.6 x 10^12 digits.]
Here is one way to see the rapid growth of the ^^ operation. Let *[n,2] be the number of digits in the number of digits of n. For example, *[10^1000, 2] = 4, since 10^1000 has 1001 digits and 1001 has 4 digits. Using the method described in Section 2D, we get the following:
*[(10^3)!, 2] = 4
*[(10^6)!, 2] = 7
*[(10^9)!, 2] = 10
*[(10^100)!, 2] = 102
*[(10^1000)!, 2] = 1003
Now let's look at what happens when we input 10^^n values.
*[10^^2, 2] = 2
*[10^^3, 2] = 11
*[10^^4, 2] = 10,000,000,001
*[10^^5, 2] = 10^^3
*[10^^6, 2] = 10^^4
Note that *[10^^i, 2] = 1 + *[10^^(i2), 2]. In other words, our *[__, 2] operation has so little apparent effect on the growth of 10^^i that just two initial applications of the successor operation make up for what the *[__, 2] operation does.
Let's feed some more power into our *[__, 2] operation. If k is a positive integer, let *[n, k+1] be the number of digits that *(n,k) has. This implies that *[n,k] is the k'thiterate of "number of digits of" that n has. Also, *[n,k] is basically the k'th iterated base10 logarithm of n.
For example, *[10^^4, 2] = 10,000,000,001, *[10^^4, 3] = 11 (since 10,000,000,001 has 11 digits), *[10^^4, 4] = 2, and *[10^^4, 5] = 1.
When k is fixed, the *[__, k] operation applied to 10^^i has the same effect as subtracting k from i. Thus, none of the *[__, k] operations has a nontrivial effect on the growth rate of the sequence 10^^1, 10^^2, 10^^3, ...
Now let !(n) be the smallest number k such that *[n,k] = 1.
In other words, when presented with a large number n, we look at the number of digits that n has, then we look at the number of digits that the number of digits of n has, then we look at the number of digits that the number of digits that the number of digits of n has, ..., until this process stabilizes. The smallest number of iterations of "the number of digits of" it takes for this process to stabilize will be denoted by !(n).
The !values of 10^^i are particularly easy to calculate >>>
!(10^^2) = 3 !(10^^3) = 4 !(10^^4) = 5 !(10^^5) = 6 * * * !(10^^i) = i+1
Notice that the !(__) operation has a much more drametic effect on the growth of 10^^i than any of the *[__, k] operations did. For each value of k, the *[__, k] operation applied to the sequence 10^^1, 10^^2, 10^^3, ... simply produces a translation of this sequence, and so none of the *[__, k] operations has any essential effect on its growth rate. On the other hand, the !(__) operation obliterates the ^^operation, leaving us with what we started with before we applied the ^^operation.
Now let's turn our attention to ^^^growth.
Unlike the situation for tetrated growth (above), hypertetrated growth is virtually unaffected by an application of our !slowdown operation >>>
!(10^^^2) = 9 = 10^^^1 !(10^^^3) = 10^^10  1 = 10^^^2 \ I've ignored the inconsequential !(10^^^4) = 10^^(10^^10) = 10^^^3 / subtraction of 1 in several !(10^^^5) = 10^^(10^^^3) = 10^^^4 / places.
To successfully slow down ^^^growth, we would have to count the number of applications of the !operation that are needed to reach 1. We might symbolize this even stronger operation applied to n by !!(n), but I think you get the idea what happens in general >>> !!...! (p !'s) slows down ^^...^growth (q ^'s) when q = p+1, but not when q > p+1.
***************************************** *****************************************
D. FACTORIALS AND EXPONENTIATION OF TETRATED NUMBERS
To motivate what follows, here is one way to describe how big the number 10^^(10^^4) is.
Let n be one googolplex. That is, n = 10^(10^100). Now consider n!!!...!, where the factorial operation is applied over and over again, a googolplex number of times. The result will be much less than 10^^(10^^4). In fact, 10^^(10^^4) is what you'd get if you applied the factorial operation 10^(10^10,000,000,000) many times to a googolplex.
Clearly, each application of the function f(n) = 10^n to 10^^i increases the tetration exponent by one. However, even functions such as 100^n, (googolplex)^n, n!, n^n, and 10^(n^2) only increase the tetration exponent of 10^^i by one with each application. Let's see how this happens.
Since 10^(n^2) is the most rapidly growing function in the list I gave (note that n! = 1*2*3*...*n is clearly smaller than n^n = n*n*n*...*n, and 10^(n^2) divided by n^n is (10^n)/n raised to the n'th power), it suffices to verify my claim for 10^(n^2). The following examples illustrate that in addition to increasing the tetrated exponent by 1, an application of 10^(n^2) adds just over .301 (the base10 logarithm of 2) to what becomes the 3'rd level exponent.
Evaluating 10^(n^2) for n = 10^^3 gives
10 ^ [10^(10^10)]^2 = 10 ^ [10^(2 x 10^10)]
= 10 ^ [10^(10^(.301 + 10))]
= (.301 + 10) @ 10^^3.
Evaluating 10^(n^2) for 10^^4 gives
10 ^ {10^[10^(10^10)]}^2 = 10 ^ {10^[2 x 10^(10^10)]}
= 10 ^ {10^[10^(.301 + 10^10)]}
= (.301 + 10^10) @ 10^^3.
Evaluating 10^(n^2) for 10^^5 gives
10 ^ {10^[10 ^ (.301 + 10^(10^10)) ]}
= (.301 + 10^^3) @ 10^^3.
Therefore, at least for i > 3, the functions 10^n, 100^n, (googolplex)^n, n!, n^n, and 10^(n^2) all have essentially the same effect on 10^^i, which is to output the number 10^^(i+1).
[[ Don't confuse appearances with reality, however. Squaring the number 1000 causes a more dramatic change than squaring the number 5, and the larger the number the more dramatic the change when we square it. However, our notation is just not equipped to show these changes when the numbers are as large as those that we're now looking at. ]]
***************************************** *****************************************
E. OBTAINING LARGE NUMBERS BY USING A FEEDBACK METHOD
Repeated addition is multiplication, repeated multiplication is exponentiation, etc. By using numbers already obtained to specify the number of repetitions, we can sail past two operation levels with a single jump. In what follows, regardless of whether you interpret "apply 10+n to 10 one hundred times" to mean 10+10+...+10 (one hundred 10's appearing) or to mean 10+10+...+10 (one hundred +'s appearing), the result will be essentially the same when exponential notation is used  10^3. Similarly for the other cases.
[[ Incidentally, this analogous to how Graham's number is usually defined, except that at each stage the numbers generated during the process are used to specify how many operations levels are to be advanced (!!), rather than how many iterations of some specified operation level are to be used. ]]
addition > exponentiation
Step 1: Begin with 10. Step 2: Apply 10+n to 10 "Step 1" number of times. 10^2 Step 3: Apply 10+n to 10 "Step 2" number of times. 10^3 Step 4: Apply 10+n to 10 "Step 3" number of times. 10^4 Step 5: Apply 10+n to 10 "Step 4" number of times. 10^5
Do this 10^^i number of times and we'll be at Step i+1 in what follows.
multiplication > tetration
Step 1: Begin with 10. Step 2: Apply 10*n to 10 "Step 1" number of times. 10^^2 Step 3: Apply 10*n to 10 "Step 2" number of times. 10^^3 Step 4: Apply 10*n to 10 "Step 3" number of times. 10^^4 Step 5: Apply 10*n to 10 "Step 4" number of times. 10^^5
Do this 10^^^i number of times and we'll be at Step i+1 in what follows.
exponentiation > hypertetration
Step 1: Begin with 10. Step 2: Apply 10^n to 10 "Step 1" number of times. 10^^^2 Step 3: Apply 10^n to 10 "Step 2" number of times. 10^^^3 Step 4: Apply 10^n to 10 "Step 3" number of times. 10^^^4 Step 5: Apply 10^n to 10 "Step 4" number of times. 10^^^5
***************************************** *****************************************
F. ANNOTATED LIST OF NUMBERS UP TO 8#(2, 184)
10^^6  Largest number in Section 1. [Knapowski's 1962 paper.]
10^^(998)  From Kolata [66] (p. 780): "Friedman showed that if, for example, you want to prove that a tree containing ten nodes must fit into another tree, the proof would require more than 2^^(1000) steps." This is also mentioned in Simpson [97] (p. 373) and Smorynski [99] (p. 183). The number 2^^1000 is approximately equal to (6.03 x 10^19727) @ 10^^95 (see Section B above).
10^^^(1.69 x 10^271)  On p. 27 of Gardner [44] Jon Folkman is said to have proved a graph theoretic result using a graph with 2^^^(2^901) points.
10^^^(10^^^10)  The number 10^^^^3 (Knuth's 10 "4uparrows" 3) is used to illustrate Knuth's uparrow notation on pp. 12351236 of Knuth [64].
(p. 1235) "In order to see how these arrow functions behave, let us look at a very small example ..."
(p. 1236) "On the other hand, it is very small as finite numbers go. We might have used H [Knuth's local abbreviation for 10^^^10] arrows instead of just four, but even that would not get us much furtheralmost all finite numbers are larger than this."
10^^^^^^184  The number 2^^^^^^184, which is utterly indistinguishable from 10^^^^^^184, is a lower bound for A(3) in Friedman [39] (see Theorem 4.7 on p. 33).
Here is what Friedman has to say about this number, A(7,184) in his notation, in Section 8 of [41]:
"Paul Sally runs a program for gifted high school students at the University of Chicago."
"He asked them to find n(1), n(2), n(3). They all got n(1) = 3. One got n(2) = 11. Nobody reported much on n(3)."
"I then started to ask several mathematicians to give an estimate on n(3), some of them very famous. I got guesses like this:"
"60, 100, 150, 200, 300."
"They were not in combinatorics. Recently I asked Lovasz, telling him about these five guesses. He guessed 20,000."
"Theorem 8.2. n(3) > A(7,184)."
"Lovasz wins, as his guess is closer to A(7,184) than the other guesses."
For a more detailed (and funnier) version of this story, see
http://www.math.psu.edu/simpson/fom/postings/9809/msg00100.html
***************************************** *****************************************
G. REFERENCES FOR SECTION 3
[39] Harvey M. Friedman, "Long finite sequences", manuscript, 8 Oct. 1998, 50 pages. This is #17 in Friedman's "1. Preprints, Drafts, and Abstracts" section at
http://www.math.ohiostate.edu/foundations/manuscripts.html
[41] Harvey M. Friedman, "Enormous integers in real life", manuscript, 1 June 2000, 11 pages. This is item #18 in Friedman's "2. Lectures" at
http://www.math.ohiostate.edu/foundations/manuscripts.html
Note: Friedman uses "E*(n)" for 2^^n (it's really 'E' with '*' as a superscript, but I can't do this in ASCII format) and "A(k,n)" for (k+1) # (2,n).
[44] Martin Gardner, "In which joining sets of points by lines leads into diverse (and diverting) paths", Mathematical Games column, Scientific American 237 (Nov. 1977), 1828. [Graham's number is discussed on page 28.]
[64] Donald E. Knuth, "Mathematics and computer science: Coping with finiteness", Science 194 (1976), 12351242.
[36] Gina Kolata, "Does Godel's theorems matter to mathematics?", Science 218 #4574 (Nov. 19, 1982), 779780. [Reprinted on pp. 399404 of L. A. Harrington et al. (editors), HARVEY FRIEDMAN'S RESEARCH ON THE FOUNDATIONS OF MATHEMATICS, North Holland, 1985.]
[51] Stephen G. Simpson, "Unprovable theorems and fastgrowing functions", Contemporary Mathematics 65 (1987), 359394.
The text of Simpson's paper (posted by Bill Dubuque) can be found at
http://groups.google.com/groups?selm=WGD.96Jun8164834%40berne.ai.mit.edu
[99] Craig Smorynski, "The varieties of arboreal experience", The Mathematical Intelligencer 4 (1982), 182189. [Reprinted on pp. 381397 of L. A. Harrington et al. (editors), HARVEY FRIEDMAN'S RESEARCH ON THE FOUNDATIONS OF MATHEMATICS, North Holland, 1985.] [See under "Ordinal 4" in "A Table of Some Growth Rates" on p. 188 for the assertion that G(n) grows at the hypertetration rate. A correction to the proof of part (ii) of the Lemma on p. 188 is given on pp. 235239 of Gallier's paper.]
***************************************** *****************************************



