Cloitre's Self-Generating Sequence

基本信息

• 论文ID: 2501.00784
• 标题: Cloitre's Self-Generating Sequence
• 作者: Jeffrey Shallit (University of Waterloo)
• 分类: math.CO cs.DM cs.FL math.NT
• 发表时间: 2025年1月3日
• 论文链接: https://arxiv.org/abs/2501.00784

摘要

2009年，Benoit Cloitre引入了一个特殊的自生成序列 $(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots$，该序列具有这样的性质：第$n$个游程（run）中所有项的和等于序列第$n$项的两倍。本文建立了该序列与纸折叠序列之间的联系，并证明了Cloitre关于序列中数字1密度的猜想。

研究背景与动机

研究问题

本文研究的核心问题是分析Cloitre自生成序列的结构性质，特别是：

1. 该序列与已知数学对象（纸折叠序列）的关系
2. 序列中数字1的渐近密度问题

问题重要性

自生成序列在组合数学中具有重要地位，它们展现了复杂的结构性质，同时与多个数学分支相关联。Cloitre序列的研究具有以下意义：

• 扩展了对自生成序列性质的理解
• 建立了与纸折叠序列等经典序列的新联系
• 为自动机理论在序列分析中的应用提供了新案例

现有研究局限性

现有关于类似序列（如Oldenburger-Kolakoski序列）的研究表明，这类序列的渐近性质往往难以分析。例如，对于Oldenburger-Kolakoski序列，其1的密度是否为1/2仍是未解决的猜想。

研究动机

Cloitre在OEIS条目A157196中提出了关于该序列中1的密度为2/3的猜想，这为本文的研究提供了明确目标。

核心贡献

1. 建立了新的序列联系：首次发现Cloitre自生成序列与正规纸折叠序列之间的深层联系
2. 证明了密度猜想：严格证明了Cloitre关于序列中1的密度为2/3的猜想
3. 提供了精确的界限：证明了$0 \leq 3g_n - 2n \leq 4$，其中$g_n$是前$n$项中1的个数
4. 开发了自动机方法：使用有限自动机和Walnut软件为序列分析提供了计算验证框架
5. 扩展到一般情况：将结果推广到任意纸折叠序列

方法详解

任务定义

研究Cloitre序列$(a_n)_{n\geq 1}$，该序列由以下自生成规则定义：

• 序列在字母表{1,2}上取值
• 以$a_1 = 1$开始
• 第$n$个游程中所有元素的和等于$2a_n$

核心方法架构

1. 序列构造链

论文构造了一系列相互关联的序列：

• 正规纸折叠序列$(p_n)$
• 二元版本$(q_n)$，满足$p_n = (-1)^{q_n}$
• 一阶差分序列$(d_n)$
• 绝对值序列$(d'_n)$
• 游程结束位置$(e'_n)$
• 最终得到$(b_n) = (a_n)$

2. 自动机表示

每个序列都可以用有限自动机表示：

• DFAO（带输出的确定有限自动机）：用于取有限值的序列
• 同步自动机：用于取整数值的序列
• 所有自动机都使用最低有效位优先的二进制表示

3. Walnut验证框架

使用Walnut软件进行形式化验证：

eval q_test "?lsd_2 An (Q[2*n]=Q[n] & Q[4*n+1]=@0 & Q[4*n+3]=@1)":

技术创新点

1. 纸折叠序列连接

创新性地发现了Cloitre序列与纸折叠序列的联系： $q_{2n} = q_n, \quad q_{4n+1} = 0, \quad q_{4n+3} = 1$

2. 猜测-验证策略

对于复杂的序列（如游程结束位置），采用了"猜测自动机然后验证"的策略，这是处理自动序列的有效方法。

3. 多层序列分析

通过构造多个中间序列，将复杂的自生成性质分解为可处理的自动机计算。

实验设置

计算工具

• Walnut软件：用于自动机计算和形式化验证
• 有限自动机：所有序列都通过自动机表示和计算
• OEIS数据库：用于序列验证和对比

验证方法

1. 自动机正确性验证：通过多个条件检验自动机的正确性
2. 递推关系验证：验证序列满足的递推关系
3. 边界条件检查：验证初始条件和特殊情况

实现细节

• 使用最低有效位优先的二进制表示
• 自动机状态数从4到32个不等
• 所有计算都经过Walnut的形式化验证

实验结果

主要定理证明

定理2：设$g_n$为序列$a_1a_2\cdots a_n$中1的个数，则： $0 \leq 3g_n - 2n \leq 4$ 因此$\lim_{n\to\infty} g_n/n = 2/3$。

关键验证结果

1. 序列一致性：验证了$b_n = a_n$，即构造的序列确实是Cloitre序列
2. 自生成性质：验证了$\sigma_n = 2b_n$，其中$\sigma_n$是第$n$个游程的和
3. 游程长度：证明了游程长度只能是1、2或4
4. 密度界限：通过16状态自动机验证了密度界限

额外发现

证明了序列$w_n = \min\{t \geq 1 : e'_t \geq n\}$就是OEIS序列A091960，满足：

• $w_1 = 1$
• $w_{2n} = w_{2n-1} + (w_n \bmod 2)$
• $w_{2n+1} = w_{2n} + 1$

相关工作

主要相关序列

1. Oldenburger-Kolakoski序列：$k := 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, \ldots$
   • 第$n$项等于第$n$个游程的长度
   • 1的密度问题仍未解决
2. Dekking序列：$1, 3, 3, 3, 1, 1, 1, 3, 3, 3, \ldots$
   • 游程长度序列等于序列本身
   • 可通过态射的不动点理解
3. 纸折叠序列：由迭代折纸产生的序列
   • 与二进制表示有深层联系
   • 可用有限自动机计算

本文贡献的独特性

Cloitre序列比Oldenburger-Kolakoski序列更易处理，因为它与二进制表示有微妙但明确的联系，这使得自动机方法特别有效。

结论与讨论

主要结论

1. 密度定理：严格证明了Cloitre序列中1的密度为2/3
2. 结构联系：建立了与纸折叠序列的深层联系
3. 计算框架：展示了自动机方法在序列分析中的强大能力

方法的普适性

论文第7节表明，所有结果都可以推广到任意纸折叠序列，尽管一般情况下没有明显的自生成性质类比。

未来方向

1. 研究其他自生成序列与经典序列的联系
2. 开发更一般的自动机分析框架
3. 探索在其他数学分支中的应用

深度评价

优点

1. 方法创新：将自动机理论与序列分析巧妙结合
2. 严格性：所有结果都通过形式化验证
3. 完整性：不仅证明了主要猜想，还发现了额外的结构性质
4. 可扩展：方法可推广到更广泛的序列类别

技术亮点

1. 猜测-验证策略：为复杂自动序列分析提供了实用方法
2. 多层序列构造：通过中间序列简化了复杂性质的分析
3. 计算验证：Walnut软件的使用确保了结果的可靠性

局限性

1. 计算复杂性：某些自动机状态数较多，可能限制了更复杂序列的分析
2. 猜测依赖：部分自动机需要先猜测再验证，缺乏系统的构造方法
3. 推广限制：虽然可推广到任意纸折叠序列，但失去了自生成性质

影响力

1. 理论贡献：为自生成序列研究提供了新的分析工具
2. 方法论价值：展示了计算机辅助证明在组合数学中的应用
3. 实用性：为OEIS中相关序列的研究提供了模板

适用场景

该方法特别适用于：

• 与二进制表示相关的序列分析
• 具有递推结构的自动序列研究
• 需要精确密度分析的组合序列

参考文献

论文引用了14篇重要文献，涵盖了自动序列理论、纸折叠序列、Kolakoski序列等相关领域的经典工作，为研究提供了坚实的理论基础。