Comprendre F5 : une théorie axiomatique des signatures

par Pierre Lairez

jeudi 11 juin 2026, 10:00 → 11:30 Europe/Paris

XR203 (XLIM)

Introduites par Faugère dans l’algorithme F5, les signatures permettent d’éviter une partie importante des réductions à zéro dans les calculs de bases de Gröbner. Elles donnent aussi accès à une information plus riche qu’une base de Gröbner ordinaire, liée aux syzygies des générateurs, ce qui les rend utiles pour certaines opérations idéales comme les quotients, saturations ou décompositions équidimensionnelles.

Dans le cadre classique des bases de Gröbner, le critère de Buchberger et le lemme de Dickson répondent à toutes les questions de correction et de terminaison : le premier dit quels calculs suffisent à garantir que l’on a bien une base de Gröbner, tandis que le second assure que le processus ne peut pas produire indéfiniment de nouveaux termes dominants. Avec les signatures, la situation devient plus subtile. L’information supplémentaire qu’elles transportent rend aussi les algorithmes plus difficiles à modifier sans remettre en cause leur correction ou leur terminaison.

Peut-on intégrer des réductions simultanées de type F4 dans un algorithme à signatures ? Peut-on ajouter des générateurs en cours de calcul, par exemple pour saturer un idéal ? Quels critères restent valables dans un cadre non commutatif, ou plus généralement hors du cadre noethérien classique ?

L’exposé présentera une approche axiomatique des bases de Gröbner avec signatures. L’objectif est de séparer la théorie des choix algorithmiques : définir ce qu’est une signature cohérente, formuler un critère combinatoire de correction, et donner un principe général de terminaison. Les notions de prébase, de base de réécriture et de sigtree apparaissent alors comme les analogues, dans le monde des signatures, du critère de Buchberger et du lemme de Dickson.