Polynômes irréductibles

Homo Topi a écrit:

Pour un corps fini F, F[X] est un ensemble fini

Ahhh, mes yeux !! (:P)
Les $X^n$ sont distincts et en nombre infini sur tout corps (car on parle de polynômes formels et pas de fonctions polynômiales).

Si $F$ est un corp fini, $F[X]$ n'est pas fini.

Il y a des algorithmes plus efficaces que "tester tous les diviseurs". Voir https://fr.wikipedia.org/wiki/Algorithme_de_Cantor-Zassenhaus.

Pour $\mathbb Q$ je pense que c'est un problème essentiellement impossible. En tout cas il existe des polynômes irréductibles de tout degré.

Sur $\mathbb F_q$, il y a des polynômes irréductibles de tout degré aussi. On peut montrer que les polynômes unitaires irréductibles de degré $n$ sont exactement les facteurs irréductibles de $X^{q^n} - X$. On peut en déduire le théorème des nombres premiers dans ce contexte : le nombre de polynômes unitaires irréductibles de degré $\leq n$ est équivalent à $\frac{q^n}{n}$ quand $n$ tend vers l'infini (on peut même aller plus loin dans le développement car l'hypothèse de Riemann est démontrée dans ce contexte !).

Dans $\mathbb Z$ on compte les nombres premiers $\leq x$, dans $\mathbb F_q[T]$ on compte les polynômes irréductibles (unitaires) de degré $\leq n$. Je te fais un post un peu plus léché bientôt, je suis un peu pris là.

Oui, mais je n'aime pas trop cette dénomination : la preuve, elle a créé une certaine confusion dans la tête d'Homo Topi.

L'analogie va beaucoup plus loin que ça, c'est pour ça qu'on garde cette terminologie. Je ferai un joli post plus tard.

Poirot a écrit:

L'analogie va beaucoup plus loin que ça, c'est pour ça qu'on garde cette terminologie.

je sais très bien jusqu'où va l'analogie. Ceci dit, les anglo-saxons parlent le plus souvent the "Prime Polynomial Theorem" (PPT), et je suis d'accord pour le choix de cette dénomination.

Il y a certes des analogies, mais aussi des différences conceptuelles majeures entre les corps finis et le reste.

OK ! De toute façon, le cours que Poirot va faire sera nécessairement instructif : il va montrer l'analogie avec le TNP classique (fonction zêta, produit eulérien, etc) et ce sera pédagogiquement intéressant de voir jusqu'où il y a analogie...et où s'arrête la comparaison.

noix de totos me met la pression en parlant de cours !

Bon, comme promis, je tente d'expliquer l'analogie, au moins dans le cas du théorème des nombres premiers (ou des polynômes premiers selon votre religion). Je pense que l'analogie entre nombres premiers et polynômes irréductibles est assez claire (ce sont les éléments irréductibles des deux anneaux $\mathbb Z$ et $\mathbb F_q[T]$, qui se trouvent être factoriels, et donc ces éléments irréductibles interviennent dans la décomposition des éléments de ces anneaux).

Dans $\mathbb Z$, on dispose d'une notion naturelle de taille, donc quand on compte les nombres premiers, on a juste à dire "je cherche les nombres premiers plus petits que $x$".

Dans $\mathbb F_q[T]$, il n'y a priori pas de telle notion de taille. Cependant, la taille d'un entier naturel $n$ peut se lire algébriquement de la manière suivante : c'est le cardinal du quotient $\mathbb Z/n \mathbb Z$. Eh bien on fait la même chose dans $\mathbb F_q[T]$ : le taille du polynôme (non nul) $P$ c'est le cardinal de $\mathbb F_q[T]/(P)$, autrement dit $|P| = q^{\deg P}$.

On s'intéresse aux polynôme unitaires pour des questions de normalisation : si $\lambda \in \mathbb F_q^{\times}$, $P$ et $\lambda P$ sont associés dans $\mathbb F_q[T]$ (tout comme $n$ et $-n$ le sont dans $\mathbb Z$ !).

