Runs in Paperfolding Sequences

本論文は、紙折り系列における走査長（ラン長）の列およびその開始・終了位置が 2-同期化（2-synchronized）であり有限オートマトンで計算可能であることを示し、これにより Bunder らの既知の結果をより一般的な枠組みで再証明するとともに、これらのラン長系列の臨界指数や部分語複雑性に関する新たな結果を導出している。

要約

この論文は、「紙を折る」という単純な遊びから生まれる、驚くほど複雑で美しい数学の法則について書かれています。

著者のジェフリー・シャリット氏は、紙を折ることでできる「折り紙数列（ペーパーフォルディング・シーケンス）」というパターンを研究し、その中にある「同じ数字が連続している長さ（ラン）」に隠された秘密を解き明かしました。

専門用語を排し、日常の例えを使ってこの研究の面白さを解説します。

---

1. 紙を折るゲームと「山と谷」

まず、想像してみてください。長い紙を何度も折って、最後に広げます。

• 山折り（+1）
• 谷折り（-1）

この「山と谷」の並び順が、紙を折る数列です。
このゲームには無限のバリエーションがあります。毎回「右に折る」か「左に折る」かを自由に選べば、無限に違うパターンが生まれます。

2. 「同じ色が並んでいる長さ」を探す

この数列を見てみると、例えば「山、山、谷、山、山、山、谷…」のように、同じ方向が連続している部分があります。これを**「ラン（Run）」**と呼びます。

• 「山、山」なら長さ 2
• 「谷」なら長さ 1
• 「山、山、山」なら長さ 3

研究者は、この「長さの並び（2, 1, 3, 2, 2...）」に注目しました。
「この長さの並びは、ある決まったルール（機械）で予測できるのか？」
というのが、この論文の核心です。

3. 魔法の機械「有限オートマトン」

通常、複雑な数列の規則を見つけるのは至難の業です。しかし、この論文では**「有限オートマトン（Finite Automaton）」**という、まるで単純なロボットのような機械を使いました。

• アナロジー：
  想像してください。この機械は「入力された数字（どの折り返し回数か）」を見て、**「次のランの長さは 1 ですか？2 ですか？それとも 3 ですか？」**を即座に答える、小さな計算機です。

  驚くべきことに、この機械は**「どんな紙の折り方（無限のパターン）に対しても、同じ一つで機能する」**ことが証明されました。
  つまり、紙の折り方がどんなに複雑でも、その「長さの規則」は、この小さな機械の頭の中にすべて収まっているのです。

4. 発見された「驚きのルール」

この機械を使って調べることで、いくつかの面白い法則が見つかりました。

• 長さの制限：
  紙を折ってできる「同じ方向の連続」の長さは、1、2、3 のどれかしかありません。4 以上は絶対に現れません。これは、紙を折る物理的な性質と数学的な美しさが一致している証拠です。

• 繰り返しの禁止：
  この長さの並びには、「同じパターンが重なり合うこと（オーバーラップ）」は絶対にありません。

  • 例：「12121」のような、1 と 2 が交互に 3 回以上続くことは起きません。
    これは、この数列が「カオス（無秩序）」ではなく、「高度に整理された秩序」を持っていることを示しています。

• パズルのピース：
  この数列の中に現れる「同じ長さの連続（例：22）」や「回文（例：212）」のパターンも、非常に限られた種類しか存在しないことが分かりました。まるで、この数列は特定のレゴブロックだけで作られた城のようですね。

5. 折り紙と「分数」の不思議な関係

論文の最後には、もっとも有名な「規則正しい折り方（常に同じ方向に折る）」の場合に、**「連分数（分数の分数）」**という数学の概念と深く結びついていることが示されました。

• アナロジー：
  紙を折る「山と谷」のパターンを、ある特定の「分数の値」に変換すると、その分数の小数点以下の桁が、折り紙のランの長さそのものになるのです！
  これは、「紙を折るという物理的な行為」と「純粋な数学の数値」が、実は同じ裏表を持っていることを意味します。

まとめ：なぜこれが重要なのか？

この研究は、単に「紙を折る遊び」の話ではありません。

• 複雑な現象は、実は単純な機械で説明できる
• 一見ランダムに見えるパターンには、厳密な法則が潜んでいる

という、数学の美しさを示しています。
また、この研究で使われた「Walnut（ウォルナット）」という自動証明ツールは、人間が手作業で証明するには不可能な複雑な計算を、コンピュータに任せて「正解」を導き出しました。これは、「人間の直感とコンピュータの計算能力」を組み合わせることで、新しい数学の真理を見つけられるという、現代の科学の進歩を象徴する物語でもあります。

つまり、「紙を折る」という子供の遊びが、実は宇宙の法則や複雑な数学の構造を解き明かす鍵になっていたという、そんな不思議な話なのです。

技術概要

論文「Runs in Paperfolding Sequences」の技術的サマリー

Jeffrey Shallit によるこの論文は、紙折り系列（Paperfolding sequences）における「ラン（run：連続する同一値のブロック）」の長さ、開始位置、終了位置の性質を調査し、それらが有限オートマトンによって計算可能であることを示すものです。また、これらの結果を用いて、ランの長さ系列の臨界指数や部分語複雑性（subword complexity）に関する新たな定理を証明し、Bunder らの既知の結果をより一般的な枠組みで再構成しています。

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

1. 問題設定

