Suite régulière

Soit ${\displaystyle k\geq 2}$ un entier. Une suite

${\displaystyle a=(a(n))_{n\geq 0}}$

d'entiers est dite ${\displaystyle k}$-régulière s'il existe un nombre fini ${\displaystyle s}$ de suites d'entiers

${\displaystyle (b_{1}(n))_{n\geq 0},(b_{1}(n))_{n\geq 0},\ldots ,(b_{s}(n))_{n\geq 0}}$

et, pour tout ${\displaystyle i\geq 0}$ et tout ${\displaystyle 0\leq j<k^{i}}$, des entiers

${\displaystyle c_{1},c_{2},\ldots ,c_{s}}$

tels que pour tout ${\displaystyle n\geq 0}$, on a

${\displaystyle a(j+k^{i}n)=c_{1}b_{1}(n)+c_{2}b_{2}(n)+\cdots +c_{s}b_{s}(n)}$.

En d'autres termes, chacune des sous-suites

${\displaystyle (a(j+k^{i}n))_{n\geq 0}}$

est combinaison linéaire, à coefficients entiers, des suites données ${\displaystyle (b_{1}(n))_{n\geq 0},(b_{1}(n))_{n\geq 0},\ldots ,(b_{s}(n))_{n\geq 0}}$. Pour simplifier l'expression ci-dessus, il est utile de donner un nom aux sous-suites considérées. On appelle ${\displaystyle k}$-noyau[3] de la suite ${\displaystyle a}$ l'ensemble

${\displaystyle \mathrm {Ker} _{k}(a)=\{(a(j+k^{i}n))_{n\geq 0}\mid i\geq 0,0\leq j<k^{i}\}}$

des sous-suites ${\displaystyle (a(j+k^{i}n))_{n\geq 0}}$ pour ${\displaystyle i\geq 0}$ et ${\displaystyle 0\leq j<k^{i}}$. Alors, et de manière plus synthétique, la suite ${\displaystyle a}$ est ${\displaystyle k}$-régulière si son ${\displaystyle k}$-noyau ${\displaystyle \mathrm {Ker} _{k}(a)}$ est contenu dans un ${\displaystyle \mathbb {Z} }$-module finiment engendré de suites d'entiers[4].

Soit ${\displaystyle A}$ un alphabet fini et soit ${\displaystyle K}$ un demi-anneau. Une série formelle ${\displaystyle S}$ est une application de ${\displaystyle A^{*}}$ dans ${\displaystyle K}$. L'image d'un mot ${\displaystyle w}$ est noté ${\displaystyle (S,w)}$. La série elle-même est aussi notées ${\displaystyle S=\sum _{w\in A^{*}}(S,w)}$[5].

Une série formelle ${\displaystyle S:A^{*}\to K}$ est dite ${\displaystyle K}$-reconnaissable s'il existe un entier ${\displaystyle m\geq 1}$, des vecteurs ${\displaystyle \lambda \in K^{1\times m}}$ , ${\displaystyle \gamma \in K^{m\times 1}}$ et un morphisme ${\displaystyle \mu :A^{*}\to K^{m\times m}}$ telle que

${\displaystyle (S,w)=\lambda \mu (w)\gamma }$ pour tout ${\displaystyle w}$.

Le triple ${\displaystyle (\lambda ,\mu ,\gamma )}$est une représentation linéaire de ${\displaystyle S}$.

Une suite ${\displaystyle a}$ est ${\displaystyle k}$-régulière si la série formelle

${\displaystyle \sum _{w\in A^{*}}\mathrm {val_{k}} (w)w}$

est ${\displaystyle \mathbb {N} }$-reconnaissable, où ${\displaystyle A=\{0,1,\ldots ,k-1\}}$. Ici

${\displaystyle \mathrm {val_{k}} (d_{r}d_{r-1}\cdots d_{0})=d_{0}+d_{1}k+d_{2}k^{2}+\cdots +d_{r}k^{r}}$

