Polynôme sans carré

En mathématiques, un polynôme sans carré est un polynôme défini sur un corps (commutatif), ou plus généralement sur un anneau factoriel, qui n'a pour facteur aucun carré d'un facteur non unitaire. Dans le cas des polynômes invariables sur un corps k, cela signifie que $f\in k[X]$ est sans carré si et seulement si $b^{2}\nmid f$ pour chaque polynôme $b\in k[X]$ de degré positif. Dans les applications en physique et en génie, un polynôme sans carré est communément appelé un polynôme sans racines répétées. Ces polynômes sont appelés séparables, mais sur un corps parfait, être séparable équivaut à être sans carré.

Une décomposition sans carré ou une factorisation sans carré d'un polynôme est une factorisation en puissances de facteurs sans carré

$f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{n}^{n}=\prod _{k=1}^{n}a_{k}^{k}\,$

où ceux des a_k qui ne sont pas égaux à 1 sont des polynômes sans carré premiers entre eux. Chaque polynôme non nul avec des coefficients dans un corps admet une factorisation sans carré, unique à produit près des facteurs par des constantes non nulles. La factorisation sans carré est beaucoup plus facile à calculer que la factorisation complète en facteurs irréductibles, et est donc souvent préférée lorsque la factorisation complète n'est pas vraiment nécessaire, comme pour la décomposition décomposition en éléments simples et l'intégration symbolique (en) des fractions rationnelles. La factorisation sans carré est la première étape des algorithmes de factorisation polynomiale qui sont implémentés dans les systèmes d'algèbre informatique. Par conséquent, l'algorithme de factorisation sans carré est basique en algèbre informatique.

Dans le cas de polynômes en une variable sur un corps, tout facteur multiple d'un polynôme introduit un facteur commun non trivial de f et sa dérivée formelle f ', donc une condition suffisante pour que f soit sans carré est que le plus grand diviseur commun de f et f ' soit 1. Cette condition est également nécessaire sur un corps de caractéristique 0 ou, plus généralement, sur un corps parfait, car sur un tel corps, tout polynôme irréductible est séparable, et donc premier avec sa dérivée.

Sur un corps de caractéristique 0, le quotient de $f$ par son PGCD (plus grand commun diviseur) avec son dérivé est le produit des $a_{i}$ dans la décomposition sans carré ci-dessus. Sur un corps parfait de caractéristique p non nulle, ce quotient est le produit des $a_{i}$ tels que i n'est pas un multiple de p. D'autres calculs de PGCD et de quotients permettent de calculer la factorisation sans carré. Dans la caractéristique zéro, un meilleur algorithme est connu, l'algorithme de Yun. Sa complexité en temps est au maximum le double de celle du calcul du PGCD du polynôme d'entrée et de sa dérivée. Plus précisément, si $T_{n}$ est le temps nécessaire pour calculer le PGCD de deux polynômes de degré $n$ et le quotient de ces polynômes par ce PGCD, alors $2T_{n}$ est un majorant du temps nécessaire pour calculer la décomposition sans carré.

Il existe également des algorithmes pour le calcul de la décomposition sans carré de polynômes en plusieurs variables.

Algorithme de Yun

Cette section décrit l'algorithme de Yun pour la décomposition sans carré des polynômes en une variable sur un corps de caractéristique 0. Il procède par une succession de calculs du PGCD et de divisions parfaites.

L'entrée est donc un polynôme f non nul, et la première étape de l'algorithme consiste à calculer le PGCD a₀ de f et sa dérivée formelle f '.

Si

$f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{k}^{k}$

est la factorisation souhaitée, on a donc

$a_{0}=a_{2}^{1}a_{3}^{2}\cdots a_{k}^{k-1},$

$f/a_{0}=a_{1}a_{2}a_{3}\cdots a_{k}$

et

$f'/a_{0}=\sum _{i=1}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.$

Si nous définissons $b_{1}=f/a_{0}$, $c_{1}=f'/a_{0}$ et $d_{1}=c_{1}-b_{1}'$, nous obtenons cela :

$\gcd(b_{1},d_{1})=a_{1},$

$b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},$

et

$c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.$

Répéter ce processus jusqu'à $b_{k+1}=1$ on trouve tous les $a_{i}.$

Ceci est formalisé dans un algorithme comme suit :

« $a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;$
répété
$a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';$
jusqu'à $b=1;$
donne $a_{1},\ldots ,a_{i-1}.$ »

Le degré de $c_{i}$ et $d_{i}$ est un degré de moins que le degré de $b_{i}.$ Comme $f$ est le produit de $b_{i},$ la somme des degrés de $b_{i}$ est le degré de $f.$ Comme la complexité des calculs et des divisions du PGCD augmente de façon plus que linéaire avec le degré, il s'ensuit que la durée d'exécution totale de la boucle de répétition est inférieur à la durée d'exécution de la première ligne de l'algorithme et que la durée d'exécution totale de l'algorithme de Yun est majorée par le double du temps nécessaire pour calculer le PGCD de $f$ et $f'$ et les quotients de $f$ et $f'$ par ce PGCD.

Racine carrée

En général, un polynôme n'a pas de racine carrée. Plus précisément, la plupart des polynômes ne peuvent pas être écrits comme le carré d'un autre polynôme.

Un polynôme a une racine carrée si et seulement si tous les exposants de la décomposition sans carré sont pairs. Dans ce cas, la racine carrée est obtenue en divisant par 2 ces exposants.

Ainsi, le problème de savoir si un polynôme a une racine carrée, et de la calculer si elle existe, est un cas particulier de factorisation sans carré.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Square-free polynomial » (voir la liste des auteurs).