Anneaux de polynômes#

1. Exponentiation rapide.#

Écrire une procédure calculant une puissance par exponentiation rapide. Estimer la complexité. Illustrer.

2. Méthode de Horner.#

Écrire une fonction d’évaluation à l’aide de la méthode de Horner. Écrire une fonction implémentant l’évaluation naive. Illustrer les résultats du cours.

3. Décomposition sans carré.#

Soit \(K\) un corps de caractéristique nulle. Pour un polynôme \(P\in \ K[X]\) unitaire, on note \(P=P_1^{r_1}\cdots P_k^{r_k}\) sa décomposition en facteurs irréductibles. La partie sans carré de \(P\) est \(P_1\cdots P_k\). On dit que \(P\) est sans carré s’il est égal à sa partie sans carré. Montrer que le polynôme \(P \in K [X]\) est sans carré si et seulement si \(P\) et \(P'\) sont premiers entre eux. Vérifiez bien que votre preuve est compatible avec les résultats de l’exercice précédent…

4. Décomposition sans carré dans \(\mathbb Q\)#

  • Expliquer comment trouver la partie sans carré d’un polynôme (unitaire) dans \(\mathbb Q[X]\) sans le factoriser.

  • Écrire une procédure calculant la partie sans carré d’un polynôme \(P\in\mathbb Q[X]\) sans le factoriser.

  • Montrer que tout polynôme \(P\in\mathbb Q[X]\) unitaire de degré \(n\) peut s’écrire \(P=Q_1 (Q_2)^2\cdots (Q_n)^n\) où les \(Q_i\in\mathbb Q [X]\) sont sans carré et premiers entre eux. On parle de \emph{décomposition sans carré}.

  • Expliquer comment calculer la décomposition sans carré d’un polynôme (unitaire) sans le factoriser.

  • Écrire une procédure calculant la décomposition sans carré d’un polynôme \(P\in\mathbb Q[X]\) sans le factoriser.

5. Un polynôme irréductible non premier avec sa dérivée.#

Soit \(K =\mathbb{Z}/ 2\mathbb{Z} (Y)\) et \(P (X)= X^2 + Y \in K[X]\).

  • Montrer que \(P\) est irréductible.

  • Vérifier votre résultat avec sage.

  • Les polynômes \(P\) et \(P'\) sont-ils premiers entre eux ?

6. Partie sans carré dans \(\mathbb Z/p\mathbb Z\).#

  • Soit \(P\in\mathbb Z/p\mathbb Z[X]\) un polynôme unitaire et \(P= P_1^{m_1} \cdots P_r^{m_r} \in \mathbb{F}_p [X]\) sa décomposition en facteurs irréductibles. Montrer que \(P /\mathrm{pgcd} (P, P') = \prod_{p \wedge m_i = 1} P_i\).

  • Expliquer comment calculer \(R = \prod_{p \wedge m_i \neq 1} P_i^{m_i}\) sans factoriser \(P\).

  • Expliquer comment calculer la partie sans carré de \(P\in\mathbb Z/p\mathbb Z[X]\) (unitaire) sans factoriser \(P\).

  • Écrire une procédure calculant la partie dans carré dans \(\mathbb Z/p\mathbb Z\).

7. Dichotomie.#

Écrire une procédure basée sur la dichotomie prenant en entrée un polynôme \(P\in\mathbb Q[X]\), \(a<b\) tels que \(P(a)P(b)<0\) et \(\epsilon >0\) et renvoyant une valeur approchée à \(\epsilon\)-près d’une racine de \(P\) dans \([a,b]\). Illustrer avec sage l’évolution de nombre de décimales correctes.

8. Lemme de Hensel.#

  • Soit \(P \in \mathbb{Z} [X]\), \(p\) premier et \(n \geq 1\). On suppose qu’il existe \(x \in \mathbb{Z}\) tel que \(P (x) \equiv 0 [p^n]\) et \(P' (x) \not\equiv 0 [p]\). Montrer qu’il existe un unique \(\overline{y} \in \mathbb{Z}/ p^{2 n} \mathbb{Z}\) tel que \(P (y) \equiv 0 [p^{2 n}]\) et \(x \equiv y [p^n]\) où \(y\) est un relevé de \(\overline{y}\). Indication : on pourra écrire \(P(X+H)=P(X)+HP'(X)+H^2R(X)\).

  • Écrire une procédure prenant en entrée un polynôme \(P\in\mathbb{Z}[x]\), un nombre premier \(p\), un entier \(x\) vérifiant \(P(x)\equiv 0\,(\bmod\, p)\) et \(P'(x)\not\equiv 0\,(\bmod\, p)\), et un entier \(m\geq 1\), et renvoyant un entier \(y\) tel que \(x\equiv y\,(\bmod\, p)\) et \(P(y)\equiv 0\,(\bmod\,p^{2^m})\).

  • En utilisant cette fonction, déterminer les racines carrées de \(2\) dans \(\mathbb{Z}/7^{32}\mathbb{Z}\).

  • (Super bonus) La preuve du lemme de Hensel fait penser à la méthode de Newton. Quel est le cadre d’application de la méthode de Newton dans ce cas ?

9. Irréductibilité dans \(\mathbb Z[X]\).#

Soit \(P=x^3+2x+16\).

  • Avec sage, factoriser \(\bar{P}\), la réduction de \(P\) modulo \(11\) .

  • En utilisant la fonction hensel de l’exercice précédent, déterminer l’unique racine de \(P\) modulo \(11^2\) (pourquoi cette racine est-elle unique ?).

  • En utilisant des bornes sur les racines, déduire que \(P\) est irréductible dans \({\mathbb Z}[x]\).

10. Irréductibilité dans \(\mathbb Z[X]\).#

Soit \(P=x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\in{\mathbb Z}[x]\).

  • Factoriser \(P\) modulo \(2\) et modulo \(13\).

  • Déduire que \(P\) est irréductible dans \({\mathbb Z}[x]\).

11. Méthode de Newton#

  • Écrire la méthode de Newton sous la forme d’une fonction prenant en entrée une fonction (dont on cherche un zéro), sa dérivée, le point de départ de l’itération de Newton et le nombre d’itérations à effectuer.

  • Tester votre fonction avec \(f :x\mapsto x^3-2\). Illustrer la convergence quadratique.

  • Tester votre fonction avec \(f : x\mapsto x^3-2x^2-11x+12\) et pour points de départ \(2.3528\), \(2.35286\) et \(2.35288\).

  • Tester votre fonction avec \(f : x\mapsto x^3 -2x+2\) avec pour point de départ \(0\).

12. Méthode de Graeffe (1826).#

Soit \(P\in\mathbb C[X]\) unitaire de degré \(n\). On note \(z_1,\dots,z_n\) ses racines (avec répétition s’il y a des racines multiples).

  • Expliquer comment obtenir, sans déterminer les racines de \(P\), un polynôme \(Q\) unitaire de degré \(n\) dont les racines sont exactement \(z_1^2,\dots,z_n^2\). Indication : on pourra considérer \(P(X)P(-X)\).

  • On suppose maintenant que \(z_n\) est réelle et strictement plus grande que \(1\) et que toutes les autres racines de \(P\) sont de module strictement plus petit que \(1\). On considère la suite de polynômes \((P_m)\) définie par \(P_0=P\) et \(P_j\) est obtenu à partir de \(P_{j-1}\) en appliquant le procédé décrit dans la question précédente. Soit \(\rho<1\) un majorant du module des racines différentes de \(z_n\). Estimer les coefficients de degré \(n-1\) de la suite \((P_m)\) à l’aide de \(z_n\), \(m\) et \(\rho\).

  • Expliquer comment utiliser ce qui précède pour déterminer une valeur approchée de \(z_n\). Illustrer avec sage.