Il est bien connu que $$\pi(x) := \#\{p \leq x \mid p \text{ premier}\} \underset{x \to +\infty}{\sim} \frac{x}{\log x},$$ c'est le Théorème des Nombres Premiers. Dans $\mathbb F_q[T]$ on a $$\pi_q(n) := \#\{P \in \mathbb F_q[T] \mid P \text{ irréductible, unitaire et } \deg P \leq n\} \underset{n \to +\infty}{\sim} \frac{q^n}{n}$$ autrement dit $$\#\{P \in \mathbb F_q[T] \mid P \text{ irréductible, unitaire et } |P| \leq X\} \underset{n \to +\infty}{\sim} \frac{X}{\log_q X}$$ en notant $X = q^n$ et $\log_q$ le logarithme en base $q$.

On va faire la démonstration qui est très simple dans ce cas ! Et tant qu'à faire on va le faire en poursuivant l'analogie avec le cas classique (il y a une démonstration purement algébrique, mais qui a le défaut de ne pas se généraliser à d'autres situations). On introduit donc la fonction $$\zeta_q : s \mapsto \sum_{Q \in \mathbb F_q[T] \text{ unitaire}} \frac{1}{|Q|^s},$$ à comparer avec $$\zeta : s \mapsto \sum_{n \text{ entier strictement positif}} \frac{1}{|n|^s}.$$ Pour déterminer la région de convergence, on réécrit la somme en utilisant la définition de $|Q|$. Il est clair que pour tout $n \in \mathbb N$, il existe exactement $q^n$ polynômes unitaires de degré $n$ dans $\mathbb F_q[T]$, et donc $$\zeta_q(s) = \sum_{n=0}^{+\infty} \sum_{\underset{\deg Q = n}{Q \in \mathbb F_q[T] \text{ unitaire}}} \frac{1}{q^{ns}} = \sum_{n=0}^{+\infty} \frac{1}{q^{n(s-1)}}.$$ La série converge donc lorsque $\frac{1}{\left|q^{s-1}\right|} < 1$, autrement dit lorsque $\mathfrak{Re}(s) > 1$, et dans ce cas on a $$\zeta_q(s) = \frac{1}{1 - q^{1-s}}.$$ Dans ce cadre, la fonction zêta est une bête bien plus sympathique que dans le cas usuel : c'est juste une fraction rationnelle en $q^{-s}$ ! C'est un phénomène sur lequel je dirai un petit mot un peu plus loin. En attendant, pour alléger les notations, je pose $u := q^{-s}$ de sorte que $\zeta_q(s) = \frac{1}{1-qu}.$

Passons au lien avec les polynômes irréductibles. Comme dans le cas classique, l'existence et l'unicité de la décomposition en facteurs irréductibles permet de voir facilement que $$\zeta_q(s) = \prod_{P \in \mathbb F_q[T] \text{ irréductible unitaire}} \left(1 - \frac{1}{|P|^s}\right)^{-1}$$ (il suffit de développer chaque facteur en série géométrique et distribuer le produit, ce qui est justifié par la convergence absolue).

Cette factorisation montre en particulier que $\zeta_q$ ne s'annule pas sur le domaine $\Omega_1 := \{s \in \mathbb C \mid \mathfrak{Re}(s) > 1\}$ de convergence du produit, on peut donc passer au logarithme : \begin{align*}\log \zeta_q(s) = - \sum_{P \in \mathbb F_q[T] \text{ irréductible unitaire}} \log \left(1 - \frac{1}{|P|^s}\right) &= - \sum_{P \in \mathbb F_q[T] \text{ irréductible unitaire}} \log \left(1 - u^{\deg P}\right)\\ &= \sum_{P \in \mathbb F_q[T] \text{ irréductible unitaire}} \sum_{k=1}^{+\infty} \frac{u^{k \deg P}}{k}.\end{align*} En dérivant tout ça (ce qui est justifié car tout converge absolument sur tout compact de $\Omega_1$), et en souvenant que quand on dérive $u$ par rapport à $s$ on obtient $-u \log q$, on obtient \begin{align*}\frac{\zeta_q'}{\zeta_q}(s) = - \log q \sum_{P \in \mathbb F_q[T] \text{ irréductible unitaire}} \sum_{k=1}^{+\infty} \deg P u^{k \deg P} &= - \log q \sum_{n=1}^{+\infty} \sum_{\underset{P \in \mathbb F_q[T] \text{ irréductible unitaire}}{\deg P = n}} \frac{nu^n}{1-u^n}\\ &= - \log q \sum_{n=1}^{+\infty} \frac{n \pi^*_q(n) u^n}{1-u^n}\end{align*} où $\pi^*_q(n)$ désigne le nombre de polynômes irréductibles unitaires de degré exactement $n$.

