\documentclass{article}
\usepackage{titling}
\author{Laura \textsc{Gay}}
\include{preambule}

\newboxedtheorem{defi}{Définition}{}
\newboxedtheorem{prop}{Proposition}{compteur2}
\newboxedtheorem{lem}{Lemme}{}
\newboxedtheorem{coro}{Corollaire}{compteur3}
\newboxedtheorem{thm}{Théorème}{}
\newboxedtheorem{appli}{Application}{compteur5}


\renewenvironment{proof}[1][]{{\underline{\bfseries \proofname #1 :} }}{\hfill $\blacksquare$\\}

\begin{document}
\renewcommand{\proofname}{Preuve}

\begin{spacing}{2}
\setlength {\shadowsize }{2pt}
\begin{center} \shadowbox{\begin{minipage}{15cm}
\centering     \begin{huge} 
\textsc{Dénombrement des polynômes irréductibles sur $\mathbb{F}_q$}\end{huge}
\end{minipage}} \end{center}\end{spacing}
~\\

\underline{Référence :} \textsc{Francinou-Gianella} : Exercices de mathématiques pour l'agrégation, p. 189\\

%\begin{multicols}{2}
\begin{thm}
Soit $n\in\mathbb{N}^*$. \\
Notons $A(n,q)$ l'ensemble des polynômes irréductibles unitaires de degré $n$ de $\mathbb{F}_q[X]$ et $I(n,q)=\text{Card}A(n,q)$.\\
Alors:
\begin{enumerate}
\item  $\displaystyle X^{q^n}-X=\prod_{d\mid n} \prod_{P\in A(d,q)} {P}$
\item Si $\mu$ est la fonction de Möbius, $I(n,q)=\frac{1}{n}\sum\limits_{d\mid n}{\mu\left(\frac{n}{d}\right)q^d}$
\item $\displaystyle I(n,q)\underset{n\rightarrow +\infty}{\sim} \frac{q^n}{n}$
\end{enumerate}
\end{thm}
~\\
\begin{proof}
\begin{enumerate}
\item Soient $d$ un diviseur de $n$ (on note $dr=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}$ (unicité des corps finis). Or, par construction, $\mathbb{F}_{q^d}$ est le corps de décomposition de $\displaystyle X^{q^d}-X$ ie l'ensemble des racines de $\displaystyle X^{q^d}-X$. En particulier\footnote{on peut également dire que $x$ non nul. $\mathbb{F}_q(x)*$ de cardinal $q-1$ et on utilise Lagrange. }, $x^{q^d}=x$. Ainsi,
\[ 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$ \footnote{Il s'agit ici de voir que $P$ n'a que des racines simples. En effet, supposons par l'absurde que $x$ soit une racine double de $P$ dans une extension $L$ de $K$. Alors $x$ est une racine de $P'$. Si on fait l'algorithme d'Euclide dans $L$ et dans $K$ par unicité de la division euclidienne c'est le même truc à chaque étape donc $\text{pgcd}_L(P,P')=\text{pgcd}_K(P,P')$. Comme $P$ est irréductible dans $K=\F_q$, $\text{pgcd}_K(P,P')=P$ ou $1$ donc $\text{pgcd}_K(P,P')=P$ car ils ont une racine commune donc ce n'est pas 1. Donc $\text{pgcd}_K(P,P')=P$ pbm de degré sauf si $P'=0$ ie $P=Q(X^p)=\sum_{i=1}^n q_i X^{ip}=\sum_{i=1}^n \tilde{q}_i^p X^{ip}=\left ( \sum_{i=1}^n \tilde{q}_i X^{i} \right)^p$. (on a utilisé la surjectivité du Frobenius au 3ième =) absurde car $P$ irréductible.} Donc $\prod_{d\mid n} \prod_{P\in A(d,q)} {P} \mid X^{q^n}-X$ par irréductibilité.\\
~\\
Réciproquement, soit $P \in \F_{q}[X]$ un polynôme irréductible divisant $\displaystyle X^{q^n}-X$. $\displaystyle X^{q^n}-X$ est scindé sur $\F_{q^n}$. Soit $x$ une racine de $P$ dans $\F_{q^n}$ donc $L:=\F_{q}(x)$ est un corps de rupture de $P$ ie $L$ est un corps intermédiaire entre $\mathbb{F}_q$ et $\mathbb{F}_{q^n}$ donc. On a $$n=[\F_{q^n}: \F_q]=[\F_{q^n}:L][L:\mathbb{F}_q]=\mbox{deg}(P)[\F_{q^n}:L]$$ 
Donc $\mbox{deg}(P)\mid n$.\\

Les racines de $X^{q^n}-X$ dans $\F_{q^n}$ sont simples. Donc tous les facteurs irréductibles de $X^{q^n}-X$ dans $\F_q[X]$ interviennent avec une multiplicité égale à 1. Il vient donc finalement: 
$$\displaystyle X^{q^n}-X=\prod_{d\mid n} \prod_{P\in A(d,q)} {P}$$

\item En prenant les degrés dans l'égalité 1., on obtient $q^n=\sum\limits_{d\mid n}{dI(d,q)}$. \\
En appliquant le formule d'inversion de Möbius (\textbf{Lemme}) à $n \mapsto nI(n,q)$ et en disisant par $n$, on obtient \[ I(n,q)=\frac{1}{n}\sum\limits_{d\mid n}{q^d\mu\left(\frac{n}{d}\right)}\]

\item On a de plus $I(n,q)=\frac{1}{n}\left(q^n+\underbrace{\sum\limits_{\substack{d\mid n \\ d<n}}{q^d\mu\left(\frac{n}{d}\right)}}_{:=r_n}\right) $.\\
On a 
$$|r_n|\leq \sum\limits_{d=1}^{ [\frac{n}{2}]} {q^d}=q \frac{q^{[\frac{n}{2}]}-1}{q-1}\leq \underbrace{\frac{q^{[ \frac{n}{2} ]+1} }{q-1} }_{\text{négligeable devant }q^n}$$
Ainsi $\displaystyle I(n,q)\underset{n\rightarrow +\infty}{\sim} \frac{q^n}{n}$.\\
\item Bonus: Pour tout $n \geq 1$, $|r_n|\leq \frac{q^{[ \frac{n}{2} ]+1} }{q/2} \leq 2q^{[\frac{n}{2}]}<q^n$ donc\footnote{car au pire $r_n=-q^n+1$ donc $I(n,q)=\frac{1}{n}>0$ (heuristiquement mais c'est impossible car $I(n,q)$ est entier)} $I(n,q)>0$ pour tout $n\in\mathbb{N}^*$.
\end{enumerate}

\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} \
[FG p.93]
\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}$ sa décomposition en facteurs premiers. \[ \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 \\ 
 &= & \sum_{k=0}^r \binom{r}{k}(-1)^k \\ &= &(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}

\vspace{2cm}

\hrulefill \\
~\\
\underline{Notes:}\\
~\\
\checkmark ~\textbf{A l'oral}, 10' sans Mobius. 14' avec 2 et 3 de Mobius. Allure normale.\\
\checkmark ~Rappel: Corps de rupture = 1 racine.\\
\checkmark ~Quand on cherche Card$\{(i_1,\dots,i_k)\in \llbracket 1,r \rrbracket ~/~i_1<\dots<i_k\}$, on a $r$ possibilités pour $i_k$, $r-1$ possibilités pour $i_{k-1}$, etc $r-k$ possibilités pour $i_1$, ceci étant à permutations près on divise par $k!$ ie $\frac{r(r-1)\dots(r-k)}{k!}=\binom{k}{r}$.\\
\checkmark ~Dès 1748, la fonction $\mu$ apparaît de manière explicite dans les travaux d'Euler. Mais c'est Möbius qui en 1832 en étudia les propriétés de manière systématique.\\
%\end{multicols}

\end{document}