WELLDOC property for words generated by morphisms

Each language version is independently generated for its own context, not a direct translation.

1. 物語の舞台：無限の文字列と「パリの地図」

まず、想像してみてください。
アルファベット（0 と 1 など）で書かれた、止まることのない長い文字列があるとします。
例：0100101001...

この文字列の中に、特定の小さな単語（例：01）が何度も登場します。
**「WELLDOC 性質」とは、この 01 が現れる「直前の場所」**が、非常に均等に分布しているかどうかという話です。

具体的なイメージ：「パリの地図と郵便番号」

文字列 = パリの街並み。
特定の単語（01） = 「エッフェル塔」。
直前の場所 = エッフェル塔にたどり着くまでの「歩いた距離」や「通った交差点の数」。
パラキベクトル（Parikh vector） = 「0 を何回通ったか」「1 を何回通ったか」を数えた**「歩数メモ」**。

WELLDOC 性質があるとは？
「エッフェル塔（01）にたどり着く前に、あなたが歩いた『0 と 1 の組み合わせ（歩数メモ）』が、どんな数字の組み合わせ（例：0 を 3 回、1 を 5 回）でも、必ずどこかで実現できる」ということです。

もしこれが成り立たないと、特定の「歩数メモ」の組み合わせしか取れないため、街の構造に**「欠陥（格子構造の欠陥）」**があることになります。これは、乱数生成器（サイコロのようなもの）を作る際に、偏りが出てしまうことを意味します。

2. この文字列はどうやって作られる？「魔法の規則」

この論文では、ランダムに文字を並べるのではなく、**「変換規則（モルフィズム）」**を使って文字列を作った場合を考えます。

規則の例：「0 は『01』に変わる」「1 は『0』に変わる」
プロセス：
1. 0 から始める。
2. 規則を適用：0 → 01
3. さらに適用：01 → 01 0 → 010
4. さらに適用：010 → 010 01 010 → 01001010
  ...と、無限に伸びていきます。

このように**「魔法の規則」で自動的に作られた文字列**が、前述の「WELLDOC 性質（均等さ）」を持っているかどうかを、この論文は突き止めました。

3. 発見された「正解の鍵」

著者たちは、この「均等さ」があるかどうかを判断する2 つの重要な条件を見つけました。

条件①：「行列式（デターミナント）」が±1 であること

イメージ：規則を「箱」や「変換器」に例えます。
この変換器が、情報を**「潰したり、歪めたりせず」、かつ「1 対 1 で正確に」**変換できているかどうかを測る数値が「行列式」です。
±1 であること = 「変換器が完璧に機能しており、情報が失われていない（あるいは 1 倍のまま保たれている）」状態です。
もしこの値が±1 でないと、文字列の「歩数メモ」が特定の方向に偏ってしまい、WELLDOC 性質は失われます。

条件②：「最初の文字に戻る道」が迷路を網羅していること

イメージ：文字列の中で「0」に戻ってくる道（リターンワード）を考えます。
2 進数（0 と 1 のみ）の場合：条件①（行列式が±1）さえ満たせば、自動的に「均等さ」が保証されます。
3 文字以上の場合：条件①だけでは不十分です。
- 「最初の文字（0）に戻る道」の組み合わせが、数学的に「すべての可能性を網羅しているか（生成しているか）」を確認する必要があります。
- 例え話：「0」に戻る道が「A 道」「B 道」しかないのに、目的地が「C 道」を通らなければならない場合、WELLDOC 性質は成立しません。すべての「道」が揃っているかが重要です。

4. なぜこれが重要なのか？

この研究は、**「より良い乱数（サイコロ）」**を作るために役立ちます。

背景：コンピュータで乱数を作る際、従来の方法には「格子構造の欠陥」という、見えない偏りがありました（サイコロの目が特定の並びになりやすいなど）。
解決策：この論文で示された「WELLDOC 性質」を持つ文字列を使えば、その偏りをなくせます。
メリット：この文字列は「魔法の規則（モルフィズム）」で簡単に作れるため、計算が非常に高速です。つまり、**「高速で、かつ偏りのない、高品質な乱数」**を作れるようになるのです。

