Beatty solutions of almost Golomb equations

Cet article démontre l'existence et l'unicité d'une solution de type suite de Beatty inhomogène (de pente $1/\sqrt{2}$) pour l'équation presque de Golomb d'ordre 2, distincte de la solution régulière connue, et établit que cette solution s'inscrit dans une famille continue vérifiant une équation triple imbriquée pour un intervalle précis de paramètres.

L'essentiel

Imaginez que vous essayez de construire une tour de briques, mais avec une règle très étrange : pour savoir quelle taille doit avoir la brique numéro 100, vous devez regarder la somme des tailles des deux briques juste avant elle (la 99 et la 98), puis chercher cette somme dans votre tour pour voir quel numéro de brique s'y trouve. C'est ce qu'on appelle l'équation de Golomb.

Normalement, il n'y a qu'une seule façon de construire cette tour : la méthode "avide" (greedy). C'est comme si vous preniez toujours la plus petite brique possible qui respecte la règle. C'est une solution très prévisible, un peu comme un train qui suit des rails fixes.

Mais ce papier, écrit par Benoît Cloitre, découvre quelque chose de magique : il existe une deuxième façon de construire cette tour, complètement différente, qui fonctionne aussi parfaitement !

Voici l'explication simple de cette découverte, avec quelques images pour mieux comprendre :

1. La Tour "Avide" (La solution connue)

Imaginez un enfant qui construit une tour brique par brique. À chaque étape, il se demande : "Quelle est la plus petite brique que je peux poser ici sans casser la règle ?".

• Le résultat : La tour grandit de manière un peu saccadée. Elle oscille, elle hésite. C'est une structure "locale" : la brique actuelle dépend uniquement de ce qui est juste à côté.
• L'analogie : C'est comme marcher dans un labyrinthe en suivant toujours le mur de gauche. Vous finirez par sortir, mais votre chemin sera un peu zigzaguant et imprévisible sur le long terme.

2. La Tour "Beatty" (La nouvelle découverte)

Le papier révèle qu'il existe une autre tour, tout aussi valide, mais qui est construite avec une règle totalement différente. Au lieu de regarder juste à côté, cette tour suit une pente invisible et irrationnelle.

