DEA d’ALGORITHMIQUE 1998-1999

Analyse d’algorithmes: Modèles combinatoires

                         Philippe.Flajolet@inria.fr
                    http://algo.inria.fr/flajolet/Teach/

Partie I. Séries de Dirichlet

On explore ici quelques propriétés des séries de Dirichlet, lesquelles sont à la base de la théorie analytique des nombres. Seule l’inversion de Moebius, équation (3), est nécessaire à la Partie II du problème. Q1. La fonction zeta de Riemann est définie par

ζ(s) := ∑_{n=1}^{∞} \frac{1}{n^{s}} .

Déterminer le meilleur s_{0} tel que la somme converge pour tout s complexe tel que ℜ(s) > s_{0}. (ℜ = partie réelle.) Que vaut lim_{s→s_{0}^{+}} ζ(s)?

Établir (sans lourd détail analytique) la formule dite du produit Eulérien,

ζ(s) = ∏_{p} \frac{1}{1 − 1/p^{s}} ,  (1)

valable pour s > s_{0}. (Ici, ∏_{p} signifie un produit étendu aux valeurs de p premiers, p = 2, 3, 5, 7, . . ..) Q2. Utiliser la question précédente pour établir par un argument tres simple d’analyse qu’il existe une infinité de nombres premiers. (Cette preuve ingénieuse du théorème d’Euclide est due à Euler.) Note, Les propriétés fines de ζ(s) sont à la base du théorème des nombres premiers (Riemann, puis Hadamard et de la Vallée-Poussin) d’après lequel le nombre de nombres premiers inférieurs à x, soit ϖ(x), est estimé par:

ϖ(x) = \frac{x}{log x}(1 + o(1)),  (2)

En admettant (2), montrer que le nombre de premiers dont la représentation binaire comporte exactement n bits est asymptotique à

c_{1} \frac{2^{n}}{n} ,

et déterminer c_{1}. Q3. Montrer que

\frac{1}{ζ(s)} = ∑_{n=1}^{∞} \frac{μ(n)}{n^{s}},

où ne prend que les valeurs 0, ±1; précisément: μ(n) = 0 dès que n est divisible par un carré (> 1), et

μ(p_{1}p_{2} ⋯ p_{r}) = (−1)^{r},

les p_{j} étant des premiers distincts. La suite des valeurs {1, −1, −1, 0, −1, 1, −1, …} est appelée suite de Moebius. Q4. Soit {a_{n}} une suite de complexes. On appelle série génératrice de Dirichlet associée à cette suite la somme

α(s) := ∑_{n≥1} a_{n}n^{−s}.

Étant donné trois suites a_{b}, b_{n}, c_{n} de séries de Dirichlet associées α(s), β(s), γ(s). Montrer l’équivalence

α(s) = β(s) · γ(s) ⟺ a_{n} = ∑_{d | n} b_{d}c_{n/d},

où la somme est étendue à tous les diviseurs d de n, ce qui est noté d | n. En déduire la formule d’inversion de Moebius: pour deux suite f_{n}, g_{n} quelconques, on a l’équivalence

f_{n} = ∑_{d | n} g_{d} ⟺ g_{n} = ∑_{d | n} μ(d)g_{n/d}.  (3)

Inverser la relation entre séries génératrices ordinaires:

f(z) = ∑_{k≥1} g(z^{k}),

en exprimant g(z) en fonction de f(z). On suppose g sans terme constant: g(0) = 0. Q5. [Facultatif] Soit Ω = {ω_{n}(z)} un système de fonctions. Les cas

Ω_{OGF} = \{z^{n}\}_{n=0}^{∞}, Ω_{EGF} = \{\frac{z^{n}}{n!} \}_{n=0}^{∞}, Ω_{DGF} = \{n^{−z}\}_{n=1}^{∞}

donnent lieu aux séries ordinaires, exponentielles, et de Dirichlet. On definit la fonction ζ et les coefficients de Moebius par

ζ_{Ω}(z) := ∑_{n} 1 · ω_{n}(z), \frac{1}{ζ_{Ω}(z)} := ∑_{n} μ_{Ω}(n)ω_{n}(z).