En réutilisant la formule $\zeta_q(s) = \frac{1}{1 - qu}$, on calcule la dérivée logarithmique $$\frac{\zeta_q'}{\zeta_q}(s) = - \log q \frac{qu}{1 - qu}.$$

On a donc obtenu l'identité $$\frac{qu}{1 - qu} = \sum_{n=1}^{+\infty} \frac{n \pi^*_q(n) u^n}{1-u^n}.$$ Les calculs peuvent paraître fastidieux, mais c'est très simple par rapport au cadre usuel, et tout est élémentaire, il n'y a que des développements en séries géométriques et de logarithmes. Je passe les détails du prochain calcul qui sont du même ressort : on développe en série les deux membres, et on identifie les coefficients devant $u^n$. On aboutit à $$\sum_{d \mid n} d \pi^*_q(d) = q^n.$$ En appliquant la formule d'inversion de Möbius, on obtient finalement une formule pour $\pi^*_q(n)$ : $$\pi^*_q(n) = \frac{1}{n} \sum_{d \mid n} \mu\left(\frac{n}{d}\right) q^d$$ d'où l'on tire facilement l'estimation $$\pi^*_q(n) = \frac{q^n}{n} + O\left(\frac{q^{n/2}}{n}\right).$$ Le fait que le reste soit de l'ordre de la racine carrée du terme principal est une manifestation de l'hypothèse de Riemann, qui est vraie dans ce contexte. En sommant, on obtient également l'équivalent annoncé du TNP (ou TPP :-P ) : $$\pi_q(n) \underset{n \to +\infty}{\sim} \frac{q^n}{n}.$$

Quelques mots pour finir : cette démonstration a le mérite de se généraliser à beaucoup d'autres problèmes de type "théorème des nombres premiers". On montre de même un théorème des nombres (polynômes) premiers en progressions arithmétiques ou plus généralement un théorème de Chebotarev sur les corps finis. Des travaux profonds de Artin, Davenport, Hasse, Weil, Dwork, Schmidt, Grothendieck et finalement Deligne montrent que dans chacun de ces cas, les fonctions $\zeta$ et $L$ sous-jacentes vérifient toutes les propriétés qu'on peut attendre d'elles : ce sont des fractions rationnelles en $u$ comme ce qu'on a vu au-dessus, satisfaisant une équation fonctionnelle reliant leurs valeurs en $s$ et en $1-s$ (donc en $u$ et en $\frac{q}{u}$, comme dans notre cas très simple) et satisfont l'hypothèse de Riemann : leurs zéros ont pour partie réelle $1/2$ !

Le théorème des nombres premiers classique se démontre avec une stratégie similaire : on étudie la dérivée logarithmique de $\zeta$ pour en tirer des informations sur la taille de ses coefficients (c'est une série de Dirichlet), ce qui mène au théorème des nombres premiers. Bien sûr c'est beaucoup plus difficile car il n'y a pas d'analogue de la gentille formule $\zeta_q(s) = \frac{1}{1-qu}$, et il faut à la place utiliser pas mal d'analyse complexe, ainsi qu'une région sans zéro non triviale pour $\zeta$. J'avais donné plus de détails, et le rapport avec l'hypothèse de Riemann, dans ce message : http://www.les-mathematiques.net/phorum/read.php?16,1966044,1967770#msg-1967770

Merci Poirot, très intéressant pour comprendre un tout petit peu le lien entre la fonction zeta et les nombres premiers.

Je crois que tu as écrit $\pi^*_q(n) = \frac{1}{n} \sum_{d|n} q^d$ au lieu de $\pi^*_q(n) = \frac{1}{n} \sum_{d|n} \mu(n/d) q^d$ (même si ça ne change rien). C'est vrai que pour arriver à cette formule, la preuve algébrique est plus rapide...

@Champ-Pot-Lion : Merci, j'avais oublié bêtement le $\mu$. 8-)

@Homo Topi :

1) Cherche un représentant de chaque classe modulo $P$. Indice : division euclidienne.

2) La somme ne dépend pas de $P$ !

