巨大関数失格 関数の増大度の相転移

$a = 1$のとき、$1\underbrace{0\cdots0}_{0 \le i < b}$の形の列で全て網羅できているので、条件を満たすbit列は${}_bC_a = b$個である。

$a > 1$の場合は、帰納法の仮定「$1$の個数がちょうど$a-1$個であり、先頭が$1$であり、長さが$b$以下であるようなbit列は、ちょうど${}_{b-1}C_a$個である」を用いて示そう。
$1$の個数がちょうど$a$個であり、先頭が$1$であり、長さが$b$以下であるようなbit列は、ある自然数$i$と、「$1$の個数がちょうど$a-1$個であり、先頭が$1$であるbit列」$S$を用いて、$1\underbrace{0\cdots0}_iS$の形で表せる。このbit列の長さは$b$以下なので、$i \le b-a$であり、$S$の長さは$b-i-1$以下である。
各$i$について、帰納法の仮定により$S$はちょうど${}_{b-i-1}C_{a-1}$通りであるため、$1$の個数がちょうど$a$個であり、先頭が$1$であり、長さが$b$以下であるようなbit列の総数は$\Sigma_{0 \le i \le b-a}\ {}_{b-i-1}C_{a-1} = \Sigma_{a-1 \le i \le b-1}\ {}_iC_{a-1} =\ _bC_a$である。□

まず、ちょうど$k$個の$1$を含む列は、$\underbrace{0\cdots0}_{a_0}1\underbrace{0\cdots0}_{a_1}1\cdots1\underbrace{0\cdots0}_{a_{k-1}}1\underbrace{0\cdots0}_{a_k}$の形で表されるので、$k+1$個の自然数の組$(a_0,a_1,\cdots,a_{k-1},a_k)$と表される。以降はちょうど$k$個の$1$を含むbit列をこの形式で表す。
$(a_0,a_1,\cdots,a_{k-1},a_k)$が$(b_0,b_1,\cdots,b_{k-1},b_k)$の部分列であることと、任意の$i \le k$について$a_i \le b_i$であることが同値であることに注意せよ。特に、$(b_0,b_1,\cdots,b_{k-1},b_k)$が$(a_0,a_1,\cdots,a_{k-1},a_k)$より辞書式順序で小さければ、$(a_0,a_1,\cdots,a_{k-1},a_k)$は$(b_0,b_1,\cdots,b_{k-1},b_k)$の部分列にはならない。

ここで、ちょうど$k$個の$1$を含み少なくとも$1$個の$0$を含むbit列と自然数の組を受け取り、同様にちょうど$k$個の$1$を含むbit列と自然数の組を返す写像$E$を以下のように定める。

• $a_k > 0$ならば、$E(a_0,\cdots,a_{k-1},a_k)[n] := (a_0,\cdots,a_{k-1},a_k-1)[n+2]$である。
• $a_k = 0$である場合、$(a_0,\cdots,a_{k-1},a_k)$は少なくとも$1$個の$0$を含むので、$a_i > 0$を満たす$i < k$が存在する。そのような$i$のうち最大のものを$m$としよう。$E(a_0,\cdots,a_k)[n] := (a_0,\cdots,a_{m-1},a_m-1,n+2,a_{m+2},\cdots,a_k)[0]$である。