Remplir une matrice 4 × 3 dont les colonnes correspondent à OGF, EGF, DGF, et les lignes donnent: (i) la fonction zeta, (ii) les coefficients de Moebius, (iii) la relation entre coefficients qui exprime le produit de séries, (iv) la relation d’inversion de type Moebius. Pouvez-vous interpréter

[z^{n}]\frac{1}{2 − \frac{1}{1−z}} , [z^{n}]\frac{1}{2 − e^{z}} , [n^{−z}]\frac{1}{2 − ζ(z)},

où l’on utilise la généralisation naturelle de la fonction coefficient [ ·]? (Une telle théorie transverse a été développée par Rota.)

Partie II. Polynômes

Cette partie du problème montre que des objets algébriques peuvent se traitent par les méthodes de la combinatoire énumérative. Les développements qui suivent sont à la base de l’analyse d’algorithmes probabilistes en calcul formel et en théorie des codes. Rappel. Pour un nombre premier p, on considère le corps F = F_{p} formé par les entiers pris modulo p. On travaille dans l’anneau F [x] des polynômes à coefficients dans F. On rappelle que, dans cet anneau, il existe une division euclidienne et une propriété de factorisation unique. Les élements de F [x] qui sont indécomposables (l’équivalent des nombres premiers) sont appelés polynômes irreductibles: f est irréductible si f = g · h implique g = 1 ou h = 1. Fixons p. On désigne par P la classe des polynômes unitaires (dont le coefficient de tête vaut 1) et par I la sous-classe des polynômes unitaires et irréductibles. Par convention, la taille (au sens combinatoire) d’un polynôme est son degré (au sens algébrique). La sous-classe Q ⊂ P représente les polynômes unitaires “sans carrés”, c-à-d, non divisibles par un carré: f est sans carré si f = g · h^{2} implique h = 1. Q1. Montrer que la série génératrice de P vaut

P (z) = \frac{1}{1 − pz} .

Observer que tout f(x) ∈ F [x] s’écrit f(x) = g(x)·h(x)^{2} où g est sans carré et h quelconque. D’autre part, sii H est une classe de polynômes de série génératrice H(z), la série génératrice de l’ensemble {h(x)^{2} / h(x) ∈ H} vaut H(z^{2}). En déduire la série génératrice de Q. Calculer la probabilité qu’un polynôme pris uniformément dans P_{n} soit sans carré. Q2. Montrer que

\begin{aligned}P (z) & = & ∏_{n=1}^{∞}(1 − z^{n})^{−I_{n}} \\ & = & exp (∑_{k=1}^{∞} \frac{1}{k}I(z^{k})) . \end{aligned}

Exprimer la relation correspondante entre zP′(z)/P (z) et J(z) = zI′(z). En déduire la relation

I_{n} = \frac{1}{n} ∑_{d | n} μ(d)p^{n/d},

où μ est le coefficient de Moebius. Q3. Montrer brièvement que

I_{n} = \frac{p^{n}}{n} (1 + o(1)).

Comment se compare la situation des polynômes sur un corps fini à celle des entiers? On suppose qu’on dispose de deux procédures: draw(n) tire au hasard un élément de P_{n} et irred(f) répond vrai ou faux selon que f est irréductible ou non. Combien d’essais en moyenne effectue l’algorithme de tirage d’un polynôme irréductible suivant?

     repeat
         f := draw(n);
     until irred(f);

Quelle est la variance du nombre de tirages? Q4. Soit ω(f) le nombre de facteurs irréductibles de f comptés avec multiplicité, par exemple,

ω ((1 + x)(3 + x + x^{3})^{5}(4 + x^{7})^{2}(2 + 2x + x^{9})) = 1 + 5 + 2 + 1 = 9.

Soit P_{n,k} le nombre de f ∈ P_{n} tels que ω(f) = k et P (z, u) := ∑_{n,k} P_{n,k}u^{k}z^{n}. Montrer que

\begin{aligned}P (z, u) & = & ∏_{n=1}^{∞}(1 − uz^{n})^{−I_{n}} \\ & = & exp (∑_{k=1}^{∞} \frac{u^{k}}{k} I(z^{k})) . \end{aligned}