3) La clé est de regrouper les termes qui contribuent à une même puissance $u^n$ donnée.

Vu que nos nombreux lecteurs trépignent d'impatience, je donne la preuve algébrique.

Lemme : Soit $n \geq 1$. Dans $\mathbb F_q[T]$ on a $$X^{q^n} - X = \prod_{\underset{\deg P \mid n}{P \in \mathbb F_q[X] \text{ irréductible unitaire}}} P.$$

Démonstration : $X^{q^n}-X$ est premier avec sa dérivée, donc ses facteurs irréductibles apparaissent avec multiplicité $1$ chacun (sinon il y aurait des racines multiples dans une clôture algébrique !). Puisque $X^{q^n}-X$ est unitaire on peut choisir chacun de ces facteurs unitaires.

Si $P$ est un polynôme irréductible de degré $d \mid n$, son corps de rupture sur $\mathbb F_q$ est un corps fini de cardinal $q^d$, et donc ses racines $\alpha$ vérifient $\alpha^{q^d-1}=1$ par le théorème de Lagrange. Comme $d$ divise $n$, $q^d-1$ divise $q^n-1$ et donc les racines de $P$ sont bien racines de $X^{q^n}-X$. Par le lemme de Gauss, $P$ divise donc $X^{q^n}-X$.

Réciproquement, si $P$ est un facteur irréductible de $X^{q^n}-X$ de degré $d$, alors son corps de rupture $K$ est de cardinal $q^d$ et il est inclus dans $L$, le corps de décomposition de $X^{q^n}-X$, qui est de cardinal $q^n$. Ainsi, $L$ est un $K$-espace vectoriel de dimension finie (puisque ce sont des ensembles finis !) $m$, et donc $q^n = \#L = \#K^m = q^{md}$ et donc $d$ divise $n$.
Il n'y a plus qu'à prendre les degrés de chaque côté pour obtenir comme précédemment $q^n = \sum_{d \mid n} d \pi^*_q(d)$, et on conclut comme avant par inversion de Möbius.

Me concernant, ce lemme est tristement associé à l'agrégation et son caractère absurdement totalement discontinu (enfin ça rend mieux en anglais : "totally disconnected").

Dans un corps finis, tout élément est une racine de l'unité (c'est ce qui fait marcher la démo ci-dessus d'ailleurs), donc effectivement on peut relier ça aux polynômes cyclotomiques !

Il y a bien la question de Christophe: http://www.les-mathematiques.net/phorum/read.php?16,1008195,1963472#msg-1963472

Mais ce n'est pas exactement cette question (on demande simplement si on a un nombre infini de degrés possibles).

Question très naïve: si on prend les nombres constructibles (i.e la clôture quadratique de $\mathbb{Q}$), on a pas, par définition, pas de polynômes irréductibles de degré $2$?

Chat-maths : oui effectivement on peut supprimer le degré $2$.
En fait de la même manière on peut supprimer n'importe quels degrés bornés je dirais (au-delà, il restera les $X^p-2$, $p$ premier plus haut que le degré fixé qui sont irréductibles j'ai l'impression; ah en fait je ne suis pas sûr mais intuitivement c'est raisonnable ?) - mais j'ai pas écrit les détails.

