🔢 mathematics

Carryless Pairing: Additive Pairing in the Fibonacci Basis

Dieser Artikel stellt eine trägerfreie, injektive Paarabbildung von $\mathbb{N}^2$ nach $\mathbb{N}$ vor, die zwei Zahlen in disjunkte Zeckendorf-Indexbänder kodiert, die durch ein Trennzeichen getrennt sind, und eine Auswertung sowie Inversion durch additive Unterstützungsoperationen ohne Multiplikation oder Faktorisierung ermöglicht, wobei die grundlegende Korrektheit in Rocq verifiziert wurde.

Ursprüngliche Autoren: Milan Rosko

Veröffentlicht 2026-05-12

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Milan Rosko

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Idee: Zwei Boxen verpacken, ohne sie zu beschädigen

Stellen Sie sich vor, Sie haben zwei Boxen mit Lego-Steinen, beschriftet mit Box X und Box Y. Sie möchten sie zu einer einzigen riesigen Struktur zusammenkleben, damit Sie sie als ein einziges Objekt herumtragen können, aber Sie wollen sie später auch wieder auseinandernehmen können, ohne Kleber, Klebeband oder Spezialwerkzeug zu verwenden.

Die meisten Methoden, Zahlen zu kombinieren (wie Standardmathematik oder Computercodes), sind wie das Verwenden von Kleber. Um sie später wieder zu trennen, müssen Sie oft komplexe Berechnungen durchführen, Zahlen faktorisieren oder Ziffern „übertragen" (wie bei $9 + 1 = 10$ in der normalen Addition, wo die 1 in die nächste Spalte „übertragen" wird). Dieses Papier schlägt eine neue Methode vor, Zahlen zu kombinieren, die null Kleber und null Überträge erfordert.

Der Rahmen: Das Fibonacci-„Lego-Set"

Um zu verstehen, wie das funktioniert, müssen wir die Regeln ändern, nach denen wir Zahlen bilden. Anstatt das Standard-Dezimalsystem (Einer, Zehner, Hunderter) zu verwenden, nutzt dieses Papier die Fibonacci-Folge ($1, 2, 3, 5, 8, 13, 21...$).

In diesem System hat jede Zahl eine spezielle „Lego-Bauanleitung", die Zeckendorf-Darstellung genannt wird. Die goldene Regel dieser Bauanleitung lautet: Sie dürfen niemals zwei aufeinanderfolgende Fibonacci-Zahlen verwenden.

Schlecht: $5 + 3$ (weil 5 und 3 in der Folge direkt nebeneinander stehen).
Gut: $5 + 2$ (weil zwischen 5 und 2 eine Lücke ist).

Diese „Keine-Nachbarn"-Regel ist der geheime Trick, der das ganze Verfahren möglich macht.

Der Zaubertrick: Die „Geraden" und „Ungeraden" Bereiche

Der Autor, Milan Rosko, hat eine Methode erfunden, um Box X und Box Y in eine einzige Zahl zu packen, indem er sie in verschiedene „Viertel" der Fibonacci-Folge versetzt.

Das gerade Viertel (Box X):
Das Papier nimmt die Bauanleitung für die Zahl X und verschiebt alle ihre Lego-Steine auf geradzahlige Positionen in der Fibonacci-Folge.
- Analogie: Stellen Sie sich vor, X ist ein Bücherregal. Wir stellen alle Bücher auf die geradzahligen Regalböden einer Bibliothek.
Der Trenner (Der Zaun):
Bevor wir Box Y hineinpacken, müssen wir wissen, wie weit X reicht. Das Papier berechnet einen „Zaun" oder Trenner basierend auf der Größe von X. Nennen wir diesen Zaun B.
- Analogie: Wenn X die Regalböden 2 bis 10 einnimmt, wird der Zaun bei Regal 12 gebaut.
Das ungerade Viertel (Box Y):
Jetzt nehmen wir die Bauanleitung für die Zahl Y und verschieben ihre Lego-Steine auf ungeradzahlige Positionen, aber nur beginnend nach dem Zaun (B).
- Analogie: Wir stellen alle Bücher für Y auf die ungeradzahligen Regalböden, aber nur auf die Böden 13, 15, 17 usw. Wir lassen die ungeraden Böden vor dem Zaun leer.

Warum es „Übertragsfrei" ist (Der beste Teil)