Montrer que l’espérance de ω prise sur l’ensemble des polynômes P_{n} vaut exactement

M_{n} = coeff[z^{n}] (\frac{∂}{∂u}P (\frac{z}{p}, u))_{u=1} .

Déterminer un équivalent asymptotique de

[z^{n}] (I(\frac{z}{p}) + I(\frac{z^{2}}{p^{2}} ) + I(\frac{z^{3}}{p^{3}} ) + ⋯)

et en déduire que

M_{n} = log n(1 + o(1)).

(Se limiter aux grandes étapes de la démonstration.) [Facultatif] Qu’est-ce que ce résultat suggère quant au nombre moyen de facteurs premiers d’un entier ≤ x? Q5. [Facultatif] Montrer que le nombre d’éléments de P_{n} qui ont n_{1} facteurs irréductibles de degré 1, n_{2} de degré 2, etc, vaut (en marquant la dépendance en p):

G(n_{1}, n_{2}, …; p) = ∏_{j=1}^{n} \binom{I_{n_{j}} + n_{j} − 1}{n_{j}}.

Les I_{n} sont bien sûr ceux qui sont relatifs à la caractéristique p du corps: I_{n} = I_{n}(p). Calculer pour n fixé et p → +∞ la limite

g(n_{1}, n_{2}, …) = lim_{p→+∞} \frac{G(n_{1}, n_{2}, …; p)}{p^{n}}.

Montrer que g(n_{1}, n_{2}, …) est aussi le nombre de permutations de n qui ont n_{1} cycles de taille 1, n_{2} cycles de taille 2, etc. En résumé la décomposition en facteurs irréductibles d’un polynôme de degre fixé n sur un corps de grande cardinalité ressemble à la décomposition en cycles d’une permutation de la même taille n.

Partie III. Explorations de calcul formel

Il s’agit là d’un exercice à préparer en binome. Le résultat peut fort bien être une feuille de travail Maple, mais éditée convenablement et brièvement commentée, ou bien un “compterendu” d’expérience manuscrit. Le problème traité ici est une simplification d’une situation qui s’est présentée réellement il y a quelques années. Les statisticiens construisent des arbres de classification appelés hiérarchies. Le problème consiste à analyser les propriétés des hiérarchies aléatoires sur la base du principe qu’une classification produite dans le monde réel (par ex. par un programme d’analyse statistique) a d’autant plus de “chances” d’être significative qu’elle s’écarte des lois du hasard. D’où l’intérêt de quantifier l’aléa! Les hiérarchies sont des arbres dont les sommets externes sont les n objets à classifier (la taille vaut alors n) et dont les sommets internes (représentant les “classes”) ont degré tous ≥ 2, car il faut que la classification soit non triviale. Par exemple:

     C=chat, H=homme, L=lion, O=orang-outang, T=tigre, V=vache
                  .              n = 5 (nombre de sommets externes)
                 /|\
                / | \            3 sommets internes (classes)
               .  V  .
              /|\    /\
             T C L   H O

Les hiérarchies sont donc “non-planaires” (pas de distinction gauche/droite) et enracinées, de par l’origine du problème. Les objets à classifier sont assimilés aux étiquettes 1, …, n. En d’autres termes:

La classe H des hiérarchies est la classe des arbres enracinés non-planaires, étiquetés aux sommets externes seulement (qui déterminent la taille) et dont les sommets internes ont tous degrés ≥ 2.

Symboliquement:

H = Z + Set(H, card ≥ 2).

III.1 Dénombrement asymptotique des hiérarchies Q1. On commence par se convaincre que la série génératrice exponentielle des hierarchies vérifie l’équation

H(z) = z + (e^{H(z)} − 1 − H(z)) .

Maple sait trouver pour nous une solution au moyen de la fonction “spéciale” LambertW (W) qui est la solution de

z = W e^{W} .

définie et positive pour z ∈ [0, e^{−1}]. (En terme de la fonction d’arbre du cours, T (z) , on a

W (z) = −T (−z); essayer series(LambertW(z),z=0,10);)

     eqH:=H=z+exp(H)-1-H; Hz:=solve(eqH,H);

