Complétude du modèle et décidabilité de la structure additive des entiers étendue avec une fonction pour une suite de Beatty

Informations de base

• ID de l'article : 2110.01673
• Titre : Model-completeness and decidability of the additive structure of integers expanded with a function for a Beatty sequence
• Auteurs : Mohsen Khani, Ali N. Valizadeh, Afshin Zarei
• Classification : math.LO (Logique mathématique)
• Date de publication : 17 avril 2024 (version finale)
• Lien de l'article : https://arxiv.org/abs/2110.01673

Résumé

Cet article introduit une théorie modèle-complète qui axiomatise complètement la structure $Z_α = ⟨Z, +, 0, 1, f⟩$, où $f : x ↦ ⌊αx⌋$ est une fonction unaire et $α$ est un nombre transcendant fixe. Lorsque $α$ est calculable, la théorie est récursivement énumérable et donc décidable en tant que conséquence de la complétude. Ce résultat s'inscrit dans le thème plus général d'ajouter des traces de multiplicativité aux entiers sans perdre la décidabilité.

Contexte et motivation de la recherche

Contexte du problème

1. Problème central : Étudier la décidabilité des structures d'expansion du groupe additif des entiers $⟨Z, +⟩$, en particulier les propriétés structurelles après l'ajout de la fonction de suite de Beatty $f(x) = ⌊αx⌋$.
2. Signification de la recherche :
   • Intersection de deux directions de recherche actives : d'une part, la décidabilité des expansions de $⟨Z, +⟩$ et leur classification (structures stables ou instables)
   • D'autre part, l'étude des expansions de la droite réelle avec des sous-groupes additifs discrets spécifiques
3. Limitations des travaux existants :
   • Hieronymi dans H16 a seulement prouvé la décidabilité pour le cas des nombres quadratiques $α$
   • Pour le cas des nombres transcendants $α$, la décidabilité de la structure plus générale $R_α$ reste non résolue
   • De nouvelles techniques sont nécessaires pour traiter l'indépendance de différentes puissances de $f$ dans le cas transcendant
4. Motivation de la recherche :
   • Fournir une preuve de décidabilité pour le cas transcendant
   • Donner une preuve constructive utilisant les outils fondamentaux de la théorie des modèles et de la théorie des nombres
   • Jeter les bases pour résoudre le problème plus général de la structure $R_α$

Contributions principales

1. Établissement d'une théorie modèle-complète : Construction de la théorie $T_α$ qui axiomatise complètement la structure $Z_α = ⟨Z, +, 0, 1, f⟩$, où $f(x) = ⌊αx⌋$ et $α$ est un nombre transcendant.
2. Preuve de décidabilité : Lorsque $α$ est calculable, $T_α$ est récursivement énumérable, et combinée à la complétude, on obtient la décidabilité.
3. Innovations techniques :
   • Transformation des relations de partie fractionnaire en formules de logique du premier ordre
   • Utilisation du lemme de Kronecker étendu pour traiter les formules non algébriques
   • Développement de techniques de réduction pour traiter les formules algébriques
4. Analyse théorique : Preuve que cette structure possède la propriété d'ordre strict et analyse de la structure des ensembles définissables.

Détails de la méthode

Définition de la tâche

Étude de la théorie du premier ordre de la structure $Z_α = ⟨Z, +, 0, 1, f⟩$ dans le langage $L = \{+, -, 0, 1, f\}$, où :

• $Z$ est l'ensemble des entiers
• $+$ est l'opération d'addition
• $f: x ↦ ⌊αx⌋$ est la fonction de suite de Beatty
• $α$ est un nombre transcendant calculable fixe

Cadre technique principal

1. Expression logique de la partie fractionnaire

Observation clé : Bien que la partie fractionnaire ne soit pas dans le langage, ses propriétés clés peuvent être décrites dans $L$ de la manière suivante :

Pour $a, b ∈ Z$ et $n ∈ N$ :

