The Thue-Morse Transform

该论文引入了基于“邪恶数”与“恶毒数”的二进制序列变换（Thue-Morse 变换），证明了其在经典 Thue-Morse 序列上的迭代具有清晰的二进结构，不仅扩展了 Prouhet-Tarry-Escott 问题的解族，还推导了相关广义数的函数方程，并完整确定了梅森层级的因子复杂度，同时提出了$d$-进制及斐波那契数制下的推广形式。

要点

这篇论文介绍了一个名为**“Thue-Morse 变换”（Thue-Morse Transform）的数学魔法。为了让你轻松理解，我们可以把这篇论文想象成是在讲述一个关于“数字积木”和“无限分身”**的故事。

1. 核心概念：什么是“邪恶”与“罪恶”？

在数学世界里，有一串著名的数字序列叫Thue-Morse 序列（你可以把它想象成一种特殊的“黑白交替”模式：0, 1, 1, 0, 1, 0, 0, 1...）。

作者把产生这个序列的位置分成了两类：

• 邪恶数 (Evil Numbers)：序列中数字是 0 的位置。
• 罪恶数 (Odious Numbers)：序列中数字是 1 的位置。

“变换”的魔法是什么？
想象你手里有一串黑白珠子（序列）。

1. 你记录下所有黑色珠子（0）的位置，把它们排成一队。
2. 你记录下所有白色珠子（1）的位置，把它们排成另一队。
3. 然后，你根据这两队新位置的顺序，重新排列出一串新的黑白珠子。

这就叫一次“变换”。如果你把这个新序列再拿去变一次，再变一次……你就得到了一个**“无限分身塔”**。

2. 主要发现：给分身们贴上“面具”

作者最酷的发现是，这个“分身塔”里的每一个序列，其实都有一个非常简单的**“面具公式”**。

• 普通版 (第 0 层)：就是原来的 Thue-Morse 序列。
• 升级版 (第 m 层)：想象每个数字 $n$ 都有一个二进制身份证（比如 5 是 101）。作者发现，第 $m$ 层的序列，只需要看 $n$ 的身份证上，哪些位没有被数字 $m$ 的“面具”挡住，然后把这些没挡住的位加起来（奇偶性），就能直接算出结果。

比喻：
这就好比你在玩一个**“找不同”**的游戏。

• 原来的游戏是：看所有位。
• 现在的游戏是：拿一张带孔的纸（面具 $m$）盖在数字上。孔没盖住的地方（位），你就把它们加起来。如果加起来是奇数，就是 1；是偶数，就是 0。
• 这个“面具”让原本复杂的无限序列，瞬间变得像按开关一样简单明了。

3. 数学界的“完美平衡”：Prouhet-Tarry-Escott 问题

论文里解决了一个古老的数学难题，叫PTE 问题。
简单来说，就是能不能把一堆数字分成两组，让这两组数字的和相等，平方和相等，立方和也相等……一直相等下去？

• 经典做法：以前人们知道怎么分（基于数字之和的奇偶性），但这只能做到一定程度的平衡。
• 本文的突破：作者发现，通过不断使用上面的“变换”和“面具”，可以创造出无数种新的分组方法。
  • 你可以控制“面具”的孔洞数量，来决定这种平衡能维持多深（比如能平衡到 10 次方，或者 100 次方）。
  • 这就像是用同一种乐高积木，通过不同的拼搭指令（面具），能搭出无数种完美对称的城堡。

4. 复杂的“修正”规则

在原来的经典序列里，位置之间的转换规则非常简单（比如：位置 $n$ 变到 $2n$ 或 $2n+1$）。
但在作者创造的“分身塔”里，这个规则变得更有趣了。

• 旧规则：就像走楼梯，一步一个台阶，非常死板。
• 新规则：就像走迷宫，有时候需要“修正”一下。这个“修正”不再是固定的，而是根据你当前所在的层级（面具 $m$）动态变化的。
• 比喻：原来的规则是“直行”，现在的规则是“直行 + 偶尔根据心情转弯”。这种转弯的规律本身也是一个自动生成的序列，非常精妙。

5. 超越二进制：从 2 进制到 10 进制，甚至“斐波那契”

作者并没有止步于此，他们把这个魔法推广了：

