Additive Bases from Primitive Dyck Words: Regular Underapproximations, Motzkin Coding, and Digit Lifting

想象一下你是一名正试图解决某种非常特定类型的数字谜题的侦探。在数学世界中，有一个分支叫做加法数论，它提出了一个简单但棘手的问题：能否通过将一组特殊的“建筑模块”相加，来构建出某一类集合中的每一个数字？你可以把它想象成一场游戏，你拥有一组有限的乐高积木，而你的目标是用这些积木搭建出所有可能的塔高。有时，你可能只需要两块积木；有时，你可能需要十块。这个游戏的“阶数”（order）是指构建任何一座塔所需要使用的积木的最大数量。

为了玩这个游戏，数学家们使用了一套非常特定的建筑模块。这些模块在写成二进制（计算机语言中的 0 和 1）时，看起来像是完美的对称括号。在数学中，这些被称为 Dyck 单词（Dyck words）。例如，1100 是一个有效的模块，因为如果你把 1 看作“上升”步，把 0 看作“下降”步，路径会上升两次，然后下降两次，且从未跌落到起始线以下。作者们关注的是这些单词的一个特殊子集，称为本原（primitive）模块，它们是那些无法被分解为更小的平衡对的“原子”碎片。这个核心问题是：我们需要将多少个本原模块相加，才能构建出任何一个偶数？

这篇论文通过混合两种不同的数学工具，成为了解决这个谜题的高手之作。作者们发现这些二进制模块与另一种被称为 Motzkin 路径（Motzkin path）的路径有着秘密的关系，这种路径允许上升、下降或保持平坦。通过这种关系，他们可以将问题转化为一种在四进制（base-4）下更容易解决的语言。他们证明了虽然大多数偶数只需寥寥数个模块即可构建，但仍有一小部分顽固的数字很难构建。具体来说，他们发现数字 46 是最难的情况，需要 8 个模块，而其他一些数字则需要 7 个。然而，他们同时也证明了，一旦超过 848，无论数字有多大，你永远不需要超过 6 个模块来构建任何偶数。这是一个关于在浩瀚的数字宇宙中寻找“最坏情况场景”，并证明秩序从何处开始、混沌何时结束的故事。

二进制平衡者的故事

让我们深入这场冒险。由栗山隆之（Takayuki Kuriyama）领导的作者们正在研究一组来自平衡二进制字符串的数字。想象你有一串灯，有些是红色的（1），有些是蓝色的（0）。一个“Dyck 单词”是指红灯和蓝灯数量相等，且如果你从左到右计数，在任何时刻蓝灯的数量都不会超过红灯的数量。这就像一场舞蹈，在匹配完每一次上升步与下降步之前，你不能踏出舞台。

作者们对“本原”舞者感兴趣。这些字符串仅在最后时刻才回到起始线（高度为零）。如果一个字符串在途中就回到了零，那么它只是两个较小的舞蹈拼接在一起，而不是一个本原的舞蹈。他们将这些字符串视为数字（按二进制读取），并询问：我们需要多少个这样的本原数字相加，才能得到任何一个偶数？

秘密代码：从二进制到四进制
这篇论文的神来之笔在于意识到这些二进制字符串具有隐藏的结构。如果将位进行配对（00, 01, 10, 11），它们就像四进制系统中的数字（0, 1, 2, 3）一样运作。作者们发现了一个完美的映射：除了最小的一个（即 2）之外，每个本原 Dyck 数字都对应一个以 3 开头、以 0 结尾，且中间包含一个“Motzkin”单词的四进制数。

把 Motzkin 单词想象成一条路径，它可以上升、下降或保持平坦，但绝不会低于地面。这种联系是这篇论文的“罗塞塔石碑”。它允许作者将一个关于复杂二进制字符串的难题，转化为一个关于四进制数字和这些平坦行走路径的更简洁的问题。这种转换揭示了他们研究的这组数字是“数字封闭”的，这意味着如果你拥有一个属于该集合的数字，你通常可以通过在末尾添加特定数字来生成新的数字。

双轨策略
为了解决这个谜题，作者们采取了巧妙的两路进攻，根据数字在除以 4 时的表现进行分类处理。

1. “简单”轨道（4 的倍数）： 对于可以被 4 整除的数字，作者们使用了一种“常规下近似”（regular underapproximation）。这是一种高级说法，意指他们找到了一个更简单、更可预测的子集，这个子集易于操作。他们证明了这个更简单的集合足以使用仅 6 个模块来构建所有大型的 4 的倍数。
2. “棘手”轨道（2 mod 4 的数字）： 对于除以 4 余 2 的数字（如 6, 10, 14），简单的集合就不够用了。在这里，他们使用了完整的“Motzkin 编码”家族的力量。他们证明了这个更大、更复杂的家族可以利用仅 5 个模块来构建这些数字。

“提升”魔法
他们如何知道这适用于所有大数字，而不只是他们检查过的那些？他们使用了一种叫做数字提升（digit lifting）的技术。想象你有一把可以到达一定高度的小梯子。作者们证明了一个定理：如果你能用一定数量的模块构建出一个连续的数字范围，你就可以通过在模块末尾添加特定数字，将这种能力“提升”到所有更大的数字。这就像有一个神奇的规则说：“如果你能构建一个高度为 100 的塔，你自动就能构建高度为 400, 401, 402 等等的塔。”这使得他们能够将一个有限的已验证数字列表，转化为证明该模式永远成立的证明。

结果：那些顽固的数字
在搭建好工具后，作者们开始对异常情况进行分类。他们发现，虽然大多数偶数都很容易构建，但确实存在一小部分“顽固”的数字需要超过 6 个模块。

• 难度冠军： 数字 46 是最难的。它无法用 7 个或更少的模块构建；它严格要求 8 个。
• 亚军： 还有另外十个数字需要 7 个模块：34, 44, 98, 154, 198, 202, 206, 838, 842, 和 846。
• 阈值： 作者们证明了 848 是那个魔力数字。从 848 及以上的每一个偶数，都可以用 6 个或更少的模块来构建。

他们并非在猜测这些数字；他们使用了精确的计算机计算来验证直到阈值前的每一个案例，并使用他们的数学证明来展示这一规律在无穷远处依然成立。

为什么这很重要
这篇论文是不同数学领域——计算机科学（语言与自动机）、组合数学（路径与树）以及数论（加法）——共舞的优美范例。作者们不仅仅是找到了一组数字；他们建立了一个框架。他们展示了即使对于一个由复杂、非重复模式（“上下文无关”语言）定义的集合，你也可以找到一个简单的、重复的模式（“正则”语言）来覆盖大部分领域，然后利用全部的复杂度来填补空隙。

他们还发现，“阶数”的游戏取决于规则的变化。如果你只看 4 的倍数，你只需要 5 个模块。但如果你把 2 mod 4 的数字也包括进来，需求就会跳升至 6 个。而如果你观察绝对最坏的情况（包括数字 46），你需要 8 个。

最终，这篇论文给了我们一张完整的地图。我们确切地知道哪些数字是麻烦制造者，我们知道麻烦停止的精确界限，并且我们拥有一个构造算法（分步食谱）来构建任何大型偶数。它将一个看似混沌的问题转化为了一个完美有序的系统，证明了即使在抽象数字的世界里，也总有一个等待被发现的模式。