🔢 mathematics

Beatty Sequences for a Quadratic Irrational: Decidability and Applications

Cet article démontre que les suites de Beatty inhomogènes associées à un irrationnel quadratique sont synchronisées, ce qui permet d'établir la décidabilité de leur théorie logique du premier ordre avec l'addition et de résoudre plusieurs problèmes ouverts en utilisant l'automate Walnut.

Auteurs originaux : Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Publié 2026-04-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

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

🌟 Titre : La Danse des Nombres Irrationnels et le Robot Détective

Imaginez que vous avez un nombre magique, un nombre qui ne se termine jamais et ne répète jamais de motif (comme $\sqrt{2}$ ou le nombre d'or $\phi$ ). Si vous multipliez ce nombre par 1, 2, 3, 4... et que vous arrondissez le résultat à l'entier le plus proche, vous obtenez une liste de nombres appelée séquence de Beatty.

C'est un peu comme si vous marchiez sur un escalier où chaque marche a une hauteur différente et bizarre. Vous sautez de marche en marche, et vous notez à quelle hauteur vous atterrissez.

Les auteurs de cet article (Luke, Jeffrey et Stefan) se sont posé une question fascinante : Peut-on prédire exactement où nous allons atterrir sur cet escalier bizarre, et pouvons-nous résoudre des énigmes complexes sur ces marches ?

La réponse est OUI, mais à une condition : les nombres magiques doivent appartenir à la même "famille" mathématique (ce qu'ils appellent un "corps quadratique").

Voici comment ils ont fait, expliqué avec des images simples :

1. Le Robot qui lit les codes secrets (Les Automates)

Pour comprendre ces séquences, les chercheurs utilisent un outil appelé Walnut. Imaginez Walnut comme un robot détective très intelligent, mais un peu spécial.

Le problème : Normalement, pour vérifier si un nombre $y$ est le résultat de la formule $\lfloor n\alpha + \beta \rfloor$ , il faut faire des calculs infinis.
La solution : Les chercheurs ont découvert que si on écrit les nombres $n$ et $y$ dans un langage spécial (appelé représentation d'Ostrowski, qui est un peu comme un code-barres basé sur des nombres de Fibonacci), un petit robot (un automate fini) peut les lire en même temps.
L'analogie : Imaginez deux personnes qui marchent côte à côte. L'une lit le numéro de la marche ( $n$ ) et l'autre lit la hauteur atteinte ( $y$ ). Le robot est un gardien qui vérifie instantanément : "Est-ce que cette hauteur correspond bien à cette marche ?". Si oui, il ouvre la porte (accepte), sinon il ferme (rejette).

Le génie de l'article est de prouver que pour les nombres "quadratiques" (comme $\sqrt{2}$ ou $\phi$ ), ce robot existe toujours et est assez simple à construire.

2. La Machine à Décider (La Décidabilité)

Une fois que ce robot existe, il devient une machine à décider.

Avant : Les mathématiciens devaient souvent passer des années à essayer de prouver des conjectures sur ces suites. C'était comme chercher une aiguille dans une botte de foin à la main.
Maintenant : Avec Walnut, on peut écrire une phrase logique (du style : "Est-ce que tous les nombres entiers peuvent être formés en additionnant 3 marches de cet escalier ?") et le robot va calculer la réponse (VRAI ou FAUX) en quelques secondes.

C'est comme si vous aviez un GPS qui vous dit non seulement le chemin, mais qui peut aussi vérifier instantanément si une route est bloquée ou si un pont existe, sans avoir besoin de rouler dessus.

3. Les Applications Concrètes (Résoudre des énigmes)

Les auteurs ont utilisé cette "machine à décider" pour résoudre des problèmes qui traînaient depuis longtemps :

Les bases additives : Ils ont pu déterminer si une suite de nombres peut servir de "briques" pour construire n'importe quel grand nombre en les additionnant. C'est comme demander : "Si j'ai des briques de tailles bizarres, puis-je construire n'importe quelle maison ?". Le robot a répondu oui ou non pour plusieurs cas.
Les conjectures de Reble et Kimberling : Des chercheurs avaient émis des hypothèses sur des suites de nombres spécifiques (comme celles liées au mot de Fibonacci). Les auteurs ont écrit le code pour ces hypothèses, et le robot a confirmé qu'elles étaient vraies. C'est comme si un détective avait résolu des crimes non élucidés en quelques clics.
La question de Graham : Ils ont résolu un problème sur la façon dont plusieurs suites de nombres peuvent se couvrir sans se chevaucher.

4. Le Secret de la "Famille" (Pourquoi ça marche ?)

Pourquoi cela fonctionne-t-il seulement pour certains nombres ?
Imaginez que les nombres $\alpha$ et $\beta$ sont des membres d'une même famille (par exemple, tous deux liés à $\sqrt{2}$ ). Parce qu'ils partagent le même ADN mathématique, le robot peut comprendre leur relation.

Si vous essayez de mélanger deux familles qui ne se parlent pas (par exemple, un nombre lié à $\sqrt{2}$ et un autre lié à $\sqrt{3}$ ), le robot perd ses repères et ne peut pas construire le code-barres nécessaire. L'article prouve aussi que si le robot fonctionne, c'est que les nombres appartiennent forcément à la même famille.

En résumé

Cet article est une victoire de l'informatique théorique sur l'analyse mathématique pure.

Ils ont créé un pont entre les nombres irrationnels complexes et la logique des ordinateurs.
Ils ont montré que pour une grande classe de nombres, tout ce qui est vrai peut être prouvé par un ordinateur en un temps raisonnable.
Ils ont utilisé cet outil pour résoudre des énigmes anciennes et découvrir de nouvelles propriétés sur des suites de nombres mystérieuses.

C'est comme si on avait donné à des mathématiciens une loupe magique qui rend visible l'invisible, transformant des problèmes qui prenaient des siècles de réflexion en quelques secondes de calcul.

1. Problématique et Contexte

L'article s'intéresse aux séquences de Beatty inhomogènes, définies par la suite $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ , où $\alpha$ et $\beta$ sont des nombres réels. L'objectif principal est d'établir la décidabilité de la théorie logique du premier ordre associée à ces suites, en particulier lorsque $\alpha$ et $\beta$ appartiennent au même corps quadratique $\mathbb{Q}(\gamma)$ , où $\gamma$ est un irrationnel quadratique.

Le problème central réside dans la capacité à déterminer algorithmiquement si des propriétés complexes (telles que la formation d'une base additive, l'équivalence asymptotique, ou l'existence de progressions arithmétiques monochromatiques) sont vraies pour ces suites. Historiquement, la décidabilité pour le cas du nombre d'or (suite de Fibonacci) était connue, mais une généralisation systématique aux irrationnels quadratiques et une méthode constructive simple faisaient défaut.

2. Méthodologie

Les auteurs développent une approche basée sur la théorie des automates finis et la représentation d'Ostrowski.

Synchronisation : Une suite $(s_n)$ est dite synchronisée (par rapport à un système de numération) s'il existe un automate fini qui accepte une paire d'entrées $(n, y)$ en représentation d'Ostrowski si et seulement si $y = s_n$ .
Représentation d'Ostrowski : Pour un irrationnel $\gamma$ , tout entier $n$ peut être représenté de manière unique comme une combinaison linéaire des dénominateurs des convergents de la fraction continue de $\gamma$ . Cette représentation est « addable » (l'addition est reconnaissable par un automate) lorsque $\gamma$ est un irrationnel quadratique.
Outil Logiciel (Walnut) : L'implémentation pratique repose sur Walnut, un logiciel libre capable de prouver des théorèmes sur les suites automatiques en exécutant des requêtes de logique du premier ordre.

La méthodologie clé consiste à démontrer que l'application $n \mapsto \lfloor n\alpha + \beta \rfloor$ est une fonction synchronisée lorsque $\alpha, \beta \in \mathbb{Q}(\gamma)$ . Une fois cette synchronisation établie, le théorème de décidabilité de la logique du premier ordre (théorème de Büchi-Bruyère-Hieronymi-Terry adapté) s'applique automatiquement.

3. Contributions Clés et Résultats Principaux

A. Théorème de Synchronisation (Théorème 9)

Les auteurs prouvent que si $\gamma$ est un irrationnel quadratique tel que $1/\gamma$ possède un développement en fraction continue purement périodique, et si $\alpha, \beta \in \mathbb{Q}(\gamma)$ , alors la suite de Beatty inhomogène $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ est $\gamma$ -Ostrowski synchronisée.

Cela signifie qu'un automate fini peut vérifier la relation $y = \lfloor n\alpha + \beta \rfloor$ en lisant les représentations d'Ostrowski de $n$ et $y$ en parallèle.
La preuve repose sur une décomposition algébrique de $\alpha$ et $\beta$ et l'utilisation de propriétés matricielles des fractions continues (Théorème 5).

B. Réciproque (Théorème 28)

Les auteurs établissent la réciproque : si la suite $(\lfloor n\alpha + \beta \rfloor)$ est synchronisée par rapport à un irrationnel quadratique $\gamma$ , alors nécessairement $\alpha$ et $\beta$ appartiennent à $\mathbb{Q}(\gamma)$ . Cette caractérisation complète le cadre théorique.

C. Décidabilité de la Théorie Logique (Corollaire 11)

En combinant la synchronisation avec les résultats existants sur les automates, ils démontrent que la théorie du premier ordre des nombres naturels munis de l'addition et de la fonction $n \mapsto \lfloor n\alpha + \beta \rfloor$ est décidable pour tout irrationnel quadratique $\gamma$ .

Contrairement aux preuves antérieures souvent complexes, cette approche fournit une procédure de décision simple et implémentable.

D. Applications Concrètes

L'article applique cette méthode pour résoudre plusieurs problèmes ouverts et conjectures :

Bases Additives (Section 7) : Il est décidable de déterminer si une suite de Beatty forme une base additive (ou asymptotique) d'ordre $r$ . Les auteurs montrent que pour tout $\alpha, \beta$ quadratiques, une telle base existe pour un certain ordre $h$ , et que le plus petit $h$ est calculable.
Conjectures de Don Reble (Section 8) : Résolution de conjectures concernant les progressions arithmétiques monochromatiques dans le mot de Fibonacci, en reliant ces propriétés à des suites de Beatty spécifiques.
Question de Graham (Section 9) : Décidabilité du problème de recouvrement (Eventual Covering Family) pour des ensembles de paires $(\alpha_i, \beta_i)$ dans un même corps quadratique.
Caractérisation de Séquences OEIS (Sections 10-13) :
- Preuve automatique de propriétés sur une suite étudiée par Hildebrand et al.
- Résolution de problèmes ouverts de Kimberling sur les séquences de « swappage » (échange de termes pairs/impairs des suites de Wythoff).
- Démonstration d'identités et de relations entre sept suites de l'OEIS liées à $\sqrt{2}$ .
Parties Fractionnaires (Section 14) : Extension de la méthode pour traiter les inégalités impliquant des parties fractionnaires $\{ \alpha x + \beta \}$ , permettant de déterminer l'ordre cyclique de points sur le cercle unité.

4. Signification et Impact

Unification et Simplicité : L'article fournit une preuve unifiée et remarquablement simple de la décidabilité pour une large classe de suites de Beatty, remplaçant des techniques antérieures plus lourdes (comme l'élimination de quantificateurs complexe).
Automatisation : La démonstration que ces problèmes peuvent être résolus « mécaniquement » en quelques secondes via le logiciel Walnut marque un tournant dans l'étude des suites combinatoires et de la théorie des nombres. Cela transforme des conjectures ouvertes en problèmes de vérification algorithmique.
Nouveaux Résultats : L'approche permet de prouver des théorèmes et de résoudre des conjectures (Reble, Kimberling, Irwin) qui étaient jusque-là hors de portée des méthodes classiques.
Converse Théorique : La preuve de la réciproque (Théorème 28) établit une correspondance forte entre la structure algébrique des paramètres ( $\alpha, \beta$ ) et la propriété automatique de la suite générée.

En résumé, ce papier démontre que la théorie des automates finis, couplée à la représentation d'Ostrowski, constitue un outil puissant et universel pour l'analyse des suites de Beatty quadratiques, ouvrant la voie à la résolution automatique de problèmes profonds en théorie des nombres additive et combinatoire.