On a perturbed Hofstadter $Q$-recursion

ホフスタッターの Q 再帰式にパリティ擾乱を加えた変形 $\widetilde{Q}$ がすべての $n$ で定義され、その漸近挙動がカタラン数に支配された自己相似構造を通じて記述可能であることを証明し、さらに元の Q 数列との関係性について数値実験に基づいた仮説を提示した。

要約

この論文は、数学の「混沌（カオス）」と「秩序」の境界線にある、非常に面白い数列の研究です。専門用語を排し、物語や日常の例えを使って解説します。

1. 物語の舞台：「迷子になった数列」Q

まず、主人公である**「ホフスタッターの Q 数列」**という存在を知りましょう。
これは、自分自身の過去の値を参照して次の値を決めるという、非常に複雑なルールを持っています。

• ルール： 「昨日の自分の位置」を見て、その位置の「さらに過去の値」を足し合わせる。

このルールは、まるで**「自分の足跡をたどりながら、さらにその足跡の先にある足跡を探す」**ようなものです。
数十年にわたって数学者たちがこの数列を研究してきましたが、ある重大な謎が解けていませんでした。

• 謎： この数列は、永遠に計算し続けられるのか？それとも、ある時点で「過去の値が見つからない」というエラー（迷子）を起こして止まってしまうのか？
• 現状： 計算機で見ると、値はカオス的に跳ね回り、予測不能です。まるで暴走する子供のように、どこへ行くかわかりません。

2. 登場人物：「整列した双子」$\tilde{Q}$

そこで、この論文の著者（Benoît Cloitre）と、この数列を提案した Mantovanelli さんが、**「少しだけルールを変えてみた」実験を行いました。
元のルールに、「+1 と -1 を交互に足す」**という小さな「おまけ（摂動）」を加えたのです。

• 新しいルール： 「元の複雑な計算」＋「+1 または -1」。

この小さな変化が、驚くべき魔法をもたらしました。

• 結果： 暴走していた数列が、急に**「整然としたリズム」**を取り戻しました。
• 特徴： 値が「1/2」を中心に、非常に規則正しく、かつ**「自己相似（フラクタル）」**という美しいパターンを描くようになったのです。
  • 例え話： 元の Q 数列が、ジャングルで迷い、枝を切り倒しながら進む探検家だとすれば、新しい $\tilde{Q}$ 数列は、整然と並んだ階段を、一定のリズムで昇り降りする体操選手のようなものです。

3. 論文の核心：2 つの発見

この論文は、この新しい数列 $\tilde{Q}$ について、2 つの重要なことを証明しました。

① 永遠に続くこと（定義の存在）

まず、この新しい数列は、**「どこまでも計算し続けられる」ことが証明されました。
元の Q 数列が「いつか迷子になるかもしれない」という不安を抱えているのに対し、新しい方は「絶対に迷子にならない」**ことがわかりました。これは、数学的な「安心感」の大きな一歩です。

② 1/2 への収束と「揺らぎ」の大きさ

この数列の値は、だんだんと「自分の番号（n）の半分（n/2）」に近づいていくことがわかりました。

• 例え話： 100 番目の値は 50 に、1000 番目は 500 に、100 万番目は 50 万に近づいていきます。
• 揺らぎ（ノイズ）： ただし、完全にピッタリ合うわけではありません。少し前後します。この論文は、**「その前後する幅（揺らぎ）が、どれくらい小さいか」**を正確に計算しました。
  • 結論：**「揺らぎの大きさは、$\frac{1}{\sqrt{\log n}}$ という非常にゆっくり減っていく量」**です。
  • イメージ： 大きな波（カオス）が、時間とともに小さくなり、静かな水面（1/2）に落ち着いていく様子です。

4. 秘密の鍵：「カタラン数」と「アーチ」

なぜ、こんなにも美しい秩序が生まれるのでしょうか？
論文は、数列の中に**「アーチ（橋）」**のような構造が隠れていることを発見しました。

• アーチ構造： 数列の値が上昇して頂点に達し、また下降する山のような形が、次々と現れます。
• カタラン数： この「山（アーチ）」の形や、その出現頻度を支配しているのは、数学に有名な**「カタラン数」**という数列です。
  • 例え話： 複雑な迷路のように見える数列ですが、実は**「レゴブロック」**のように、小さなブロック（アーチ）が、ある決まったルール（カタラン数）で積み重ねられているだけだったのです。
  • この「積み重ねのルール」が、数列の暴走を防ぎ、美しい自己相似パターンを生み出していました。

