Ordre monomial

En mathématiques, un ordre monomial est un ordre total sur l'ensemble des monômes d'un anneau de polynômes donné, compatible avec la multiplication, c'est-à-dire :

• Pour tout monôme $w$, si deux monômes $u$ et $v$ satisfont $u\leq v$ selon l'ordre monomial, alors $uw\leq vw$.

Les ordres monomiaux sont le plus souvent utilisés pour le calcul des bases de Gröbner et la division multivariée. En particulier, la propriété d'être une base de Gröbner est toujours relative à un ordre monomial spécifique.

Définition, détails et variantes

En plus d'être compatible avec la multiplication, les ordres monomiaux doivent souvent être de bons ordres, car cela garantit que l'algorithme de division multivariée termine. Il existe cependant des applications pratiques pour les relations d'ordre compatibles avec la multiplication, mais qui ne sont pas des bons ordres.

Dans le cas d'un nombre fini de variables, le fait qu'un ordre monomial soit un bon ordre équivaut à la conjonction des deux conditions suivantes :

1. L'ordre est une ordre total.
2. Si u est un monôme alors $1\leq u$.

Ces conditions sont parfois préférées pour définir un ordre monomial, étant donné qu'il est parfois préférable de les vérifier pour un ordre monomial explicite, que de prouver directement qu'il s'agit d'un bon ordre.

L'ordre peut aussi être défini de manière équivalente sur les t-uple des coefficients de chacune des variables de l'anneau : si l'anneau des polynômes est $R[x,y]$ (sans perte de généralité, l'anneau est construit sur deux variables et les polynômes sont alors bivariés en les variables $x$ et $y$), les monômes d'un polynôme sont de la forme $x^{\alpha _{i}}y^{\beta _{i}}$ avec les exposants $\alpha _{i}$ et $\beta _{i}$ entiers positifs. La définition d'un bon ordre monomial sur les couples $(\beta ,\gamma )$ est alors :

1. L'ordre est un ordre total.
2. $(0,0)$ est l'élement minimal pour cet ordre.

Monômes, termes et coefficients de tête

Le choix d'un ordre total sur les monômes permet de trier les termes d'un polynôme. Le terme de tête d'un polynôme est alors le terme du plus grand monôme pour l'ordre monomial choisi.

Concrètement, soit R un anneau de polynômes quelconque. Alors l'ensemble M des monômes de R est une base de R, considérée comme un espace vectoriel sur le corps des coefficients. Ainsi, tout polynôme non nul p dans R a une expression unique $p=\textstyle \sum _{u\in S}c_{u}u$ comme une combinaison linéaire de monômes, où S est un sous-ensemble fini de M et les c_u sont tous non nuls. Lorsqu'un ordre monomial a été choisi, le monôme de tête est le plus grand u de S, le coefficient de tête est le c_u correspondant et le terme de tête est le c_uu correspondant. Le monôme/coefficient/terme de tête est parfois appelé "dominant". Dans cet article, un monôme est supposé ne pas inclure de coefficient.

La propriété des ordres monomiaux implique que l'ordre des termes est conservé lors de la multiplication d'un polynôme par un monôme. De plus, le terme dominant d'un produit de polynômes est le produit des termes dominants des facteurs.

Ordres communs

Sur l'ensemble $\left\{x^{n}\mid n\in \mathbb {N} \right\}$ des puissances de la variable $x$, les seuls ordres monomiaux sont l'ordre naturel $1<x<x^{2}<x^{3}<...$ et son opposé, mais ce dernier n'est pas un bon ordre. La notion d'ordre monomial ne devient intéressante que lorsqu'il y a plusieurs variables.

Lorsque les variables sont en nombre fini, l'ordre monomial donne un ordre sur celles-ci. On peut simplifier la classification des ordres monomiaux en supposant que les variables sont nommées $x_{1}$, $x_{2}$, $x_{3}$… dans l'ordre décroissant de l'ordre monomial considéré, de sorte que $x_{1}>x_{2}>x_{3}>\dots$. Avec cette convention, il existe encore de nombreux exemples d'ordres monomiaux différents.

Ordre lexicographique

L'ordre lexicographique (lex) compare d'abord les exposants de $x_{1}$ dans les monômes selon l'ordre naturel sur les entiers, et en cas d'égalité compare les exposants de $x_{2}$, et ainsi de suite. Le nom est dérivé de la similitude avec l'ordre alphabétique habituel utilisé en lexicographie pour les dictionnaires, si les monômes sont représentés par le n-uplet des exposants des variables. Si le nombre de variables est fini (comme c'est généralement le cas), l'ordre lexicographique est un bon ordre. Pour les calculs de bases de Gröbner, cet ordre a tendance à être le plus coûteux; il faut donc l'éviter, dans la mesure du possible, sauf pour des calculs très simples.

Ordre lexicographique gradué

L'ordre lexicographique gradué (grlex pour graded lexicographic order, ou deglex pour degree lexicographic order) compare d'abord le degré total (somme de tous les exposants) des monômes, et en cas d'égalité applique l'ordre lexicographique. Cet ordre n'est pas seulement un bon ordre, il a aussi la propriété que tout monôme n'est précédé que d'un nombre fini d'autres monômes ; ce n'est pas le cas pour l'ordre lexicographique, où toutes les puissances de $x$ (en nombre infini) sont inférieures à $y$ (cet ordre lexicographique est néanmoins un bon ordre : il est impossible de construire une chaîne décroissante infinie de monômes). Bien que très naturel, cet ordre est rarement utilisé : la base de Gröbner pour l'ordre lexicographique inverse gradué est plus facile à calculer et fournit la même information sur l'ensemble de polynômes d'entrée.

Ordre lexicographique inverse gradué

