💻 computer science

Recursive Prime Factorizations: Dyck Words as Numbers

Cet article propose un système de numération non positionnel basé sur les mots de Dyck, issu d'une factorisation première récursive, qui permet de représenter de manière unique les nombres naturels et rationnels tout en explorant des langages complets où chaque mot de Dyck correspond à un nombre.

Auteurs originaux : Ralph L. Childress

Publié 2026-02-18

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ralph L. Childress

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

🎈 L'Arbre de Noël des Nombres : Une nouvelle façon de compter

Imaginez que vous essayez de décrire un nombre, comme le 520, à un ami.
Dans notre système habituel (décimal), vous dites "cinq cent vingt". Mais ce système est un peu arbitraire. Pourquoi "cinq", "deux", "zéro" ? Pourquoi la base 10 ? C'est comme si nous avions décidé que tous les arbres devaient avoir 10 branches parce que nous avons 10 doigts. C'est pratique, mais ce n'est pas la vraie nature de l'arbre.

L'auteur de ce papier, Ralph Childress, se demande : "Et si on décrivait les nombres en utilisant leur véritable ADN, c'est-à-dire leurs facteurs premiers, sans utiliser de base ni d'addition ?"

Il a découvert une méthode géniale qui transforme les nombres en mots faits uniquement de parenthèses, un peu comme des poupées russes ou des nids d'oiseaux.

1. Le Système des "Poupées Russes" (Les Nombres Naturels)

Dans notre système habituel, pour écrire 520, on fait : $5 \times 100 + 2 \times 10 + 0$ . C'est compliqué, il faut additionner.

Dans le système de Ralph, on regarde comment 520 est construit avec des nombres premiers (2, 3, 5, 7, 11...).
$520 = 2^3 \times 5^1 \times 13^1$ .

Mais Ralph va plus loin : il dit que les exposants (les petits chiffres en haut comme le 3 ou le 1) sont aussi des nombres ! Donc, il faut décomposer ces nombres aussi.

Le 3 est $3^1$ .
Le 1 est... un cas spécial.

Il transforme tout cela en une suite de parenthèses.

0 devient un vide (rien du tout).
1 devient () (une paire de parenthèses vide).
2 devient (()) (une paire contenant 1).
3 devient ()(()) (une paire vide, puis une paire contenant 1).

