On the Monotonicity of Higher-Fold Representation Functions

Résumé Technique : Sur la monotonie des fonctions de représentation à $h$ plis

Énoncé du Problème
L'article étudie les propriétés de monotonie de la fonction de représentation ordonnée à $h$ plis $R_{A,h}(n)$, définie comme le nombre de solutions ordonnées à $n = a_1 + \dots + a_h$ avec $a_i \in A$, où $A \subseteq \mathbb{N}$. La question centrale est de savoir si $R_{A,h}(n)$ peut être strictement croissante pour un ensemble $A$ dont le complément $\mathbb{N} \setminus A$ est infini (un ensemble co-infini).

Historiquement, Erdős, Sárközy et Sós ont prouvé que pour $h=2$, la croissance stricte implique que $A$ est cofini (c'est-à-dire que son complément est fini). Pour $h \ge 3$, Dombi a conjecturé que si $\mathbb{N} \setminus A$ est infini, $R_{A,h}(n)$ ne peut pas être éventuellement strictement croissante. Cette conjecture a été réfutée par Shallit, qui a utilisé la théorie des automates pour construire un ensemble co-infini $A$ où $R_{A,3}(n)$ est strictement croissante. Plus précisément, Shallit a utilisé l'ensemble $B = \{0\} \cup \{m \ge 1 : \text{l'expansion en base 4 de } m \text{ commence par 1 ou 2}\}$. Bien que Shallit ait établi la monotonie stricte pour $R_{B,h}(n)$ pour un $h \ge 3$ fixé, le taux de croissance précis de la différence $R_{B,h}(n+1) - R_{B,h}(n)$ est resté une question quantitative ouverte. De plus, Dombi a posé un problème concernant l'existence de tels ensembles avec une densité asymptotique $\alpha \neq 1/2$ (ou spécifiquement $\alpha \neq 1$).

Méthodologie
Les auteurs emploient une combinaison de fonctions génératrices, de relations de récurrence dérivées de la structure auto-similaire de l'ensemble $B$, et d'arguments de convolution pour établir des bornes sur la fonction de différence $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$.

1. Analyse de la Récurrence pour l'Ensemble $B$ :
   L'ensemble $B$ est défini par sa séquence indicatrice $c_n$, qui satisfait une équation fonctionnelle dans la fonction génératrice $C(x) = \sum c_n x^n$ :
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   En élevant cette équation au carré et au cube, les auteurs dérivent des relations de récurrence pour les différences des fonctions de représentation à deux plis ($\beta_n$) et à trois plis ($\alpha_n$).

• Lemmes 2.1 & 2.2 : Ces lemmes établissent des formules récursives pour $\beta_n$ et $\alpha_n$ basées sur les valeurs aux indices $n/4$.
• Bornes sur $\beta_n$ : Le Lemme 3.1 prouve que la différence pour la fonction à deux plis est bornée : $-1 \le \beta_n \le 2$.
• Bornes sur $\alpha_n$ : En utilisant les bornes sur $\beta_n$ et les relations de récurrence, le Lemme 3.2 établit une borne inférieure linéaire $\alpha_n \ge n/5 + 4$ pour $n \ge 78$, tandis que le Lemme 3.3 fournit une borne supérieure linéaire $\alpha_n \le 3n + 2$.

2. Élévation par Convolution :
   Pour étendre les résultats de $h=3$ à un $h \ge 3$ arbitraire, les auteurs utilisent l'identité de convolution :
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   Ceci conduit à une relation pour les différences :
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   En fixant $p=3$ et $q=h-3$, le comportement de $\Delta_h(n)$ est contrôlé par le comportement connu de $\Delta_3(n)$ (soit $\alpha_n$) et la croissance de $R_{h-3}(n)$.

3. Construction de l'Ensemble $C$ :
   Pour répondre au problème de densité de Dombi, les auteurs construisent un ensemble $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$. Ils analysent la fonction génératrice $G_C(x) = (1-x)^{-1} - D(x)$, où $D(x)$ correspond aux puissances de 2 retirées. La rareté de l'ensemble retiré permet une estimation explicite de la différence $R_{C,h}(n+1) - R_{C,h}(n)$.

Contributions Clés et Résultats

1. Ordre de Croissance Polynomiale (Théorème 1.1) :
   L'article prouve que pour l'ensemble $B$, la différence $R_{B,h}(n+1) - R_{B,h}(n)$ croît polynomialement avec un ordre $n^{h-2}$. Plus précisément, pour tout entier $h \ge 3$, il existe des constantes $c_h, C_h > 0$ telles que pour tout $n \ge 1$ :
   $$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$$
   Ce résultat confirme que malgré le fait que $B$ possède un complément infini avec de grands écarts, sa fonction de représentation se comporte asymptotiquement comme celle de l'ensemble complet $\mathbb{N}$ (où la différence est $\binom{n+h-1}{h-2} \asymp n^{h-2}$).

2. Monotonie Stricte pour un $h \ge 3$ Arbitraire :
   Les auteurs prouvent rigoureusement que $R_{B,h}(n+1) > R_{B,h}(n)$ pour tout $n \ge 0$ et tout $h \ge 3$, améliorant ainsi le résultat de Shallit qui se concentrait sur l'existence de tels ensembles sans quantifier le taux de croissance pour tout $h$.

3. Résolution du Problème de Densité de Dombi (Théorème 1.2) :
   L'article construit un ensemble co-infini $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ tel que :

• La densité asymptotique existe et est égale à 1 : $\lim_{n \to \infty} C(n)/n = 1$.
• La fonction de représentation $R_{C,h}(n)$ est strictement croissante pour chaque entier $h \ge 3$.
  Cela répond au problème de Dombi en fournissant un ensemble de densité 1 (distinct des exemples de densité 1/2 précédemment connus) qui maintient une monotonie stricte.

Signification
L'article affine la compréhension des fonctions de représentation additive dans les ensembles co-infinis. Il démontre que l'obstacle à la monotonie trouvé dans le cas $h=2$ ne persiste pas pour $h \ge 3$, même lorsque l'ensemble possède un complément infini "large". En établissant l'ordre de croissance polynomial précis de la fonction de différence, les auteurs montrent que l'ensemble $B$ conserve la "régularité" de l'ensemble complet des entiers en termes de croissance de la représentation. De plus, la construction de l'ensemble $C$ élargit le paysage de ces ensembles, montrant que la monotonie stricte est compatible avec une densité asymptotique de 1, réduisant ainsi l'écart entre les comportements cofini et co-infini en théorie additive des nombres.

Les auteurs concluent en posant des problèmes ouverts concernant l'existence de tels ensembles pour des densités prescrites arbitraires $d \in [0, 1)$ et pour des ensembles avec des densités liminf et limsup spécifiques, suggérant que la caractérisation complète des conditions de monotonie pour les fonctions de représentation reste un domaine de recherche actif.