GoucherのT関数

GoucherのT関数とは、組合せ論に起因する、ベクレミシェフの虫の関数Worm(n)に酷似した急成長する関数である。名前の通り、Adam P. Goucherにより考案された。この関数はC8問題という問題を背景に持つため、まずはC8問題とその変形について説明をする。

C8問題とその変形

国際数学オリンピック(IMO)にはたくさんの問題が投稿される。良い問題がショートリストに乗り、とくによい問題６つが本選に使用される。しかし、ショートリスト止まりになる問題も少なからずある。次の問題は、2009年IMOショートリストのC8問題（オーストリアから投稿）である:

整数n≧2に対し、次のような操作を施して得られる整数h(n)を定義する。但し、nの最も右の桁をrとする。

• r=0なら、h(n)=n/10である。つまり、右端のゼロを取り除く。
• それ以外、rが非ゼロなら、次のような操作をする。nの桁数をDと置き、正整数N≦Dに対しnの下N桁をn_Nと置く。n_Nの各桁がr以上となる最大の正整数N≦Dを用いて、n_NをRと置く。残りの部分、つまり(n-n_N)/10^NはLと置く。h(n)を、十進法の位取り記法でLにR-1を2回繰り返して連結して得られる数とする。例えば、n=17151345543なら、r=3、L=17151、R=345543で、R-1=345542、h(n)=17151345542345542である。

全ての整数n≧2に対し、h関数を有限回施すことで、その値を1にすることが出来ることを証明せよ。

例えば、2 → 11 → 1010 → 101 → 1000 → 100 → 10 → 1となる。

この問題は非自明である。さらに、この問題をより難しくした変形を考えることが出来る。h関数ではR-1を2回繰り返していたが、この変種ではc回繰り返す。ここで、cは2から始まり、関数を施すごとに1ずつ増えてゆく数である。例えば、2回目の変形ではR-1を3回、3回目ならR-1を4回…繰り返す。n=2の時の計算ステップはこうである:

2 → 11 → 101010 → 10101 → 10100000 → 1010000 → 101000 → 10100 → 1010 → 101 → 1000000 → 100000 → 10000 → 1000 → 100 → 10 → 1

位取り記法から数列への拡張

C8問題でもそう呼ばれていたが、nを「数」と考えず、文字0,1,2,3,4,5,6,7,8,9の繋がった文字列と考えるべきである。すると、その文字列は9以下の非負整数の空列でない有限列とみなすことが出来る。非負整数の空列でない有限列に対する操作としてh(n)を以下のように再定義することが出来る：

非負整数の空列でない有限列nに対し、次のような操作を施して得られる数列h'(n)を定義する。但し、nの最も右の成分をrとする。

• r=0なら、h'(n)はnの末尾の0を取り除いて得られる整数の有限列である。
• それ以外、rが非ゼロなら、次のような操作をする。nの桁数をDと置き、正整数N≦Dに対しnの末尾N項からなる部分列をn_Nと置く。n_Nの各成分がr以上となる最大の正整数N≦Dを用いて、n_NをRと置く。残りの部分、つまりnの先頭D-N項からなる部分列をLと置く。h'(n)を、LにR-1を2回繰り返して連結して得られる列とする。

ここで、h'(n)の定義においてはnの成分が9以下に限られていないことに注意する。nの成分が全て9以下でありかつ先頭が0でない場合は、nの各成分を連結して得られる文字列が十進法の位取り記法で表す非負整数をn'と置くと、n'≧2ならばh(n')の十進法の位取り記法による表示がh'(n)と一致する。この意味で確かにh'(n)はh(n)の拡張となる。一般にnの先頭が0でない時、Mをnの成分の最大値より大きい数とし、hの計算規則において10の代わりにMを用いて得られる亜種をh_Mと置き、nの各成分をM進法で１桁の数字として連結して得られる文字列がM進法の位取り記法で表す非負整数をn'と置くと、h_M(n')のM進法の位取り記法による表示はMによらずh'(n)と一致する。

C8問題と同様に、cを用いることでこの操作をより複雑にすることが出来る。そうして得られる問題をC8'と呼ぶ。正整数nに対し、nを非負整数の長さ1の有限列とみなした時にこのcを用いた操作で1に達するまでの長さはとても長い。そのステップ数をT(n)とおく。これがGoucherのT関数である。

Goucherによると、このT関数は急増加関数で\(f_{\varepsilon_0}(x)\)ほどである。C8問題の物を用いれば\(f_4(x)\)ほどとなる。似たような関数(グッドスタインの定理を参照)はn=12の時にグラハム数を超える。T(1)=0、T(2)=16、そしてT(3)はとても大きくなる。T(9)まではh'の操作ではなくhの操作で計算することが出来るのでそれに基づいたn=3の時の計算ステップはこうである:

3 → 22 → 212121 → 212120212120212120212120 → 21212021212021212021212 → 212120212120212120212111111 → 212120212120212120212111110212111110212111110212111110212111110212111110 → …

停止性

非負整数の空列でない有限列を順序数へ対応させる関数gを考えよう。g("0")=1とする。g("3420001107000")=ω^g(“231″) + 1 + 1 + 1 + ω^g(“00″) + 1 + ω^g(“6″) + 1 + 1 + 1とする。特に言えば、数を非ゼロ整数に分解し、その桁から1づつ引き、それを基数に対応させ、べき乗の乗数をωとし、すべて足し合わせる操作である。これを再帰的に対応させる。

連続するゼロを消去することはそれをすべて1に替えることで実現できる。もう一つの操作は、 ωⁿをω^n-1cと置き換えるものである。ここで、cは上記と同じである。c < ωであるため、この列は減少していく。

\(\varepsilon_0\)より小さい順序数は整列集合であるため、そこには無限減少列は存在しない。よって、この列は必ず有限回の操作で1に達する。Q.E.D.

Tの増大度が\(f_{\varepsilon_0}(x)\)に相当するならば、ペアノ公理ではTの全域性が証明できない。従って変形の問題C8'は、国際数学オリンピックには難しすぎて出題されないだろう。