Devoir en temps libre d’algorithmique à rendre le mardi 26 octobre 1999

Bases de Gröbner

Soit K un corps commutatif, par exemple celui des réels. On se place dans l’anneau des polynômes à plusieurs variables K[X_{1}, …, X_{n}]. Rappelons qu’un polynôme f s’écrit de manière unique comme une somme finie ∑ a_{i}m_{i} où les a_{i} sont des éléments non nuls de K, les m_{i} sont distincts, chaque m_{i} étant un monôme X_{1}^{k_{1}} ⋯ X_{n}^{k_{n}} où les k_{i} sont des entiers strictement positifs. Le degré d’un tel monôme est ∑ k_{j}. On dit que a_{i} est le coefficient de m_{i} dans f. On note (idéal engendré) :

⟨f_{1}, …, f_{k}⟩ = {f_{1}g_{1} + ⋯ + f_{k}g_{k} | g_{1}, …, g_{k} ∈ K[X_{1}, …, X_{n}]} .

Si J est un idéal (i.e. un sous-ensemble clos par addition et par multiplication par un polynôme quelconque) on note g ≡_{J} h si et seulement si g − h ∈ J.

Le problème est : étant donné J = ⟨f_{1}, …, f_{k}⟩ décider ≡_{J}, i.e. trouver un algorithme qui prend deux polynômes g et h en entrée et renvoie OUI si g ≡_{J} h et NON si g ≢_{J} h. Cela revient à se demander si g − h ≡_{J} 0. La technique employée est la réécriture. Le principe est le suivant. Supposons que J = ⟨f⟩. Si f est un polynôme dans lequel apparaît un monôme m_{1} avec le coefficient a on peut “couper” f en am_{1} et f̂ = f −am_{1}. On a am_{1} ≡_{J} −f̂ que l’on regarde comme une règle de réécriture (ou de calcul) am_{1} → −f̂. On applique cette règle de la manière suivante: si g = bm_{1}m_{2} + g_{1} est un polynôme dont l’un des monômes est divisé par m_{1}, on écrit

g → g′ = −(b/a)f̂m_{2} + g_{1} .

On a g ≡_{J} g′ (car g′ = g − (b/a)fm_{2}) avec g′ “plus simple” pour peu que l’on ait choisi m_{1} “maximal” dans f. On dit que m_{1}m_{2} est le pivot de la réduction. Il faut donc définir un ordre sur les monômes. En voici un (>_{lex} est l’ordre lexicographique) :

