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 ${\displaystyle f\in k[X]}$ est sans carré si et seulement si ${\displaystyle b^{2}\nmid f}$ pour chaque polynôme ${\displaystyle b\in k[X]}$ de degré positif^[1]. 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é

${\displaystyle 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^[1]. 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 ${\displaystyle f}$ par son PGCD (plus grand commun diviseur) avec son dérivé est le produit des ${\displaystyle 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 ${\displaystyle 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^[1]. 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 ${\displaystyle T_{n}}$ est le temps nécessaire pour calculer le PGCD de deux polynômes de degré ${\displaystyle n}$ et le quotient de ces polynômes par ce PGCD, alors ${\displaystyle 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^[2].

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^[1]. 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

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

est la factorisation souhaitée, on a donc

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

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

et

${\displaystyle 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 ${\displaystyle b_{1}=f/a_{0}}$, ${\displaystyle c_{1}=f'/a_{0}}$ et ${\displaystyle d_{1}=c_{1}-b_{1}'}$, nous obtenons cela :

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

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

et

${\displaystyle 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'à ${\displaystyle b_{k+1}=1}$ on trouve tous les ${\displaystyle a_{i}.}$

Ceci est formalisé dans un algorithme comme suit :

« ${\displaystyle 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é
${\displaystyle 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'à ${\displaystyle b=1;}$
donne ${\displaystyle a_{1},\ldots ,a_{i-1}.}$ »

Le degré de ${\displaystyle c_{i}}$ et ${\displaystyle d_{i}}$ est un degré de moins que le degré de ${\displaystyle b_{i}.}$ Comme ${\displaystyle f}$ est le produit de ${\displaystyle b_{i},}$ la somme des degrés de ${\displaystyle b_{i}}$ est le degré de ${\displaystyle 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 ${\displaystyle f}$ et ${\displaystyle f'}$ et les quotients de ${\displaystyle f}$ et ${\displaystyle 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).

1. (en) David Y. Y. Yun, « On square-free decomposition algorithms », dans SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation, 1976 (DOI 10.1145/800205.806320), p. 26-35.
2. (en) P. Gianni et B. Trager, « Square-free algorithms in positive characteristic », Applicable Algebra In Engineering, Communication And Computing, vol. 7, n^o 1,‎ 1996, p. 1-14 (DOI 10.1007/BF01613611).