2025-11-14T18:28:10.300710

On the conjugates of Christoffel words

Bugeaud, Reutenauer

We introduce a parametrization of the conjugates of Christoffel words based on the integer Ostrowski numeration system. We use it to give a precise description of the borders (prefixes which are also suffixes) of the conjugates of Christoffel words and to revisit the notion of Sturmian graph introduced by Epifanio et al.

academic

Christoffel語の共役に関して

基本情報

論文ID: 2202.05486
タイトル: On the conjugates of Christoffel words
著者: Yann Bugeaud (ストラスブール大学およびCNRS、フランス大学研究所)、Christophe Reutenauer (ケベック大学モントリオール校)
分類: math.CO (組合せ論)
発表誌/会議: Discrete Mathematics and Theoretical Computer Science, vol. 27:3 #20 (2025)
受理日: 2025年10月23日
論文リンク: https://arxiv.org/abs/2202.05486

要約

本論文は、整数Ostrowski数制系に基づいてChristoffel語の共役類のパラメータ化方法を導入している。このパラメータ化を利用して、著者はChristoffel語の共役元の境界（前接尾辞かつ後接頭辞である部分語）の正確な特性付けを与え、Epifanioらによって導入されたSturmian図の概念を再検討している。

研究背景と動機

研究問題

本論文はChristoffel語の共役類（conjugation class）の構造と性質を研究している。Christoffel語は1875年にChristoffelによって導入された二元字母表上の特殊な語のクラスであり、その共役は循環置換によって得られる語である。

問題の重要性

Christoffel語とその共役は複数の数学分野で重要な意義を持つ：

自由群理論：二生成元自由群における正の、循環既約化された、基を成す元素に対応する
データ圧縮：二元字母表上の「完全クラスタリング語」（perfectly clustering words）であり、Burrows-Wheeler変換理論に現れる
Sturmian語理論：Sturmian無限語の有限版であり、平面直線の離散化と関連している
二次形式理論：Markoff二次形式およびその最小値を符号化する

既存方法の限界

Christoffel語自体が非負有理数によってパラメータ化されることは周知の結果であるが、その共役類の体系的なパラメータ化方法は以前は不完全であった。特に：

すべての共役元を記述する統一的なパラメータ化フレームワークが欠けていた
Christoffel語の共役元の境界と周期の正確な特性付けが不十分であった
Sturmian図とOstrowski表現の関係をより深く理解する必要があった

研究動機

本論文は、Ostrowski数制に基づく体系的フレームワークを確立し、Christoffel語の共役類を完全に特性付け、このフレームワークを境界問題とSturmian図の構造問題に適用することを目指している。

核心的貢献

パラメータ化構成：整数Ostrowski数制系に基づいて、Christoffel語の共役類の完全なパラメータ化方法を導入した（定理7.3）。これはRauzy規則と標準語構成の一般化である
非可換リフト：Fridの標準語の前接頭辞に関する結果をこの方法の系として証明した（系7.6）。これはOstrowski数制系の非可換リフトと見なせる
境界の特性付け：Christoffel語の共役元の最長境界の正確な記述を与えた（定理8.1）。任意の境界はあるChristoffel語の共役元の冪であることを証明した（系8.2）
Sturmian図の埋め込み：コンパクト図とSturmian図が中心語木とStern-Brocot木に自然に埋め込まれることを証明した（系9.5）。de Lucaの反復回文化理論を利用した
統一フレームワーク：Ostrowski表現、共役類、境界、グラフ理論的構造の間の深い関連性を確立した

方法の詳細説明

タスク定義

正整数列 $a_1, \ldots, a_m$ が与えられたとき、以下を定義する：

連分数多項式： $q_i = K(a_1, \ldots, a_i)$ 。ここで $K$ はcontinuant多項式
パラメータ： $b_i = a_i - 1$ （ $i=1$ の場合）、 $b_i = a_i$ （ $i \geq 2$ の場合）

目標：各整数 $N = \sum_{i=1}^m d_i q_{i-1}$ （Ostrowski表現）に対して、対応するChristoffel語の共役元を構成する。

