\documentclass[10pt]{article}

\usepackage[cp1252]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[a4paper]{geometry}
\usepackage{amsmath, amssymb}
\usepackage{dsfont}
\usepackage[frenchb]{babel}

\usepackage{graphicx}


\usepackage{amsthm}

\theoremstyle{plain}
\newtheorem*{thm}{Th\'eor\`eme}
\newtheorem*{lem}{Lemme}
\newtheorem*{prop}{Proposition}
\newtheorem*{cor}{Corollaire}

\theoremstyle{definition}
\newtheorem*{defi}{D\'efinition}
\newtheorem*{exe}{Exemple}

\theoremstyle{remark}
\newtheorem*{rmq}{Remarque}

\begin{document}
\pagestyle{empty}

\begin{center}
\Large Dénombrement des polynômes irréductibles sur $\mathbb{F}_q$
\end{center}

\medskip

Référence : \emph{Francinou-Gianella, Exercices de mathématiques pour l'agrégation, p189}

\medskip

\begin{thm}
Notons $A(n,q)$ l'ensemble des polynômes irréductibles de $\mathbb{F}_q[X]$ et $I(n,q)=A(n,q)$. Montrons que pour tout $n\in\mathbb{N}^*$ et tout $q$, $I(n,q)\geq 1$ et que $\displaystyle I(n,q)\underset{n\rightarrow +\infty}{\sim} \frac{q^n}{n}$.
\end{thm}
\begin{proof}
Montrons que $\displaystyle X^{q^n}-X=\prod\limits_{\substack{d\mid n \\ P\in A(d,q)}}{P}$.

Soient $d\mid n$ et $P\in A(d,q)$. Soit $x$ une racine de $P$ dans une clôture algébrique. $\mathbb{F}_q[x]$ est un corps de rupture de $P$ et $[\mathbb{F}_q[x]:\mathbb{F}_q]=\mbox{deg}(P)=d$. On a donc $\mathbb{F}_q[x]\cong\mathbb{F}_{q^d}$. Or, par construction, $\mathbb{F}_{q^d}$ est le corps de décomposition de $\displaystyle X^{q^d}-X$. En particulier, $x^{q^d}=x$. Ainsi, en notant $dr=n$, \[ x^{q^n}=\left(\underbrace{\left(\left(x^{q^d}\right)^{q^d}\right)^{q^d}\dots}_{\mbox{$r$ fois}}\right)^{q^d}=\left(\underbrace{\left(\left(x^{q^d}\right)^{q^d}\right)^{q^d}\dots}_{\mbox{$r-1$ fois}}\right)^{q^d}=\dots=x^{q^d}=x.\]
Donc $x$ est une racine de $\displaystyle X^{q^n}-X$. D'où $\displaystyle P\mid X^{q^n}-X$.

Réciproquement, soit $P$ un polynôme irréductible divisant $\displaystyle X^{q^n}-X$. Soit $L$ un corps de rupture de $P$. On a $[L:\mathbb{F}_q]=\mbox{deg}(P)$. Or $L$ est un corps intermédiaire entre $\mathbb{F}_q$ et $\mathbb{F}_{q^n}$ donc, par multiplicativité des degrés, $\mbox{deg}(P)\mid n$. On a donc le résultat escompté.

\medskip

En prenant les degrés dans l'égalité otenue, on obtient $q^n=\sum\limits_{d\mid n}{dI(d,q)}$. En appliquant le formule d'inversion de Möbius (démontrée ci-après), on obtient \[ I(n,q)=\frac{1}{n}\sum\limits_{d\mid n}{q^d\mu\left(\frac{n}{d}\right)}=\frac{1}{n}\left(q^n+\sum\limits_{\substack{d\mid n \\ d<n}}{q^d\mu\left(\frac{n}{d}\right)}\right)=\frac{1}{n}\left(q^n+r_n\right). \]

On a \[ |r_n|\leq \sum\limits_{d=1}^{ \lfloor \frac{n}{2} \rfloor}{q^d}=q\frac{q^{\lfloor \frac{n}{2} \rfloor}-1}{q-1}\leq q^{\lfloor \frac{n}{2} \rfloor+1} \] qui est négligeable devant $q^n$. Ainsi $\displaystyle I(n,q)\underset{n\rightarrow +\infty}{\sim} \frac{q^n}{n}$.

De plus, $|r_n|<q^n$ donc $I(n,q)>0$ pour tout $n\in\mathbb{N}^*$.

\end{proof}

\begin{defi}
La fonction $\mu$ de Möbius est définie par \[ \begin{array}{ccl} \mathbb{N}^* &\longrightarrow &\left\{-1,0,1\right\} \\ n &\longmapsto & \left\{ \begin{array}{cl} 1 &\mbox{si}\ n=1 \\ 0 &\mbox{si} \ n \ \mbox{a un facteur carré} \\ (-1)^r &\mbox{si} \ n=p_1\dots p_r \ (\mbox{premiers distincts}) \\ \end{array} \right. \end{array}. \]
\end{defi}

\begin{lem}
La fonction de Möbius vérifie :
\begin{enumerate}
\item $\mu$ est multiplicative : $\forall n,m\in\mathbb{N}^*, \mbox{pgcd}(n,m)=1, \ \mu(nm)=\mu(n)\mu(m)$;
\item $\displaystyle \sum\limits_{d\mid n}{\mu(d)}=\left\{ \begin{array}{cl} 1 &\mbox{si } n=1 \\ 0 & \mbox{sinon} \\ \end{array} \right. $;
\item la formule d'inversion : si $\displaystyle g(n)=\sum\limits_{d\mid n}{f(d)}$ alors $\displaystyle f(n)=\sum\limits_{d\mid n}{g(d)\mu\left(\frac{n}{d}\right)}=\sum\limits_{d\mid n}{g\left(\frac{n}{d}\right)\mu(d)}$.
\end{enumerate}
\end{lem}
\begin{proof} \

\begin{enumerate}
\item Si $n=1$ ou $m=1$, le résultat est évident car $\mu(1)=1$ par définition. 

Si $n$ ou $m$ a un facteur carré, $nm$ a un facteur carré. 

Enfin, comme pgcd($n$,$m$)=1, le dernier cas possible est $n=p_1\dots p_r$ et $m=q_1\dots q_s$ avec les $p_i$ et les $q_i$ des nombres premiers tous distincts. On a alors $\mu(nm)=\mu(p_1\dots p_rq_1\dots q_s)=(-1)^{r+s}=(-1)^r(-1)^s=\mu(p_1\dots p_r)\mu(q_1\dots q_s)=\mu(n)\mu(m)$.

\item Le cas $n=1$ est évident. 

Notons $n=p_1^{\alpha_1}\dots p_r^{\alpha_r}$. \[ \begin{array}{rcl} \displaystyle \sum\limits_{d\mid n}{\mu(d)} &= &\displaystyle \mu(1)+\sum\limits_{i=1}^r{\mu(p_i)}+\sum\limits_{i<j}{\mu(p_ip_j)}+\sum\limits_{i<j<k}{\mu(p_ip_jp_k)}+\dots+\mu(p_1\dots p_r)+0 \\ &= &\displaystyle 1+\sum\limits_{i=1}^r{(-1)}+\sum\limits_{i<j}{(-1)^2}+\sum\limits_{i<j<k}{(-1)^3}+\dots+(-1)^r \\ &= &\displaystyle 1-\binom{1}{r}+\binom{2}{r}-\binom{3}{r}+\dots+(-1)^r \\ &= &(1-1)^r \\ &= &0 \end{array}.\]

\item \[ \sum\limits_{d\mid n}{g\left(\frac{n}{d}\right)\mu(d)} = \sum\limits_{d\mid n}\sum\limits_{d'\mid\frac{n}{d}}{f(d')\mu(d)} = \sum\limits_{dd'\mid n}{f(d')\mu(d)}=\sum\limits_{d'\mid n}{f(d')\sum\limits_{d\mid\frac{n}{d'}}{\mu(d)}}=f(n) \] (on a utilisé le point 2 pour la dernière égalité). Par changement de variable, on a \[ \sum\limits_{d\mid n}{g\left(\frac{n}{d}\right)\mu(d)}=\sum\limits_{d\mid n}{\mu\left(\frac{n}{d}\right)g(d)}. \]

\end{enumerate}

\end{proof}




\end{document}