Brik's sequence: a strange recursion

技術的サマリー：Brik 列：奇妙な再帰

問題定義
本論文は、Garo Brik によって 2018 年に提案された特定の再帰的反復によって生成される、二値語の列 $(B_i)_{i \ge 1}$ と、それによって生じる無限二値列 $b$ の性質を調査する。この列は、基本ケース $B_1 = 101$ と、$i \ge 1$ に対する漸化式 $B_{i+1} = B_i C_i$ によって定義される。ここで $C_i$ は、$B_i$ の最初の $i$ 個の記号を除去して得られる $B_i$ の接尾辞である。すべての $i \ge 2$ に対して $B_{i-1}$ が $B_i$ の接頭辞であるため、これらの語は一意の無限列 $b$ に収束する。本論文は、$b$ の再帰性、因子複雑性、準同型性、および記号「1」の密度を含む、$b$ の組合せ論的および算術的性質を特徴づけることを目指す。

手法
分析には、帰納的証明、語の因子に関する組合せ論的議論、および解析的数論的手法の組み合わせが用いられる。

• 構造分析: 著者らは、自明な帰納法を通じて語 $B_i$ の長さとその接尾辞の性質を確立する。「境界（border）」（接頭辞でありかつ接尾辞であるもの）の概念を用いて、特定のインデックスが「良い」こと、すなわち $B_i$ が $B_{\ell_i}$ の境界であることを証明する。
• 再帰性と複雑性: 本論文は、再帰的性質を決定するために $b$ 内での因子の出現を分析する。禁止された部分文字列を同定することにより、すべての有効な因子の集合を特徴づける。
• 成長分析: 特定のパターン（特に 1 の連続）の開始位置は、漸化式を用いて追跡され、成長率はクヌースのテトレーション表記を用いて分析される。
• 密度計算: 1 の密度は、長さ $\ell_n = |B_n|$ の接頭辞における 1 の数を分析することで導き出される。著者らは、列自体の二進展開を含む極限式を導き出し、誤差項分析 ($E(N)$) を用いて、特定の接頭辞からの極限を任意の接頭辞へ拡張する。
• 超越性証明: 密度極限 $\alpha$ の性質を決定するために、本論文は Adamczewski と Bugeaud による「吃音（stammering）」判定基準の簡略化版を適用する。これは、列の反復構造と、その二進展開によって形成される数の超越性との関係を扱う。

主要な貢献と結果

1. 再帰的性質:

   • 無限語 $b$ は再帰的（すべての有限因子が無限回出現する）であるが、一様再帰的ではないことが証明される。
   • 本論文は、$b$ が任意に長い 1 の連続 ($1^n$ for all $n$) を含むことを示しており、これが一様再帰性を排除する。$1^n$ の最初の出現の開始位置 $r_n$ は、$n \ge 2$ に対して漸化式 $r_{n+1} = 2^{r_{n-2}} + r_n$ に従い、極めて急速な成長（テトレーション）をもたらす。

2. 因子複雑性:

   • $b$ の因子の完全な特徴付けが提供される：二値語は、連続する 0 を 2 つ含まない場合かつその場合に限り、$b$ の因子となる。
   • したがって、長さ $n$ の異なる因子の数は、正確に $F_{n+2}$（第 $n+2$ フィボナッチ数）である。これにより、$b$ が指数関数的な因子複雑性を持つことが確立される。

3. 非準同型性:

   • 指数関数的な因子複雑性に基づき、本論文は $b$ が準同型ではないと結論づける。これは、Ehrenfeucht、Lee、および Rozenberg の結果、すなわち準同型列は多項式因子複雑性（具体的には $O(n^2)$）を持たなければならないという結果に由来する。

4. 1 の密度:

   • 本論文は、$b$ における 1 の漸近密度 $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$ が存在することを証明する。
   • その値は、$\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$ という式で与えられる。ここで $b_i$ は列の $i$ 番目のビットである。
   • 数値は約 $0.64505878493452$ である。

5. 超越性:

   • 密度 $\alpha$ は超越数であることが証明される。証明は、関連する数 $\beta = \sum b_i 2^{-i}$ が吃音判定基準を用いて超越数であることを示すことに依存する。$\beta$ は有理数であり得ない（そうであれば有界な因子複雑性を意味するため）上、列は必要な「吃音」構造（$B_{n+1}$ が $B_n$ を含み、それに接尾辞の反復が続く）を示すため、$\beta$（したがって $\alpha$）は超越数でなければならない。

意義と主張
本論文は、単純な反復規則によって定義されているにもかかわらず、直ちに明らかではない微妙で複雑な性質を示す列を提示する。主な意義は、一様再帰的ではないが再帰的であり、指数関数的な因子複雑性を持ち、超越的な 1 の密度を生成する列の発見にある。著者らは、この列が OEIS（初期項を欠く A334820 として）に掲載されていることに言及し、再帰的定義と生じる算術的性質との相互作用を強調している。

本論文は、これらの結果が 2026 年 5 月に APL を用いた実験と ChatGPT 5.5 との協力によって得られ、すべての主張はその後著者によって書き換えられ検証されたことを明示的に認めている。この研究は、再帰的に定義された二値語の性質と、組合せ論的列への超越性判定基準の適用に関する事例研究として機能する。