核心的構成方法

再帰的定義（公式11）

語列 $V_i = V_i(d_1, \ldots, d_m) \in F(A)$ （自由群）を定義する：

$V_{-1} = b, \quad V_0 = a$

$V_i = V_{i-1}^{b_i - d_i} V_{i-2} V_{i-1}^{d_i}, \quad i = 1, \ldots, m$

ここで $A = \{a, b\}$ は二元字母表である。

主要な性質：

$0 \leq d_i \leq b_i$ のとき、 $V_i \in A^*$ （正の語）
$V_i$ の長さは $q_i = K(a_1, \ldots, a_i)$
$V_i$ の傾き（slope）は $[0, a_1, \ldots, a_i]$ （連分数）

自己準同型表現（補題7.1）

語 $V_i$ は自己準同型の合成で表現できる：

$(V_i, V_{i-1}) = \pi(b_1 - d_1, d_1) \circ \cdots \circ \pi(b_i - d_i, d_i)$

ここで $\pi(i, j) = (a^i b a^j, a)$ は特定の字母表自己準同型である。

パラメータ化定理（定理7.3）

主要な結果：

すべての $V_m(d_1, \ldots, d_m)$ （ $0 \leq d_i \leq b_i$ ）は自由群において $M_m = V_m(0, \ldots, 0)$ と共役である
語の意味での共役類は、法的条件を満たすすべてのOstrowski表現に対応する語からなる
正確な公式： $V_m = C^N(M_m)$ 。ここで $C$ は共役作用素、 $N = \sum d_i q_{i-1}$

証明の概要：

補題5.1（自己準同型の共役関係に関する）を利用
$V_m = h^{-1} M_m h$ となる共役元 $h$ を構成
$h$ の代数的長さがちょうど $N$ であることを計算
Ostrowski表現の一意性を利用して共役類全体をカバーすることを証明

技術的な革新点

統一フレームワーク：Rauzy規則、標準語構成、Ostrowski数制を再帰的定義（11）に統一した
代数的方法：自由群の共役理論と自己準同型のabelianization行列を利用して長さを計算
二重表現：
- Greedy表現： $\forall i \geq 2, d_i = b_i \Rightarrow d_{i-1} = 0$
- Lazy表現： $\forall i, 2 \leq i \leq k, d_i = 0 \Rightarrow d_{i-1} = b_{i-1}$
鏡像対称性（命題7.8）： $\widetilde{V_m(d_1, \ldots, d_m)} = V_m(b_1 - d_1, \ldots, b_m - d_m)$
これはgreedy表現とlazy表現の間の双対関係を確立する。

境界理論（第8節）

主要定理（定理8.1）

Christoffel語ではない $V_m(d_1, \ldots, d_m)$ （greedy表現）に対して、その最長境界 $B$ は以下の場合によって決定される：

場合分け：

(i) $d_m = b_m$ の場合： $B = V_{m-1}$
(ii) $1 \leq d_m \leq b_m - 1$ かつ $1 \leq d_{m-1} \leq b_{m-1} - 1$ の場合： $B = V_{m-1}^\ell$ 。ここで $\ell = \min\{b_m - d_m, d_m\}$
(iii)-(vii) その他の場合は類似だがより複雑な記述がある

主要補題（補題8.14）： $V_m = V_{m-1}^{b_m - d_m} V_{m-2} V_{m-1}^{d_m}$ において、 $V_{m-1}$ の出現回数は最大で $b_m + 2$ 回であり、追加の出現は $V_{m-2}$ の近くにのみ起こる。

系（系8.2）

Christoffel語の共役元の任意の境界は、あるChristoffel語の共役元の冪である。

証明の概要：

$u$ がChristoffel語 $w$ の境界ならば、 $uu$ は $ww$ の因子である
$ww$ はSturmian語であるため、 $u$ のすべての共役もSturmian語である
その中にLyndon語の冪が存在し、そのLyndon語はChristoffel語である必要がある

Sturmian図理論（第9節）

コンパクト図の構成

定義：

