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

123

前置きの前置き

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

前置き

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

ラムゼイ理論

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

パーティー問題

6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が必ず存在する。

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

(Ramsey)

$k, l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (k, l, r)$ が存在して、次を満たす：

要素数が $N$ 以上であるような有限集合 $S$ があって、 $S$ のすべての大きさ $k$ の部分集合が $r$ 色で塗られているとする。このとき、（ $S$ をどのようにとっても） $S$ のある大きさ $l$ の部分集合 $S_{0}$ が存在して、 $S_{0}$ のいかなる大きさ $k$ の部分集合も同じ色で塗られている。

この定理で $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らはこの予想を解決しようとしている。

(Rota)

$k, l, r$ を正整数とする。 $F$ を位数が $q$ の有限体とする。このとき、ある（十分大きな）数 $N = N (q, k, l, r)$ が存在して、次を満たす：

次元が $N$ 以上であるような $F$ 上のベクトル空間 $V$ があって、 $V$ のすべての $k$ 次元部分空間が $r$ 色で塗られているとする。このとき、（ $V$ をどのようにとっても） $V$ のある $l$ 次元部分空間 $V_{0}$ が存在して、 $V_{0}$ のいかなる $k$ 次元部分空間も同じ色で塗られている。

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

$n$ -parameter set

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

$G F (q)^{n}$ の1次元部分アフィン空間は
${(x_{1}, x_{2}, \dots, x_{n}) + α (y_{1}, y_{2}, \dots, y_{n}) ∣ α \in G F (q)}$
と書ける(和と積は $G F (q)$ に入っている演算)。 $y_{i} = 0$ (このゼロは $G F (q)$ の加法単位元)のとき、 $i$ 番目の成分は $x_{i}$ で固定となり、 $y_{i} \neq 0$ のとき、 ${x_{i} + α y_{i} ∣ α \in G F (q)} = G F (q)$ となる（任意の $β \in G F (q)$ に対し $α = (β - x_{i}) y_{i}^{- 1}$ と取ればよい）ことに注目すると、 $A^{n}$ の1-parameter subsetは ${(a_{i 1}, a_{i 2}, \dots, a_{i n}) ∣ 1 \leq i \leq t}$ の形をしていて、 $a_{1 j} = a_{2 j} = \dots = a_{t j}$ であるか、 $a_{1 j}, a_{2 j}, \dots, a_{t j}$ が ${a_{1}, a_{2}, \dots, a_{t}}$ の順列である必要がある。

$G F (q)^{n}$ の2次元部分アフィン空間は
${(x_{1}, x_{2}, \dots, x_{n}) + α (y_{1}, y_{2}, \dots, y_{n}) + β (z_{1}, z_{2}, \dots, z_{n}) ∣ α, β \in G F (q)}$ と書ける。一般の場合を考えるのは難しいので、任意の $1 \leq i \leq n$ に対して $y_{i} z_{i} = 0$ である場合のみ考える。ここで、成分を分類することができる：

$y_{i} = 0$ かつ $z_{i} = 0$ のとき、 $i \in S_{0}$
$y_{i} \neq 0$ かつ $z_{i} = 0$ のとき、 $i \in S_{1}$
$y_{i} = 0$ かつ $z_{i} \neq 0$ のとき、 $i \in S_{2}$

