\documentclass{article}
\usepackage[francais]{babel}
% changement de l'encodage de T1 en OT1 sur mon système
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newtheorem{thm}{Théorème}

\begin{document}
\title{Compléments sur les polynômes}
\author{Bernard.Parisse@ujf-grenoble.fr}
\maketitle
\section{Le résultant}
Il s'agit d'un point de vue d'algèbre linéaire sur le PGCD. Considérons
deux polynômes $A$ et $B$ de degrés $p$ et $q$ et de pgcd $D$ et 
l'identité de Bézout correspondante~:
\begin{equation} \label{eq:bezout}
 A U + B V =D
\end{equation}
avec degré$(U)<q$ et degré$(V)<p$.
Imaginons qu'on cherche $U$ et $V$ en oubliant qu'il s'agit d'une
identité de Bézout, en considérant simplement qu'il s'agit d'un
problème d'algèbre linéaire de $p+q$ équations (obtenues en développant
et en identifiant chaque puissance de $X$ de 0 à $p+q-1$) 
à $p+q$ inconnues (les $p$ coefficients de $V$ et les $q$ coefficients de $U$)
On sait que $A$ et $B$ sont premiers entre eux si et seulement si ce problème
d'algèbre linéaire a une solution pour $D=1$. Donc si le déterminant
du système est non nul, alors $A$ et $B$ sont premiers entre eux.
Réciproquement si $A$ et $B$ sont premiers entre eux, le système a
une solution unique non seulement avec comme second membre $1$ mais avec
n'importe quel polynôme de degré inférieur $p+q$, donc le
déterminant du système est non nul.

{\bf Définition:} \\
On appelle résultant de $A$ et $B$ le déterminant de ce système 
(\ref{eq:bezout}). Il s'annule si et seulement si $A$ et $B$
ne sont pas premiers entre eux (ont au moins une racine commune).
On appelle matrice de Sylvester la transposée de la matrice du système
(les inconnues étant par ordre décroissant les coefficients de $U$
et $V$)
\[ M(A,B)=\left( \begin{array}{cccccccc}
a_a   & a_{a-1} & \ldots & \ldots & a_0 & 0   & \ldots & 0 \\
0     & a_a     & \ldots & \ldots & a_1 & a_0 & \ldots & 0 \\
\vdots &        &        &      &     &  &      & \vdots \\
0     & 0       & \ldots &     &     &    &    & a_0 \\
b_b   & b_{b-1} & \ldots & b_0  & 0 &  0 & \ldots & 0 \\
\vdots &        &        &      &     &    &    & \vdots \\
0     &   0     & \ldots &    &      &     &   & b_0 
\end{array}
\right) \]
(cette matrice contient $b=$degré$(B)$ lignes de coefficients
du polynôme $A$ et $a=$degré$(A)$ lignes de coefficients du
polynôme $B$)