• $f(na) = nf(a) + i$ si et seulement si $\frac{i}{n} < [αa] < \frac{i+1}{n}$
• $[αa] + [αb] < 1$ si et seulement si $f(a+b) = f(a) + f(b)$
• $[αa] < [αb]$ si et seulement si $f(b-a) = f(b) - f(a)$

où $[x] = x - ⌊x⌋$ désigne la partie fractionnaire.

2. Stratégie de classification des formules

Partition systématique des formules $L$ en deux classes :

Formules non algébriques : De la forme $\sum_{i=0}^{\ell_1} n_{1i}[αf^i(x_1)] + \cdots + \sum_{i=0}^{\ell_k} n_{ki}[αf^i(x_k)] \triangleleft \sum_{i=0}^{k'} m_i[αy_i] + [αq] + \ell$

Formules algébriques : De la forme $h_1(x_1) + \cdots + h_n(x_n) = y$, où $h_i(x)$ est un $f$-polynôme.

3. Lemme de Kronecker étendu

Théorème 3.4 (Lemme de Kronecker étendu) : Pour chaque $n ∈ N$, l'ensemble de $(n+1)$-uplets suivant est dense dans $(0,1)^{n+1}$ : $\{([αa], [αf(a)], [αf^2(a)], \ldots, [αf^n(a)]) : a ∈ N\}$

Ceci est vrai car la transcendance de $α$ garantit que $1, α, α^2, \ldots, α^n$ sont linéairement indépendants sur $\mathbb{Q}$.

Stratégie de preuve de la complétude du modèle

Étape 1 : Traitement des formules non algébriques

• Lemme 3.6 : Pour tout ensemble de formules non algébriques $Γ(x; \bar{y})$, il existe une formule sans quantificateurs $χ(\bar{y})$ telle que $Z_α ⊨ ∀\bar{y}(∃xΓ(x; \bar{y}) ↔ χ(\bar{y}))$
• Utilisation de l'algorithme d'élimination de Fourier-Motzkin pour traiter les systèmes d'inégalités linéaires

Étape 2 : Techniques de réduction

• Lemme 4.12 (Astuce technique) : Réduction des systèmes mixtes contenant des formules algébriques à des systèmes non algébriques avec moins de variables
• Idée clé : Par l'introduction de variables auxiliaires $w$ et du terme $h(x)$, transformation des équations algébriques multivariables en cas univariable

Étape 3 : Fermeture algébrique

• Lemme 4.13 : Si $M_1 ⊆ M_2$ sont des modèles de $T_α$, $b ∈ M_1$, $a ∈ M_2$ et $h(a) = b$, alors $a ∈ M_1$
• Garantit la fermeture de la sous-structure sous les opérations inverses de différentes puissances de $f$

Système d'axiomatisation

Schéma d'axiome 1 (Calcul de $f(n)$)

Pour $n ∈ N$ et $0 ≤ i < n$ avec $\frac{f(n)}{n} ≡ i$ : $f(\underbrace{1 + \cdots + 1}_{n \text{ fois}}) = \underbrace{f(1) + \cdots + f(1)}_{n \text{ fois}} + \underbrace{1 + \cdots + 1}_{i \text{ fois}}$

Axiome 2 (Propriétés fondamentales)

1. $∀x∀y(f(x+y) = f(x) + f(y) ∨ f(x+y) = f(x) + f(y) + 1)$
2. $∀x(f(-x) = -f(x) - 1)$
3. $∀y∃x(\bigvee_{i=0}^{f(1)} y + i = f(x))$
4. La relation $[αx] < [αy]$ est un ordre linéaire dense

Schéma d'axiome 3 (Densité)

Pour $m, n ∈ N$ : Si $\bigwedge_{i=1}^n [αz_i] < [αy_i]$, alors il existe au moins $m$ $x$ distincts tels que $\bigwedge_{i=1}^n [αy_i] < [αf^i(x)] < [αz_i]$.

Résultats expérimentaux et analyse théorique

Résultats principaux

Théorème principal : Soit $α$ un nombre réel transcendant, alors :

1. $T_α$ est une axiomatisation complète et modèle-complète de la structure $Z_α$
2. $Z_α$ possède la propriété d'ordre strict
3. Lorsque $α$ est calculable, $T_α$ est décidable

Propriétés des ensembles définissables

1. Ensembles structurés : Les formules sans puissances de $f$ définissent des classes de congruence (progressions arithmétiques infinies)
2. Ensembles aléatoires : Les ensembles définis par des formules contenant des puissances de $f$ ne contiennent pas de progressions arithmétiques infinies
3. Propriétés mixtes : L'image de tout $f$-polynôme contient des progressions arithmétiques finies de longueur arbitraire

Proposition 5.1 : Pour $h(x) = \sum_{i=0}^k m_i f^i(x)$, pour chaque $n ∈ N$, l'image de $h$ contient une progression arithmétique de longueur $n$.

Travaux connexes

1. Hieronymi H16 : Preuve de la décidabilité de $R_α$ pour le cas quadratique
2. Conant & Pillay CP18 : Étude de la classification de stabilité des expansions de $⟨Z, +⟩$
3. Günaydin & Özsahakyan GO22 : Recherche indépendante, traitement des suites de Beatty comme prédicats plutôt que comme fonctions
4. Khani & Zarei KZ22 : Preuve simplifiée pour le cas du nombre d'or

Conclusion et discussion

Conclusions principales

1. Généralisation réussie du résultat de Hieronymi des nombres quadratiques aux nombres transcendants
2. Fourniture d'une preuve constructive de la complétude du modèle
3. Établissement d'un nouveau cadre technique pour traiter le cas transcendant

Limitations

1. Nécessité de la calculabilité de $α$ pour garantir l'énumérabilité récursive
2. Le problème plus général de la structure $R_α$ reste non résolu
3. L'élimination des quantificateurs dans le cas transcendant semble impossible

Directions futures

1. Problème ouvert : Décidabilité et complétude du modèle de la structure $⟨Z, <, +, -, 0, 1, f⟩$ (avec l'ordre sur les entiers)
2. Généralisation à d'autres types de nombres transcendants
3. Étude de combinaisons plus complexes de suites de Beatty

Points d'innovation technique

1. Complétude du modèle effective : Le processus de preuve est constructif et permet l'élimination effective des quantificateurs
2. Connexion o-minimale : Lien entre la partie non algébrique $T_{nalg}$ et les théories o-minimales
3. Cadre unifié : Approche unifiée pour traiter les formules algébriques et non algébriques

Évaluation approfondie

Avantages

1. Contribution théorique : Généralisation significative des résultats connus, passage des nombres quadratiques aux nombres transcendants constitue un progrès important
2. Innovation technique : L'application du lemme de Kronecker étendu et la conception des techniques de réduction sont très créatives
3. Généralité de la méthode : Les techniques peuvent être appliquées au cas des nombres algébriques
4. Preuve constructive : Fourniture d'un résultat effectif de complétude du modèle

Insuffisances

1. Complexité computationnelle : Bien que théoriquement décidable, la complexité pratique peut être très élevée
2. Limitations d'expressivité : Incapacité à traiter certaines structures connexes naturelles
3. Complexité technique : La preuve implique plusieurs lemmes techniques complexes

Impact

1. Valeur académique : Fourniture de nouvelles techniques et résultats pour le domaine de la logique mathématique et de la théorie des modèles
2. Perspectives d'application : Fondation pour l'étude de structures arithmétiques plus complexes
3. Contribution méthodologique : Démonstration de comment traiter systématiquement ce type de structures mixtes algébrico-analytiques

Domaines d'application

1. Recherche en théorie de la décidabilité en logique mathématique
2. Problèmes diophantiens en géométrie arithmétique
3. Preuve automatisée de théorèmes en informatique
4. Étude des propriétés de distribution en théorie des nombres

Références

• H16 P. Hieronymi, Expansions of the ordered additive group of real numbers by two discrete subgroups
• KZ22 M. Khani and A. Zarei, The additive structure of integers with the lower Wythoff sequence
• HM+21 P. Hieronymi et al., Decidability for Sturmian words
• C60 I. G. Connell, Some properties of Beatty sequences II