On the conjugates of Christoffel words

基本信息

• 论文ID: 2202.05486
• 标题: On the conjugates of Christoffel words
• 作者: Yann Bugeaud (Université de Strasbourg et CNRS, Institut universitaire de France), Christophe Reutenauer (Université du Québec à Montréal)
• 分类: math.CO (Combinatorics)
• 发表会议/期刊: 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词是由Christoffel在1875年引入的二元字母表上的特殊词类，其共轭是通过循环置换得到的词。

问题重要性

Christoffel词及其共轭在多个数学领域具有重要意义：

1. 自由群理论：它们对应于二生成元自由群中正的、循环约化的且构成基的元素
2. 数据压缩：它们是二字母表上的"完美聚类词"（perfectly clustering words），在Burrows-Wheeler变换理论中出现
3. Sturmian词理论：它们是Sturmian无限词的有限版本，与平面直线的离散化相关
4. 二次型理论：它们编码Markoff二次型及其最小值

现有方法局限性

虽然Christoffel词本身由非负有理数参数化是众所周知的结果，但其共轭类的系统性参数化方法此前并不完善。特别是：

• 缺乏统一的参数化框架来描述所有共轭元
• Christoffel词共轭元的边界（borders）和周期的精确刻画不够完整
• Sturmian图与Ostrowski表示的关系需要更深入的理解

研究动机

本文旨在建立一个基于Ostrowski数制的系统性框架，完整刻画Christoffel词的共轭类，并应用这一框架解决边界问题和Sturmian图的结构问题。

核心贡献

1. 参数化构造：基于整数Ostrowski数制系统，引入了Christoffel词共轭类的完整参数化方法（定理7.3），这是Rauzy规则和标准词构造的推广
2. 非交换提升：证明了Frid关于标准词前缀的结果作为推论（推论7.6），这可视为Ostrowski数制系统的非交换提升
3. 边界刻画：给出了Christoffel词共轭元的最长边界的精确描述（定理8.1），并证明任何边界都是某个Christoffel词共轭元的幂（推论8.2）
4. Sturmian图嵌入：证明了紧致图和Sturmian图自然嵌入到中心词树和Stern-Brocot树中（推论9.5），利用了de Luca的迭代回文化理论
5. 统一框架：建立了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）

主要结果：

1. 所有 $V_m(d_1, \ldots, d_m)$（其中 $0 \leq d_i \leq b_i$）在自由群中共轭于 $M_m = V_m(0, \ldots, 0)$
2. 在词意义下的共轭类恰好是所有满足legal条件的Ostrowski表示对应的词
3. 精确公式：$V_m = C^N(M_m)$，其中 $C$ 是共轭算子，$N = \sum d_i q_{i-1}$

证明思路：

• 利用引理5.1（关于自同构的共轭关系）
• 构造共轭元 $h$ 使得 $V_m = h^{-1} M_m h$
• 计算 $h$ 的代数长度恰为 $N$
• 利用Ostrowski表示的唯一性证明覆盖整个共轭类

技术创新点

1. 统一框架：将Rauzy规则、标准词构造、Ostrowski数制统一在递归定义（11）中
2. 代数方法：利用自由群的共轭理论和态射的abelianization矩阵计算长度
3. 双重表示：
   • 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}$
4. 镜像对称（命题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$ 的路径。

证明要点：

1. 图的确定性：每个顶点最多两条出边，标签首字母不同
2. 路径标签恰对应lazy Ostrowski表示
3. 利用推论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$

这些结果保证了参数化的完备性。

相关工作

历史背景

1. Christoffel (1875) 和 Smith (1876)：独立引入Christoffel词
2. Markoff (1879, 1880)：用于构造二次型，虽然未意识到与Christoffel的联系
3. Frobenius (1913)：明确建立了联系，提出著名的Markoff数猜想

现代理论

1. Rauzy (1985)："Rauzy规则"，标准词构造的基础
2. de Luca & Mignosi (1994, 1997)：标准词理论和迭代回文化
3. Ostrowski (1922)：Ostrowski数制系统
4. Epifanio et al. (2007, 2012)：Sturmian图和lazy表示

本文创新

1. vs Rauzy/de Luca：本文的递归构造（11）是更一般的框架，包含标准词作为特例
2. vs Frid (2018)：本文的推论7.6推广了Frid的结果到整个共轭类
3. vs Lapointe (2017)：本文用完全不同的方法（Ostrowski参数化）重新证明了周期结果
4. vs Epifanio et al.：本文给出了Sturmian图嵌入到树结构的新视角

结论与讨论

主要结论

