summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorFabrice (eramangarria) <Fabrice.Orgogozo+git@gmail.com>2015-07-29 21:16:06 (GMT)
committerFabrice Orgogozo <Fabrice.Orgogozo+git@gmail.com>2015-07-29 21:16:06 (GMT)
commitb0c076b7532cf82775c4747b8b5bdc5a2eae86a6 (patch)
tree7d46dec7941a16f370e45fa37af815a870760afd
parentc9051ce822a800c117fdc5ad00a5aaaea686cb15 (diff)
downloadgalois-b0c076b7532cf82775c4747b8b5bdc5a2eae86a6.zip
galois-b0c076b7532cf82775c4747b8b5bdc5a2eae86a6.tar.gz
galois-b0c076b7532cf82775c4747b8b5bdc5a2eae86a6.tar.bz2
[CF] démonstration de la jolie proposition (et d'une autre)
-rw-r--r--chapitres/corps-finis.tex96
1 files changed, 93 insertions, 3 deletions
diff --git a/chapitres/corps-finis.tex b/chapitres/corps-finis.tex
index 889157d..ae52d28 100644
--- a/chapitres/corps-finis.tex
+++ b/chapitres/corps-finis.tex
@@ -677,12 +677,102 @@ La conclusion résulte alors des inégalités
$\frac{p-2}{p-1} ≥ ½$ et $1-\frac{2}{p} ≥ ⅓$.
\end{démo}
+\subsubsection{Fonction zêta $ζ$}Pour tout polynôme unitaire $f ∈ 𝔽_p[T]$, notons $|f|$ l'entier
+$p^{\deg(f)}$ ; en particulier, $|1|=1$. Pour chaque $s ∈ ℂ$ de partie réelle $>1$, considérons la série
+(de Dirichlet)
+\[
+ζ(s) ≔ ∑_{f \text{ unitaire}} \frac{1}{|f|^s},
+\]
+analogue à la fonction zêta usuelle de Riemann $\displaystyle ζ_{ℤ}(s) ≔ ∑_{n ≥ 1} \frac{1}{n^s} = ∏_{p} \frac{1}{1-p^{-s}}$.
+Ici aussi, l'existence et l'unicité de la décomposition en produit d'irréductibles entraîne formellement l'égalité
+(« produit eulérien ») $ζ(s) = ∏_{P \text{ irr. unit.}} \frac{1}{1-|P|^{-s}}$.
+En effet, le terme de droite est égal à $∏_{P} \big(∑_{n ≥ 1} |P|^{-ns}\big)=∑_f |f|^{-s}$ :
+si $f=P₁^{n₁} ⋯ P_r^{n_r}$, on a $|f|^{-s}=|P₁|^{-n₁s} ⋯ |P_r|^{-n_rs}$.
+Par contre, à la différence du cas de l'anneau $ℤ$, la fonction zêta de $𝔽_p[T]$
+est facile à calculer : $ζ(s)=\displaystyle ∑_{d ≥ 0} \frac{p^d}{p^{ds}}=\frac{1}{1-p⋅p^{-s}}$ car il
+y a exactement $p^d$ polynômes unitaires de degré $d$.
+
+\subsubsection{Fonction Zêta $Z$}Il est parfois plus commode de faire le changement de variable $x=p^{-s}$, c'est-à-dire considérer la série (formelle/entière)
+\[
+Z(x) ≔ ∏_P \frac{1}{1-x^{\deg(P)}}= ∏_{d ≥ 1} \frac{1}{(1-x^d)^{I_d}},
+\]
+où $P$ parcourt les polynômes irréductibles unitaires de $𝔽_p[T]$ et
+$I_d$ désigne le nombre d'entre eux de degré $d$.
+Par construction, on a $ζ(s)=Z(p^{-s})$ et, d'après le calcul du paragraphe précédent,
+on a $\displaystyle Z(x)=\frac{1}{1-px}$.
+Notons qu'en prenant la dérivée logarithmique de l'égalité $\displaystyle ∏_{d ≥ 1} \frac{1}{(1-x^d)^{I_d}}=\frac{1}{1-px}$,
+on retrouve les égalités $∑_{a|d} aI_a=p^d$.
+
+\subsubsection{Polynômes sans facteur carré}
+Soit $ζ_{⧄}$ l'analogue de $ζ$ pour les polynômes unitaires
+\emph{sans facteur carré} : $ζ_{⧄}(s)=∑_{f} |f|^{-s}$ où $f$ parcourt les polynômes unitaires
+sans facteur carré. On a trivialement $ζ_{⧄}(s)=∏_P (1+|P|^{-s})$,
+où $P$ parcourt les polynômes unitaires irréductibles.
+De l'identité $\displaystyle 1+z=\frac{1-z²}{1-z}$ appliquée aux $z=|P|^{-s}$, on tire l'égalité
+\[
+ζ_{⧄}(s)=\frac{ζ(s)}{ζ(2s)}.
+\]
+On peut réécrire cette formule en faisant le changement de variable précédent :
+\[
+Z_{⧄}(x)=\frac{Z(x)}{Z(x²)}=\frac{1-px²}{1-px}.
+\]
+Comme $Z_{⧄}(x)=∑_d I^{⧄}_d  x^d$, où $I^{⧄}_d$ est le nombre de polynômes unitaires
+de degré $d$ sans facteur carré, on a $I^{⧄}_d=p^d-p^{d-1}=p^d(1-p^{-1})$
+pour chaque $d ≥ 2$. On a donc démontré la proposition suivante.
+
+\begin{proposition2}
+La proportion de polynômes $f ∈ 𝔽_p[T]$ unitaires de degré $d ≥ 2$ sans facteur carré est $\displaystyle 1-p^{-1}=\frac{1}{ζ(2)}$.
+\end{proposition2}
+
+(Il n'est pas difficile de montrer directement qu'à $d$ fixé le nombre de tels polynômes est $1-𝗈(1)$ lorsque $p → + ∞$,
+cf. p. ex. \cite[lemme 4]{cycles-of-a-random-permutation//Tao}.)
+
+\subsubsection{Nombre moyen de facteurs irréductibles}
+Pour tout polynôme unitaire $f ∈ 𝔽_p[T]$, notons $λ(f)$ le nombre de ses facteurs irréductibles
+(comptés avec multiplicités, avec la convention que $λ(1)=0$) et considérons la série formelle de deux
+variables
+\[
+Z(x,u) ≔ ∏_{d ≥ 1} (1-ux^d)^{-I_d} = ∑_f x^{\deg(f)} u^{λ(f)}
+\]
+qui encode les nombres de polynômes unitaires $f$ de degré et nombre de facteurs irréductibles donnés.
+Elle raffine la fonction Zêta précédente : $Z(x,1)=Z(x)$.
+Sa dérivée logarithmique par rapport à la nouvelle variable $u$
+est égale à $\displaystyle ∑_{d ≥ 1} \frac{I_d x^d}{1-ux^d}=∑_{d ≥ 1,k ≥ 0} I_d x^{d(k+1)} u^k$
+si bien que l'on a l'égalité
+\[
+Z(x,u)= \exp\big(∑_{k ≥ 1} u^k \frac{I(x^k)}{k}\big)\text{ où }I(x) ≔ ∑_{d ≥ 1} I_d x^d.
+\]
+Pour chaque entier $d ≥ 1$, notons $𝕖_d$ le nombre moyen de facteurs irréductibles
+d'un polynôme unitaire de degré $d$.
+Par construction et le calcul précédent, on a
+\[
+∑_{d ≥ 1} 𝕖_d x^d = \frac{\mathrm{d}Z}{\mathrm{d}u}(x/p,u)_{|u=1} = Z(x/p)× ∑_{k ≥ 1} I(x^k/p^k).
+\]
+Or, il résulte de la formule d'inversion de Möbius que l'on a
+\[
+I(x) = -∑_{m ≥ 1} \frac{μ(m)}{m}\log(1-px^m)
+\]
+d'où, en utilisant $∑_{m|d} φ(m)=d$ et à nouveau la formule d'inversion,
+\[
+∑_{k ≥ 1} I(x^k)= - ∑_{d ≥ 1} \frac{φ(d)}{d}\log(1-px^d).
+\]
+Finalement, $\displaystyle ∑_{d ≥ 1} 𝕖_d x^d = \frac{1}{1-x}∑_{d ≥ 1} \frac{φ(d)}{d}\log(\frac{1}{1-p^{1-d}x^d})$.
+En développant le logarithme, on en déduit que
+\[
+𝕖_d=\big(1+\frac{1}{2}+\frac{1}{3}+ ⋯ +\frac{1}{d}\big) + ∑_{r=1}^d \frac{1}{r p^r} \big(∑_{k ≥ 2 \atop k-1 ∣ r} φ(k) ⋅ (1-\frac{1}{k})\big).
+\]
+Le second terme est un $\displaystyle 𝖮(∑_{r=1}^d r p^{-r})=𝖮(p^{-1})$, uniformément en $d$.
+On a donc en particulier montré la proposition suivante.
\begin{proposition2}
-La proportion de polynômes (unitaires) de degré $d$ sans
-facteur carré est $1-q^{-1}$.
+Le nombre moyen de facteurs irréductibles
+d'un polynôme unitaire de degré $d$ de $𝔽_p[T]$
+est équivalent à $\log(d)$ lorsque $d → + ∞$ ($p$ fixé ou non).
\end{proposition2}
-\commentaire{Via la fonction zêta… Voir par exemple [Rosen]}
+Il en est du même du nombre moyen de cycles d'une
+permutation aléatoire de $𝔖_d$ lorsque $d → +∞$ ;
+ce n'est pas une coïncidence.
+% Préciser ce lien.
\subsection{Critères d'irréductibilité}