5. 元の「暴走した Q 数列」への示唆

この研究の最大の意義は、「元の暴走した Q 数列」へのヒントを与えたことです。

• 仮説： 元の Q 数列と、整然とした新しい $\tilde{Q}$ 数列の「差」は、実は非常に小さい（新しい数列の揺らぎと同じくらい）かもしれません。
• 意味： もしこれが本当なら、**「元の Q 数列も、実は迷子にならず、1/2 に収束している」**可能性が極めて高くなります。
  • 例え話： 暴走する子供（Q）の横に、整然とした双子（$\tilde{Q}$）がいて、その距離があまり離れていないなら、暴走する子供も実は「目的地（1/2）」に向かって歩いているのかもしれません。

まとめ

この論文は、**「少しだけルールを変えるだけで、カオスが秩序に変わる」**という魔法のような現象を解明しました。

1. 新しい数列 $\tilde{Q}$ は、永遠に計算でき、1/2 に収束する。
2. その美しさの正体は、「カタラン数」という数学的なレゴブロックの積み重ねだった。
3. この発見は、長年謎だった「元の暴走する数列 Q」が、実は秩序だった世界にあるかもしれないという希望を与えた。

数学の世界では、複雑なカオスの中に隠された「隠れた秩序」を見つけることが、最もロマンチックな冒険の一つです。この論文は、その冒険の素晴らしい一歩となりました。

技術概要

本論文「On a perturbed Hofstadter Q-recursion（摂動されたホフスタッター Q-再帰について）」は、Benoît Cloitre によって 2026 年 4 月に発表された数学論文です。この論文は、長年未解決であったホフスタッターの Q 数列（Hofstadter Q-sequence）の摂動版である $\tilde{Q}$ 数列の厳密な解析を行い、その定義可能性と漸近挙動を証明しています。

以下に、論文の技術的な要約を問題設定、手法、主要な貢献、結果、意義の観点から詳述します。

1. 問題設定 (Problem)

• ホフスタッター Q 数列の未解決性:
  従来のホフスタッター Q 数列 $Q(n)$ は、$Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$ で定義されるネスト型再帰（nested recurrence）の代表的な例です。しかし、数十年の研究にもかかわらず、$Q(n)$ がすべての $n$ で定義されるかどうか、あるいは $Q(n)/n$ が収束するかどうかさえ未証明のままです。その振る舞いはカオス的であり、$Q(n)/n$ は $1/2$ の周りで不規則に振動します。
• 摂動版 $\tilde{Q}$ の導入:
  Mantovanelli (2026) は、再帰式に $(-1)^n$ を加えた摂動版 $\tilde{Q}$ を導入しました。
  $$\tilde{Q}(n) = \tilde{Q}(n-\tilde{Q}(n-1)) + \tilde{Q}(n-\tilde{Q}(n-2)) + (-1)^n$$
  この摂動は、元の数列のカオス的な振る舞いを「正確な二進的自己相似性（exact dyadic self-similarity）」に変える驚くべき効果を持ちます。Mantovanelli は数値的に $\tilde{Q}(n)/n \to 1/2$ が成り立つと推測していましたが、その証明はなされていませんでした。

2. 手法とアプローチ (Methodology)

論文は、$\tilde{Q}$ 数列の構造を「アーチ（arch）」と呼ばれる区間に分解し、その内部の自己相似性を「インターリーブ変換器（interleave transducer）」という決定論的機械を用いて解析する手法を採用しています。

• パリティ分割と部分列:
  $\tilde{Q}(n)$ の値は常に奇数であるため、$R(n) = (\tilde{Q}(n)+1)/2$ と置き、奇数項と偶数項をそれぞれ $A(m)$ と $B(m)$ という 2 つの部分列に分割します。これにより、元の再帰式は $A$ と $B$ の結合された再帰式に変換されます。
• アーチ分解と $\delta$ 関数:
  $A(m)$ と $B(m)$ の差 $\delta(m) = B(m) - A(m)$ を定義します。$\delta(m)$ の符号変化（ゼロ点）が自然な「アーチ（正のアーチと負のアーチ）」を形成します。このアーチ構造が数列の骨格を形成します。
