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 , cela signifie que  est sans carré si et seulement si  pour chaque polynôme  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é

 

où ceux des  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' 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  par son PGCD (plus grand commun diviseur) avec son dérivé est le produit des  dans la décomposition sans carré ci-dessus. Sur un corps parfait de caractéristique  non nulle, ce quotient est le produit des  tels que  n'est pas un multiple de . 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  est le temps nécessaire pour calculer le PGCD de deux polynômes de degré  et le quotient de ces polynômes par ce PGCD, alors  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 a0 de f et sa dérivée formelle f '.

Si

 

est la factorisation souhaitée, on a donc

 
 

et

 

Si nous définissons ,  et , nous obtenons cela :

 
 

et

 

Répéter ce processus jusqu'à  on trouve tous les 

Ceci est formalisé dans un algorithme comme suit :

Le degré de  et  est un degré de moins que le degré de  Comme  est le produit de  la somme des degrés de  est le degré de  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  et  et les quotients de  et  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 

Calcul formel
Polynôme