この写像$E$は、入力も出力も同じ形式なので、bit列側が$(\underbrace{0,\cdots,0}_{k+1})$になるまで反復できる。$n$回反復したものを$E^n$と表すことにしよう。
このとき、$E^{n-1}(1,\underbrace{0,\cdots,0}_k)[0]$のbit列側を$X_n$として定める。$E^{n-1}(1,\underbrace{0,\cdots,0}_k)[0] = (\underbrace{0,\cdots,0}_{k+1})[m]$を満たす$m$が存在するような$n$を$N$とおくことで、bit列の列$X_1,X_2,\cdots,X_N$が定義される。
これが3つの条件を満たすことを確認しよう。
$(a_0,\cdots,a_k)$の長さが$k+\Sigma_{i \le k}a_i$であることに気を付けつつ$E$の定義を観察すると、$E$はbit列長と自然数の和をちょうど$1$増やすことがわかる。$(1,\underbrace{0,\cdots,0}_k)[0]$ではこの値が$k+1$なので、$E^{i-1}(1,\underbrace{0,\cdots,0}_k)[0]$ではこの値が$i+k$となる。特に、任意の$1 \le i \le N$について、$X_i$の長さは$i+k$以下である。
$X_i$がちょうど$k$個の$1$を含むことは自明。
また、$E$はbit列側において、$k+1$個組の自然数による表示を辞書式順序で減少させる。つまり、$X_1,X_2,\cdots,X_N$は辞書式順序による狭義単調減少列であり、任意の$1 \le i < j \le N$について$X_j$は$X_i$より辞書式順序で小さい。従って、$X_i$は$X_j$の部分列ではない。
以上により、$X_1,X_2,\cdots,X_N$が3条件を満たすことが確認された。

最後に、$(1,\underbrace{0,\cdots,0}_k)[0]$に$E$を何回反復すればbit列側が$(\underbrace{0,\cdots,0}_{k+1})$になるかを確認する。
もし、$E^{N-1}(1,\underbrace{0,\cdots,0}_k)[0] = (\underbrace{0,\cdots,0}_{k+1})[m]$と表されるならば、$E$が常にbit列の長さと自然数の和を$1$ずつ増やすことから、$m = N$である。よって、ここでは実際に何回反復するかではなく、bit列側が$(\underbrace{0,\cdots,0}_{k+1})$になった際に組となる自然数がいくつになったかを確認するという手法をとる。
$E$の反復でbit列の$k+1$組表示において最も右にある$0$でない成分を$1$減らしたときに、組となる自然数がどう変化するかを、順番に見ていこう。
便宜的に、ここからは項の番号を右から順に$(a_k,\cdots,a_0)$のように数えていく。

$(a_k,\cdots,a_0+1)[n]$に$E$を適用すると、$(a_k,\cdots,a_0)[n+2]$となる。
$(a_k,\cdots,a_1+1,0)[n]$に$E$を適用すると、$(a_k,\cdots,a_1,n+2)[0]$となり、更に$n+2$回$E$を適用することで$(a_k,\cdots,a_1,0)[2n+4] = (a_k,\cdots,a_1,0)[A_0(n+4)-4]$となる。
以降は帰納法によって示そう。$(a_k,\cdots,a_{i+1}+1,\underbrace{0,\cdots,0}_{i+1})[n]$に$E$を有限回適用するといずれは$(a_k,\cdots,a_{i+1},\underbrace{0,\cdots,0}_{i+1})[A_i(n)]$になると仮定する。$(a_k,\cdots,a_{i+2}+1,\underbrace{0,\cdots,0}_{i+2})[n]$に$E$を$1$回適用すると$(a_k,\cdots,a_{i+2},n+2,\underbrace{0,\cdots,0}_{i+1})[0] = (a_k,\cdots,a_{i+2},n+2,\underbrace{0,\cdots,0}_{i+1})[A_i(A_i(1))-4]$となり、仮定によりここから$E$を有限回適用すれば$(a_k,\cdots,a_{i+2},n+1,\underbrace{0,\cdots,0}_{i+1})[A_i(A_i(A_i(1))-4+4)-4] = (\textrm略)[A_i(A_i(A_i(1)))-4]$となる。同様に$n+1$回仮定を用いると、毎回$A_i$の中と外の$-4$と$+4$が打ち消し合い、$E$の有限回の適用により$(a_k,\cdots,a_{i+2},0,\underbrace{0,\cdots,0}_{i+1})[A_i^{n+4}(1)-4] = (a_k,\cdots,a_{i+2},\underbrace{0,\cdots,0}_{i+2})[A_{i+1}(n+4)-4]$となる。
帰納法により、任意の$i \le k$について、$(a_k,\cdots,a_{i+1}+1,\underbrace{0,\cdots,0}_{i+1})[n]$に$E$を有限回適用するといずれは$(a_k,\cdots,a_{i+1},\underbrace{0,\cdots,0}_{i+1})[A_i(n)]$となる。

