Positive Lower Density for Hofstadter's $ab-1$ Problem

無限の数作りゲーム

数字が玩具となっている、広大で果てしない遊び場を想像してみてください。数学の世界、特に数論と呼ばれる分野では、研究者たちは古いものから新しいものを生成するルールを使って、新しい数字を作り出すゲームを好んで行います。これは「再帰」あるいは「更新」と呼ばれる、ある種の有名なゲームの一種です。音楽に合わせて椅子取りゲームをするようなものだと考えてください。ただし、プレイヤーは人間ではなく数字であり、椅子は代わりに数直線上の特定の場所です。数学者たちが数十年にわたって問い続けてきた大きな疑問は、もしこのゲームを永遠に続けたとしたら、生成された数字は遊び場全体に均等に広がっていくのか、それとも一角に固まってしまい、巨大な空白地帯を残してしまうのか、ということです。

この特定の論文は、単純なルールから始まったパズルに取り組んでいます。まず「2」と「3」という数字から始めます。次に、すでに持っている異なる2つの数字を取り出し、それらを掛け合わせ、そこから1を引きます。もしその結果が整数であれば、それを自分のコレクションに加えます。これを永遠に繰り返します。伝説的な数学者ポール・エルデシュ（彼は有名な「ホフスタッターの図形・図形」数列の著者からこの話を聞きました）が提示した問いは、この数字の集合が十分に「厚い」かどうかです。つまり、「正の下密度（positive lower density）」を持つでしょうか？ 平易な言葉で言えば、このルールによって生成される数の集合は、たとえどれほど遠くまで進んだとしても、最終的に数直線のかなりの割合（ゼロではない割合）を占めることになるのでしょうか？ 長い間、その答えがイエスなのかノーなのかは誰にも分かりませんでした。

解決策：数字のための交通システム

この論文において、サミュエル・コーレスキーは、答えはイエスであることを証明しています。このルールによって生成される数の集合は、確かに正の下密度を持っています。これは、より大きな範囲の数字を見ていくとき、常にこの特別な集合に属する数字の、確実かつゼロではない塊が見つかることを意味します。それは単に散らばった数個の数字ではなく、豊富に存在するのです。

著者がどのようにしてこれを解いたかを理解するために、この数の集合を一つの「都市」とし、ルールである「掛け算して1を引く」を「一方通行の道路」だと想像してみてください。著者の目的は、この都市を通り抜けるための方法が非常に多く、結果として多くの目的地を避けて通ることはできないことを示すことでした。しかし、一つ落とし穴があります。ルールは、数字を「異なる」もの同士で掛け合わせなければならないと言っています。もしある数字を自分自身と同じ数字で掛けようとすると、ルールが壊れてしまいます。これは、もし同じ行程の中で既に通ったことがある道路セグメントであれば、その道を通ってはならないという交通法規のようなものです。

著者の戦略は、20個の特定のゾーン（区間）に分割されたマップを使用して、「交通管制システム」を構築することです。彼は、これらのゾーンに異なる「乗数」（例えば2、3、5、9、14）を割り当てます。ある数字がゾーンに到達すると、システムはその数字に対して次にどの乗数を使うべきかを指示します。この証明の天才的な点は、これらの乗数の選び方にあります。著者は、4つの異なる「交通パターン（割り当て）」を設定しました。現在のシステムの状況に基づいてこれらのパターンを切り替えることで、数字が停滞したり、「相異なるもの」というルールの違反に陥ったりしないようにしているのです。

これは、リーダーが完璧なバランスを保とうとしている「フォロー・ザ・リーダー」のゲームのようなものです。著者は、数字の「成分」（具体的には素数2、3、5、7の累乗）を追跡します。彼は、レシピが一定の形で維持されるようにしたいと考えています。そこでフィードバックループを用います。もしレシピが「2」に偏りすぎたら、システムは「3」や「5」を増やしてバランスを取るパターンへと切り替わります。これにより、成長の「傾斜（数値が大きくなる速度）」を特定の目標にロックし続けることができます。

この論文は、これらの切り替えを注意深く管理することで、システムが同じ「傾斜」へと行き着く膨大な数のユニークな経路を作り出すことを示しています。経路はユニークであり、かつシステムが何度も出発点に戻るように設計されている（「正の再帰性」と呼ばれる概念）ため、数学的に、これらには無限に多くの異なる数字が生成されることが証明されます。

決定的なのは、基礎となる数学がいくらかの重複を許容している（システムは厳密な意味での「自由」な状態ではない）にもかかわらず、著者がこれらの経路が互いに独立していることを証明している点です。彼は、20ゾーンのマップ上で経路を逆方向に辿ることで、それらが終点に到達するまで決して交差しないことを示します。これにより、すべての経路がユニークな最終数値を生成することが保証されます。

最後の決め手は、計数に関する議論です。著者は、このプロセスの各「ステップ」において、有効な経路の数が数字自体の成長率と一致する速度で増加することを計算します。彼は、特定の大きな数 $x$ に対して、$1$から$x$までの範囲にある彼の特別な集合の量は、少なくとも$c \times x$（ここで$c$ はゼロより大きい定数）であることを証明します。言い換えれば、どれほどカウントを進めても、常にこれらの数字の安定した流れが見つかるということです。

この論文は、それが単に「ありそうだ」と示唆しているだけではありません。確率（システムが開始点に戻り続けることを示すため）、幾何学（区間をマッピングするため）、そして数論（素因数を数えるため）を組み合わせた、厳密でステップ・バイ・ステップの数学的証明を提供しています。その結果、数十年来の問いに対する決定的な答えが出されました。この集合は疎（まばら）ではなく、密であり、信頼できる、正の存在感を持って数直線を埋め尽くしているのです。