\documentstyle[12pt, fullpage]{article}
\parskip=2.5pt plus 0.5 pt minus 0.5pt
\parindent=0pt
\def\ds{\displaystyle}
\newcommand{\Frac}[2]{\frac{\ds{#1}}{\ds{#2}}}
\def\deg{\hbox{deg}}
\def\hat {\widehat}
\def \pn {\par \noindent}
\def\bar{overline}

\begin{document}

\begin{center}
{\Large \bf\sf DEA d'ALGORITHMIQUE 1998-1999} \\
{\large\bf\sf Analyse d'algorithmes: Mod\`eles combinatoires}\\
{\tt Philippe.Flajolet@inria.fr}\\
{\tt http://algo.inria.fr/flajolet/Teach/}
\end{center}

\begin{center}
\sc Partie I. S\'eries de Dirichlet
\end{center}

{\em On explore ici quelques propri\'et\'es des s\'eries de Dirichlet,
lesquelles sont \`a la base de la th\'eorie analytique des nombres. 
Seule l'inversion de Moebius, \'equation~(\ref{moebius}),
est n\'ecessaire \`a la Partie~II du probl\`eme.
}

{\bf Q1.} La fonction {\em zeta\/} de Riemann est d\'efinie par
\[
\zeta(s):=\sum_{n=1}^\infty \frac{1}{n^s}.
\]
D\'eterminer le meilleur $s_0$ tel que la somme converge pour tout $s$
complexe tel que $\Re(s)>s_0$. 
($\Re$ = partie r\'eelle.)
Que vaut $\lim_{s\to s_0^+}\zeta(s)$?

\'Etablir (sans lourd d\'etail analytique) la formule
dite du produit Eul\'erien,
\begin{equation}\label{euler}
\zeta(s)=\prod_p \frac{1}{1-1/p^s},
\end{equation}
valable pour $s>s_0$. (Ici, $\prod_p$ signifie un produit \'etendu aux
valeurs de $p$ premiers, $p=2,3,5,7,\ldots$\,.)

{\bf Q2.} Utiliser la question pr\'ec\'edente pour \'etablir 
par un argument tres simple d'analyse 
qu'il existe une infinit\'e de nombres 
premiers. (Cette preuve ing\'enieuse du th\'eor\`eme d'Euclide
est due  \`a Euler.)


{\bf Note,} Les propri\'et\'es fines de $\zeta(s)$ sont \`a la base du
th\'eor\`eme des nombres premiers (Riemann, 
puis Hadamard et de la Vall\'ee-Poussin)
d'apr\`es lequel
le nombre de nombres premiers inf\'erieurs
\`a~$x$, soit $\varpi(x)$, est estim\'e par:
\begin{equation}\label{pnt}
\varpi(x)=\frac{x}{\log x}(1+o(1)),
\end{equation}

En admettant~(\ref{pnt}),
montrer que le nombre de premiers dont la repr\'esentation binaire
comporte exactement $n$~bits est asymptotique \`a 
\[
c_1\frac{2^n}{n},
\]
et d\'eterminer $c_1$.

{\bf Q3.} Montrer que
\[
\frac{1}{\zeta(s)}=\sum_{n=1}^\infty \frac{\mu(n)}{n^s},
\]
o\`u ne prend que les valeurs $0,\pm1$; pr\'ecis\'ement:
$\mu(n)=0$ d\`es que $n$ est divisible par un carr\'e ($>1$),
et
\[
\mu(p_1p_2\cdots p_r)=(-1)^r,\]
les $p_j$ \'etant des premiers distincts.
La suite des valeurs  $\{1,-1,-1,0,-1,1,-1,\ldots\}$ est appel\'ee suite
de Moebius.

{\bf Q4.} Soit $\{a_n\}$ une suite de complexes. On appelle
{\em s\'erie g\'en\'eratrice de Dirichlet\/}
associ\'ee \`a cette suite la somme
\[
\alpha(s):=\sum_{n\ge1} a_n n^{-s}.
\]
\'Etant donn\'e trois suites $a_b,b_n,c_n$ de s\'eries de Dirichlet
associ\'ees $\alpha(s),\beta(s),\gamma(s)$. 
Montrer l'\'equivalence
\[
\alpha(s)=\beta(s)\cdot\gamma(s)
~~\Longleftrightarrow~~
a_n=\sum_{d\;|\;n} b_d c_{n/d},
\]
o\`u la somme est \'etendue \`a tous les diviseurs $d$ de $n$, ce qui
est
not\'e $d~|~n$.

En d\'eduire la {\em formule d'inversion de Moebius\/}:
pour deux suite $f_n,g_n$ quelconques, on a l'\'equivalence
\begin{equation}\label{moebius}
f_n=\sum_{d\;|\;n}g_d
~~\Longleftrightarrow~~
g_n=\sum_{d\;|\;n} \mu(d)g_{n/d}.
\end{equation}

Inverser la relation entre s\'eries g\'en\'eratrices ordinaires:
\[
f(z)=\sum_{k\ge1} g(z^k),
\]
en exprimant $g(z)$ en fonction  de $f(z)$. On suppose $g$ sans terme constant:
$g(0)=0$.


{\bf Q5.} [Facultatif] Soit $\Omega=\{\omega_n(z)\}$ un syst\`eme de fonctions.
Les cas
\[
\Omega_{OGF}=\{z^n\}_{n=0}^\infty,~~
\Omega_{EGF}=\{\frac{z^n}{n!}\}_{n=0}^\infty,~~
\Omega_{DGF}=\{n^{-z}\}_{n=1}^\infty
\]
donnent lieu  aux s\'eries ordinaires, exponentielles, et de Dirichlet.
On definit la fonction $\zeta$ et les coefficients de Moebius par
\[\zeta_\Omega(z):=\sum_n 1\cdot \omega_n(z),~~
\frac{1}{\zeta_\Omega(z)}:=\sum_n \mu_\Omega(n)\omega_n(z).
\]
Remplir une matrice $4\times 3$ dont les colonnes correspondent \`a
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\'eries,
(iv) la relation d'inversion de type Moebius.

Pouvez-vous interpr\'eter
\[
[z^n]\frac{1}{2-\frac{1}{1-z}},
~~~
[z^n]\frac{1}{2-e^z},~~~
[n^{-z}] \frac{1}{2-\zeta(z)},
\]
o\`u l'on utilise la g\'en\'eralisation naturelle de la fonction coefficient
$[\,\cdot\,]$?
(Une telle th\'eorie transverse a \'et\'e d\'evelopp\'ee par Rota.)


\begin{center}
\sc Partie II. Polyn{\^o}mes
\end{center}

{\em Cette partie du probl\`eme 
montre que des objets alg\'ebriques
peuvent se traitent par les m\'ethodes
de la combinatoire \'enum\'erative. Les d\'eveloppements qui suivent sont \`a la base de
l'analyse d'algorithmes probabilistes en calcul formel et en 
th\'eorie des codes.}

{\bf Rappel.}
Pour un nombre premier $p$, on consid\`ere le corps  $F=F_p$ form\'e par les
entiers pris modulo~$p$. On travaille dans  l'anneau $F[x]$ des polyn\^omes
\`a 
coefficients  dans $F$. On rappelle que, dans cet anneau, il existe 
une division euclidienne et une propri\'et\'e de factorisation unique.
Les \'elements de $F[x]$ qui sont ind\'ecomposables (l'\'equivalent
des nombres premiers) sont appel\'es polyn{\^o}mes irreductibles:
$f$ est irr\'eductible si $f=g\cdot h$ implique $g=1$ ou $h=1$.

Fixons $p$.
On d\'esigne par ${\cal P}$ la classe des polyn\^omes unitaires
(dont le coefficient de t\^ete vaut 1) et par ${\cal I}$ la
sous-classe des polyn\^omes unitaires et irr\'eductibles. Par
convention, la taille (au sens combinatoire) d'un polyn{\^o}me est son
degr\'e (au sens alg\'ebrique). La sous-classe ${\cal Q}\subset {\cal P}$ repr\'esente 
les polyn\^omes unitaires ``sans carr\'es'', c-\`a-d, non divisibles
par un carr\'e:
$f$ est sans carr\'e si $f=g\cdot h^2$ implique $h=1$.


{\bf Q1.}
Montrer que la s\'erie g\'en\'eratrice de $\cal P$ vaut
\[
P(z)=\frac{1}{1-pz}.
\]

Observer que tout $f(x)\in F[x]$ s'\'ecrit $f(x)=g(x)\cdot h(x)^2$
o\`u $g$ est sans carr\'e et $h$ quelconque. D'autre part,
sii ${\cal H}$ est une classe de polyn\^omes de s\'erie g\'en\'eratrice
$H(z)$, la s\'erie g\'en\'eratrice de l'ensemble
$\{h(x)^2~/~h(x)\in{\cal H}\}$ vaut $H(z^2)$.
En d\'eduire la s\'erie g\'en\'eratrice de $\cal Q$.
Calculer la probabilit\'e qu'un polyn\^ome pris uniform\'ement 
dans ${\cal P}_n$
soit sans carr\'e.

{\bf Q2.} Montrer que
\[
\begin{array}{lll}
P(z)&=&\ds \prod_{n=1}^\infty (1-z^n)^{-I_n}\\
&=&\ds \exp\left(\sum_{k=1}^\infty \frac1k I(z^k)\right).
\end{array}
\]
Exprimer la relation correspondante  entre $zP'(z)/P(z)$ et $J(z)=zI'(z)$.
En d\'eduire la relation
\[
I_n =\frac{1}{n}\sum_{d~|~n}\mu(d)p^{n/d},
\]
o\`u $\mu$ est le coefficient de Moebius.

{\bf Q3.}
Montrer bri\`evement que 
\[
I_n =\frac{p^n}{n}(1+o(1)).
\]
Comment se compare la situation des polyn\^omes sur un corps fini \`a celle des entiers?

On suppose qu'on dispose de deux proc\'edures:
{\tt draw(n)} tire au hasard un \'el\'ement de ${\cal P}_n$
et {\tt irred(f)} r\'epond vrai ou faux selon que $f$ est irr\'eductible ou non.

Combien d'essais en moyenne effectue l'algorithme de tirage d'un
polyn\^ome irr\'eductible suivant?
\begin{verbatim}
     repeat
         f := draw(n);
     until irred(f);
\end{verbatim}
Quelle est la variance du nombre de tirages?

{\bf Q4.}
Soit $\omega(f)$ le nombre de facteurs irr\'eductibles de 
$f$ compt\'es avec multiplicit\'e, par exemple,
\[
\omega\left((1+x)(3+x+x^3)^5(4+x^7)^2(2+2x+x^9)\right)=1+5+2+1=9.
\]
Soit $P_{n,k}$ le nombre de $f\in{\cal P}_n$ tels que $\omega(f)=k$
et $P(z,u):=\sum_{n,k}P_{n,k}u^kz^n$.
Montrer que
\[
\begin{array}{lll}
P(z,u)&=&\ds \prod_{n=1}^\infty (1-uz^n)^{-I_n}\\
&=&\ds \exp\left(\sum_{k=1}^\infty \frac{u^k}{k} I( z^k)\right).
\end{array}
\]

Montrer que l'esp\'erance de $\omega$ prise sur l'ensemble des
polyn\^omes ${\cal P}_n$ vaut exactement
\[
M_n=\hbox{coeff} [z^n]\, \left(\frac{\partial}{\partial u}P\left(\frac
zp ,u\right)\right)_{u=1}. 
\]
D\'eterminer un \'equivalent asymptotique de
\[
[z^n] \left(I(\frac{z}{p})+I(\frac{z^2}{p^2})+I(\frac{z^3}{p^3})+\cdots\right)
\]
et en d\'eduire que
\[
M_n=\log n (1+o(1)).
\]
(Se limiter aux grandes \'etapes de la d\'emonstration.)

[Facultatif] Qu'est-ce que ce r\'esultat sugg\`ere 
quant au nombre moyen de facteurs premiers d'un entier $\le x$?

{\bf Q5.} [Facultatif] Montrer que le nombre d'\'el\'ements de ${\cal P}_n$
qui ont $n_1$ facteurs irr\'eductibles de degr\'e $1$, $n_2$ de
degr\'e~2, etc,  vaut (en marquant la d\'ependance en~$p$):
\[
G(n_1,n_2,\ldots;p)=\prod_{j=1}^n {I_{n_j}+n_j-1\choose n_j}.
\]
Les $I_n$ sont bien s\^ur ceux qui sont relatifs \`a 
la caract\'eristique $p$ du corps:
$I_n=I_n(p)$.
Calculer pour $n$ {\em fix\'e\/}
et $p\to+\infty$
la limite
\[
g(n_1,n_2,\ldots)=\lim_{p\to+\infty}
\frac{G(n_1,n_2,\ldots;p)}{p^n}.
\]

Montrer que $g(n_1,n_2,\ldots)$ 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\'esum\'e la d\'ecomposition en facteurs irr\'eductibles d'un polyn\^ome 
de degre fix\'e~$n$ sur un corps de grande cardinalit\'e ressemble \`a
la d\'ecomposition en cycles d'une permutation de la m\^eme taille~$n$.





\clearpage

\begin{center}
\sc Partie III. Explorations de calcul formel
\end{center}

Il s'agit l\`a d'un exercice \`a pr\'eparer en binome.
Le r\'esultat peut fort bien \^etre une feuille de travail {\sc Maple},
mais \'edit\'ee convenablement et bri\`evement
comment\'ee, ou bien un ``compte-rendu''
d'exp\'erience manuscrit.

{\em Le probl\`eme trait\'e ici est une simplification d'une situation qui
s'est pr\'esent\'ee r\'eellement il y a quelques ann\'ees. Les
statisticiens construisent des arbres de classification  appel\'es
{\em hi\'erarchies\/}.
Le probl\`eme consiste \`a analyser les propri\'et\'es des
hi\'erarchies al\'eatoires sur la base du principe qu'une
classification produite dans le monde r\'eel (par ex. par un programme
d'analyse statistique) a d'autant plus de ``chances'' d'\^etre
significative qu'elle s'\'ecarte des lois du hasard.
D'o\`u l'int\'er\^et de quantifier l'al\'ea!}

Les hi\'erarchies  sont des arbres dont les sommets externes sont les
$n$ objets \`a 
classifier (la taille vaut alors $n$) et dont les sommets internes 
(repr\'esentant les ``classes'') ont
degr\'e tous $\ge2$, car il faut que la classification soit non triviale.
Par exemple:
\begin{small}
\begin{verbatim}
     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
\end{verbatim}
\end{small}
Les hi\'erarchies sont donc ``non-planaires'' (pas de distinction
gauche/droite) et enracin\'ees,
de par l'origine du probl\`eme. Les objets \`a classifier sont
assimil\'es aux \'etiquettes $1,\ldots,n$.
En d'autres termes:
\begin{quote}\sl
La classe ${\cal H}$ des hi\'erarchies est la classe des arbres enracin\'es
non-planaires, \'etiquet\'es aux
sommets externes seulement (qui d\'eterminent la taille)
et dont les sommets internes ont tous degr\'es $\ge2$.
\end{quote}
Symboliquement:
\[
{\cal H}={\cal Z}+{\tt Set}({\cal H}, \hbox{card}\ge2).\]


\bigskip

{\bf III.1 D\'enombrement asymptotique des hi\'erarchies}


{\bf Q1.} On commence par se convaincre que la s\'erie g\'en\'eratrice
exponentielle des hierarchies v\'erifie l'\'equation
\[
H(z)=z+\left(e^{H(z)}-1-H(z)\right).
\]
Maple sait trouver pour nous une solution au moyen de la fonction
``sp\'eciale'' {\tt LambertW} $(W$) qui est la solution de 
\[
z=We^W.
\]
d\'efinie et positive pour $z\in[0,e^{-1}]$.
(En terme de la fonction d'arbre du cours, $T(z)$ , on a
$W(z)=-T(-z)$;
essayer {\tt series(LambertW(z),z=0,10);})

\begin{verbatim}
     eqH:=H=z+exp(H)-1-H; Hz:=solve(eqH,H);
\end{verbatim}

Calculer les 30 premiers coefficients
\begin{verbatim}
     Hs:=series(Hz,z=0,31);
     for i from 0 to 30 do 
         c[i]:=coeff(Hs,z,i)*1.0 od;
\end{verbatim}
et deviner une loi tr\`es approximative de croissance de
\[
c_i=[z^i]\, H(z).
\]
On pourra s'aider de
\begin{verbatim}
     plot([seq([i,c[i+1]/c[i]],i=5..30)],0..30,0..3);
\end{verbatim}
Le nombre de hi\'erarchies de taille $n$ vaut $H_n=n!c_n$.


{\bf Q2.} On sait que le rayon de convergence d'une s\'erie enti\`ere 
\`a coefficients positifs est \'egal \`a la distance entre l'origine 
et la singularit\'e positive la plus proche. Ici, la singularit\'e
correspond \`a une pente verticale (de d\'eriv\'ee infinie),
comme on peut s'en convaincre par un {\tt plot}.
\begin{verbatim}
     plot(Hz,z=0..0.5); plot(diff(Hz,z),z=0..0.5);
     H1z:=normal(diff(Hz,z));
\end{verbatim}
Par une suite de trac\'es de ce type, on devra obtenir une
approximation \`a 0.001 pr\`es de la singularit\'e positive,
\[\rho=???\pm0.001.\]

Combien de chiffres environ comporte la repr\'esentation d\'ecimale de
$H_{1000}$?

{\bf Q3.} On se propose de d\'eterminer maintenant exactement la
singularit\'e positive $\rho$. En supposant qu'elle provient de
l'annulation du denominateur de $\frac{d}{dz}H(z)$,
on d\'eterminera alors sa valeur exacte (utliser {\tt solve}):
\[
\rho=???
\]

On peut alors tenter de comprendre de quelle mani\`ere $H(z)$ devient
singuli\`ere lorsque $z$ tend vers $\rho$ par valeurs inf\'erieures.
Il est commode de poser $z=\rho-h$ et faire $h\to0^+$,
ce qui s'obtient par un d\'eveloppement en s\'erie.
\begin{verbatim}
    map(simplify,series(subs(z=rho-h,Hz),h=0));
\end{verbatim}

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 \sim [z^n]\left(c_0-c_1\sqrt{\rho-z}\right).
\]
En d'autres termes, on suppose, et cela est justifi\'e par
l'analyse de singularit\'e que:{\em une bonne approximation de la
fonction donne une bonne approximation des coefficients}.
En d\'eduire une formule asymptotique pour $c_n$ de la forme
\[
c_n \sim K_1 K_2^n n^{K_3},~~~ K_1,K_2,K_3=???.
\]

V\'erifier comme suit:
\begin{verbatim}
     for i from 2 to 30 do
             evalf(coeff(Hs,z,i)/rho^(-i+1/2)*i^(3/2)*sqrt(Pi)) 
     od;
\end{verbatim}
Avec quelle pr\'ecision estimez-vous pouvoir pr\'evoir la valeur de 
$H_{1000}$?


{\bf III.2 Nombre d'\'etapes de classification.}
On s'int\'eresse au nombre de sommets internes de l'arbre
(le nombre de classes).
Soient $H_{n,k}$ le nombre de hi\'erarchies de taille $n$ ayant $k$
sommets internes et $n$ sommets externes.
On se convaincra (ou bien, on admettra) que
la s\'erie double
\[
H(z,u)=\sum_{n,k}H_{n,k}u^k\frac{z^n}{n!}
\]
v\'erifie l'equation
\[
H(z,u)=z+u\left(e^{H(z,u)}-1-H(z,u)\right).
\]

{\bf Q4.} R\'esoudre cette \'equation en termes de la fonction 
$W$ de Lambert. 
On pose
\[
G(z):=\left(\frac{\partial}{\partial u}F(z,u)\right)_{u=1}
\]
Exprimer de m\^eme $G(z)$ (la d\'erivation s'obtient par {\tt diff}).

Soit $d_n:=[z^n]G(z)$, de sorte que le nombre moyen de
sommets internes dans une hi\'erarchie de taille $n$ vaut
\[
\mu_n=\frac{d_n}{c_n}.
\]
On tabulera $\mu_n$ pour $n=2\,.\,.\,30$.

Deviner une formule approximative d\'ecrivant la croissance
asymptotique de $\mu_n$. 

Chercher a am\'eliorer l'estimation, empiriquement (en devinant
simultan\'ement une valeur approch\'ee du terme d'erreur), et/ou
en \'evaluant
\[
\gamma:=\lim_{z\to\rho^-} \frac{G(z)}{z\frac{d}{dz}H(z)}.
\]

Estimer au mieux $\mu_{1000}$. 

Un programme de classification produit sur $n=1000$ donn\'ees une
hierarchie qui comprend 273 classes (sommets internes). La
hi\'erarchie ainsi constitu\'ee ressemble-t-elle \`a une hi\'erarchie
al\'eatoire? 
\begin{quote}
[\ ] OUI~~~~~[\ ] NON~~~~~[\ ] INCERTAIN
\end{quote}





\end{document}

