Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

BIG NUMBERS #3

140 views
Skip to first unread message

Dave L. Renfro

unread,
Apr 8, 2002, 6:57:22 PM4/8/02
to
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 double-check
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 Howard-Bachmann ordinal
level of the Grzegorczyk-Wainer 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 HYPER-TETRATION (^^^)

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 hyper-exponent towers in a top-down manner.

x^^1 = x
x^^(y+1) = x ^ (x^^y) tetration

x^^^1 = x
x^^^(y+1) = x ^^ (x^^^y) hyper-tetration

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), 123-129. [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^^(n-5) 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^^(n-4) 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^^(i-2), 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'th-iterate of
"number of digits of" that n has. Also, *[n,k] is basically
the k'th iterated base-10 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 non-trivial 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), hyper-tetrated
growth is virtually unaffected by an application of our !-slow-down
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 base-10 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 ---> hyper-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


*****************************************
*****************************************


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 "4-up-arrows" 3)
is used to illustrate Knuth's up-arrow notation
on pp. 1235-1236 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
further--almost 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.ohio-state.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.ohio-state.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), 18-28. [Graham's
number is discussed on page 28.]

[64] Donald E. Knuth, "Mathematics and computer science: Coping
with finiteness", Science 194 (1976), 1235-1242.

[36] Gina Kolata, "Does Godel's theorems matter to mathematics?",
Science 218 #4574 (Nov. 19, 1982), 779-780. [Reprinted on
pp. 399-404 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 fast-growing
functions", Contemporary Mathematics 65 (1987), 359-394.

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), 182-189.
[Reprinted on pp. 381-397 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 hyper-tetration rate. A correction to the proof of part
(ii) of the Lemma on p. 188 is given on pp. 235-239 of
Gallier's paper.]


*****************************************
*****************************************

0 new messages