Anneaux de polynômes

Les bases de Gröbner sont à la géométrie algébrique ce que la décomposition en valeurs singulières est à l’algèbre linéaire numérique : un outil universel qui rend les problèmes calculables.

Bruno Buchberger

Introduction

L’anneau \(K[X]\) des polynômes à une variable est l’un des objets les mieux compris de l’algèbre : il est euclidien, principal, et factoriel. Mais dès que l’on passe à plusieurs variables, la situation devient radicalement plus riche — et plus difficile. L’anneau \(K[X_1, \ldots, X_n]\) pour \(n \geq 2\) n’est plus principal, et la division euclidienne n’est plus canonique. Les bases de Gröbner, introduites par Bruno Buchberger en 1965, résolvent ce problème en fournissant, pour tout idéal de \(K[X_1, \ldots, X_n]\), un système générateur remarquable qui rend le reste de la division unique. Elles sont aujourd’hui au cœur des systèmes de calcul formel et de la géométrie algébrique effective.

Show code cell source

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from matplotlib.patches import FancyArrowPatch
import itertools

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

fig, axes = plt.subplots(2, 1, figsize=(10, 12))

# --- Visualisation 1 : comparaison des 3 ordres monomiaux ---
# Monômes X^a Y^b de degré total <= 3
monomials = [(a, b) for a in range(4) for b in range(4) if a + b <= 3]

def lex_key(ab):
    return ab  # (a, b), ordre lexicographique

def grlex_key(ab):
    a, b = ab
    return (a + b, a, b)

def grevlex_key(ab):
    a, b = ab
    return (a + b, -b, -a)

ax = axes[0]
orders = [
    ("lex", lex_key, "steelblue"),
    ("grlex", grlex_key, "tomato"),
    ("grevlex", grevlex_key, "seagreen"),
]

# Trier les monômes selon chaque ordre et afficher le rang
for idx, (name, key, color) in enumerate(orders):
    sorted_m = sorted(monomials, key=key)
    ranks = {m: r for r, m in enumerate(sorted_m)}
    xs = [m[0] + idx * 0.25 - 0.25 for m in monomials]
    ys = [ranks[m] for m in monomials]
    ax.scatter(xs, ys, color=color, s=60, label=f"${name}$", alpha=0.85, zorder=3)

ax.set_xlabel("Monôme $X^a Y^b$ (numéroté par index $4a+b$)", fontsize=9)
ax.set_ylabel("Rang dans l'ordre monomial", fontsize=9)
ax.set_xticks(range(len(monomials)))
ax.set_xticklabels([f"$X^{{{a}}}Y^{{{b}}}$" for a, b in monomials], rotation=70, fontsize=7)
ax.set_title("Comparaison des ordres monomiaux lex, grlex, grevlex\nsur les monômes $X^a Y^b$, $a+b \\leq 3$", fontsize=10)
ax.legend(fontsize=9)

# --- Visualisation 2 : division multivariée étape par étape ---
# f = XY + 1, f1 = XY - X, f2 = Y - 1, ordre lex (X > Y)
# Étape 1 : LT(f) = XY, LT(f1) = XY → quotient q1 += 1, reste = f - f1 = X + 1
# Étape 2 : f_courant = X + 1, LT = X, aucun LT(fi) ne divise X → passer dans reste
# Résultat : q1 = 1, q2 = 0, r = X + 1

steps = [
    ("$f = XY + 1$",           "diviseur $f_1 = XY - X$",  "$q_1 += 1$",  "$XY+1-(XY-X) = X+1$"),
    ("$f_{\\rm courant} = X+1$","$\\mathrm{LT}(f_1)=XY\\nmid X$\n$\\mathrm{LT}(f_2)=Y\\nmid X$",
                                "$r += X$",     "$1$"),
    ("$f_{\\rm courant} = 1$", "$\\mathrm{LT}(f_1)=XY\\nmid 1$\n$\\mathrm{LT}(f_2)=Y\\nmid 1$",
                                "$r += 1$",     "$0$"),
]

