グラハム数 Graham number

Wednesday, 19th April, 2000.
Wednesday, 30th October, 2002.
Sunday, 16th March, 2003.
Saturday, 13th December, 2003.
Sunday, 14th December, 2003.


意味のある数の中では知られている限り最も大きい数である。 (ギネスブックにも載った。 但し, 今でも載っているか, 今でも最も大きい数かと言われると不明)

それを述べるために, 幾つか準備をする。

Wilhelm Ackermann (アッカーマン, 1896--1962) は 「帰納的函数はすべて原始帰納的函数か」 という問に対して次のような函数を示して, そうでない例をつくった (という話は故前原昭二先生からうかがったのだが, うろ覚えのため誤っているかもしれない)。 Ackermann 函数が原始帰納的でない帰納的函数の例であるというのは, 廣瀬健: 帰納的函数, 共立講座 「現代の数学」 3, 共立出版, p. 43 注意 2.5 に出ている。 非負整数 x, y, z (但し z ≧ 2) に対し

ak(x, y, 0) = x + y,
ak(x, y, 1) = xy,
ak(x, y, 2) = xy,
ak(x, 0, c + 1) = x,
ak(x, y + 1, z + 1) = ak(x, ak(x, y, z+1), z)

とする。これを Ackermann 函数と呼ぶ。ラムゼー理論の専門家達は同様のことを tower というものを用いて次のように表現する。

x↑y = xy,
x↑↑2 = x↑x, x↑↑y = x↑(x↑↑(y - 1)),
x↑↑↑2= x↑↑x, x↑↑↑y = x↑↑(x↑↑↑(y - 1)),
x↑↑↑↑2 = x↑↑↑x, x↑↑↑↑y = x↑↑↑(x↑↑↑↑(y - 1))

と決める。グラハム数の記述にはこれで充分であるが, 上述の Ackermann 函数との関連を述べるために, 簡単にx↑2 y = x↑↑y, x↑3 y = x↑↑↑y等と書くことにすれば, 上記の定義は x↑m 1 = x↑m−1 x,  x↑m y = x↑m−1 (x↑m (y−1)) と比較的簡単に書け, x↑m y = ak(x, y, m+1) であることが確かめられる。

さて, グラハム数とは a1 = 3↑4 3 とし, an = 3↑an-1 3 としたときの a64 という数である。 試しに a1 を途中まで計算してみるとグラハム数は信じられないくらい大きい数であることが分かる。 実際

3↑4 3 = 3↑3(3↑4 2) = 3↑3(3↑3 3) = 3↑3(3↑2 (3↑3 2)) = 3↑3(3↑2 (3↑2 3)) = 3↑3(3↑2 (3↑(3↑3)) = 3↑3(3↑2 (3↑(33)) = 3↑3(3↑2 (3↑27)) = 3↑3(3↑2 (327))= 3↑3(3↑2 7625597484987)

であるので, とてもこれ以上続けられない。凄まじく大きい数である。 更にこれが 63 段も上にある数が Graham 数であるから想像を絶するくらい大きい数であることが分かる。

この数がどういう意味を持つのかというと, 1970 年のグラハム・ロートシルト (R. L. Graham and B. L. Rothschild) の次の結果と関係がある。

定理
n 次元の超立方体の合計 2n 個の頂点を総て結び, それを赤と青の二色の何れかに塗る。 このとき n が充分大きいならば, どのような塗り方をしても, 必ず同一平面上にある四点でそれらを結ぶ線が総て同一の色であるものが存在する。

この定理の中の 「充分大きい」 n はどの位大きければいいのだろうか? というのの答えの一つがグラハム数で, この数より大きければ間違いないということが分かっている。 尤も予想では 6 以上なら大丈夫なんじゃないかということである。 何だか 「大山鳴動して鼠一匹」 みたいな話である。


更に馬鹿でっかい数 Busy Beaver Function というのに関してここに記述がある。

Wednesday, 30 October, 2002.


新たに page を作るほどではないので, ここに書くがスキューズ数というのがあるそうだ。

通常は第 1 スキューズ数のことを指し, リーマン仮説が正しいとしたときに, π(n) < Li(n) が必ず成立しなくなる最小の数のこと。 スキューズ数の上限は、スキューズによって e^(e^(e^79)) (≒ 10^(10^(10^34))) であることが示された。 その後, Riele (1987) によってe^(e^(27/4)) (≒ 10^(10^370)) まで小さくされたが, Conway and Guy (1996) は現在の最善の限界は 10^1167 であるとした。

Sunday, 16 March, 2003.


以前, この部分は次のように書いていた。 どうして間違えたのか不明だが, 巨大数探索スレッド5 の 705 で 03/10/24 12:23 に誤りが指摘されていたので, 訂正した。 最初の誤りがどのようなものであったかを示すために, 以前のものを残しておく。 (要するに tower の初期条件を誤ったのである)

x↑y = xy,
x↑↑1 = x↑x, x↑↑y = x↑(x↑↑(y - 1)),
x↑↑↑1 = x↑↑x, x↑↑↑y = x↑↑(x↑↑↑(y - 1)),
x↑↑↑↑1 = x↑↑↑x, x↑↑↑↑y = x↑↑↑(x↑↑↑↑(y - 1))
と決める。グラハム数の記述にはこれで充分であるが, 上述の Ackermann 函数との関連を述べるために, 簡単にx↑2 y = x↑↑y, x↑3 y = x↑↑↑y等と書くことにすれば, 上記の定義は x↑m 1 = x↑m−1 x, x↑m y = x↑m−1 (x↑m (y−1)) と比較的簡単に書け, x↑m y = ak(x, y, m+1) であることが確かめられる。 さて, グラハム数とは3↑43という数である。3↑3 3を途中までやってみると分かるが, 途中で馬鹿でっかい数であることが分かる。従ってグラハム数は信じられないくらい大きい数であることが分かる。実際
3↑33 = 3↑2(3↑3 2) = 3↑2(3↑2 (3↑31)) = 3↑2(3↑2 (3↑23)) = 3↑2(3↑2 (3↑(3↑22))) = 3↑2(3↑2 (3↑(3↑(3↑21)))) = 3↑2(3↑2 (3↑(3↑(3↑3)))) = 3↑2(3↑2 (3↑(3↑(33)))) = 3↑2(3↑2 (3↑(3↑27))) = 3↑2(3↑2 (3↑(327)))= 3↑2(3↑2 (3↑7625597484987)) = 3↑2(3↑2 (37625597484987)).

間違いを発見したら, 出来たら私の方にも知らせていただきたい。

以前 3↑4 3 自身をグラハム数であると書いていたが, 実は数学セミナーの記事の読み間違いであった。 お詫びして訂正する。 尚, この間違いを指摘してくださった, 雑記草 (ざっきそう) の owner 後藤氏に感謝する。 (Sun 14 Dec, 2003)


1970年のグラハムとロートシルト (R. L. Graham and B. L. Rothschild) による問題について。
Geoff Exoo は 2003 年にこの問題の下限が 11 であることを示した。 (上限ではない)
A Ramsey Problem on Hypercubes

Sunday, 25th May, 2008.


W. Ackermann, Zum Hilbertischen Aufbau der reelen Zahlen, Math. Ann. 99 (1928), S. 118--133
廣瀬健: 帰納的函数, 共立講座「現代の数学」3, 共立出版
sin 「グラハム数」 数学セミナー (11), 1986.
Graham's Number
Graham's Number

Tower に関して
http://mathworld.wolfram.com/PowerTower.html
及び http://mathworld.wolfram.com/ArrowNotation.html

Miscellaneous の index
HOME