A pairing function takes two natural numbers $x$ and $y$ and returns a single natural number from which both can be recovered. The construction here works in the Fibonacci basis: each input is written as a sum of distinct, non-consecutive Fibonacci numbers (its Zeckendorf support), and the two supports are placed on disjoint even and offset odd index bands. Because the bands cannot overlap, the encoding and its inverse use only addition and bounded search, never a carry.
Key materials:
Secondary literature and prerequisites for comprehension:
We first describe a mechanism, then turn it into a pairing function.
(i) A chosen collection of Fibonacci numbers is added together into a single value. (ii) The list of chosen indices is then discarded, and only the resulting sum is handed to a Greedy Algorithm. (iii) From that sum alone, the original collection of indices is reconstructed in a bounded number of steps arithmetically.
This round trip, from an arbitrary input to its canonical additive form and back, relies on Binet’s Formula, Hurwitz’s Theorem, and Zeckendorf’s Theorem. Together they yield a stable, reversible, and fully bounded encoding-decoding scheme.
(iv) The same machinery yields a constructive, and therefore injective, arithmetical pairing function. Writing $Z(n)$ for the set of Zeckendorf indices of $n$, we set $Z(0):=\varnothing$ and let $x, y \in \mathbb{N}$:
For $x,y\in\mathbb{N}$ we define the even-band and odd-band supports,
Carryless Pairing (recommended when $0$ is reserved, e.g. for $\varnothing$) is the function
given by:
Equivalently,
The offset term $F_2$ shifts the output away from zero, so that
This keeps $0$ free as a reserved value (for example, to denote the empty support $\varnothing$).
Realization. The demo executes the carryless construction in four stages, each fully effective: bounded Fibonacci decomposition, reconstruction by local search, forward pairing, and inverse unpairing.
Step 1. Select at least two integers. JavaScript decomposes each one uniquely into non-consecutive Fibonacci summands.
Step 2. Forget the supporting Fibonacci indices.
Then reconstruct them through a series of local search steps.
Step 3. Use this correspondence to build an injective $\Delta_0$ pairing function that takes any two natural numbers and returns a single one.
$x \in \mathbb{N}:$
$y \in \mathbb{N}:$
Step 4. The inverse — recovering $(x, y)$ from $n$ — is computed by a bounded search that runs in subpolynomial time.
$n \in \mathbb{N}:$
Remark. The pairing $\pi_{\mathrm{CL}}^\tau$ is finitary: each step uses a finite, explicitly bounded amount of arithmetic. Its correctness depends on the fact that every natural number has exactly one Zeckendorf decomposition, and that this decomposition is preserved under the standard order on $\mathbb{N}$. What looks like division is modular arithmetic, in fact a bounded $\mathcal{O}(\log n)$ search. These guarantees, however, presuppose that the underlying number model is faithful to $\{\,\mathbb{N},\, +,\, \le\,\}$; IEEE-754 floating point past $2^{53}$ is a familiar case where this assumption breaks down. We note a recurring theme in computation: exact arithmetical structure is routinely simulated inside hardware that is only approximate.
Acknowledgment. Thanks to Albert Visser Utrecht University for timely criticism and guidance.
The display below states the pairing as a finite arithmetic procedure. The input numbers are first converted to their canonical Zeckendorf supports; those supports are then placed on disjoint Fibonacci index bands. Decoding reverses the construction by decomposing the output, separating the even and offset odd bands, and summing the recovered Fibonacci terms.