ax2 = axes[1]
ax2.axis("off")
ax2.set_xlim(0, 10)
ax2.set_ylim(-0.5, len(steps) + 0.5)
ax2.set_title("Division de $f = XY+1$ par $(f_1, f_2)$ en ordre lex\n$f_1 = XY-X$, $f_2 = Y-1$", fontsize=10)

headers = ["Courant", "Condition", "Mise à jour", "Nouveau courant"]
col_x = [0.2, 2.8, 6.0, 8.0]
for j, h in enumerate(headers):
    ax2.text(col_x[j], len(steps) + 0.1, h, fontsize=9, fontweight="bold", color="navy")

colors_rows = ["#d0e8f5", "#f5e0d0", "#d0f5d8"]
for i, (courant, cond, update, nouveau) in enumerate(steps):
    row_y = len(steps) - 1 - i
    ax2.add_patch(plt.Rectangle((0, row_y - 0.4), 10, 0.8,
                                color=colors_rows[i], alpha=0.5, lw=0))
    for j, txt in enumerate([courant, cond, update, nouveau]):
        ax2.text(col_x[j], row_y, txt, fontsize=8, va="center")

ax2.text(0.2, -0.3,
         "Résultat : $q_1 = 1$, $q_2 = 0$, reste $r = X + 1$",
         fontsize=9, color="darkred", fontweight="bold")

plt.show()

Polynômes en plusieurs variables

Définition 32 (Monôme et polynôme multivarié)

Soit \(K\) un corps et \(n \geq 1\). Un monôme en \(X_1, \ldots, X_n\) est un produit

\[X^\alpha = X_1^{\alpha_1} \cdots X_n^{\alpha_n}, \qquad \alpha = (\alpha_1, \ldots, \alpha_n) \in \mathbb{N}^n.\]

Son degré total est \(|\alpha| = \alpha_1 + \cdots + \alpha_n\), et son degré partiel en \(X_i\) est \(\alpha_i\).

Un polynôme \(f \in K[X_1, \ldots, X_n]\) est une combinaison linéaire finie de monômes :

\[f = \sum_{\alpha \in \mathbb{N}^n} c_\alpha X^\alpha, \qquad c_\alpha \in K, \text{ presque tous nuls.}\]

Le degré de \(f\) est \(\deg(f) = \max\{|\alpha| : c_\alpha \neq 0\}\).

Remarque 18

L’anneau \(K[X]\) est euclidien (algorithme de division euclidienne par le degré) et donc principal (tout idéal est engendré par un seul élément). En revanche, pour \(n \geq 2\), l’anneau \(K[X_1, \ldots, X_n]\) est factoriel mais pas principal : l’idéal \((X_1, X_2) = \{f : f(0, \ldots, 0) = 0\}\) ne peut pas être engendré par un seul polynôme.

Proposition 11 (Non-principalité de \(K[X, Y]\))

L’idéal \(I = (X, Y) \subset K[X, Y]\) n’est pas principal.

Proof. Supposons \(I = (P)\) pour un certain \(P \in K[X, Y]\). Alors \(P \mid X\) et \(P \mid Y\) dans \(K[X, Y]\). Puisque \(X\) et \(Y\) sont irréductibles et non associés, \(P\) doit être une unité de \(K[X, Y]\), c’est-à-dire \(P \in K^*\). Mais alors \((P) = K[X, Y] \neq I\) car \(1 \notin I\) (tout élément de \(I\) a un terme constant nul). Contradiction.

Ordres monomiaux

Définition 33 (Ordre monomial)

Un ordre monomial sur \(\mathbb{N}^n\) est une relation d’ordre total \(\leq\) sur \(\mathbb{N}^n\) telle que :

1. \(\leq\) est compatible avec l’addition : \(\alpha \leq \beta \implies \alpha + \gamma \leq \beta + \gamma\) pour tout \(\gamma \in \mathbb{N}^n\)

2. \(\leq\) est un bon ordre : tout sous-ensemble non vide de \(\mathbb{N}^n\) a un plus petit élément

