Base de Gröbner

Le point de départ est un procédé de réduction qui, à l'instar de la division euclidienne dans K[X], remplace un polynôme par un autre « plus petit » mais équivalent modulo l'idéal. On appelle monôme un polynôme produit d'indéterminées, et terme un monôme multiplié par un scalaire, son coefficient. Pour définir cette « division euclidienne généralisée », il est utile de choisir une façon d'ordonner les monômes de l'anneau considéré (ce dont on se convainc facilement en essayant de diviser un polynôme de K[X, Y] par un autre).

Un ordre monomial est un ordre total sur les monômes tel que

• pour tout monôme ${\displaystyle u}$, on ait ${\displaystyle 1\leq u}$ et
• pour tous les monômes ${\displaystyle u}$ et ${\displaystyle v}$ tels que ${\displaystyle u\leq v}$, on ait ${\displaystyle uw\leq vw}$ pour tout monôme ${\displaystyle w}$.

Un ordre monomial est toujours un bon ordre. On définit naturellement les notions de monôme dominant, de coefficient dominant et de terme dominant — noté ici λ(f) — d'un polynôme f relativement à un ordre monomial.

Par exemple, l'ordre lexicographique est un ordre monomial. D'autres relations d'ordre sont possibles, pourvu qu'elles vérifient certaines propriétés, destinées à ce que les algorithmes de calculs puissent aller à leur terme, sans boucler par exemple. Les relations d'ordre présentent différentes propriétés et donc certains avantages les unes par rapport aux autres, suivant le type de problème posé. Par exemple, l'ordre lexicographique, relativement coûteux en temps de calcul, est assez pratique pour faire des projections de la variété associée à l'idéal.

Fixons un ordre monomial et une partie finie B de K[X₁, …, X_n]. Introduisons une règle de réécriture sur K[X₁, …, X_n] en posant

${\displaystyle g\quad \to \quad g-{\frac {t}{\lambda (f)}}\;f}$

si t est le terme de g de plus haut degré divisible par un certain λ(f) avec f∈B. La clôture réflexive transitive →* de → est appelée réduction modulo B. Autrement dit, pour réduire g, on essaie de lui retrancher un multiple convenable d'un polynôme f de B, de sorte que les termes dominants se simplifient. (On retrouve ici non seulement la division euclidienne pour les polynômes à une variable, mais aussi, dans le cas linéaire, le pivot de Gauss.) Si l'on ne parvient pas à éliminer le terme dominant de g, on l'ajoute au « reste » de la division et on passe au terme de degré immédiatement inférieur.

La réduction →* termine (elle est « nœthérienne »), mais elle n'est en général pas confluente, c'est-à-dire que bien que tout polynôme admette une forme réduite modulo B, celle-ci n'a aucune raison d'être unique.

Une base de Gröbner est une partie B pour laquelle la situation est plus favorable.

Soit I un idéal de K[X₁, …, X_n]. Une base de Gröbner, ou base standard, de I est une partie génératrice finie G de I vérifiant en outre les propriétés équivalentes suivantes.

1. La réduction modulo G est confluente (et donc fortement normalisante).
2. Un polynôme g appartient à I si et seulement s'il se réduit à 0 modulo G.
3. Pour tous f, g de G, ${\displaystyle {\frac {\lambda (f)\vee \lambda (g)}{\lambda (f)}}\,f-{\frac {\lambda (f)\vee \lambda (g)}{\lambda (g)}}\,g\quad \to ^{*}\quad 0}$ modulo G, le symbole ∨ désignant le ppcm normalisé.
4. Les monômes dominants des polynômes de G engendrent le même idéal que les monômes dominants des éléments de I (cela implique que G engendre I).

Cette dernière propriété est la définition usuelle des bases de Gröbner. Elle est pertinente pour leur étude théorique, mais les deux premières formulations sont peut-être plus parlantes. L'assertion 3 fournit quant à elle un moyen simple pour tester si une famille de polynômes est une base de Gröbner.

On peut montrer que tout idéal admet une base de Gröbner. Avec cette définition, il n'y a pas unicité ; si G est une base de Gröbner de I et si f appartient à I, alors G∪{f} est encore une base de Gröbner de I. En revanche, tout idéal admet une unique base de Gröbner minimale, c'est-à-dire à laquelle on ne peut enlever de polynôme en maintenant la propriété d'être une base de Gröbner de l'idéal.