頂点集合 $V$ ：中心回文 $p = L_0^{c_1} L_1^{c_2} \cdots L_{m-1}^{c_m}$ のすべての前接頭辞（ $L_i$ 上の語として）
辺：二種類の辺
1. 水平辺： $U \xrightarrow{L_i} UL_i$
2. ジャンプ辺： $U \xrightarrow{L_{i+1}} UL_i^k L_{i+1}$ （ $k \geq 1$ ）

主要な結果（系9.2）

定理：中心回文 $p$ の各後接尾辞 $s$ に対して、原点から出発し、ラベルが $s$ である一意の経路が存在する。

証明の要点：

グラフの決定性：各頂点は最大2本の出辺を持ち、ラベルの最初の文字が異なる
経路のラベルはlazy Ostrowski表現に対応する
系9.1を利用： $s = L_0^{d_1} L_1^{d_2} \cdots L_{m-1}^{d_m}$

Stern-Brocot木への埋め込み（系9.5）

命題9.4：中心語 $p$ の指導語（directive word）は $v = a^{c_1} b^{c_2} a^{c_3} \cdots$

埋め込み結果：

コンパクト図とSturmian図は中心語木に自然に埋め込まれる
Stern-Brocot木の対応関係を通じて、この木にも埋め込まれる
de Lucaの反復回文化作用素 $\text{Pal}$ を利用した

実験と検証

計算例（第9節末）

パラメータ： $m = 3, a_1 = 2, a_2 = 1, a_3 = 3$

計算結果：

$M_0 = a, M_1 = ab, M_2 = aba, M_3 = abaabaabaab$
$M_3 = pab$ 。中心語 $p = aba^2ba^2ba$
回文前接頭辞： $1, a, aba, abaaba, p$
指導語： $v = abaa$
$L_0 = a, L_1 = ba, L_2 = aba$

検証：

$p = L_0 L_1^2 L_2 = a \cdot (ba)^2 \cdot aba = aba^2ba^2ba$ ✓
コンパクト図の経路とlazy表現が一致する ✓

理論的検証

論文は付録（第10節）でOstrowski表現の存在と一意性の完全な証明を与えている：

補題10.1：交互列は $q_k - 1$ に対応する

補題10.2：

Greedy表現： $N \leq q_k - 1$
Lazy表現： $N \leq q_k + q_{k-1} - 2$

これらの結果はパラメータ化の完全性を保証する。

結論と考察

主要な結論

完全なパラメータ化：Christoffel語の共役類とOstrowski表現の間の全単射関係を確立した
境界の完全な特性付け：すべての境界はChristoffel語の共役元の冪であり、最長境界の明示的公式を与えた
グラフ理論的統一：Sturmian図とコンパクト図が古典的な木構造に自然に埋め込まれることを示した
理論の深化：組合せ語論、数論（連分数）、自由群理論、グラフ理論を一つのフレームワークで統一した

限界

計算複雑性：論文はパラメータ化構成の計算複雑性を議論していない
一般化可能性：方法は二元字母表に限定されており、より大きな字母表への推広は明らかでない
応用：理論は優雅だが、実際の応用場面の議論は少ない
アルゴリズム実装：具体的なアルゴリズムの疑似コードと実装の詳細が欠けている

今後の方向性

アルゴリズム化：共役元と境界を計算する効率的なアルゴリズムの開発
一般化：より大きな字母表または無限語の類似理論の研究
応用：データ圧縮、パターンマッチングでの応用の探索
関連性：Markoff理論、二次形式との深い関連性のさらなる研究

深い評価

利点

理論的深さ：
- 複数の数学分野の深い関連性を確立した（組合せ論、数論、代数）
- 証明は厳密で完全、論理は明確
方法の革新性：
- Ostrowski パラメータ化は全く新しい視点
- 再帰的構成（11）は優雅で統一的
- 鏡像対称性（命題7.8）は深い構造を明らかにする
結果の完全性：
- 存在性だけでなく一意性と明示的構成も与えた
- 境界定理はすべての場合をカバーしている
- 複数の既知結果を推広し統一した
執筆の質：
- 構造が明確で、基本定義から高度な結果へと段階的に進む
- 補題と定理がよく組織されている
- 具体例が提供されている（第9節）