{\bf Lien avec l'algorithme du sous-résultant (calcul de PGCD)}\\
On peut calculer le déterminant avec la suite des restes de divisions
euclidiennes de la manière suivante, on part de la pseudo-division
de $A$ par $B$~:
\[ b_b^{a-b+1} A=BQ+R \]
on effectue alors sur chaque ligne contenant les coefficients de $A$
la manipulation de ligne correspondante, c'est-à-dire multiplier
la ligne par $b_b^{a-b+1}$ et soustraire ($q_0$ fois la ligne
de $B$ terminant dans la même colonne+$q_1$ fois la ligne
de $B$ terminant une colonne avant+...). Toutes les lignes
contenant les coefficients de $A$ ont été remplacées par des lignes 
contenant les coefficients de $R$. Ces lignes contiennent $k$ zéros initiaux
avec $k \geq 1$, ce qui permet de réduire le déterminant à celui
de la matrice de Sylvester de $R$ et $B$ (à un coefficient multiplicatif
près qui vaut $b_b^k$ par rapport au précédent donc
$b_b^{k-b(a-b+1)}$ par rapport au déterminant de départ). 
On échange ensuite $R$ et $B$ ce qui change
éventuellement le signe et on continue en faisant les
divisions euclidiennes de l'algorithme du sous-r\'esultant (cf.
Knuth o\`u on utilise la matrice de Sylvester pour prouver que
l'algorithme du sous-r\'esultant est correct). Rappelons que
le sous-résultant définit les suites $A_k$ ($A_0=A, A_1=B$),
$d_k$ le degré de $A_k$, $\delta_k=d_k-d_{k+1}$,
$g_k$ ($g_0=1$, si $k\neq 0$, $g_k$ coefficient dominant de $A_k$) 
$h_k$ ($h_0=1$, $h_{k+1}=h_k^{1-\delta_k} g_{k+1}^{\delta_k}$) et
\[ g_k^{\delta_{k-1}+1} A_{k-1} = A_k Q_{k+1} + 
g_{k-1} h_{k-1}^{\delta_{k-1}} A_{k+1} \]
\begin{thm}
Le résultant est égal au signe près au coefficient $h_k$ où $k$
correspond au reste $A_k$ constant (en supposant que le résultant
soit non nul).
\end{thm}

{\bf Preuve}\\
La transcription de l'égalité précédente sur les
résultants donne par la méthode ci-dessus~:
\begin{eqnarray*}
 g_k^{(\delta_{k-1}+1)d_k}\mbox{Res}(A_{k-1},A_k)
&=& 
g_k^{d_{k-1}-d_{k+1}} \mbox{Res}(g_{k-1} h_{k-1}^{\delta_{k-1}} A_{k+1},A_k)\\
&= &
g_k^{d_{k-1}-d_{k+1}} (g_{k-1} h_{k-1}^{\delta_{k-1}})^{d_k}
\mbox{Res}(A_{k+1},A_k)
 \end{eqnarray*}
On en déduit que~:
\[ \frac{\mbox{Res}(A_{k-1},A_k)}{g_{k-1}^{d_k} h_{k-1}^{d_{k-1}-1}}
= g_k^{d_{k-1}-d_{k+1}-(\delta_{k-1}+1)d_k}  
h_{k-1}^{\delta_{k-1}{d_k}+1-d_{k-1}} \mbox{Res}(A_{k+1},A_k) \]
On observe que~:
\[ h_{k-1}^{\delta_{k-1}{d_k}+1-d_{k-1}} =h_{k-1}^{(\delta_{k-1}-1)(d_k-1)}
= \left( h_{k-1}^{\delta_{k-1}-1}\right) ^{d_k-1}
= \left( \frac{g_k^{\delta_{k-1}}}{h_{k}} \right) ^ {d_k-1}\]
donc~:
\begin{eqnarray*}
 \frac{\mbox{Res}(A_{k-1},A_k)}{g_{k-1}^{d_k} h_{k-1}^{d_{k-1}-1}}
&=& g_k^{d_{k-1}-d_{k+1}-(\delta_{k-1}+1)d_k}  
\left( \frac{g_k^{\delta_{k-1}}}{h_{k}} \right) ^ {d_k-1} 
\mbox{Res}(A_{k+1},A_k) \\
&=& 
g_k^{d_{k-1}-d_{k+1}-d_k-\delta_{k-1}}  
\left( \frac{1}{h_{k}} \right) ^ {d_k-1} 
\mbox{Res}(A_{k+1},A_k) \\
&=& \frac{ \mbox{Res}(A_{k+1},A_k) } { g_k^{d_{k+1}} h_{k}^ {d_k-1}}
\end{eqnarray*}
Donc en valeur absolue
\[ |\frac{\mbox{Res}(A_{0},A_1)}{g_{0}^{d_1} h_{0}^{d_{0}-1}}|
= |\frac{\mbox{Res}(A_{k-1},A_k)}{g_{k-1}^{d_k} h_{k-1}^{d_{k-1}-1}} |\]
En prenant le rang $k$ tel que $A_{k}$ est constant, on a $d_k=0$
et le résultant est égal à $g_k^{d_{k-1}}$, on obtient donc~:
\[ |\mbox{Res}(A_{0},A_1)|=|\frac{g_k^{d_{k-1}}}{ h_{k-1}^{d_{k-1}-1}} |
\]
Comme ici $\delta_{k-1}=d_{k-1}$, le terme de droite est $|h_k|$.

{\bf Remarque}\\
On peut calculer au fur et à mesure le signe du résultant en tenant 
compte des degrés de $A_k$ pour inverser l'ordre de $A_{k-1}$ et
$A_k$ dans le résultant.

{\bf Utilisation}\\
La valeur du r\'esultant est tr\`es utile pour savoir si 2 polyn\^omes
d\'ependant de param\`etres sont premiers entre eux en fonction
de la valeur des param\`etres. En effet, la fonction {\tt gcd} d'un
logiciel de calcul formel calculera le PGCD par rapport \`a toutes
les variables en incluant les param\`etres. En cherchant quand le r\'esultant
s'annule en fonction des param\`etres on obtient un autre type
d'information.

{\bf Exemple~:}\\ 
Chercher quand le polyn\^one $P=x^3+px+q$ poss\`ede
une racine multiple en fonction de $p$ et $q$. On calcule le
r\'esultant de $P$ et $P'$ et on trouve $4p^3+27q^2$, donc $P$
a une racine multiple si et seulement si $4p^3+27q^2=0$.

{\bf Remarque~:}\\
On peut montrer que le r\'esultant de $P$ et $P'$ est divisible
par le coefficient dominant de $P$, on appelle le quotient discriminant.

\section{Les suites de Sturm}
L'algorithme du sous-r\'esultant appliqu\'e \`a un polyn\^ome sans
racine multiple $P$ et \`a sa d\'eriv\'ee
permet, \`a condition de changer les signes dans la suite des restes, 
de connaitre le nombre de racines r\'eelles d'un polyn\^ome dans un 
intervalle. Ceci est tr\`e utile pour par exemple simplifier des valeurs
absolues de polyn\^omes dans un intervalle.

On d\'efinit donc la suite de polyn\^omes $A_0=P, A_1=P', ..., A_k,0$
par~:
\begin{equation} \label{eq:sturm}
 A_{i} = A_{i+1} Q_{i+2} - A_{i+2} 
\end{equation}
avec $A_k$, le dernier reste non nul, un polyn\^ome constant puisque
$P$ n'a pas de racine multiple. On utilise plutot l'algorithme du 
sous-r\'esultant que l'algorithme d'Euclide, il faut alors
s'assurer que les signes de $A_i$ et $A_{i+2}$ sont oppos\'es lorsque
$A_{i+1} $ s'annule quitte \`a changer le signe de $A_{i+2}$ en fonction
du signe du coefficient dominant de $A_{i+1}$, de la parit\'e de
la diff\'erence des degr\'es et du signe du coefficient $gh^{1-\delta}$.

On d\'efinit $s(a)$ comme \'etant le nombre de changements de signes
de la suite $A_i(a)$ en ignorant les 0.
Alors le nombre de racines r\'eelles de $A_0=P$ sur l'intervalle
$]a,b]$ est \'egal \`a $s(a)-s(b)$.

{\bf Preuve}\\
On consid\'ere la suite des signes en un point~: elle ne peut contenir
deux 0 successifs (sinon toute la suite vaudrait 0 en ce point en appliquant
(\ref{eq:sturm}), or $A_k$ est constant non nul). Elle ne peut pas
non plus contenir +,0,+ ni -,0,- \`a cause de la convention de signe
sur les restes de (\ref{eq:sturm}). Donc une racine $b$
de $A_i$ pour $0<i<k$, n'influe pas sur la valeur de $s$ au voisinage
de $b$ (il y a toujours un changement de signe entre les positions
$i-1$ et $i+1$). Comme $A_k$ est constant, seules les racines de $A_0=P$
sont susceptibles de faire varier $s$. Comme $A_1=P'$, le sens de
variations de $A_0$ au voisinage d'une racine de $A_0$ est d\'etermin\'e
par le signe de $A_1$, donc les possibilit\'es sont -,+ vers +,+
ou +,- vers -,-, ce qui diminue $s$ d'une unit\'e.

\section{Exercices sur les polynômes}
\subsection{Quelques instructions utiles}
Les instructions arithm\'etiques de \verb|maple| 
sont dans la librairie standard. Celles de \verb|MuPAD| sont
dans la librairie standard ou dans la librairie \verb|numlib|
(utilisez \verb|?numlib| pour avoir la liste des fonctions de théorie 
des nombres), on peut lancer la commande 
\verb|export(numlib);| pour \'eviter de taper \verb|numlib::|
devant les commandes correspondantes.

\subsubsection{Entiers}
\begin{itemize}
\item (MuPAD) \verb|numlib::divisors| / (maple) \verb|numtheory::divisors|: 
liste des diviseurs d'un entier
\item \verb|gcd|: PGCD
\item (MuPAD) \verb|numlib::ichrem|/ (maple) \verb|chrem|: 
restes chinois (entier)
\item \verb|igcdex|: Bézout pour des entiers
\item (MuPAD) \verb|numlib::genpoly|/ (maple) \verb|genpoly|: 
crée un polynôme à partir de la
représentation $z$-adique d'un entier (utile pour le PGCD heuristique) 
\item \verb|iquo| et \verb|irem| quotient et reste de la division euclidienne
de deux entiers
\item \verb|isprime| test de (pseudo-)primalit\'e
\item \verb|modp|: reste euclidien positif,
\item \verb|mods|: reste euclidien symétrique
\item \verb|nextprime| et \verb|prevprime| 
(\verb|numlib::prevprime| en mupad): nombre premier suivant ou pr\'ec\'edent
\end{itemize}

\subsubsection{Polyn\^omes}
Pour travailler efficacement en MuPAD avec les polynômes, on utilisera
\verb|poly|, en pr\'ecisant le type de coefficients si on travaille
dans $\Z/n\Z$, par exemple \verb|poly(x^2+1,[x],IntMod(13))|. 
Pour travailler dans $\Z/n\Z[X]$ en Maple,
on utilise les formes inertes des instructions (qui renvoient l'instruction
non \'evalu\'ee), dont le nom est le m\^eme que le nom de commande
habituel mais pr\'ec\'ed\'e par une majuscule, puis on indique
\verb|mod n|, par exemple \verb|Gcd(a,b) mod 11|.

\begin{itemize}
\item \verb|coeff| coefficient(s) d'un polyn\^ome, 
\item (Maple) \verb|coeffs|  liste des coefficients d'un polyn\^ome
(\`a d\'evelopper auparavant, en mupad on utilise \verb|coeff|)
\item \verb|content| contenu (pgcd des coefficients)
\item \verb|degree| degré
\item \verb|divide| division euclidienne, 
\item \verb|gcd| PGCD,
\item \verb|gcdex| B\'ezout, 
\item \verb|icontent|: contenu entier pour un polyn\^ome \`a plusieurs
variables
\item \verb|indets|: liste des noms de variables d'une expression
\item \verb|lcoeff|: coefficient dominant d'un polyn\^ome
\item \verb|ldegree|: valuation
\item \verb|multcoeffs| multiplie les coefficients d'un polynômes
\item (MuPAD) \verb|pdivide| pseudo-division
\item (MuPAD) \verb|poly(expr,[var],coeff)| crée un polynôme à partir de
l'expression symbolique \verb|expr| par rapport une variable ou
à une liste de variables \verb|var|, on peut indiquer dans quel anneau 
vivent les coefficients (par exemple dans $\Z/13\Z$ avec comme 3ème argument
\verb|IntMod(13)|)
\item \verb|primpart|: partie primitive d'un polyn\^ome
\item \verb|quo|, \verb|rem| (Maple) quotient et reste euclidien
\item \verb|tcoeff|: coefficient de plus bas degr\'e d'un polyn\^ome
\end{itemize}

\subsection{Exercices (PGCD et applications)}
\begin{enumerate}
\item Déterminez la factorisation dans $\Z[X]$ de
$P=72x^6+276x^5-106x^4-217x^3+72x^2+44x-16$ 
en utilisant \verb|gcd| pour déterminer la multiplicité des facteurs.
\item On veut comprendre comment un logiciel de calcul formel calcule
\[ \int \frac{x^6+2}{(x^3+1)^2} \ dx \]
On se ramène d'abord à une fraction propre (num\'erateur $N$ de degr\'e 
inf\'erieur au d\'enominateur),
Soit $P=X^3+1$, calculez le PGCD de $P$ et $P'$, puis
deux polyn\^omes $U$ et $V$ tels que:
\[ N=UP+VP' \]
On d\'ecompose alors l'int\'egrale en deux morceaux~:\\
\[ \int \frac{N}{P^2}=\int \frac{U}{P}  + \int V \frac{P'}{P^2}  \]
Faites une int\'egration par parties sur le deuxi\`eme terme
et en d\'eduire la valeur de l'int\'egrale du d\'epart.

\item Calculez le pgcd de $x^{202}+x^{101}+1$
et sa dérivée modulo 3 et modulo 5. Conclusion?

\item $P=51x^3-35x^2+39x-115$ et $Q=17x^4-23x^3+34x^2+39x-115$.
Calculez le pgcd de $P$ et $Q$ modulo 5, 7 et 11. En déduire
le pgcd de $P$ et $Q$ par le théorème des restes chinois. Pourquoi
ne doit-on pas essayer modulo 17?

\item Détaillez l'algorithme du PGCD heuristique pour les
polynômes  $P=(x+1)^7-(x-1)^6$ et sa dérivée. Comparez avec l'algorithme
d'Euclide naïf.
\item Montrer que si $P(\frac{p}{q})=0$ avec $p$ et $q$ premiers
entre eux, alors $p$ divise le coefficient
constant de $P$ et $q$ le coefficient dominant de $P$. 
D\'eterminer les racines rationnelles du polyn\^ome $2X^3-X^2-1262X-11339$.
\'Ecrire un programme mettant en oeuvre cet algorithme, que pensez-vous
de son efficacité?\\
Retrouvez les racines rationnelles de $(2*x-999)*(3*x-1000)*(5*x-1001)$
par une m\'ethode modulaire/p-adique (avec $p=11$)
\item \'Ecrire un programme qui d\'etermine le degr\'e probable
du pgcd de 2 polyn\^omes en une variable en utilisant le pgcd modulaire 
(on consid\`ere le degr\'e probable d\'etermin\'e lorsqu'on trouve
deux nombres premiers r\'ealisant le minimum des degr\'es trouv\'es)
\item M\^eme question pour un polyn\^ome \`a plusieurs variables
en utilisant cette fois l'\'evaluation en toutes les variables
sauf une
\item \'Ecrire un programme mettant en oeuvre le pgcd heuristique
pour des polyn\^omes \`a une variable.
\item Que se passe-t-il lorsqu'on ex\'ecute l'algorithme de Yun
dans $\Z/n\Z$?
\item Calculer le pgcd par une m\'ethode modulaire de
$(xy-x+1)(xy+x^2+1)$ et $(xy-x-y)(xy-x+1)$
\end{enumerate}

\subsection{Exercices (factorisation)~:}
\begin{itemize}
\item Déterminer les degrés des facteurs de $(x^3+x+1)(x^4+x+1)$ modulo 5
et 7 (sans utiliser la commande factor). Peut-on en déduire que $x^3+x+1$ et
$x^4+x+1$ sont irréductibles sur $\Z$?
\item Factoriser le polynôme $x^5+x+1$ en utilisant la méthode 
de Berlekamp.
\item Utiliser les options ``verbose'' de votre logiciel de calcul formel
pour factoriser $x^{202}+x^{101}+1$ et vérifiez que vous avez compris
la méthode utilisée.
\item Montrer que $2x+x^2y+x^3+2x^4+y^3+x^5$ est irréductible sur $\Z$
sans utiliser l'instruction factor (on pourra factoriser pour quelques
valeurs de $x$ ou de $y$)
\item Calculer avec un logiciel les valeurs numériques des racines
complexes de $P(x)=x^5+x+1$. Trouver les combinaisons de racines
dont la somme est entière (aux arrondis près). En déduire la factorisation
en facteurs irréductibles sur $\Z$ de $P$.
\item Factorisation numérique sur $\C$. \'Ecrire un programme
qui calcule une racine d'un polynôme à coefficients complexes
en utilisant une méthode itérative de type méthode de Newton 
(avec éventuellement un préfacteur lorsqu'on débute la recherche).
Les polynômes seront représentés par la liste de leurs coefficients
et l'évaluation faite par la méthode de Horner.
Trouver ensuite toutes les racines du polynôme en éliminant la
racine trouvée (toujours avec Horner). Trouver les combinaisons
de racines correspondant à un facteur à coefficients entiers.
\item Même question pour les facteurs de degré 2 d'un polynôme à coefficients
réels sans racines réelles en utilisant la méthode de Bairstow décrite
ci-dessous.\\
On cherche un facteur $F=x^2+sx+p$ de $P$, on calcule le quotient et le reste
de la division $P=FQ+R$ par une méthode de type Horner, il s'agit de 
rendre $R$ (vu comme un vecteur à 2 composantes) nul. On calcule
donc $\partial_{s,p} R$ (en cherchant le quotient et le reste
de $xQ$ et $Q$ par $F$, pourquoi?) et on pose~:
\[(s,p)_{n+1}=(s,p)_n- \lambda (\partial_{s,p} R)^{-1} R (s,p)_n\]
où $\lambda$ est un préfacteur compris entre 0 et 1 et ajusté à 1 
lorsqu'on est proche du facteur.

\end{itemize}


\end{document}

\section{Les limites}
L'algorithme mrv

\section{L'int\'egration}
L'algorithme de Risch.

\section{Syst\`emes polynomiaux}
Les bases de Groebner.