🔢 mathematics

Additive Bases from Primitive Dyck Words: Regular Underapproximations, Motzkin Coding, and Digit Lifting

Cet article établit que tout entier pair positif peut être représenté comme une somme d'au plus six mots de Dyck primitifs, à l'exception d'un ensemble fini d'entiers (incluant 46, qui en nécessite huit) et du seuil asymptotique net de 848, en exploitant une nouvelle connexion entre les chemins de Dyck et le codage de Motzkin pour prouver des théorèmes de levée de chiffres et des bornes de génération.

Auteurs originaux : Takayuki Kuriyama

Publié 2026-07-28

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Takayuki Kuriyama

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

Imaginez que vous soyez un détective essayant de résoudre un type très spécifique d'énigme numérique. Dans le monde des mathématiques, il existe une branche appelée théorie additive des nombres, qui pose une question simple mais complexe : peut-on construire tous les nombres d'un certain groupe en additionnant quelques nombres « blocs de construction » spéciaux ? Considérez cela comme un jeu où vous avez un ensemble limité de briques Lego, et vous voulez savoir si vous pouvez construire toutes les hauteurs de tours possibles en utilisant uniquement ces briques. Parfois, vous n'aurez besoin que de deux briques ; d'autres fois, vous en aurez besoin de dix. L'« ordre » du jeu est le nombre maximum de briques dont vous aurez jamais besoin pour construire n'importe quelle tour.

Pour jouer à ce jeu, les mathématiciens de cette histoire utilisent un ensemble de blocs de construction très spécifique. Ces blocs sont des nombres qui, lorsqu'ils sont écrits en binaire (le langage informatique composé de 0 et de 1), ressemblent à des parenthèses parfaitement équilibrées. En mathématiques, on appelle cela des mots de Dyck. Par exemple, 1100 est un bloc valide car si vous traitez 1 comme une étape « vers le haut » et 0 comme une étape « vers le bas », le chemin monte deux fois et descend deux fois, sans jamais descendre en dessous de la ligne de départ. Les auteurs se concentrent sur un sous-ensemble spécial de ces blocs appelés primitifs, qui sont les pièces « atomiques » qui ne peuvent pas être décomposées en couples plus petits et équilibrés. La grande question qu'ils abordent est la suivante : quel est le nombre maximum de blocs primitifs que vous devez additionner pour créer n'importe quel nombre pair ?

Ce document est un chef-d'œuvre de résolution de ce puzzle en mélangeant deux outils mathématiques différents. Les auteurs ont découvert que ces blocs binaires ont une relation secrète avec un autre type de chemin appelé chemin de Motzkin, qui leur permet de traduire le problème dans un langage différent (base 4) où il devient beaucoup plus facile à résoudre. Ils ont prouvé que, bien que la plupart des nombres pairs puissent être construits avec seulement une poignée de ces blocs, il existe un petit groupe d'êtres obstinés qui sont beaucoup plus difficiles à construire. Plus précisément, ils ont trouvé que le nombre 46 est le cas le plus difficile, nécessitant huit blocs, tandis que quelques autres en nécessitent sept. Cependant, ils ont également prouvé qu'une fois passé le nombre 848, vous n'aurez jamais besoin de plus de six blocs pour construire n'importe quel nombre pair, peu importe sa taille. C'est l'histoire de la recherche des « scénarios du pire » dans un vaste univers de nombres et de la preuve exacte de l'endroit où le chaos s'arrête et où l'ordre commence.

L'histoire des équilibreurs binaires

Plongeons dans l'aventure. Les auteurs, dirigés par Takayuki Kuriyama, étudient un ensemble de nombres qui proviennent d'un langage de chaînes binaires équilibrées. Imaginez que vous avez une chaîne de lumières, certaines rouges (1) et d'autres bleues (0). Un « mot de Dyck » est une chaîne où vous avez le même nombre de lumières rouges et bleues, et si vous comptez de gauche à droite, vous n'avez jamais plus de bleues que de rouges à aucun moment. C'est comme une danse où vous ne pouvez pas quitter la scène avant d'avoir fait correspondre chaque pas vers le haut avec un pas vers le bas.

