2025-11-10T03:12:56.960652

Cloitre's Self-Generating Sequence

Shallit
In 2009 Benoit Cloitre introduced a certain self-generating sequence $$(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots,$$ with the property that the sum of the terms appearing in the $n$'th run equals twice the $n$'th term of the sequence. We give a connection between this sequence and the paperfolding sequence, and then prove Cloitre's conjecture about the density of $1$'s appearing in $(a_n)_{n \geq 1}$.
academic

Cloitreの自己生成数列

基本情報

  • 論文ID: 2501.00784
  • タイトル: Cloitre's Self-Generating Sequence
  • 著者: Jeffrey Shallit (ウォータールー大学)
  • 分類: math.CO cs.DM cs.FL math.NT
  • 発表日: 2025年1月3日
  • 論文リンク: https://arxiv.org/abs/2501.00784

要旨

2009年、Benoit Cloitreは特殊な自己生成数列 (an)n≥1=1,1,2,1,1,1,1,2,1,1,2,1,1,2,2,…(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots を導入しました。この数列は、第nn番目のラン（run）内のすべての項の合が数列の第nn項の2倍に等しいという性質を持ちます。本論文は、この数列と紙折り数列との関連性を確立し、数列内の数字1の密度に関するCloitreの予想を証明しています。

研究背景と動機

研究問題

本論文が研究する中心的な問題は、Cloitre自己生成数列の構造的性質の分析です。特に以下の点が対象です：

  1. 該当数列と既知の数学対象（紙折り数列）との関係
  2. 数列内の数字1の漸近密度問題

問題の重要性

自己生成数列は組合せ論において重要な地位を占めており、複雑な構造的性質を示すとともに、複数の数学分野と関連しています。Cloitre数列の研究は以下の意義を持ちます：

  • 自己生成数列の性質に関する理解の拡張
  • 紙折り数列などの古典的数列との新たな関連性の確立
  • オートマトン理論の数列分析への応用における新しい事例の提供

既存研究の限界

Oldenburger-Kolakoski数列などの類似数列に関する既存研究は、このような数列の漸近的性質の分析がしばしば困難であることを示しています。例えば、Oldenburger-Kolakoski数列については、1の密度が1/2であるかどうかは依然として未解決の予想です。

研究動機

Cloitreは OEIS エントリ A157196 において、該当数列内の1の密度が2/3であるという予想を提出しました。これが本論文の研究に明確な目標を提供しています。

核心的貢献

  1. 新しい数列関連性の確立：Cloitre自己生成数列と正規紙折り数列との間の深層的関連性を初めて発見
  2. 密度予想の証明：Cloitreが提唱した数列内の1の密度が2/3であるという予想を厳密に証明
  3. 精密な境界の提供：0≤3gn−2n≤40 \leq 3g_n - 2n \leq 4 を証明。ここでgng_nは最初のnn項における1の個数
  4. オートマトン手法の開発：有限オートマトンとWalnutソフトウェアを用いた数列分析の計算検証フレームワークを構築
  5. 一般的ケースへの拡張：結果を任意の紙折り数列に推広

方法論の詳細

タスク定義

Cloitre数列(an)n≥1(a_n)_{n\geq 1}を研究します。この数列は以下の自己生成規則により定義されます：

  • 数列は文字集合{1,2}上の値を取る
  • a1=1a_1 = 1から開始
  • 第nn番目のラン内のすべての要素の合は2an2a_nに等しい

核心的方法論の構造

1. 数列構成チェーン

論文は相互に関連する一連の数列を構成しました：

  • 正規紙折り数列(pn)(p_n)
  • 二進版(qn)(q_n)。pn=(−1)qnp_n = (-1)^{q_n}を満たす
  • 一階差分数列(dn)(d_n)
  • 絶対値数列(dn′)(d'_n)
  • ラン終了位置(en′)(e'_n)
  • 最終的に(bn)=(an)(b_n) = (a_n)を得る

2. オートマトン表現

各数列は有限オートマトンで表現できます：

  • DFAO（出力付き決定性有限オートマトン）：有限値を取る数列用
  • 同期オートマトン：整数値を取る数列用
  • すべてのオートマトンは最下位ビット優先の二進表現を使用

3. Walnut検証フレームワーク

Walnutソフトウェアを用いた形式的検証：

eval q_test "?lsd_2 An (Q[2*n]=Q[n] & Q[4*n+1]=@0 & Q[4*n+3]=@1)":

技術的革新点

1. 紙折り数列との接続

Cloitre数列と紙折り数列との関連性を革新的に発見： q2n=qn,q4n+1=0,q4n+3=1q_{2n} = q_n, \quad q_{4n+1} = 0, \quad q_{4n+3} = 1

2. 予想-検証戦略

複雑な数列（ラン終了位置など）に対して、「オートマトンを予想してから検証する」戦略を採用しました。これは自動数列を扱う際の効果的な方法です。

3. 多層数列分析

複数の中間数列を構成することで、複雑な自己生成性質を処理可能なオートマトン計算に分解しました。

実験設定

計算ツール

  • Walnutソフトウェア：オートマトン計算と形式的検証用
  • 有限オートマトン：すべての数列はオートマトン表現と計算を通じて処理
  • OEISデータベース：数列検証と比較用

検証方法

  1. オートマトン正確性検証：複数の条件チェックを通じたオートマトンの正確性検証
  2. 漸化式検証：数列が満たす漸化式の検証
  3. 境界条件チェック：初期条件と特殊ケースの検証

実装詳細

  • 最下位ビット優先の二進表現を使用
  • オートマトン状態数は4から32個まで様々
  • すべての計算はWalnutの形式的検証を経由

実験結果

主要定理の証明

定理2：gng_nを数列a1a2⋯ana_1a_2\cdots a_n内の1の個数とすると： 0≤3gn−2n≤40 \leq 3g_n - 2n \leq 4 したがってlim⁡n→∞gn/n=2/3\lim_{n\to\infty} g_n/n = 2/3。

主要検証結果

  1. 数列一貫性：bn=anb_n = a_nを検証。構成された数列が実際にCloitre数列であることを確認
  2. 自己生成性質：σn=2bn\sigma_n = 2b_nを検証。ここでσn\sigma_nは第nn番目のランの合
  3. ラン長：ラン長が1、2、または4のみであることを証明
  4. 密度境界：16状態オートマトンを通じた密度境界の検証

追加的発見

数列wn=min⁡{t≥1:et′≥n}w_n = \min\{t \geq 1 : e'_t \geq n\}がOEIS数列A091960であることを証明。以下を満たします：

  • w1=1w_1 = 1
  • w2n=w2n−1+(wn mod 2)w_{2n} = w_{2n-1} + (w_n \bmod 2)
  • w2n+1=w2n+1w_{2n+1} = w_{2n} + 1

関連研究

主要関連数列

  1. Oldenburger-Kolakoski数列：k:=1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,…k := 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, \ldots
    • 第nn項は第nn番目のランの長さに等しい
    • 1の密度問題は依然未解決
  2. Dekking数列：1,3,3,3,1,1,1,3,3,3,…1, 3, 3, 3, 1, 1, 1, 3, 3, 3, \ldots
    • ラン長数列が数列そのものに等しい
    • 射の不動点として理解可能
  3. 紙折り数列：反復的な紙折りから生成される数列
    • 二進表現との深層的関連性
    • 有限オートマトンで計算可能

本論文の貢献の独自性

Cloitre数列はOldenburger-Kolakoski数列より扱いやすいです。なぜなら、二進表現との微妙だが明確な関連性があり、これがオートマトン手法を特に有効にするからです。

結論と考察

主要結論

  1. 密度定理：Cloitre数列内の1の密度が2/3であることを厳密に証明
  2. 構造的関連性：紙折り数列との深層的関連性を確立
  3. 計算フレームワーク：数列分析におけるオートマトン手法の強大な能力を実証

方法論の普遍性

論文第7節は、すべての結果が任意の紙折り数列に推広可能であることを示しています。ただし、一般的ケースでは明白な自己生成性質の類似物がありません。

今後の方向性

  1. 他の自己生成数列と古典的数列との関連性の研究
  2. より一般的なオートマトン分析フレームワークの開発
  3. 他の数学分野への応用の探索

深層的評価

利点

  1. 方法論の革新性：オートマトン理論と数列分析の巧妙な結合
  2. 厳密性：すべての結果が形式的検証を通じて実施
  3. 完全性：主要予想の証明に加えて、追加的な構造的性質を発見
  4. 拡張可能性：方法論がより広範な数列カテゴリーに推広可能

技術的ハイライト

  1. 予想-検証戦略：複雑な自動数列分析に実用的な方法を提供
  2. 多層数列構成：中間数列を通じた複雑性質分析の簡潔化
  3. 計算検証：Walnutソフトウェアの使用により結果の信頼性を保証

限界

  1. 計算複雑性：特定のオートマトン状態数が多く、より複雑な数列分析を制限する可能性
  2. 予想依存性：部分的なオートマトンが予想後の検証に依存し、体系的な構成方法が不足
  3. 推広制限：任意の紙折り数列への推広は可能ですが、自己生成性質を失う

影響力

  1. 理論的貢献：自己生成数列研究に新しい分析ツールを提供
  2. 方法論的価値：組合せ論における計算機支援証明の応用を実証
  3. 実用性：OEIS内の関連数列研究にテンプレートを提供

適用シーン

本手法は特に以下に適しています：

  • 二進表現と関連する数列分析
  • 漸化構造を持つ自動数列研究
  • 精密な密度分析が必要な組合せ数列

参考文献

論文は14篇の重要な文献を引用しており、自動数列理論、紙折り数列、Kolakoski数列など関連分野の古典的業績をカバーしており、研究に堅実な理論的基礎を提供しています。