🔢 mathematics

Carryless Pairing: Additive Pairing in the Fibonacci Basis

Ce papier introduit une application d'appariement sans retenue et injective de $\mathbb{N}^2$ vers $\mathbb{N}$ qui encode deux nombres dans des bandes d'indices de Zeckendorf disjointes séparées par un délimiteur, permettant une évaluation et une inversion par des opérations de support additif sans multiplication ni factorisation, la correction fondamentale étant vérifiée dans Rocq.

Auteurs originaux : Milan Rosko

Publié 2026-05-12

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Milan Rosko

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La Grande Idée : Empaquetter deux boîtes sans les briser

Imaginez que vous avez deux boîtes de briques Lego, étiquetées Boîte X et Boîte Y. Vous voulez les coller ensemble pour former une seule structure géante afin de les transporter comme un objet unique, mais vous souhaitez aussi pouvoir les séparer plus tard sans utiliser de colle, de ruban adhésif ou d'outils spéciaux.

La plupart des méthodes pour combiner des nombres (comme les mathématiques standard ou le code informatique) ressemblent à l'utilisation de colle. Pour les séparer plus tard, vous devez souvent effectuer des calculs complexes, factoriser des nombres ou « reporter » des chiffres (comme lorsque $9 + 1 = 10$ dans l'addition normale, où le 1 est « reporté » vers la colonne suivante). Ce papier propose une nouvelle façon de combiner des nombres qui nécessite zéro colle et zéro report.

Le Cadre : Le « Set de Lego » de Fibonacci

Pour comprendre comment cela fonctionne, nous devons changer les règles de construction des nombres. Au lieu d'utiliser le système décimal standard (unités, dizaines, centaines), ce papier utilise la suite de Fibonacci ($1, 2, 3, 5, 8, 13, 21...$).

Dans ce système, chaque nombre possède un « plan de montage Lego » spécial appelé représentation de Zeckendorf. La règle d'or de ce plan est : Vous ne pouvez jamais utiliser deux nombres de Fibonacci consécutifs.

Mauvais : $5 + 3$ (car 5 et 3 sont l'un à côté de l'autre dans la suite).
Bon : $5 + 2$ (car 5 et 2 ont un écart).

Cette règle de « pas de consécutifs » est l'ingrédient secret qui rend tout l'astuce possible.

L'Astuce de Magie : Les Bandes « Paires » et « Impaires »

L'auteur, Milan Rosko, a inventé une méthode pour empaqueter la Boîte X et la Boîte Y dans un seul nombre en les plaçant dans différents « quartiers » de la suite de Fibonacci.

Le Quartier Paire (Boîte X) :
Le papier prend le plan de montage du nombre X et déplace toutes ses pièces Lego vers des positions paires dans la suite de Fibonacci.
- Analogie : Imaginez que X est un ensemble de livres. Nous les plaçons tous sur les étagères numérotées paires d'une bibliothèque.
Le Délimiteur (La Clôture) :
Avant de placer la Boîte Y, nous devons savoir jusqu'où s'étend X. Le papier calcule une « clôture » ou un délimiteur basé sur la taille de X. Appelons cette clôture B.
- Analogie : Si X occupe les étagères 2 à 10, la clôture est construite à l'étagère 12.
Le Quartier Impaire (Boîte Y) :
Maintenant, nous prenons le plan de montage du nombre Y et déplaçons ses pièces Lego vers des positions impaires, mais uniquement en commençant après la clôture (B).
- Analogie : Nous plaçons tous les livres de Y sur les étagères impaires, mais uniquement sur les étagères 13, 15, 17, etc. Nous laissons les étagères impaires avant la clôture vides.

Pourquoi c'est « Sans Retenue » (La Meilleure Partie)

En mathématiques normales, si vous additionnez deux nombres, vous pouvez obtenir une « retenue » (par exemple, $5+5=10$ ). Dans ce système de Fibonacci, si vous additionnez deux nombres qui ne partagent aucun emplacement « consécutif », aucune retenue ne se produit.

Comme le papier place X sur les étagères paires et Y sur les étagères impaires (avec un écart entre les deux), les deux ensembles de pièces Lego ne se touchent jamais.

X est sur des emplacements pairs.
Y est sur des emplacements impaires (loin).
Il n'y a pas deux nombres consécutifs dans le mélange final.

Résultat : Le nombre combiné est déjà dans sa forme parfaite et « normale ». Vous n'avez pas besoin de faire de nettoyage ou de calculs pour le corriger. C'est comme assembler deux pièces de puzzle qui ne se touchent pas ; elles s'emboîtent parfaitement.

Comment le Dépaqueter (Décodage)

Pour récupérer les boîtes originales, il suffit de regarder le nombre combiné et de se poser deux questions simples :