La condition de bon ordre implique que \(0 = (0, \ldots, 0)\) est le plus petit élément, et que tout monôme \(X^\alpha\) satisfait \(1 \leq X^\alpha\).

Exemple 25 (Les trois ordres classiques en deux variables)

Soit \(\alpha = (a_1, a_2)\) et \(\beta = (b_1, b_2)\) des exposants dans \(\mathbb{N}^2\).

Ordre lexicographique (\(\mathrm{lex}\)) : \(\alpha >_{\mathrm{lex}} \beta\) si le premier indice \(i\) où \(\alpha_i \neq \beta_i\) vérifie \(\alpha_i > \beta_i\). Exemple : \(X^2 >_{\mathrm{lex}} XY^5 >_{\mathrm{lex}} Y^{100}\).

Ordre lexicographique gradué (\(\mathrm{grlex}\)) : \(\alpha >_{\mathrm{grlex}} \beta\) si \(|\alpha| > |\beta|\), ou \(|\alpha| = |\beta|\) et \(\alpha >_{\mathrm{lex}} \beta\). Exemple : \(XY^2 >_{\mathrm{grlex}} X^2\) (car \(|XY^2| = 3 > 2 = |X^2|\)).

Ordre gradué lexicographique inverse (\(\mathrm{grevlex}\)) : \(\alpha >_{\mathrm{grevlex}} \beta\) si \(|\alpha| > |\beta|\), ou \(|\alpha| = |\beta|\) et le dernier indice \(i\) où \(\alpha_i \neq \beta_i\) vérifie \(\alpha_i < \beta_i\). L’ordre grevlex produit souvent les calculs les plus rapides en pratique.

Définition 34 (Terme dominant, monôme dominant, coefficient dominant)

Soit \(>\) un ordre monomial et \(f = \sum_\alpha c_\alpha X^\alpha \in K[X_1, \ldots, X_n]\), \(f \neq 0\).

• Le monôme dominant de \(f\) est \(\mathrm{LM}(f) = X^{\alpha^*}\) où \(\alpha^* = \max_{>}\{\alpha : c_\alpha \neq 0\}\).

• Le coefficient dominant de \(f\) est \(\mathrm{LC}(f) = c_{\alpha^*} \in K^*\).

• Le terme dominant de \(f\) est \(\mathrm{LT}(f) = \mathrm{LC}(f) \cdot \mathrm{LM}(f)\).

Remarque 19

Pour tout ordre monomial, on a \(\mathrm{LM}(fg) = \mathrm{LM}(f) \cdot \mathrm{LM}(g)\) et, si \(\mathrm{LM}(f) \neq \mathrm{LM}(g)\), alors \(\mathrm{LM}(f + g) = \max(\mathrm{LM}(f), \mathrm{LM}(g))\). Ces propriétés sont fondamentales pour l’algorithme de Buchberger.

Division euclidienne multivariée

Définition 35 (Algorithme de division multivariée)

Soit \(f, f_1, \ldots, f_s \in K[X_1, \ldots, X_n]\) et \(>\) un ordre monomial. L”algorithme de division de \(f\) par la liste ordonnée \((f_1, \ldots, f_s)\) produit des quotients \(q_1, \ldots, q_s\) et un reste \(r\) tels que :

\[f = q_1 f_1 + \cdots + q_s f_s + r\]

où aucun monôme de \(r\) n’est divisible par \(\mathrm{LT}(f_1), \ldots, \mathrm{LT}(f_s)\).

L’algorithme procède à chaque étape en cherchant le premier \(f_i\) dont \(\mathrm{LT}(f_i)\) divise le terme dominant du reste courant, et en effectuant la soustraction correspondante.

Exemple 26 (Division de \(XY + 1\) par \((XY - X, \; Y - 1)\) en ordre lex)

Posons \(f = XY + 1\), \(f_1 = XY - X\), \(f_2 = Y - 1\), ordre lex avec \(X > Y\).