Le nombre 520 devient une longue chaîne de parenthèses : (()(()))()(())()()(().

L'analogie : Imaginez que chaque nombre est une boîte.

Si la boîte est vide, c'est le 0.
Si la boîte contient une petite boîte vide, c'est le 1.
Si la boîte contient une boîte qui contient une boîte vide, c'est le 2.
Si la boîte contient plusieurs boîtes collées les unes aux autres, c'est un nombre composé (comme 6, qui est 2 fois 3).

La beauté de ce système, c'est que vous n'avez besoin que de deux symboles : ( et ). Pas de chiffres, pas de base 10, pas d'addition. Juste la structure des boîtes.

2. Le Secret des Parenthèses : Le Langage Dyck

Ces suites de parenthèses ne sont pas n'importe quelles suites. Elles doivent être bien équilibrées (comme des parenthèses en mathématiques : chaque ( doit avoir un ) correspondant). En informatique, on appelle cela un "Mot de Dyck".

Ralph a prouvé que :

Chaque nombre entier (0, 1, 2, 3...) a une seule et unique façon d'être écrit avec ces boîtes.
On peut toujours reconstituer le nombre original en regardant la structure des boîtes. C'est comme lire un code-barres qui se lit de l'intérieur vers l'extérieur.

3. L'Extension Magique : Les Nombres "Superrationnels"

C'est ici que ça devient vraiment fou. Ralph se demande : "Et si on permettait des boîtes un peu plus étranges ?"

Dans son système de base, une boîte vide () signifie "1". Mais il a trouvé un moyen d'utiliser une petite astuce pour signifier "moins".

Si vous ajoutez une petite boîte vide à la fin d'une phrase, cela change le signe du nombre.
() = 1
()() = -1 (une boîte vide, puis une autre qui agit comme un signe moins).

Grâce à cette petite modification, son système ne s'arrête plus aux nombres entiers. Il peut maintenant représenter :

Les fractions (comme 1/2).
Les racines carrées (comme $\sqrt{2}$ ).
Même certains nombres infinis et mystérieux (comme $2^{\sqrt{2}}$ ).

L'analogie : Imaginez que votre système de boîtes était un jeu de construction avec des briques rouges et bleues. Au début, vous ne pouviez construire que des murs solides (nombres entiers). Ralph a découvert qu'en ajoutant une petite brique "invisibile" à la fin, vous pouviez maintenant construire des ponts, des arches et des structures flottantes (fractions, racines, nombres transcendants), sans ajouter aucun nouveau type de brique. Vous utilisez toujours les mêmes deux symboles !

4. Pourquoi est-ce important ? (La leçon pour les ordinateurs)

Pourquoi s'embêter avec des parenthèses au lieu de nos chiffres ?

Pas de "Biais" : Notre système décimal cache la vraie nature des nombres (pourquoi 3 divise-t-il 9 ?). Le système de Ralph expose la structure mathématique pure.
Pour l'Intelligence Artificielle : Les chercheurs essaient d'entraîner des IA (comme les grands modèles de langage) à comprendre les mathématiques. Ce papier suggère que si on entraîne une IA avec ces "mots de parenthèses", elle pourrait mieux comprendre la logique profonde des nombres, car le langage lui-même est la logique mathématique. C'est comme apprendre à un enfant à cuisiner en lui donnant les ingrédients bruts plutôt que des recettes toutes faites.
Compression : Ces mots pourraient aider à compresser des données mathématiques d'une manière très efficace, car ils éliminent le "bruit" des bases arbitraires.

En résumé

Ralph Childress nous propose de voir les nombres non pas comme des étiquettes sur un étagère (1, 2, 3...), mais comme des arbres généalogiques ou des boîtes emboîtées.

Avant : Le nombre 520 est juste un mot "cinq-cent-vingt".
Avec Ralph : Le nombre 520 est une histoire complexe de boîtes imbriquées qui raconte exactement comment il est fabriqué à partir de ses briques fondamentales (les nombres premiers).

C'est un système élégant, purement logique, qui utilise seulement deux symboles pour décrire l'univers des nombres, des entiers simples jusqu'aux nombres les plus complexes et mystérieux. C'est comme si on avait trouvé la langue secrète que les nombres utilisent pour se parler entre eux.

1. Problématique

L'auteur identifie deux limitations fondamentales des systèmes de numération positionnels traditionnels (comme le système décimal) :

Arbitraire de la base : Le choix d'une base (ex: 10) est conventionnel et masque les propriétés intrinsèques des nombres. Les motifs mathématiques (comme la divisibilité par 3 en base 10) dépendent de cette base et ne sont pas universels.
Complexité opérationnelle : L'évaluation d'un nombre en notation positionnelle nécessite trois opérations distinctes : l'exponentiation, la multiplication et l'addition.
Absence de lien structurel : Les représentations positionnelles ne reflètent pas directement la structure arithmétique fondamentale des nombres, à savoir leur décomposition en facteurs premiers.

L'objectif est de concevoir un système de numération non positionnel, basé uniquement sur la factorisation en nombres premiers, qui élimine le besoin d'une base arbitraire et de l'addition pour l'évaluation, tout en utilisant un alphabet minimal (deux symboles).

2. Méthodologie

L'auteur propose une approche fondée sur la théorie des langages formels et la récursivité :

Factorisation Primaire Minimale Parenthésée (MPPPF) : Pour un nombre $n$ , on écrit sa décomposition en facteurs premiers sous forme exponentielle, en incluant les puissances nulles pour tous les nombres premiers consécutifs jusqu'au plus grand facteur premier. Chaque terme exponentiel est entouré de parenthèses.
Récursivité : Les exposants de cette factorisation sont eux-mêmes représentés par leur propre factorisation récursive. Ce processus se poursuit jusqu'à ce que tous les exposants soient réduits à 0 ou 1.
Encodage Dyck : Une fois la structure récursive établie, tous les symboles (nombres premiers, opérateurs) sont supprimés, ne laissant que les parenthèses. Le résultat est un mot du langage de Dyck (séquences de parenthèses équilibrées).
Définitions formelles :
- 0 est représenté par la chaîne vide ( $\epsilon$ ).
- 1 est représenté par ().
- Pour $n > 1$ , la représentation est la concaténation de parenthèses entourant les représentations des exposants.
Extension Superrationnelle : L'auteur étend le système pour inclure les nombres rationnels, certains irrationnels algébriques et transcendants. Cela est réalisé en permettant des exposants négatifs (via une paire de parenthèses vide supplémentaire à la fin d'un mot pour indiquer le signe négatif) et en généralisant la définition de l'ensemble des nombres.

