2004年10月15日（金）

ホフスタッターのブラマンジェ

　当サイト『ジュエリーアイズ on the Web 040915-プレオープンサイト』が稼動して約1ヶ月、数字が一回りしました。縦に細長いページに付き合っていただき、ありがとうございます。古い記事は1ヶ月、正確には31日後に削除し、過去ログとして収録する予定です。
　前回の更新以降、ROSESに来店していませんので、ROSESやサイト関連で目新しいことは発生していません。では、お約束どおり、「ホフスタッターのブラマンジェ」について語っていきたいと思います。
（なお、これが恐らく、日本で初めてホフスタッター・コンウェイの10,000ドル数列についてウェブ上で考察した記事になるであろうということをお伝えしておきます）
　始めにお断りしておきますが、以下のお話はインターネットで得た断片的な資料をもとに月下香治が構成したものであり、事実と完全に一致するとは必ずしも保証できません。図書館で調べようとしたところ、正式な資料となる書籍は書庫に入っているということで、時間がなかったので借りる手続きができなかったのですが、ROSES随一の哲学家にしてコメディアンのブルーベルベットこと山下ヒロスウィーさんこと、ROSESではヘルシング大佐がその書籍をお持ちだと言うので、いずれ正確に調査しようと考えています。
　ホフスタッター（Douglas R. Hofstadter）は、論理学やカオス、人工知能に関する考察など、数学や社会の深遠に造詣の深いアメリカの数学者です。日本にもいくつかの著書が紹介され、現代思想に一定の影響を与えています。
　一方、「ブラマンジェ」とは、牛乳などを材料とするフランス料理の一品で、ふるふると揺れる白い姿が甘い憧憬を誘うデザートの一種です（私はまだ食したことがありません）。これらふたつにいったい何の関係があるのか、それについては後にお話しすることにしましょう。
（なお、『魔法乱舞ジュエリーアイズ』では、「ブラマンジェ」は「白色のエプロン」と定義されるアイテムの一種です）
　ホフスタッターについて語る前に、準備として「フィボナッチ数列」についてお話しましょう。フィボナッチ数列とは F[1]=F[2]=1, F[n]=F[n-1]+F[n-2] (n≧3) で定義される数列で（言葉で表すならば、それぞれの項が直前の2項の和になっているということです）、最も基本的な再帰数列です。具体的には、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... と続いていきます。フィボナッチ数列は多くの数学者によって研究され、多くの数学的性質が発見されるとともに、植物の形状など、自然界においてもフィボナッチ数列に従う現象が発見されています。
　ホフスタッターはフィボナッチ数列のような数列が他にも作れないかと考えました。しかし、F[1] や F[2] の数値を変更した程度の数列は既に研究されつくしています。ここでホフスタッターはひとつの発想の転換をしました。引数 n はもちろん自然数ですが、もし各項 F[n] が自然数ならば、項自体を引数として適用することによって新たな数列が作れるのではないかと。この考えに基いた数列が、著書『ゲーデル,エッシャー,バッハ―あるいは不思議の環』で発表されました。そのうちのひとつが、現在「ホフスタッターのQ数列（Hofstadter Q-sequence）」と呼ばれる数列です。
　ホフスタッターのQ数列とは、Q[1]=Q[2]=1, Q[n]=Q[n-Q[n-1]]+Q[n-Q[n-2]] (n≧3) で定義される数列です。言葉で表すならば、自然数からなる有限数列があるとき、最後のふたつの項をチェックし、それぞれの数値分、後ろから数えていったところに存在する項をふたつ足し合わせて得られた数値を、その数列の次の項として追加していくということです。具体的には、1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, ... と続いていきます。
　この数列は基本的には Q[n]≒n/2 のあたりを推移するのですが、7が出現しなかったり、8から10に飛んで9に戻ったりと、最初のほうだけを見ても不規則な振舞いを見せます。さらに n が大きくなると、上下に激しく振動したり、時折収束したりと、その振舞いもカオスの様相を見せてきます。本来カオスとは、掛け算を含む2次式以上の複雑な数式を何度も反復的に適用したときに出現するとされているのですが、1次式の範疇である足し算・引き算を適用しただけでカオス（のようなもの）が出現するというのは非常に示唆的です。Q数列の性質は完全には解明されておらず（特定の n に対する Q[n] を求めるには、Q[1] から順に計算していかなければならない）、解明すればフィールズ賞が獲れるとも囁かれています。
　ホフスタッターが著書を発表して後、多くの数学者がQ数列などに関する研究を始めました。中でも数学者コンウェイ（Conway）は、Q数列を若干改良して扱いやすくなった数列を研究し、その性質（a[n]/n が1/2に収束する）を証明しました。そしてコンウェイはその数列に関する問題を提出し、賞金10,000ドルの懸賞問題として発表したのです。
　欧米の数学界では、賞金付きの問題が出されるというのはさほど珍しいことではありません。それにしても、10,000ドルというのは、その問題のレベルからしても破格でした。さっそく意気盛んな数学者マローズ（Mallows）が問題を解き、コンウェイに賞金を要求しました。
「ああ、ごめんごめん。賞金が10,000ドルってのは間違いだったんだ。本当は1,000ドルだったんだって、さっき修正しておいたんだよ」
　確かに、マローズの回答より先に、賞金の金額が修正されていたというのは事実でした。このエピソードが知れ渡ると、この数列は皮肉をこめて「ホフスタッター・コンウェイの10,000ドル数列（Hofstadter-Conway 10,000-Dollar Sequence）」と呼ばれるようになりました。なお、マローズが実際に受け取った賞金がいくらだったかは審らかではありません。
　日本ではあまり見当たりませんが、海外には数学用語を網羅して解説する『MathWorld』というようなサイトも存在します。そういうサイトを見ていて、たまたま「10,000ドル」などという俗っぽい語句を含む数学用語を発見し、びっくりしたのですが、欧米人というのはなかなか面白い発想をするものです。
　さて、ここからが本題、「ホフスタッター・コンウェイの10,000ドル数列」に関する性質です。
　ホフスタッター・コンウェイの10,000ドル数列とは、a[1]=a[2]=1, a[n]=a[a[n-1]]+a[n-a[n-1]] (n≧3) で定義される数列です。言葉で表すならば、自然数からなる有限数列があるとき、最後の項をチェックし、その数値分、前から数えていったところに存在する項と後ろから数えていったところに存在する項とを足し合わせて得られた数値を、その数列の次の項として追加していくということです。具体的には、1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, ... と続いていきます。
　この数列にはいろいろと面白い性質があります。前述の a[n]/n が1/2に収束するという性質のほか、すべての項がその直前の項に等しい、もしくは直前の項より1大きいとか、a[2^m] がその引数の半分 2^(m-1) に等しく、それ以外の a[n] は n/2 より大きいなどというものもあります。この最後の性質を確認するために 2*a[n]-n という数列を作り、そのグラフを書いてみると、とても美しい図形が出現します。
　ここで、日本人数学者高木貞治が考案した関数、「高木関数」をご紹介しておきましょう。高木関数のグラフは左右対称の山形の曲線で、連続でありながらいたるところ微分不可能で、一部分が全体の縮小形に等しいというフラクタルな性質を持っています。高木関数はその形状から、欧米では俗に「ブラマンジェ関数」と呼ばれています。
　数列 2*a[n]-n のグラフは、このブラマンジェ関数のグラフが倍々に大きくなりながら無限に続いていくという形状を持っています。これが、私が勝手に「ホフスタッターのブラマンジェ」と呼んでいる物です。数学の事情通ならば、なかなかの感動を味わえることでしょう。
　ここで私も、10,000ドル数列の性質をひとつ証明してみようと思います。そもそも10,000ドル数列は a[n]=a[a[n-1]]+a[n-a[n-1]] で定義するなどといいますが、例えば a[n-1] が n より大きくなったとすると、（a[1] から a[n-1] までしか定義されていないのに）a[n] を定義するのに a[n+1] 以上の項が必要となるという矛盾が生じ、それ以上は定義できなくなってしまいます。ここでは先に述べた、すべての項がその直前の項に等しい、もしくは直前の項より1大きい（つまり、どの項も存在する）という性質を証明します。これによって、10,000ドル数列には全ての自然数が少なくともひとつずつは存在し、Q数列のように飛んだり戻ったりはしないということも併せて示すことができます。
　―――――――――――――――
問）a[1]=a[2]=1, a[n]=a[a[n-1]]+a[n-a[n-1]] (n≧3) とする。
　全ての n(≧2) について、a[n]=a[n-1]、もしくは a[n]=a[n-1]+1 のいずれかであることを証明せよ。
証）a[1] から a[k-1] まで、全項が自然数で、初項を除く全ての項が前項、もしくは前項に1を加えた数に等しく、上関係式によって導かれた a[k] も a[k-1]、もしくは a[k-1]+1 に等しいと仮定する。
　なお、a[1]=a[2]=1、および、a[3]=a[a[2]]+a[3-a[2]]=a[1]+a[3-1]=a[1]+a[2]=2 もこの仮定を満たす。
　このとき、a[k]=a[a[k-1]]+a[k-a[k-1]] であり、a[a[k-1]]・a[k-a[k-1]] ともに a[1] から a[k-1] までのいずれかであることから、1≦a[k-1]≦k-1, 1≦k-a[k-1]≦k-1。
　また、上関係式に従い、a[k+1]=a[a[k]]+a[k+1-a[k]] とする。
　a[k]=a[k-1] の場合、
　a[k+1]=a[a[k]]+a[k+1-a[k]]
　=a[a[k-1]]+a[k-a[k-1]+1]
　=a[a[k-1]]+a[k-a[k-1]]+a[k-a[k-1]+1]-a[k-a[k-1]]
　=a[k]+(a[k-a[k-1]+1]-a[k-a[k-1]])。
　ここで、1≦k-a[k-1]≦k-1 であることから 2≦k-a[k-1]+1≦kであり、a[k-a[k-1]+1] は既に定義されている a[2] から a[k] までのいずれかとして存在する。
　また、a[k-a[k-1]+1] は a[k-a[k-1]] の後項であるので、仮定により、a[k-a[k-1]+1]-a[k-a[k-1]] は0または1である。
　よって、a[k+1] は a[k] もしくは a[k]+1 に等しい。
　a[k]=a[k-1]+1 の場合、
　a[k+1]=a[a[k]]+a[k+1-a[k]]
　=a[a[k-1]+1]+a[k-a[k-1]]
　=a[a[k-1]+1]-a[a[k-1]]+a[a[k-1]]+a[k-a[k-1]]
　=(a[a[k-1]+1]-a[a[k-1]])+a[k]。
　ここで、1≦a[k-1]≦k-1 であることから 2≦a[k-1]+1≦kであり、a[a[k-1]+1] は既に定義されている a[2] から a[k] までのいずれかとして存在する。
　また、a[a[k-1]+1] は a[a[k-1]] の後項であるので、仮定により、a[a[k-1]+1]-a[a[k-1]] は0または1である。
　よって、a[k+1] は a[k] もしくは a[k]+1 に等しい。
　a[k]=a[k-1], a[k]=a[k-1]+1 のいずれの場合においても a[k+1] が a[k] もしくは a[k]+1 に等しいので、a[k+1] は恒常的に a[k] もしくは a[k]+1 に等しい。
　よって、数学的帰納法により、全ての n(≧2) について、a[n]=a[n-1]、もしくは a[n]=a[n-1]+1 のいずれかである。（終）
　―――――――――――――――
（今年3月、ROSESの仲間と一緒に旅行したときに、布団の中で考えていました）
　ここで10,000ドル数列が無限数列として存在するということが確かに保証されましたが、証明を見ると、これは特に10,000ドル数列に限ったことではありません。a[1]=a[2]=a[3]=1 とすると、この数列は 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8, 8, 9, ... となります。この数列はフィボナッチ数列と関連が深く、フィボナッチ数列に存在する数を引数とする a[F[n]] は F[n-2] に等しいという性質を持っています。
　フィボナッチ数列から出発し、フィボナッチ数列に帰ってきました。数学はこのように、世界の裏側に張り巡らされた隠れた論理のネットを自覚することによって、宇宙の真相に迫ろうとするものだとも言われています。小難しいなどと言って毛嫌いせずに、少しだけでも論理を働かせてみれば、何か面白いことに出会えるかもしれません。
　本格始動後の学術サイトでもこのようなことを考察していきますが、このサイトでも時々はこういうことをしてみたいと思います。言語学・数学・科学に関して疑問をお持ちの方は、メール、もしくはROSESで直接お伝えください。可能な限りお答えいたしましょう。