Milan Rosko — Logician & Designer

Navigation:

Main site .html

On this page:

Interactive demo #

Summary

CARRYLESS PAIRING

Our function encodes a pair of natural numbers using only addition and primitive recursion. We work in the Fibonacci basis and place the digits of $x$ in even-index slots and the digits of $y$ in odd-index slots after an offset, so the two bands stay disjoint and no carrying is needed.

Key materials:

Repository T001 (Rocq) GitHub
Main Paper arXiv
Secondary Paper arXiv

Secondary literature and prerequisites:

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

The algorithm below emerges solely from addition and bounded recursion. We demonstrate the core mechanism and the pairing function.

(i) First, a chosen set of Fibonacci terms is aggregated into a single numerical value.

(ii) In a second step, the selection itself is discarded, and only the resulting sum is returned to a Greedy Algorithm.

(iii) Finally, the original terms are recovered from the sum alone within a bounded number of steps.

This round-trip, from arbitrary input to canonical additive form and back, utilizes Binet’s Formula, the Hurwitz Satz, and Zeckendorf’s Theorem to yield a stable, reversible, and fully bounded finitary encoding-decoding scheme.

(iv) The structure can be used to realize a constructive (hence injective) arithmetical pairing function by defining $Z(0):=\varnothing$ and $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$ ensures

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

Demo

Realization. We demonstrate effectivity of the carryless construction in four stages: 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.

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 from two arbitrary natural numbers.

$x \in \mathbb{N}:$

$y \in \mathbb{N}:$

Waiting for input.

Step 4. The inverse is recovered by bounded search in subpolynomial time.

$n \in \mathbb{N}:$

Waiting for input.

Remark. The pairing $\pi_{\mathrm{CL}}^\tau$ is finitary and correctness relies on the uniqueness and stability of Zeckendorf decompositions (cf. 'Phi'-adic Logic) under exact order. The apparent division at reversal is a $\mathcal{O}(\log n)$ search problem. However, if one realizes the procedure in a numerical model that is not an exact copy of $\{\,\mathbb{N},\, +,\, \le\,\}$ (with $\Delta I$), then the underlying invariants might not be preserved, e.g. IEEE-754 floating-point past $2^{53}$. This highlights a persistent key bias in contemporary computation.

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

Illustration: Recurrence relations are computationally expressive.