Suite de Piatetski-Shapiro

La suite de Piatetski-Shapiro d'ordre $c$ , où $c > 0$ est un nombre réel, est la suite d'entiers

(⌊ n^{c} ⌋)_{n \geq 1}

.

Un nombre de la forme $⌊ n^{c} ⌋$ est appelé un nombre de Piatetski-Shapiro par Joël Rivat dans sa thèse^[1].

Définitions et estimations

Ilya Piatetski-Shapiro a étudié à plusieurs reprises, et pour la première fois en 1953^[2], le nombre de nombres premiers parmi les éléments d'une suite de Piatetski-Shapiro. On note $π_{c} (x)$ le nombre d'entiers $n$ inférieurs à $x$ tels que $⌊ n^{c} ⌋$ est premier, soit formellement

π_{c} (x) = Card {n < x ∣ ⌊ n^{c} ⌋ est premier}

,

il est conjecturé^[1] que

π_{c} (x) \sim \frac{x}{c \ln x} x \to \infty

.

Piatetski-Shapiro a montré^[2] que cette équivalence était vraie pour $0 < c < 12 / 11$ , puis la majoration a été progressivement améliorée^[1] :

1972 : Kolesnik : $0 < c < 10 / 9 = 1, 111 . . .$
Graham et Leitmann, indépendamment (non publié): $0 < c < 69 / 62 = 1, 112903 . . .$
1983 : Heath-Brown : $0 < c < 755 / 662 = 1, 140483 . . .$
1985 : Kolesnik : $0 < c < 39 / 34 = 1, 14705 . . . .$
1990 : Liu et Rivat (indépendamment) : $0 < c < 15 / 13 = 1, 15 . . . .$
1992 : Rivat : $0 < c < 6121 / 5301 = 1, 1544 . . .$
2001 : Rivat et Sargos : $0 < c < 2817 / 2426 = 1, 16117 . . .$ .
2001 : Rivat et Wu : $0 < c < 243 / 205 = 1, 18536 . . .$ .

Complexité arithmétique des termes suivant une suite de Piatetski-Shapiro

La complexité d'un mot infini $x$ sur un alphabet fini est la fonction qui donne le nombre de facteur de chaque longueur dans $x$ . La complexité arithmétique d'un mot infini $x$ selon la suite de Piatetski-Shapiro $(⌊ n^{c} ⌋)$ est la complexité du mot obtenu en ne conservant que les termes d'indice $⌊ n^{c} ⌋$ .

Parmi les études dans ce cadre, il y a l'article de Deshouillers, Drmota, Müllner, Shubin et Spiegelhofer^[3] qui considère la complexité arithmétique d'un mot automatique synchronisant. Un cas particulier est la suite $(⌊ n^{c} ⌋ mod m)$ dont ils montrent que la complexité arithmétique est polynomiale.