Base de Gröbner - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Intérêt - Calcul - Définition

Introduction

En mathématiques, une base de Gröbner (ou base standard, ou base de Buchberger) d'un idéal $I$ de l'anneau de polynômes $K[X_1,\dots, X_n]$ est un ensemble de générateurs de cet idéal, vérifiant certaines propriétés supplémentaires. Cette notion a été introduite dans les années 1960, indépendamment par Heisuke Hironaka et Bruno Buchberger, qui leur a donné le nom de son directeur de thèse Wolfgang Gröbner.

Les bases de Gröbner ont le grand avantage de ramener l'étude des idéaux polynomiaux à l'étude des idéaux monomiaux (c'est-à-dire formés de monômes), plus faciles à appréhender.

Intérêt

Soit $K$ un corps (commutatif).

Revenons un instant sur le cas des polynômes à une seule variable : l'anneau $K [X]$ est euclidien, et un idéal $I$ de $K [X]$ se représente naturellement par son générateur principal. Mieux, l'algorithme d'Euclide permet de déterminer celui-ci à partir d'une famille finie de générateurs, et ainsi de tester l'appartenance d'un polynôme à $I$ , ou encore de calculer un représentant canonique pour un élément de $K [X] / I$ .

L'anneau $K[X_1, \dots, X_n]$ , en revanche, est factoriel et nœthérien mais pas principal. Concrètement, on ne peut pas y étendre « naturellement » la division euclidienne des polynômes à une variable.

Les bases de Gröbner permettent néanmoins de calculer modulo un idéal de $K[X_1, \dots, X_n]$ , et notamment

de décider si l'idéal est $K[X_1, \dots, X_n]$ tout entier (c'est-à-dire d'un point de vue géométrique si sa variété dans une clôture algébrique de $K$ est vide, ou encore si un système polynomial donné y admet au moins une solution) ;
de décider si un polynôme appartient à l'idéal, ou à son radical — et ainsi, si une fonction polynomiale est nulle sur une variété ;
de trouver des représentants canoniques pour les éléments de l'algèbre quotient, et partant, d'effectuer des calculs algébriques modulo l'idéal ;
de déterminer la dimension et le degré d'une variété équidimensionnelle (ou plus généralement la dimension et la somme des degrés des composantes équidimensionnelles de dimension maximale d'une variété quelconque).

Plus généralement, les bases de Gröbner permettent de calculer la fonction et le polynôme de Hilbert d'un module gradué. Elles fournissent aussi un moyen de déterminer l'intersection de deux idéaux.

Calcul

On dispose d'algorithmes pour calculer les bases de Gröbner. Très sommairement, le premier et le plus connu, l'algorithme de Buchberger, procède en ajoutant des polynômes à la base pour éliminer peu à peu les paires critiques qui contredisent l'assertion 3, un peu à la manière de la complétion de Knuth-Bendix. On sait aussi calculer les bases de Gröbner minimales.

Ces algorithmes sont très inefficaces dans le pire des cas, et les cas plus favorables sont mal connus.

Pour un idéal de polynômes à $n$ variables de degré total borné par $D$ , on sait calculer une base de Gröbner en au plus $D^{2^{O(n)}}$ opérations dans le corps de base. Ernst Mayr et Albert Meyer ont montré que cette borne supérieure énorme pouvait être atteinte, et donc est optimale : il existe des idéaux dont toute base de Gröbner compte $2^{2^{\Omega(n)}}$ éléments, eux-mêmes de degré doublement exponentiel en $n$ . Tout n'est pas perdu pour autant. En effet, expérimentalement, cette borne n'est atteinte que sur les exemples construits dans ce but. Pour un système rationnel ayant un nombre fini de solutions complexes, Daniel Lazard a établi que le calcul était faisable en temps $D O (n)$ . Sous des hypothèses légèrement différentes, Jean-Charles Faugère donne une borne de $O (D 4,3 n)$ . Mais de façon générale, la complexité du calcul de bases de Gröbner dans les cas usuels est mal maîtrisée.