Milan Rosko — Logician & Designer

Navigation:

Main site .html

On this page:

Interactive demo #

Summary

CARRYLESS PAIRING

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:

Repository A001 (Rocq) GitHub
Main paper arXiv
A subsequent specialization by Dr. Zoltán Sóstai adapts the present even/odd band-partition mechanism to a linear-size Fibonacci encoding for Gödel numbering, retaining the carry-free decoding strategy of Carryless Pairing arXiv.
Philosophical companion paper arXiv

Secondary literature and prerequisites for comprehension:

Fibonacci and Lucas Numbers DOI
Boolos, Burgess, Jeffrey: Computability and Logic DOI
On “Zeckendorf's Theorem” Wikipedia

The construction below uses only addition and bounded recursion. We first describe the underlying 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.

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,

$$\begin{align} E(x) &:= \{\, 2k : k \in Z(x) \,\},\\ r(x) &:= \min\{\, m \ge 2 : F_m > x \,\},\\ B(x) &:= 2r(x),\\ O(x,y) &:= \{\, B(x) + (2j - 1) : j \in Z(y) \,\}. \end{align}$$

Carryless Pairing (recommended when $0$ is reserved, e.g. for $\varnothing$) is the function $\pi_{\mathrm{CL}}:\mathbb{N}^2\to\mathbb{N}$ given by:

$$\pi_{\mathrm{CL}}(x,y) \;:=\; F_2 \;+\; \sum_{k\in Z(x)} F_{2k} \;+\; \sum_{j\in Z(y)} F_{\,B(x)+(2j-1)}.$$

Equivalently,

$$\pi_{\mathrm{CL}}(x,y)=F_2+\sum_{i\in E(x)\cup O(x,y)} F_i,$$

The offset term $F_2$ shifts the output away from zero, so that

$$\pi_{\mathrm{CL}}(x,y)\ge 1, \pi_{\mathrm{CL}}(0,0)\neq 0.$$

This keeps $0$ free as a reserved value (for example, to denote the empty support $\varnothing$).

Demo

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.

Waiting for summands.

Step 2. Forget the supporting Fibonacci indices.

Then reconstruct them through a series of local search steps.

Waiting for command.

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}:$

Waiting for input.

Step 4. The inverse — recovering $(x, y)$ from $n$ — is computed by a bounded search that runs in subpolynomial time.

$n \in \mathbb{N}:$

Waiting for input.

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}$ (cf. phi-adic logic). What looks like a division in the inverse is in fact a bounded $\mathcal{O}(\log n)$ search. These guarantees, however, presuppose that the underlying number model is faithful to $\{\,\mathbb{N},\, +,\, \le\,\}$ (without an arithmetic discrepancy $\Delta I$); IEEE-754 floating point past $2^{53}$ is a familiar case where this assumption breaks down. The deeper point is not a detail of implementation but a recurring bias of modern computation: exact arithmetical structure is routinely simulated inside hardware that is only approximate.

Acknowledgment. Thanks to Albert Visser University of Utrecht for timely criticism and guidance.

Illustration: Recurrence relations are computationally expressive.