Carryless Pairing: Additive Pairing in the Fibonacci Basis
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914553050169344 |
|---|---|
| author | Rosko, Milan |
| author_facet | Rosko, Milan |
| contents | We define a pairing map $π_{\mathsf{CL}} : \mathbb{N}^2\to\mathbb{N}$ that encodes $x$ and $y$ into two disjoint bands of Zeckendorf indices separated by a delimiter computed from $x$. The construction is "carryless" by design: the combined support has no consecutive indices, so each produced code is already in Zeckendorf-normal form, and both evaluation and inversion proceed by additive support operations alone, without multiplication, factorization, or positional digit interleaving. The map is injective not surjective, image membership is decidable by the same support machinery used for decoding. The core correctness theorems are mechanized in Rocq. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10382 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Carryless Pairing: Additive Pairing in the Fibonacci Basis Rosko, Milan Logic Logic in Computer Science 03B30, 11H71, 03F40, 18A15, 03F15 I.1.2; I.2.3 We define a pairing map $π_{\mathsf{CL}} : \mathbb{N}^2\to\mathbb{N}$ that encodes $x$ and $y$ into two disjoint bands of Zeckendorf indices separated by a delimiter computed from $x$. The construction is "carryless" by design: the combined support has no consecutive indices, so each produced code is already in Zeckendorf-normal form, and both evaluation and inversion proceed by additive support operations alone, without multiplication, factorization, or positional digit interleaving. The map is injective not surjective, image membership is decidable by the same support machinery used for decoding. The core correctness theorems are mechanized in Rocq. |
| title | Carryless Pairing: Additive Pairing in the Fibonacci Basis |
| topic | Logic Logic in Computer Science 03B30, 11H71, 03F40, 18A15, 03F15 I.1.2; I.2.3 |
| url | https://arxiv.org/abs/2509.10382 |