フリードマン円列定理

フリードマン円列定理
型	組合せ数学
急増加関数	≥\(f_{\varepsilon_0}(n)\)

フリードマン円列定理とは、特定の性質を持つ円の列の長さについての定理である。数理論理学者の Harvey Friedman は、この定理から巨大な数が生まれることを発見した。この定理を用いて定義される関数\(\textrm{Circle}\)は、ヒドラ関数などと同程度の速さで増大する。

フリードマン円列定理

平面\(\mathbb R^2\)上の、互いに交わらない円(ここでいう「円」は、内部を持たず縁の部分だけの図形)の列\(C_1,C_2,C_3,\cdots,C_n\)が以下の性質を満たすとき、円の列\(C_1,C_2,C_3,\cdots,C_n\)は\(k\)-goodであるという。

• \(k \le i < j \le n \div 2\)かつ、ある位相同型写像\(f : \mathbb R^2 \to \mathbb R^2\)が存在して\(C_i \cup \cdots \cup C_{2i}\)の\(f\)による像が\(C_j \cup \cdots \cup C_{2j}\)の部分集合となるような組\((i,j)\)が存在する。

フリードマン円列定理とは、「任意の正整数\(k\)について、十分長い円の列は\(k\)-goodである」という定理である。

フリードマン円列定理により、\(k\)-goodでない円の列には、長さが最大のものが存在する。この長さを\(\textrm{Circle}(k)\)と表すことで、自然数上の関数\(\textrm{Circle}\)が定義される。

森による言い換え

平面上の互いに交わらない円の有限集合\(S\)は、異なる2つの円\(C,C' \in S\)について「\(C\)が\(C'\)の内部に含まれる」という関係を\(C' \prec C\)と表すことで、順序集合とみなせる。特に、このようにして得た順序集合\((S,\prec)\)は森である。

更に言えば、円の互いに交わらない有限集合\(S,S'\)について、\(\bigcup S\)の\(f\)による像が\(\bigcup S'\)の部分集合となるような位相同型写像\(f\)は、\(C,C'\)を森とみなしたときの\(C\)から\(C'\)への順序埋め込み写像とみなせる。逆に、\(C\)から\(C'\)への順序埋め込み写像が存在すれば、\(\bigcup S\)の\(f\)による像が\(\bigcup S'\)の部分集合となるような位相同型写像\(f\)が存在する。

以上を用いて、\(k\)-good、及び\(\textrm{Circle}\)を森に関する言明に言い換えることができる。

頂点が\(1\)から順に番号付けた森\((\{x_1,x_2,\cdots,x_n\},\prec)\)が\(k\)-goodであるとは、\(k \le i < j \le n \div 2\)かつ、部分森\((\{x_i,\cdots,x_{2i}\},\prec)\)から部分森\((\{x_j,\cdots,x_{2j}\},\prec)\)への順序埋め込みが存在するような組\((i,j)\)が存在することである。

\(\textrm{Circle}(k)\)とは、\(k\)-goodでない番号付けが可能な森の頂点数のうち、最大のものである。

\(\textrm{Circle}(k)\)の値

関数\(\textrm{Circle}\)の値について、以下のことがわかっている。ただし、\(\textrm{Hydra}\)はヒドラ関数である。

• \(\textrm{Circle}(k)\)は奇数
• \(\textrm{Circle}(1) = 3\)
• \(\textrm{Circle}(2) \ge 17\)
• \(k \ge 3\)のとき、\(\textrm{Circle}(2k+5) \ge \textrm{Hydra}(k)\)