このようにすることで、 $I_{n} = {1, 2, \dots, n}$ の分割 $S_{0}, S_{1}, S_{2}$ を得ることができる。
$\begin{aligned} S_{0} & = {k_{1}, \dots, k_{n_{0}}} \\ S_{1} & = {i_{1}, \dots, i_{n_{1}}} \\ S_{2} & = {j_{1}, \dots, j_{n_{2}}} \\ (n & = n_{0} + n_{1} + n_{2}) \end{aligned}$
とし、見やすくするため項を並び替えてしまおう：
${(\overset{S_{0}}{\overset{⏞}{x_{k_{1}}, \dots, x_{k_{n_{0}}}}}, \overset{S_{1}}{\overset{⏞}{x_{i_{1}} + α y_{i_{1}}, \dots, x_{i_{n_{1}}} + α y_{i_{n_{1}}}}}, \overset{S_{2}}{\overset{⏞}{x_{j_{1}} + β z_{j_{1}}, \dots, x_{j_{n_{2}}} + β z_{j_{n_{2}}}}}) ∣ α, β \in G F (q)}$
これを $A^{n}$ の2-parameter subsetに翻訳すると、
${(\overset{S_{0}}{\overset{⏞}{c_{k_{1}}, \dots, c_{k_{n_{0}}}}}, \overset{S_{1}}{\overset{⏞}{a_{t_{1} i_{1}}, \dots, a_{t_{1} i_{n_{1}}}}}, \overset{S_{2}}{\overset{⏞}{b_{t_{2} j_{1}}, \dots, b_{t_{2} j_{n_{2}}}}}) ∣ 1 \leq t_{1} \leq t, 1 \leq t_{2} \leq t}$
となる。ただし、 $a_{1 i}, a_{2 i}, \dots, a_{t i} (i \in S_{1})$ および $b_{1 j}, b_{2 j}, \dots, b_{t j} (j \in S_{2})$ は ${a_{1}, a_{2}, \dots, a_{t}}$ の順列である。
このように、普通の有限集合上で、 $G F (q)^{n}$ の「都合のいい」部分空間の模倣ができる。1次元までなら完全な模倣ができるが、2次元以上では部分的にしか模倣できていない。
結局のところ、 $n$ -parameter setは有限体の部分アフィン空間の出来損ないのようなものだと思ってよい。
いままでの気持ちの話を一般の次元について厳密にやると次のようになる：

n

-parameter set

$A = {a_{1}, a_{2}, \dots, a_{t}} (t \geq 2)$ とする。 $H : A \to A$ を $A$ に作用する置換群とする。 $a \in A$ と $σ \in H$ に対し、 $a \to a^{σ}$ で作用を表す。
部分集合 $B \subseteq A$ に対し写像の集合 $\overset{―}{B} = {\overset{―}{b} ∣ b \in B}$ を定める。ただし、 $\overset{―}{b}$ は $x^{\overset{―}{b}} = b$ で与えられる定数写像である。
$Π = {S_{0}, S_{1}, \dots, S_{k}}$ を $I_{n} = {1, 2, \dots, n}$ の交わりのない分割とする。ただし、 $S_{0}$ 以外は空集合になりえないものとする。
$f : I_{n} \to H \cup \overset{―}{B}$ を次を満たす写像とする：
$\begin{aligned} f (i) \in \overset{―}{B} & if i \in S_{0} \\ f (i) \in H & if i \in I_{n} ∖ S_{0} \end{aligned}$
このとき、
$P (A, B, H, Π, f, n, k) = ⋃_{1 \leq t_{0}, \dots, t_{k} \leq t} {(x_{1}, \dots, x_{n}) ∣ x_{j} = a_{t_{y}}^{f (j)} if j \in S_{y}}$
とし、 $P \subseteq A^{n}$ を $A^{n}$ 上の $k$ -parameter setと呼ぶ。

$P_{l}$ が $A^{n}$ 上の $l$ -parameter setであって、 $P_{k} \subseteq P_{l}$ かつ $P_{k}$ が $A^{n}$ 上の $k$ -parameter setであるとき、 $P_{k}$ を $P_{l}$ の $k$ -parameter subsetと呼ぶ。

主定理

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

Graham-Rothschild (1971)

$A, B \subseteq A$ を集合、 $H$ を $A$ に作用する置換群、 $k, r, t_{1}, t_{2}, \dots, t_{r}$ を正整数とする。このとき $N = N (A, B, H, k, r, t_{1}, t_{2}, \dots, t_{r})$ が存在して、次を満たす：
$n \geq N$ および $n$ -parameter set $P_{n} = P (A, B, H, Π, f, w, n) \subseteq A^{w}$ があって、 $P_{n}$ のすべての $k$ -parameter subsetが $r$ 色で塗られているとする。このとき、（ $P_{n}$ をどのようにとっても）ある色 $1 \leq i \leq r$ が存在して、 $P_{n}$ のある $t_{i}$ -parameter subsetが存在して、そのいかなる $k$ -parameter subsetも同じ色 $i$ で塗られている。

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

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