est le nombre représenté par son développement ${\displaystyle d_{0}d_{1}\cdots d_{r}\in A^{*}}$ en base ${\displaystyle k}$.

La suite, traditionnellement notée ${\displaystyle (s_{2}(n))_{n\geq 0}}$ :

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, . . .

qui compte la somme des bits dans l'écriture binaire des entiers naturels est un prototype de suite 2-régulière. C'est la suite  A007814 de l'Encyclopédie en ligne des suites de nombres entiers). Pour le vérifier, calculons son 2-noyau. On prend d'abord les deux sous-suites dont les indices sont pairs ou impairs, ce qui donne :

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, . . .

et

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, . . .

La première sous-suite est égale à la suite de départ, la deuxième est égale à suite de départ dont chaque terme est augmenté de 1. Plus généralement, comme on a

${\displaystyle s_{2}(j+2^{i}n)=s_{2}(j)+s_{2}(n)}$,

tout élément du 2-noyau est une combinaison linéaire de la suite de départ et de la suite constante ${\displaystyle (1)}$.

Une représentation linéaire de la série ${\displaystyle s_{2}}$ est donnée par

${\displaystyle \lambda =(10),\ \mu (0)={\begin{pmatrix}1&0\\0&1\end{pmatrix}},\ \mu (1)={\begin{pmatrix}1&0\\1&1\end{pmatrix}},\ \gamma ={\binom {1}{0}}}$.

On a alors, pour ${\displaystyle n=\mathrm {val_{k}} (w)}$, ${\displaystyle n\neq 0}$ :

${\displaystyle \mu (w)={\begin{pmatrix}s_{2}(n)&1\\0&1\end{pmatrix}}}$