Les auteurs s'intéressent aux danseurs « primitifs ». Ce sont les chaînes qui ne reviennent à la ligne de départ (hauteur zéro) qu'à la toute fin. Si une chaîne revient à zéro à mi-chemin, c'est juste deux plus petites danses collées ensemble, et non une danse primitive. Ils traitent ces chaînes comme des nombres (en les lisant en binaire) et demandent : combien de ces nombres primitifs devons-nous additionner pour obtenir n'importe quel nombre pair ?

Le code secret : de la binaire à la base 4
Le mouvement brillant de cet article est de réaliser que ces chaînes binaires possèdent une structure cachée. Si vous regroupez les bits par paires (00, 01, 10, 11), ils agissent comme des chiffres dans un système en base 4 (0, 1, 2, 3). Les auteurs ont trouvé une carte parfaite : chaque nombre de Dyck primitif (sauf le plus petit, qui est 2) correspond à un nombre en base 4 qui commence par un 3, se termine par un 0, et possède un mot « Motzkin » au milieu.

Considérez un mot de Motzkin comme un chemin qui peut monter, descendre ou rester plat, mais qui ne descend jamais en dessous du sol. Cette connexion est la « pierre de Rosette » de l'article. Elle permet aux auteurs de traduire un problème difficile sur des chaînes binaires complexes en un problème plus propre sur des nombres en base 4 et ces chemins de marche plate. Cette traduction révèle que l'ensemble des nombres qu'ils étudient est « numériquement clos », ce qui signifie que si vous avez un nombre dans l'ensemble, vous pouvez souvent en générer de nouveaux en ajoutant des chiffres spécifiques.

La stratégie à deux voies
Pour résoudre le puzzle, les auteurs utilisent une attaque astucieuse à deux volets, en traitant les nombres pairs selon leur comportement lorsqu'ils sont divisés par 4.

La voie « facile » (multiples de 4) : Pour les nombres qui sont parfaitement divisibles par 4, les auteurs utilisent une « sous-approximation régulière ». C'est une façon sophistiquée de dire qu'ils ont trouvé un sous-ensemble plus simple et prévisible des nombres, qui est facile à manipuler. Ils ont prouvé que cet ensemble plus simple est assez puissant pour construire tous les grands multiples de 4 en utilisant seulement six blocs.
La voie « délicate » (nombres de 2 mod 4) : Pour les nombres qui laissent un reste de 2 lorsqu'ils sont divisés par 4 (comme 6, 10, 14), l'ensemble plus simple n'est pas suffisant. Ici, ils utilisent toute la puissance de la famille codée par « Motzkin ». Ils ont prouvé que cette famille plus large et plus complexe peut construire ces nombres en utilisant seulement cinq blocs.

La magie du « levage »
Comment savent-ils que cela fonctionne pour tous les grands nombres, et pas seulement pour ceux qu'ils ont vérifiés ? Ils utilisent une technique appelée levage de chiffres (digit lifting). Imaginez que vous avez une petite échelle qui peut atteindre une certaine hauteur. Les auteurs ont prouvé un théorème qui dit : si vous pouvez construire une plage continue de nombres avec un certain nombre de blocs, vous pouvez « lever » cette capacité pour construire tous les nombres plus grands en ajoutant simplement des chiffres spécifiques aux extrémités des blocs. C'est comme avoir une règle magique qui dit : « Si vous pouvez construire une tour de hauteur 100, vous pouvez automatiquement construire des tours de hauteur 400, 401, 402, et ainsi de suite. » Cela leur permet de prendre une liste finie de nombres vérifiés et de prouver que le modèle se maintient pour l'éternité.

Les résultats : les nombres obstinés
Après avoir mis en place leurs outils, les auteurs se sont mis au travail pour classer les exceptions. Ils ont découvert que, bien que la plupart des nombres pairs soient faciles à construire, il existe une liste spécifique de nombres « obstinés » qui nécessitent plus de six blocs.

Le champion de la difficulté : Le nombre 46 est le plus difficile de tous. Il ne peut pas être construit avec sept blocs ou moins ; il nécessite strictement huit.
Les dauphins : Il y a dix autres nombres qui nécessitent sept blocs : 34, 44, 98, 154, 198, 202, 206, 838, 842 et 846.
Le seuil : Les auteurs ont prouvé que 848 est le nombre magique. Chaque nombre pair de 848 et au-delà peut être construit avec six blocs ou moins.