$i = k$の場合を用いれば、$(1,\underbrace{0,\cdots,0}_k)[0]$に$E$を有限回適用することで、$(\underbrace{0,\cdots,0}_{k+1})[A_k(4)-4]$となることがわかる。以上により、$N = A_k(4)-4$である。□

$x \ge (4(n+1))^{n+1}$であるような$x$について考察しよう。
明らかに、$x \ge 2n+1$であり、$\dfrac{(2x+2)(n+1)}{x-n}$は$x > n$で単調減少であることから$\dfrac{(2x+2)(n+1)}{x-n} \le 4(n+1)$である。
また、$2x+2 \ge (4(n+1))^{n+1} \ge (\dfrac{(2x+2)(n+1)}{x-n})^{n+1}$である。両端に注目して整理すると、$(2x+2)^n \le (\dfrac{x-n}{n+1})^{n+1}$となり、更に$\le \ _xC_{n+1}$である。
$(2x+2)^n \le \ _xC_{n+1}$を満たす最小の自然数$x$を$d$とおく。$(4(n+1))^{n+1} \ge d$である。

ここから、実際に$\textrm{bit}_f$の条件を満たす列$X_1,X_2,\cdots,X_N$を構成していくが、そのために、まずは補題4によって示された、$\{Y_i\}_{1 \le i \le A_k(4)-4}$を取る。$Y_i$の長さは$i+k$以下で、ちょうど$k$個の$1$が含まれる。更に、任意の$1 \le i < j \le A_k(4)-4$について、$Y_i$は$Y_j$の部分列にならない。

まず、$1 \le i \le \ _{k+d}C_{n+1}$であるときの$X_i$として、$1$の個数が$2k$個より多いものを並べる。列の長さが$2k+(4(n+1))^{n+1}$以下で、$1$の個数がちょうど$2k + (4(n+1))^{n+1}-(n+1)$個あるものは、$_{2k+(4(n+1))^{n+1}}C_{2k + (4(n+1))^{n+1}-(n+1)} =\ _{2k+(4(n+1))^{n+1}}C_{n+1} \ge\ _{k+d}C_{n+1}$個以上あるので、これらを並べればよい。
以降は$1$の個数がちょうど$2k$個のbit列のみ並べるので、これらの$1$を$2k$個より多くもつbit列は埋め込めない。

任意の$1 \le j \le A_k(4)-4$について、$_{k+d+j-1}C_{n+1} < i \le\ _{k+d+j}C_{n+1}$であるときの$X_i$として、$Y_jB$の形のものを考える。ただし、$B$は長さが$k+d+j$以下であり、$1$がちょうど$k$個含まれており、先頭も$1$であるbit列である。$B$は$_{k+d+j}C_{n+1}$個以上存在し、$B$部分の長さが降順になるように並べれば、$_{k+d+j-1}C_{n+1} < i < i' \le\ _{k+d+j}C_{n+1}$の場合に$X_i$は$X_{i'}$の部分列とならないようにできる。
$X_i$の長さは$Y_j$の長さに$B$の長さを足しているので、$(k+j)+ (k+d+j) \le 2(k+d+j) \le\ (_{k+d+j-1}C_{n+1})^{\dfrac1n}$以下である。

