Résultat - Resultant

En mathématiques , la résultante de deux polynômes est une expression polynomiale de leurs coefficients, qui est égale à zéro si et seulement si les polynômes ont une racine commune (éventuellement dans une extension de champ ), ou, de manière équivalente, un facteur commun (sur leur champ de coefficients). Dans certains textes plus anciens, la résultante est aussi appelée l' éliminant .

La résultante est largement utilisée en théorie des nombres , soit directement, soit par l'intermédiaire du discriminant , qui est essentiellement la résultante d'un polynôme et de sa dérivée. La résultante de deux polynômes avec des coefficients rationnels ou polynomiaux peut être calculée efficacement sur un ordinateur. C'est un outil de base du calcul formel et une fonction intégrée à la plupart des systèmes de calcul formel . Il est utilisé, entre autres, pour la décomposition algébrique cylindrique , l' intégration de fonctions rationnelles et le tracé de courbes définies par une équation polynomiale bivariée .

La résultante de n polynômes homogènes à n variables (appelée aussi résultante multivariée , ou résultante de Macaulay pour la distinguer de la résultante habituelle) est une généralisation, introduite par Macaulay , de la résultante habituelle. C'est, avec les bases de Gröbner , l'un des principaux outils de la théorie de l'élimination efficace (théorie de l'élimination sur ordinateur).

Notation

La résultante de deux polynômes univariés A et B est communément notée ou${\displaystyle \operatorname {res} (A,B)}$${\displaystyle \operatorname {Res} (A,B).}$

Dans de nombreuses applications de la résultante, les polynômes dépendent de plusieurs indéterminés et peuvent être considérés comme des polynômes univariés dans l'un de leurs indéterminés, avec des polynômes dans les autres indéterminés comme coefficients. Dans ce cas, l'indéterminé retenu pour définir et calculer la résultante est indiqué en indice : ou${\displaystyle \operatorname {res} _{x}(A,B)}$${\displaystyle \operatorname {Res} _{x}(A,B).}$

Les degrés des polynômes sont utilisés dans la définition de la résultante. Cependant, un polynôme de degré d peut également être considéré comme un polynôme de degré supérieur où les coefficients dominants sont nuls. Si un tel degré plus élevé est utilisé pour le résultat, il est généralement indiqué comme un indice ou un exposant, tel que ou${\displaystyle \operatorname {res} _{d,e}(A,B)}$${\displaystyle \operatorname {res} _{x}^{d,e}(A,B).}$

Définition

La résultante de deux polynômes univariés sur un corps ou sur un anneau commutatif est communément définie comme le déterminant de leur matrice de Sylvester . Plus précisément, laissez

${\displaystyle A=a_{0}x^{d}+a_{1}x^{d-1}+\cdots +a_{d}}$

et

${\displaystyle B=b_{0}x^{e}+b_{1}x^{e-1}+\cdots +b_{e}}$

être des polynômes non nuls de degrés d et e respectivement. Désignons par l' espace vectoriel (ou module libre si les coefficients appartiennent à un anneau commutatif) de dimension i dont les éléments sont les polynômes de degré strictement inférieur à i . La carte ${\displaystyle {\mathcal {P}}_{i}}$

${\displaystyle \varphi :{\mathcal {P}}_{e}\times {\mathcal {P}}_{d}\rightarrow {\mathcal {P}}_{d+e}}$

tel que

${\displaystyle \varphi (P,Q)=AP+BQ}$

est une application linéaire entre deux espaces de même dimension. Sur la base des puissances de x (classées par ordre décroissant), cette carte est représentée par une matrice carrée de dimension d + e , qui est appelée matrice de Sylvester de A et B (pour de nombreux auteurs et dans l'article Matrice de Sylvester , la matrice de Sylvester est définie comme la transposée de cette matrice ; cette convention n'est pas utilisée ici, car elle rompt avec la convention habituelle d'écriture de la matrice d'une application linéaire).

La résultante de A et B est donc le déterminant

${\displaystyle {\begin{vmatrix}a_{0}&0&\cdots &0&b_{0}&0&\cdots &0\\a_{1}&a_{0}&\cdots &0&b_{1}&b_{0}&\cdots &0\ \a_{2}&a_{1}&\ddots &0&b_{2}&b_{1}&\ddots &0\\\vdots &\vdots &\ddots &a_{0}&\vdots &\vdots &\ddots &b_{0 }\\a_{d}&a_{d-1}&\cdots &\vdots &b_{e}&b_{e-1}&\cdots &\vdots \\0&a_{d}&\ddots &\vdots &0&b_{e }&\ddots &\vdots \\\vdots &\vdots &\ddots &a_{d-1}&\vdots &\vdots &\ddots &b_{e-1}\\0&0&\cdots &a_{d}&0&0&\cdots &b_{e}\end{vmatrix}},}$