In der normalen Mathematik können Sie beim Addieren zweier Zahlen einen „Übertrag" erhalten (z. B. $5+5=10$ ). In diesem Fibonacci-System tritt kein Übertrag auf, wenn Sie zwei Zahlen addieren, die keine „aufeinanderfolgenden" Stellen teilen.

Da das Papier X auf gerade Böden und Y auf ungerade Böden (mit einer Lücke dazwischen) setzt, berühren sich die beiden Sätze von Lego-Steinen niemals.

X befindet sich auf geraden Stellen.
Y befindet sich auf ungeraden Stellen (weit entfernt).
Es gibt keine zwei aufeinanderfolgenden Zahlen in der endgültigen Mischung.

Ergebnis: Die kombinierte Zahl befindet sich bereits in ihrer perfekten, „normalen" Form. Sie müssen keine Aufräumarbeiten oder Mathematik durchführen, um sie zu korrigieren. Es ist, als würden Sie zwei sich nicht berührende Puzzleteile zusammenfügen; sie passen einfach perfekt zusammen.

Wie man es wieder auspackt (Decodierung)

Um die ursprünglichen Boxen zurückzubekommen, schauen Sie sich einfach die kombinierte Zahl an und stellen zwei einfache Fragen:

Wer ist auf den geraden Böden? (Das ist X).
Wer ist auf den ungeraden Böden nach dem Zaun? (Das ist Y).

Da die Regeln so streng sind (kein Berühren, spezifische Lücken), gibt es keine Verwirrung. Sie können immer genau erkennen, welches Stück zu X gehört und welches zu Y.