1. 完整参数化：建立了Christoffel词共轭类与Ostrowski表示的双射关系
2. 边界完全刻画：所有边界都是Christoffel词共轭元的幂，给出了最长边界的显式公式
3. 图论统一：Sturmian图和紧致图自然嵌入到经典的树结构中
4. 理论深化：将组合词论、数论（连分数）、自由群理论、图论统一在一个框架下

局限性

1. 计算复杂性：论文未讨论参数化构造的计算复杂度
2. 推广性：方法局限于二元字母表，更大字母表的推广不明显
3. 应用：虽然理论优美，但实际应用场景的讨论较少
4. 算法实现：缺少具体的算法伪代码和实现细节

未来方向

1. 算法化：开发高效算法计算共轭元和边界
2. 推广：研究更大字母表或无限词的类似理论
3. 应用：探索在数据压缩、模式匹配中的应用
4. 连接：进一步研究与Markoff理论、二次型的深层联系

深度评价

优点

1. 理论深度：
   • 建立了多个数学领域的深刻联系（组合、数论、代数）
   • 证明严谨完整，逻辑清晰
2. 方法创新：
   • Ostrowski参数化是全新视角
   • 递归构造（11）优雅且统一
   • 镜像对称性（命题7.8）揭示了深层结构
3. 结果完整性：
   • 不仅给出存在性，还有唯一性和显式构造
   • 边界定理涵盖所有情况
   • 推广和统一了多个已知结果
4. 写作质量：
   • 结构清晰，从基础定义到高级结果层层递进
   • 引理和定理组织良好
   • 提供了具体示例（第9节）

不足

1. 可读性挑战：
   • 需要较强的组合词论和自由群背景
   • 符号系统复杂（$V_i, M_i, L_i, q_i, b_i$ 等）
   • 定理8.1的七种情况过于繁琐
2. 实验验证：
   • 仅有一个小规模示例
   • 缺少大规模数值验证
   • 未提供代码或计算工具
3. 应用导向：
   • 理论性强但应用讨论不足
   • 未明确说明如何用于实际问题
   • 计算效率未分析
4. 技术细节：
   • 某些证明（如定理8.1）冗长且技术性强
   • 附录的Ostrowski表示证明虽完整但可读性较差

影响力

1. 学术贡献：
   • 为Christoffel词理论提供了新的统一框架
   • 解决了边界刻画这一重要问题
   • 连接了Ostrowski数制与词组合学
2. 潜在应用：
   • 数据压缩算法（Burrows-Wheeler变换）
   • 符号动力系统
   • 数论中的丢番图逼近
3. 可复现性：
   • 理论结果可复现性强
   • 但缺少软件实现限制了实际应用
   • 示例计算可手工验证
4. 后续研究：
   • 为算法研究提供了理论基础
   • 可能启发更大字母表的研究
   • 与Markoff理论的联系值得深入探索

适用场景

1. 理论研究：
   • 组合词论的进一步研究
   • Sturmian词和Christoffel词的性质探索
   • 自由群和自由幺半群理论
2. 算法开发：
   • 字符串匹配和模式识别
   • 周期检测算法
   • 数据压缩优化
3. 教学：
   • 组合数学和词组合学的高级课程
   • 连分数理论的应用示例
   • 自由群理论的具体实例
4. 跨学科应用：
   • 数论中的连分数展开
   • 离散几何中的直线离散化
   • 二次型理论

技术亮点总结

核心数学工具

1. 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})$ 连接了递归定义和连分数
2. 态射复合： $M(\pi(i,j)) = P(i+j) = \begin{pmatrix} i+j & 1 \\ 1 & 0 \end{pmatrix}$ 通过abelianization计算长度
3. 共轭算子： $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$

这些不等式保证了表示的唯一性和参数化的完备性。

参考文献（关键引用）

1. Christoffel, E. B. (1875): Observatio arithmetica - 原始定义
2. Rauzy, G. (1985): Mots infinis en arithmétique - Rauzy规则
3. de Luca, A. (1997): Sturmian words: structure, combinatorics - 标准词理论
4. Epifanio et al. (2007, 2012): On Sturmian graphs - Sturmian图
5. Frid, A. E. (2018): Sturmian numeration systems - 本文推广的结果
6. Lapointe, M. (2017): Study of Christoffel classes - 周期和normal form
7. Bugeaud & Laurent (2023): Combinatorial structure of Sturmian words - 无限词版本

总体评价：这是一篇理论深度极高的纯数学论文，在Christoffel词理论中做出了重要贡献。通过引入Ostrowski参数化，作者建立了一个优雅的统一框架，解决了共轭类刻画和边界问题。论文的主要价值在于理论创新和多领域连接，但在算法实现和实际应用方面还有拓展空间。对于组合词论和相关领域的研究者，这是一篇必读的重要文献。