L'ordre lexicographique inverse gradué (grevlex pour graded reverse lexicographic order ou degrevlex pour degree reverse lexicographic order) compare d'abord le degré total, puis utilise un ordre lexicographique inversé comme condition de départage, puis inverse ce résultat. Concrètement, l'ordre lexicographique inverse gradué consiste à comparer d'abord le degré total, puis à comparer les exposants de la dernière variable $x_{n}$ mais en inversant le résultat (donc le monôme avec le plus petit exposant est plus grand dans l'ordre), suivi (comme toujours uniquement en cas d'égalité) par une comparaison similaire de $x_{n-1}$, et ainsi de suite en terminant par $x_{1}$ si nécessaire.

Les différences entre l'ordre lexicographique gradué et l'ordre lexicographique inverse gradué sont subtiles, puisqu'ils coïncident en fait pour 1 et 2 variables. La première différence vient pour les monômes de degré 2 en 3 variables, qui sont ordonnés par grlex comme $x_{1}^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}$ mais ordonnés par grevlex comme $x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}x_{3}>x_{2}x_{3}>x_{3}^{2}$.

Ordre d'élimination

L'ordre de blocs ou ordre d'élimination (lexdeg) peut être défini pour n'importe quel nombre de blocs mais, par souci de simplicité, nous ne considérons que le cas de deux blocs. Si le nombre de blocs est égal au nombre de variables, cet ordre est simplement l'ordre lexicographique. Pour cet ordre, les variables sont divisées en deux blocs $x_{1},...,x_{h}$ et $y_{1},...,y_{k}$ et un ordre monomial est choisi pour chaque bloc, généralement l'ordre lexicographique inverse gradué. Deux monômes sont comparés en comparant leur bloc de variables $x$, et en cas d'égalité, en comparant leur bloc de variables $y$. Cet ordre est important car il permet l'élimination, opération qui correspond à la projection en géométrie algébrique.

Ordre pondéré

L'ordre pondéré dépend d'un vecteur $(a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}$ appelé vecteur de pondération. Il compare d'abord le produit scalaire des séquences d'exposants des monômes avec ce vecteur de pondération et, en cas d'égalité, utilise un autre ordre monomial.

Par exemple, les deux ordres gradués mentionnés ci-dessus sont des ordres pondérés pour le vecteur de pondération $(1,1,...,1)$ qui permet le calcul de la somme des degrés.

Si les $a_{i}$ sont des nombres rationnellement indépendants (donc en particulier aucun d'entre eux n'est nul et toutes les fractions ${\tfrac {a_{i}}{a_{j}}}$ sont irrationnelles), alors une égalité ne peut jamais se produire, et la pondération elle-même spécifie un ordre monomial. Dans le cas contraire, on pourrait utiliser une autre pondération pour rompre les égalités, et ainsi de suite ; après avoir utilisé n vecteurs de pondération linéairement indépendantes, il ne peut plus y avoir d'égalité. On peut en effet définir tout ordre monomial par une séquence de vecteurs de pondération (Cox et al. pp. 72–73), par exemple (1,0,0,...,0), (0,1,0,...,0), ... (0,0,...,1) pour lex, ou (1,1,1,...,1), (1,1,..., 1,0), ... (1,0,...,0) pour grevlex.

Exemple

Dans l'exemple, les variables sont nommées $x$, $y$ et $z$ au lieu de $x_{1}$, $x_{2}$ et $x_{3}$.

Considérons les monômes $xy^{2}z$, $z^{2}$, $x^{3}$, et $x^{2}z^{2}$ ; les ordres monomiaux définis ci-dessus ordonnent ces quatre monômes comme suit :

• Lex : $x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}$ (la puissance de $x$ domine).
• Grlex : $x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}$ (le degré total domine ; la puissance supérieure de $x$ départage les deux premiers).
• Grevlex : $xy^{2}z>x^{2}z^{2}>x^{3}>z^{2}$ (le degré total domine ; la puissance inférieure de $z$ départage les deux premiers).
• Un ordre pondéré avec vecteur de pondération (1,2,4) : $x^{2}z^{2}>xy^{2}z>z^{2}>x^{3}$ (les produits scalaires 10 > 9 > 8 > 3 ne nécessitent pas de départages).

Notions associées

• Un ordre d'élimination garantit qu'un monôme impliquant l'une des variables d'un bloc sera toujours supérieur à un monôme n'impliquant que des variables des blocs suivants.
• Un ordre produit est l'exemple le plus simple d'un ordre d'élimination. Il consiste à combiner des ordres monomiaux sur des ensembles disjoints de variables en un ordre monomial sur leur réunion. Il compare simplement les exposants des variables du premier ensemble en utilisant le premier ordre monomial, puis départage les égalités en utilisant l'ordre monomial sur les variables du deuxième ensemble. Cette méthode se généralise évidemment à toute union disjointe d'ensembles de variables ; l'ordre lexicographique peut être ainsi obtenu à partir des ensembles de singletons {x₁}, {x₂}, {x₃}, ... (avec l'ordre monomial naturel pour chaque singleton).

Lors de la recherche de bases de Gröbner, les résultats et la difficulté du calcul peuvent varier considérablement selon le choix de l'ordre monomial. Par exemple, l'ordre lexicographique inverse gradué a la réputation de produire, presque toujours, les bases de Gröbner qui sont les plus faciles à calculer (ceci est renforcé par le fait que, dans des conditions assez courantes sur l'idéal, les polynômes de la base de Gröbner ont une degré qui est au plus exponentiel dans le nombre de variables ; aucun résultat similaire n'existe pour les autres ordres). D'autre part, les ordres d'élimination sont requis pour les problèmes d'élimination et les problèmes associés.

Références

• David Cox, John Little et Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 2007 (ISBN 978-0-387-35650-1)