まとめ

この論文は、**「特定の規則で無限に続く文字列」が、「どんなパターンでも均等に現れる完璧なランダム性」を持っているかどうかを判断する「チェックリスト」**を作ったものです。

チェックポイント 1：規則が情報を歪めていないか（行列式が±1）。
チェックポイント 2：（文字の種類が多い場合）規則がすべての道筋をカバーしているか。

このチェックに合格すれば、その文字列は「偏りのない、美しい無限の物語」と言えるのです。

Each language version is independently generated for its own context, not a direct translation.

この論文「WELLDOC property for words generated by morphisms（準同型写像によって生成される単語の WELLDOC 性質）」は、無限単語の組合せ論的性質である「WELLDOC（well distributed occurrences）」と、それを生成する準同型写像（morphism）の代数的性質との関係を解明したものです。

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

1. 問題設定 (Problem)

WELLDOC 性質の定義:
無限単語 $w$ が WELLDOC 性質を満たすとは、 $w$ の任意の因子（部分列） $u$ と任意の正整数 $m$ 、および任意のベクトル $v \in \mathbb{N}^d$ に対して、 $u$ の出現位置の直前にある $w$ の接頭辞（prefix）の Parikh ベクトル（各文字の出現回数を成分とするベクトル）が、 $v$ に合同（modulo $m$ ）となるような $u$ の出現が存在することを意味します。
簡潔に言えば、任意の因子 $u$ に対して、その出現直前の接頭辞の文字構成（Parikh ベクトル）が、任意のモジュロ $m$ において、 $\mathbb{Z}_m^d$ のすべての要素を網羅している性質です。
背景と動機:
この性質は、疑似乱数生成器（PRNG）における「格子構造（lattice structure）」の欠陥を避けるための条件として導入されました。線形合同生成器を組み合わせる際、生成される数列が格子構造を持たないことを保証する組合せ的条件として WELLDOC が提案されています。
既知の結果として、シュトゥルミアン（Sturmian）単語やエピシュトゥルミアン（episturmian）単語は WELLDOC 性質を満たすことが知られていましたが、「どのような準同型写像が生成する単語が WELLDOC 性質を満たすのか？」という一般的な特徴付けは未解決でした。
研究課題:
準同型写像によって生成される無限単語が WELLDOC 性質を満たすための必要十分条件を導出すること。

2. 手法とアプローチ (Methodology)

論文は、代数学（線形代数、群論）と組合せ論（準同型写像、再帰的単語、戻り単語）を融合させてアプローチしています。

代数的アプローチ:
準同型写像 $\phi$ に対して、その文字の出現回数の変化を表す行列 $A_\phi$ （Parikh 行列）を定義します。この行列の行列式 $\det A_\phi$ の性質（特に $\pm 1$ かどうか）が鍵となります。
- $\det A_\phi = \pm 1$ の場合、行列は整数環 $\mathbb{Z}$ 上で可逆であり、任意のモジュロ $m$ においても可逆です。
- $\det A_\phi \neq \pm 1$ の場合、ある素数 $p$ に対して行列が特異となり、特定のベクトルを生成できなくなります。
戻り単語（Return Words）の解析:
単語の先頭文字（ここでは 0）への「戻り単語（return words）」の Parikh ベクトルが生成する加法群に注目します。WELLDOC 性質は、これらの戻り単語の Parikh ベクトルが $\mathbb{Z}^\sigma$ （ $\sigma$ はアルファベットサイズ）を生成するかどうかに帰着されます。
切断因子（Cutting Factor）の概念:
必要性の証明においては、Mossé による「識別可能（recognizable）」な準同型写像の性質を利用します。 $\det A_\phi \neq \pm 1$ の場合、特定の長さの因子が「切断因子」となり、その出現位置が常に切断点（ブロック境界）と一致することを示し、WELLDOC 性質が破綻することを証明します。