Qui est sur les étagères paires ? (C'est X).
Qui est sur les étagères impaires après la clôture ? (C'est Y).

Comme les règles sont si strictes (pas de contact, écarts spécifiques), il n'y a aucune confusion. Vous pouvez toujours dire exactement quelle pièce appartient à X et laquelle appartient à Y.

Limitations Importantes (La Partie « Non Surjective »)

Le papier admet que cette méthode ne crée pas un code pour tous les nombres possibles.

Analogie : Imaginez un parking où les voitures (les nombres) ne peuvent se garer que dans des emplacements spécifiques. Si vous essayez de garer une voiture dans un emplacement qui viole la règle de « pas de contact » ou la règle de la « clôture », cet emplacement reste vide.
Le papier qualifie cela d'injectif mais non surjectif.
- Injectif : Chaque paire de (X, Y) obtient un code unique. Aucune deux paires ne produisent le même nombre.
- Non Surjectif : Certains nombres dans le monde ne peuvent pas être formés par cette méthode. Si vous choisissez un nombre au hasard, il se peut qu'il ne soit pas une paire « empaquetée » valide.

Cependant, le papier fournit un test simple : si vous essayez de dépaqueter un nombre, puis de le re-empaqueter, et que vous obtenez exactement le même nombre, alors c'était une paire valide. Si le nombre change, ce n'était pas une paire valide au départ.

Pourquoi cela compte-t-il ? (Le « Pourquoi »)

L'auteur ne cherche pas à créer une calculatrice plus rapide pour votre téléphone. La motivation est plus profonde, enracinée dans la logique et les fondements des mathématiques :

Addition Pure : La plupart des façons de combiner des nombres reposent sur la multiplication ou une division complexe (comme décomposer un nombre en facteurs premiers). Cette méthode repose uniquement sur l'addition et la vérification des positions.
Systèmes Mathématiques Faibles : Dans certains systèmes de logique très basiques (où la multiplication n'est pas autorisée), on ne peut pas prouver que l'on peut combiner deux nombres et les récupérer. Ce papier montre une façon de le faire en utilisant uniquement une addition simple, ce qui aide les mathématiciens à comprendre les exigences minimales absolues nécessaires au fonctionnement de la logique.
Vérification de Preuve : Comme le processus est si simple (seulement regarder les positions et additionner), il est très facile pour un ordinateur de vérifier que les mathématiques sont correctes sans se tromper.

Résumé en Une Phrase

Ce papier introduit une méthode ingénieuse pour combiner deux nombres en un seul en utilisant la suite de Fibonacci, où les deux nombres vivent dans des « zones » séparées et non adjacentes afin qu'ils puissent être additionnés sans mathématiques désordonnées, et séparés simplement en regardant où ils sont assis.

Résumé technique : Appariement sans retenue dans la base de Fibonacci

Énoncé du problème
L'article aborde la construction d'une fonction d'appariement $\pi: \mathbb{N}^2 \to \mathbb{N}$ opérant strictement dans les contraintes additives de la base de Zeckendorf (Fibonacci). Les schémas d'appariement traditionnels reposent souvent sur l'entrelacement positionnel de chiffres (par exemple, codes Z-order/Morton) ou sur des opérations arithmétiques impliquant la multiplication et la factorisation première (par exemple, numérotation de Gödel, appariement de Cantor). L'auteur cherche un mécanisme où le codage et le décodage d'une paire $(x, y)$ reposent uniquement sur l'extraction de support et des opérations additives, évitant la multiplication, l'exponentiation et la nécessité de propagation de « retenues » ou d'étapes de normalisation lors de la combinaison de données. Cela est motivé par le désir de soutenir des arguments d'incomplétude et des investigations proof-théoriques dans des substrats arithmétiques faibles (tels que $I\Delta_0$ ) où la multiplication n'est pas supposée ou est coûteuse.

Méthodologie
La solution proposée, dénommée Appariement sans retenue ( $\pi_{CL}$ ), encode deux nombres naturels dans des « bandes » disjointes d'indices de Fibonacci basées sur leurs supports de Zeckendorf.

Représentation de Zeckendorf : Tout nombre naturel $n$ est représenté de manière unique comme une somme de nombres de Fibonacci non consécutifs $F_k$ (où $k \ge 2$ ). L'ensemble des indices est noté $Z(n)$ .
Construction du délimiteur : Pour une paire $(x, y)$ , l'algorithme calcule d'abord le rang $r(x)$ , défini comme le plus petit indice tel que $F_{r(x)} > x$ . Un délimiteur $B(x)$ est défini comme $2r(x)$ .
Séparation des bandes :
- Bande paire (pour $x$ ) : Les indices du support de $x$ , $Z(x)$ , sont mappés vers des indices pairs via $e \mapsto 2e$ . Ceux-ci sont placés dans l'intervalle $[4, 2r(x))$ .
- Bande impaire (pour $y$ ) : Les indices du support de $y$ , $Z(y)$ , sont mappés vers des indices impairs via $j \mapsto B(x) + (2j - 1)$ . Ceux-ci sont placés strictement au-dessus du délimiteur $B(x)$ .
Invariant sans retenue : Parce que $Z(x)$ ne contient pas d'entiers consécutifs, les indices pairs mappés présentent des écarts d'au moins 4. De même, les indices impairs mappés présentent des écarts d'au moins 4. Crucialement, le délimiteur $B(x)$ garantit que le plus grand indice pair utilisé par $x$ est strictement inférieur au plus petit indice impair utilisé par $y$ . Par conséquent, l'union de ces deux ensembles d'indices ne contient aucun entier consécutif.
Encodage : La valeur encodée est la somme des nombres de Fibonacci correspondant à l'union de ces indices. Puisque le support ne contient aucun indice consécutif, le résultat est automatiquement sous forme normale de Zeckendorf ; aucune propagation de retenue n'est requise.

Contributions clés

Dispositif entièrement additif : L'article définit une application d'appariement $\pi_{CL}$ et une application d'inversion unpair qui opèrent exclusivement sur les supports de Zeckendorf en utilisant l'addition et des balayages bornés. Aucune multiplication ni factorisation n'est utilisée.
Injectivité et décidabilité : L'application est prouvée injective. Bien que non surjective, l'appartenance à l'image est décidable via un « test de point fixe » : un nombre $n$ est dans l'image si et seulement si $\pi_{CL}(\text{unpair}(n)) = n$ .
Canonisation en une étape : L'article introduit une fonction de canonisation $can(n) = \pi_{CL}(\text{unpair}(n))$ . Cette fonction mappe tout nombre naturel vers son représentant unique dans l'image de $\pi_{CL}$ en une seule étape.
Lemme de stabilité : L'article établit que modifier la deuxième coordonnée $y$ (ajouter ou retirer un indice de son support) entraîne un changement local de la valeur encodée (ajout ou soustraction d'un nombre de Fibonacci spécifique), à condition que $x$ reste fixe.
Mécanisation : Tous les théorèmes de correction fondamentaux (inversion et injectivité) sont mécanisés en Rocq (anciennement Coq), en utilisant le langage de spécification Gallina. La formalisation inclut des preuves de l'existence et de l'unicité des supports de Zeckendorf, garantissant que le dispositif d'appariement ne repose pas sur des axiomes non prouvés concernant l'interface de support.

Résultats

Correction : Le théorème 6.0.1 prouve que unpair $\circ$ $\pi_{CL}$ est la fonction identité sur $\mathbb{N}^2$ .
Non-surjectivité : L'application n'est pas surjective ; de nombreux nombres naturels (par exemple, 6) ne correspondent pas à des paires valides selon ce schéma car leurs supports de Zeckendorf ne s'alignent pas avec les contraintes spécifiques de parité et de délimiteur.
Complexité : Le coût de l'appariement et du déappariement est dominé par l'étape d'extraction du support (typiquement $O(r(n))$ pour un balayage glouton). L'article note qu'il s'agit d'observations informelles plutôt que de théorèmes de complexité certifiés.
Comparaison : Contrairement à la numérotation de Gödel (qui nécessite une factorisation) ou à l'appariement de Cantor (qui nécessite une multiplication et des racines carrées), $\pi_{CL}$ opère purement de manière additive. Contrairement à l'ordre Z (qui entrelace des positions binaires fixes), $\pi_{CL}$ déplace la position du deuxième opérande en fonction du rang du premier, créant un délimiteur dynamique.

Signification et affirmations
L'article positionne cette construction comme un outil pour les mathématiques inversées et l'étude des substrats arithmétiques faibles. En fournissant une fonction d'appariement évitant la multiplication, l'auteur suggère qu'elle pourrait être utile pour investiguer les arguments de consistance et la prouvabilité dans des systèmes où la multiplication n'est pas disponible ou est restreinte (référence à Buss, 1997 ; Friedman, 1976).

L'auteur déclare explicitement une modestie concernant les implications plus larges :

L'article ne prétend pas dériver l'interface de support de Zeckendorf elle-même à partir de principes d'addition uniquement, conjecturant qu'une telle dérivation pourrait n'exister.
Il ne prétend pas fournir une caractérisation simple sous forme fermée de l'image de $\pi_{CL}$ ; la procédure de décision est le test de point fixe basé sur le support.
La contribution principale est la construction explicite d'un dispositif « sans retenue » et la vérification de ses propriétés, rendant l'image et sa structure géométrique directement inspectables pour l'analyse théorique.

Le travail est présenté comme un dispositif arithmétique fondamental plutôt que comme une structure de données pratique pour l'informatique générale, soulignant son utilité théorique en logique et en proof-théorie.