Ils n'ont pas seulement deviné ces nombres ; ils ont utilisé des calculs informatiques exacts pour vérifier chaque cas jusqu'au seuil et ont utilisé leurs preuves mathématiques pour montrer que cela se maintient pour l'infini.

Pourquoi cela importe
Cet article est un bel exemple de la façon dont différents domaines des mathématiques — l'informatique (langages et automates), la combinatoire (chemins et arbres) et la théorie des nombres (addition) — peuvent danser ensemble. Les auteurs n'ont pas seulement trouvé une liste de nombres ; ils ont construit un cadre. Ils ont montré que même pour un ensemble de nombres défini par un motif complexe et non répétitif (un langage « contextuel »), on peut trouver un motif simple et répétitif (un langage « régulier ») qui couvre la majeure partie du terrain, puis utiliser la pleine complexité pour combler les lacunes.

Ils ont également découvert que l'« ordre » du jeu change selon les règles. Si l'on ne regarde que les multiples de 4, on n'a besoin que de 5 blocs. Mais si l'on inclut les nombres de 2 mod 4, l'exigence passe à 6. Et si l'on considère le pire scénario absolu (incluant le nombre 46), on en a besoin de 8.

En fin de compte, l'article fournit une carte complète. Nous savons exactement quels nombres sont les perturbateurs, nous connaissons le seuil exact où les problèmes s'arrêtent, et nous disposons d'un algorithme constructif (une recette étape par étape) pour construire n'importe quel grand nombre pair en utilisant ces blocs binaires spéciaux. Cela transforme un problème d'apparence chaotique en un système parfaitement ordonné, prouvant que même dans le monde des nombres abstraits, il existe toujours un motif qui attend d'être découvert.

Résumé Technique : Bases Additives issues des Mots de Dyck Primitifs

Énoncé du Problème
Cet article étudie les représentations additives des entiers pairs positifs en utilisant des sommandes tirées de l'ensemble $N_pD$ . Cet ensemble est composé de zéro et des valeurs entières des mots de Dyck primitifs interprétés comme des nombres binaires. Un mot de Dyck est une séquence équilibrée de 1 (montées) et de 0 (descentes) ; un mot est dit primitif si son chemin associé ne revient à la hauteur zéro qu'à la toute fin. La question centrale est de déterminer l'ordre additif de cet ensemble : spécifiquement, le plus petit entier $h$ tel que tout entier pair suffisamment grand puisse être exprimé comme une somme d'au plus $h$ éléments de $N_pD$ , et de classifier l'ensemble exact des entiers « exceptionnels » qui nécessitent plus d'un certain nombre de sommandes.

Méthodologie
Les auteurs emploient une approche hybride combinant la théorie des langages formels, la théorie combinatoire des nombres et des algorithmes constructifs :

