雑談はここに書け！【２】

平均的２ちゃんねらー＠数学板の知能を1としたときに、某いまいの知能指数がこのグラハム数の逆数となる。

非負整数 x, y, z (但し z ≧ 2) に対し
ak(x, y, 0) = x + y,
ak(x, y, 1) = xy,
ak(x, y, 2) = x^y,
ak(x, 0, c + 1) = x,
ak(x, y + 1, z + 1) = ak(x, ak(x, y, z+1), z)
とする。これを Ackermann 函数と呼ぶ。同様のことを tower というものを用いて次のように表現する。
x↑y = x^y,
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↑^4 3という数である。

この数がどういう意味を持つのかというと, 1970 年のグラハムロートシルトの次の結果と関係がある。
定理
n 次元の超立方体の合計2n個の頂点を総て結び, それを赤と青の二色の何れかに塗る。このとき n が充分大きいならば, どのような塗り方をしても, 必ず同一平面上にある四点でそれらを結ぶ線が総て同一の色であるものが存在する。
この定理の中の「充分大きい」 n はどの位大きければいいのだろうか?
の答えの一つがグラハム数で, この数より大きければ間違いないということが分かっている。
まあ予想では 6 以上なら大丈夫なんじゃないかということだが。