(Rotaの予想の部分的解決)
$k$ を0または1とすれば、Rotaの予想は正しい。

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

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

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

$l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (l, r)$ が存在して、次を満たす：

要素数が $N$ 以上であるような有限集合 $S$ があって、 $S$ のすべての部分集合が $r$ 色で塗られているとする。このとき、 $l$ 個の互いに交わらない空でない部分集合 $S_{1}, S_{2}, \dots, S_{l}$ が存在して、それらの $2^{l} - 1$ 種類の和集合がすべて同じ色で塗られている。

(Folkman-Rado-Sanders)
$l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (l, r)$ が存在して、次を満たす：

$n \geq N$ について、 $n$ 以下の自然数が $r$ 色で塗られているとする。このとき、 $l$ 個の自然数 $a_{1}, a_{2}, \dots, a_{l}$ が存在して、それらの $2^{l} - 1$ 種類の和がすべて同じ色で塗られている。

$l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (l, r)$ が存在して、次を満たす：

要素数が $N$ 以上であるような群 $G$ があって、 $G$ のすべての元が $r$ 色で塗られているとする。このとき、 $l$ 個の元 $a_{1}, a_{2}, \dots, a_{l}$ が存在して、それぞれの元を0回または1回掛けた（単位元を除く） $2^{l} - 1$ 種類の積がすべて同じ色で塗られている。

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

二つの互いに交わらない集合 ${x_{i} \in N ∣ 1 \leq i \leq n}$ と ${y_{i} \in N ∣ 1 \leq i \leq n}$ について、 $m$ 連立方程式
$\sum_{i = 1}^{n} x_{i}^{k} = \sum_{i = 1}^{n} y_{i}^{k} for 1 \leq k \leq m \dots (⋆)$
を考える。
方程式 $(⋆)$ が正整数解をもつとき（ $n \geq 2^{m - 1}$ なら必ず存在するらしい）、正整数をどのように $r$ 色で塗分けたとしても、同じ色で塗られている正整数のみからなる方程式 $(⋆)$ の解が存在する。

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

(van der Werden)
$l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (l, r)$ が存在して、次を満たす：

$n \geq N$ について、 $n$ 以下の自然数が $r$ 色で塗られているとする。このとき、長さ $l$ の等差数列が存在して、数列の要素がすべて同じ色で塗られている。

(Hales-Jewett)
$l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (l, r)$ が存在して、次を満たす：

一辺の長さが $l$ の $n$ 次元超立方体の格子点が $r$ 色で塗分けられているとき、縦・横・ななめなど任意の方向の一列があって、その格子点がすべて同じ色で塗られている。

あるいは、 $n$ 次元 $l^{n}$ マス $r$ 人マルバツゲームは必ず終了する。

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

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

$k, l, r$ を正整数とする。このとき、ある（十分大きな）数 $N = N (k, l, r)$ が存在して、次を満たす：

$n \geq N$ であるような $n$ について $C_{n}$ のあらゆる $k$ -subspaceが $r$ 色で塗られているとする。このとき、ある $l$ -subspaceが存在し、そのすべての $k$ -subspaceが同じ色で塗られている。

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

(グラハム問題)
ある（十分大きな）数 $N^{*} = N (1, 2, 2)$ が存在して、次を満たす：

$n \geq N$ であるような $n$ について $n$ 次元超立方体のあらゆる辺が2色で塗られているとする。このとき、ある同一平面上の4点が存在し、それらを結ぶすべての辺が同じ色で塗られている。

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

さらなる高みへ……

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

Graham-Leeb-Rothschild (1972)

とある条件を満たす圏の類(という言い方が正しいかわからないが...)について、ラムゼイの定理の類似が成り立つ。(詳しいステートメントは参考文献2を参照)

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

Rotaの予想は正しい。

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

余談

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

参考文献

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

投稿日：29日前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

川面

423

他の人のコメント

コメントはありません。

読み込み中

川面

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

前置きの前置き
前置き
ラムゼイ理論
$n$-parameter set
主定理
主定理から導かれる"系"たち
さらなる高みへ……
余談
参考文献

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

前置きの前置き

前置き

ラムゼイ理論

n-parameter set

主定理

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

さらなる高みへ……

余談

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

$n$ -parameter set