Wichtige Einschränkungen (Der Teil „Nicht surjektiv")

Das Papier gibt zu, dass diese Methode nicht für jede mögliche Zahl einen Code erzeugt.

Analogie: Stellen Sie sich einen Parkplatz vor, auf dem Autos (Zahlen) nur an bestimmten Stellen parken dürfen. Wenn Sie versuchen, ein Auto an einer Stelle zu parken, die gegen die „Keine-Nachbarn"-Regel oder die „Zaun"-Regel verstößt, bleibt diese Stelle leer.
Das Papier nennt dies injektiv, aber nicht surjektiv.
- Injektiv: Jedes Paar (X, Y) erhält einen eindeutigen Code. Keine zwei Paare ergeben dieselbe Zahl.
- Nicht surjektiv: Einige Zahlen in der Welt können mit dieser Methode nicht gebildet werden. Wenn Sie eine zufällige Zahl auswählen, ist sie möglicherweise kein gültiges „gepacktes" Paar.

Das Papier bietet jedoch einen einfachen Test: Wenn Sie versuchen, eine Zahl auszupacken und sie dann wieder einzupacken und Sie exakt dieselbe Zahl zurückbekommen, dann war es ein gültiges Paar. Wenn sich die Zahl ändert, war sie von vornherein kein gültiges Paar.

Warum ist das wichtig? (Das „Warum")

Der Autor versucht nicht, einen schnelleren Rechner für Ihr Handy zu bauen. Die Motivation ist tiefer und wurzelt in Logik und mathematischen Grundlagen:

Reine Addition: Die meisten Methoden, Zahlen zu kombinieren, beruhen auf Multiplikation oder komplexer Division (wie das Zerlegen einer Zahl in Primfaktoren). Diese Methode beruht nur auf Addition und dem Prüfen von Positionen.
Schwache Mathematische Systeme: In einigen sehr grundlegenden Systemen der Logik (in denen Sie keine Multiplikation verwenden dürfen) können Sie nicht beweisen, dass Sie zwei Zahlen kombinieren und wieder zurückbekommen können. Dieses Papier zeigt einen Weg, dies nur mit einfacher Addition zu tun, was Mathematikern hilft, die absoluten Mindestanforderungen zu verstehen, die für das Funktionieren der Logik notwendig sind.
Proof Checking: Da der Prozess so einfach ist (nur Positionen ansehen und addieren), ist es für einen Computer sehr einfach zu überprüfen, ob die Mathematik korrekt ist, ohne verwirrt zu werden.

Zusammenfassung in einem Satz

Dieses Papier stellt eine clevere Methode vor, zwei Zahlen unter Verwendung der Fibonacci-Folge zu einer einzigen zu kombinieren, wobei die beiden Zahlen in getrennten, sich nicht berührenden „Zonen" leben, sodass sie ohne verworrene Mathematik addiert und einfach durch Betrachten ihrer Sitzpositionen wieder getrennt werden können.

Technische Zusammenfassung: Trägersfreies Pairing in der Fibonacci-Basis

Problemstellung
Der Artikel behandelt die Konstruktion einer Paarungsfunktion $\pi: \mathbb{N}^2 \to \mathbb{N}$ , die strikt innerhalb der additiven Beschränkungen der Zeckendorf-Fibonacci-Basis operiert. Traditionelle Paarungsschemata stützen sich häufig auf die positionelle Ziffern-Interleaving (z. B. Z-Order/Morton-Codes) oder arithmetische Operationen, die Multiplikation und Primfaktorzerlegung beinhalten (z. B. Gödel-Nummerierung, Cantor-Paarung). Der Autor sucht nach einem Mechanismus, bei dem die Kodierung und Dekodierung eines Paares $(x, y)$ ausschließlich auf der Extraktion von Trägern und additiven Operationen beruhen, wobei Multiplikation, Exponentiation sowie die Notwendigkeit von „Träger"-Propagation oder Normalisierungsschritten während der Kombination von Daten vermieden werden. Dies wird durch das Bestreben motiviert, Unvollständigkeitsargumente und proof-theoretische Untersuchungen in schwachen arithmetischen Substraten (wie $I\Delta_0$ ) zu unterstützen, in denen die Multiplikation nicht angenommen wird oder kostspielig ist.

Methodik
Die vorgeschlagene Lösung, bezeichnet als Trägersfreies Pairing ( $\pi_{CL}$ ), kodiert zwei natürliche Zahlen in disjunkte „Bänder" von Fibonacci-Indizes basierend auf ihren Zeckendorf-Trägern.

Zeckendorf-Darstellung: Jede natürliche Zahl $n$ wird eindeutig als Summe nicht-konsecutiver Fibonacci-Zahlen $F_k$ (wobei $k \ge 2$ ) dargestellt. Die Menge der Indizes wird mit $Z(n)$ bezeichnet.
Konstruktion des Trennzeichens: Für ein Paar $(x, y)$ berechnet der Algorithmus zunächst den Rang $r(x)$ , definiert als der kleinste Index, sodass $F_{r(x)} > x$ gilt. Ein Trennzeichen $B(x)$ wird auf $2r(x)$ gesetzt.
Trennung der Bänder:
- Gerades Band (für $x$ ): Die Indizes des Trägers von $x$ , $Z(x)$ , werden über $e \mapsto 2e$ auf gerade Indizes abgebildet. Diese werden im Bereich $[4, 2r(x))$ platziert.
- Ungerades Band (für $y$ ): Die Indizes des Trägers von $y$ , $Z(y)$ , werden über $j \mapsto B(x) + (2j - 1)$ auf ungerade Indizes abgebildet. Diese werden strikt oberhalb des Trennzeichens $B(x)$ platziert.
Trägersfreie Invariante: Da $Z(x)$ keine aufeinanderfolgenden ganzen Zahlen enthält, weisen die abgebildeten geraden Indizes Lücken von mindestens 4 auf. Ebenso weisen die abgebildeten ungeraden Indizes Lücken von mindestens 4 auf. Entscheidend ist, dass das Trennzeichen $B(x)$ sicherstellt, dass der höchste von $x$ verwendete gerade Index strikt kleiner ist als der niedrigste von $y$ verwendete ungerade Index. Folglich enthält die Vereinigung dieser beiden Indizesmengen keine aufeinanderfolgenden ganzen Zahlen.
Kodierung: Der kodierte Wert ist die Summe der Fibonacci-Zahlen, die der Vereinigung dieser Indizes entsprechen. Da der Träger keine aufeinanderfolgenden Indizes enthält, befindet sich das Ergebnis automatisch in Zeckendorf-Normalform; keine Träger-Propagation ist erforderlich.

Hauptbeiträge

Vollständig additives Gerät: Der Artikel definiert eine Paarungsmapping $\pi_{CL}$ und eine Inversionsmapping unpair, die ausschließlich auf Zeckendorf-Trägern unter Verwendung von Addition und beschränkten Scans operieren. Es wird keine Multiplikation oder Faktorisierung verwendet.
Injektivität und Entscheidbarkeit: Es wird bewiesen, dass die Abbildung injektiv ist. Obwohl sie nicht surjektiv ist, ist die Mitgliedschaft im Bild über einen „Fixpunkt-Test" entscheidbar: Eine Zahl $n$ gehört genau dann zum Bild, wenn $\pi_{CL}(\text{unpair}(n)) = n$ gilt.
Ein-Schritt-Canonicalisierung: Der Artikel führt eine Canonicalisierungsfunktion $can(n) = \pi_{CL}(\text{unpair}(n))$ ein. Diese Funktion bildet jede natürliche Zahl in einem einzigen Schritt auf ihren eindeutigen Repräsentanten im Bild von $\pi_{CL}$ ab.
Stabilitäts-Lemma: Der Artikel stellt fest, dass eine Modifikation der zweiten Koordinate $y$ (Hinzufügen oder Entfernen eines Index aus ihrem Träger) zu einer lokalen Änderung des kodierten Werts (Hinzufügen oder Subtrahieren einer spezifischen Fibonacci-Zahl) führt, sofern $x$ unverändert bleibt.
Mechanisierung: Alle Kernkorrektheitsbeweise (Inversion und Injektivität) wurden in Rocq (ehemals Coq) unter Verwendung der Gallina-Spezifikationssprache mechanisiert. Die Formalisierung umfasst Beweise für die Existenz und Eindeutigkeit von Zeckendorf-Trägern und stellt sicher, dass das Paarungsgerät nicht auf unbewiesenen Axiomen bezüglich der Trägerschnittstelle beruht.

Ergebnisse

Korrektheit: Satz 6.0.1 beweist, dass unpair $\circ$ $\pi_{CL}$ die Identitätsfunktion auf $\mathbb{N}^2$ ist.
Nicht-Surjektivität: Die Abbildung ist nicht surjektiv; viele natürliche Zahlen (z. B. 6) entsprechen unter diesem Schema keinen gültigen Paaren, da ihre Zeckendorf-Träger nicht mit den spezifischen Paritäts- und Trennzeichen-Beschränkungen übereinstimmen.
Komplexität: Die Kosten für Pairing und Unpairing werden durch den Schritt der Trägerextraktion dominiert (typischerweise $O(r(n))$ für einen gierigen Scan). Der Artikel stellt fest, dass dies informelle Beobachtungen und keine zertifizierten Komplexitätssätze sind.
Vergleich: Im Gegensatz zur Gödel-Nummerierung (die Faktorisierung erfordert) oder der Cantor-Paarung (die Multiplikation und Quadratwurzeln erfordert), operiert $\pi_{CL}$ rein additiv. Im Gegensatz zur Z-Order (die feste binäre Positionen interleaved), verschiebt $\pi_{CL}$ die Position des zweiten Operanden basierend auf dem Rang des ersten und erzeugt so ein dynamisches Trennzeichen.

Bedeutung und Behauptungen
Der Artikel positioniert diese Konstruktion als Werkzeug für die Reverse Mathematik und die Untersuchung schwacher arithmetischer Substrate. Indem er eine Paarungsfunktion bereitstellt, die die Multiplikation vermeidet, schlägt der Autor vor, dass sie für die Untersuchung von Konsistenzargumenten und Beweisbarkeit in Systemen nützlich sein könnte, in denen die Multiplikation nicht verfügbar ist oder eingeschränkt wird (unter Bezugnahme auf Buss, 1997; Friedman, 1976).

Der Autor äußert ausdrücklich Bescheidenheit hinsichtlich breiterer Implikationen:

Der Artikel behauptet nicht, die Zeckendorf-Trägerschnittstelle selbst aus reinen Additionsprinzipien abzuleiten, und vermutet, dass eine solche Ableitung möglicherweise nicht existiert.
Er behauptet keine einfache geschlossene Form-Charakterisierung des Bildes von $\pi_{CL}$ ; das Entscheidungsverfahren ist der trägerbasierte Fixpunkt-Test.
Der Hauptbeitrag ist die explizite Konstruktion eines „trägersfreien" Geräts und die Verifikation seiner Eigenschaften, wodurch das Bild und seine geometrische Struktur direkt für theoretische Analysen überprüfbar werden.

Die Arbeit wird als fundamentales arithmetisches Gerät präsentiert und nicht als praktische Datenstruktur für die allgemeine Datenverarbeitung, wobei ihr theoretischer Nutzen in Logik und Beweistheorie betont wird.