ENS Informatique Fondamentale (Maths Info) MP 2012Sujet et corrigé

(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 (s_n)_(n ∈ ℕ) d'éléments de ℝ. L'ensemble des séries formelles est noté ℝ[[X]]. Les opérations usuelles d'addition (terme à terme) et de multiplication par un scalaire (terme à terme) sur les suites font naturellement de ℝ[[X]] un ℝ-espace vectoriel.

La suite ( s_n ), considérée comme série formelle, est également notée ∑_n s_n X^n. 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 ∑_n n!X^n est un élément de ℝ[[X]], 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 ℝ[[X]] une opération de multiplication de deux séries formelles de la manière suivante : si S = ∑_n s_n X^n et T = ∑_n t_n X^n, alors S.T = U = ∑_n u_n X^n, avec

Lorsqu'une série formelle S est définie, s_n désigne implicitement son "coefficient de degré n ", i.e. S = ∑_n u_n X^n. Deux séries formelles S et T sont égales si et seulement si on a, pour tout n ≥ 0, s_n = t_n.

On note X_F la série formelle (u_n)_(n ≥ 0) définie par u_1 = 1, u_i = 0 pour i ≠ 1; 1_F la série formelle (v_n)_(n ≥ 0) définie par v_0 = 1, v_i = 0 pour i ≠ 0; et 0_F 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 1_F comme élément neutre et 0_F comme élément absorbant.

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

Question 1.1. Quelle est la suite associée à la série formelle (X_F)^n ?

Question 1.2. Montrer qu'il existe une unique application linéaire f : ℝ[X] → ℝ[[X]] telle que, pour tout n ≥ 0, f(X^n) = (X_F)^n, et qu'il s'agit d'un morphisme injectif d'algèbres.

Dans la suite, on identifiera un polynôme P ∈ ℝ[X] à son image f(P) ∈ ℝ[[X]], et on pourra considérer que ℝ[X] est un sous-ensemble de ℝ[[X]]. On se gardera toutefois d'utiliser la notation S(a) lorsque a est un réel et que S est une série formelle qui n'est pas un polynôme.

Pour une série formelle S = ∑_n s_n X^n non identiquement nulle, la valuation de S est définie parν(S) = min{i : s_i ≠ 0}. Pour deux séries formelles S et T, on définit

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

Question 1.4. Soient S et T deux séries formelles. Montrer que S.T = 0_F si et seulement si S = 0_F ou T = 0_F.

Soit U ∈ ℝ[[X]], et U^((n)) une suite d'éléments de ℝ[[X]]. On dit que la suite (U^((n))) converge vers U au sens des séries formelles, si lim_(n → ∞)d(U^((n)), U) = 0.

On définit également la convergence d'une série de séries formelles, de la manière suivante : si (V^((n))) est une suite d'éléments de R[[X]], on dira que la série ∑_n V^((n)) converge, avec comme somme U, si la suite U^((n)) = ∑_(k = 0)^n V^((k)) converge vers U.

(a). Montrer que la suite de polynômes définie par P_n(X) = 1 + (1/n)X ne converge pas au sens des séries formelles. Existe-t-il une norme sur ℝ[X] pour laquelle elle converge?
(b). Montrer qu'une condition nécessaire et suffisante pour que la suite (U^((n))) de séries formelles converge vers une série formelle U est que, pour tout k ≥ 0, la suite (u_k^((n)))_(n ≥ 0) soit ultimement constante et égale à u_k.
(c). Montrer qu'une suite de séries formelles (U^((n))) converge au sens des séries formelles si et seulement si la suite (U^((n + 1)) − U^((n))) converge vers la série 0_F.

Question 1.6. Montrer que toute série formelle ∑u_n X^n est la somme de la série de séries formelles ∑_n S_n, où S_n = u_n(X_F)^n.

Question 1.7. On définit sur ℝ[[X]] une relation binaire ≤ _F de la manière suivante : ∑_n u_n X^n ≤ _F∑_n v_n X^n si et seulement si, pour tout n ≥ 0, on a u_n ≤ v_n. Montrer que ≤ _F est une relation d'ordre sur ℝ[[X]].

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 ℝ[[X]] dans lui-même, une série formelle S est une solution de l'équation Φ(S) = 0_F si l'image de S par Φ est la série nulle. De même, une série formelle est une solution de l'équation Φ(S) = S si S est sa propre image par Φ ( S est un point fixe de Φ ).

Question 2.1. Soit S une série formelle non identiquement nulle, et k ∈ ℕ. Montrer qu'il existe une série formelle T telle que l'on ait S = (X_F)^k ⋅ T, si et seulement si ν(S) ≥ k.

Question 2.2. La série formelle T est un inverse (multiplicatif) de la série formelle S, si l'on a S.T = 1_F.
(a). En supposant connus les coefficients de S, écrire de manière générique les équations sur les coefficients de T qui caractérisent le fait que T soit un inverse de S.
(b). Montrer qu'une série S = ∑_(n ≥ 0)s_n X^n admet un inverse si et seulement si s_0 ≠ 0, et que cet inverse est alors unique.
(c). Soit S = ∑_n n!X^n, et soit T = ∑_n t_n X^n l'inverse de S. Calculer t_0, t_1, t_2 et t_3.

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

Une série formelle solution d'une équation de la forme P − Q.S = 0_F, où P et Q ≠ 0 sont des polynômes, est appelée série rationnelle.

Question 2.4. Soit (s_n)_(n ≥ 0) une suite satisfaisant, pour tout n ≥ 2, s_n = s_(n − 1) + s_(n − 2). Montrer que la série formelle S = ∑_n s_n X^n est rationnelle.

Question 2.5. Montrer que, pour toute série rationnelle S ≠ 0_F, il existe un unique couple (P^∗, Q^∗) de polynômes premiers entre eux, avec P^∗ unitaire, tels que S soit l'unique solution de l'équation P^∗ − Q^∗.S = 0_F. Dans la suite, ces deux polynômes seront notés respectivement Num(S) et Den(S).

Question 2.6. Soit S une série rationnelle. Montrer qu'il existe un entier k ≥ 0, un entier n_0 ≥ 0, et des réels a_1, …, a_k tels que les coefficients (s_n)_(n ≥ 0) satisfassent, pour tout n ≥ n_0,

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 P et Q deux polynômes non identiquement nuls, avec Q(0) = 1. On suppose que P et Q sont donnés par leurs degrés respectifs d_P et d_Q (considérés comme des constantes), et leurs coefficients (p_i)_(0 ≤ i ≤ d_P) et (q_j)_(0 ≤ j ≤ d_Q). Soit alors S la série formelle d'équation P − Q.S = 0_F. Montrer qu'il est possible de calculer le coefficient s_n en O(n) opérations arithmétiques sur des nombres entiers.

Une fonction Φ de ℝ[[X]] dans lui-même est dite contractante si, pour toutes séries formelles S et T telles que S ≠ T, on a

(a). Montrer que si Φ est contractante, alors l'équation S = Φ(S) a au plus une solution.
(b). On suppose Φ contractante. Soit S^((0)) une série formelle quelconque. On définit la suite de séries formelles (S^((n)))_(n ≥ 0)parS^((n + 1)) = Φ(S^((n))) pour n ≥ 0. Montrer que, pour tout n > 0 tel que S^((n + 1)) ≠ S^((n)), on a

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

Une équation de la forme Φ(S) = 0_F est algébrique s'il existe un entier k ≥ 1 et k + 1 polynômes P_0, …, P_k, non tous nuls, tels que Φ(S) 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 Φ(S) = 0_F, pour laquelle le polynôme P_1 ne s'annule pas en 0 , alors que chaque polynôme P_i pour 1 < i ≤ k s'annule en 0 . Montrer qu'une telle équation a une solution unique dans ℝ[[X]].

Question 2.11. Soit P ∈ ℝ[X] un polynôme tel que l'on ait P(0) = p_0 > 0. On s'intéresse aux solutions de l'équation S^2 − P = 0.
(a). Montrer qu'une condition nécessaire pour qu'une série formelle S = ∑_n s_n X^n soit solution de l'équation S^2 − P = 0 est que s_0 appartienne à un ensemble E = {s, s^′} à déterminer.
(b). Montrer que l'équation S^2 − P = 0 a exactement deux solutions dans ℝ[[X]].

Soit A un ensemble fini non vide. A^∗ désigne l'ensemble des suites finies d'éléments de A, suites qui sont appelées mots sur l'alphabet A. On supposera systématiquement que les suites
finies non vides sont de la forme (w_k)_(1 ≤ k ≤ n), i.e. sont indexées à partir de 1 . L'entier n est alors la longueur du mot, notée |w|. 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 (a, b, b, a) (de longueur 4) se note abba.

Un langage L est une partie de A^∗; l'ensemble des langages sur l'alphabet A est noté L(A).
Une occurrence d'une lettre a ∈ A dans un mot w est un indice 1 ≤ i ≤ |w| tel que l'on ait w_i = a. Le nombre d'occurrences de a dans w est noté |w|_a.

Si L est un langage, on note L_n = L ∩ A^n, pour tout entier n, l'ensemble des mots de L dont la longueur est n, et ℓ_n = #L_n. On a donc en particulier ℓ_0 = 1 ou ℓ_0 = 0 selon que ε appartient ou non à L.

On définit la série génératrice du langage L comme la série formelle S_L = ∑_n ℓ_n X^n.

Question 3.1. Soient L et L^′ deux langages. Montrer que, si L ⊂ L^′, alors on a S_L ≤ _F S_(L^′), et que, si de plus on a S_L = S_(L^′), alors L = L^′.

Question 3.2. Soient L et L^′ deux langages. Montrer que S_(L ∪ L^′) ≤ _F S_L + S_(L^′), et qu'il y a égalité si et seulement si les langages L et L^′ sont disjoints.

L'ensemble A^∗ est muni d'une loi de composition interne dite produit de concaténation, notée . et définie comme suit : si u = (u_k)_(1 ≤ k ≤ n) et v = (v_k)_(1 ≤ k ≤ m) sont deux mots de longueurs respectives n et m, u.v est le mot w, de longueur n + m, 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 L et L^′ comme le langage L.L^′ défini par : w ∈ L.L^′ si et seulement s'il existe deux mots u ∈ L et v ∈ L^′ tels que l'on ait w = u.v. Lorsque l'un des langages est réduit à un unique mot, on s'autorise un abus de notation consistant par exemple à écrire w.L pour le langage {w}.L. Cette définition s'étend à un produit de plus de deux langages : si L_1, …, L_k sont des langages, L_1.L_2….L_k désigne l'ensemble des mots w tels qu'il existe des mots w_i ∈ L_i (pour 1 ≤ i ≤ k ) avec w = w_1.w_2…..w_k.

Le produit L_1.L_2….L_k est dit non ambigu si, pour tout mot w ∈ L_1.L_2….L_k, le k-uplet de mots (w_i)_(1 ≤ i ≤ k) est unique.

Un mot u est un préfixe d'un mot w s'il existe un mot v tel que l'on ait w = u.v; en particulier, le mot vide ε est préfixe de tout mot, et tout mot est préfixe de lui-même. Un langage L est dit préfixe si, pour tout couple (w, w^′) ∈ L^2, w est préfixe de w^′ si et seulement si w = w^′ (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 ( a est préfixe de ab ), mais le langage {a, ba} l'est.

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

Question 3.4. Soient L et L^′ deux langages.

Question 3.5. On définit un langage F ⊂ {a, b}^∗ sur l'alphabet A = {a, b}, de la manière suivante : F est l'ensemble des mots (y compris le mot vide) qui ne contiennent pas deux occurrences consécutives de la lettre b, i.e. l'ensemble des mots w = a_1…a_n (avec a_i ∈ {a, b} pour chaque i) tels que, pour tout 1 ≤ i ≤ n − 1, a_i ≠ b ou a_(i + 1) ≠ b.
(a). Montrer que F satisfait l'identité ensembliste

(b). Montrer que la série génératrice S_F = ∑_n f_n X^n de F est une série rationnelle, et déterminer Num(S_F) et Den(S_F).
(c). Donner une relation de récurrence définissant la suite (f_n)_(n ≥ 0).

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

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

Question 3.7. Soit (L_n)_(n ≥ 0) une suite de langages sur un même alphabet fini A. On suppose que l'on a, pour tout n ≥ 0, L_n ⊂ L_(n + 1). On note S^((n)) la série génératrice du langage L_n. Montrer que la suite (S^((n))) converge au sens des séries formelles vers la série génératrice S_L du langage L = ∪ _n L_n 。

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

On définit deux suites de langages (K_n)_(n ≥ 0) et (M_n)_(n ≥ 0), de la manière suivante : K_0 = ∅, M_0 = A^∗, et pour n ≥ 0, K_(n + 1) = Ψ(K_n) et M_(n + 1) = Ψ(M_n). Enfin, on pose K = ∪ _n K_n et M = ∩ _n M_n.

(a). Montrer que l'on a, pour tout n ≥ 0, K_n ⊂ K_(n + 1) ⊂ M_(n + 1) ⊂ M_n.
(b). Montrer que K et M satisfont K = Ψ(K) ⊂ Ψ(M) ⊂ M.
(c). Montrer que, si L est un langage qui satisfait L = Φ(L), alors K ⊂ L ⊂ Ψ(M).

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

où ψ_0 ∈ L(A) est un langage fixé et chaque ψ_ℓ (pour 1 ≤ ℓ ≤ k ) est une fonction (A^∗)^ℓ → L(A) qui, à chaque ℓ-uplet de mots, associe un langage.

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

Trouver un entier k 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 (w_1, …, w_ℓ) et tout mot w ∈ ψ_ℓ(w_1, …, w_ℓ), on a |w| > ∑_(i = 1)^ℓ|w_i|.

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

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

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

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 U = ∑_n u_n X^n, on notera ∑_n u_n t^n la série entière correspondante, et, une fois la convergence en un point t (qui sera toujours réel) établie, on notera U~(t) la valeur en t de la fonction somme.

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

Question 4.2. Soient T et U 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 V = T + U et W = T.U ont également un rayon de convergence strictement positif, et que l'on a, pour |t| < ρ (pour un certain ρ > 0), V~(t) = T~(t) + U~(t) et W~(t) = T~(t).U~(t).

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