🔢 mathematics

Carryless Pairing: Additive Pairing in the Fibonacci Basis

本文提出了一种从 $\mathbb{N}^2$ 到 $\mathbb{N}$ 的无进位单射配对映射，该映射将两个数编码为由分隔符隔开的互不相交的齐肯多夫索引带，从而仅通过加法支持操作（无需乘法或分解）即可实现求值与逆运算，其核心正确性已在Rocq中得到验证。

原作者： Milan Rosko

发布于 2026-05-12

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Milan Rosko

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是论文《斐波那契基中的无进位配对》的通俗解释，辅以日常类比。

核心思想：在不破坏的情况下打包两个盒子

想象你有两个乐高积木盒，分别标记为X 盒和Y 盒。你想把它们粘合成一个巨大的结构，以便作为一个整体携带，但你也希望以后能不用任何胶水、胶带或特殊工具将它们重新分开。

大多数组合数字的方法（如标准数学或计算机代码）就像使用胶水。为了日后将它们分开，你通常需要进行复杂的计算、分解数字，或者“进位”（就像普通加法中 $9 + 1 = 10$ ，其中的 1“进位”到下一列）。这篇论文提出了一种新的数字组合方法，它不需要任何胶水，也不需要任何进位。

背景：斐波那契“乐高套装”

要理解这是如何运作的，我们需要改变构建数字的规则。这篇论文不使用标准的十进制系统（个位、十位、百位），而是使用斐波那契数列（$1, 2, 3, 5, 8, 13, 21...$）。

在这个系统中，每个数字都有一个特殊的“乐高蓝图”，称为泽肯多夫表示法（Zeckendorf representation）。这个蓝图的黄金法则是：你绝不能使用两个连续的斐波那契数。

错误示例： $5 + 3$ （因为 5 和 3 在数列中是相邻的）。
正确示例： $5 + 2$ （因为 5 和 2 之间有间隔）。

这个“不连续”规则是使整个技巧成为可能的秘密所在。

魔法技巧：“偶数”与“奇数”区域

作者米兰·罗斯科（Milan Rosko）发明了一种方法，通过将 X 盒和 Y 盒放入斐波那契数列中不同的“街区”，将它们打包进一个单一的数字中。

偶数街区（X 盒）：
论文取数字X的蓝图，将其所有乐高积木块移动到斐波那契数列中的偶数位置。
- 类比： 想象 X 是一套书。我们将它们全部放在图书馆的偶数号书架上。
分隔符（围栏）：
在放入 Y 盒之前，我们需要知道 X 延伸到了多远。论文根据 X 的大小计算一个“围栏”或分隔符。我们将这个围栏称为B。
- 类比： 如果 X 占据了第 2 到第 10 号书架，那么围栏就建在第 12 号书架处。
奇数街区（Y 盒）：
现在，我们取数字Y的蓝图，将其乐高积木块移动到奇数位置，但仅从围栏（B）之后开始。
- 类比： 我们将 Y 的所有书放在奇数号书架上，但仅限于第 13、15、17 号等书架。围栏之前的奇数书架保持空置。

为什么它是“无进位”的（最精彩的部分）

在普通数学中，如果你将两个数字相加，可能会产生“进位”（例如 $5+5=10$ ）。在这个斐波那契系统中，如果你相加的两个数字不共享任何“连续”的位置，就不会发生进位。

因为论文将 X 放在偶数位置，将 Y 放在奇数位置（中间有间隔），这两组乐高积木永远不会接触。

X 在偶数位置。
Y 在奇数位置（远离 X）。
最终混合结果中不存在两个连续的数字。

结果： 组合后的数字已经处于其完美的“标准”形式。你不需要进行任何清理或数学运算来修正它。这就像将两块互不接触的拼图拼在一起；它们完美契合。

如何 unpack（解码）

要取回原始的盒子，你只需查看组合后的数字，并提出两个简单的问题：

谁在偶数书架上？（那是 X）。
谁在围栏之后的奇数书架上？（那是 Y）。

因为规则非常严格（不接触、特定间隔），所以不会产生混淆。你总能确切地分辨出哪块积木属于 X，哪块属于 Y。

重要限制（“非满射”部分）

论文承认，这种方法并不能为每一个可能的数字生成代码。

类比： 想象一个停车场，汽车（数字）只能停在特定的位置。如果你试图将车停在一个违反“不接触”规则或“围栏”规则的位置，那个位置就是空的。
论文称这种方法为单射但非满射。
- 单射： 每一对 (X, Y) 都会获得一个唯一的代码。没有两对会产生相同的数字。
- 非满射： 世界上有些数字无法通过这种方法形成。如果你随机选择一个数字，它可能不是一个有效的“打包”对。

然而，论文提供了一个简单的测试：如果你尝试解包一个数字，然后重新打包它，并得到了完全相同的数字，那么它就是一个有效的对。如果数字发生了变化，那么它从一开始就不是一个有效的对。

这为什么重要？（“为什么”）

作者并不是想为你的手机制造一个更快的计算器。其动机更深，根植于逻辑和数学基础：

纯加法： 大多数组合数字的方法都依赖于乘法或复杂的除法（如将数字分解为质因数）。这种方法仅依赖于加法和位置检查。
弱数学系统： 在某些非常基础的逻辑系统中（不允许使用乘法），你无法证明可以将两个数字组合并再取回。这篇论文展示了一种仅使用简单加法来实现这一目标的方法，这有助于数学家理解逻辑运作所需的绝对最低要求。
证明检查： 由于该过程非常简单（仅查看位置和相加），计算机非常容易验证数学的正确性而不会感到困惑。

一句话总结