Codage par Blocs Positionnels : L'intuition structurelle centrale est une bijection entre les mots de Dyck primitifs et les mots de Motzkin à deux couleurs via un codage par blocs en base 4. En associant des paires de chiffres binaires consécutifs, les auteurs projettent les mots de Dyck primitifs (excluant le mot « 10 ») vers des mots en base 4 de la forme $3w0$ , où $w$ est un mot de Motzkin à deux couleurs. Cela permet aux auteurs de traduire le langage de Dyck (non régulier) vers une structure compatible avec l'arithmétique positionnelle en base 4.
Sous-approximation Régulière : Pour traiter les entiers congrus à $0 \pmod 4$ , les auteurs construisent une sous-approximation régulière explicite du langage de Dyck primitif. Ce sous-ensemble, défini par l'expression régulière $11(01|10)^*00$ , correspond aux mots de Motzkin composés uniquement des chiffres $\{1, 2\}$ . Ce sous-ensemble régulier est amenable aux méthodes d'automates finis et fournit une couverture pour les multiples de 4.
Élévation de Chiffre et Propagation (Digit Lifting) : L'article introduit un Théorème d'Élévation de Chiffre par Intervalle. Ce théorème prouve que si un ensemble $A$ satisfait une propriété de clôture (spécifiquement $4A + \{1, 2\} \subseteq A$ ), alors un intervalle fini de nombres représentables peut être étendu de manière récursive à une queue infinie. Cela permet aux auteurs de convertir des certificats de calcul finis (sommes d'ensembles de petits nombres) en preuves de représentabilité pour tous les entiers suffisamment grands.
Certificats Finis et Recherche Exhaustive : La preuve repose sur l'arithmétique entière exacte pour calculer les sommes d'ensembles de générateurs de petite taille. Les auteurs vérifient des intervalles spécifiques où les sommes d'ensembles de la famille régulière (pour les multiples de 4) et de la famille codée par Motzkin (pour les entiers $\equiv 2 \pmod 4$ ) se chevauchent suffisamment pour déclencher la propagation par élévation de chiffre.

Contributions Clés

Caractérisation Exacte en Base 4 : L'article établit l'identité $DP = \{10\} \cup \phi(3 \cdot \text{Motz} \cdot 0)$ , où $\phi$ est un morphisme uniforme mappant les chiffres en base 4 vers des paires binaires. Cela fournit un lien structurel précis entre les mots de Dyck primitifs et les chemins de Motzkin qui préserve les valeurs positionnelles canoniques.
Classification des Entiers Exceptionnels : Les auteurs classifient complètement les entiers pairs positifs nécessitant plus de six sommandes.
- L'entier 46 est l'unique entier pair nécessitant huit sommandes.
- Les entiers 34, 44, 98, 154, 198, 202, 206, 838, 842 et 846 nécessitent exactement sept sommandes.
- Tout autre entier pair positif nécessite au plus six sommandes.
Seuils Précis : Le papier identifie 848 comme le seuil asymptotique net : tout entier pair $N \ge 848$ est une somme d'au plus six nombres de Dyck primitifs.
Analyse de l'Ordre Asymptotique : Les auteurs distinguent l'« ordre relatif » (pour tous les entiers pairs) de l'« ordre asymptotique » (pour des entiers suffisamment grands).
- L'ensemble $N_pD$ est une base additive relative d'ordre 8 pour les entiers pairs (en raison de l'exception à 46).
- L'ordre asymptotique relatif est de 6.
- La famille « divisée par deux » $P$ (où $N_pD = \{0, 2\} \cup 4P$ ) a un ordre additif asymptotique de 5.
Algorithmes Constructifs : Le mécanisme d'élévation de chiffre produit un algorithme constructif qui génère des représentations pour de grands entiers en $O(\log n)$ étapes récursives, convertissant des noyaux de représentation finis en queues infinies.

Résultats et Signification
L'article démontre que bien que le langage des mots de Dyck primitifs soit déterministe et contextuel libre (et donc non régulier), ses propriétés additives peuvent être analysées efficacement en séparant le problème en classes de résidus modulo 4.

Pour $N \equiv 0 \pmod 4$ , une sous-approximation régulière suffit pour prouver que six sommandes sont éventuellement suffisantes.
Pour $N \equiv 2 \pmod 4$ , la preuve nécessite la pleine puissance de la famille codée par Motzkin et une couverture à cinq sommandes, ce qui, combiné à la nécessité d'utiliser un nombre impair de la sommande '2', porte le seuil asymptotique à six.

La signification de ce travail réside dans l'application réussie de sous-approximations régulières à un langage non régulier pour résoudre un problème de théorie additive des nombres. Il fournit un exemple concret où l'interaction entre la structure du langage formel (Dyck vs Motzkin) et les systèmes de numération positionnelle produit des bornes nettes et calculables. Les auteurs notent explicitement que la borne de six est asymptotiquement optimale, car la séquence $N_k = 10 \cdot 4^{k+1} - 6$ nécessite exactement six sommandes pour tout $k \ge 2$ .

Tous les certificats finis et la classification des valeurs exceptionnelles sont vérifiés par des programmes complémentaires utilisant l'arithmétique entière exacte, garantissant la reproductibilité des résultats. L'article conclut que 848 est le plus petit entier pair tel que tous les entiers pairs plus grands soient représentables par au plus six nombres de Dyck primitifs, tandis que 46 demeure l'unique exception nécessitant huit.

L'histoire des équilibreurs binaires

Articles similaires