不足点

可読性の課題：
- 組合せ語論と自由群の強い背景が必要
- 記号体系が複雑（ $V_i, M_i, L_i, q_i, b_i$ など）
- 定理8.1の7つの場合は過度に複雑
実験的検証：
- 小規模な例が1つのみ
- 大規模な数値検証が欠けている
- コードや計算ツールが提供されていない
応用指向：
- 理論的に強いが応用の議論が不足している
- 実際の問題への適用方法が明確でない
- 計算効率が分析されていない
技術的詳細：
- 定理8.1などの証明は長く技術的である
- 付録のOstrowski表現の証明は完全だが可読性が低い

影響力

学術的貢献：
- Christoffel語理論に新しい統一フレームワークを提供した
- 境界の特性付けという重要な問題を解決した
- Ostrowski数制と語組合せ論を結びつけた
潜在的応用：
- データ圧縮アルゴリズム（Burrows-Wheeler変換）
- 記号力学系
- 数論のディオファントス近似
再現可能性：
- 理論的結果は高い再現可能性を持つ
- ソフトウェア実装の欠如が実際の応用を制限する
- 計算例は手作業で検証可能
後続研究：
- アルゴリズム研究に理論的基礎を提供した
- より大きな字母表の研究を刺激する可能性がある
- Markoff理論との関連性の深い探索に値する

適用場面

理論研究：
- 組合せ語論のさらなる研究
- Sturmian語とChristoffel語の性質の探索
- 自由群と自由モノイド理論
アルゴリズム開発：
- 文字列マッチングとパターン認識
- 周期検出アルゴリズム
- データ圧縮の最適化
教育：
- 組合せ数学と語組合せ論の高度なコース
- 連分数理論の応用例
- 自由群理論の具体例
学際的応用：
- 数論における連分数展開
- 離散幾何における直線の離散化
- 二次形式理論

技術的ハイライトの要約

核心的な数学的ツール

Continuant多項式： $K(n_1, \ldots, n_k) = K_{k-1}(n_1, \ldots, n_{k-1})n_k + K_{k-2}(n_1, \ldots, n_{k-2})$ 再帰的定義と連分数を結びつける
自己準同型の合成： $M(\pi(i,j)) = P(i+j) = \begin{pmatrix} i+j & 1 \\ 1 & 0 \end{pmatrix}$ abelianizationを通じて長さを計算
共役作用素： $C(au) = ua, \quad C^n(w) = \text{循環移位}$ 代数的長さと語の共役を結びつける

主要な不等式

Greedy表現（補題10.2(i)）： $q_{k-1} - 1 < N \leq q_k - 1$

Lazy表現（補題10.2(ii)）： $q_{k-1} + q_{k-2} - 2 < N \leq q_k + q_{k-1} - 2$

これらの不等式は表現の一意性とパラメータ化の完全性を保証する。

参考文献（主要な引用）

Christoffel, E. B. (1875): Observatio arithmetica - 原始的定義
Rauzy, G. (1985): Mots infinis en arithmétique - Rauzy規則
de Luca, A. (1997): Sturmian words: structure, combinatorics - 標準語理論
Epifanio et al. (2007, 2012): On Sturmian graphs - Sturmian図
Frid, A. E. (2018): Sturmian numeration systems - 本論文が推広した結果
Lapointe, M. (2017): Study of Christoffel classes - 周期と正規形
Bugeaud & Laurent (2023): Combinatorial structure of Sturmian words - 無限語版

総合的評価：これは理論的深さが極めて高い純粋数学の論文であり、Christoffel語理論に重要な貢献をしている。Ostrowski パラメータ化の導入により、著者は優雅な統一フレームワークを確立し、共役類の特性付けと境界問題を解決した。論文の主要な価値は理論的革新と複数分野の関連性にあるが、アルゴリズム実装と実際の応用の面ではさらなる拡張の余地がある。組合せ語論および関連分野の研究者にとって、これは必読の重要な文献である。