従って、このように構成した列$X_1,\cdots,X_{_{k+d+A_k(4)-4}C_{n+1}}$は、$\textrm{bit}_f(2k+(4(n+1))^{n+1})$の長さの条件を満たす。
あとは$i < i'$のときに$X_i$が$X_{i'}$の部分列とならないことを示せばよい。とはいえ、$i \le\ _{k+d}C_{n+1}$の場合や、ある$1 \le j \le A_k(4)-4$について$_{k+d+j-1}C_{n+1} < i < i' \le\ _{k+d+j}C_{n+1}$である場合は既に確認済みである。
そうでない場合は、ある$1 \le j < j' \le A_k(4)-4$について、$_{k+d+j-1}C_{n+1} < i \le\ _{k+d+j}C_{n+1}$かつ$_{k+d+j'-1}C_{n+1} < i' \le\ _{k+d+j'}C_{n+1}$となる。このとき、$X_i = Y_jB$かつ$X_{i'} = Y_{j'}B'$を満たす、ちょうど$k$個の$1$をもち、先頭が$1$であるようなbit列$B,B'$が存在する。$X_i$が$X_{i'}$の部分列ならば、両者ともに$1$の個数が等しいので、右から($1$から数えて)$k$番目の$1$より左側同士も部分列となる。すなわち$Y_i$は$Y_{i'}$の部分列であるが、これは$\{Y_i\}_{1 \le i \le A_k(4)-4}$が補題4を満たすことに反する。よって、$X_i$は$X_{i'}$の部分列ではない。
以上により、bit列の列$X_1,\cdots,X_{_{k+d+A_k(4)-4}C_{n+1}}$は、$\textrm{bit}_f(2k + (4(n+1))^{n+1})$の部分列の条件を満たす。
この長さは$A_k(4)$以上なので、$\textrm{bit}_f(2k + (4(n+1))^{n+1}) \ge A_k(4)$である。□

$X_1,\cdots,X_N$が$\textrm{bit}_f(k)$の条件を満たすと仮定する。$X_1 = x_0\cdots x_{l-1}(x_i \in \{0,1\})$とおく。また、$y_i := 1-x_i$とおく。
$n > 0$のとき、$X_1$を部分列にもたない長さ$n$以下の列について考えよう。このような列は、そもそも$x_0$を部分列にもたないか、ある$0 < i < l$について、$x_0\cdots x_{i-1}$を部分列にもつが$x_0\cdots x_i$を部分列にもたないかのいずれかである。
前者は$y_0y_0\cdots y_0$の形のbit列しかなく、このうち長さ$n$以下のものは$n+1$個しかない。
後者は$y_0\cdots y_0x_0y_1\cdots y_1x_1y_2 \cdots\cdots x_{i-1}y_i\cdots y_i$のような形のbit列になる。このとき、各$x_i$が何文字目であるかの値と、bit列の長さ$+1$は、いずれも$1$以上$n+1$以下でありそれぞれ異なる値を取る。bit列はこの$i+1$個の値で決定されるので、$_{n+1}C_{i+1}$個である。
従って、$X_1$を部分列にもたない長さ$n$以下の列は、$(n+1) + \Sigma_{0< i< l}\ _{n+1}C_{i+1} \le \Sigma_{i\le l}\ _{n+1}C_i \le \Sigma_{i\le l}(n+1)^l = (l+1)(n+1)^l \le 2^l(l+1)n^l$個以下となる。

$X_{f(1)+2},\cdots,X_N$は、明らかにそれぞれ異なる。また、それぞれの長さは$f(N) = N^{\dfrac1{F^{-1}(N)}}$以下である。これらはいずれも$X_1$を部分列にもたないので、高々$2^l(l+1)N^{\dfrac l{F^{-1}(N)}}$以下である。
よって、$N-f(1)-1 \le 2^l(l+1)N^{\dfrac l{F^{-1}(N)}}$である。
$N \ge 2(f(1)+1)$である場合、$N \le 2N-2(f(1)+1) \le 2^{l+1}(l+1)N^{\dfrac l{F^{-1}(N)}}$である。よって、$N^{1-\dfrac l{F^{-1}(N)}} \le 2^{l+1}(l+1)$である。
$N \ge F(2l)$の場合、$F^{-1}(N) \ge 2l$なので$N^{\dfrac12} \le N^{1-\dfrac l{F^{-1}(N)}} \le 2^{l+1}(l+1)$である。つまり、$N \le 2^{l+2}(l+1)^2$である。
以上と$l \le k+f(1)$により、$N \le \max\{2(f(1)+1),F(2l),2^{l+2}(l+1)^2\} \le 2(f(1)+1)+\Sigma_{l \le k + f(1)}(F(2l) + 2^{l+2}(l+1)^2)$である。
この左辺$2(f(1)+1)+\Sigma_{l \le k + f(1)}(F(2l) + 2^{l+2}(l+1)^2)$は、定数、和、積、冪、総和、原始再帰関数の合成も原始再帰となることから、$k$についての原始再帰であるとわかる。以上により、$\textrm{bit}_f(k)$は原始再帰的な上限をもつ。

$\textrm{bit}_f$が原始再帰関数によって上から抑えられるとする。すると、$\textrm{bit}_f(2n+(4(n+1))^{n+1})$も原始再帰関数であり、$F(n)$に支配される。すなわち、ある自然数$N$が存在して、任意の$n > N$について、$\textrm{bit}_f(2n+(4(n+1))^{n+1}) < F(n)$が成り立つ。
このとき、任意の$i \le \textrm{bit}_f(2n+(4(n+1))^{n+1})$について$F^{-1}(i) < n$であり、よって$f(i) \ge i^{\dfrac1n}$である。
末尾が空列で、長さが$\textrm{bit}_f(2n+(4(n+1))^{n+1})+1$であるbit列の列$X_1,\cdots,X_{\textrm{bit}_f(2n+(4(n+1))^{n+1})},\epsilon$を任意に取る。これが$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1})$の条件を満たすとき、それは$\textrm{bit}_f(2n+(4(n+1))^{n+1})$の条件を満たしてしまい、最大性に矛盾する。すなわち、末尾が空列で、長さが$\textrm{bit}_f(2n+(4(n+1))^{n+1})+1$であるbit列の列であって、$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1})$の条件を満たすものは存在しない。
特に、ここの空列$\epsilon$を他の列に書き換えた任意のbit列の列$X_1,\cdots,X_{\textrm{bit}_f(2n+(4(n+1))^{n+1})+1}$も$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1})$の条件を満たさないので、$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1}) \le \textrm{bit}_f(2n+(4(n+1))^{n+1})$が成り立つ。
定理5より、$\textrm{bit}_f(2n+(4(n+1))^{n+1}) \ge \textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1}) \ge A_n(4)$が成り立つ。

