グラハム数は系の系の系のおまけの下位互換

前置きの前置き

すみません。タイトルはかなりclickbaitです。「$1+2+3+\cdots = -\frac{1}{12}$」くらい恣意的な表現になります。が、この記事を最後まで読めばなぜこういうタイトルにしたくなるか理解していただけるかと思います。

前置き

Grahamの論文「RAMSEY'S THEOREM FOR $n$-PARAMETER SETS」をチョット読む。
この論文の最後の方には、みんな大好き「小グラハム数」の定義が載っている。本稿では小グラハム数の誕生の経緯を知っていただく……つもりだったのに、なんかそれどころじゃないくらいヤバいことが書いてあった、という報告である。
証明まで書いていると記事が長くなりすぎるので、主定理とその系の紹介にとどめる。ステートメントを眺めるだけでも十分面白いので。

ラムゼイ理論

ラムゼイ理論は、集合についてのある性質が、どれぐらい集合が大きければ必ず成り立つか研究する分野である。「ラムゼイ理論」について語られるとき、言及されることのおおい最も基本的な結果は次であろう：

「パーティー問題」で検索すれば証明はすぐに見つかる。これの一般化が次の定理である：

この定理で$k=2, r=2, l=3$としたときがパーティー問題で、このとき$N(2,2,3)=6$である。なぜか：

• $S$を人の集合とする。
• 「すべての大きさ2の部分集合が2色で塗られている」=「すべての2人組に知り合いかそうでないかの情報を付与されている」
• 「ある大きさ3の部分集合$S_0$が存在して、$S_0$のいかなる大きさ2の部分集合も同じ色で塗られている」=「ある3人組が存在して、3人組うちのいかなる2人組も同時に知り合いであるか、同時に知り合いでない」

RotaはRamseyの定理を拡張し、次のような予想を立てた。今回読む論文では、Grahamらはこの予想を解決しようとしている。

有限体とは、ざっくり四則演算がうまくできる有限集合のこと。たとえば、位数$q$が素数のときは、集合を$\mathbb{Z}/q\mathbb{Z}$とし、$\mod q$での通常の四則演算を考えればよい。位数$q$が素数でないときは、$\mod q$での乗法逆元がうまくとれないので少し頑張る必要がある。本筋ではないので、これ以降とりあえず有限体は有限だけど+,-,×,÷はいい感じにできる集合だと思ってほしい。$GF(q)$で位数$q$の有限体を表す。
また、アフィン空間についても知っておく必要がある。アフィン空間はざっくり「原点を忘れたベクトル空間」である。ベクトル空間は基底ベクトルの線形結合で表せるが、アフィン空間では原点をどこにとっても良い分、不定性が増える。Rotaの予想はベクトル空間でなくアフィン空間で考えても同値であるらしい。

$n$-parameter set

Grahamらは、有限体上のベクトル空間を真正面から考える代わりに、$n$-parameter setなる概念を導入した。これは有限体上の$n$次元アフィン空間を部分的に模倣する。有限体上のアフィン空間を模倣するには、通常の集合にどのような性質を加えていけばよいだろうか。
$GF(q)$上の$n$次元アフィン空間は、集合としては$q^n$個の$GF(q)$の元の$n$つ組である。なので、$n$-parameter setは$t^n$個の$A=\qty{a_1, a_2, \ldots, a_t}$の元の$n$つ組である必要がある。

$GF(q)^n$の1次元部分アフィン空間は
$$\qty{(x_1, x_2, \ldots, x_n)+\alpha(y_1, y_2, \ldots, y_n) \mid \alpha \in GF(q)}$$
と書ける(和と積は$GF(q)$に入っている演算)。$y_i = 0$(このゼロは$GF(q)$の加法単位元)のとき、$i$番目の成分は$x_i$で固定となり、$y_i \neq 0$のとき、$\qty{x_i + \alpha y_i \mid \alpha \in GF(q)} = GF(q)$となる（任意の$\beta \in GF(q)$に対し$\alpha = (\beta - x_i)y_i^{-1}$と取ればよい）ことに注目すると、$A^n$の1-parameter subsetは$\qty{(a_{i1}, a_{i2}, \ldots, a_{in}) \mid 1 \le i \le t}$の形をしていて、$a_{1j}=a_{2j}=\cdots=a_{tj}$であるか、$a_{1j},a_{2j},\cdots,a_{tj}$が$\qty{a_1, a_2, \ldots, a_t}$の順列である必要がある。

$GF(q)^n$の2次元部分アフィン空間は
$$\qty{(x_1, x_2, \ldots, x_n)+\alpha(y_1, y_2, \ldots, y_n)+\beta(z_1, z_2, \ldots, z_n) \mid \alpha, \beta \in GF(q)}$$と書ける。一般の場合を考えるのは難しいので、任意の$1 \le i \le n$に対して$y_i z_i = 0$である場合のみ考える。ここで、成分を分類することができる：

1. $y_i = 0$かつ$ z_i = 0$のとき、$i \in S_0$
2. $y_i \neq 0$かつ$ z_i = 0$のとき、$i \in S_1$
3. $y_i = 0$かつ$ z_i \neq 0$のとき、$i \in S_2$

