2005年11月16日（水）

「ホフスタッター数列群」仮稿２

　前回の更新から2ヶ月、最新1か月分の記事を表示するこの日記システムも、あまり意味を成さなくなっていますね。
　さて、この間のROSESダーツ大会の様子はどうだったかというと、万全の態勢で大会に臨むという姿勢が奏功し、高得点が出るようになりました。
　9月大会では445点を叩き出し、一時トップに立っていたのですが、伏兵コズン・グラハムが大会初の500点台となる505点を付けて月間1位となるとともに、年間成績でも約90点差まで追い上げてきました。仮にこの調子が10月からの3ヶ月間続いたとすると、私ガルマ・ザビの年間トップも危うくなってきます。せっかくキャプテンシャア・アズナブルから年間トップもチャンピオン大会に出場できるとの言質を取ったというのに。
　そこで10月大会ではさらに奮起して、半分の4ラウンド目までで300点以上という高調子を維持し、最終的には489点という、練習でも出したことのない自身最高得点で、月間1位を確定しました。年間2位以下も不調だったり不参加だったりで、約300点の差が開き、年間成績でも私の優位がほぼ確定いたしました。念願のチャンピオン大会出場資格獲得です。
　ご声援ありがとうございます。この好成績に気を緩めることなく、残りの2ヶ月も全力で臨んで月平均400点を目指し、チャンピオン大会でも奮戦していきたいと思います。
　さて、11月16日は、去年プレオープンサイトでも申し上げましたが、当サイトにて構想中のRPG素案『魔法乱舞（マジカルラプソディー）ジュエリーアイズ』の主人公、ピュリス=ミナヅキの誕生日です。去年はこの機を捉えて、物語の一端を紹介させていただきました。今年もそうできればちょうどよかったのですが、漫然とした忙しさに紛れて設定やストーリーの整備が進まず、皆様に新たにご紹介できるものが準備できていないのが残念なところです。
　当コンソーシアムの一員、REMWIN研究所の点字研究室では世界中の点字を収集し、紹介しています。点字がどのように設計されているかということについても知見を得ているのですが、点字研究室では点字の形（点形）に従って整理するのみで、それぞれの言語や分野でどのようになっているのかについて統一的に紹介してきませんでした。この場で一度点字について解説してみたいと思っていましたが、点字のような図形的な対象を扱うには当日記コーナーを表示するプログラムを調整する必要がありますので、もう少し先のことになるでしょう。
　ところで、アクセス解析を見ることがあるのですが、「ホフスタッター数列」とか「コンウェイ数列」とかなどのキーワードで当サイトにご訪問くださる閲覧者様もけっこういらっしゃるようです。当サイトをホフスタッター研究のひとつの拠点とみなしていただけるということは、たいへんありがたいことです。そこで今回は、4月にご紹介した「ホフスタッター数列群」についてもう一度考察してみようと思います。
　「ホフスタッター数列群（Hofstadter sequences）」とは「ホフスタッター型高階再帰数列（Hofstadter-type high-order recursive sequences）」の略称で、「ホフスタッターG数列（Hofstadter G-sequence）」「ホフスタッターQ数列（Hofstadter Q-sequence）」「ホフスタッター・コンウェイの10,000ドル数列（Hofstadter-Conway 10,000-dollar sequence）」、および、これらの数列に類似の方法で生成され、類似の性質を示す数列の総称と、4月の記事では定義していました。もう少し正確には「引数と1とを有限回加算・減算し、その数を引数とする項を算出し、その項と引数と1と、さらにはそれ以前に算出されたすべての項とを有限回加算・減算することを有限回繰り返して得られたひとつの数式を再帰式とし、有限の個数の値を初期値として得られる無限数列で、すべての自然数の引数で自然数の値をとり、基本的に増加傾向を示し、グラフで表現したときに一次直線など、単純な多項式で表される曲線によっておおむね近似されるもの」とも定義していましたが、これが若干（というか、かなり）わかりにくいものでしたので、具体的な例に基づいて解説することにします。
　ここでは、「ホフスタッター数列群」の代表としてホフスタッターG数列（G[1]=1, G[n]=n-G[G[n-1]]（n≧2））・ホフスタッターQ数列（Q[1]=Q[2]=1, Q[n]=Q[n-Q[n-1]]+Q[n-Q[n-2]]（n≧3））・ホフスタッター・コンウェイの10,000ドル数列（a[1]=a[2]=1, a[n]=a[a[n-1]]+a[n-a[n-1]]（n≧3））を例として解説していきます。
　上記の定義の「引数」とは、自然数値をとる変数 n です。「引数と1とを有限回加算・減算し」とは、整数係数をとる n の1次式を作ることです。n-1 は n から 1 を減算したもの、n-2 は n-1 から 1 を減算したものです。n 自身も、n に有限回の一種である0回加算・減算を施したものとみなすことができます。上記の各定義式に登場する n, n-1, n-2 は、この定義に合致します。しかし、乗算・除算は許されていませんので、n^2 や n/2 などを作ることはできません。
　「その数を引数とする項を算出し」とは、上で作った式に数列を表す記号 a[…] を被せて、ひとつの項を表す式を作ることです（数列を表す記号は、それぞれの数列に応じて別の記号を用いる場合もあります）。上記の定義式に登場する G[n-1], Q[n-1], Q[n-2], a[n-1] は、この定義に合致します。
　「その項と引数と1と、さらにはそれ以前に算出されたすべての項とを有限回加算・減算することを有限回繰り返し」とは、上の2種類の操作を繰り返すことです。G数列では、G[n-1] にさらに G[…] を被せて G[G[n-1]] を作り、n から減算しています。Q数列では、Q[n-1], Q[n-2] をそれぞれ n から減算し、それぞれに Q[…] を被せて、ふたつの式を加算しています。10,000ドル数列では、a[n-1] にさらに a[…] を被せて a[a[n-1]] を作り、また、n から a[n-1] を減算して a[…] を被せて a[n-a[n-1]] を作って、ふたつの式を加算しています。「得られたひとつの数式を再帰式とし」とは、こうして作った式を a[n] と等号で結んで、数列 a[n] を定義する再帰式を作ることです。
　再帰数列は初期値が存在しないと定義できません。G数列は G[1]=1 、Q数列は Q[1]=Q[2]=1 、10,000ドル数列は a[1]=a[2]=1 を初期値としています。「有限の個数の値を初期値として」と定義していますので、初期値の個数はいくつでもかまいません。
　ただし、再帰式や初期値の設定によっては「無限数列」にならなかったり、「すべての自然数の引数で自然数の値」をとらなかったりする場合もあります。これらの再帰式は複雑なのでいろいろな可能性が考えられますが、a[n] を計算する過程で a[n] 以降の項や a[0] 以前の項を参照する必要に迫られる事態に陥った場合、これらの項は定義されていないので a[n] も定義できず、数列の算出が停止して無限数列にはならなくなります。また、初期値が整数ならば定義上すべての項が整数になりますが、再帰式が減算を使用している場合、項が 0 や負になることも考えられます（後に a[0] 以前の項を参照する事態にも繋がりかねません）。G数列・Q数列・10,000ドル数列はいずれも、（幸いにも）すべての n について計算していくことが可能です。
　「基本的に増加傾向を示し」としていますが、部分的に減少する場合があってもかまいません。G数列と10,000ドル数列は広義単調増加（m＜n ならば a[m]≦a[n]）ですが、Q数列は激しく乱高下を繰り返します。ただし、整数列ですので、上に有界だといずれは増加傾向が消失することになることから、基本的には無限大に発散するという条件がつきます。
　「グラフで表現したときに一次直線など、単純な多項式で表される曲線によっておおむね近似される」というように、G[n]≒((-1+√5)/2)n, Q[n]≒n/2, a[n]≒n/2 と近似されます。放物線などの二次曲線で近似される数列も知られていますが、3次以上の曲線で近似される数列はまだ見かけていません。再帰数列として最も有名なフィボナッチ数列（F[1]=F[2]=1, F[n]=F[n-1]+F[n-2]（n≧3））は、再帰式や初期値の設定は定義に合致しますが、F[n]≒(((-1+√5)/2)^n)/√5 と指数関数でしか近似できませんので、「ホフスタッター数列群」には含まれないとしておきます。
　以上が、「ホフスタッター数列群」の定義のあらましです。フィボナッチ数列のような反例もありますので、基本的には、再帰式や初期値を定義どおりに設定したのち、実際に数列を算出してその性質を見出し、残りの定義に合致するか検証することになるでしょう。
　4月の記事では、この定義の範囲内で10,000ドル数列を一般化することを考えました。10,000ドル数列の一般化には3つの方向性があります。
・初期値の個数を一般化する「一般化コンウェイ数列（Generalized Conway sequences）」
　a[1]=…=a[c+1]=1, a[n]=a[a[n-1]]+a[n-a[n-1]]（n≧c+2）
（c=1 ならば10,000ドル数列、c=2 ならばコンウェイ数列です）
・引数から減算する数を一般化する「一般化マローズ数列（Generalized Mallows sequences）」
　a[1]=…=a[m+1]=1, a[n]=a[a[n-m]]+a[n-a[n-m]]（n≧m+2）
（m=1 ならば10,000ドル数列、m=2 ならばマローズ数列です）
・再帰の深さを一般化する「一般化グリッチュク数列（Generalized Grytczuk sequences）」
　a[1]=a[2]=1, a[n]=a[a^(g)[n-1]]+a[n-a^(g)[n-1]]（n≧3）
　ただし、a^(0)[n]=n, a^(t)[n]=a[a^(t-1)[n]]
（g=1 ならば10,000ドル数列、g=2 ならばグリッチュク数列です）
　これら3つの一般化を同時に適用したのが、次の再帰式によって定義される「ホフスタッターのドローブリッジ数列（Hofstadter's drawbridge sequences）」です。
・H{c,m,g}[n]=1（1≦n≦c+m）
・H{c,m,g}[n]=H{c,m,g}[H^(g){c,m,g}[n-m]]+H{c,m,g}[n-H^(g){c,m,g}[n-m]]（n≧c+m+1）
（ただし、H^(0){c,m,g}[n]=n, H^(t){c,m,g}[n]=H{c,m,g}[H^(t-1){c,m,g}[n]] とする）
　10,000ドル数列は 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, ... と続き、すべての項はその前項に等しい、もしくは1大きい（階差数列が0または1のみで構成される）という性質を持っていますが、一般のドローブリッジ数列もこの性質を持っているということは数学的帰納法によって証明することができます（証明は省略します）。
　一般にドローブリッジ数列は、c, m, g の値によって定まる定数 a（0≦a≦1）が存在して、H{c,m,g}[n]≒an と近似できると考えられています。lim[n→∞] H{c,m,g}[n]/n が存在する場合、この極限を H[c,m,g] とすると、B{c,m,g}[n]=H{c,m,g}[n]-nH[c,m,g] で定義される数列はx軸あたりを推移する数列になります。この数列群を「ホフスタッターのブラマンジェ数列（Hofstadter's blancmanger sequences）」と呼びます。
　「ホフスタッター数列群」の実用的な応用法のひとつとして、これをフラクタルの整数による近似とみなして、描画ソフトなどへの応用が考えられています。「ホフスタッター数列群」は整数列ですので、厳密には無限小数を無限回計算する必要がある真正のフラクタルに比べて格段に計算が高速にはなりますが、無限大に発散する（必要なスケールに比較して過大な数値をとる）という問題があります。ブラマンジェ数列は0に近い値をとりますので、適当なブラマンジェ数列を求めて描画したい図形に沿わせれば、近似的にフラクタル図形が描画できるでしょう。
　しかし、この議論の前提となるブラマンジェ数列ですが、実は極限 H[c,m,g] が必ずしも存在するとは証明されていません。一般に数列が収束するということを証明する方法としてε-δ法などというものがありますが、これはむしろ収束する数列が持つ性質を述べたもので、実際の証明は個々の数列が持つ個別の性質を利用した技巧的なものなのです。
　10,000ドル数列については、a[n]/n が 1/2 に収束する（H[1,1,1]=1/2）ことが証明されています。しかし、これはコンウェイが1988年6月15日にベル研究所（AT&T Bell Laboratories）で行った講話の中で述べられたもので、論文として残されたものではありません。私もネット上を鋭意捜索しましたが、この証明を載せた文書は見つかっていません。この議論を真に信頼に足るものにするためには、自分で証明するしかありません。
　証明は、まだできていません。しかし、それに繋がりそうな事実を発見することができましたので、ここで述べてみたいと思います。
　b[n]=2a[n]-n（=2B{1,1,1}[n]）とすると、b[n] は n=2^t（t は自然数）で最小値0をとります。そこで、2^t≦n＜2^(t+1) における b[n] の最大値を c[t] とすると、c[t]/(2^t)≧b[n]/n（2^t≦n＜2^(t+1)）になります。この c[t]/(2^t) が t→∞で0に収束することを証明すれば、a[n]/n が 1/2 に収束することが示されたことになります。
　c[t] は 1, 2, 3, 5, 8, 14, 24, 44, 79, 149, ... という値をとります。これをオンライン整数列大事典で検索すると、A072100という数列がヒットしました。ちなみに名称は「配列 m[i,1]=m[1,j]=1, m[i,j]=m[i-1,j-1]+m[i-1,j+1] の第2列」などという無味乾燥なものになっていて、あまり注目されていない数列のようです。2次元配列はちょっと扱いにくいのですが、それとは別に、「パスカルの三角形の中央の列とその左隣の列の数を上から順に加算して、さらに1を加算したものに等しい」という性質を持っています。
　これには10,000ドル数列の階差数列の性質が関わっています。a[n] の階差数列 a[n+1]-a[n] は1または0（b[n] の場合は1または-1）で構成されますが、その配列には一定のパターンがあります。2^t≦n＜2^(t+1) の範囲内では、まずt個の1が並んだ後で0が1個並び、1の個数が1個（最初の場合は2個）減って0が1個並び、1の個数が0個になるまで繰り返したのち、1の個数を直前の繰り返しから1個（最初の場合は2個）減らして同様に繰り返していくうちに、0が連続することが多くなり、最終的には最初と逆のパターンで0がt個並ぶのです。1よりも0（b[n] の場合は-1）が多く連続するようになる直前の b[n] が最大値をとります。このようなパターンでは1の個数は三角数とか四面体数とか五胞体数とかになりますので、パスカルの三角形が関係するのもなんとなく納得できます。
　最終的な証明に繋げるためにしなければならないことは、次の3つです。
(1) a[n] の階差数列のパターンを証明する
(2) c[t] がA072100に等しいことを証明する
(3) c[t]/(2^t) が t→∞で0に収束することを証明する
　(1)や(2)は、数学的帰納法を用いれば比較的簡単に証明できるでしょう。問題は(3)です。c[t] がA072100に等しいならば、c[t] は多数の階乗を足したり掛けたりしたものになりますが、階乗は足したり掛けたりしても多項式のように単純な形態にはなりませんので、証明の方針を立てるのが困難なのです。
　ということで、4月の記事からほとんど進展がないものでした。あらためて述べ立てるほどのものでもないと言われそうではありますが、どうせほとんど更新せずに長らく晒しておくものなら学術的なものにしたほうがいいだろうと思い、書いてみました。この記事が流れる前に更新する機会があるならば、ここで省略した証明など、もう少し詳しく書くかもしれません。
　それでは、今回はこういうことで。