Algorithme qui, étant donné un ensemble fini de polynômes multivariés dans un anneau de polynômes sur un corps et un ordre monomial fixé, produit une base de Gröbner de l'idéal qu'ils engendrent ; la sortie est un ensemble fini de générateurs dont les monômes dominants engendrent l'idéal des termes dominants.

Principe

Former itérativement les S-polynômes de paires d'éléments de la base et les réduire par rapport à la base courante ; si le reste est non nul, l'ajouter à la base et répéter jusqu'à ce que tous les S-polynômes se réduisent à zéro, obtenant ainsi une base stable par réduction polynomiale pour l'ordre choisi.

Démonstration

Avec des générateurs f1, f2 dans k[x,y], calculer S(f1,f2) pour annuler les termes dominants ; réduire S(f1,f2) par f1,f2. Si la réduction donne un reste r non nul, ajouter r et recalculer les S-polynômes impliquant r. Répéter jusqu'à absence de nouveaux restes non nuls ; l'ensemble final est une base de Gröbner permettant de tester l'appartenance à l'idéal et d'effectuer des éliminations.

Mauvaise application

Exécuter l'algorithme sans ordre monomial fixé, ou supposer que la terminaison est automatique dans des anneaux autres que des anneaux de polynômes sur un corps ; confondre la base obtenue immédiatement avec une base réduite ou minimale sans post-traitement.

Conséquence

Un déroulement correct donne une base de Gröbner qui décide l'appartenance aux idéaux, permet le calcul des idéaux d'élimination, des dimensions et des syzygies ; de nombreuses tâches algorithmiques en théorie des idéaux deviennent mécaniques une fois la base connue.

Inversion

Au lieu de compléter par réduction des S-polynômes, on peut partir d'une base de Gröbner et tenter de retrouver les générateurs initiaux ; ce processus inverse n'est pas unique et perd généralement de l'information structurelle.

Limite

Nécessite un anneau de polynômes sur un corps (ou un domaine de coefficients permettant la division par les coefficients dominants) et un ordre monomial bien fondé. Dans des anneaux non Noethériens ou sur des corps partiels, le comportement et la terminaison peuvent échouer ou exiger des adaptations.

Tension sémantique

Souvent confondu avec la notion même de base de Gröbner ; l'algorithme est une procédure de construction tandis qu'une base de Gröbner est un objet mathématique indépendant de la méthode. Il faut aussi distinguer l'algorithme originel de Buchberger des variantes optimisées (F4, F5, méthodes à signatures).

Synthèse

L'algorithme de Buchberger complète un ensemble générateur d'un idéal polynômial en une base de Gröbner exploitable algorithmiquement en annulant les conflits de termes dominants par des S-polynômes et des réductions répétées pour un ordre monomial donné.