3. Contributions Clés

A. Le Système RPF Naturel Minimal ( $RPFNr_{min}$ )

Langage : $D_{rmin}$ , un sous-ensemble propre du langage de Dyck $D$ .
Propriété : Il existe une bijection (correspondance un-à-un) entre l'ensemble des nombres naturels $\mathbb{N}$ et $D_{rmin}$ .
Évaluation : Une fonction d'évaluation $\alpha_{Nrmin}$ permet de reconstruire le nombre entier à partir du mot de Dyck en interprétant la profondeur et la structure des parenthèses comme des puissances de nombres premiers.
Théorème : $D_{rmin}$ est un langage context-free (défini par une grammaire et un automate fini déterministe qui rejette les suffixes )() et les sous-chaînes )())).

B. Le Système RPF Superrationnel ( $RPFSr_{min}$ )

Extension : Le système est étendu pour représenter l'ensemble $S$ des « nombres superrationnels », qui inclut $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ , certains irrationnels (ex: $\sqrt{2}$ ) et transcendants (ex: $2^{\sqrt{2}}$ ).
Mécanisme : L'ajout d'une opération de négation permet d'encoder les exposants négatifs. La représentation de $-1$ est ()().
Langage : $D_{rqmin}$ (quasi-minimal), un sous-ensemble de $D$ où les mots peuvent contenir au plus une « inflation » (une paire de parenthèses vide supplémentaire) par rapport à la forme minimale.
Unicité : Contrairement aux systèmes positionnels où $01$ et $1$ sont équivalents, ici, chaque nombre dans $S$ a une représentation unique et minimale dans $D_{rqmin}$ .

C. Interprétations Dyck-Complètes

L'auteur définit des interprétations où le langage sous-jacent est le langage de Dyck complet $D$ (toutes les séquences de parenthèses équilibrées).
Dans ce cadre, la fonction d'évaluation n'est plus injective : plusieurs mots de Dyck peuvent représenter le même nombre (phénomène d'« inflation »). Cela permet d'étudier la structure du langage de Dyck lui-même à travers la lentille de l'arithmétique.

4. Résultats et Propriétés Mathématiques

Représentation sans base : Le système ne nécessite aucune base numérique. La structure du mot reflète directement la factorisation en nombres premiers.
Évaluation sans addition : L'évaluation d'un mot ne nécessite que la multiplication et l'exponentiation (itération de la multiplication).
Correspondance avec les nombres premiers : La $k$ -ème paire de parenthèses imbriquée correspond à la $k$ -ème nombre premier.
Complexité et Algorithmes :
- Un algorithme est proposé pour extraire la factorisation première d'un nombre de Dyck.
- La complexité temporelle est dominée par la taille de la sortie (la longueur du mot de Dyck), qui croît logarithmiquement avec la valeur du nombre, mais peut être plus longue que la représentation décimale pour les grands nombres.
Stripes (Bandes) : L'analyse des mots de Dyck par longueur (semilength) révèle des motifs intéressants, notamment des séquences liées à la tétration en base 2 et aux nombres premiers.

5. Signification et Perspectives de Recherche

Théorie des Langages et Arithmétique : Ce travail établit un pont profond entre la théorie des langages formels (grammaires context-free, automates) et la théorie des nombres. Il suggère que la structure de l'arithmétique peut être étudiée via la syntaxe des langages formels.
Apprentissage Automatique (AI) : L'auteur suggère que les mots de Dyck générés par ce système (surtout la version superrationnelle qui encode l'identité des nombres premiers) pourraient servir de corpus pour entraîner des réseaux de neurones (Transformers). Contrairement aux factorisations « lossy » (qui oublient l'identité des premiers), cette représentation est « lossless » et pourrait améliorer la capacité des modèles à apprendre les règles de l'arithmétique.
Compression : L'utilisation d'algorithmes de compression basés sur la grammaire (comme Re-Pair) sur des séquences de mots de Dyck pourrait révéler des motifs cachés dans les suites de nombres.
Cryptographie : La capacité à caractériser des sous-ensembles de nombres (comme les semi-premiers sans facteur carré) via des expressions régulières sur les mots de Dyck ouvre de nouvelles perspectives pour l'analyse cryptographique.

En résumé, Childress propose un système de numération élégant et théoriquement riche qui remplace la notion de « base » par la structure récursive des nombres premiers, offrant un nouvel angle d'attaque pour l'étude des motifs numériques et leur application potentielle en informatique théorique et en intelligence artificielle.