Graham's Number -- Practically Everyone Has It Wrong!?
r.e.s.
various websites and papers that claim to define the
integer known as "Graham's number". This is supposed
to be the number stated by Graham & Rothschild [1] as
an upper bound in a certain problem in Ramsey theory.
Apparently, practically everyone has got it wrong ...
Here is the definition from the original paper [1]:
====================begin quote=======================
We recall that by definition N(1,2,2) is an integer
such that if n >= N(1,2,2) and the C(2n,2) straight
line segments joining all possible pairs of vertices
of a unit n-cube are arbitrarily 2-colored, then
there always exists a set of four coplanar vertices
which determines six line segments of the same color.
Let N* be the least possible value N(1,2,2) can
assume. We introduce a calibration function F(m,n)
... defined recursively as follows:
F(1,n) = 2^n, F(m,2) = 4, m >= 1, n >= 2
F(m,n) = F(m-1,F(m,n-1)), m >= 2, n >= 3.
... the best estimate for N* we obtain this way is
roughly
N* <= F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
On the other hand it is known only that N* >= 6.
===================end quote==========================
So Graham's number (the upper bound quoted above), is
G = F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
(Note that F(m,n) = 2^^...^n (m ^'s) in Knuth's arrow
notation.)
In particular, G is much larger than the number given
in a paper by Smorynski, but is much smaller than the
number given on so many websites, such as
http://mathworld.wolfram.com/GrahamsNumber.html
It's a bit unnerving to post this, as it disagrees
with literally all of the online definitions I could
find (almost all of which agreed with one another).
Possibly the definition quoted from [1] was itself
corrected at some later date by its authors. (?)
[1]
Graham, R. L. and Rothschild, B. L.
"Ramsey's Theorem for n-Parameter Sets."
Trans. Amer. Math. Soc. 159, 257-292, 1971.
--r.e.s.
|-|erc
> F(1,n) = 2^n, F(m,2) = 4, m >= 1, n >= 2
> F(m,n) = F(m-1,F(m,n-1)), m >= 2, n >= 3.
>
> ... the best estimate for N* we obtain this way is
> roughly
> N* <= F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
>
K(0,n) = n^n
K(m+1, n) = K(m, K(m,n))
Next, we define G: N --> N using K.
G(0) = K(3,3)
G(n+1) = K(G(n), 3)
the n^n instead of 2^n is different, but Smorynski defn G(64) looks bigger,
unless F(12,3) > G(56)
Herc
my...@yahoo.com
>Possibly the definition quoted from [1] was itself
>corrected at some later date by its authors. (?)
I would tend to believe this is the case. In the 1977 Scientific
American article by Martin Gardner (where the number was announced), an
*unpublished* proof by Graham was quoted as the source. I had a copy
of the SciAm article but I have since misplaced it. Renfro has it as a
reference in his post above.
-cs
r.e.s.
> [r.e.s. wrote ...]
Smorynski's G(64) is even smaller than F(12,3), so it's
certainly smaller than Graham's number, which is
F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
From David Renfro's page at
http://mathforum.org/discuss/sci.math/m/394644/394645
(which, however, does not use the original definition of
Graham's number -- although it gives two variants), we have
G(64) < 3^^^131.
Now
3^^^131 < 2^^^262 [*]
But 2^^^262 = F(3,262), which is much smaller than F(12,3):
F(12,3) = F(11,F(12,2)) = F(11,4) = F(10,F(11,3)) > F(3,262).
Conclusion:
Smorynski's G(64) is much smaller than Graham's number,
which is F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
[*]
3^^...^n < 2^^...^(2n) (k ^'s in each, k >= 2).
This is a special case of a more general inequality for
"change of base" in an Ackermann hierarchy, which I proved
in an earlier thread:
http://groups.google.com/groups?selm=bagkcl$bhd$1...@slb4.atl.mindspring.net
--r.e.s.
r.e.s.
Not having seen the Gardner article, it seems also possible
that the bound Gardner *says* Graham found but didn't publish,
is actually a bound for some problem other than the one it's
commonly associated with (i.e. the problem described in the
original paper). If Graham discovered that the bound he
published was wrong, surely he would publish the correction
(unless it was felt to be too trivial a matter).
I would very much like to know exactly what problem Gardner
says the number is associated with; but as was the case for
my accessing the Graham & Rothschild paper, it's quite a lot
of trouble for me to get hold of the SciAm article.
--r.e.s.
mensa...@aol.com
I just bought a book yesterday:
The universal book of mathematics:
from abracadabra to Zenos paradoxes/
David Darling.
He also references Martin Gardner's SciAm article but has Graham's
number as G(62), not G(64). So it doesn't look like the off-line
sources are any better than the on-line ones.
Do popularizers do more harm than good now that mistakes propagate
all over the internet?
my...@yahoo.com
:)
Years ago I did a little research on Graham's Number, including
xeroxing the SciAm article I mentioned. And I turned around and lost
it. So I can only recall, naturally, some portions, including the
*unpublished* (this caught my eye) remark of Gardner. And it makes
sense that he, Graham, would publish a recalculation of his earlier
work. I don't know. Maybe you could email Graham himself.
And I remember a thread here a couple of years ago where someone tried
to get the proof because he couldn't believe that such an immense
quantity could be the result of any realistic (I'm paraphrasing here
from memory :) ) mathematical proof. If interested, try searching sci
math "Graham's Number" for this post and thread.
Concerning the SciAm article, it was the first time the so-called
Graham's Number was mentioned in the popular press, and it was
definitely the same problem in Ramsey Theory about the lowest dimension
of a hypercube such that if the lines joining all pairs of corners are
two-colored, a planar graph Kv[4} of one color will be forced.
The number in the SciAm article is the same as Wolfram's and, as you
said before, the same as most representations online. Gardner
represented it in an informal graph, something like this- (hope this
comes out okay)
/ 3^^^^3 arrows
| ______^_______
| / \
| 3^^^...........^^3 arrows
| ______^_______
| / \
| 3^^............^^3 arrows
64 layers< .
| .
| .
| _______^_______
| / \
\ 3^^.............^^3
HTH
-cs
|-|erc
> "|-|erc" wrote ...
> > [r.e.s. wrote ...]
> >>
> >> F(1,n) = 2^n, F(m,2) = 4, m >= 1, n >= 2
> >> F(m,n) = F(m-1,F(m,n-1)), m >= 2, n >= 3.
> >>
> >> ... the best estimate for N* we obtain this way is
> >> roughly
> >> N* <= F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
>
> > K(0,n) = n^n
> > K(m+1, n) = K(m, K(m,n))
> >
> > Next, we define G: N --> N using K.
> >
> > G(0) = K(3,3)
> > G(n+1) = K(G(n), 3)
> >
> > the n^n instead of 2^n is different,
> > but Smorynski defn G(64) looks bigger, unless F(12,3) > G(56)
>
> Smorynski's G(64) is even smaller than F(12,3), so it's
> certainly smaller than Graham's number, which is
> F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
>
> From David Renfro's page at
> http://mathforum.org/discuss/sci.math/m/394644/394645
> (which, however, does not use the original definition of
> Graham's number -- although it gives two variants), we have
> G(64) < 3^^^131.
<ignore that part>
>
> Now
> 3^^^131 < 2^^^262 [*]
> But 2^^^262 = F(3,262), which is much smaller than F(12,3):
> F(12,3) = F(11,F(12,2)) = F(11,4) = F(10,F(11,3)) > F(3,262).
>
> Conclusion:
> Smorynski's G(64) is much smaller than Graham's number,
> which is F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
>
> [*]
> 3^^...^n < 2^^...^(2n) (k ^'s in each, k >= 2).
> This is a special case of a more general inequality for
> "change of base" in an Ackermann hierarchy, which I proved
> in an earlier thread:
> http://groups.google.com/groups?selm=bagkcl$bhd$1...@slb4.atl.mindspring.net
>
But this
> > G(0) = K(3,3)
> > G(n+1) = K(G(n), 3)
is just shorthand for
K(K(K(K(K(K(K(K(K(3,3),3),3),3),3),3),3),3),3)
<----------n K's------->
Since K is almost the same a F,
your original papers value is
F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
and the accepted value is G(64)
F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F
(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(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),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3).
Can the center of you term, F(12,3) be substitued with G(58)
F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F
(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(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),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3),3).
in which case they would be equal.
Does F(F(F(F(F(F( F(12,3) ,3),3),3),3),3),3) = F(F(F(F(F(F( G(58) ,3),3),3),3),3),3)
<original paper> <accepted value>
Herc
r.e.s.
> "r.e.s." <r...@ZZmindspring.com> wrote in
>> "|-|erc" wrote ...
>> > [r.e.s. wrote ...]
>> >>
>> >> F(1,n) = 2^n, F(m,2) = 4, m >= 1, n >= 2
>> >> F(m,n) = F(m-1,F(m,n-1)), m >= 2, n >= 3.
>> > K(0,n) = n^n
>> > K(m+1, n) = K(m, K(m,n))
>> > G(0) = K(3,3)
>> > G(n+1) = K(G(n), 3)
>> Conclusion:
>> Smorynski's G(64) is much smaller than Graham's number,
>> which is F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
> But this
>> > G(0) = K(3,3)
>> > G(n+1) = K(G(n), 3)
>
> is just shorthand for
> K(K(K(K(K(K(K(K(K(3,3),3),3),3),3),3),3),3),3)
>
> <----------n K's------->
For G(n+1), that would be n+2 K's.
> Since K is almost the same a F,
-snip-
No, that would take us far astray.
Since the number specified by the "popular" definition
is not the one in the paper by Graham et al, but was
apparently merely attributed to Graham by Martin Gardner,
maybe the popular one should be called "Gardham's number". ;o)
--r.e.s.
|-|erc
> "|-|erc" <h@r.c> wrote ...
> > "r.e.s." <r...@ZZmindspring.com> wrote in
> >> "|-|erc" wrote ...
> >> > [r.e.s. wrote ...]
> >> >>
> >> >> F(1,n) = 2^n, F(m,2) = 4, m >= 1, n >= 2
> >> >> F(m,n) = F(m-1,F(m,n-1)), m >= 2, n >= 3.
>
> >> > K(0,n) = n^n
> >> > K(m+1, n) = K(m, K(m,n))
>
> >> > G(0) = K(3,3)
> >> > G(n+1) = K(G(n), 3)
>
> >> Conclusion:
> >> Smorynski's G(64) is much smaller than Graham's number,
> >> which is F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).
>
> > But this
> >> > G(0) = K(3,3)
> >> > G(n+1) = K(G(n), 3)
> >
> > is just shorthand for
> > K(K(K(K(K(K(K(K(K(3,3),3),3),3),3),3),3),3),3)
> >
> > <----------n K's------->
>
> For G(n+1), that would be n+2 K's.
>
> > Since K is almost the same a F,
> -snip-
>
> No, that would take us far astray.
but the popular version is larger, its 64 F_3's to your 6,
and it's n^n instead of your 2^n. there is one other difference
that may even make them equivalent.
>
> Since the number specified by the "popular" definition
> is not the one in the paper by Graham et al, but was
> apparently merely attributed to Graham by Martin Gardner,
> maybe the popular one should be called "Gardham's number". ;o)
>
Is Gardners number the hypercube solution? if so then its just a minor correction, or compact form
of the original formulation.
Herc
--
> then it is uniquely defined AFTER the flippers have flipped
> enough (given that every flipper is only a finite number of
> flippers from the beginning, and every flip is only a finite
> number of flips from the beginning, no individual flip or anti-
> flip needs infinite inputs to compute). GEORGE GREENE sci.logic