Suite régulière

En théorie des nombres, en informatique théorique et en combinatoire des mots, une suite régulière ou plus précisément une suite k-régulière où k>1 est un entier, est une suite d'entiers qui est définie par des relations de dépendance linéaire de certaines de ses sous-suites. Les sous-suites sont celles dont les indices forment des progressions arithmétiques dont les raisons sont des puissances de k. La condition est que toutes ces sous-suites appartiennent à un espace vectoriel (ou un module) finiment engendré.

Il apparaît qu'un nombre considérable de suites d'entiers figurent dans cette catégorie. De plus, les suites k-régulières qui ne prennent qu'un nombre fini de valeurs sont exactement les suites k-automatiques.

La suite

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  A000120. Un autre exemple est la suite

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, . . .

des exposants des plus hautes puissances de 2 divisant les entiers (appelée en anglais la « ruler function »). C'est la suite  A007814.

Le concept de suite k-régulière a été introduit par Allouche et Shallit[1]. Ils en présentent un développement détaillé dans leur livre[2]. Le lien avec les séries rationnelles en variables non commutatives, déjà mentionné dans leur article[1], est aussi détaillé dans le chapitre 5 du livre Berstel et Reutenauer 2011. Une présentation synthétique est donnée dans le premier chapitre (section 1.6.2 : Regular sequences) du livre Berthé et Rigo 2018.

Définition

Comme pour les suites automatiques, il existe plusieurs définitions équivalentes : par un ensemble de relations de récurrence, par une représentation matricielle, Il est commode de noter une suite d'entiers de façon fonctionnelle, c'est-à-dire comme une fonction des entiers naturels dans les entiers.

Une première formulation de la définition est la suivante.

Noyau

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].

Représentation linéaire

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}$.

Premiers exemples

Somme des bits

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}}}$

Valuation 2-adique

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)}$.

Propriétés générales

Suites régulières et suites automatiques

• 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].

Propriétés de fermeture

• 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.

Croissance des coefficients

• 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}$.

Généralisation à un anneau noethérien

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é.

Autres exemples de suites

Somme cumulée de digits

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

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.

Notes et références

1. Allouche et Shallit 1992
2. Allouche et Shallit 2003, chap.16
3. Ce terme est aussi employé dans le cadre des suites automatiques.
4. Une subtile différence existe entre la définition originale d'Allouche et Shallit et celle adoptée par Berthé et Rigo : pour ces derniers, la condition est que le noyau lui-même est finiment engendré (et pas seulement contenu dans un module finiment engendré.
5. On suit ici la définition donnée par Émilie Charlier dans son chapitre First-order logic and numeration systems, section 3.4.1 dans le livre Berthé et Rigo 2018
6. Allouche et Shallit 2003, Theorem 16.1.5.
7. Allouche et Shallit 2003, Corollary 16.1.6.
8. Allouche et Shallit 2003, Theorem 16.2.1.
9. Allouche et Shallit 1992, Theorem 2.10.
10. Allouche et Shallit 2003, exemple 16.5.4.

Bibliographie

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)