Accueil🇫🇷Chercher

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èrek>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 OEISA000120. 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 OEISA007814.

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 un entier. Une suite

d'entiers est dite -régulière s'il existe un nombre fini de suites d'entiers

et, pour tout et tout , des entiers

tels que pour tout , on a

.

En d'autres termes, chacune des sous-suites

est combinaison linéaire, à coefficients entiers, des suites données . Pour simplifier l'expression ci-dessus, il est utile de donner un nom aux sous-suites considérées. On appelle -noyau[3] de la suite l'ensemble

des sous-suites pour et . Alors, et de manière plus synthétique, la suite est -régulière si son -noyau est contenu dans un -module finiment engendré de suites d'entiers[4].

Représentation linéaire

Soit un alphabet fini et soit un demi-anneau. Une série formelle est une application de dans . L'image d'un mot est noté . La série elle-même est aussi notées [5].

Une série formelle est dite -reconnaissable s'il existe un entier , des vecteurs , et un morphisme telle que

pour tout .

Le triple est une représentation linéaire de .

Une suite est -régulière si la série formelle

est -reconnaissable, où . Ici

est le nombre représenté par son développement en base .

Premiers exemples

Somme des bits

La suite, traditionnellement notée :

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 OEISA007814 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

,

tout élément du 2-noyau est une combinaison linéaire de la suite de départ et de la suite constante .

Une représentation linéaire de la série est donnée par

.

On a alors, pour , :

Valuation 2-adique

La valuation 2-adique d'une entier n (aussi appelée « ruler function ») est l'exposant de la plus grande puissance de 2 divisant n : ainsi et . Les premières valeurs de la suite (c'est la suite OEISA007814) 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 .

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 est k-régulière, alors la suite est k-automatique pour tout (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 et est la suite
Le produit de Cauchy des deux suites est la suite définie par
.
  • Si est une suite -régulière et si et sont des entiers naturels, alors la suite est -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 des valeurs d'un polynôme à valeurs entières est k-régulière pour tout entier .

Généralisation à un anneau noethérien

La notion de suite k-régulière s'étend comme suit à un anneau . Soit un sous-anneau noethérien commutatif de . Une séquence d'éléments de est '-régulièresi le -module engendré par les

pour et

est finiment engendré.

Autres exemples de suites

Somme cumulée de digits

Soit la somme des digits de l'écriture de en base et soit

.

La suite est le produit de Cauchy de la suite et de la suite constante . Elle est donc -régulière.

La suite de Kimberling

La suite de Kimberling[10] est la suite définie par et pour par

Ici est la plus haute puissance de 2 qui divise . 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 et pour , donc la suite est 2-régulière.

Notes et références

Notes

  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
Articles récents
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.