このようにすることで、$I_n = \qty{1,2,\ldots,n}$の分割$S_0,S_1,S_2$を得ることができる。
\begin{align*} S_0 &= \qty{k_1,\ldots,k_{n_0}} \\ S_1 &= \qty{i_1,\ldots,i_{n_1}} \\ S_2 &= \qty{j_1,\ldots,j_{n_2}} \\ (n &= n_0 + n_1 + n_2) \end{align*}
とし、見やすくするため項を並び替えてしまおう：
$$\qty{(\overbrace{x_{k_1},\ldots,x_{k_{n_0}}}^{S_0}, \overbrace{x_{i_1}+\alpha y_{i_1},\ldots,x_{i_{n_1}}+\alpha y_{i_{n_1}}}^{S_1}, \overbrace{x_{j_1}+\beta z_{j_1},\ldots,x_{j_{n_2}}+\beta z_{j_{n_2}}}^{S_2}) \mid \alpha, \beta \in GF(q)}$$
これを$A^n$の2-parameter subsetに翻訳すると、
$$\qty{(\overbrace{c_{k_1},\ldots,c_{k_{n_0}}}^{S_0}, \overbrace{a_{t_1i_1},\ldots,a_{t_1i_{n_1}}}^{S_1}, \overbrace{b_{t_2j_1},\ldots,b_{t_2j_{n_2}}}^{S_2}) \mid 1\le t_1\le t,\,1\le t_2\le t}$$
となる。ただし、$a_{1i},a_{2i},\cdots,a_{ti}(i \in S_1)$および$b_{1j},b_{2j},\cdots,b_{tj}(j \in S_2)$は$\qty{a_1, a_2, \ldots, a_t}$の順列である。
このように、普通の有限集合上で、$GF(q)^n$の「都合のいい」部分空間の模倣ができる。1次元までなら完全な模倣ができるが、2次元以上では部分的にしか模倣できていない。
結局のところ、$n$-parameter setは有限体の部分アフィン空間の出来損ないのようなものだと思ってよい。
いままでの気持ちの話を一般の次元について厳密にやると次のようになる：

主定理

以上の道具立てをもって、ようやく主定理のステートメントを読めるようになる。

定理2とよく読み比べてほしい。相当読みづらくなっているが、文の基本構造は変わっていないことがわかるかと思う。

主定理から導かれる"系"たち

$n$-parameter setの構成から考えて、$k \ge 2$ではアフィン空間の$k$次元部分空間を一部しか再現できていないので、こうなる。

面白いのはここからで、実はこの主定理、有限のラムゼイ理論で重要な定理のほとんどを系としてふくんでいるのである。以下にどんな系が導かれるか列挙する。

まずは同じ形をした三つの系から。

次の系が一番ヤバイ見た目をしている：

さらに、次の二つの大定理も含んでいる：

また、当然のごとく、Ramseyの定理自体も系として含んでいる。

さて、ようやく本題である。
$C_n = \qty{(x_1,\ldots,x_n) \mid x_i \in \qty{0, 1}}$を$\mathbb{R}^n$における$n$次元超立方体とし、集合$Q_k \subseteq C_n$が$|Q_k| = 2^k$かつ$\mathbb{R}^n$の$k$次元超平面内に収まっているとき、$Q_k$は$C_n$の$k$-subspaceと呼ぶことにする。

$k=1, l=2, r=2$とすれば次が得られる(系8の系)：

論文ではこのあとに、$N^\star$の評価として
$$N^\star \le F(F(F(F(F(F(F(12,3),3),3),3),3),3),3)$$
を与えている。ただし、$F$は
\begin{align*} F(1, n) &= 2^n &(n \ge 2)\\ F(m, 2) &= 4 &(m \ge 1) \\ F(m, n) &= F(m-1, F(m, n-1)) &(m \ge 2,\; n \ge 3) \end{align*}
で与えられる関数。これが親の顔より見た小グラハム数である。
さらに言うと、（当然ではあるが）小グラハム数は彼らの定理のある種の「使い物にならなさ」の説明としてしか言及されていない。つまり、$N^*$の存在を言うことはできるが、その真の大きさの推定には全く役に立たないと言いたいがために、「こんなに小さい$k, l, r$なのにこんなラフな評価しかできませんよ」と例示したのが小グラハム数なのだ。
この評価よりも大きな（普通の）グラハム数が示されている論文は未出版である。なぜ未出版であるかは、ここまで辛抱強く付き合ってくれた方なら理解できるはずである。

さらなる高みへ……

Grahamらは、より一般的な定理を見つけており、その定理は圏論の言葉を使って記述されている。定理3の時点でステートメントを書ききるのに結構な分量を割かなければいけなかったが、次の定理はステートメントの記述だけで定理3の倍くらいの分量が必要になる。

その定理の系として次が導かれている：

また、圏の言葉で記述された定理は$n$-parameter setに関する定理（定理3）も含んでいるため、小グラハム数は定理4の系の系の系のおまけでしかないことがわかる。
さらに言えばグラハム数はグラハム問題の解のより悪い評価なので、グラハム数は系の系の系のおまけの下位互換といえる(巨大数論的には上位互換だけど)。

余談

巨大数に興味のある人間としては、定理4から導かれる超一般グラハム数とでもいうべき数の大きさが知りたくなったので、筆者はとりあえず定理4の証明を一通り追った。筆者の読みが正しければ、超一般グラハム数を生み出す超一般グラハム関数の大きさは上で定義される$F$の入れ子の増大度($f$を急増加関数として$f_\omega$)を大きく上回らない。もっと言えば、$f_{\omega+1}$で抑えられるであろう。
グラハム問題(系9)は存在が示される数の上限が使い物にならないくらい大きくなってしまう例の”最小構成”だったというわけだ。

参考文献

1. R. L. Graham and B. L. Rothschild, RAMSEY'S THEOREM FOR $n$-PARAMETER SETS ( https://doi.org/10.2307/1996010 )
2. R. Graham, K. Leeb, B. Rothschild, Ramsey's Theorem for a Class of Categories. ( https://doi.org/10.1016/0001-8708(72)90005-9 )