3. 主要な貢献と結果 (Key Contributions and Results)

この論文の中心的な成果は、準同型写像によって生成される無限単語が WELLDOC 性質を満たすための必要十分条件の提示です。

定理 1（2 文字アルファベットの場合）

2 文字アルファベット上で生成される無限の再帰的（recurrent）単語 $w$ について、以下の同値が成り立ちます。

$w$ は WELLDOC 性質を満たす。
準同型写像 $\phi$ の行列 $A_\phi$ の行列式が $\det A_\phi = \pm 1$ である。

定理 2（一般のアルファベットの場合）

一般のアルファベット（サイズ $\ge 2$ ）上で生成される無限単語 $w$ について、以下の同値が成り立ちます。

$w$ は WELLDOC 性質を満たす。
$\det A_\phi = \pm 1$ かつ、単語 $w$ の先頭文字への戻り単語の Parikh ベクトルが、加法群として $\mathbb{Z}^{|\Sigma|}$ を生成する。

決定可能性 (Decidability)

定理 2 の条件（戻り単語の Parikh ベクトルが $\mathbb{Z}^{|\Sigma|}$ を生成するか）は、アルゴリズム的に判定可能であることを示しました（Proposition 7）。具体的には、戻り単語の集合を有限ステップで計算し、そのベクトルが生成する群を調べることで判定できます。

具体例と反例

シュトゥルミアン単語: 既知の結果を再証明し、シュトゥルミアン準同型写像の行列式が常に $\pm 1$ であることを示しました。
反例: 行列式が $\pm 1$ であっても、戻り単語の条件を満たさない場合（非 2 文字の場合）には WELLDOC 性質を満たさないことを示す具体的な準同型写像の例を提示しました。これにより、非 2 文字の場合における「戻り単語の条件」の必要性が確認されました。

4. 論文の構成と証明の概要

定義と主要結果: WELLDOC 性質、Parikh ベクトル、準同型写像の行列の定義。
代数的背景: 行列の可逆性、 $\mathbb{Z}/m\mathbb{Z}$ 上の生成性に関する代数補題。
十分性の証明:
- $\det A_\phi = \pm 1$ かつ戻り単語が $\mathbb{Z}^\sigma$ を生成する場合、任意の因子 $u$ に対して、その直前の接頭辞の Parikh ベクトルが任意の値を取りうることを示す（帰納法と行列の可逆性を利用）。
- 2 文字の場合、戻り単語の条件が自動的に満たされることを証明（Theorem 4）。
必要性の証明:
- $\det A_\phi \neq \pm 1$ の場合、Mossé の識別可能性（recognizability）を用いて「切断因子」の存在を証明。
- 切断因子が存在すると、接頭辞の Parikh ベクトルが特定の部分空間に制限され、WELLDOC 性質が成り立たないことを示す（Theorem 7, 9）。

5. 意義と応用 (Significance)

疑似乱数生成器の設計:
格子構造の欠陥を持たない高品質な疑似乱数生成器を構築する際、どの準同型写像を用いればよいかを理論的に保証する基準を提供しました。準同型写像は高速に生成できるため、実用的な PRNG 設計において重要です。
組合せ論と代数学の統合:
無限単語の組合せ論的性質（因子の分布）を、代数的な不変量（行列式、生成群）と厳密に結びつけた点で、理論的な深みがあります。
決定可能性の確立:
与えられた準同型写像が WELLDOC 性質を満たすかどうかを、有限の計算で判定できることを示したことは、実用的なアルゴリズム開発の基盤となります。

総じて、この論文は「WELLDOC 性質」という抽象的な組合せ論的性質を、準同型写像の行列式と戻り単語の構造という具体的な代数的・組合せ論的条件によって完全に特徴付けることに成功した重要な研究です。