• インターリーブ変換器とステップワード:
  再帰式は、2 つのテープ（過去の値）を交互に読み取る決定論的機械として再定式化されます。各アーチレベル $r$ において、差分 $\Delta A$ と $\Delta B$ を記録する「ステップワード（step words）」$P_r$ と $N_r$ が生成されます。
  • Law 1 と Law 2: 正のアーチから負のアーチへ、負のアーチから次の正のアーチへステップワードが生成される規則（Law 1, Law 2）が確立され、これらは「インターリーブ演算子（Interleave operator）」によって記述されます。
• 自己相似性と対称性:
  ステップワードは「反パリンダローム（anti-palindromic）」であり、バランスが取れています。この構造により、各レベルで新しいステップワードの高さが、前のレベルからの負の寄与を上回る正の寄与を持つことが証明され、数列が崩壊しないことが示されます。
• 2 つの経路（Route A と Route B）:
  • Route B (頻度解析): 二進ブロックにおける $A$ と $B$ の訪問頻度を解析し、無条件に収束率を導出します。
  • Route A (振幅解析): アーチの振幅（$\delta$ の最大値）を直接解析し、条件付きで正確な漸近定数を導出します。

3. 主要な貢献と結果 (Key Contributions and Results)

論文の主要な成果は以下の定理としてまとめられます。

定理 1.1 (Main Result)

1. 無条件の定義可能性と収束:

   • $\tilde{Q}(n)$ はすべての $n \ge 1$ で定義されます（$1 \le \tilde{Q}(n) \le n$）。
   • 収束速度は $O(1/\sqrt{\log n})$ です。
     $$\left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| = O\left( \frac{1}{\sqrt{\log n}} \right)$$
   • この結果は、アーチの骨格、1-Lipschitz 性、および頻度法則の確立に基づいて無条件に証明されています。

2. 条件付きの正確な漸近定数:

   • 2 つの観察事実（Observation 9.4: 記録主張、Observation 9.10: 走査識別）が成り立つと仮定すると、振幅の増分 $W_r$ はカタラン数に関連する二項係数 $\binom{2r+1}{r}$ で与えられ、以下の正確な上限定数が導かれます。
     $$\limsup_{n\to\infty} \left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| \sqrt{\log_2 n} = \frac{1}{3\sqrt{2\pi}}$$
   • この定数は、振幅の増分が $\binom{2r+1}{r} \sim \frac{4^r}{\sqrt{\pi r}}$ として振る舞うこと（カタラン核の出現）に基づいています。

その他の重要な発見:

• カタラン核の普遍性: 解析の核心には、方程式 $1 - z + xz^2 = 0$（カタラン生成関数の定義式）が現れます。これは頻度側（中央二項係数）と振幅側（カタラン木構造）の両方で支配的な役割を果たしています。
• Conway-Mallows 数列との対比: 従来の Conway-Mallows 数列は単一の二進木と中央二項係数で制御されますが、Mantovanelli 数列はカタラン型の係数を持つ「カタランの森」によって制御されます。
• 元の Q 数列への示唆: 数値実験により、$Q(n) - \tilde{Q}(n) = O(n/\sqrt{\log n})$ という予想が示唆されており、$\tilde{Q}$ が元のカオス的な $Q$ の扱いやすい代理（proxy）として機能する可能性が示されました。

4. 意義 (Significance)

• ネスト型再帰の最初の厳密な解析:
  数十年未解決だったホフスタッター型再帰の摂動版について、定義可能性と漸近挙動を厳密に証明した最初の成果です。カオス的な再帰に摂動を加えることで、厳密な自己相似性と解析可能な構造が現れることを示しました。
• 組合せ論的構造の解明:
  ネスト型再帰が、単なる数値的カオスではなく、深い組合せ論的構造（カタラン数、反パリンダローム、インターリーブ演算）によって支配されていることを明らかにしました。
• 解析的組合せ論との接点:
  収束速度 $O(1/\sqrt{\log n})$ や振幅の挙動が、解析的組合せ論における臨界点（$x=1/4$）と密接に関連していることを示し、再帰数列の理論と解析的組合せ論の橋渡しを行いました。
• 将来の研究への道筋:
  元の Q 数列の解析への道を開く「代理モデル」としての $\tilde{Q}$ の有用性を提案し、摂動の強さや他のネスト型再帰への拡張可能性についての新たな研究課題を提示しました。

総じて、この論文は、複雑な再帰数列の背後に隠された秩序を、自己相似性と組合せ論的構造の観点から解き明かす画期的な研究です。