論文「Almost Golomb Sequences」の技術的概要

Benoît Cloitre によるこの論文は、整数列の自己言及的性質、特に Golomb 数列の一般化と、その有限メモリ版である「Almost Golomb 数列（ほぼ Golomb 数列）」の構造を深く分析したものです。Golomb 数列の滑らかなべき則成長が、窓のサイズを固定したスライドウィンドウによる再帰定義によって、どのように振動する線形成長と自動的な構造へと変容するかを明らかにしています。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定と背景

1.1 Golomb 数列

Golomb 数列 $G(n)$ は、正整数 $n$ がちょうど $G(n)$ 回現れるような、単調非減少の正整数列として定義されます（OEIS A001462）。
その定義は以下の自己言及的な式で表されます：
$$G\left( \sum_{k=1}^n G(k) \right) = n$$
この数列は、黄金比 $\phi = (1+\sqrt{5})/2$ によって支配される滑らかなべき則 $G(n) \sim \phi^{2-\phi} n^{\phi-1}$ で成長します。また、任意の $k \ge 2$ に対して $k$-正則（$k$-regular）ではありません。

1.2 Almost Golomb 数列の導入

著者は、上記の定義における「全累積和」を、直近の $r$ 項からなる「スライドウィンドウ（固定サイズ $r$ の累積和）」に置き換えた数列を**Almost Golomb 数列（$r$ 次）**として定義しました。
定義 1.1（$r \ge 2$）:
$$a\left( \sum_{j=0}^{r-1} a(n-j) \right) = n$$
ここで、$a(n)$ は条件を満たす最小の正整数（貪欲法則）として選択されます。
この「無限メモリ」から「有限メモリ」への切り替えが、数列の性質を根本的に変えることが本研究の核心です。

2. 手法とアプローチ

本研究では、以下の数学的・計算機的アプローチを組み合わせました。

• 構造的解析と数学的帰納法: 数列の「ラン（連続する同一値の区間）」の構造を厳密に解析し、開始位置 $S_n$ と値 $a(n)$ の関係を導出しました。
• Allouche-Shallit 基準の適用: 数列が $r$-正則（$r$-regular）であることを証明するために、数列の差分列が有限状態オートマトン（DFAO）によって生成される $r$-自動的（$r$-automatic）であることを示しました。
• 明示的な「脱ネスト（Denesting）」公式の導出: 再帰式 $a(rn+i)$を、$a(n)$ やそのシフト、および補正列を用いた明示的な式に変換しました。
  • $r=2, 3$ の場合は直接証明。
  • $r=4, 5$ の場合は、明示的な再帰パターンの同定と、定理証明器 Walnut による自動検証をハイブリッドに行いました。
• 数値実験と対称性の分析: 異なる $r$ 値に対する数列の挙動を計算し、極限値の振る舞いや、Golomb 数列との隠れた関係性を数値的に検証しました。

3. 主要な貢献と結果

3.1 普遍的正則性（Universal r-regularity）

定理 2.9: 任意の $r \ge 2$ に対して、Almost Golomb 数列 $a(n)$ は $r$-正則です。

• 意義: Golomb 数列が $k$-正則でないのに対し、その有限メモリ版はすべて $r$-正則となります。これは、数列が $r$ 進数の桁に基づいた線形再帰を満たすことを意味します。

3.2 明示的な脱ネスト公式（Explicit Denesting Formulas）

各 $r$ に対して、$a(rn+i)$を$a(n)$の線形結合と補正列（$r$-自動的）の和として表す公式が導出されました。

• $r=2$ の場合:
  • $a(2n) = a(n) + a(n+1) - 1$
  • $a(2n+1) = a(n) + a(n+1)$
  • さらに、Mallows 型の入れ子再帰式 $a(n+1) = 1 + a(n+1 - a(a(n)+1) + a(a(n)-1))$ も得られました。
• $r=3$ の場合: 補正列 $\varepsilon(n)$（3-自動的）を用いた公式が得られ、数列の構造がパロンドミカルな置換規則と関連していることが示されました。
• $r=4, 5$ の場合: 複数の補正列（$\varepsilon_i$ など）を用いた公式が導かれ、Walnut による完全な検証が行われました。

3.3 収束性の欠如（Non-convergence of a(n)/n）

定理 7.1, 7.5, 7.6, 7.8: 任意の $r \ge 2$ に対して、比 $a(n)/n$ は収束しません。

• Golomb 数列では $a(n)/n^{\phi-1}$ が定数に収束しますが、Almost Golomb 数列では $a(n)/n$ が2 つの異なる有理数極限値の間で振動します。
  • $r=2$: 極限値 $3/4$ と $2/3$
  • $r=3$: 極限値 $8/15$ と $5/8$
  • $r=4, 5$ でも同様に異なる極限値が存在します。
• この振動は、数列のラン長（値の出現回数）が周期的または準周期的に変化することに起因します。

3.4 組合せ的解釈

• $r=2$: 値の重複回数 $N_2(n)$ が、$n-1$ の 2 進表現の「2 番目の最上位ビット」によって決定されることが示されました。また、差分列 $d(n)$ が単純なブールセルオートマトン（偶数位置は 1、奇数位置は親の論理積）によって生成されることが証明されました。
• $r=3$: 差分列のブロックが回文的（palindromic）構造を持ち、遅延フィードバック機構によって振動が生じていることが示されました。

3.5 Golomb メタ構造の仮説（Golomb Meta-structure Conjecture）

最も驚くべき発見の一つは、Almost Golomb 数列の族における「最大重複度」$M(r) = \sup_n N_r(n)$ が、元の Golomb 数列 $G(n)$ によって支配されているという数値的証拠です。

• 仮説 9.1: $M(r) \ge k$ となる最小の $r$ を $j_k$ とすると、$k \ge 4$ において $j_{k+1} - j_k = G(k)$ が成り立ちます。
• これは、有限メモリで切り捨てられた数列の族が、その生成源である Golomb 数列の法則を「メタ構造」として内包していることを示唆しています。この仮説は「Prefix Conjecture」と「Domination Lemma」の 2 つの境界条件に帰着されます。

4. 結論と意義

この論文は、自己言及的数列の分野において以下の重要な知見を提供しました。

1. メモリ制限の質的変化: 無限メモリ（Golomb 数列）から有限メモリ（Almost Golomb 数列）への移行が、数列の性質を「解析的なべき則・非正則」から「代数的な線形成長・正則・振動」へと劇的に変化させることを示しました。
2. 自動的構造の普遍性: 任意の $r$ に対して数列が $r$-正則であることを証明し、その構造を明示的な再帰式と補正列によって記述可能にしました。
3. 非収束性の明確化: $a(n)/n$ が収束しないこと、そしてその振動が $r$ 進数の構造と密接に関連していることを示しました。
4. Golomb 数列との深層的な関係: 一見すると単純な変形に見える Almost Golomb 数列の族が、実は元の Golomb 数列の成長律を「最大重複度」という形で再帰的に再現しているという、驚くべきメタ構造を提唱しました。

本研究は、整数列の理論において、自動的数列（Automatic sequences）と自己言及的数列（Self-referential sequences）の交差点を深く掘り下げたものであり、今後の組合せ論や数論的研究への道を開くものです。特に、Walnut 定理証明器を用いた形式的検証と、数学的証明の融合は、複雑な再帰数列の解析における新しい標準を示唆しています。