Rappels et 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. 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 ?

4. Polynôme sans carré.#

Soit \(K\) de caractéristique nulle ou \(K =\mathbb{Z}/ p\mathbb{Z}\). Pour un polynôme \(P\in \mathbb 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…

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

  • Soit \(P = P_1^{m_1} \cdots P_r^{m_r} \in \mathbb Z/p\mathbb Z[X]\) unitaire où les \(P_i\) sont deux à deux distincts. 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\).

6. 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.

7. 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\).

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 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.

12. Bonus - Fractale de Newton.#

L’objectif de cet exercice est d’étudier les bassins d’attraction de la méthode de Newton appliquée à la fonction \(f :\mathbb C\to \mathbb C\) définie par \(f(z)=z^3-1\). La fonction \(f\) a trois racines complexes \(1\), \(j\) et \(j^2\), on attribue à chacun de ces points une couleur. On veut colorier le plan en fonction des racines atteintes par l’itération de Newton. On procède de la façon suivante.

  • On choisit un maillage du carré \([-2,2]\times[-2,2]\), un nombre d’itérations \(N\) (par exemple 20) et une borne d’erreur \(\epsilon\) (par exemple \(10^{-3}\)).

  • Pour tout point \(x_0\) du maillage, on lance une itération de Newton à partir de \(x_0\)

    • Si l’itération tombe en moins de \(N\) étapes dans un disque de taille \(\epsilon\) autour d’une des racines, on arrête d’itérer et on colorie \(x_0\) de la couleur associée à la racine approchée.

    • Si en \(N\) itérations, on ne s’est pas approché d’une racine, on laisse le point en blanc.