On pourrait reformuler la question de Poirot: sous les mêmes hypothèses existe-t-il des polynômes irréductibles de tout degré $\geq n$ pour au moins un $n$ ?

J'ai envie de croire que la réponse est non, en faisant une construction idiote (résoudre tous les polynômes de degré $p_n$ pour une certaine suite $(p_n)$ non bornée, qui est assez petite en "densité" pour que ça n'implique pas de résoudre tous les polynômes et donc de finir sur la clôture algébrique de $\mathbb Q$ ? je ne sais pas si ça peut marcher)

Ah ! Soit $(p_n)$ une suite croissante non bornée de nombres premiers, qui ne les contient pas tous. Je suppose que $p_1 = 2$ (c'est pour être sûr d'avoir un $i$ et ne pas me casser la tête)

Soit $K$ l'extension algébrique de $\mathbb Q$ construite comme suit : je rajoute une racine à chaque polynôme irréductible de degré $p_n, n\in\mathbb N$, j'obtiens $K_1$, puis je réitère, j'obtiens $K_2$, puis je réitère etc. et je prends l'union (je devrais être plus précis. $K_{n+1}$ est une union dénombrable d'extensions du type $K_{n,m+1}=K_{n,m}(x)/K_{n,m}$ où $x$ est racine d'un polynôme irréductible de degré $p_k$ pour un certain $k$ - je fais une liste de tous ces polynômes et à chaque étape, je rajoute une racine si le polynôme est resté irréductible, et non sinon). J'obtiens un corps $K:=\bigcup_{n\in\mathbb N}K_n$.

Déjà $K$ n'a pas de polynômes irréductibles de degré $p_n$ (il apparaît dans un des $K_n$, et donc on lui rajoute une racine ou bien il perd son irréductibilité, absurde), pour aucun $n$. Donc pour $K$, la réponse à ma question modifiée de Poirot est négative.

Reste à voir si $K$ est algébriquement clos. Je prétends que non. Soit $p$ premier n'apparaissant pas dans la liste $\{p_n, n\in \mathbb N\}$. Je prétends qu'alors $X^p-2$ n'a pas de racine dans $K$. En effet supposons que $x\in K$ soit une telle racine. Alors par construction, $x$ apparaît dans une des extensions successives, disons $K_n$.
Il me suffit donc de prouver par récurrence sur $K_n$ que $x$ n'y apparaît pas.
Pour $K_0 :=\mathbb Q$, c'est clair.
Supposons que c'est vrai au rang $n$ et supposons $x\in K_{n+1}$. Alors pareil, $x$ apparaît après qu'on a rajouté un certain nombre de racines de polynômes irréductibles de degrés $p_{i_1},...,p_{i_k}$. Donc $K_n(x) /K_n$ est une sous-extension d'une tour d'extensions de degrés premiers à $p$. C'est absurde par multiplicativité des degrés.

Donc $x\notin K_{n+1}$.

On conclut ainsi.

Je raconte peut-être n'importe quoi (il est tard, et j'ai pas écrit tous les détails), mais ça a pas l'air fou. Au début d'ailleurs j'avais mal écrit la construction de $K_{n+1}$ à partir de $K_n$ : c'est important de ne pas rajouter de racines aux polynômes qui deviennent réductibles au fur et à mesure, sinon la sur-extension de $K_n(x)/K_n$ peut ne pas être de la forme souhaitée.

On verra au réveil si je divague ou pas.

@Max : ça m'a l'air de fonctionner. Bien joué, notamment le fait de ne pas ajouter bêtement les racines de polynômes qui ne sont plus irréductibles pour faire jouer la multiplicativité des degrés. (tu)

Bonjour,

Tu pourrais nous mettre tout ça dans un pdf, Poirot ? Je sais, c'est du boulot.

Cordialement,

Rescassol

Poirot : merci de confirmer (tu) je suis d'accord que même après m'être réveillé (bon, il est re-tard) ça me semble tenir la route.

Bonjour,

Merci, Poirot.

Cordialement,

Rescassol