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

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

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 -noyauCe terme est aussi employé dans le cadre des suites automatiques. 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'entiersUne 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é..

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 <ref>On suit ici la définition donnée par Émilie Charlier dans son chapitre dans le livre </ref>.

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 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 ) 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 ) 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. Une suite k-régulière qui ne prend qu'un nombre fini de valeurs est k-automatique.. Si une suite est k-régulière, alors la suite est k-automatique pour tout (mais la réciproque est fausse)..

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. 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.. 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''. 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 . On vérifie facilement que et pour , donc la suite est 2-régulière.

Notes et références

Bibliographie Documents généraux . .

Articles récents

régulière Catégorie:Combinatoire des mots Catégorie:Combinatoire