Dyck Words, Pattern Avoidance, and Automatic Sequences

この論文は、0 と 1 をそれぞれ左括弧と右括弧とみなしたときの Dyck 語の性質を研究し、$7/3$-冪フリーな二進語の括弧の入れ子深さが有界であることを示すとともに、Thue-Morse 語に含まれる Dyck 語の因子を明示的に特徴づけ、その個数に関する厳密な上下界を導出したものである。

要約

この論文は、数学とコンピュータサイエンスの面白い交差点にある「括弧の並び」と「規則的なパターン」について書かれたものです。専門用語を避け、誰でもイメージしやすい例え話を使って解説しましょう。

🎈 物語の舞台：「括弧の森」と「自動運転の車」

まず、この論文で扱っている「 Dyck 語（ダイク語）」とは何か想像してみてください。
それは**「正しくバランスの取れた括弧の列」**です。
例えば、(()()) は正しいですが、(() や ())( はダメです。
ここでは、0 を「左の括弧 (」に、1 を「右の括弧 )」に見立てています。
論文の著者たちは、この「正しい括弧の列」が、ある特定の「無限に続く数字の列（2 進数の並び）」の中に、どれくらい隠れているか、そしてどんな形をしているかを調べました。

---

🔍 発見その 1：「繰り返しのルール」と「括弧の深さ」

【どんな話？】
ある数字の列の中に、「同じパターンが何度も繰り返されること」を禁止すると、括弧の「重なり具合（深さ）」に上限ができるのか？という実験です。

【例え話】
Imagine you are building a tower of nesting dolls (matryoshka).

• 7/3 乗フリー（7/3-power-free）： 「同じ形が 2.33 回以上繰り返されないように」という厳しいルールがあります。
• 結果： この厳しいルールを守ると、括弧の重なり（ネスト）は高々 3 段までに抑えられます。どんなに長い列を作っても、4 段目の奥まで入ることはできません。
• でも、ルールを少し緩めると： 「2.33 回より少しだけ多く繰り返してもいいよ」というルール（7/3 乗より大きい指数）にすると、無限に深い括弧の塔を作ることができてしまいます。

【意味】
「繰り返しの厳しさ」と「括弧の複雑さ」には、驚くほど密接な関係があることがわかりました。

---

🤖 発見その 2：「トゥー・モース数列」という魔法の機械

【どんな話？】
「トゥー・モース数列（Thue-Morse sequence）」という、コンピュータが生成する有名な規則的な数字の列があります（01101001... と続く）。
この列の中に、正しい括弧の列（Dyck 語）がどれくらい含まれているか、そしてそれがどんな形をしているかを完全に解明しました。

【例え話】
この列は、ある「変換ルール（魔法の機械）」を通すと、すべて括弧の形に変わるという性質を持っています。

• 著者たちは、「この列のどの部分を取り出しても、それが括弧の形になるためには、元の列が『特定の形』をしていなければならない」という完全なレシピを見つけました。
• さらに、長さ $2n$ の括弧の列が、この数列の中にいくつあるかを正確に数える公式（正確には、コンピュータが計算できる「規則的な数列」）を見つけ出しました。

【すごい点】
「どれくらいあるか」を数えるのが難しい問題ですが、著者たちは「 Walnut（ウォルナット）」という強力な証明プログラムを使って、この数を正確に計算し、その数が増えるパターン（最大値や最小値の目安）を突き止めました。

---

🧩 発見その 3：他の数列でも「括弧」は隠れている

【どんな話？】
トゥー・モース数列だけでなく、他の有名な数列（フィボナッチ数列やルディン・シャピロ数列など）でも、括弧の列を探してみました。

【例え話】

• フィボナッチ数列： ここには、括弧の列は「01（1 段）」と「0101（2 段）」しかありません。深い塔は作れません。
• ルディン・シャピロ数列： こちらは驚くべきことに、無限に深い括弧の塔を作ることができます！
• 折り紙数列（Paperfolding）： これについては「長さ $n$ の括弧の列ができるかどうか」の条件を推測（予想）しました。

---

🛠️ 使われた道具：「Walnut（ウォルナット）」

この論文の最大の特徴は、人間の頭だけで計算するのではなく、「Walnut」という AI 的な証明プログラムを駆使したことです。

• 著者たちは、複雑な数学的なルールをプログラムに「入力」し、「本当にそうなるか？」をコンピュータに厳密に検証させました。
• 人間には計算しきれないような巨大なパターン（130GB のメモリを使うような計算）も、このツールを使えば「はい、間違いありません」と証明できてしまいます。

---

💡 まとめ：この論文が伝えたかったこと

1. ルールは重要： 「繰り返しの禁止ルール」を少し変えるだけで、括弧の重なり具合が「有限」から「無限」に劇的に変わります。
2. 規則的な世界には秩序がある： 一見ランダムに見える「トゥー・モース数列」のような規則的な列でも、括弧の列の出現パターンには美しい法則（線形表現）が存在します。
3. コンピュータの力： 複雑な数学の問題も、適切なツール（Walnut）を使えば、人間が証明できないレベルの厳密さで解ける時代が来ている。

この論文は、**「括弧のバランス」という単純なゲームを通して、「無限の列の中に潜む隠れた秩序」**を暴き出した、数学的な探検記録なのです。

技術概要

論文「Dyck words, pattern avoidance, and automatic sequences」の技術的サマリー

この論文は、Lucas Mol, Narad Rampersad, Jeffrey Shallit によって執筆され、2025 年の『Communications in Mathematics』に掲載された研究です。主なテーマは、二値列（0 と 1 の列）におけるDyck 語（括弧付きの平衡列）の性質、特にパターン回避（重複の回避）との関係、および自動列（automatic sequences）における Dyck 部分列の構造と数え上げです。

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

---

1. 問題設定と背景

• Dyck 語の定義: 0 を左括弧「(」、1 を右括弧「)」とみなしたとき、バランスの取れた括弧列となる有限二値列を Dyck 語と呼びます。
  • 例: 010011 は Dyck 語ですが、0110 はそうではありません。
  • 形式的には、空列、または 0y1 または yz（y, z が Dyck 語）の形として定義されます。
• ネストレベル（Nesting Level）: 列内の括弧の入れ子の深さを表す指標 $N(x)$ です。
• パターン回避: 特定の冪（power）を含むことを避ける性質を研究します。
  • 指数 $\alpha$ の冪（$\alpha$-power）: 周期 $p$ を持つ列 $w$ において、$|w|/p = \alpha$ となるもの。
  • $\alpha$-power-free: 指数が $\alpha$ 以上の冪を含まない列。
• 研究目的:
  1. 特定の冪回避条件（例: 7/3-power-free）を満たす Dyck 語のネストレベルに上限があるか？
  2. Thue-Morse 列やその他の自動列において、Dyck 部分列がどのように現れ、その数はどのように振る舞うか？
  3. Dyck 部分列の数を数え上げる関数の性質（k-regular 性など）を明らかにする。

2. 手法とアプローチ

本研究では、組合せ論的な証明と、Walnut という定理証明システム（自動列に関する性質を検証するためのツール）を併用しています。

• Walnut の活用:
  • 自動列の性質を第一階論理式で記述し、有限オートマトン（DFAO）を構築して検証します。
  • 重複回避（overlap-free, power-free）や Dyck 語の存在、ネストレベルの計算などを自動化して証明しています。
• 準同型写像（Morphism）の構成:
  • 任意のネストレベルを持つ Dyck 語を構成するために、特定の準同型写像 $f$ と $g$ を定義し、その反復適用によって目的の列を生成します。
• 線形表現（Linear Representation）:
  • Dyck 部分列の個数 $d(n)$ が $k$-regular 列（線形表現を持つ列）であることを示すために、行列とベクトルを用いた表現を構築し、漸近的な挙動を解析します。

3. 主要な貢献と結果

3.1 冪回避とネストレベルの関係

• 定理 2.1: 二値列が 7/3-power-free かつ Dyck 語である場合、そのネストレベルは最大で 3 以下です。
  • 証明は、ネストレベル 3 以上の列を構成しようとすると、必ず 7/3 以上の冪（立方など）が現れてしまうことを示すことでなされました。
• 最適性の証明: 指数 7/3 は最適です。すなわち、7/3+-power-free（7/3 より大きい冪を含まない）な Dyck 語は、任意のネストレベルで存在します。
  • 具体的な構成として、6-ユニフォーム準同型 $g$ と 38-ユニフォーム準同型 $f$ を用い、$f(g^t(2))$ がネストレベル $2t+2$ の 7/3+-power-free Dyck 語となることを Walnut で検証しました。

3.2 Thue-Morse 列における Dyck 部分列

• 特徴付け（定理 3.1）: Thue-Morse 列 $t$ の Dyck 部分列は、ある特定の準同型 $h$ を施した $s$（Thue-Morse 列に関連する別の列）の部分列と完全に一致します。
  • $h(0)=01, h(1)=0011, h(2)=001011$ として、$h(x)$ が Dyck 語となる $x$ の構造を特定しました。
• 自動列一般への拡張（定理 4.1）:
  • 「running-sum synchronized」（部分和が同期した）という条件を満たす $k$-automatic 列において、Dyck 部分列の開始位置と長さ、およびネストレベルを判定する有限オートマトンを構築可能であることを示しました。
  • これにより、Thue-Morse 列のような列において、「任意の長さの Dyck 部分列が存在するか」「ネストレベルが有界か」が決定可能（decidable）であることが示されました。
• 数え上げと k-regular 性（定理 4.5, 4.6）:
  • Thue-Morse 列の長さ $2n$の Dyck 部分列の個数$d(n)$ は、2-regular 列であることを証明しました。
  • 具体的には、$d(n)$ を計算するためのランク 7 の線形表現 $(v_d, \gamma_d, w_d)$ を導出しました（Remark 4.7）。これにより効率的な計算が可能になりました。

3.3 $d(n)$ の上下界

• 定理 5.2（上界）: 任意の $n \ge 1$ に対して $d(n) \le n$ が成り立ちます。また、$n = 3 \cdot 2^i$ の場合に等号が成立します（tight bound）。
• 定理 5.3（下界）: $n \ge 0$ に対して $d(n) \ge n/2$ が成り立ちます。また、$n$ が奇数の場合は $d(n) \ge (n+3)/2$ です。
• 定理 5.4（平均値）: 部分和 $\sum_{i=0}^{2^n-1} d(i)$ の漸近挙動を解析し、$d(n)$ の平均値が約 $\frac{19}{24}n$ であることを示しました。

3.4 その他の列における結果

• Fibonacci 列: 非空の Dyck 語は 01 と 0101 のみです（Proposition 6.1）。
• Period-doubling 列: 非空の Dyck 語は 01, 0101, 010101 のみです（Proposition 6.2）。
• Rudin-Shapiro 列:
  • 任意に大きなネストレベルを持つ Dyck 部分列が存在します（定理 6.3）。
  • 長さ $n$ の Dyck 部分列が存在する $n$ の集合は、4-automatic（したがって 2-automatic）集合です（定理 6.4）。
  • Walnut を用いて、長さ $n$ の Dyck 部分列の存在を判定するオートマトンを構築しました。

4. 意義と結論

この論文は、Dyck 語という古典的な言語理論の概念を、現代の自動列理論とパターン回避の文脈で深く掘り下げたものです。

1. 理論的限界の明確化: 「7/3-power-free」という条件が Dyck 語の複雑さ（ネストレベル）を厳密に制限する閾値であることを示しました。これは、重複回避と構造的複雑さの間の興味深い関係を示唆しています。
2. 計算可能性の確立: 自動列の文脈において、Dyck 語の存在やその性質（長さ、ネストレベル）が有限オートマトンによって決定可能であることを示し、Walnut を用いた具体的な検証手法を確立しました。
3. 数え上げの解析: Thue-Morse 列における Dyck 部分列の個数 $d(n)$ が 2-regular 列であることを示し、その正確な漸近挙動（上下界と平均値）を導出しました。これは、自動列内の特定のパターンの頻度を解析する手法の発展に寄与しています。

総じて、この研究は形式言語理論、組合せ論、計算理論の交差点において、Dyck 語の振る舞いに関する重要な知見を提供し、Walnut などの定理証明ツールを用いた自動列研究の手法論をさらに強化するものとなっています。