Calculer les 30 premiers coefficients

     Hs:=series(Hz,z=0,31);
     for i from 0 to 30 do
         c[i]:=coeff(Hs,z,i)*1.0 od;

et deviner une loi très approximative de croissance de

c_{i} = [z^{i}] H(z).

On pourra s’aider de

     plot([seq([i,c[i+1]/c[i]],i=5..30)],0..30,0..3);

Le nombre de hiérarchies de taille n vaut H_{n} = n!c_{n}. Q2. On sait que le rayon de convergence d’une série entière à coefficients positifs est égal à la distance entre l’origine et la singularité positive la plus proche. Ici, la singularité correspond à une pente verticale (de dérivée infinie), comme on peut s’en convaincre par un plot.

     plot(Hz,z=0..0.5); plot(diff(Hz,z),z=0..0.5);
     H1z:=normal(diff(Hz,z));

Par une suite de tracés de ce type, on devra obtenir une approximation à 0.001 près de la singularité positive,

ρ =??? ± 0.001.

Combien de chiffres environ comporte la représentation décimale de H_{1000}? Q3. On se propose de déterminer maintenant exactement la singularité positive ρ. En supposant qu’elle provient de l’annulation du denominateur de \frac{d}{dz}H(z), on déterminera alors sa valeur exacte (utliser solve):

ρ =???

On peut alors tenter de comprendre de quelle manière H(z) devient singulière lorsque z tend vers ρ par valeurs inférieures. Il est commode de poser z = ρ − h et faire h → 0^{+}, ce qui s’obtient par un développement en série.

    map(simplify,series(subs(z=rho-h,Hz),h=0));

On suppose que c_{n} est asymptotiquement equivalent a ce que l’on obtient en ne retenant que les deux premiers termes, soit

c_{n} ∼ [z^{n}] (c_{0} − c_{1}\sqrt{ρ − z}) .

En d’autres termes, on suppose, et cela est justifié par l’analyse de singularité que:une bonne approximation de la fonction donne une bonne approximation des coefficients. En déduire une formule asymptotique pour c_{n} de la forme

c_{n} ∼ K_{1}K_{2}^{n}n^{K_{3}}, K_{1}, K_{2}, K_{3} =???.

Vérifier comme suit:

     for i from 2 to 30 do
             evalf(coeff(Hs,z,i)/rho^(-i+1/2)*i^(3/2)*sqrt(Pi))
     od;

Avec quelle précision estimez-vous pouvoir prévoir la valeur de H_{1000}? III.2 Nombre d’étapes de classification. On s’intéresse au nombre de sommets internes de l’arbre (le nombre de classes). Soient H_{n,k} le nombre de hiérarchies de taille n ayant k sommets internes et n sommets externes. On se convaincra (ou bien, on admettra) que la série double

H(z, u) = ∑_{n,k} H_{n,k}u^{k} \frac{z^{n}}{n!}

vérifie l’equation

H(z, u) = z + u (e^{H(z,u)} − 1 − H(z, u)) .

Q4. Résoudre cette équation en termes de la fonction W de Lambert. On pose

G(z) := (\frac{∂}{∂u}F (z, u))_{u=1}

Exprimer de même G(z) (la dérivation s’obtient par diff). Soit d_{n} := [z^{n}]G(z), de sorte que le nombre moyen de sommets internes dans une hiérarchie de taille n vaut

μ_{n} = \frac{d_{n}}{c_{n}} .

On tabulera μ_{n} pour n = 2 . . 30. Deviner une formule approximative décrivant la croissance asymptotique de μ_{n}. Chercher a améliorer l’estimation, empiriquement (en devinant simultanément une valeur approchée du terme d’erreur), et/ou en évaluant

γ := lim_{z→ρ^{−}} \frac{G(z)}{z \frac{d}{dz}H(z)}.

Estimer au mieux μ_{1000}. Un programme de classification produit sur n = 1000 données une hierarchie qui comprend 273 classes (sommets internes). La hiérarchie ainsi constituée ressemble-t-elle à une hiérarchie aléatoire?

[ ] OUI [ ] NON [ ] INCERTAIN