• 多进制版：不仅限于 0 和 1，这个变换可以应用到 3 进制、4 进制甚至 10 进制的世界里。
• 斐波那契版：他们尝试把这个魔法用在了“斐波那契数列”（1, 1, 2, 3, 5, 8...）的计数系统上。虽然这里没有像二进制那样完美的“面具公式”，但也发现了一些有趣的平衡规律，就像在另一个平行宇宙里发现了类似的魔法。

6. 总结：这篇论文在说什么？

用一句话概括：
作者发明了一个新的数学“复印机”（变换），把经典的 Thue-Morse 序列无限复制并改造。他们发现这些复制品都有极其简单的“生成密码”（面具公式），并且这些复制品能解决极其复杂的“数字平衡”难题，甚至还能推广到其他数字系统。

给普通人的启示：
这就像是你发现了一个简单的**“折叠纸”技巧**。

1. 你有一张普通的纸（经典序列）。
2. 你发明了一种折叠方法（变换），折叠一次，纸的纹理变了。
3. 你发现，无论折叠多少次，纸的纹理都遵循一个极其简单的**“折痕规律”**（面具公式）。
4. 更神奇的是，用这些折叠后的纸，可以完美地拼出各种对称的图案（解决 PTE 问题），甚至这种折叠法还能用在不同材质的纸上（多进制和斐波那契）。

这篇论文不仅给出了具体的公式，还展示了数学中**“简单规则产生复杂结构”**的极致美感。

技术摘要

这是一份关于 Benoît Cloitre 论文《Thue–Morse 变换》（The Thue–Morse Transform）的详细技术总结。

1. 研究问题与背景

本文的核心研究对象是一个定义在二进制序列上的算子，称为Thue–Morse 变换（TM 变换）。

• 背景：经典的 Prouhet–Tarry–Escott (PTE) 问题寻求将整数集划分为若干子集，使得各子集的前 $k$ 次幂和相等。经典的二进制 Prouhet 构造利用 Thue–Morse 序列（$t(n) = s_2(n) \mod 2$，即 $n$ 的二进制数位和的奇偶性）将区间 $\{0, \dots, 2^L-1\}$ 划分为“邪恶数”（evil numbers，$t(n)=0$）和“凶恶数”（odious numbers，$t(n)=1$），从而得到幂和相等的解。
• 问题：如果将 Thue–Morse 变换迭代应用，会生成什么样的序列族？这些迭代序列是否保留了 PTE 问题的解结构？它们对应的广义“邪恶数”和“凶恶数”具有怎样的算术性质？此外，这些序列的因子复杂度（factor complexity）如何？

2. 方法论

作者定义了一个递归算子 $T$，作用于满足特定条件（以 01 开头且 0 和 1 均无限次出现）的二进制序列 $\sigma$：

• 定义：设 $v_\sigma(n)$ 为 $\sigma$ 中 0 的位置序列（广义邪恶数），$u_\sigma(n)$ 为 1 的位置序列（广义凶恶数）。变换 $T(\sigma) = \tau$ 定义为：
  $$\tau(v_\sigma(n)) = \tau(n), \quad \tau(u_\sigma(n)) = 1 - \tau(n), \quad \tau(0) = 0$$
• 迭代塔：从经典 Thue–Morse 序列 $a_0 = t$ 开始，定义 $a_{m+1} = T(a_m)$，形成一个序列塔。
• 核心工具：
  • 位掩码公式（Bit-mask formula）：利用二进制展开和按位运算（XOR, AND）推导序列的闭式表达。
  • 生成函数：推广 Borwein 和 Ingalls 的方法，利用生成函数在 $x=1$ 处的零点阶数来证明幂和相等性。
  • 去替换论证（Desubstitution）：通过分析导出的差分序列（derived sequence）来研究因子复杂度。
  • 自动序列理论：利用 $k$-自动序列的性质分析序列的结构和复杂度。

3. 主要贡献与结果

(1) 迭代序列塔的显式闭式表达

作者证明了第 $m$ 次迭代的序列 $a_m(n)$ 具有极其简洁的显式公式：
$$a_m(n) = \bigoplus_{p \ge 0, \, p \ \& \ m = 0} b_p(n)$$
其中 $b_p(n)$ 是 $n$ 的第 $p$ 个二进制位，$\oplus$ 是异或运算，$\&$ 是按位与运算。