紙折り系列は、紙を繰り返し折りたたんで展開する際に生じる「山（+1）」と「谷（-1）」の列として定義される無限系列です。特定の折りたたみ指示列 $f$ に対して一意に定まる系列 $P_f$ が存在しますが、指示列 $f$ の選び方によって非可算無限個の異なる紙折り系列が存在します。

本研究の焦点は、これらの紙折り系列における「ラン（連続する同一値のブロック）」の特性にあります。具体的には以下の問いに答えることを目指しました：

1. ランの長さの系列、および $n$ 番目のランの開始・終了位置は、有限オートマトンによって計算可能か（すなわち、自動的か）？
2. ランの長さ系列の構造（重複、平方、回文など）はどうなるか？
3. 正規の紙折り系列（すべての指示が 1 の場合）に関する既知の結果（Bunder らによるもの）を、より一般的な紙折り系列に対して一般化できるか？
4. ランの長さ系列と実数の連分数展開との間にどのような関係があるか？

2. 手法

本研究の核心的な手法は、定理証明器 Walnut の使用です。Walnut は、第一階論理（First-order logic）で記述された命題が真か偽かを決定し、その証明を構築するツールです。

• 同期オートマトン（Synchronized Automata）の構築:
  紙折り系列自体は有限オートマトンで計算可能（自動的）であることが知られていますが、ランの長さや位置の系列が自動的に計算可能である保証はありません。著者は、折りたたみ指示列 $f$、ランのインデックス $n$、および位置 $x$ を並列に読み取る「同期オートマトン」を構築することで、これらの系列が計算可能であることを示しました。
• 推測と検証のサイクル:
  1. 具体的な例（有限の紙折り系列）からデータを収集し、候補となるオートマトンを推測する。
  2. Walnut を用いて、そのオートマトンが正しいことを第一階論理の式で厳密に検証する。
  3. 検証が成功すれば、その性質がすべての紙折り系列（有限・無限）に成り立つことが数学的に証明される。

3. 主要な貢献と結果

3.1 同期性と計算可能性

• 定理 3: すべての紙折り系列に対して、$n$ 番目のランの開始位置 $S_f[n]$ と終了位置 $E_f[n]$ を計算する同期オートマトンが存在する。
  • 開始位置 $S_f$ を計算するオートマトン $sp$ は 17 状態。
  • 終了位置 $E_f$ を計算するオートマトン $ep$ は 13 状態。
  • これにより、ランの長さ $R_f[n] = E_f[n] - S_f[n] + 1$ も自動的に計算可能であることが示されました。
• 定理 4: 終了位置 $E_f[n]$ は、$2n - \epsilon_n$（$\epsilon_n \in {0, 1}$）の形で表され、$\epsilon_n$は$f$に関連する別の系列$g$の$n$ 番目の項の符号によって決定されることを証明しました。

3.2 ラン長さ系列の構造的特徴

• ** Proposition 5**: 任意の紙折り系列におけるランの長さは、常に 1, 2, または 3 のいずれかであることが証明されました（Bunder らは正規系列のみでこれを証明していました）。
• 定理 7: ラン長さ系列には「オーバーラップ（$axaxa$ 型の部分列）」は存在しない（overlap-free）。
• 定理 8: ラン長さ系列に現れる「平方（$zz$ 型）」は、$22$、$123123$、$321321$ の 3 種類に限られます。
• 定理 10: 現れる回文は、$1, 2, 3, 22, 212, 232, 12321, 32123$ のみです。
• 定理 11: 無限紙折り系列のラン長さ系列の部分語複雑性（length $n$ の異なる部分列の数）は、$n \ge 6$ において $4n + 4$ であることが証明されました。

3.3 正規紙折り系列への適用

正規の紙折り系列（指示列が $1^\omega$）に特化した場合、著者は Bunder らが得た結果（ランの長さ系列$g(n)$や終了位置系列$h(n)$の性質）を、Walnut を用いてより簡潔かつ一般的に再証明しました。例えば、$h(n)$の補集合からなる数列$t(n)$と$g(n)$ の関係性（定理 12）が厳密に検証されました。

3.4 連分数との関係

• 定理 13: 非可算無限個の無理数 $\alpha(\epsilon_2, \epsilon_3, \dots)$ の連分数展開が、紙折り系列のランの長さ系列 $R$ と直接関連していることを示しました。
  • 具体的には、$\alpha$ の連分数が $[0, 1, (2R)']$ （最後の項を 1 増やす）の形で表されることを、折りたたみ補題（Folding Lemma）を用いて帰納的に証明しました。
  • これにより、Bunder らの特定の数に関する結果が、非可算無限個の数のクラスに一般化されました。

4. 意義と結論

この論文の最大の意義は、Walnut 定理証明器を用いることで、紙折り系列のランに関する複雑な数論的・組合せ論的性質を、手計算や個別のケース分析に頼らず、体系的かつ厳密に証明・一般化できた点にあります。

• 一般化: 特定の「正規」系列に限られていた結果を、非可算無限個の紙折り系列全体に適用可能な形で拡張しました。
• 自動化: 自動的（automatic）であることと同期（synchronized）であることの概念を、ランの位置や長さの系列に適用し、それらが有限オートマトンで記述可能であることを示しました。
• 構造の解明: ラン長さ系列が非常に制限された構造（オーバーラップフリー、特定の平方のみ許容、部分語複雑性の線形性）を持つことを明らかにしました。

これらの結果は、自動系列（automatic sequences）の理論、特にその部分系列や変換された系列の複雑性に関する理解を深めるものであり、連分数展開と離散構造の間の驚くべき対応関係を示唆しています。