🔢 mathematics

Carryless Pairing: Additive Pairing in the Fibonacci Basis

This paper introduces a carryless, injective pairing map from $\mathbb{N}^2$ to $\mathbb{N}$ that encodes two numbers into disjoint Zeckendorf index bands separated by a delimiter, enabling evaluation and inversion through additive support operations without multiplication or factorization, with core correctness verified in Rocq.

Original authors: Milan Rosko

Published 2026-05-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Milan Rosko

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Packing Two Boxes Without Breaking Them

Imagine you have two boxes of Lego bricks, labeled Box X and Box Y. You want to glue them together into one giant structure so you can carry them around as a single object, but you also want to be able to pull them apart later without using any glue, tape, or special tools.

Most ways of combining numbers (like standard math or computer code) are like using glue. To separate them later, you often have to do complex calculations, factorize numbers, or "carry" digits over (like when $9 + 1 = 10$ in normal addition, where the 1 "carries" over to the next column). This paper proposes a new way to combine numbers that requires zero glue and zero carrying.

The Setting: The Fibonacci "Lego Set"

To understand how this works, we need to change the rules of how we build numbers. Instead of using the standard base-10 system (ones, tens, hundreds), this paper uses the Fibonacci sequence ($1, 2, 3, 5, 8, 13, 21...$).

In this system, every number has a special "Lego blueprint" called a Zeckendorf representation. The golden rule of this blueprint is: You can never use two consecutive Fibonacci numbers.

Bad: $5 + 3$ (because 5 and 3 are next to each other in the sequence).
Good: $5 + 2$ (because 5 and 2 have a gap).

This "no-consecutive" rule is the secret sauce that makes the whole trick possible.

The Magic Trick: The "Even" and "Odd" Bands

The author, Milan Rosko, invented a method to pack Box X and Box Y into a single number by putting them in different "neighborhoods" of the Fibonacci sequence.

The Even Neighborhood (Box X):
The paper takes the blueprint for number X and shifts all its Lego pieces to even-numbered positions in the Fibonacci sequence.
- Analogy: Imagine X is a set of books. We put them all on the even-numbered shelves of a library.
The Delimiter (The Fence):
Before we put Box Y in, we need to know how far X extends. The paper calculates a "fence" or delimiter based on the size of X. Let's call this fence B.
- Analogy: If X takes up shelves 2 through 10, the fence is built at shelf 12.
The Odd Neighborhood (Box Y):
Now, we take the blueprint for number Y and shift its Lego pieces to odd-numbered positions, but only starting after the fence (B).
- Analogy: We put all the books for Y on the odd-numbered shelves, but only on shelves 13, 15, 17, etc. We leave the odd shelves before the fence empty.

Why It's "Carryless" (The Best Part)

In normal math, if you add two numbers, you might get a "carry" (e.g., $5+5=10$ ). In this Fibonacci system, if you add two numbers that don't share any "consecutive" spots, no carrying happens.

Because the paper puts X on even shelves and Y on odd shelves (with a gap in between), the two sets of Lego pieces never touch.

X is on even spots.
Y is on odd spots (far away).
There are no two consecutive numbers in the final mix.

Result: The combined number is already in its perfect, "normal" form. You don't need to do any cleanup or math to fix it. It's like putting two non-touching puzzle pieces together; they just fit perfectly.

How to Unpack It (Decoding)

To get the original boxes back, you just look at the combined number and ask two simple questions:

Who is on the even shelves? (That's X).
Who is on the odd shelves after the fence? (That's Y).

Because the rules are so strict (no touching, specific gaps), there is no confusion. You can always tell exactly which piece belongs to X and which belongs to Y.

Important Limitations (The "Not Surjective" Part)

The paper admits that this method doesn't create a code for every possible number.

Analogy: Imagine a parking lot where cars (numbers) can only park in specific spots. If you try to park a car in a spot that violates the "no-touching" rule or the "fence" rule, that spot is empty.
The paper calls this injective but not surjective.
- Injective: Every pair of (X, Y) gets a unique code. No two pairs make the same number.
- Not Surjective: Some numbers in the world cannot be formed by this method. If you pick a random number, it might not be a valid "packed" pair.

However, the paper provides a simple test: If you try to unpack a number and then re-pack it, and you get the exact same number back, then it was a valid pair. If the number changes, it wasn't a valid pair to begin with.

Why Does This Matter? (The "Why")

The author isn't trying to make a faster calculator for your phone. The motivation is deeper, rooted in logic and math foundations:

Pure Addition: Most ways of combining numbers rely on multiplication or complex division (like breaking a number into prime factors). This method relies only on addition and checking positions.
Weak Math Systems: In some very basic systems of logic (where you aren't allowed to use multiplication), you can't prove that you can combine two numbers and get them back. This paper shows a way to do it using only simple addition, which helps mathematicians understand the absolute minimum requirements needed for logic to work.
Proof Checking: Because the process is so simple (just looking at positions and adding), it's very easy for a computer to verify that the math is correct without getting confused.

Summary in One Sentence

This paper introduces a clever way to combine two numbers into one using the Fibonacci sequence, where the two numbers live in separate, non-touching "zones" so they can be added together without any messy math, and pulled apart just by looking at where they are sitting.

Technical Summary: Carryless Pairing in the Fibonacci Basis

Problem Statement
The paper addresses the construction of a pairing function $\pi: \mathbb{N}^2 \to \mathbb{N}$ that operates strictly within the additive constraints of the Zeckendorf (Fibonacci) basis. Traditional pairing schemes often rely on positional digit interleaving (e.g., Z-order/Morton codes) or arithmetic operations involving multiplication and prime factorization (e.g., Gödel numbering, Cantor pairing). The author seeks a mechanism where the encoding and decoding of a pair $(x, y)$ rely solely on support extraction and additive operations, avoiding multiplication, exponentiation, and the need for "carry" propagation or normalization steps during the combination of data. This is motivated by the desire to support incompleteness arguments and proof-theoretic investigations in weak arithmetic substrates (such as $I\Delta_0$ ) where multiplication is not assumed or is costly.

Methodology
The proposed solution, termed Carryless Pairing ( $\pi_{CL}$ ), encodes two natural numbers into disjoint "bands" of Fibonacci indices based on their Zeckendorf supports.

Zeckendorf Representation: Every natural number $n$ is uniquely represented as a sum of non-consecutive Fibonacci numbers $F_k$ (where $k \ge 2$ ). The set of indices is denoted $Z(n)$ .
Delimiter Construction: For a pair $(x, y)$ , the algorithm first computes the rank $r(x)$ , defined as the smallest index such that $F_{r(x)} > x$ . A delimiter $B(x)$ is set to $2r(x)$ .
Band Separation:
- Even Band (for $x$ ): The indices of $x$ 's support, $Z(x)$ , are mapped to even indices via $e \mapsto 2e$ . These are placed in the range $[4, 2r(x))$ .
- Odd Band (for $y$ ): The indices of $y$ 's support, $Z(y)$ , are mapped to odd indices via $j \mapsto B(x) + (2j - 1)$ . These are placed strictly above the delimiter $B(x)$ .
Carryless Invariant: Because $Z(x)$ contains no consecutive integers, the mapped even indices have gaps of at least 4. Similarly, the mapped odd indices have gaps of at least 4. Crucially, the delimiter $B(x)$ ensures that the highest even index used by $x$ is strictly less than the lowest odd index used by $y$ . Consequently, the union of these two sets of indices contains no consecutive integers.
Encoding: The encoded value is the sum of Fibonacci numbers corresponding to the union of these indices. Since the support contains no consecutive indices, the result is automatically in Zeckendorf normal form; no carry propagation is required.

Key Contributions

Fully Additive Device: The paper defines a pairing map $\pi_{CL}$ and an inversion map unpair that operate exclusively on Zeckendorf supports using addition and bounded scans. No multiplication or factorization is used.
Injectivity and Decidability: The map is proven to be injective. While not surjective, image membership is decidable via a "fixed-point test": a number $n$ is in the image if and only if $\pi_{CL}(\text{unpair}(n)) = n$ .
One-Step Canonicalization: The paper introduces a canonicalization function $can(n) = \pi_{CL}(\text{unpair}(n))$ . This function maps any natural number to its unique representative in the image of $\pi_{CL}$ in a single step.
Stability Lemma: The paper establishes that modifying the second coordinate $y$ (adding or removing an index from its support) results in a local change to the encoded value (adding or subtracting a specific Fibonacci number), provided $x$ remains fixed.
Mechanization: All core correctness theorems (inversion and injectivity) are mechanized in Rocq (formerly Coq), using the Gallina specification language. The formalization includes proofs of the existence and uniqueness of Zeckendorf supports, ensuring the pairing device does not rely on unproven axioms regarding the support interface.

Results

Correctness: Theorem 6.0.1 proves that unpair $\circ$ $\pi_{CL}$ is the identity function on $\mathbb{N}^2$ .
Non-Surjectivity: The map is not surjective; many natural numbers (e.g., 6) do not correspond to valid pairs under this scheme because their Zeckendorf supports do not align with the specific parity and delimiter constraints.
Complexity: The cost of pairing and unpairing is dominated by the support extraction step (typically $O(r(n))$ for a greedy scan). The paper notes these are informal observations rather than certified complexity theorems.
Comparison: Unlike Gödel numbering (which requires factorization) or Cantor pairing (which requires multiplication and square roots), $\pi_{CL}$ operates purely additively. Unlike Z-order (which interleaves fixed binary positions), $\pi_{CL}$ shifts the position of the second operand based on the rank of the first, creating a dynamic delimiter.

Significance and Claims
The paper positions this construction as a tool for reverse mathematics and the study of weak arithmetic substrates. By providing a pairing function that avoids multiplication, the author suggests it may be useful for investigating consistency arguments and provability in systems where multiplication is not available or is restricted (referencing Buss, 1997; Friedman, 1976).

The author explicitly states modesty regarding broader implications:

The paper does not claim to derive the Zeckendorf support interface itself from addition-only principles, conjecturing that such a derivation may not exist.
It does not claim a simple closed-form characterization of the image of $\pi_{CL}$ ; the decision procedure is the support-based fixed-point test.
The primary contribution is the explicit construction of a "carryless" device and the verification of its properties, making the image and its geometric structure directly inspectable for theoretical analysis.

The work is presented as a foundational arithmetic device rather than a practical data structure for general computing, emphasizing its theoretical utility in logic and proof theory.