(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Le présent sujet comporte 8 pages numérotées de 2 à 9 .

Une série formelle à coefficients dans est une suite d'éléments de . L'ensemble des séries formelles est noté . Les opérations usuelles d'addition (terme à terme) et de multiplication par un scalaire (terme à terme) sur les suites font naturellement de un -espace vectoriel.

La suite ( ), considérée comme série formelle, est également notée . La légitimité de cette notation sommatoire sera explorée plus tard ; pour l'instant, elle ne doit pas s'interpréter comme provenant d'une notion de série classique. Ainsi, la série formelle est un élément de , bien que la série entière correspondante ait un rayon de convergence nul. En particulier, en dehors de la dernière partie du problème, toute considération de rayon de convergence est exclue.

On définit sur une opération de multiplication de deux séries formelles de la manière suivante : si et , alors , avec

Lorsqu'une série formelle est définie, désigne implicitement son "coefficient de degré ", i.e. . Deux séries formelles et sont égales si et seulement si on a, pour tout .

On note la série formelle définie par pour la série formelle définie par pour ; et la série formelle dont tous les termes sont nuls. On admettra que le produit de séries formelles est commutatif et associatif, et admet comme élément neutre et comme élément absorbant.

Lorsque est un ensemble fini, on note le cardinal de .

Question 1.1. Quelle est la suite associée à la série formelle ?

Question 1.2. Montrer qu'il existe une unique application linéaire telle que, pour tout , et qu'il s'agit d'un morphisme injectif d'algèbres.

Dans la suite, on identifiera un polynôme à son image , et on pourra considérer que est un sous-ensemble de . On se gardera toutefois d'utiliser la notation lorsque est un réel et que est une série formelle qui n'est pas un polynôme.

Pour une série formelle non identiquement nulle, la valuation de est définie . Pour deux séries formelles et , on définit

(a). Montrer que définit une distance sur .
(b). Montrer que n'est pas une distance provenant d'une norme sur .

Question 1.4. Soient et deux séries formelles. Montrer que si et seulement si ou .

Soit , et une suite d'éléments de . On dit que la suite converge vers au sens des séries formelles, si .

On définit également la convergence d'une série de séries formelles, de la manière suivante : si est une suite d'éléments de , on dira que la série converge, avec comme somme , si la suite converge vers .

(a). Montrer que la suite de polynômes définie par ne converge pas au sens des séries formelles. Existe-t-il une norme sur pour laquelle elle converge?
(b). Montrer qu'une condition nécessaire et suffisante pour que la suite de séries formelles converge vers une série formelle est que, pour tout , la suite soit ultimement constante et égale à .
(c). Montrer qu'une suite de séries formelles converge au sens des séries formelles si et seulement si la suite converge vers la série .

Question 1.6. Montrer que toute série formelle est la somme de la série de séries formelles , où .

Question 1.7. On définit sur une relation binaire de la manière suivante : si et seulement si, pour tout , on a . Montrer que est une relation d'ordre sur .

Dans cette partie, nous nous intéressons à différentes formes d'équations portant sur des séries formelles, et à donner des conditions permettant d'affirmer l'existence et l'unicité de solutions.

Si est une fonction de dans lui-même, une série formelle est une solution de l'équation si l'image de par est la série nulle. De même, une série formelle est une solution de l'équation si est sa propre image par ( est un point fixe de ).

Question 2.1. Soit une série formelle non identiquement nulle, et . Montrer qu'il existe une série formelle telle que l'on ait , si et seulement si .

Question 2.2. La série formelle est un inverse (multiplicatif) de la série formelle , si l'on a .
(a). En supposant connus les coefficients de , écrire de manière générique les équations sur les coefficients de qui caractérisent le fait que soit un inverse de .
(b). Montrer qu'une série admet un inverse si et seulement si , et que cet inverse est alors unique.
(c). Soit , et soit l'inverse de . Calculer et .

Question 2.3. Soient et deux polynômes, non identiquement nul.
(a). Montrer qu'il existe au plus une série formelle telle que .
(b). Montrer que, si , alors il existe une série formelle telle que .
(c). Donner une condition nécessaire et suffisante sur et pour qu'une telle série formelle existe (sans nécessairement supposer ).

Une série formelle solution d'une équation de la forme , où et sont des polynômes, est appelée série rationnelle.

Question 2.4. Soit une suite satisfaisant, pour tout . Montrer que la série formelle est rationnelle.

Question 2.5. Montrer que, pour toute série rationnelle , il existe un unique couple de polynômes premiers entre eux, avec unitaire, tels que soit l'unique solution de l'équation . Dans la suite, ces deux polynômes seront notés respectivement et .

Question 2.6. Soit une série rationnelle. Montrer qu'il existe un entier , un entier , et des réels tels que les coefficients satisfassent, pour tout ,

Question 2.7. Réciproquement, démontrer que toute série formelle qui satisfait une condition de la forme (1) est rationnelle.

Question 2.8. Soient et deux polynômes non identiquement nuls, avec . On suppose que et sont donnés par leurs degrés respectifs et (considérés comme des constantes), et leurs coefficients et . Soit alors la série formelle d'équation . Montrer qu'il est possible de calculer le coefficient en opérations arithmétiques sur des nombres entiers.

Une fonction de dans lui-même est dite contractante si, pour toutes séries formelles et telles que , on a

(a). Montrer que si est contractante, alors l'équation a au plus une solution.
(b). On suppose contractante. Soit une série formelle quelconque. On définit la suite de séries formelles pour . Montrer que, pour tout tel que , on a

(c). Montrer que, si est contractante, alors l'équation a une solution unique.

Une équation de la forme est algébrique s'il existe un entier et polynômes , non tous nuls, tels que s'exprime sous la forme

Une éventuelle solution d'une équation algébrique est elle-même appelée série formelle algébrique.

Question 2.10. Soit une équation algébrique , pour laquelle le polynôme ne s'annule pas en 0 , alors que chaque polynôme pour s'annule en 0 . Montrer qu'une telle équation a une solution unique dans .

Question 2.11. Soit un polynôme tel que l'on ait . On s'intéresse aux solutions de l'équation .
(a). Montrer qu'une condition nécessaire pour qu'une série formelle soit solution de l'équation est que appartienne à un ensemble à déterminer.
(b). Montrer que l'équation a exactement deux solutions dans .

Soit un ensemble fini non vide. désigne l'ensemble des suites finies d'éléments de , suites qui sont appelées mots sur l'alphabet . On supposera systématiquement que les suites
finies non vides sont de la forme , i.e. sont indexées à partir de 1 . L'entier est alors la longueur du mot, notée . L'unique mot de longueur 0 , appelé mot vide, est noté .

Afin de simplifier les notations, on note les mots en écrivant directement la séquence de leurs lettres: ainsi, le mot (de longueur 4) se note .

Un langage est une partie de ; l'ensemble des langages sur l'alphabet est noté .
Une occurrence d'une lettre dans un mot est un indice tel que l'on ait . Le nombre d'occurrences de dans est noté .

Si est un langage, on note , pour tout entier , l'ensemble des mots de dont la longueur est , et . On a donc en particulier ou selon que appartient ou non à .

On définit la série génératrice du langage comme la série formelle .

Question 3.1. Soient et deux langages. Montrer que, si , alors on a , et que, si de plus on a , alors .

Question 3.2. Soient et deux langages. Montrer que , et qu'il y a égalité si et seulement si les langages et sont disjoints.

L'ensemble est muni d'une loi de composition interne dite produit de concaténation, notée . et définie comme suit : si et sont deux mots de longueurs respectives et est le mot , de longueur , défini par

On admettra que le produit de concaténation est associatif et admet comme élément neutre.
On définit le produit (ensembliste) de deux langages et comme le langage défini par : si et seulement s'il existe deux mots et tels que l'on ait . Lorsque l'un des langages est réduit à un unique mot, on s'autorise un abus de notation consistant par exemple à écrire pour le langage . Cette définition s'étend à un produit de plus de deux langages : si sont des langages, désigne l'ensemble des mots tels qu'il existe des mots (pour ) avec .

Le produit est dit non ambigu si, pour tout mot , le -uplet de mots est unique.

Un mot est un préfixe d'un mot s'il existe un mot tel que l'on ait ; en particulier, le mot vide est préfixe de tout mot, et tout mot est préfixe de lui-même. Un langage est dit préfixe si, pour tout couple est préfixe de si et seulement si (attention, la terminologie est un peu trompeuse : un langage préfixe est un langage qui ne contient pas de couples de mots distincts préfixes l'un de l'autre). À titre d'exemple, le langage fini {a,ab} n'est pas préfixe ( est préfixe de ), mais le langage l'est.

Question 3.3. Soit un langage préfixe, et un langage quelconque. Montrer que le produit est non ambigu.

Question 3.4. Soient et deux langages.

Question 3.5. On définit un langage sur l'alphabet , de la manière suivante : est l'ensemble des mots (y compris le mot vide) qui ne contiennent pas deux occurrences consécutives de la lettre , i.e. l'ensemble des mots (avec pour chaque tels que, pour tout ou .
(a). Montrer que satisfait l'identité ensembliste

(b). Montrer que la série génératrice de est une série rationnelle, et déterminer et .
(c). Donner une relation de récurrence définissant la suite .

Question 3.6. On définit un langage sur l'alphabet de la manière suivante : un mot est dans si et seulement si, d'une part, , et d'autre part, pour tout préfixe de , on a .
(a). Soient et deux mots de . Montrer que a. .
(b). Soit un mot non vide de . Montrer qu'il existe deux mots et de tels que l'on ait , et que ces deux mots sont uniques.
(c). Montrer que le langage satisfait l'identité ensembliste

(d). Montrer que la série génératrice satisfait l'équation

Question 3.7. Soit une suite de langages sur un même alphabet fini . On suppose que l'on a, pour tout . On note la série génératrice du langage . Montrer que la suite converge au sens des séries formelles vers la série génératrice du langage 。

Dans le reste de cette partie, désigne une fonction de dans lui-même. On suppose que est croissante au sens suivant : pour tous langages et , si alors .

On définit deux suites de langages et , de la manière suivante : , , et pour et . Enfin, on pose et .

(a). Montrer que l'on a, pour tout .
(b). Montrer que et satisfont .
(c). Montrer que, si est un langage qui satisfait , alors .

On suppose maintenant que peut s'exprimer de la manière suivante : pour tout langage ,

où est un langage fixé et chaque (pour ) est une fonction qui, à chaque -uplet de mots, associe un langage.

Question 3.9. Soient et trois langages fixés, et définie (pour cette question seulement) par

Trouver un entier et des permettant d'exprimer sous la forme précédente.

Question 3.10. Montrer qu'une telle fonction est croissante au sens précédemment défini.

Question 3.11. On suppose que chaque satisfait la condition suivante : pour tout -uplet de mots et tout mot , on a .

Montrer que sous ces conditions, le langage précédemment défini est l'unique langage tel que l'on ait .

Question 3.12. On se donne, sur un alphabet fixé, deux langages et , dont on suppose que est préfixe, et qu'aucun mot de n'a de préfixe dans .
(a). Montrer qu'il existe un unique langage tel que l'identité soit satisfaite, et que la série génératrice de satisfait l'équation

(b). Montrer que, si les langages et ont des séries génératrices rationnelles, alors il en est de même de .

Dans cette partie, on s'intéresse aux liens entre la théorie des séries formelles et celle des fonctions sommes de séries entières. Étant donnée une série formelle , on notera la série entière correspondante, et, une fois la convergence en un point (qui sera toujours réel) établie, on notera la valeur en de la fonction somme.

Question 4.1. Soit un alphabet fini, un langage d'alphabet , et la série génératrice de . Montrer que la série entière correspondant à a un rayon de convergence strictement positif.

Question 4.2. Soient et deux séries formelles dont les séries entières associées ont un rayon de convergence strictement positif. Montrer que les séries formelles et ont également un rayon de convergence strictement positif, et que l'on a, pour (pour un certain et .

Question 4.3. Soit la somme de la série entière correspondant à la série génératrice du langage défini à la question 3.6.
(a). Montrer que la fonction est, sur un voisinage de 0 , solution de l'équation fonctionnelle .
(b). Donner une expression analytique pour au voisinage de 0 .

Question 4.4. On note le coefficient de degré de , i.e., . Montrer que, pour , on a