• \(\mathrm{LT}(f) = XY\), \(\mathrm{LT}(f_1) = XY\) divise \(XY\) : \(q_1 \mathrel{+}= 1\), courant \(\leftarrow (XY+1) - 1 \cdot (XY-X) = X + 1\).

• \(\mathrm{LT}(X+1) = X\) ; \(\mathrm{LT}(f_1) = XY \nmid X\) et \(\mathrm{LT}(f_2) = Y \nmid X\) : \(r \mathrel{+}= X\), courant \(\leftarrow 1\).

• \(\mathrm{LT}(1) = 1\) ; aucun \(\mathrm{LT}(f_i)\) ne divise \(1\) : \(r \mathrel{+}= 1\), courant \(\leftarrow 0\).

Résultat : \(q_1 = 1\), \(q_2 = 0\), \(r = X + 1\).

Remarque 20

Le reste de la division multivariée dépend de l’ordre des diviseurs. Si l’on divise le même polynôme \(f = XY + 1\) par \((f_2, f_1)\) au lieu de \((f_1, f_2)\), on obtient un reste différent. C’est précisément ce problème que les bases de Gröbner résolvent : avec une base de Gröbner, le reste est unique et ne dépend pas de l’ordre de présentation des générateurs.

Idéal de tête et \(S\)-polynômes

Définition 36 (Idéal des termes dominants)

Soit \(I \subset K[X_1, \ldots, X_n]\) un idéal et \(>\) un ordre monomial. L”idéal des termes dominants de \(I\) est

\[\mathrm{LT}(I) = \bigl(\mathrm{LT}(f) : f \in I, \; f \neq 0\bigr).\]

Si \((f_1, \ldots, f_s)\) est un système générateur de \(I\), on a en général

\[\bigl(\mathrm{LT}(f_1), \ldots, \mathrm{LT}(f_s)\bigr) \subsetneq \mathrm{LT}(I).\]

L’égalité caractérise précisément les bases de Gröbner.

Définition 37 (\(S\)-polynôme)

Soient \(f, g \in K[X_1, \ldots, X_n]\) non nuls. Notons \(L = \mathrm{lcm}(\mathrm{LM}(f), \mathrm{LM}(g))\) le plus petit commun multiple de leurs monômes dominants. Le \(S\)-polynôme de \(f\) et \(g\) est

\[S(f, g) = \frac{L}{\mathrm{LT}(f)} \cdot f - \frac{L}{\mathrm{LT}(g)} \cdot g.\]

Par construction, les termes dominants se simplifient : \(\mathrm{LM}(S(f, g)) < L\).

Exemple 27 (Calcul d’un \(S\)-polynôme)

Soient \(f = X^2 + Y\) et \(g = XY + 1\) avec l’ordre grlex.

\(\mathrm{LM}(f) = X^2\), \(\mathrm{LM}(g) = XY\), \(L = \mathrm{lcm}(X^2, XY) = X^2 Y\).

\[S(f, g) = \frac{X^2 Y}{X^2} \cdot (X^2 + Y) - \frac{X^2 Y}{XY} \cdot (XY + 1) = Y(X^2 + Y) - X(XY + 1) = Y^2 - X.\]

Ce \(S\)-polynôme capture l’annulation mutuelle des termes dominants et engendre de nouvelles relations dans l’idéal \((f, g)\).

Bases de Gröbner

Définition 38 (Base de Gröbner)

Soit \(I \subset K[X_1, \ldots, X_n]\) un idéal non nul et \(>\) un ordre monomial. Un ensemble fini \(G = \{g_1, \ldots, g_t\} \subset I\) est une base de Gröbner de \(I\) si

\[\mathrm{LT}(I) = \bigl(\mathrm{LT}(g_1), \ldots, \mathrm{LT}(g_t)\bigr).\]

Autrement dit, pour tout \(f \in I\) non nul, il existe \(g_i \in G\) tel que \(\mathrm{LT}(g_i) \mid \mathrm{LT}(f)\).