X_{1}^{k_{1}} ⋯ X_{n}^{k_{n}} ≻ X_{1}^{l_{1}} ⋯ X_{n}^{l_{n}} ⇔ \{ \begin{matrix}(∑ k_{j} > ∑ l_{j}) ou \\ (∑ k_{j} = ∑ l_{j}) et ((k_{1}, …, k_{n}) >_{lex} (l_{1}, …, l_{n})) . \end{matrix}

(A) Montrer que ≻ est bien fondé (pas de suite infinie strictement décroissante).

Soit f un polynôme. On note H(f) son plus grand monôme (selon ≻). On supposera toujours sans perte de généralité que le coefficient de H(f) dans f est 1 (soit a = 1 ci-dessus). On pose R(f) = f − H(f). On note →_{f} la relation → de ci-dessus obtenue avec ce découpage de f, soit :

g + bH(f)m →_{f} g − bR(f)m

Si G = {f_{1}, …, f_{k}} on note →_{G}= ⋃ →_{f_{i}}. Soulignons que →_{G} dépend du choix des générateurs f_{1}, …, f_{k} de J = ⟨f_{1}, …, f_{k}⟩ (cf. la distinction entre un espace vectoriel et une base particulière de cet espace).

(B) Soit G = {f_{1}, …, f_{k}} et J = ⟨f_{1}, …, f_{k}⟩. Montrer que ≡_{J} est la clôture réflexive, symétrique et transitive ↔_{G}^{∗} de →_{G}.

(C) Montrer que la relation →_{G} est bien fondée.

On pose ensuite la définition suivante : G = {f_{1}, …, f_{k}} est appelé base de Gröbner (pour J = ⟨f_{1}, … f_{k}⟩) si →_{G} est confluent, i.e. si

∀ f, g, h ((f →_{G}^{∗} g et f →_{G}^{∗} h) ⇒ (∃ k g →_{G}^{∗} k et h →_{G}^{∗} k)) .

Les deux résultats qui suivent sont des lemmes généraux.

(D1) Montrer que si →_{G} est confluent alors pour tous f et g si f ↔_{G}^{∗} g alors f et g ont un réduit commun.

(D2) Montrer que la bonne fondation de →_{G} implique que →_{G} est confluente si et seulement si la propriété suivante (appelée confluence locale) est vérifiée:

∀ f, g, h ((f →_{G} g et f →_{G} h) ⇒ (∃ k g →_{G}^{∗} k et h →_{G}^{∗} k))

(un seul pas de réduction dans chacune des hypothèses).

On retourne aux polynômes. La question suivante montre l’intérêt des bases de Gröbner.

(E1) Montrer que si G = {f_{1}, …, f_{n}} est une base de Gröbner pour J = ⟨f_{1}, …, f_{k}⟩, alors ≡_{J} est décidable.

(E2) Trouver des polynômes f_{1}, f_{2} tels que {f_{1}, f_{2}} ne soit pas une base de Gröbner.

(E3) Pour tous g_{1}, g_{2} on pose S(g_{1}, g_{2}) = m_{1}g_{1} − m_{2}g_{2} où m_{1} et m_{2} sont tels que m_{1}H(g_{1}) = m_{2}H(g_{2}) est le plus petit commun multiple de H(g_{1}) et H(g_{2}). Montrer que G = {f_{1}, …, f_{k}} est une base de Gröbner si et seulement si (S(f_{i}, f_{j}) →_{G}^{⋆} 0) pour toutes les paires i, j.

L’étape finale du problème consiste à trouver une base de Gröbner pour un idéal donné J = ⟨f_{1}, …, f_{k}⟩. Si {f_{1}, …, f_{k}} satisfait déjà le critère (E3) il n’y a rien à faire. Sinon on utilise l’algorithme suivant. On pose (G_{0}, B_{0}) = ({f_{1}, …, f_{k}}, {(f_{l}, f_{r}) | 1 ≤ l < r ≤ k}) et on définit le système formel suivant (\underline{h} désigne le polynôme kh (k ∈ K) tel que le coefficient du monôme de tête ait le coefficient 1) :

(f_{l}, f_{r}) ∈ B S(f_{l}, f_{r}) →_{G}^{⋆} h ≠ 0 et irréductible pour →_{G}
(G, B) ⟶ (G ∪ \{\underline{h}\}, B ∪ \{(\underline{h}, f) | f ∈ G\} \ \{(f_{l}, f_{r})\})

\begin{matrix}(f_{l}, f_{r}) ∈ B S(f_{l}, f_{r}) →_{G}^{⋆} 0 \\ (G, B) ⟶ (G, B \ \{(f_{l}, f_{r})\}) \end{matrix}

(F1) Montrer que si (G, B) = (G_{p}, B_{p}) est une forme normale de (G_{0}, B_{0}) pour ce système alors G est une base de Gröbner pour J.

(F2) Montrer que le système termine toujours en admettant le résultat suivant (objet de la question (G)) : si m_{1}, …, m_{n}, … est une suite infinie de monômes alors il existe i < j tel que m_{i} divise m_{j}.

Pour prouver la propriété utilisée en (F2) il reste un petit peu de travail et cela passe par la notion de bon ordre partiel. Un bon ordre partiel est un ensemble ordonné X tel que pour toute suite infinie x_{1}, …, x_{n}, … d’éléments de X il existe i, j tels que i < j et x_{i} ≤ x_{j}. Cette propriété implique la bonne fondation, car s’il existait une suite x_{1}, …, x_{n}, … telle que x_{n} > x_{n+1} pour tout n alors on ne pourrait avoir i < j tels que x_{i} ≤ x_{j} (antisymétrie de ≤). Réciproquement si l’ordre est total il est facile de voir que la bonne fondation implique la propriété de bon ordre partiel.

Si X et Y sont des ordres partiels l’ordre produit sur X × Y est défini par (x_{1}, y_{1}) ≤ (x_{2}, y_{2}) si et seulement si x_{1} ≤ x_{2} et y_{1} ≤ y_{2}. Il est facile de voir que si X et Y sont bien fondés alors X × Y est bien fondé. Mais c’est le résultat plus fort que X × Y est un bon ordre partiel qui nous intéresse (noter que si X et Y sont des ordres totaux, X × Y n’est pas total sauf cas trivial: (3, 5) versus (4, 2)).

(G1) Montrer que dans un bon ordre partiel X tout suite infinie x_{1}, …, x_{n}, … admet une sous-suite croissante x_{i_{1}} ≤ ⋯ ≤ x_{i_{n}} ≤ · · ·.

(G2) Prouver que si X et Y sont des bons ordres partiels alors X × Y est un bon ordre partiel.

(G3) Prouver l’hypothèse faite dans la question (F2).