这篇论文介绍了一种利用斐波那契数列将两个数字组合成一个数字的巧妙方法，其中两个数字生活在相互分离、互不接触的“区域”中，因此它们可以相加而无需任何复杂的数学运算，并且只需查看它们所在的位置即可将它们分开。

技术摘要：斐波那契基下的无进位配对

问题陈述
本文探讨构建一个配对函数 $\pi: \mathbb{N}^2 \to \mathbb{N}$ ，该函数严格在齐肯多夫（Zeckendorf，即斐波那契）基的加法约束下运行。传统的配对方案通常依赖于位置数字交错（如 Z 序/莫顿码）或涉及乘法与素因数分解的算术运算（如哥德尔编号、康托尔配对）。作者寻求一种机制，使得对数对 $(x, y)$ 的编码和解码仅依赖于支撑集提取和加法运算，避免乘法、指数运算，以及在数据组合过程中所需的“进位”传播或归一化步骤。这一动机源于支持弱算术基底（如 $I\Delta_0$ ）中的不完全性论证和证明论研究的愿望，在这些基底中，乘法未被假设或代价高昂。

方法论
所提出的解决方案称为无进位配对（ $\pi_{CL}$ ），它基于齐肯多夫支撑集，将两个自然数编码到不相交的斐波那契索引“带”中。

齐肯多夫表示：每个自然数 $n$ 被唯一表示为非连续斐波那契数 $F_k$ （其中 $k \ge 2$ ）之和。索引集合记为 $Z(n)$ 。
分隔符构建：对于数对 $(x, y)$ ，算法首先计算秩 $r(x)$ ，定义为满足 $F_{r(x)} > x$ 的最小索引。分隔符 $B(x)$ 设为 $2r(x)$ 。
带分离：
- 偶带（用于 $x$ ）： $x$ 的支撑集索引 $Z(x)$ 通过 $e \mapsto 2e$ 映射到偶数索引。这些索引被放置在范围 $[4, 2r(x))$ 内。
- 奇带（用于 $y$ ）： $y$ 的支撑集索引 $Z(y)$ 通过 $j \mapsto B(x) + (2j - 1)$ 映射到奇数索引。这些索引被严格放置在分隔符 $B(x)$ 之上。
无进位不变性：由于 $Z(x)$ 不包含连续整数，映射后的偶数索引之间至少有 4 的间隙。同样，映射后的奇数索引之间也至少有 4 的间隙。关键在于，分隔符 $B(x)$ 确保了 $x$ 使用的最高偶数索引严格小于 $y$ 使用的最低奇数索引。因此，这两组索引的并集不包含连续整数。
编码：编码值是对应这些索引并集的斐波那契数之和。由于支撑集不包含连续索引，结果自动处于齐肯多夫标准型；无需进位传播。

主要贡献

全加法装置：本文定义了一个配对映射 $\pi_{CL}$ 和一个逆映射 unpair，它们仅使用加法和有界扫描在齐肯多夫支撑集上运行。未使用乘法或因数分解。
单射性与可判定性：已证明该映射是单射的。虽然它不是满射，但像集成员资格可通过“不动点测试”进行判定：当且仅当 $\pi_{CL}(\text{unpair}(n)) = n$ 时，数 $n$ 属于像集。
一步规范化解：本文引入了规范化解函数 $can(n) = \pi_{CL}(\text{unpair}(n))$ 。该函数在单步内将任何自然数映射到 $\pi_{CL}$ 像集中的唯一代表元。
稳定性引理：本文确立了修改第二个坐标 $y$ （在其支撑集中添加或移除一个索引）会导致编码值发生局部变化（添加或减去特定的斐波那契数），前提是 $x$ 保持不变。
机械化：所有核心正确性定理（逆映射和单射性）均在 Rocq（前身为 Coq）中使用 Gallina 规范语言进行了机械化。形式化工作包括对斐波那契支撑集存在性和唯一性的证明，确保配对装置不依赖于关于支撑集接口的未证明公理。

结果

正确性：定理 6.0.1 证明了 unpair $\circ$ $\pi_{CL}$ 是 $\mathbb{N}^2$ 上的恒等函数。
非满射性：该映射不是满射；许多自然数（例如 6）在该方案下不对应有效的数对，因为它们的齐肯多夫支撑集不符合特定的奇偶性和分隔符约束。
复杂度：配对和去配对的代价主要由支撑集提取步骤主导（对于贪婪扫描，通常为 $O(r(n))$ ）。本文指出这些是非正式的观察，而非经过认证的复杂度定理。
比较：与需要因数分解的哥德尔编号或需要乘法和平方根的康托尔配对不同， $\pi_{CL}$ 纯粹基于加法运行。与交错固定二进制位置的 Z 序不同， $\pi_{CL}$ 根据第一个操作数的秩移动第二个操作数的位置，从而创建动态分隔符。

意义与主张
本文将该构造定位为逆向数学和弱算术基底研究的工具。通过提供一种避免乘法的配对函数，作者建议它可能有助于研究乘法不可用或受限的系统中的一致性论证和可证性（引用 Buss, 1997; Friedman, 1976）。

作者明确对更广泛的影响保持谦逊：

本文不声称从仅加法原则推导出齐肯多夫支撑集接口本身，并推测此类推导可能不存在。
本文不声称对 $\pi_{CL}$ 的像集有简单的闭式刻画；判定过程是基于支撑集的不动点测试。
主要贡献是显式构建了一个“无进位”装置并验证了其性质，使得像集及其几何结构可直接用于理论分析的检视。

这项工作被呈现为一种基础算术装置，而非用于通用计算的实际数据结构，强调其在逻辑和证明论中的理论效用。