Théorème 21 (Existence et unicité du reste)

Soit \(G = \{g_1, \ldots, g_t\}\) une base de Gröbner de \(I\). Pour tout \(f \in K[X_1, \ldots, X_n]\), il existe un unique \(r \in K[X_1, \ldots, X_n]\) tel que :

1. \(f - r \in I\)

2. Aucun monôme de \(r\) n’est divisible par \(\mathrm{LT}(g_1), \ldots, \mathrm{LT}(g_t)\)

Ce polynôme \(r\) est le reste normal de \(f\) par rapport à \(G\), noté \(\overline{f}^G\).

Proof. Existence : l’algorithme de division de \(f\) par \(G\) termine toujours (l’ordre monomial est un bon ordre) et produit un reste \(r\) vérifiant les conditions.

Unicité : Supposons \(r\) et \(r'\) deux tels restes. Alors \(r - r' \in I\). Si \(r \neq r'\), alors \(\mathrm{LT}(r - r')\) est divisible par \(\mathrm{LT}(g_i)\) pour un certain \(i\) (car \(G\) est une base de Gröbner). Mais \(\mathrm{LT}(r - r')\) est un monôme de \(r\) ou de \(r'\), et aucun monôme de \(r\) ni de \(r'\) n’est divisible par les \(\mathrm{LT}(g_i)\) par hypothèse. Contradiction.

Théorème 22 (Critère de Buchberger)

Soit \(G = \{g_1, \ldots, g_t\}\) une base de l’idéal \(I = (g_1, \ldots, g_t)\). Alors \(G\) est une base de Gröbner de \(I\) si et seulement si pour tous \(i \neq j\),

\[\overline{S(g_i, g_j)}^G = 0.\]

Proof. (\(\Leftarrow\)) Si tous les \(S\)-polynômes se réduisent à \(0\) par \(G\), on montre (par récurrence sur l’ordre monomial) que tout \(f \in I\) a un reste nul par \(G\). Plus précisément, si \(f = \sum c_i g_i \in I\), on exprime \(\mathrm{LT}(f)\) et on utilise les hypothèses sur les \(S\)-polynômes pour montrer que \(\mathrm{LT}(f) \in (\mathrm{LT}(g_1), \ldots, \mathrm{LT}(g_t))\).

(\(\Rightarrow\)) Si \(G\) est une base de Gröbner, alors \(S(g_i, g_j) \in I\), donc son reste par \(G\) est \(0\).

Corollaire 7 (Appartenance à un idéal)

Soit \(G\) une base de Gröbner de \(I\). Alors \(f \in I\) si et seulement si \(\overline{f}^G = 0\). Ce critère rend décidable le problème d’appartenance à un idéal.

Algorithme de Buchberger

Définition 39 (Algorithme de Buchberger)

L”algorithme de Buchberger calcule une base de Gröbner de l’idéal \((f_1, \ldots, f_s)\) :

1. Initialiser \(G \leftarrow \{f_1, \ldots, f_s\}\).

2. Pour chaque paire \(\{g_i, g_j\} \subset G\) non encore examinée, calculer \(r = \overline{S(g_i, g_j)}^G\).

3. Si \(r \neq 0\), ajouter \(r\) à \(G\) et reprendre depuis l’étape 2 avec les nouvelles paires.

4. Terminer quand tous les \(S\)-polynômes se réduisent à \(0\).

L’algorithme termine en raison du lemme de Dickson : toute suite croissante d’idéaux monomiaux dans \(K[X_1, \ldots, X_n]\) est stationnaire.

Définition 40 (Base de Gröbner réduite)

Une base de Gröbner \(G\) de \(I\) est réduite si :

1. \(\mathrm{LC}(g) = 1\) pour tout \(g \in G\) (polynômes unitaires)

2. Pour tout \(g \in G\), aucun monôme de \(g\) n’est divisible par \(\mathrm{LT}(g')\) pour \(g' \in G\), \(g' \neq g\)

La base de Gröbner réduite d’un idéal \(I\) est unique pour un ordre monomial fixé.

Exemple 28 (Base de Gröbner de \(I = (X^2 + Y, \; XY + 1)\))

Travaillons dans \(\mathbb{Q}[X, Y]\) avec l’ordre grlex, \(X > Y\).

\(f_1 = X^2 + Y\), \(f_2 = XY + 1\).

\(S(f_1, f_2) = \frac{X^2 Y}{X^2}(X^2+Y) - \frac{X^2 Y}{XY}(XY+1) = Y(X^2+Y) - X(XY+1) = Y^2 - X\).

Réduction de \(Y^2 - X\) par \(\{f_1, f_2\}\) : \(\mathrm{LT}(Y^2 - X) = Y^2\), non divisible par \(X^2\) ni par \(XY\). Reste : \(f_3 = Y^2 - X\).

Calculons \(S(f_1, f_3)\) et \(S(f_2, f_3)\) : après réduction, les deux \(S\)-polynômes se réduisent à \(0\).

Base de Gröbner : \(G = \{X^2 + Y, \; XY + 1, \; Y^2 - X\}\).

Show code cell source

Hide code cell source

fig, axes = plt.subplots(2, 1, figsize=(10, 12))

# --- Visualisation : étapes de Buchberger sur I = (X^2+Y, XY+1) ---
ax = axes[0]
ax.axis("off")
ax.set_xlim(0, 10)
ax.set_ylim(-0.5, 5)
ax.set_title("Algorithme de Buchberger sur $I = (X^2+Y, XY+1) \\subset \\mathbb{Q}[X,Y]$\n(ordre grlex)", fontsize=10)

buchberger_steps = [
    ("Étape 0", "$G = \\{f_1 = X^2+Y,\\ f_2 = XY+1\\}$", "initialisation"),
    ("Étape 1", "$S(f_1, f_2) = Y^2 - X \\neq 0$", "ajouter $f_3 = Y^2 - X$"),
    ("Étape 2", "$S(f_1, f_3) \\overset{G}{\\rightarrow} 0$", "OK, pas d'ajout"),
    ("Étape 3", "$S(f_2, f_3) \\overset{G}{\\rightarrow} 0$", "OK, pas d'ajout"),
    ("Résultat", "$G = \\{X^2+Y,\\ XY+1,\\ Y^2-X\\}$", "base de Gröbner"),
]

step_colors = ["#d0e8f5", "#f5e0d0", "#e8f5d0", "#e8f5d0", "#d5f5e3"]
for i, (step, expr, comment) in enumerate(buchberger_steps):
    y = 4 - i * 0.85
    ax.add_patch(plt.Rectangle((0.1, y - 0.35), 9.8, 0.7,
                               color=step_colors[i], alpha=0.6, lw=0))
    ax.text(0.3, y, f"\\textbf{{{step}}}", fontsize=9, va="center", color="navy")
    ax.text(2.8, y, expr, fontsize=9, va="center")
    ax.text(7.5, y, comment, fontsize=8, va="center", color="gray", style="italic")

# Flèches entre étapes
for i in range(len(buchberger_steps) - 1):
    y_from = 4 - i * 0.85 - 0.35
    y_to = 4 - (i + 1) * 0.85 + 0.35
    ax.annotate("", xy=(5, y_to), xytext=(5, y_from),
                arrowprops=dict(arrowstyle="->", color="steelblue", lw=1.2))

# Encadrer le résultat
ax.add_patch(plt.Rectangle((0.1, 4 - 4 * 0.85 - 0.38), 9.8, 0.76,
                            fill=False, edgecolor="seagreen", lw=2.5))

# --- Visualisation : variété V(I) dans R^2 ---
ax2 = axes[1]
x_vals = np.linspace(-2.5, 2.5, 600)
y_vals = np.linspace(-2.5, 2.5, 600)
X_grid, Y_grid = np.meshgrid(x_vals, y_vals)

# f1 = X^2 + Y = 0  ⟺  Y = -X^2
Z1 = X_grid**2 + Y_grid
# f2 = XY + 1 = 0  ⟺  Y = -1/X
Z2 = X_grid * Y_grid + 1

contour1 = ax2.contour(X_grid, Y_grid, Z1, levels=[0], colors="steelblue", linewidths=2)
contour2 = ax2.contour(X_grid, Y_grid, Z2, levels=[0], colors="tomato", linewidths=2)

# Points d'intersection (solutions du système)
# X^2 + Y = 0 et XY + 1 = 0 : Y = -X^2, donc X(-X^2)+1=0, -X^3+1=0, X=1, Y=-1
# Et les racines complexes de X^3=1 : seulement X=1 réel
ax2.scatter([1], [-1], s=150, color="gold", zorder=5, label="Solution réelle $(1, -1)$")
ax2.annotate("$(1,{-1})$", xy=(1, -1), xytext=(1.3, -0.5), fontsize=9,
             arrowprops=dict(arrowstyle="->", color="gold"))

ax2.axhline(0, color="k", lw=0.5, alpha=0.5)
ax2.axvline(0, color="k", lw=0.5, alpha=0.5)
ax2.set_xlabel("$X$")
ax2.set_ylabel("$Y$")
ax2.set_title("Variété $V(I)$ dans $\\mathbb{R}^2$\n$f_1 = X^2+Y$ (bleu), $f_2 = XY+1$ (rouge)", fontsize=10)

from matplotlib.lines import Line2D
legend_elements = [
    Line2D([0], [0], color="steelblue", lw=2, label="$X^2+Y=0$"),
    Line2D([0], [0], color="tomato", lw=2, label="$XY+1=0$"),
    Line2D([0], [0], marker="o", color="w", markerfacecolor="gold",
           markersize=10, label="Solution réelle $(1,-1)$"),
]
ax2.legend(handles=legend_elements, fontsize=9)
ax2.set_xlim(-2.5, 2.5)
ax2.set_ylim(-2.5, 2.5)

plt.show()

Applications des bases de Gröbner

Théorème 23 (Théorème d’élimination)

Soit \(I \subset K[X_1, \ldots, X_n]\) un idéal et \(G\) une base de Gröbner de \(I\) pour l’ordre lex avec \(X_1 > X_2 > \cdots > X_n\). Pour tout \(1 \leq k \leq n\), l’ensemble

\[I_k = I \cap K[X_{k+1}, \ldots, X_n]\]

est un idéal appelé \(k\)-ème idéal d’élimination de \(I\), et

\[G_k = G \cap K[X_{k+1}, \ldots, X_n]\]

est une base de Gröbner de \(I_k\).

Proof. L’ordre lex a la propriété que si \(X^\alpha\) contient \(X_1, \ldots, X_k\), alors \(X^\alpha > X^\beta\) pour tout \(\beta\) n’impliquant que \(X_{k+1}, \ldots, X_n\). Cela garantit que les éléments de \(G\) qui n’impliquent que \(X_{k+1}, \ldots, X_n\) ont leurs termes dominants dans \(K[X_{k+1}, \ldots, X_n]\), et forment une base de Gröbner de \(I_k\).

Proposition 12 (Résolution de systèmes polynomiaux par élimination)

La résolution d’un système polynomial \(\{f_1 = 0, \ldots, f_s = 0\}\) avec \(f_i \in K[X_1, \ldots, X_n]\) se ramène à la triangulation par élimination successive :

1. Calculer une base de Gröbner \(G\) de \(I = (f_1, \ldots, f_s)\) pour l’ordre lex.

2. \(G_1 = G \cap K[X_2, \ldots, X_n]\) donne un système en \(n-1\) variables.

3. Répéter jusqu’à obtenir \(G_{n-1} \subset K[X_n]\), résoudre en \(X_n\), puis remonter.

Cette méthode généralise la substitution successive et l’élimination gaussienne au cadre polynomial.

Exemple 29 (Résolution par élimination)

Reprenons \(I = (X^2 + Y, XY + 1) \subset \mathbb{Q}[X, Y]\) avec la base de Gröbner \(G = \{X^2+Y, XY+1, Y^2-X\}\) en ordre lex (\(X > Y\)).

L’idéal d’élimination \(I_1 = I \cap \mathbb{Q}[Y]\) est engendré par les éléments de \(G\) ne dépendant que de \(Y\). On vérifie que \(Y^3 + 1 \in I\) : en effet, \(Y \cdot (X^2+Y) - X \cdot (XY+1) = Y^2 - X\), puis \(Y \cdot (Y^2-X) + X \cdot (X^2+Y) - X^2 \cdot (XY+1)\) donne \(Y^3+1\) après simplification. Ainsi \(I_1 = (Y^3+1)\) et les valeurs de \(Y\) sont les racines de \(Y^3 + 1 = 0\), soit \(Y = -1\) sur \(\mathbb{R}\). On remonte : \(Y = -1 \implies X^2 = 1 \implies X = \pm 1\), puis \(XY + 1 = 0 \implies X = 1\). Solution unique réelle : \((X, Y) = (1, -1)\).

Proposition 13 (Base de Gröbner et dimension)

Soit \(I \subset K[X_1, \ldots, X_n]\) un idéal et \(G\) une base de Gröbner de \(I\). Les monômes standard (ceux non divisibles par aucun \(\mathrm{LT}(g_i)\)) forment une base de l’espace vectoriel \(K[X_1, \ldots, X_n] / I\).

En particulier, l’idéal \(I\) est zéro-dimensionnel (la variété \(V(I)\) est finie sur \(\bar{K}\)) si et seulement si, pour chaque variable \(X_i\), il existe un monôme \(X_i^{m_i}\) qui est un terme dominant d’un élément de \(G\).

Proof. Les monômes standard sont les représentants canoniques des classes dans \(K[X_1, \ldots, X_n] / I\), en vertu de l’unicité du reste normal par rapport à une base de Gröbner. La condition de dimension zéro découle du théorème d’élimination et du fait que les idéaux d’élimination successifs doivent être non triviaux dans \(K[X_i]\).

Résumé

Concept	Propriété clé
\(K[X_1,\ldots,X_n]\)	Anneau factoriel ; non principal pour \(n \geq 2\)
Ordre monomial	Ordre total compatible avec \(\times\), bon ordre ; exemples : lex, grlex, grevlex
\(\mathrm{LT}(f)\), \(\mathrm{LM}(f)\), \(\mathrm{LC}(f)\)	Terme, monôme, coefficient dominants pour un ordre fixé
Division multivariée	Quotients \(q_i\) et reste \(r\) tels que \(f = \sum q_i f_i + r\) ; le reste dépend de l’ordre des \(f_i\)
\(S\)-polynôme	\(S(f,g) = \frac{\mathrm{lcm}(\mathrm{LM}(f),\mathrm{LM}(g))}{\mathrm{LT}(f)} f - \frac{\mathrm{lcm}(\mathrm{LM}(f),\mathrm{LM}(g))}{\mathrm{LT}(g)} g\)
Base de Gröbner	\(\langle \mathrm{LT}(g_1),\ldots,\mathrm{LT}(g_t) \rangle = \mathrm{LT}(I)\) ; le reste est unique
Critère de Buchberger	\(G\) base de Gröbner \(\iff\) \(\overline{S(g_i,g_j)}^G = 0\) pour tous \(i \neq j\)
Base réduite	Polynômes unitaires, pas de monôme divisible par un \(\mathrm{LT}(g_j)\) étranger ; unique
Idéal d’élimination	\(I_k = I \cap K[X_{k+1},\ldots,X_n]\) ; base de Gröbner en ordre lex donne base de \(I_k\)
Appartenance à \(I\)	\(f \in I \iff \overline{f}^G = 0\) pour toute base de Gröbner \(G\) de \(I\)
Dimension de \(K[\mathbf{X}]/I\)	Les monômes standard (non réductibles) forment une base de l’espace quotient