• 意义：$a_m(n)$ 的值取决于 $n$ 的二进制位中，那些位置索引 $p$ 与掩码 $m$ 的按位与为 0 的位的奇偶性。这揭示了迭代变换本质上是对二进制位位置的选择性过滤。

(2) 广义 Prouhet–Tarry–Escott (PTE) 解

• 结果：对于每个层级 $m$ 和长度参数 $L$，序列 $a_m$ 在区间 $[0, N)$ 上诱导的划分（$a_m(n)=0$ 和 $a_m(n)=1$）满足幂和相等，直到次数 $D = s_m L - 1$。
• 参数：$s_m$ 是掩码 $m$ 在一个周期内选中的位位置数量。
• 推广：
  • 通过交叉多个层级（multi-level），可以构造 $2^k$ 类的 PTE 划分。
  • 该构造可以推广到 $d$ 进制（$d$-ary），结合 Prouhet 的原始思想和位掩码机制。

(3) 广义邪恶数与凶恶数的复合恒等式

作者研究了广义邪恶数 $v_m(n)$ 和凶恶数 $u_m(n)$ 的复合性质（如 $u_m(u_m(n))$）。

• 经典情况：当 $m=0$ 时，复合公式中的修正项是常数（0 或 1）。
• 新发现：当 $m > 0$ 时，修正项不再是常数，而是非平凡的自动序列（automatic sequences），记为 $c_m(n)$。
• 公式：例如，当 $m$ 为奇数时，$u_m(u_m(n)) = 2u_m(n) + 1 - c_m(n)$。
• 结构：修正集 $C(m)$ 是原始掩码集合 $S(m)$ 的循环移位。这揭示了迭代变换在算术结构上的丰富性。

(4) 因子复杂度（Factor Complexity）

针对梅森数层级（Mersenne levels，即 $m = 2^k - 1$），作者完全确定了序列 $a_m$ 的因子复杂度 $p_{a_m}(n)$（即长度为 $n$ 的不同子串数量）。

• 初始线性区：在 $1 \le n \le B+1$ 范围内（$B$ 为特定周期），复杂度为 $p(n) = 2n$。
• 分段公式：利用去替换论证，推导出了完整的分段线性公式。复杂度呈现“增长相”和“平台相”交替的层级结构。
• 非梅森数层级：对于非梅森数层级，复杂度行为更为复杂，目前尚未给出完全闭式解，但观察到初始线性区的长度受 $B(m)$ 控制。

(5) 超越经典 Thue–Morse 种子

• Meta-Thue–Morse 序列：展示了该变换机制同样适用于 Campbell 和 Cloitre 提出的 Meta-Thue–Morse 序列 $M_2$，证明了该框架的普适性。
• 斐波那契类比：探讨了基于 Zeckendorf 表示（斐波那契进制）的斐波那契-Thue–Morse 序列。虽然在该设置下无法得到完美的 PTE 解（存在非零的幂和缺陷），但缺陷项具有明确的斐波那契多项式形式。

4. 意义与影响

1. 统一框架：本文建立了一个统一的框架，将 Thue–Morse 序列的迭代、PTE 问题的构造、自动序列的复合性质以及因子复杂度研究联系在一起。
2. PTE 问题的新解：提供了一种通过位掩码参数控制 PTE 解次数的新方法，不仅限于经典的 $L-1$ 次，而是可以扩展到 $s_m L - 1$ 次，并能生成多类划分。
3. 算术结构的深化：揭示了迭代变换产生的修正项从“常数”变为“自动序列”的深刻转变，丰富了自动序列理论中的复合恒等式研究。
4. 开放问题：提出了 $d$ 进制下的复合理论、非梅森数层级的复杂度公式以及更广泛的自动序列种子（如 Sturmian 序列）的变换轨道等开放问题，为后续研究指明了方向。

5. 总结

Benoît Cloitre 的这篇论文通过定义 Thue–Morse 变换，构建了一个具有清晰算术结构的序列塔。该塔不仅提供了 PTE 问题的一系列新解，还展示了迭代过程中自动序列性质的演变（从常数修正到自动修正）。文章通过显式的位掩码公式、生成函数分析和组合论证，系统地解决了该序列族的 PTE 性质、复合恒等式及复杂度问题，并成功将其推广到 $d$ 进制和非二进制（如斐波那契）场景，是组合数论和自动序列领域的重要进展。