qui a e colonnes de a _i et d colonnes de b _j (le fait que la première colonne de a et la première colonne de b aient la même longueur, c'est-à-dire d = e , n'est ici que pour simplifier l'affichage du déterminant). Par exemple, en prenant d = 3 et e = 2, nous obtenons

${\displaystyle {\begin{vmatrix}a_{0}&0&b_{0}&0&0\\a_{1}&a_{0}&b_{1}&b_{0}&0\\a_{2}&a_{1}&b_{2 }&b_{1}&b_{0}\\a_{3}&a_{2}&0&b_{2}&b_{1}\\0&a_{3}&0&0&b_{2}\end{vmatrix}}.}$

Si les coefficients des polynômes appartiennent à un domaine intégral , alors

${\displaystyle \operatorname {res} (A,B)=a_{0}^{e}b_{0}^{d}\prod _{\begin{array}{c}1\leq i\leq d\ \1\leq j\leq e\end{array}}(\lambda _{i}-\mu _{j})=a_{0}^{e}\prod _{i=1}^{d} B(\lambda _{i})=(-1)^{de}b_{0}^{d}\prod _{j=1}^{e}A(\mu _{j}),}$

où et sont respectivement les racines, comptées avec leurs multiplicités, de A et B dans tout corps algébriquement clos contenant le domaine intégral. Ceci est une conséquence directe des propriétés caractérisantes de la résultante qui apparaissent ci-dessous. Dans le cas courant des coefficients entiers, le corps algébriquement clos est généralement choisi comme corps des nombres complexes . ${\displaystyle \lambda _{1},\dots ,\lambda _{d}}$${\displaystyle \mu _{1},\dots ,\mu _{e}}$

Propriétés

Dans cette section et ses sous-sections, A et B sont deux polynômes en x de degrés respectifs d et e , et leur résultante est notée ${\displaystyle \operatorname {res} (A,B).}$

Propriétés caractéristiques

La résultante de deux polynômes A et B de degrés respectifs d et e , à coefficients dans un anneau commutatif R , a les propriétés suivantes qui caractérisent la résultante, si R est un corps ou, plus généralement, un domaine intégral

• Si R est un sous - anneau d'un autre anneau S , alors que est A et B ont la même résultante lorsqu'elle est considérée comme polynômes sur R ou S .${\displaystyle \operatorname {res} _{R}(A,B)=\operatorname {res} _{S}(A,B).}$
• Si d = 0 (c'est-à-dire si est une constante non nulle) alors De même, si e = 0 , alors${\style d'affichage A=a_{0}}$${\displaystyle \operatorname {res} (A,B)=a_{0}^{e}.}$${\displaystyle \operatorname {res} (A,B)=b_{0}^{d}.}$
• ${\displaystyle \operatorname {res} (x+a_{1},x+b_{1})=b_{1}-a_{1}}$
• ${\displaystyle \operatorname {res} (B,A)=(-1)^{de}\operatorname {res} (A,B)}$
• ${\displaystyle \operatorname {res} (AB,C)=\operatorname {res} (A,C)\operatorname {res} (B,C)}$

En d'autres termes, la résultante est l'unique fonction des coefficients de deux polynômes qui possède ces propriétés.

Zéros

• La résultante de deux polynômes à coefficients dans un domaine intégral est nulle si et seulement s'ils ont un diviseur commun de degré positif.
• La résultante de deux polynômes à coefficients dans un domaine intégral est nulle si et seulement s'ils ont une racine commune dans un corps algébriquement clos contenant les coefficients.
• Il existe un polynôme P de degré inférieur à e et un polynôme Q de degré inférieur à d tels que Ceci est une généralisation de l'identité de Bézout aux polynômes sur un anneau commutatif arbitraire. Autrement dit, la résultante de deux polynômes appartient à l' idéal engendré par ces polynômes.${\displaystyle \operatorname {res} (A,B)=AP+BQ.}$

Invariance par homomorphismes d'anneaux

Soient A et B deux polynômes de degrés respectifs d et e avec des coefficients dans un anneau commutatif R , et un homomorphisme d'anneau de R dans un autre anneau commutatif S . L'application aux coefficients d'un polynôme s'étend à un homomorphisme d'anneaux polynomiaux , que l'on note aussi Avec cette notation, on a : ${\displaystyle \varphi \colon R\to S}$${\style d'affichage \varphi }$${\style d'affichage \varphi }$${\style d'affichage R[x]\à S[x]}$${\displaystyle \varphi .}$

• Si préserve les degrés de A et B (c'est-à-dire si et ), alors${\style d'affichage \varphi }$${\displaystyle \deg(\varphi (A))=d}$${\displaystyle \deg(\varphi (B))=e}$

${\displaystyle \varphi (\operatorname {res} (A,B))=\operatorname {res} (\varphi (A),\varphi (B)).}$

• Si et alors${\displaystyle \deg(\varphi (A))<d}$${\displaystyle \deg(\varphi (B))<e,}$

${\displaystyle \varphi (\operatorname {res} (A,B))=0.}$

• Si et et le coefficient dominant de A est alors${\displaystyle \deg(\varphi (A))=d}$${\displaystyle \deg(\varphi (B))=f<e,}$${\style d'affichage a_{0}}$

${\displaystyle \varphi (\operatorname {res} (A,B))=\varphi (a_{0})^{ef}\operatorname {res} (\varphi (A),\varphi (B)).}$

• Si et et le coefficient dominant de B est alors${\displaystyle \deg(\varphi (A))=f<d}$${\displaystyle \deg(\varphi (B))=e,}$${\style d'affichage b_{0}}$

${\displaystyle \varphi (\operatorname {res} (A,B))=(-1)^{e(df)}\varphi (b_{0})^{df}\operatorname {res} (\varphi ( A),\varphi (B)).}$

Ces propriétés se déduisent facilement de la définition de la résultante en tant que déterminant. Ils sont principalement utilisés dans deux situations. Pour calculer une résultante de polynômes à coefficients entiers, il est généralement plus rapide de la calculer modulo plusieurs nombres premiers et de récupérer la résultante souhaitée avec le théorème des restes chinois . Lorsque R est un anneau polynomial dans d'autres indéterminés, et S est l'anneau obtenu en spécialisant en valeurs numériques certains ou tous les indéterminés de R , ces propriétés peuvent être reformulées comme si les degrés étaient conservés par la spécialisation, la résultante de la spécialisation de deux polynômes est la spécialisation de la résultante . Cette propriété est fondamentale, par exemple, pour la décomposition algébrique cylindrique .

Invariance sous changement de variable

• ${\displaystyle \operatorname {res} (A(x+a),B(x+a))=\operatorname {res} (A(x),B(x))}$
• ${\displaystyle \operatorname {res} (A(ax),B(ax))=a^{de}\operatorname {res} (A(x),B(x))}$
• Si et sont les polynômes réciproques de A et B , respectivement, alors${\style d'affichage A_{r}(x)=x^{d}A(1/x)}$${\style d'affichage B_{r}(x)=x^{e}B(1/x)}$

${\displaystyle \operatorname {res} (A_{r},B_{r})=(-1)^{de}\operatorname {res} (A,B)}$

Cela signifie que la propriété de la résultante étant zéro est invariante sous les changements linéaires et projectifs de la variable.

Invariance sous changement de polynômes

• Si a et b sont des constantes non nulles (c'est-à-dire qu'elles sont indépendantes de l'indéterminé x ), et A et B sont comme ci-dessus, alors

${\displaystyle \operatorname {res} (aA,bB)=a^{e}b^{d}\operatorname {res} (A,B).}$

• Si A et B sont comme ci - dessus, et C est un autre polynôme tel que le degré de A - CB est δ , alors

${\displaystyle \operatorname {res} (A-CB,B)=b_{0}^{\delta -d}\operatorname {res} (A,B).}$

• En particulier, si B est monique , ou deg C < deg A – deg B , alors

${\displaystyle \operatorname {res} (A-CB,B)=\operatorname {res} (A,B),}$

et, si f = deg C > deg A – deg B = d – e , alors

${\displaystyle \operatorname {res} (A-CB,B)=b_{0}^{e+fd}\operatorname {res} (A,B).}$

Ces propriétés impliquent que dans l' algorithme d'Euclide des polynômes , et toutes ses variantes ( séquences pseudo-restes ), la résultante de deux restes successifs (ou pseudo-restes) diffère de la résultante des polynômes initiaux par un facteur facile à calculer . A l'inverse, cela permet de déduire la résultante des polynômes initiaux de la valeur du dernier reste ou pseudo-reste. C'est l'idée de départ de l' algorithme sous-résultant-pseudo-reste-séquence , qui utilise les formules ci-dessus pour obtenir des polynômes sous-résultants en tant que pseudo-restes, et le résultat en tant que dernier pseudo-reste non nul (à condition que le résultat ne soit pas nul). Cet algorithme fonctionne pour des polynômes sur des entiers ou, plus généralement, sur un domaine intégral, sans aucune division autre que des divisions exactes (c'est-à-dire sans faire intervenir de fractions). Il implique des opérations arithmétiques, tandis que le calcul du déterminant de la matrice de Sylvester avec des algorithmes standards nécessite des opérations arithmétiques. ${\style d'affichage O(de)}$${\style d'affichage O((d+e)^{3})}$

Propriétés génériques

Dans cette section, nous considérons deux polynômes

${\displaystyle A=a_{0}x^{d}+a_{1}x^{d-1}+\cdots +a_{d}}$

et

${\displaystyle B=b_{0}x^{e}+b_{1}x^{e-1}+\cdots +b_{e}}$

dont d + e + 2 coefficients sont des indéterminés distincts . Laisser

${\displaystyle R=\mathbb {Z} [a_{0},\ldots ,a_{d},b_{0},\ldots ,b_{e}]}$

être l'anneau polynomial sur les entiers définis par ces indéterminés. La résultante est souvent appelée la résultante générique pour les degrés d et e . Il a les propriétés suivantes. ${\displaystyle \operatorname {res} (A,B)}$

• ${\displaystyle \operatorname {res} (A,B)}$est un polynôme absolument irréductible .
• Si est l' idéal de généré par A et B , alors est l' idéal principal généré par .${\style d'affichage I}$${\style d'affichage R[x]}$${\displaystyle I\cap R}$${\displaystyle \operatorname {res} (A,B)}$

Homogénéité

La résultante générique pour les degrés d et e est homogène de diverses manières. Plus précisément:

• Il est homogène de degré e en${\displaystyle a_{0},\ldots ,a_{d}.}$
• Il est homogène de degré d en${\displaystyle b_{0},\ldots ,b_{e}.}$
• Il est homogène de degré d + e dans toutes les variables et${\style d'affichage a_{i}}$${\style d'affichage b_{j}.}$
• Si et sont donnés le poids i (c'est-à-dire que le poids de chaque coefficient est son degré en tant que polynôme symétrique élémentaire ), alors il est quasi-homogène du poids total de .${\style d'affichage a_{i}}$${\style d'affichage b_{i}}$
• Si P et Q sont des polynômes multivariés homogènes de degrés respectifs d et e , alors leur résultante en degrés d et e par rapport à un indéterminé x , noté en § Notation , est homogène de degré de dans les autres indéterminés.${\displaystyle \operatorname {res} _{x}^{d,e}(P,Q)}$

Propriété d'élimination

∗Soit l' idéal engendré par deux polynômes A et B dans un anneau polynomial où est lui-même un anneau polynomial sur un corps. Si au moins l'un de A et B est unitaire dans x , alors : ${\displaystyle I=\langle A,B\rangle }$${\style d'affichage R[x],}$${\displaystyle R=k[y_{1},\ldots ,y_{n}]}$

• ${\displaystyle \operatorname {res} _{x}(A,B)\in I\cap R}$
• Les idéaux et définissent le même ensemble algébrique . C'est-à-dire qu'un n tuple d'éléments d'un corps algébriquement clos est un zéro commun des éléments de si et seulement c'est un zéro de${\displaystyle I\cap R}$${\displaystyle R\operatorname {res} _{x}(A,B)}$${\displaystyle I\cap R}$${\displaystyle \operatorname {res} _{x}(A,B).}$
• L'idéal a le même radical que l' idéal principal C'est-à-dire que chaque élément de a une puissance qui est un multiple de${\displaystyle I\cap R}$ ${\displaystyle R\operatorname {res} _{x}(A,B).}$${\displaystyle I\cap R}$${\displaystyle \operatorname {res} _{x}(A,B).}$
• Tous les facteurs irréductibles de diviser chaque élément de${\displaystyle \operatorname {res} _{x}(A,B)}$${\displaystyle I\cap R.}$

La première assertion est une propriété de base de la résultante. Les autres affirmations sont des corollaires immédiats de la seconde, qui peuvent être prouvées comme suit.

Comme au moins l'un de A et B est unitaire, un n tuple est un zéro de si et seulement s'il existe tel qui est un zéro commun de A et B . Un tel zéro commun est aussi un zéro de tous les éléments de Inversement, si est un zéro commun des éléments de c'est un zéro de la résultante, et il existe tel qui est un zéro commun de A et B . Donc et ont exactement les mêmes zéros. ${\displaystyle (\beta _{1},\ldots ,\beta _{n})}$${\displaystyle \operatorname {res} _{x}(A,B)}$${\style d'affichage \alpha }$${\displaystyle (\beta _{1},\ldots ,\beta _{n},\alpha )}$${\displaystyle I\cap R.}$${\displaystyle (\beta _{1},\ldots ,\beta _{n},\alpha )}$${\displaystyle I\cap R,}$${\style d'affichage \alpha }$${\displaystyle (\beta _{1},\ldots ,\beta _{n},\alpha )}$${\displaystyle I\cap R}$${\displaystyle R\operatorname {res} _{x}(A,B)}$

Calcul

Théoriquement, le résultat pourrait être calculé en utilisant la formule l'exprimant comme un produit des différences de racines. Cependant, comme les racines peuvent généralement ne pas être calculées exactement, un tel algorithme serait inefficace et numériquement instable . Comme le résultat est une fonction symétrique des racines de chaque polynôme, il pourrait également être calculé en utilisant le théorème fondamental des polynômes symétriques , mais ce serait très inefficace.

Comme la résultante est le déterminant de la matrice de Sylvester (et de la matrice de Bézout ), elle peut être calculée en utilisant n'importe quel algorithme de calcul des déterminants. Cela nécessite des opérations arithmétiques. Comme les algorithmes sont connus avec une meilleure complexité (voir ci-dessous), cette méthode n'est pas utilisée en pratique. ${\style d'affichage O(n^{3})}$

Il résulte du § Invariance sous changement de polynômes que le calcul d'une résultante est fortement lié à l' algorithme d'Euclide pour les polynômes . Ceci montre que le calcul de la résultante de deux polynômes de degrés d et e peut se faire dans des opérations arithmétiques dans le domaine des coefficients. ${\style d'affichage O(de)}$

Cependant, lorsque les coefficients sont des entiers, des nombres rationnels ou des polynômes, ces opérations arithmétiques impliquent un nombre de calculs PGCD de coefficients qui est du même ordre et rendent l'algorithme inefficace. Les séquences pseudo-restes sous-résultantes ont été introduites pour résoudre ce problème et éviter toute fraction et tout calcul PGCD de coefficients. Un algorithme plus efficace est obtenu en utilisant le bon comportement de la résultante sous un homomorphisme d'anneau sur les coefficients : pour calculer une résultante de deux polynômes à coefficients entiers, on calcule leurs résultantes modulo suffisamment de nombres premiers puis reconstruit le résultat avec le chinois théorème des restes .

L'utilisation de la multiplication rapide d'entiers et de polynômes permet des algorithmes pour les résultantes et les plus grands diviseurs communs qui ont une meilleure complexité temporelle , qui est de l'ordre de la complexité de la multiplication, multipliée par le logarithme de la taille de l'entrée ( où s est une limite supérieure du nombre de chiffres des polynômes d'entrée). ${\displaystyle \log(s(d+e)),}$

Application aux systèmes polynomiaux

Les résultats ont été introduits pour résoudre des systèmes d'équations polynomiales et fournissent la preuve la plus ancienne qu'il existe des algorithmes pour résoudre de tels systèmes. Ceux-ci sont principalement destinés aux systèmes de deux équations à deux inconnues, mais permettent également de résoudre des systèmes généraux.

Cas de deux équations à deux inconnues

Considérons le système de deux équations polynomiales

${\displaystyle {\begin{aligned}P(x,y)&=0\\Q(x,y)&=0,\end{aligned}}}$

où P et Q sont des polynômes de degrés totaux respectifs d et e . Alors est un polynôme en x , qui est génériquement de degré de (par propriétés de § Homogénéité ). Une valeur de x est une racine de R si et seulement si soit il existe dans un corps algébriquement clos contenant les coefficients, tels que , soit et (dans ce cas, on dit que P et Q ont une racine commune à l'infini pour ). ${\displaystyle R=\operatorname {res} _{y}^{d,e}(P,Q)}$${\style d'affichage \alpha }$${\displaystyle \beta }$${\style d'affichage P(\alpha ,\beta )=Q(\alpha ,\beta )=0}$${\displaystyle \deg(P(\alpha ,y))<d}$${\displaystyle \deg(Q(\alpha ,y))<e}$${\style d'affichage x=\alpha }$

Par conséquent, les solutions du système sont obtenues en calculant les racines de R , et pour chaque racine en calculant la ou les racines communes de et${\style d'affichage \alpha ,}$${\style d'affichage P(\alpha ,y),}$ ${\style d'affichage Q(\alpha ,y),}$${\displaystyle \operatorname {res} _{x}(P,Q).}$

Le théorème de Bézout résulte de la valeur de , le produit des degrés de P et Q . En effet, après un changement linéaire de variables, on peut supposer que, pour chaque racine x de la résultante, il existe exactement une valeur de y telle que ( x , y ) soit un zéro commun de P et Q . Ceci montre que le nombre de zéros communs est au plus le degré de la résultante, c'est-à-dire au plus le produit des degrés de P et Q . Avec quelques détails techniques, cette preuve peut être étendue pour montrer que, en comptant les multiplicités et les zéros à l'infini, le nombre de zéros est exactement le produit des degrés. ${\displaystyle \deg \left(\operatorname {res} _{y}(P,Q)\right)\leq de}$

Cas général

À première vue, il semble que les résultantes peuvent être appliquées à un système polynomial général d'équations

${\style d'affichage P_{1}(x_{1},\ldots ,x_{n})=0}$

${\style d'affichage \vdots }$

${\displaystyle P_{k}(x_{1},\ldots ,x_{n})=0}$

en calculant les résultantes de chaque paire par rapport à pour éliminer une inconnue, et en répétant le processus jusqu'à obtenir des polynômes univariés. Malheureusement, cela introduit de nombreuses solutions parasites, qui sont difficiles à éliminer. ${\style d'affichage (P_{i},P_{j})}$${\style d'affichage x_{n}}$

Une méthode, introduite à la fin du 19ème siècle, fonctionne comme suit : introduire k − 1 nouveaux indéterminés et calculer ${\displaystyle U_{2},\ldots ,U_{k}}$

${\displaystyle \operatorname {res} _{x_{n}}(P_{1},U_{2}P_{2}+\cdots +U_{k}P_{k}).}$

Il s'agit d'un polynôme dont les coefficients sont des polynômes dans lesquels ont la propriété d' être un zéro commun à ces coefficients polynomiaux, si et seulement si les polynômes univariés ont un zéro commun, éventuellement à l'infini . Ce processus peut être itéré jusqu'à trouver des polynômes univariés. ${\displaystyle U_{2},\ldots ,U_{k}}$${\displaystyle x_{1},\ldots ,x_{n-1},}$${\displaystyle \alpha _{1},\ldots ,\alpha _{n-1}}$${\displaystyle P_{i}(\alpha _{1},\ldots ,\alpha _{n-1},x_{n})}$

Pour obtenir un algorithme correct, deux compléments doivent être ajoutés à la méthode. Premièrement, à chaque étape, un changement linéaire de variable peut être nécessaire afin que les degrés des polynômes dans la dernière variable soient les mêmes que leur degré total. Deuxièmement, si, à n'importe quelle étape, la résultante est nulle, cela signifie que les polynômes ont un facteur commun et que les solutions se séparent en deux composantes : l'une où le facteur commun est nul, et l'autre qui est obtenue en factorisant ce commun facteur avant de continuer.

Cet algorithme est très compliqué et a une complexité temporelle énorme . Son intérêt est donc principalement historique.

Autres applications

La théorie du nombre

Le discriminant d'un polynôme, qui est un outil fondamental en théorie des nombres, est le quotient par son coefficient dominant de la résultante du polynôme et de sa dérivée.

Si et sont des nombres algébriques tels que , alors est une racine de la résultante et est une racine de , où est le degré de . Combiné avec le fait que c'est une racine de , cela montre que l'ensemble des nombres algébriques est un corps . ${\style d'affichage \alpha }$${\displaystyle \beta }$${\style d'affichage P(\alpha )=Q(\beta )=0}$${\displaystyle \gamma =\alpha +\beta }$${\displaystyle \operatorname {res} _{x}(P(x),Q(zx)),}$${\displaystyle \tau =\alpha \beta }$${\displaystyle \operatorname {res} _{x}(P(x),x^{n}Q(z/x))}$${\style d'affichage n}$${\style d'affichage Q(y)}$${\style d'affichage 1/\beta }$${\style d'affichage y^{n}Q(1/y)=0}$

Soit une extension de champ algébrique générée par un élément qui a pour polynôme minimal . Chaque élément de peut être écrit comme où est un polynôme. Alors est une racine de et cette résultante est une puissance du polynôme minimal de${\style d'affichage K(\alpha )}$${\style d'affichage \alpha ,}$${\style d'affichage P(x)}$${\displaystyle \beta \in K(\alpha )}$${\displaystyle \beta =Q(\alpha ),}$${\style d'affichage Q}$${\displaystyle \beta }$${\displaystyle \operatorname {res} _{x}(P(x),zQ(x)),}$${\displaystyle \beta .}$

Géométrie algébrique

Étant donné deux courbes algébriques planes définies comme les zéros des polynômes P ( x , y ) et Q ( x , y ) , la résultante permet le calcul de leur intersection. Plus précisément, les racines de sont les coordonnées x des points d'intersection et des asymptotes verticales communes, et les racines de sont les coordonnées y des points d'intersection et des asymptotes horizontales communes. ${\displaystyle \operatorname {res} _{y}(P,Q)}$${\displaystyle \operatorname {res} _{x}(P,Q)}$

Une courbe plane rationnelle peut être définie par une équation paramétrique

${\displaystyle x={\frac {P(t)}{R(t)}},\qquad y={\frac {Q(t)}{R(t)}},}$

où P , Q et R sont des polynômes. Une équation implicite de la courbe est donnée par

${\displaystyle \operatorname {res} _{t}(xR-P,yR-Q).}$

Le degré de cette courbe est le degré le plus élevé de P , Q et R , qui est égal au degré total de la résultante.

Intégration symbolique

En intégration symbolique , pour calculer la primitive d'une fraction rationnelle , on utilise la décomposition en fractions partielles pour décomposer l'intégrale en une "partie rationnelle", qui est une somme de fractions rationnelles dont les antiprimitives sont des fractions rationnelles, et une "partie logarithmique" qui est une somme de fractions rationnelles de la forme

${\style d'affichage {\frac {P(x)}{Q(x)}},}$

où Q est un polynôme sans carré et P est un polynôme de degré inférieur à Q . La primitive d'une telle fonction fait nécessairement intervenir des logarithmes , et généralement des nombres algébriques (les racines de Q ). En fait, la primitive est

${\displaystyle \int {\frac {P(x)}{Q(x)}}dx=\sum _{Q(\alpha )=0}{\frac {P(\alpha )}{Q'(\ alpha )}}\log(x-\alpha ),}$

où la somme parcourt toutes les racines complexes de Q .

Le nombre de nombres algébriques impliqués par cette expression est généralement égal au degré de Q , mais il arrive fréquemment qu'une expression avec moins de nombres algébriques puisse être calculée. La méthode de Lazard – Rioboo – Trager a produit une expression, où le nombre de nombres algébriques est minimal, sans aucun calcul avec des nombres algébriques.

Laisser

${\displaystyle S_{1}(r)S_{2}(r)^{2}\cdots S_{k}(r)^{k}=\operatorname {res} _{r}(rQ'(x) -P(x),Q(x))}$

être la factorisation sans carré de la résultante qui apparaît à droite. Trager a prouvé que la primitive est

${\displaystyle \int {\frac {P(x)}{Q(x)}}dx=\sum _{i=1}^{k}\sum _{S_{i}(\alpha )=0} \alpha \log(T_{i}(\alpha ,x)),}$

où les sommes internes courent sur les racines du (si la somme est nulle, comme étant la somme vide ), et est un polynôme de degré i en x . La contribution de Lazard-Rioboo est la preuve qui est la sous- résultante de degré i de et Elle est donc obtenue gratuitement si la résultante est calculée par la pseudo-suite sous- résultante . ${\style d'affichage S_{i}}$${\style d'affichage S_{i}=1}$${\style d'affichage T_{i}(r,x)}$${\style d'affichage T_{i}(r,x)}$${\style d'affichage rQ'(x)-P(x)}$${\style d'affichage Q(x).}$

Calcul formel

Toutes les applications précédentes, et bien d'autres, montrent que la résultante est un outil fondamental en calcul formel . En fait, la plupart des systèmes de calcul formel incluent une implémentation efficace du calcul des résultantes.

résultante homogène

La résultante est également définie pour deux polynômes homogènes à deux indéterminés. Étant donné deux polynômes homogènes P ( x , y ) et Q ( x , y ) de degrés totaux respectifs p et q , leur résultante homogène est le déterminant de la matrice sur la base monôme de l'application linéaire

${\style d'affichage (A,B)\mapsto AP+BQ,}$

où A parcourt les polynômes homogènes bivariés de degré q − 1 , et B parcourt les polynômes homogènes de degré p − 1 . Autrement dit, la résultante homogène de P et Q est la résultante de P ( x , 1) et Q ( x , 1) lorsqu'on les considère comme des polynômes de degré p et q (leur degré en x peut être inférieur à leur total degré):

${\displaystyle \operatorname {Res} (P(x,y),Q(x,y))=\operatorname {res} _{p,q}(P(x,1),Q(x,1)) .}$

(La majuscule de "Res" est utilisée ici pour distinguer les deux résultantes, bien qu'il n'y ait pas de règle standard pour la majuscule de l'abréviation).

La résultante homogène a essentiellement les mêmes propriétés que la résultante habituelle, avec essentiellement deux différences : au lieu de racines polynomiales, on considère des zéros dans la ligne projective , et le degré d'un polynôme ne peut pas changer sous un homomorphisme d'anneau . C'est-à-dire:

• La résultante de deux polynômes homogènes sur un domaine intégral est nulle si et seulement si ils ont un zéro commun non nul sur un corps algébriquement clos contenant les coefficients.
• Si P et Q sont deux polynômes homogènes bivariés avec des coefficients dans un anneau commutatif R , et un homomorphisme d'anneau de R dans un autre anneau commutatif S , puis s'étendant aux polynômes sur R , on a${\displaystyle \varphi \colon R\to S}$${\style d'affichage \varphi }$

${\displaystyle \operatorname {Res} (\varphi (P),\varphi (Q))=\varphi (\operatorname {Res} (P,Q)).}$

• La propriété d'une résultante homogène d'être nulle est invariante sous tout changement projectif de variables.

Toute propriété de la résultante habituelle peut être étendue de la même manière à la résultante homogène, et la propriété résultante est soit très similaire, soit plus simple que la propriété correspondante de la résultante habituelle.

résultante de Macaulay

La résultante de Macaulay , du nom de Francis Sowerby Macaulay , également appelée la résultante multivariée , ou la résultante multipolynomiale , est une généralisation de la résultante homogène à n polynômes homogènes à n indéterminés . La résultante de Macaulay est un polynôme aux coefficients de ces n polynômes homogènes qui s'annule si et seulement si les polynômes ont une solution commune non nulle dans un corps algébriquement clos contenant les coefficients, ou, de manière équivalente, si les n hyper surfaces définies par les polynômes ont un zéro commun dans l' espace projectif de dimension n- 1 . La résultante multivariée est, avec les bases de Gröbner , l'un des principaux outils de la théorie de l'élimination effective (théorie de l'élimination sur ordinateur).

Comme la résultante homogène, celle de Macaulay peut être définie avec des déterminants , et se comporte donc bien sous les homomorphismes d'anneaux . Cependant, il ne peut pas être défini par un seul déterminant. Il s'ensuit qu'il est plus facile de le définir d'abord sur des polynômes génériques .

Résultant de polynômes homogènes génériques

Un polynôme homogène de degré d en n variables peut avoir jusqu'à

${\displaystyle {\binom {n+d-1}{n-1}}={\frac {(n+d-1)!}{(n-1)!\,d!}}}$

coefficients; il est dit générique , si ces coefficients sont des indéterminés distincts.

Laissez - être n polynômes homogènes génériques n indéterminés, des respectifs degrés Ensemble, ils impliquent ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle d_{1},\dots ,d_{n}.}$

${\displaystyle \sum _{i=1}^{n}{\binom {n+d_{i}-1}{n-1}}}$

coefficients indéterminés. Soit C l'anneau polynomial sur les entiers, dans tous ces coefficients indéterminés. Les polynômes appartiennent donc à et leur résultante (encore à définir) appartient à C . ${\displaystyle P_{1},\ldots ,P_{n}}$${\displaystyle C[x_{1},\ldots ,x_{n}],}$

Le degré de Macaulay est l'entier fondamental dans la théorie de Macaulay. Pour définir la résultante, on considère la matrice de Macaulay , qui est la matrice sur la base monôme de la carte C -linéaire ${\displaystyle D=d_{1}+\cdots +d_{n}-n+1,}$

${\displaystyle (Q_{1},\ldots ,Q_{n})\mapsto Q_{1}P_{1}+\cdots +Q_{n}P_{n},}$

dans laquelle chacun parcourt les polynômes homogènes de degré et le codomaine est le C -module des polynômes homogènes de degré D . ${\displaystyle Q_{i}}$${\displaystyle D-d_{i},}$

Si n = 2 , la matrice de Macaulay est la matrice de Sylvester, et est une matrice carrée , mais ce n'est plus vrai pour n > 2 . Ainsi, au lieu de considérer le déterminant, on considère tous les mineurs maximaux , c'est-à-dire les déterminants des sous-matrices carrées qui ont autant de lignes que la matrice de Macaulay. Macaulay a prouvé que l' idéal C généré par ces mineurs principaux est un idéal principal , qui est généré par le plus grand diviseur commun de ces mineurs. Comme on travaille avec des polynômes à coefficients entiers, ce plus grand commun diviseur est défini à son signe près. La résultante générique de Macaulay est le plus grand diviseur commun qui devient 1 , lorsque, pour chaque i , zéro est substitué à tous les coefficients de sauf le coefficient de auquel un est substitué. ${\style d'affichage P_{i},}$${\displaystyle x_{i}^{d_{i}},}$

Propriétés de la résultante générique de Macaulay

• La résultante générique de Macaulay est un polynôme irréductible .
• Elle est homogène de degré dans les coefficients d' où est la borne de Bézout .${\displaystyle B/d_{i}}$${\style d'affichage P_{i},}$${\displaystyle B=d_{1}\cdots d_{n}}$
• Le produit avec la résultante de chaque monôme de degré D en appartient à l'idéal de généré par${\displaystyle x_{1},\dots ,x_{n}}$${\displaystyle C[x_{1},\dots ,x_{n}]}$${\displaystyle P_{1},\dots ,P_{n}.}$

Résultant de polynômes sur un corps

Désormais, on considère que les polynômes homogènes de degrés ont leurs coefficients dans un corps k , c'est-à-dire qu'ils appartiennent à leur résultante est définie comme l'élément de k obtenu en remplaçant dans la résultante générique les coefficients indéterminés par les coefficients réels de les${\displaystyle P_{1},\ldots ,P_{n}}$${\displaystyle d_{1},\ldots ,d_{n}}$ ${\displaystyle k[x_{1},\dots ,x_{n}].}$${\style d'affichage P_{i}.}$

La propriété principale de la résultante est qu'elle est nulle si et seulement si a un zéro commun non nul dans une extension algébriquement fermée de k . ${\displaystyle P_{1},\ldots ,P_{n}}$

La partie "seulement si" de ce théorème résulte de la dernière propriété du paragraphe précédent, et est une version effective de Projective Nullstellensatz : Si la résultante est non nulle, alors

${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle ^{D}\subseteq \langle P_{1},\ldots ,P_{n}\rangle ,}$

où est le degré de Macaulay, et est l'idéal homogène maximal. Cela implique qu'il n'y a pas d'autre zéro commun que l'unique zéro commun, (0, ..., 0) , de${\displaystyle D=d_{1}+\cdots +d_{n}-n+1}$${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle }$${\displaystyle P_{1},\ldots ,P_{n}}$${\displaystyle x_{1},\ldots ,x_{n}.}$

Calculabilité

Comme le calcul d'une résultante peut être réduit au calcul des déterminants et des plus grands diviseurs communs polynomiaux , il existe des algorithmes pour calculer les résultantes en un nombre fini d'étapes.

Cependant, la résultante générique est un polynôme de très haut degré (exponentiel en n ) dépendant d'un très grand nombre d'indéterminés. Il s'ensuit que, sauf pour de très petits n et de très petits degrés de polynômes d'entrée, la résultante générique est, en pratique, impossible à calculer, même avec des ordinateurs modernes. De plus, le nombre de monômes de la résultante générique est si élevé que, s'il était calculable, le résultat ne pourrait pas être stocké sur les dispositifs de mémoire disponibles, même pour des valeurs assez petites de n et des degrés des polynômes d'entrée.

Par conséquent, le calcul de la résultante n'a de sens que pour les polynômes dont les coefficients appartiennent à un champ ou sont des polynômes en quelques indéterminés sur un champ.

Dans le cas de polynômes d'entrée à coefficients dans un champ, la valeur exacte de la résultante est rarement importante, seule son égalité (ou non) à zéro compte. Comme la résultante est nulle si et seulement si le rang de la matrice de Macaulay est inférieur à son nombre de ses lignes, cette égalité à zéro peut être testée en appliquant l'élimination de Gauss à la matrice de Macaulay. Cela fournit une complexité de calcul où d est le degré maximum de polynômes d'entrée. ${\style d'affichage d^{O(n)},}$

Un autre cas où le calcul de la résultante peut fournir des informations utiles est lorsque les coefficients des polynômes d'entrée sont des polynômes dans un petit nombre d'indéterminés, souvent appelés paramètres. Dans ce cas, la résultante, sinon nulle, définit une hypersurface dans l'espace des paramètres. Un point appartient à cette hypersurface, si et seulement s'il existe des valeurs dont, avec les coordonnées du point, sont un zéro des polynômes d'entrée. En d'autres termes, la résultante est le résultat de l'" élimination " des polynômes d'entrée. ${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{1},\ldots ,x_{n}}$

U -résultant

La résultante de Macaulay fournit une méthode, appelée " U -résultante " par Macaulay, pour résoudre des systèmes d'équations polynomiales .

Etant donné n − 1 polynômes homogènes de degrés en n indéterminés sur un corps k , leur U -résultante est la résultante des n polynômes où ${\displaystyle P_{1},\ldots ,P_{n-1},}$${\displaystyle d_{1},\ldots ,d_{n-1},}$${\displaystyle x_{1},\ldots ,x_{n},}$${\displaystyle P_{1},\ldots ,P_{n-1},P_{n},}$

${\displaystyle P_{n}=u_{1}x_{1}+\cdots +u_{n}x_{n}}$

est la forme linéaire générique dont les coefficients sont de nouvelles indéterminées La notation ou pour ces coefficients génériques est classique, et est à l'origine du terme U -résultant. ${\displaystyle u_{1},\ldots ,u_{n}.}$${\style d'affichage u_{i}}$${\displaystyle U_{i}}$

La résultante U est un polynôme homogène dans It est nul si et seulement si les zéros communs de forment un ensemble algébrique projectif de dimension positive (c'est-à-dire qu'il y a une infinité de zéros projectifs sur une extension algébriquement fermée de k ). Si la résultante U n'est pas nulle, son degré est la borne de Bézout. La résultante U se factorise sur une extension algébriquement fermée de k en un produit de formes linéaires. Si est un tel facteur linéaire, alors sont les coordonnées homogènes d'un zéro commun de De plus, chaque zéro commun peut être obtenu à partir d'un de ces facteurs linéaires, et la multiplicité en tant que facteur est égale à la multiplicité d'intersection du à ce zéro. En d'autres termes, la résultante U fournit une version complètement explicite du théorème de Bézout . ${\displaystyle k[u_{1},\ldots ,u_{n}].}$${\displaystyle P_{1},\ldots ,P_{n-1}}$ ${\displaystyle d_{1}\cdots d_{n-1}.}$${\displaystyle \alpha _{1}u_{1}+\ldots +\alpha _{n}u_{n}}$${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$${\displaystyle P_{1},\ldots ,P_{n-1}.}$${\style d'affichage P_{i}}$

Extension à plus de polynômes et de calcul

La résultante U telle que définie par Macaulay requiert que le nombre de polynômes homogènes dans le système d'équations soit , où est le nombre d'indéterminés. En 1981, Daniel Lazard a étendu la notion au cas où le nombre de polynômes peut différer de , et le calcul résultant peut être effectué via une procédure d' élimination gaussienne spécialisée suivie d'un calcul de déterminant symbolique . ${\style d'affichage n-1}$${\style d'affichage n}$${\style d'affichage n-1}$

Soient des polynômes homogènes en degrés sur un corps k . Sans perte de généralité, on peut supposer que Setting for i > k , la borne de Macaulay est${\displaystyle P_{1},\ldots ,P_{k}}$${\displaystyle x_{1},\ldots ,x_{n},}$${\displaystyle d_{1},\ldots ,d_{k},}$${\displaystyle d_{1}\geq d_{2}\geq \cdots \geq d_{k}.}$${\displaystyle d_{i}=1}$${\displaystyle D=d_{1}+\cdots +d_{n}-n+1.}$

Soit de nouveaux indéterminés et défini Dans ce cas, la matrice de Macaulay est définie comme étant la matrice, sur la base des monômes de l'application linéaire ${\displaystyle u_{1},\ldots ,u_{n}}$${\displaystyle P_{k+1}=u_{1}x_{1}+\cdots +u_{n}x_{n}.}$${\displaystyle x_{1},\ldots ,x_{n},}$

${\displaystyle (Q_{1},\ldots ,Q_{k+1})\mapsto P_{1}Q_{1}+\cdots +P_{k+1}Q_{k+1},}$

où, pour chaque i , parcourt l'espace linéaire constitué de zéro et des polynômes homogènes de degré . ${\displaystyle Q_{i}}$${\displaystyle D-d_{i}}$

En réduisant la matrice de Macaulay par une variante d' élimination gaussienne , on obtient une matrice carrée de formes linéaires en Le déterminant de cette matrice est la U -résultante. Comme avec la résultante U originale, elle est nulle si et seulement si ont une infinité de zéros projectifs communs (c'est-à-dire si l' ensemble algébrique projectif défini par a une infinité de points sur une clôture algébrique de k ). Encore une fois, comme avec la résultante U originale, lorsque cette résultante U n'est pas nulle, elle se factorise en facteurs linéaires sur toute extension algébriquement fermée de k . Les coefficients de ces facteurs linéaires sont les coordonnées homogènes des zéros communs de et la multiplicité d'un zéro commun est égale à la multiplicité du facteur linéaire correspondant. ${\displaystyle u_{1},\ldots ,u_{n}.}$${\displaystyle P_{1},\ldots ,P_{k}}$${\displaystyle P_{1},\ldots ,P_{k}}$${\displaystyle P_{1},\ldots ,P_{k},}$

Le nombre de lignes de la matrice de Macaulay est inférieur à celui où e ~ 2,7182 est la constante mathématique habituelle , et d est la moyenne arithmétique des degrés de Il s'ensuit que toutes les solutions d' un système d' équations polynomiales avec un nombre fini de zéros projectifs . peut être déterminé en temps Bien que cette borne soit grande, elle est presque optimale dans le sens suivant : si tous les degrés d'entrée sont égaux, alors la complexité temporelle de la procédure est polynomiale dans le nombre attendu de solutions ( théorème de Bézout ). Ce calcul peut être pratiquement viable lorsque n , k et d ne sont pas grands. ${\displaystyle (ed)^{n},}$${\style d'affichage P_{i}.}$ ${\style d'affichage d^{O(n)}.}$

Voir également

• Théorie de l'élimination
• Sous-résultant

Remarques

Les références

• Gelfand, IM; Kapranov, MM; Zelevinsky, AV (1994), Discriminants, résultantes et déterminants multidimensionnels , Boston : Birkhäuser, ISBN 978-0-8176-3660-9
• Macaulay, FS (1902), "Certaines formules dans l'élimination" , Proc. Mathématiques de Londres. Soc. , 35 : 3-27, doi : 10.1112/plms/s1-35.1.3
• Macaulay, FS (1916), The Algebraic Theory of Modular Systems , The Cornell Library of Historical Mathematical Monographs, Cambridge University Press, ISBN 978-1275570412
• Salmon, George (1885) [1859], Leçons d'introduction à l'algèbre supérieure moderne (4e éd.), Dublin, Hodges, Figgis, and Co., ISBN 978-0-8284-0150-0

Liens externes

• Weisstein, Eric W. "Résultant" . MathWorld .