Upload
dinhkhanh
View
213
Download
0
Embed Size (px)
Citation preview
Développement - Dénombrement des polynômes irréductibles sur Fq Préparation à l’agrégation - Jérôme Von Buhren - http://vonbuhren.free.fr
Dénombrement des polynômes irréductibles sur Fq
1. Le développementOn fixe q = pm où p ∈ N est un nombre premier m ∈ N∗. Pour tout n ∈ N,on désigne par Pq(n) l’ensemble des polynômes irréductibles de degré n dansl’anneau Fq[X] et on note Iq(n) = Card(Pq(n)).
Lemme : Dans Fq[X], on a la décomposition
Xqn −X =∏d|n
∏P∈Pq(d)
P.
Démonstration :1) Soit P ∈ Pq(d) où d | n. Le corps de rupture K = Fq[X]/(P ) de P est uncorps de cardinal qd. On note x ∈ K la classe de X dans K qui est une racinede P . Comme x ∈ K, on a xqd = x, donc en écrivant n = kd avec k ∈ N∗, on apar une récurrence immédiate
xqn = xq
kd =(xq
d)q(k−1)d
= xq(k−1)d = · · · = xq
d = x.
Ainsi, le polynôme Xqn −X ∈ Fq[X] annule x ∈ K. Comme P est le polynômeminimal de x sur Fq, on obtient P | Xqn −X.2) Réciproquement, soit P ∈ Fq[X] un facteur irréductible de Xqn−X. Commele polynôme Xqn −X est scindé sur K = Fqn , il existe une racine x ∈ K de P .On a alors
n = [K : Fq(x)] · [Fq(x) : Fq] = [K : Fq(x)] · deg(P ),
donc deg(P ) | n.3) Comme Xqn − X est scindé à racines simples sur Fqn , sa décompositionen produit de polynômes irréductibles dans Fq[X] ne contient que des facteurssimples, ce qui permet de conclure.
Théorème : On a Iq(n) > 0 pour tout n ∈ N∗ et Iq(n) ∼ qn
nlorsque n→ +∞.
Démonstration :1) En appliquant le degré à la formule du lemme, on obtient
qn =∑d|n
dIq(d).
En particulier, on a nIq(n) 6 qn pour tout n ∈ N. D’une part, on obtient
nIq(n) = qn −∑d|nd 6=n
dIq(d) > qn −n−1∑d=0
qd = qn − qn − 1q − 1 = qn(q − 2) + 1
q − 1 > 0.
2) D’autre part, en minorant plus finement, on obtient
qn > nIq(n) = qn −∑d|nd6=n
dIq(d) > qn −bn/2c∑d=0
qd = qn − qbn/2c+1 − 1q − 1 .
On en déduit que Iq(n) ∼ qn/n lorsque n→ +∞.
Références : • Chapitre 2, Partie 6, Sujet d’étude 1 de [Gou09].
1/3
Développement - Dénombrement des polynômes irréductibles sur Fq Préparation à l’agrégation - Jérôme Von Buhren - http://vonbuhren.free.fr
2. Remarques sur le développement
2.1. Inclusion de corps finis
On aurait pu utiliser le résultat suivant dans la démonstration du lemme.
Proposition : Soit (d, n) ∈ N∗ ×N∗. Le corps Fqd est un sous-corps de Fqn siet seulement si d | n.
Démonstration :1) Si Fqd est un sous-corps de Fqn , alors on a
n = [Fqn : Fq] = [Fqn : Fqd ] · [Fqd : Fq] = [Fqn : Fqd ] · d,
donc d | n.2) Réciproquement, si d | n, il est classique que Xqd −X divise Xqn −X. Onen déduit que K = {x ∈ Fqn | xqd = x} est un sous-corps de Fqn qui est decardinal Fqd .
2.2. Théorème de l’élément primitif pour les corps finis
Une conséquence du théorème du développement est la suivante.
Théorème de l’élément primitif pour les corps finis : Soit n ∈ N∗. Ilexiste un élément x ∈ Fqn tel que Fqn = Fq(x).
Démonstration :1) Si P ∈ Iq(n), alors on a Fqn ' Fq(X)/(P ) = Fq(x) où x ∈ K désigne laclasse de X dans K, d’où le résultat.2) Voici une seconde démonstration n’utilisant pas notre résultat. Comme legroupe F×qn est cyclique, il existe x ∈ F×qn tel que F×qn = {1, x, . . . , xq−2}. Enparticulier, on a Fqn = Fq(x).
3. Comment déterminer Pq(n) ?Si les valeurs de q et n sont petites, on peut utiliser la méthode du crible. Parexemple, pour q = 2, on a
I2(1) = {X,X+1}, I2(2) = {X2+X+1}, I2(3) = {X3+X+1, X3+X2+1}.
Si les valeurs de q ou de n sont grandes, on peut implémenter l’algorithme deBerlekamp (voir [BMP05, Partie 5.3.2]) pour factoriser le polynôme Xqn −Xavec un ordinateur.
4. Expression avec la fonction de MöbiusOn a une expression explicite de Iq(n) en utilisant la fonction de Möbius. Onnote P l’ensemble des nombres premiers et on rappelle que la fonction deMöbius µ : N∗ → {−1, 0, 1} est définie par
µ(n) ={
0 si n est divisible par le carré d’un nombre premier,(−1)r si n = p1 · · · pr où p1, . . . , pr ∈P sont distincts.
On a alors le résultat suivant.
Formule d’inversion de Möbius : Soit f : N∗ → A où A un groupe abéliennoté additivement. Si g : N∗ → A est la fonction définie par
∀n ∈ N∗, g(n) =∑d|n
f(d),
alors on a∀n ∈ N∗, f(n) =
∑d|n
µ
(n
d
)g(d).
Démonstration :Voir [Per96, Chapitre III, Exercice 2.7].
2/3
Développement - Dénombrement des polynômes irréductibles sur Fq Préparation à l’agrégation - Jérôme Von Buhren - http://vonbuhren.free.fr
On en déduit une expression de Iq(n) avec la fonction de Möbius.
Proposition : Pour tout n ∈ N∗, on a
Iq(n) = 1n
∑d|n
µ
(n
d
)qd.
Démonstration :Il suffit d’appliquer la formule d’inversion de Möbius à la fonction f : N∗ → Zdéfinie par f(n) = nIq(n). Dans la démonstration du développement, on amontré que la fonction g : N∗ → Z est définie par g(n) = qn, d’où le résultat.
Pour terminer, citons deux autres formules utilisant la fonction de Möbius.
Proposition : Pour tout n ∈ N∗, on a
ϕ(n) =∑d|n
µ
(n
d
)d et Φn(X) =
∏d|n
(Xd − 1)µ(nd ).
Démonstration :Il suffit d’appliquer la formule d’inversion de Möbius et d’utiliser les relationssuivantes.
∀n ∈ N∗, n =∑d|n
ϕ(d) et Xn − 1 =∏d|n
Φd(X).
Bibliographie[BMP05] V. Beck, J. Malick et G. Peyré – Objectif agrégation, 2e édition,
H&K, 2005.[Gou09] X. Gourdon – Algèbre, 2e édition, Ellipses, 2009.[Per96] D. Perrin – Cours d’algèbre, Ellipses, 1996.
3/3