On orbit sets generated by semigroups of one-dimensional affine functions

Résumé Technique : Ensembles d'Orbites Générés par des Semi-groupes de Fonctions Affines Unidimensionnelles

Énoncé du Problème
Cet article étudie la croissance asymptotique des ensembles d'orbites unidimensionnels $\langle F : s \rangle$ et des multiensembles d'orbites $\langle F : s \rangle^\#$, générés par un ensemble de fonctions affines entières $F = \{f_i(x) = a_i x + b_i\}_{i=1}^n$ agissant sur une valeur (ou un ensemble) initiale $s$. Le problème central est de déterminer la densité de ces ensembles, spécifiquement si la fonction de croissance $|\langle F : s \rangle \cap [0, x]|$ est positive (c'est-à-dire possède une densité asymptotique inférieure non nulle) sous des conditions spécifiques.

L'étude se concentre sur le cas critique où les pentes $a_i$ satisfont l'équation $\sum_{i=1}^n \frac{1}{a_i} = 1$. Des travaux antérieurs de P. Erdős ont établi une borne supérieure de $O(x^{\sigma+\epsilon})$ pour la fonction de croissance lorsque $\sum a_i^{-\sigma} = 1$. Erdős et Graham ont posé une question ouverte spécifique : si $F$ forme une base de semi-groupe libre (signifiant qu'aucune relation de composition non triviale n'existe entre les fonctions) et que $\sum a_i^{-1} = 1$, l'ensemble d'orbite $\langle F : s \rangle$ a-t-il une densité positive ? S'il était connu que si $\sum a_i^{-1} < 1$ la densité est nulle, le cas d'égalité restait non résolu pour les semi-groupes libres généraux.

Méthodologie
Les auteurs emploient une combinaison d'analyse combinatoire, d'induction et de techniques algébriques pour dériver des bornes inférieures pour la taille de ces ensembles d'orbite.

1. Borne Inférieure pour les Multiensembles : L'article établit d'abord une borne inférieure pour la taille du multiensemble d'orbite $\langle F : s \rangle^\#$. En analysant la composition de fonctions affines, les auteurs dérivent une inégalité auxiliaire (Lemme 4) bornant l'image d'un point sous une composition de fonctions. En utilisant cela, ils prouvent une borne inférieure de $\Omega(x^\sigma)$ pour la taille du multiensemble lorsque $\sum a_i^{-\sigma} = 1$. Cela complète la borne supérieure $O(x^{\sigma+\epsilon})$ d'Erdős-Lagarias, bien que les auteurs notent qu'un écart subsiste entre la borne supérieure $O(x^{\sigma+\epsilon})$ et la borne inférieure $\Omega(x^\sigma)$, laissant le comportement asymptotique précis ($\Theta(x^\sigma)$) comme une question ouverte pour les cas généraux.

2. Borne Sous-linéaire pour les Semi-groupes Libres : Pour répondre à la question d'Erdős-Graham, les auteurs utilisent les propriétés des semi-groupes libres. Ils construisent un ensemble de compositions de fonctions ayant des pentes égales mais des coefficients libres distincts (Lemme 6). En appliquant l'approximation de Stirling au décompte de ces compositions, ils dérivent une borne inférieure sous-linéaire pour la taille de l'ensemble d'orbite lorsque $\sum a_i^{-1} = 1$ et que $F$ est une base de semi-groupe libre.

3. Systèmes de Recouvrement Exacts : L'article introduit un lien entre les ensembles d'orbite et les « systèmes de recouvrement exact » (partitions d'entiers en progressions arithmétiques disjointes). En appliquant une version du Lemme Ping-Pong aux fonctions directes sur l'ensemble des entiers $\mathbb{Z}$, les auteurs montrent que si les fonctions de $F$ forment un système de recouvrement exact (c'est-à-dire $f_1(\mathbb{Z}) \sqcup \dots \sqcup f_n(\mathbb{Z}) = \mathbb{Z}$), l'ensemble d'orbite a une densité positive.

Contributions Clés et Résultats

• Théorème 2 (Borne Inférieure du Multiensemble) : Les auteurs prouvent que pour un ensemble fini de fonctions affines avec $\sum a_i^{-\sigma} = 1$, la taille du multiensemble d'orbite satisfait $|\langle F : s \rangle^\# \cap [0, x]| = \Omega(x^\sigma)$. Cela fournit la première borne inférieure générale complétant la borne supérieure d'Erdős-Lagarias.
• Théorème 5 (Borne Sous-linéaire pour les Semi-groupes Libres) : Répondant à la question d'Erdős-Graham, l'article établit que si $F$ est une base de semi-groupe libre et $\sum a_i^{-1} = 1$, alors pour tout $s \ge 0$, la taille de l'ensemble d'orbite satisfait :
  $$|\langle F : s \rangle \cap [0, x]| = \Omega\left(\frac{x}{\log^{\frac{n-1}{2}} x}\right)$$
  Ce résultat démontre que la croissance est au moins sous-linéaire, bien qu'il ne parvienne pas à prouver une densité positive (ce qui nécessiterait $\Omega(x)$) pour le cas général des semi-groupes libres.
• Théorème 7 (Densité Positive pour les Systèmes de Recouvrement Exacts) : L'article prouve que si les fonctions de $F$ forment un système de recouvrement exact d'entiers, l'ensemble d'orbite $\langle F : s \rangle$ a une densité positive. La preuve repose sur la démonstration que, dans ces conditions, la multiplicité des éléments du multiensemble d'orbite est au plus de un, réduisant la taille du multiensemble à la taille de l'ensemble, qui est ensuite bornée inférieurement par le terme linéaire dérivé du Théorème 2.
• Application aux Tuples de Klarner : Les auteurs appliquent leurs résultats à des « tuples de Klarner » spécifiques (triplets d'entiers $(a, b, c)$ où $2x+a, 3x+b, 6x+c$ forment un semi-groupe libre). Bien que le problème de la densité reste ouvert pour les pentes classiques $\{2, 3, 6\}$, les auteurs démontrent que pour l'ensemble de pentes $\{2, 4, 4\}$ avec des coefficients spécifiques dérivés de systèmes de recouvrement exacts, l'ensemble d'orbite possède une densité positive.

Signification et Revendications
L'article affirme compléter les travaux fondateurs d'Erdős et Lagarias en fournissant une borne inférieure correspondante pour la taille du multiensemble, réduisant ainsi l'écart dans la compréhension de la croissance de ces ensembles. Plus précisément, il fournit une borne inférieure « presque linéaire » pour la question d'Erdős-Graham dans le contexte des semi-groupes libres.

En outre, l'article prétend résoudre la question d'Erdős-Graham par l'affirmative pour le sous-cas spécifique où les fonctions génératrices forment un système de recouvrement exact. Les auteurs soulignent que cela relie deux sujets auparavant distincts de la théorie des nombres : l'étude des ensembles d'orbite et la théorie des systèmes de recouvrement exact (un sujet popularisé par Erdős). Le travail clarifie que, bien que le cas général pour les semi-groupes libres avec $\sum a_i^{-1} = 1$ demeure ouvert (avec seulement une borne sous-linéaire actuellement prouvée), la condition de former un système de recouvrement exact est suffisante pour garantir une densité positive. L'article ne prétend pas résoudre la question d'Erdős-Graham générale pour tous les semi-groupes libres, ni résoudre le problème de densité pour les pentes spécifiques $\{2, 3, 6\}$, notant que ces derniers restent ouverts.