← 返回 PaperDaily
大模型与智能体
滑铁卢大学算出重复规避门槛：3字母最长84，4字母直通无限
重复规避是组合词学的经典问题，但这篇把"词本身"和"卷曲数变换"的重复规避同时拎出来，用自动机定理证明器Walnut和穷举搜索硬生生算出了字母表门槛：三字母最长84，四字母直接无限。门槛是4，不多不少。极致的离散数学美感，值得一读。
龙哥读论文
发布于 2026-08-19 00:20:22
阅读 3
查看原文
原论文信息如下：
写东西写着写着就重复了，这大概是每个文案的噩梦。但"重复"这件事，在数学家眼里不是玄学，而是一套精确的度量体系。一个单词里有没有隐藏的连续重复？能撑多长不重复？如果再加一个苛刻条件——把每个前缀的"卷曲数"记下来形成新序列，这个新序列也必须不重复——那这个游戏还能玩多久？
滑铁卢大学的 Jeffrey Shallit 团队（合作者还有 Geofrey Caveney 和 Haoxuan Dong）最近在 arXiv 上挂出一篇论文《Repetition Avoidance in Curling-Number Transforms》，把一个看起来很小、实则极其精巧的组合学问题推到了边界：如果我们同时要求一个单词和它的"卷曲数变换"都不含重叠，那么字母表到底需要多大？答案是 4。三字母最多撑到长度 84，四字母直接突破到无限。
卷曲数变换：一个被忽视的重复避免新战场 先来认识一下"卷曲数"（curling number）到底是个啥。给定一个有限单词 x，它的卷曲数是最大的整数 k，使得 x 可以写成 yz^k 的形式，其中 z 是非空单词，y 是前缀。说白了，就是看这个单词的末尾能"卷"多少次尾巴。比如 brouhaha 这个单词，末尾 haha 是 ha 的两遍，所以它的卷曲数是 2。看起来平平无奇，对吧？
卷曲数的妙处在于，它可以对单词的每一个前缀都算一遍。把第 i 个前缀的卷曲数记下来，拼成一串新的数字序列，这就是"卷曲数变换" C(x)。比如某个单词的前缀依次算出来是 1、2、1、2，那变换就是 1212。van de Bult 等人在 2007 年研究过这个变换，发现它产生的序列增长极其缓慢，还和著名的 Gijswijt 序列有关系。不过这次龙哥要讲的，不是它的增长速度，而是另一个更刁钻的视角：重复避免。
追追剧的朋友都知道，追剧最怕的就是剧情套路重复。单词也一样，连续重复的片段被称为"方"（square）或"立方"（cube）。比如 murmur 是 square，因为它是 mur 的两次重复；shshsh 是 cube，因为是 sh 的三次重复。还有一种更隐蔽的重复叫"重叠"（overlap），形如 axaxa，a 是单个字母，x 是任意单词，比如 alfalfa。无重叠（overlap-free）是比无平方更弱的条件，但依然很严格。
经典结果里，挪威数学家 Axel Thue 早在 1912 年就构造了无限长的无重叠单词：著名的 Thue-Morse 序列 0110100110010110... 就是无重叠的。但本篇论文玩的不是单机版，而是双人版——不仅单词本身不能有重叠，它的卷曲数变换也必须无重叠。这就好比要求一个作家不仅正文不灌水，连每个章节的字数统计序列也不能有重复模式。于是问题来了：在多大的字母表上，才能同时满足这两个条件、并且能无限玩下去？
要理解这个问题的难度，可以先想想为什么"自身无重叠"和"变换无重叠"是两个独立的约束。一个单词自身无重叠，只约束了单词内部的因子结构；而变换无重叠，则要求每个前缀的卷曲数序列本身也不含重叠。卷曲数的计算依赖于单词的"尾部重复"结构，这意味着变换的每个字符都携带了单词某个前缀的全局信息。因此，这两个约束之间没有简单的蕴含关系——一个满足自身无重叠的单词，其变换完全可能包含重叠；反之亦然。正是这种"双重约束"的交互作用，使得问题变得异常复杂。
论文还引入了一个重要的概念区分：α-free 与 α⁺-free。α-free 是指单词中不存在指数至少为 α 的因子，也就是说允许出现等于 α 的指数但不可以超过；α⁺-free 则更严格地不允许任何指数严格大于 α 的因子，但允许指数恰好等于 α。这个看似细微的差别，在论文中反复出现，并且直接决定了有限与无限的分界。比如在二元字母表上，要求源单词无立方（3-free）且变换无立方，最大长度只有 17；但如果只要求无 3⁺（即指数不超过 3），立即出现无限构造。一个"等于"与"严格大于"的差别，就造成了有限与无限的天壤之别。
从Thue-Morse到无限构造：态射设计的艺术 怎么构造无限长的、同时满足"自身无重叠且变换无重叠"的单词？直接硬写肯定不行，需要系统性的方法。这篇论文的做法非常优雅：从 Thue-Morse 序列出发，先做一个"2 块编码"，把相邻两位映射成一个新符号，得到一个四字母序列 p，然后寻找合适的均匀态射 h，把 p 映射成目标单词 Q = h(p)。
这里先解释一下"均匀态射"。态射就是把每个输入字母替换成一个固定长度的输出字符串。如果所有替换的长度都一样，就叫均匀态射。比如 h(0)=01110、h(1)=00101，每个输出长度都是 5，这就是一个均匀态射。把态射反复应用到初始字母上，就能得到无限长的单词。这种由"有限规则迭代生成无限结构"的思路，在整个数学和计算机科学里到处都是——分形、L-系统、自动机，本质上都是这一套。
但问题来了：态射千千万，怎么找到合适的那个？论文的策略是用广度优先搜索（BFS）自动生成候选态射的图像，从外向内扩展，然后用 Walnut 自动定理证明器逐个验证。Walnut 是滑铁卢大学团队开发的工具，专门用来验证自动序列的一阶逻辑性质。打个比方，Walnut 就像一个数学版的静态分析器，你告诉它"这个序列不应该有重叠"，它就能自动构造证明或反驳。
在 Walnut 的验证脚本里，几个核心谓词起着关键作用：has2 和 has3 用来检测前缀是否以平方或立方结尾；cn1、cn2、cn3 用来定义卷曲数变换的输出值；checkoverlap 用来验证变换是否无重叠。整个验证过程是自动化的，但背后需要研究者精心设计态射和谓词逻辑。这种"人类设计框架，机器验证细节"的协作模式，在近年来的组合数学研究中越来越常见。
论文的附录里给出了五组态射的完整 Walnut 验证脚本。比如四字母情形的核心态射 h5：h5(0)=1001200122322300，h5(1)=1001200122003220，h5(2)=0313110021100200，h5(3)=0313112202203003。最终要验证的单词是 w = 00 h5(p)。这个"00"前缀不是随便加的，它负责调整卷曲数变换的相位，让变换恰好等于从第 3 位开始的 Thue-Morse 序列的一个双射编码。这种细节设计，味道很像调试程序时修一个 off-by-one 错误——只不过这里的"程序"是数学对象。
态射设计的过程本身也值得多说几句。论文提到，候选态射并不是凭空产生的，而是通过一个"图像扩展"的迭代过程逐步构建的。研究者先确定一个较小的种子片段，然后通过 BFS 不断尝试在两端添加字符，同时检查局部约束是否满足。每一步扩展都会产生多个候选，但大部分会在后续验证中被淘汰。最终保留下来的态射，往往具有某种"对称性"或"自相似性"——比如 h5 的四个映射长度都是 16，且内部结构呈现出明显的块状重复。这种设计思路，本质上是一种"约束满足 + 启发式搜索"的组合优化过程。
穷举搜索定边界：二元与三元的有限最大长度 无限构造解决了"存在性"问题，那么另一个方向的"不存在性"呢？在二元和三元字母表上，某些约束组合下，满足条件的单词长度是有限的。为了精确找到这个极限，论文采用了穷举广度优先搜索（BFS）：从空单词开始，逐层扩展，保留所有满足约束的单词，直到某一层没有任何合法扩展。
这个搜索之所以能做到完备，是因为"合法性"是前缀继承的：一旦源单词出现了违规因子，所有后续扩展都违规；变换也一样，因为 C(u) 是 C(uv) 的前缀。所以每个长度为 n+1 的合法单词一定是从某个长度为 n 的合法单词扩展而来。搜索可以无遗漏地遍历所有可能。
论文系统地给出了二元和三元字母表上的六个有限最大长度结果，以及对应的无限构造边界条件。下面这张表总结了所有结果，可以清楚地看到 α-free 和 α⁺-free 之间的微妙差异如何决定了有限与无限的分界：
二元字母表上的结果很有意思。定理2说，同时要求无立方、且变换也无立方的二元单词，最长只有 17。去掉"源单词无立方"的限制、只要求无 3⁺（即指数不超过 3）时，立即出现无限构造（定理3）。但这还不够过瘾：如果要求源单词无立方、只放宽变换到无重叠，最大长度是 13（定理4）。这里二元字母表就出现了"放宽一点点就无限、收紧一点点就卡死"的临界现象。
三元字母表的中心结果当然是定理7：同时要求源单词和变换都无重叠，最长长度是 84。穷举搜索发现长度为 84 的合法单词共有 6048 个，长度 85 的为零。这 6048 个单词可以按首字母分成三类，每类 2016 个，关于三个字母的置换对称。论文给出了其中一个 84 长度的例子，它的变换是一个由 1 和 2 组成的 63 位序列，也是无重叠的。
更令人惊讶的是，三元字母表上另外两个"单侧放松"的边界也是 84。定理9说，把源单词从无重叠放松到 (9/4)-free，变换仍要求无重叠，最大长度还是 84。定理11说，源单词保持无重叠，变换放松到 (7/3)-free，最大长度依然还是 84！三个不同约束组合指向同一个数字 84，这绝不是巧合，而是说明 84 这个长度背后有一个更深层的结构性原因在起作用。当 α 取 α⁺ 时，却有无限构造——严格与非严格一字之差，有限与无限天壤之别。
为什么三个不同的约束组合都恰好卡在 84？论文作者在讨论部分提出了一种可能的解释：三元字母表上，任何长度超过 84 的单词，其前缀的卷曲数序列必然会出现某种"结构性重复"，而这种重复与源单词自身的重复约束形成了不可调和的矛盾。换句话说，84 可能是三元字母表上"信息容量"的一个内在极限——超过这个长度，源单词的局部结构和变换的全局结构就无法再保持兼容。当然，这只是一个启发性的解释，严格的证明仍然是一个开放问题。
四字母突破：同时重叠自由的无限解 三字母卡在 84，四字母就能无限？这个跨越看似魔幻，但构造其实非常优美。论文采用的核心态射 h5 作用在序列 p 上，再在最前面加上两个 0，得到单词 w = 00h5(p)。加上 00 前缀本质上是为了把卷曲数变换整体平移，从而暴露出它和 Thue-Morse 序列的深层联系。
判定这个构造有效的核心有几步。首先，Walnut 验证 w 是无重叠的。然后利用前面提到的性质，将 C(w) 的计算简化为平方后缀检测。最后 Walnut 验证了一个更加惊人的等式：
这个结果展示了一个极为罕见的数学巧合：一个看似复杂的四字母无限单词，它的卷曲数变换居然能精确地落到 Thue-Morse 序列上。这也解释了为什么四个字母就足够了——因为 Thue-Morse 序列本身的结构被完整地编码进了变换里。
至此，论文的主定理（定理12 + 推论13）呼之欲出：四字母是存在"自身和卷曲数变换同时无重叠"的无限单词的最小字母表。三字母最长 84，四字母直接突破到无限——这个门槛不多不少，正好是 4。
值得注意的是，四字母的无限构造并不是唯一的。论文在附录中给出了五组不同的态射，每一组都能生成满足条件的无限单词。这些态射之间有着微妙的联系——有些是彼此的"镜像"或"旋转"，有些则结构差异较大。这种多样性暗示着四字母字母表上的解空间可能非常丰富，而论文只是探索了其中的一小部分。这也为后续研究留下了有趣的问题：四字母字母表上，满足条件的无限单词到底有多少"本质不同"的构造？
Walnut验证与计算可复现性：严谨性的典范 说到 Walnut，值得展开讲讲。这是由滑铁卢大学的 Hamoon Mousavi 在 Jeffrey Shallit 指导下开发的自动定理证明器，专门处理自动序列的一阶逻辑性质。它的工作方式很神奇：给定一个用自动序列定义的结构和一则一阶逻辑公式，Walnut 能自动构造一个验证公式的自动机，而自动机的空性判定是计算可判定的。换言之，对于自动序列来说，"这个序列是否满足某个逻辑性质"这个问题，在理论上是可以机械回答的。
但 Walnut 并不是黑盒魔法。它的验证结果依赖于研究者正确地把数学性质翻译成一阶逻辑公式。例如，验证"无重叠"需要表达成：不存在位置 i 和长度 n≥1，使得对所有的 t≤n 都有 x[i+t] = x[i+t+n]。这个公式在 Walnut 里用一行谓词就写清楚了。为了处理分数指数，论文采用了周期比较的方法：要排除指数大于 α 的因子，只需比较相隔一定距离的位置。
这种自动验证的可靠性，在论文中还得到了交叉验证：两位作者分别用 APL 和 Python 独立实现了穷举搜索，结果完全一致；另外还提供了一个独立的 C++17 程序 bfs_verify.cpp，可以复现所有六个有限最大长度结果。如此严谨的多重验证，在计算机辅助数学证明中堪称典范。论文还附上了 SHA-256 校验和，确保读者下载的补充材料没有被篡改。
这种"机器证明 + 独立复现"的做法越发成为组合数学研究的新标配。论文里的声明也提到了 GPT-5.6 模型参与了构造搜索和脚本调试，但作者保留了最终数学责任的审查。这说明在未来的数学研究中，人类提出框架与方向、AI 负责大规模搜索和证明验证的协作模式，已经实实在在地落地了。
Walnut 的验证过程本身也值得一提。论文中提到的最大中间自动机约有 146 万状态，这在 Walnut 的应用中属于中等规模。验证过程在普通 PC 上即可完成，运行时间从几分钟到几十分钟不等。这种计算成本对于数学研究来说是非常友好的——不需要超级计算机，也不需要分布式计算集群，一台普通的笔记本电脑就足够了。这也意味着，任何有兴趣的读者都可以轻松地复现论文中的全部验证过程。
龙迷三问 这篇论文到底在解决什么问题？ 滑铁卢大学团队研究“词与卷曲数变换同时避免重复”的极限：三字母字母表上最长只有84，四字母上存在无限构造。本文用Thue-Morse态射构造与Walnut验证，确定了最小字母表门槛为4。这篇工作最值得看的点是什么？ 论文通过穷举搜索精确确定了二元、三元字母表下各边界情况的有限最大长度（如二元cubefree+cubefree最大长度17，三元overlap-free+overlap-free最大长度84），并构造了四字母表上的无限例子，结果完整且自洽。这篇工作的边界或风险在哪里？ 优点：理论结果精确且完整，给出了字母表大小的精确阈值（4），方法结合了自动定理证明与穷举搜索，验证严谨；缺点：缺乏直观的构造解释，对非专业读者门槛较高，且结果局限于特定重复避免条件。如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★☆
首次系统研究"单词与卷曲数变换同时避免重复"的边界问题，给出精确字母表门槛。核心思路不算开创性，但问题切入角度新颖，结果本身很有冲击力。实验合理度： ★★★★☆
无限构造用 Walnut 验证、有限边界用穷举搜索，且三种独立实现互相印证。验证方法完备可靠，但缺少对构造生成过程的系统化解释。学术研究价值： ★★★★☆
给出了组合词学中一个全新的阈值结果，推动了对"重复避免+变换"这一复合结构的理解，给后续研究者留下了边界情况等开放问题。稳定性： ★★★★☆
结果都是精确定理，不依赖近似或概率，理论上绝对稳定。四个无限构造均有完整的 Walnut 证明脚本，可在机器上复现验证。适应性以及泛化能力： ★★★☆☆
方法（态射+Walnut验证+穷举搜索）可以推广到其他重复避免问题，但需要针对具体约束重新设计态射和逻辑公式，泛化成本不低。硬件需求及成本： ★★★★☆
Walnut 验证和有限搜索在普通 PC 上即可运行（最大中间自动机约 146 万状态，属中等规模），C++17 编译后运行时间预计在几分钟到几十分钟。复现难度： ★★★★☆
论文提供了 Walnut 脚本、C++17 验证程序、APL/Python 独立实现和 SHA-256 校验和。所有数据和代码齐全，复现门槛较低。产品化成熟度： ★★☆☆☆
这是纯数学理论结果，不直接面向产品落地。但 Walnut 自动定理证明的工作流对形式化验证、程序分析等方向有潜在的方法论借鉴意义。可能的问题： 态射的发现过程依赖 AI 辅助搜索，论文对搜索策略的描述不够细化；三个三元边界同样都是 84 这个现象未能给出解释；缺少对构造规则为何如此设计的理论直觉说明。
主要参考文献
[1] F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane, and A. R. Wilks, A slow-growing sequence defined by an unusual recurrence, J. Integer Sequences 10 (2007), Article #07.1.2. [2] B. Chafin, J. P. Linderman, N. J. A. Sloane and A. Wilks, On curling numbers of integer sequences, J. Integer Sequences 16 (2013), Article #13.4.3. [3] H. Mousavi. Automatic theorem proving in Walnut. ArXiv preprint arXiv:1603.06017 [cs.FL] (2016), https://arxiv.org/abs/1603.06017. [4] J. Shallit, The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut, Vol. 482 of London Math. Soc. Lecture Note Series, Cambridge University Press, 2024. [5] N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences (2026). Online resource, available at https://oeis.org. [6] A. Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1–67. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
写词也讲究"不重复自己"，卷曲数变换给重复划了条精确的线。想和龙哥一起读更多有意思的算法/数学论文？
扫描下方二维码或者添加龙哥助手微信号加群 ：kangjinlonghelper。
一定要备注：研究方向+地点+学校/公司+昵称（如 图像处理+上海+清华+龙哥） ，根据格式备注，可更快被通过且邀请进群。
『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群
