3
Développement - Dénombrement des polynômes irréductibles sur F q Préparation à l’agrégation - Jérôme Von Buhren - http://vonbuhren.free.fr Dénombrement des polynômes irréductibles sur F q 1. Le développement On fixe q = p m p N est un nombre premier m N * . Pour tout n N, on désigne par P q (n) l’ensemble des polynômes irréductibles de degré n dans l’anneau F q [X ] et on note I q (n) = Card(P q (n)). Lemme : Dans F q [X ], on a la décomposition X q n - X = d|n P Pq (d) P. Démonstration : 1) Soit P P q (d) où d | n. Le corps de rupture K = F q [X ]/(P ) de P est un corps de cardinal q d . On note x K la classe de X dans K qui est une racine de P . Comme x K, on a x q d = x, donc en écrivant n = kd avec k N * , on a par une récurrence immédiate x q n = x q kd = x q d q (k-1)d = x q (k-1)d = ··· = x q d = x. Ainsi, le polynôme X q n - X F q [X ] annule x K. Comme P est le polynôme minimal de x sur F q , on obtient P | X q n - X . 2) Réciproquement, soit P F q [X ] un facteur irréductible de X q n - X . Comme le polynôme X q n - X est scindé sur K = F q n , il existe une racine x K de P . On a alors n =[K : F q (x)] · [F q (x): F q ]=[K : F q (x)] · deg(P ), donc deg(P ) | n. 3) Comme X q n - X est scindé à racines simples sur F q n , sa décomposition en produit de polynômes irréductibles dans F q [X ] ne contient que des facteurs simples, ce qui permet de conclure. Théorème : On a I q (n) > 0 pour tout n N * et I q (n) q n n lorsque n +. Démonstration : 1) En appliquant le degré à la formule du lemme, on obtient q n = d|n dI q (d). En particulier, on a nI q (n) 6 q n pour tout n N. D’une part, on obtient nI q (n)= q n - d|n d=n dI q (d) > q n - n-1 d=0 q d = q n - q n - 1 q - 1 = q n (q - 2) + 1 q - 1 > 0. 2) D’autre part, en minorant plus finement, on obtient q n > nI q (n)= q n - d|n d=n dI q (d) > q n - n/2 d=0 q d = q n - q n/2+1 - 1 q - 1 . On en déduit que I q (n) q n /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 …vonbuhren.free.fr/Agregation/Developpements/dev_denombrement... · Développement-DénombrementdespolynômesirréductiblessurF q Préparationàl’agrégation-JérômeVonBuhren-

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