La valuation 2-adique ${\displaystyle \nu _{2}(n)}$ d'une entier n (aussi appelée « ruler function ») est l'exposant de la plus grande puissance de 2 divisant n : ainsi ${\displaystyle \nu _{2}(8)=3}$ et ${\displaystyle \nu _{2}(9)=0}$. Les premières valeurs de la suite (c'est la suite  A007814) sont, en commençant par n=1 :

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,

La sous-suite des indices pairs est la suite nulle, la suite des indices impairs est la suite de départ dont chaque terme est augmenté de 1. À nouveau, le 2-noyau est formé de la suite de départ et de la suite constante ${\displaystyle (1)}$.

• Toute suite k-automatique est k-régulière[1].
• Une suite k-régulière qui ne prend qu'un nombre fini de valeurs est k-automatique[6].
• Si une suite ${\displaystyle (a(n))_{n\geq 0}}$ est k-régulière, alors la suite ${\displaystyle (a(n){\bmod {m}})_{n\geq 0}}$ est k-automatique pour tout ${\displaystyle m\geq 1}$ (mais la réciproque est fausse)[7].

• La famille des suites k-régulières est fermée par addition, par multiplication par une constante, par multiplication terme-à-terme (produit de Hadamard) et par produit de Cauchy[8]

Le produit terme-à-terme (aussi appelé produit de Hadamard) de deux suites ${\displaystyle (a(n))_{n\geq 0}}$ et ${\displaystyle (b(n))_{n\geq 0}}$ est la suite

${\displaystyle (a(n)b(n))_{n\geq 0}}$

Le produit de Cauchy des deux suites est la suite ${\displaystyle (c(n))_{n\geq 0}}$ définie par

${\displaystyle c(n)=\sum _{i+j=n}a(i)b(j)}$.

• Si ${\displaystyle (a(n))_{n\geq 0}}$ est une suite ${\displaystyle k}$-régulière et si ${\displaystyle p}$ et ${\displaystyle q}$ sont des entiers naturels, alors la suite ${\displaystyle (a(pn+q))_{n\geq 0}}$ est ${\displaystyle k}$-régulière.

• Les termes d'une suite k-régulière croissent au plus polynomialement en fonction de leur indice[9]. La suite ${\displaystyle f(n)_{n\geq 0}}$ des valeurs d'un polynôme à valeurs entières ${\displaystyle f(x)}$ est k-régulière pour tout entier ${\displaystyle k\geq 2}$.

La notion de suite k-régulière s'étend comme suit à un anneau ${\displaystyle R}$. Soit ${\displaystyle R'}$ un sous-anneau noethérien commutatif de ${\displaystyle R}$. Une séquence ${\displaystyle a(n)_{n\geq 0}}$ d'éléments de ${\displaystyle R}$ est '${\displaystyle (R',k)}$-régulièresi le ${\displaystyle R'}$-module engendré par les

${\displaystyle (a(k^{e}n+b))_{n\geq 0}}$ pour ${\displaystyle e\geq 0}$ et ${\displaystyle 0\leq b<k^{e}}$

est finiment engendré.

Soit ${\displaystyle s_{k}(n)}$ la somme des digits de l'écriture de ${\displaystyle n}$ en base ${\displaystyle k}$ et soit

${\displaystyle S_{k}(n)=\sum _{0\leq i\leq n}s_{k}(i)}$.

La suite ${\displaystyle (S_{k}(n))_{n\geq 0}}$ est le produit de Cauchy de la suite ${\displaystyle (s_{k}(n))_{n\geq 0}}$ et de la suite constante ${\displaystyle (1)}$. Elle est donc ${\displaystyle k}$-régulière.

La suite de Kimberling[10] est la suite ${\displaystyle (c(n))_{n\geq 0}}$ définie par ${\displaystyle c(0)=0}$ et pour ${\displaystyle n>0}$ par

${\displaystyle c(n)={\frac {1}{2}}(n/2^{\nu _{2}(n)}+1).}$

Ici ${\displaystyle 2^{\nu _{2}(n)}}$ est la plus haute puissance de 2 qui divise ${\displaystyle n}$. Les premières valeurs sont

0, 1, 1, 2, 1, 3, 2, 2, 4, 1, 5, . . .

C'est la suite A003602 de l'OEIS. On vérifie facilement que ${\displaystyle c(2n)=c(n)}$ et ${\displaystyle c(2n-1)=n}$ pour ${\displaystyle n\geq 1}$, donc la suite est 2-régulière.

Documents généraux

• Jean-Paul Allouche et Jeffrey Shallit, « The ring of k-regular sequences », Theoretical Computer Science, vol. 98,‎ 1992, p. 163–197 (DOI 10.1016/0304-3975(92)90001-v, lire en ligne).
• Jean-Paul Allouche et Jeffrey Shallit, « The ring of k-regular sequences, II », Theoretical Computer Science, vol. 307,‎ 2003, p. 3–29 (DOI 10.1016/s0304-3975(03)00090-2, lire en ligne).
• Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press, 2003, 571 p. (ISBN 978-0-521-82332-6, zbMATH 1086.11015, présentation en ligne)
• Jean Berstel et Christophe Reutenauer, Noncommutative rational series with applications, Cambridge, Cambridge University Press, coll. « Encyclopedia of Mathematics and Its Applications » (n^o 137), 2011, 248 p. (ISBN 978-0-521-19022-0, zbMATH 1250.68007, lire en ligne)
• Valérie Berthé et Michel Rigo (éditeurs), Sequences, groups, and number theory, Birkhäuser, coll. « Trends in Mathematics », 2018, 578 p. (ISBN 978-3-319-69151-0)
• Émilie Charlier, « First-order logic and numeration systems », dans Valérie Berthé, Michel Rigo (éditeurs), Sequences, groups, and number theory, Birkhäuser, coll. « Trends in Mathematics », 2018 (ISBN 978-3-319-69151-0), p. 89-142

Articles récents

• Clemens Heuberger, Daniel Krenn et Gabriel F. Lipnik, « Asymptotic analysis of q-recursive sequences », Algorithmica, vol. 84, n^o 9,‎ septembre 2022, p. 2480–2532 (ISSN 0178-4617, DOI 10.1007/s00453-022-00950-y, arXiv 2105.04334)