しかし、$A_n(4)$は任意の原始再帰的な関数を支配するので、これは$\textrm{bit}_f(2n+(4(n+1))^{n+1})$が原始再帰関数を上限にもつことに反する。
背理法により、$\textrm{bit}_f$には原始再帰的な上限が存在しない。

$\textrm{bit}_f(2n+(4(n+1))^{n+1}) < F(n) = A_n(4)$と仮定する。
bit列の列$X_1,\cdots,X_{\textrm{bit}_f(2n+(4(n+1))^{n+1})+1}$を任意に取る。これが$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1})$の条件を満たすならば、$X_1,\cdots,X_{\textrm{bit}_f(2n+(4(n+1))^{n+1})},\epsilon$も条件を満たす。
任意の$1 \le i \le \textrm{bit}_f(2n+(4(n+1))^{n+1})$について$X_i$の長さが$i^{\dfrac1n} + 2n+(4(n+1))^{n+1}$以下なので、特に$f(i) + 2n+(4(n+1))^{n+1}$以下である。従って、$X_1,\cdots,X_{\textrm{bit}_f(2n+(4(n+1))^{n+1})},\epsilon$が$\textrm{bit}_f(2n+(4(n+1))^{n+1})$の条件を満たしてしまい、最大性に反する。
従って、$\textrm{bit}_f(2n+(4(n+1))^{n+1})$より大きい長さをもち、$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1})$の条件を満たすものは存在しない。特に、$\textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1}) \le \textrm{bit}_f(2n+(4(n+1))^{n+1})$である。
定理5より、$A_n(4) \le \textrm{bit}_{x^{\dfrac1n}}(2n+(4(n+1))^{n+1}) \le \textrm{bit}_f(2n+(4(n+1))^{n+1})$である。これは仮定に反する。
従って、$\textrm{bit}_f(2n+(4(n+1))^{n+1}) \ge A_n(4)$である。これは任意の原始再帰関数を支配する。□