• Le secret : Cette tour suit une pente de $1/\sqrt{2}$ (environ 0,707). C'est comme si vous dessiniez une ligne droite sur un papier quadrillé et que vous posiez vos briques exactement là où cette ligne coupe les lignes horizontales.
• L'analogie : Imaginez que vous lancez une balle de tennis sur une table de ping-pong avec un angle très précis et irrationnel. La balle rebondit partout, mais son trajet est parfaitement régulier et prévisible à long terme. C'est ce qu'on appelle une séquence de Beatty.
• La différence clé : Au début, les deux tours (l'avide et la Beatty) se ressemblent énormément. Elles sont identiques jusqu'à la brique numéro 11. Mais à la brique 12, elles divergent. L'une met une brique de taille 8, l'autre une de taille 9. Pourtant, les deux respectent la règle magique ! C'est comme si deux chemins différents menaient au même sommet.

3. La Famille des Tours "Tropiques" (L'intervalle continu)

Le papier va encore plus loin. Il ne s'agit pas seulement de deux solutions, mais d'une famille continue de solutions.

• Imaginez que la solution "Beatty" parfaite est un point précis sur une ligne. Le papier montre que si vous déplacez légèrement ce point (en changeant un petit paramètre, comme une vis de réglage), vous obtenez une nouvelle tour qui respecte une règle un peu plus faible (une règle "triple").
• C'est comme un orchestre : la solution parfaite est un accord parfait. Mais si vous accordez légèrement les instruments dans une certaine fourchette, l'orchestre joue encore une musique harmonieuse, même si ce n'est plus l'accord parfait initial.

4. Pourquoi est-ce important ? (Le mystère des carrés)

Les auteurs ont testé cette idée pour différentes tailles de fenêtres (pas seulement 2 briques, mais 3, 5, etc.).

• Le miracle : Pour des nombres comme 2, 3, 5, 9, 25 (des carrés impairs), cette "pente magique" fonctionne parfaitement.
• Le blocage : Pour les carrés pairs (comme 4, 16), cela ne marche pas. C'est comme si la physique de l'univers changeait selon que le nombre est pair ou impair.
• L'outil magique : Pour prouver tout cela, ils ont utilisé un ordinateur très puissant (appelé Walnut) qui vérifie des millions de cas en utilisant un système de numération spécial (Ostrowski), un peu comme si on traduisait les nombres en une langue secrète où les règles deviennent évidentes.

En résumé

Ce papier nous dit que les mathématiques cachent souvent des mondes parallèles.

1. Il y a la solution "égoïste" (la plus petite possible), qui est locale et un peu chaotique.
2. Il y a la solution "harmonieuse" (la pente irrationnelle), qui est globale, fluide et basée sur des nombres comme $\sqrt{2}$.
3. Et il y a tout un continuum entre les deux, où l'on peut glisser d'une solution à l'autre sans casser la règle, tant que l'on reste dans une zone précise.

C'est une belle démonstration que même dans des règles très strictes et simples, la nature peut trouver plusieurs façons d'être cohérente, un peu comme un écrivain qui peut raconter la même histoire de deux manières totalement différentes, toutes deux vraies.

Résumé technique

1. Problématique et Contexte

L'article s'intéresse aux séquences presque de Golomb d'ordre $r$. Ces séquences sont définies comme les suites d'entiers positifs non décroissantes $a(n)$ satisfaisant l'équation fonctionnelle implicite :
$$a\left(\sum_{j=0}^{r-1} a(n-j)\right) = n, \quad \text{pour } n \ge 1$$
avec $a(k)=0$ pour $k<1$.

Pour $r=2$, cette équation devient $a(a(n) + a(n-1)) = n$.

• La solution greedy (avide) : Il existe une solution unique obtenue par construction inductive (choisir le plus petit entier possible). Pour $r=2$, cette suite est 2-régulière (au sens d'Allouche et Shallit), présente une croissance linéaire oscillante ($a(n)/n$ oscille entre $2/3$ et $3/4$) et ne converge pas.
• La question centrale : L'équation implicite, qui contraint la valeur de $a$ à une position dépendant de la suite elle-même, admet-elle d'autres solutions monotones non triviales ? L'article démontre l'existence d'une deuxième solution, de nature fondamentalement différente, basée sur les suites de Beatty.

2. Méthodologie

L'auteur utilise une combinaison d'outils mathématiques variés pour analyser l'équation :

• Analyse asymptotique et heuristique : En supposant $a(n) \sim cn$, l'équation impose $2c^2 = 1$, d'où $c = 1/\sqrt{2}$. Cela suggère une solution de type Beatty $a(n) = \lfloor n/\sqrt{2} + d \rfloor$.
• Théorie des suites de Sturm et mots mécaniques : La structure des différences premières $\Delta(n) = a(n+1) - a(n)$ est liée à des rotations irrationnelles sur le cercle unité.
• Systèmes de numération d'Ostrowski : L'analyse fine des erreurs d'arrondi et des propriétés de la suite repose sur la représentation des entiers dans la base d'Ostrowski associée à l'irrationnel $1/\sqrt{2}$.
• Preuves formelles assistées par ordinateur : Pour les cas généraux ($r$ non carré), l'auteur utilise le théorème-proveur Walnut pour certifier l'identité sur des intervalles finis et vérifier des bornes de discrépance.
• Théorie des jeux et nombres de Pell : Les liens avec le jeu de Wythoff et les nombres de Pell (convergents de $\sqrt{2}$) sont exploités pour étudier les bifurcations et les intervalles de validité.

3. Contributions et Résultats Clés

A. Existence d'une solution de Beatty (Théorème 1)

Pour l'ordre $r=2$, l'article prouve l'existence d'une solution monotone unique de type suite de Beatty inhomogène :
$$a(n) = \left\lfloor \frac{n}{\sqrt{2}} + \frac{\sqrt{2}}{2} \right\rfloor$$
Cette suite satisfait exactement l'équation $a(a(n) + a(n-1)) = n$.

• Différence avec la solution greedy : Les deux suites coïncident jusqu'à $n=11$, puis divergent. La solution greedy est 2-régulière (structure locale, binaire), tandis que la solution Beatty est Sturmienne (structure globale, liée à l'irrationalité de $\sqrt{2}$).
• Unicité : Cette solution est la seule suite de Beatty satisfaisant l'équation forte (3).

B. Famille continue de solutions faibles (Théorèmes 2 et 3)

En considérant l'équation triple-nestée (plus faible) :
$$a(a(a(n) + a(n-1))) = a(n)$$
l'auteur démontre qu'il existe un intervalle continu de paramètres $d$ pour lesquels la suite $a_d(n) = \lfloor n/\sqrt{2} + d \rfloor$ est solution.

• L'intervalle $I$ : $d \in [\frac{\sqrt{2}}{2}, 2(\sqrt{2}-1)]$.
• Mécanisme d'absorption : Pour $d$ dans cet intervalle (sauf l'extrémité gauche), l'identité forte $a(f(n))=n$ échoue parfois, mais l'erreur est absorbée par la composition externe $a(\cdot)$ car la suite reste non décroissante avec des sauts de 0 ou 1.

C. Généralisation aux ordres $r$ (Section 9)

L'article généralise ces résultats à tout ordre $r \ge 2$ :

• Cas des carrés impairs ($r=s^2$, $s$ impair) : L'identité $a_r(S_r(n)) = n$ est prouvée pour la suite de Beatty $a_r(n) = \lfloor n/s + s/2 \rfloor$.
• Cas des carrés pairs ($r=(2m)^2$) : L'identité échoue systématiquement (la suite donne $n+1$ au lieu de $n$).
• Cas non-carrés ($r$ non carré) : Une conjecture forte est émise selon laquelle l'identité hold pour tout $r$ non carré. L'auteur prouve ce résultat pour tous les $r$ non carrés jusqu'à 30 en utilisant la certification Walnut dans le système d'Ostrowski.

D. Structure et Complexité

• Mots de Sturm : Les différences premières de la solution Beatty forment un mot de Sturm de pente $1/\sqrt{2}$.
• Systèmes de substitution : À la frontière droite de l'intervalle $I$, la séquence des défauts (erreurs) suit une structure substitutive complexe gouvernée par une matrice dont le rayon spectral est le nombre d'argent ($1+\sqrt{2}$).
• Représentation d'Ostrowski : Une identité de "swap de chiffres" est proposée reliant la suite $a(n)$ aux nombres de Pell via la représentation d'Ostrowski de $n$.

4. Signification et Implications

Ce travail est significatif pour plusieurs raisons :

1. Rupture de l'unicité : Il montre que les équations implicites de type Golomb, souvent considérées comme définissant une unique suite "naturelle" (la solution greedy), peuvent admettre des solutions de nature totalement différente (Sturmienne/Irrationnelle).
2. Pont entre domaines : L'article connecte la théorie des suites automatiques (séquences régulières), la théorie des nombres (suites de Beatty, nombres de Pell, fractions continues) et la théorie des jeux combinatoires (jeu de Wythoff).
3. Nouvelle classe de solutions : Il identifie une famille continue de solutions pour une équation affaiblie, illustrant comment des erreurs locales peuvent être "absorbées" par la structure globale d'une suite monotone.
4. Méthodologie hybride : L'utilisation combinée de preuves analytiques rigoureuses (cas $r=2,3,5$) et de preuves assistées par ordinateur (Walnut pour $r \le 30$) ouvre la voie à l'étude de problèmes de discrépance et de bornes de reste dans les rotations irrationnelles.

En résumé, Benoît Cloitre révèle que l'équation presque de Golomb d'ordre 2 possède une "ombre" irrationnelle (la solution de Beatty) qui coexiste avec la solution greedy, et établit des fondations solides pour l'existence de telles solutions pour une large classe d'ordres $r$.