\ifx\danslelivre\undefined
\documentclass[9pt]{../configuration/smfart}
\input{../configuration/commun}
\input{../configuration/smf}
\input{../configuration/adresse}
\input{../configuration/gadgets}
\input{../configuration/francais}
\input{../configuration/numerotation}
\input{../configuration/formules}
\input{../configuration/encoredesmacros}

\usepackage{stmaryrd}
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
%\usepackage{tikz}
%\usetikzlibrary{matrix,arrows}

\externaldocument{spectre}
\externaldocument{extensions-algebriques}
\externaldocument{calculs-galois}

\synctex=1

\title{Bases de Gr\"{o}bner et applications}
 
\begin{document}
\maketitle
\setcounter{tocdepth}{2}
\tableofcontents
\else
\chapter{Bases de Gröbner et applications}
\fi

\newcommand{\initial}{\mathop{\mathrm{in}}}


\section{Bases de Gröbner}

\subsection{Motivations}\label{section-motivations-groebner}

\subsubsection{Le cas d'une seule variable} Les idéaux de l'anneau
$k[Z]$ des polynômes univariés sont bien compris puisque cet anneau
est principal : pour tout idéal $I$ de $k[Z]$, il existe un unique
polynôme $f$ unitaire ou nul tel que $I = (f)$.  De plus, on dispose
d'une base évidente du $k$-espace vectoriel $k[Z]/I$, à savoir les
monômes $1,Z,Z^2,\ldots,Z^{\ell-1}$ où $\ell$ est le degré de $f$ si
ce dernier n'est pas nul (pour $I = (0)$ on peut prendre tous les
$Z^i$ mais ce cas ne nous préoccupera guère).

Parmi les opérations algorithmiquement faciles à effectuer,
mentionnons notamment les suivantes :
\begin{itemize}
\item donné un idéal $I = (f_1,\ldots,f_r)$ engendré par plusieurs
  éléments $f_i$ de $k[Z]$, écrire cet idéal sous la forme standard,
  c'est-à-dire $I = (f)$ avec $f$ unitaire (il suffit de prendre pour
  $f$ le pgcd de $f_1,\ldots,f_s$, ce qui se calcule avec l'algorithme
  d'Euclide) ; on pourra, de plus, explicitement convertir ce nouveau
  générateur $f$ en fonction des anciens, c'est-à-dire trouver
  $g_1,\ldots,g_r$ tels que $f = g_1 f_1 + \cdots + g_r f_r$ (avec
  l'algorithme d'Euclide étendu) ;
\item une fois fixé $I = (f)$, et connaissant un $h \in k[Z]$, décider
  si $h \in I$ ou non ; si oui, trouver un $g$ tel que $h = g f$ ; si
  non, décomposer $h$ modulo $I$ dans la base choisie de $k[Z]/I$ (il
  suffit d'effectuer la division euclidienne de $h$ par $f$ et de
  considérer son quotient ou son reste selon le problème étudié) ;
\item effectuer les opérations algébriques dans l'anneau quotient
  $k[Z]/I$.
\end{itemize}

Si de plus on suppose qu'on sait effectuer la factorisation des
polynômes de $k[Z]$, on peut alors tester si $k[Z]/(f)$ est un
\emph{corps}, c'est-à-dire si $I = (f)$ est un idéal maximal, puisque
cela revient précisément à tester si $f$ est irréductible.  (Dans ce
cas, $k[Z]/(f)$ est, bien entendu, le corps de rupture de $f$ sur $k$,
c'est notamment pour pouvoir effectuer des calculs dans celui-ci que
la question algorithmique nous préoccupe.)

\subsubsection{} Toutes ces questions deviennent beaucoup moins
évidentes lorsqu'on a affaire à un anneau $k[Z_1,\ldots,Z_d]$ de
polynômes multivariés.  Les \textbf{bases de Gröbner}, parfois aussi
appelées \textbf{bases standard} (sous différentes variantes) ont pour
but notamment d'y répondre et, de façon générale, de fournir les
outils nécessaires à la manipulation algorithmique des idéaux de
$k[Z_1,\ldots,Z_d]$.

La clé de la définition des bases de Gröbner consiste à trouver un
concept multivarié analogue à celui de terme dominant (c'est-à-dire,
de plus haut degré) d'un polynôme univarié.  L'ordre de divisibilité
sur les monômes (cf. ci-dessous) ne fournit qu'un ordre partiel,
tandis que la seule comparaison du degré total ne fournit qu'un
préordre (deux monômes peuvent évidemment avoir le même degré total
sans être égaux) : pour pouvoir parler de bases de Gröbner on devra au
préalable avoir fait le choix d'un ordre total sur les monômes
vérifiant certaines propriétés de compatibilité avec la structure
algébrique (on parlera d'ordre « admissible » ci-dessous), et toutes
les définitions seront relatives à ce choix d'un ordre monomial.

Pour se faire une idée du contexte dans lequel on utilisera ces
notions, on pourra notamment penser au cas, qui sera étudié plus
précisément en \ref{section-algebre-de-decomposition-universelle}
ci-dessous, où $f \in k[X]$ est un polynôme univarié irréductible et
séparable, disons $f = X^d + a_1 X^{d-1} + \cdots + a_d$ et où on
considère l'idéal $I$ de $k[Z_1,\ldots,Z_d]$ engendré par les
relations $e_i = (-1)^i a_i$ où $e_i$ désigne le $i$-ième polynôme
symétrique élémentaire en $Z_1,\ldots,Z_d$ : autrement dit, ces
relations imposent aux $Z_1,\ldots,Z_d$ d'être les racines distinctes,
dans un certain ordre, de $f$ (remarquons d'ailleurs que $f(Z_i) \in
I$ pour tout $i$), et il s'avère que l'algèbre $k[Z_1,\ldots,Z_d]/I$
est de dimension finie, réduite, et est un produit de copies du corps
de décomposition de $f$ qui s'écrivent de la forme
$k[Z_1,\ldots,Z_d]/J$ avec $J \supseteq I$ un idéal dont le calcul
équivaut essentiellement au calcul du groupe de Galois de $f$.

\subsection{Monômes et idéaux monomiaux}

On appelle \textbf{monôme} de $k[Z_1,\ldots,Z_d]$ un polynôme de la
forme $Z_1^{\ell_1}\cdots Z_d^{\ell_d}$.  On dit qu'un monôme
$Z_1^{\ell_1}\cdots Z_d^{\ell_d}$ \textbf{divise} un monôme
$Z_1^{\ell'_1}\cdots Z_d^{\ell'_d}$ lorsque $\ell_i \leq \ell'_i$ pour
tout $i$ (c'est bien la relation de divisibilité dans l'anneau
factoriel $k[Z_1,\ldots,Z_d]$, restreinte aux monômes, et le rapport
entre les deux monômes est alors lui-même un monôme).  Un
\textbf{terme} est un monôme multiplié par une constante
(c'est-à-dire, un élément de $k$) non nulle : on parle alors du monôme
\emph{de} ce terme.  Tout polynôme s'écrit de façon unique comme somme
de termes dont les monômes sont distincts : ce sont les termes de
(=intervenant dans) ce polynôme.

Commençons par la remarque suivante, qui est évidente, mais
essentielle :
\begin{proposition2}\label{divisibilite-des-monomes}
Si $s_1,\ldots,s_r$ sont des monômes de $k[Z_1,\ldots,Z_d]$, alors
pour chaque terme $c s$ de $g_1 s_1 + \cdots + g_r s_r$ (où
$g_1,\ldots,g_r \in k[Z_1,\ldots,Z_d]$) le monôme $s$ de ce terme est
divisible par l'un des $s_i$.
\end{proposition2}
\begin{proof}
En développant l'écriture $g_1 s_1 + \cdots + g_r s_r$, puisque la
somme comporte le terme $c s$, au moins un des facteurs comporte un
terme dont le monôme est $s$, ce qui montre bien que $s$ est divisible
par un des $s_i$.
\end{proof}

\begin{corollaire2}\label{composition-ideaux-monomiaux}
Si $s_1,\ldots,s_r$ sont des monômes de $k[Z_1,\ldots,Z_d]$, l'idéal
qu'ils engendrent est exactement l'idéal des polynômes dont le monôme
de chaque terme est divisible par un des $s_i$.
\end{corollaire2}
\begin{proof}
On vient de montrer que si $f$ est dans $(s_1,\ldots,s_r)$ alors le
monôme de chaque terme de $f$ est divisible par un des $s_i$.
Réciproquement, si c'est le cas, $f$ est somme de termes multiples
des $s_i$, qui appartiennent donc à l'idéal engendré par les $s_i$.
\end{proof}

\begin{corollaire2}\label{equivalences-ideaux-monomiaux}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$, les deux propriétés
suivantes sont équivalentes :
\begin{itemize}
\item l'idéal $I$ est engendré par des monômes (ou : par tous ses monômes),
\item tout terme d'un élément de $I$ est élément de $I$.
\end{itemize}
\end{corollaire2}
\begin{proof}
Le fait que la première propriété implique la deuxième découle
trivialement du corollaire précédent (si $I = (s_1,\ldots,s_r)$ et
si $f \in I$, alors tout terme de $f$ est divisible par un des $s_i$
donc, en particulier, appartient à $I$).

Réciproquement si $I$ vérifie la deuxième propriété, et si
$f_1,\ldots,f_t$ engendrent $I$, appelons $s_1,\ldots,s_r$ l'ensemble
de tous les monômes intervenant dans un des $f_i$ : l'hypothèse
assure que les $s_i$ appartiennent à $I$, et manifestement ils
engendrent les $f_i$, donc engendrent tout $I$, donc $f =
(s_1,\ldots,s_r)$, ce qui démontre la première propriété.
\end{proof}

On appelle \textbf{idéal monomial} un idéal de $k[Z_1,\ldots,Z_d]$ qui
vérifie les propriétés équivalentes énoncées ci-dessus.



%
\subsection{Ordres admissibles sur les monômes}

\begin{definition2}\label{definition-ordres-admissibles}
On appelle \textbf{ordre admissible} (ou \textbf{ordre monomial}) sur
les monômes de $k[Z_1,\ldots,Z_d]$ une relation d'ordre total
$\preceq$ sur les monômes de ce dernier telle que :
\begin{itemize}
\item $1 \preceq s$ pour tout monôme $s$, et
\item si $s_1 \preceq s_2$ et $s$ est un monôme quelconque, alors $s
  s_1 \preceq s s_2$.
\end{itemize}
(On notera souvent abusivement $c s \preceq c' s'$, lorsque $cs, c's'$
sont deux termes, pour signifier que leurs monômes vérifient $s
\preceq s'$.)

Si de plus l'ordre vérifie la propriété que $\deg s < \deg s'$
implique $s \preceq s'$ (autrement dit, si l'ordre considéré raffine
l'ordre partiel donné par le degré total), on dit qu'il est
\textbf{gradué}.
\end{definition2}

\begin{proposition2}\label{proprietes-ordres-admissibles}
Si $\preceq$ est un ordre admissible sur les monômes de
$k[Z_1,\ldots,Z_d]$, alors
\begin{itemize}
\item si $s_1 | s_2$ alors $s_1 \preceq s_2$,
\item $\preceq$ est un bon ordre (c'est-à-dire : tout ensemble non
  vide de monômes a un plus petit élément pour $\preceq$, ou de façon
  équivalente, il n'y a pas de suite infinie strictement décroissante
  de monômes pour $\preceq$).
\end{itemize}
\end{proposition2}
\begin{proof}
Le premier point est évident : si $s_2 = s s_1$ alors $1 \preceq s$
entraîne $s_1 \preceq s s_1 = s_2$.  Montrons le second : si $S$ est
un ensemble de monômes, soit $I$ l'idéal qu'ils engendrent ; comme
$k[Z_1,\ldots,Z_d]$ est noethérien, il existe un sous-ensemble fini
$S_0 \subseteq S$ qui engendre le même idéal $I$.  Soit $s$ le plus
petit élément de $S_0$ : on prétend que $s$ est aussi le plus petit
élément de $S$.  En effet, si $s' \in S$ alors $s' \in I$ donc $s'$
s'écrit comme combinaison d'éléments de $S_0$, mais alors
d'après \ref{divisibilite-des-monomes}, $s'$ est simplement multiple d'un
élément de $S_0$, et d'après le premier point, $s\preceq s'$, ce qui
conclut.
\end{proof}

Lorsque $d=1$, le seul ordre admissible sur les monômes est évidemment
celui donné par $Z^\ell \preceq Z^{\ell'}$ ssi $\ell \leq \ell'$
(l'ordre par le degré).

\begin{definition2}
Une fois fixé un ordre admissible $\preceq$ sur les monômes, si $f \in
k[Z_1,\ldots,Z_d]$ est non nul, on note $\initial_{\preceq}(f)$ (ou
simplement $\initial(f)$ si l'ordre est sous-entendu) et on appelle
\textbf{terme initial} (ou \textbf{terme de tête}) de $f$ le terme au
\emph{plus grand} monôme pour l'ordre en question, et le monôme
lui-même est appelé \textbf{monôme initial}, ou monôme de tête,
de $f$.  Si $f=0$ on pose (un peu abusivement) $\initial(f) = 0$.
\end{definition2}

Lorsque $d=1$, pour le seul ordre admissible sur les monômes,
$\initial(f)$ est simplement le terme dominant de $f$.

Le $(\ell_1,\ldots,\ell_d)$ pour lequel le monôme initial de $f$
s'écrive $Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ s'appelle parfois
\textbf{multidegré} de $f$ ; si on se permet d'identifier le monoïde
multiplicatif des monômes avec le monoïde $\NN^d$ des multidegrés, on
peut considérer « multidegré » comme simplement synonyme de « monôme
  initial ».

\begin{remarque2}
Si $f,g$ sont deux polynômes, alors $\initial(gf) =
\initial(g)\,\initial(f)$ : en effet, les propriétés d'un ordre
admissible (\ref{definition-ordres-admissibles}) font que le monôme
d'aucun terme de $gf$ ne peut être plus grand que celui produit du
terme de tête de $g$ et de celui de $f$.

En particulier, si $cs$ est un terme (avec $c \in k$ une constante et
$s$ un monôme), alors pour tout polynôme $f$ on a $\initial(csf) =
cs\initial(f)$.
\end{remarque2}

\medbreak

Donnons maintenant quelques exemples importants d'ordres admissibles
sur les monômes.  On supposera toujours, quitte à renuméroter les
variables, que $Z_1 \preceq Z_2 \preceq \cdots \preceq Z_d$.

\subsubsection{L'ordre lexicographique (pur)}  L'\textbf{ordre
  lexicographique} est défini par $Z_1^{\ell_1} \cdots Z_d^{\ell_d}
\mathrel{\preceq_{\mathtt{lex}}} Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$
ssi $\ell_i < \ell'_i$ pour le \emph{plus grand} $i$ tel que $\ell_i
\neq \ell'_i$.  Autrement dit, l'ordre lexicographique compare deux
monômes en comparant leur degré en $Z_d$ ou, en cas d'égalité, de
$Z_{d-1}$ puis $Z_{d-2}$ et ainsi de suite jusqu'à $Z_1$ (la
comparaison lexicographique se fait dans cet ordre, c'est-à-dire en
donnant le poids le plus fort à l'exposant de la dernière variable, en
raison de notre choix de l'ordre des variables, $Z_1 \preceq Z_2
\preceq \cdots \preceq Z_d$ ; plus généralement, tout ordre total sur
l'ensemble des variables définit un unique ordre lexicographique pur
associé).

Pour cet ordre on a donc $1 \preceq Z_1 \preceq Z_1^2 \preceq Z_1^3
\preceq \cdots \preceq Z_2 \preceq Z_1 Z_2 \preceq Z_1^2 Z_2 \preceq
\cdots \preceq Z_2^2 \preceq Z_1 Z_2^2 \preceq \cdots \preceq Z_2^3
\preceq \cdots \preceq Z_3 \preceq Z_1 Z_3 \preceq Z_1^2 Z_3 \preceq
\cdots \preceq Z_2 Z_3 \preceq Z_1 Z_2 Z_3 \preceq \cdots \preceq
Z_3^2 \preceq \cdots \preceq Z_4 \preceq \cdots$ (l'ordinal associé à
ce bon ordre sur les monômes de $k[Z_1,\ldots,Z_d]$ vaut $\omega^d$).

\begin{proposition2}\label{caracterisation-ordre-lexicographique-pur}
Si $\initial_{\mathtt{lex}}(f) \in k[Z_1,\ldots,Z_t]$ (pour un $t\leq
d$) alors $f \in k[Z_1,\ldots,Z_t]$.  De plus, cette propriété
caractérise l'ordre lexicographique (parmi les ordres admissibles).
\end{proposition2}
\begin{proof}
La première affirmation est claire : tous les monômes plus petits,
pour l'ordre lexicographique, qu'un monôme dans $k[Z_1,\ldots,Z_t]$,
sont eux-mêmes dans $k[Z_1,\ldots,Z_t]$.

Supposons maintenant qu'un ordre admissible $\preceq$ soit tel que si
$\initial_{\preceq}(f) \in k[Z_1,\ldots,Z_t]$ (pour un $t\leq d$)
alors $f \in k[Z_1,\ldots,Z_t]$ : ceci signifie que tout monôme
faisant intervenir (à un degré non nul) une variable $Z_i$ avec $i>t$
est strictement supérieur à tout monôme ne faisant intervenir que
$Z_1,\ldots,Z_t$.  Considérons $s = Z_1^{\ell_1} \cdots Z_d^{\ell_d}$
et $s' = Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$ deux monômes.  Soit $i$
le \emph{plus grand} possible tel que $\ell_i \neq \ell'_i$, et disons
que $\ell_i < \ell'_i$.  Posons $\ell^0_j = \min(\ell_j,\ell'_j)$, de
sorte que $s^0 = Z_1^{\ell^0_1} \cdots Z_d^{\ell^0_d}$ soit le plus
grand diviseur commun de $s$ et $s'$, disons $s = s^0 s^1$ et $s' =
s^0 s^{1\prime}$.  La définition de $i$ assure que $s^{1\prime}$ fait
intervenir la variable $Z_i$ alors que $s^1 \in
k[Z_1,\ldots,Z_{i-1}]$.  La propriété sur $\preceq$ montre que $s^1
\preceq s^{1\prime}$, donc $s \preceq s'$.  On a donc montré que si
$s,s'$ sont dans un certain ordre pour l'ordre lexicographique, ils le
sont aussi pour l'ordre $\preceq$ : c'est bien que ces deux ordres
coïncident.
\end{proof}

\subsubsection{L'ordre lexicographique gradué}  L'\textbf{ordre
  lexicographique par degré} ou \textbf{ordre lexicographique gradué}
est défini par $Z_1^{\ell_1} \cdots Z_d^{\ell_d}
\mathrel{\preceq_{\mathtt{glex}}} Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$
ssi $\sum \ell_i < \sum \ell'_i$ ou $\sum \ell_i = \sum \ell'_i$ et
$\ell_i < \ell'_i$ pour le \emph{plus grand} $i$ tel que $\ell_i \neq
\ell'_i$.  Autrement dit, les monômes sont classés en priorité par
degré total puis, en cas d'égalité, par l'ordre lexicographique pur
défini ci-dessus, c'est-à-dire en donnant le plus de poids à la plus
grande variable.  (De même que ci-dessus, nous avons fixé $Z_1 \preceq
Z_2 \preceq \cdots \preceq Z_d$, mais plus généralement, il y a un
unique ordre lexicographique gradué pour chaque ordre total sur les
variables.)

Pour cet ordre, on a donc $1 \preceq Z_1 \preceq Z_2 \preceq Z_3
\preceq Z_4 \preceq \cdots \preceq Z_1^2 \preceq Z_1 Z_2 \preceq Z_2^2
\preceq Z_1 Z_3 \preceq Z_2 Z_3 \preceq Z_3^2 \preceq \cdots \preceq
Z_1^3 \preceq Z_1^2 Z_2 \preceq Z_1 Z_2^2 \preceq Z_2^3 \preceq Z_1^2
Z_3 \preceq Z_1 Z_2 Z_3 \preceq \cdots$ (l'ordinal associé à ce bon
ordre sur les monômes de $k[Z_1,\ldots,Z_d]$ vaut $\omega$ comme c'est
le cas pour tout ordre gradué).

\begin{proposition2}\label{caracterisation-ordre-lexicographique-gradue}
L'ordre $\mathrel{\preceq_{\mathtt{glex}}}$ est gradué au sens
de \ref{definition-ordres-admissibles}, et si
$\initial_{\mathtt{glex}}(f) \in k[Z_1,\ldots,Z_t]$ (pour un $t\leq
d$) avec $f$ un polynôme homogène, alors $f \in k[Z_1,\ldots,Z_t]$.
De plus, ces propriétés caractérisent l'ordre lexicographique gradué
(parmi les ordres admissibles).
\end{proposition2}
\begin{proof}
Le fait que l'ordre $\mathrel{\preceq_{\mathtt{glex}}}$ soit gradué
est évident sur sa définition ; pour ce qui est de la deuxième
propriété, il suffit de remarquer que tous les monômes plus petits,
pour l'ordre lexicographique gradué, et de même degré, qu'un monôme
dans $k[Z_1,\ldots,Z_t]$, sont eux-mêmes dans $k[Z_1,\ldots,Z_t]$
(puisque, étant de même degré, ils sont plus petits pour l'ordre
lexicographique pur).

Pour montrer que les propriétés énoncées caractérisent l'ordre
lexicographique gradué, on procède comme
en \ref{caracterisation-ordre-lexicographique-pur} : soit $\preceq$ un
ordre admissible gradué tel que si $\initial_{\preceq}(f) \in
k[Z_1,\ldots,Z_t]$ (pour un $t\leq d$) avec $f$ homogène alors $f \in
k[Z_1,\ldots,Z_t]$ ; ceci signifie que tout monôme faisant intervenir
(à un degré non nul) une variable $Z_i$ avec $i>t$ est strictement
supérieur à tout monôme du même degré ne faisant intervenir que
$Z_1,\ldots,Z_t$.  Si $s = Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et $s' =
Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$ sont deux monômes de même degré
total tels que $s \mathrel{\preceq_{\mathtt{glex}}} s'$ (donc, vu que
le degré total est le même, $s \mathrel{\preceq_{\mathtt{lex}}} s'$),
la démonstration utilisée dans le cas de l'ordre lexicographique pur
montre que $s \preceq s'$, et ceci démontre que $\preceq$ coïncide
avec l'ordre $\mathrel{\preceq_{\mathtt{glex}}}$.
\end{proof}

\subsubsection{L'ordre lexicographique inversé gradué} L'\textbf{ordre
  lexicographique inversé par degré} (ou \textbf{...gradué}) est
défini par $Z_1^{\ell_1} \cdots Z_d^{\ell_d}
\mathrel{\preceq_{\mathtt{grevlex}}} Z_1^{\ell'_1} \cdots
Z_d^{\ell'_d}$ ssi $\sum \ell_i < \sum \ell'_i$ ou $\sum \ell_i = \sum
\ell'_i$ et $\ell_i > \ell'_i$ pour le \emph{plus petit} $i$ tel que
$\ell_i \neq \ell'_i$.  Autrement dit, cet ordre trie en premier lieu
par degré total puis, en cas d'égalité, classe en premier les monômes
ayant le plus grand degré dans la plus petite variable --- et non pas
comme le fait l'ordre lexicographique le plus petit degré dans la plus
grande variable.  (Comme dans les cas précédents, cette définition est
faite relativement à l'ordre convenu sur les variables, et plus
généralement tout ordre sur celles-ci définit un unique ordre
lexicographique inversé gradué.)

Pour cet ordre, on a donc $1 \preceq Z_1 \preceq Z_2 \preceq Z_3
\preceq Z_4 \preceq \cdots \preceq Z_1^2 \preceq Z_1 Z_2 \preceq Z_1
Z_3 \preceq Z_1 Z_4 \preceq \cdots \preceq Z_2^2 \preceq Z_2 Z_3
\preceq \cdots \preceq Z_3^2 \preceq \cdots \preceq Z_1^3 \preceq
Z_1^2 Z_2 \preceq Z_1^2 Z_3 \preceq \cdots \preceq Z_1 Z_2^2 \preceq
Z_1 Z_2 Z_3 \preceq \cdots \preceq Z_2^3 \preceq \cdots$ (l'ordinal
associé à ce bon ordre sur les monômes de $k[Z_1,\ldots,Z_d]$
vaut $\omega$ comme c'est le cas pour tout ordre gradué).

On peut noter que $\mathrel{\preceq_{\mathtt{grevlex}}}$ et
$\mathrel{\preceq_{\mathtt{glex}}}$ coïncident lorsqu'il n'y a que
deux variables (une fois fixé l'ordre entre celles-ci).

\begin{proposition2}\label{caracterisation-ordre-lexicographique-inverse-gradue}
L'ordre $\mathrel{\preceq_{\mathtt{grevlex}}}$ est gradué au sens
de \ref{definition-ordres-admissibles}, et si
$\initial_{\mathtt{grevlex}}(f) \in (Z_1,\ldots,Z_t)$ (pour un $t\leq
d$, et en notant bien sûr $(Z_1,\ldots,Z_t)$ l'idéal engendré par ces
variables) avec $f$ un polynôme homogène, alors $f \in
(Z_1,\ldots,Z_t)$.  De plus, ces propriétés caractérisent l'ordre
lexicographique inversé gradué (parmi les ordres admissibles).
\end{proposition2}
\begin{proof}
Le fait que l'ordre $\mathrel{\preceq_{\mathtt{grevlex}}}$ soit gradué
est évident sur sa définition ; pour ce qui est de la deuxième
propriété, il suffit de remarquer que tous les monômes plus petits,
pour l'ordre lexicographique inversé gradué, et de même degré, qu'un
monôme dans $(Z_1,\ldots,Z_t)$, sont eux-mêmes dans
$(Z_1,\ldots,Z_t)$ : en effet, dire d'un monôme qu'il appartient à
$(Z_1,\ldots,Z_t)$ signifie qu'il a un degré $>0$ dans l'une des $t$
premières variables, et, à degré total constant, diminuer le monôme
pour $\mathrel{\preceq_{\mathtt{grevlex}}}$ se fait en augmentant le
degré dans la plus petite variable.

Pour montrer que les propriétés énoncées caractérisent l'ordre
lexicographique inversé gradué, on procède comme
en \ref{caracterisation-ordre-lexicographique-pur} : soit $\preceq$ un
ordre admissible gradué tel que si $\initial_{\preceq}(f) \in
(Z_1,\ldots,Z_t)$ (pour un $t\leq d$) avec $f$ homogène alors $f \in
(Z_1,\ldots,Z_t)$ ; ceci signifie que tout monôme faisant intervenir
(à un degré non nul) une variable $Z_i$ avec $i\leq t$ est strictement
inférieur à tout monôme du même degré ne faisant intervenir que
$Z_{t+1},\ldots,Z_d$.  Si $s = Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et
$s' = Z_1^{\ell'_1} \cdots Z_d^{\ell'_d}$ sont deux monômes de même
degré total tels que $s \mathrel{\preceq_{\mathtt{grevlex}}} s'$,
c'est-à-dire tels que $\ell_i > \ell'_i$ où $i$ est le \emph{plus
  petit} possible tel que $\ell_i \neq \ell'_i$, on appelle comme
précédemment $s^0 = Z_1^{\ell^0_1} \cdots Z_d^{\ell^0_d}$ le plus
grand diviseur commun de $s$ et $s'$ et $s^1$ et $s^{1\prime}$ définis
par$s = s^0 s^1$ et $s' = s^0 s^{1\prime}$ : on a alors $s^1 \preceq
s^{1\prime}$ puisque $s^1$ fait intervenir $Z_i$ et non $s^{1\prime}$
(alors qu'ils sont de même degré total), donc $s \preceq s'$, et ceci
démontre que $\preceq$ coïncide avec
l'ordre $\mathrel{\preceq_{\mathtt{grevlex}}}$.
\end{proof}

\subsubsection{Quelques autres ordres possibles} Il est assez fréquent
qu'au lieu d'utiliser le degré total dans les définitions de l'ordre
lexicographique gradué ou lexicographique inverse gradué, on utilise
un degré pondéré dans lequel les variables ont reçu des poids
$w_1,\ldots,w_d > 0$ (autrement dit, le premier critère de comparaison
sur un monôme $Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ est son degré pondéré
$\lambda(\ell) := \sum_{i=1}^d w_i \ell_i$).

Si les variables se divisent en plusieurs blocs $\mathscr{B}_j = \{
Z_{j,1},\ldots,Z_{j,d_j} \}$, et si on dispose d'un ordre
$\mathrel{\preceq_j}$ sur les monômes sur chaque bloc, on peut
combiner ceux-ci lexicographiquement (une fois choisi un ordre entre
les blocs, disons $\mathscr{B}_1 \preceq \cdots \preceq \mathscr{B}_r$
pour fixer les idées) en décrétant que $s \preceq s'$ ssi $s_{(j)}
\mathrel{\preceq_j} s'_{(j)}$ pour le plus grand $j$ tel que $s_{(j)}
\neq s'_{(j)}$, où $s_{(j)}$ désigne le plus grand facteur de $s$
formé de variables du bloc $\mathscr{B}_j$ (c'est-à-dire le produit
des variables de ce bloc aux mêmes multiplicités qu'elles apparaissent
dans $s$).  L'ordre lexicographique pur sur $d$ variables est un cas
particulier où on combine $d$ fois l'unique ordre possible sur les
monômes en une unique variable.

\subsubsection{Ordres monomiaux définis par des vecteurs de poids}
Supposons donnés des éléments $\lambda^{(0)},\ldots,\lambda^{(r)}$ du
dual de $\RR^d$ et qui l'engendrent en tant qu'espace vectoriel (ou
simplement dont l'intersection des noyaux ne contient pas de point à
coordonnées entières).  On va poser $s \preceq s'$, avec $s =
Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et $s' = Z_1^{\ell'_1} \cdots
Z_d^{\ell'_d}$, lorsque $\lambda^{(j)}(\ell' - \ell) > 0$ pour le plus
petit $j$ tel que $\lambda^{(j)}(\ell' - \ell) \neq 0$ (en considérant
$\ell$ et $\ell'$ comme des éléments de $\NN^d \subseteq \RR^d$) ---
autrement dit, on utilise successivement les formes linéaires
$\lambda^{(j)}$ pour comparer les vecteurs d'exposants, en donnant le
poids le plus fort aux premières.  Cette définition conduit bien à un
ordre admissible sur les monômes lorsque pour tout $1 \leq i \leq d$,
pour le plus petit $j$ tel que le coefficient de $\ell_i$ dans la
forme linéaire $\lambda^{(j)}$ soit non nul, ce coefficient soit en
fait strictement positif (c'est par exemple le cas si déjà
$\lambda^{(0)}$ est à coefficients strictement positifs).  On dit que
l'ordre $\preceq$ est défini par les formes linéaires (ou
\emph{vecteurs de poids}) $\lambda^{(0)},\ldots,\lambda^{(r)}$.

Le cas de l'ordre lexicographique pur s'obtient en prenant pour
$\lambda^{(i)}$ les $d$ formes linéaires de projection sur les
coordonnées $\ell_d,\ldots,\ell_1$ de la plus grande vers la plus
petite variable ; l'ordre lexicographique gradué s'obtient en
précédant toutes ces formes $\lambda^{(i)}$ de la forme
$\lambda^{(0)}$ de degré total $(\ell_i) \mapsto \sum_{i=1}^d \ell_i$
dont tous les coefficients valent $1$ ; l'ordre lexicographique
inversé gradué utilise cette même forme $\lambda^{(0)}$ de degré total
puis les formes \emph{opposées} des projections sur les coordonnées
$\ell_1,\ldots,\ell_d$.

En fait, il est possible de montrer que \emph{tout} ordre admissible
peut être défini par des formes linéaires
$\lambda^{(0)},\ldots,\lambda^{(r)}$ comme on vient de le dire.

Remarquons que, selon les cas, une seule forme linéaire
$\lambda^{(0)}$ peut suffire à définir tout l'ordre : par exemple, en
deux variables $X,Y$, penser à l'ordre monomial admissible défini par
la seule forme linéaire $\lambda(i,j) = i + \sqrt{2}\,j$, autrement
dit $X^i Y^j \preceq X^{i'} Y^{j'}$ ssi $(i'-i) + \sqrt{2}\,(j'-j)
\geq 0$.


%
\subsection{Bases de Gröbner}

\begin{definition2}\label{definition-ideal-initial}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$ et $\preceq$ un ordre
admissible, on note $\initial_{\preceq}(I)$ et on appelle
\textbf{idéal initial} de $I$ (relativement à l'ordre $\preceq$)
l'idéal engendré par les $\initial_{\preceq}(f)$ pour tous les $f\in
I$ (c'est donc un idéal monomial).
\end{definition2}

En lisant cette définition, on gardera à l'esprit le
corollaire \ref{composition-ideaux-monomiaux} : on peut définir
l'idéal initial de $I$ comme l'ensemble des polynômes qui sont
combinaisons linéaires de monômes chacun divisible par un
$\initial_{\preceq}(f)$ pour $f\in I$.

\begin{proposition2}\label{inclusion-ideaux-et-egalite-ideaux-initiaux}
Si $J \subseteq I$ sont deux idéaux de $k[Z_1,\ldots,Z_d]$ et que
$\initial(J) = \initial(I)$ (relativement à un certain ordre
admissible $\preceq$), alors $J = I$.
\end{proposition2}
\begin{proof}
Si ce n'est pas le cas, soit $f \in I$ ayant $\initial(f)$ le plus
petit possible tel que $f \not\in J$.  Comme
$\initial(f) \in \initial(I) = \initial(J)$, il existe $g \in J$ tel
que $\initial(g) = \initial(f)$.  Alors
$\initial(f-g) \prec \initial(f)$ (strictement), mais on a $f - g \in
I$ et $f - g \not\in J$, ce qui contredit la minimalité de $f$.
\end{proof}

On prendra en revanche garde au fait qu'il n'y a aucune raison en
général que prendre les $\initial_{\preceq}(f)$ pour $f$ parcourant
tel ou tel ensemble de générateurs de $I$ suffise à engendrer
$\initial_{\preceq}(I)$.  La définition et la proposition qui suivent
signifient que les bases de Gröbner sont précisément les ensembles de
générateurs pour lesquels c'est le cas.

\begin{definition2}
Si $I$ est un idéal de $k[Z_1,\ldots,Z_d]$ et $\preceq$ un ordre
admissible sur les monômes de ce dernier, on appelle \textbf{base de
  Gröbner} de $I$ (relativement à l'ordre $\preceq$) un ensemble
$f_1,\ldots,f_r$ d'éléments de $I$ tels que
$\initial_{\preceq}(f_1),\ldots,\initial_{\preceq}(f_r)$
engendrent $\initial_{\preceq}(I)$.
\end{definition2}

A priori, rien ne dit que $f_1,\ldots,f_r$ engendrent $I$.  C'est
pourtant le cas :
\begin{proposition2}
Dans les conditions ci-dessus, on a $I = (f_1,\ldots,f_r)$.
\end{proposition2}
\begin{proof}
On a $(f_1,\ldots,f_r) \subseteq I$ puisque les $f_i$ sont supposés
dans $I$.  D'après \ref{inclusion-ideaux-et-egalite-ideaux-initiaux},
il suffit de montrer que $\initial(J) = \initial(I)$ où $J =
(f_1,\ldots,f_r)$.  On sait que $\initial(J) \subseteq \initial(I)$ ;
mais réciproquement, si $h \in I$, par hypothèse sur les $f_i$ on peut
écrire $\initial(h) = g_1 \initial(f_1) + \cdots + g_r \initial(f_r)$,
donc $\initial(h) \in J$ et ainsi $\initial(h) \in \initial(J)$ : ceci
montre bien $\initial(J) = \initial(I)$.
\end{proof}

\begin{proposition2}\label{existence-bases-de-groebner}
Tout idéal de $k[Z_1,\ldots,Z_d]$ admet une base de Gröbner (finie).
\end{proposition2}
\begin{proof}
La propriété noethérienne assure que parmi les $\initial(f)$ pour
$f\in I$, qui par définition engendrent $\initial(I)$, on peut
extraire un ensemble fini engendrant $\initial(I)$ --- il s'agit d'une
base de Gröbner de $I$.
\end{proof}

Cette démonstration n'est manifestement pas constructive.  On va
cependant donner dans la section suivante un algorithme permettant de
calculer une base de Gröbner à partir d'un ensemble quelconque de
générateurs d'un idéal.  Commençons cependant par expliquer en quoi la
connaissance d'une base de Gröbner d'un idéal permet de résoudre la
question algorithmique de l'appartenance d'un élément à cet idéal :

\begin{algorithme2}[algorithme de division]\label{algorithme-division}
Soient $f,f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ et $\preceq$ un ordre
admissible sur les monômes.  Alors il existe une écriture
\[
f = g_1 f_1 + \cdots + g_r f_r + \rho
\tag{$*$}
\]
où $g_1,\ldots,g_r,\rho \in k[Z_1,\ldots,Z_d]$, où aucun des monômes
de $\rho$ n'est divisible par un des $\initial(f_i)$, et où $\initial(g_i
f_i) \preceq \initial(f)$ pour chaque $i$ ; et on va donner un algorithme
pour calculer cette écriture ; un tel $\rho$ s'appelle un
\textbf{reste} de $f$ par rapport au $f_1,\ldots,f_r$ et pour l'ordre
monomial $\preceq$ (on dit aussi que l'écriture ($*$) s'appelle une
\textbf{écriture standard} de $f$ par rapport aux $f_1,\ldots,f_r$ et
pour cet ordre monomial).

Lorsque les $f_1,\ldots,f_r$ forment une base de Gröbner (d'un
idéal $I = (f_1,\ldots,f_r)$), on a $f \in (f_1,\ldots,f_r)$ si et
seulement si $\rho = 0$, et $\rho$ est défini de façon unique par $f$.
\end{algorithme2}

\begin{proof}[Description de l'algorithme]
Si aucun terme de $f$ n'est divisible par aucun des $\initial(f_i)$,
retourner $\rho = f$ (et tous les $g_i = 0$).  Sinon, soit $c s
\initial(f_i)$ (où $c\neq 0$ est une constante et $s$ un monôme) le
$\preceq$-plus grand terme de $f$ qui soit divisible par un
des $\initial(f_i)$ : on applique récursivement l'algorithme à $f' = f -
c s f_i$ (qui vérifie $\initial(f') \preceq \initial(f)$), si $f' = g'_1 f_1
+ \cdots + g'_r f_r + \rho'$ est le résultat, renvoyer $g_j = g'_j$
sauf $g_i = g'_i + c s$, et $\rho = \rho'$.
\end{proof}

\begin{proof}
L'algorithme termine car le $\preceq$-plus grand monôme de $f$
divisible par un des $\initial(f_i)$ décroît strictement à chaque
itération, or $\preceq$ est un bon ordre
(cf. \ref{proprietes-ordres-admissibles}).  La propriété sur $\rho$
est évidente.  La propriété $\initial(g_j f_j) \preceq \initial(f)$ découle
par induction de $\initial(g'_j f_j) \preceq \initial(f') \preceq \initial(f)$
et $\initial(c s f_i) = c s \initial(f_i) = c\initial(f)$.

Si $\rho = 0$, le fait que $f \in (f_1,\ldots,f_r)$ est trivial.  Si
$f_1,\ldots,f_r$ forment une base de Gröbner et $f \in
(f_1,\ldots,f_r)$, comme on a aussi $\rho \in (f_1,\ldots,f_r)$, alors
$\initial(\rho) \in (\initial(f_1),\ldots,\initial(f_r))$, ce qui vu le fait
qu'aucun monôme de $\rho$ n'est divisible par un des $\initial(f_i)$,
n'est possible que si $\rho = 0$ (cf. \ref{divisibilite-des-monomes}) ; de
même, si $\rho$ et $\rho'$ sont deux restes différents du même $f$,
disons $f = g_1 f_1 + \cdots + g_r f_r + \rho$ et $f = g'_1 f_1 +
\cdots + g'_r f_r + \rho'$, alors $(g'_1-g_1) f_1 + \cdots +
(g'_r-g_r) f_r + (\rho'-\rho)$ est une écriture standard de $0$, donc
$\rho'=\rho$.
\end{proof}

Connaître une base de Gröbner d'un idéal $I$ permet de donc répondre à
la question de savoir si $f\in I$ pour un idéal donné.  Mieux, si
$(f_1,\ldots,f_r)$ est cette base de Gröbner, l'ensemble des classes
(modulo $I$) des monômes qui ne sont divisibles par aucun
des $\initial(f_i)$ constitue une base de $k[Z_1,\ldots,Z_d]/I$, ce
qui, avec l'algorithme de division, permet de calculer dans l'anneau
en question (cf. \ref{algorithmes-fondamentaux-anneau-quotient}).

\begin{remarque2}
On dit parfois simplement que des polynômes $f_1,\ldots,f_r$ sont
« une base de Gröbner » pour signifie qu'ils sont une base de Gröbner
de l'idéal qu'ils engendrent.
\end{remarque2}

\begin{proposition2}
Soient $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ des polynômes tels que
\emph{tout} $f \in (f_1,\ldots,f_r)$ ait une écriture standard avec
reste nul.  Alors $f_1,\ldots,f_r$ sont une base de Gröbner.
\end{proposition2}
\begin{proof}
Supposons par l'absurde que $f_1,\ldots,f_r$ ne sont pas une base de
Gröbner de l'idéal $I$ qu'ils engendrent, c'est-à-dire qu'il existe $f
\in I$ tel que $\initial(f)$ ne soit pas dans l'idéal engendré par les
$\initial(f_i)$, autrement dit
(cf. \ref{composition-ideaux-monomiaux}) ne soit multiple d'aucun
des $\initial(f_i)$.  Par hypothèse, il existe une écriture $f = g_1
f_1 + \cdots + g_r f_r$ où $\initial(g_i f_i) \preceq \initial(f)$
pour chaque $i$, et en fait $\initial(g_i f_i) \prec \initial(f)$ sans
quoi $\initial(f)$ serait multiple de $\initial(f_i)$.  Mais avoir
$\initial(g_i f_i) \prec \initial(f)$ pour tout $i$ contredit
manifestement $f = g_1 f_1 + \cdots + g_r f_r$.
\end{proof}

(Le théorème \ref{critere-de-buchberger} donne un critère beaucoup
plus fort et utilisable en pratique.)

Lorsque $f_1,\ldots,f_r$ ne forment pas une base de Gröbner, on peut
très bien avoir $\rho \neq 0$ et pourtant que $\rho$
(c'est-à-dire, $f$) appartienne à l'idéal $(f_1,\ldots,f_r)$.  Par
exemple, pour deux polynômes, $g_1 f_1 + g_2 f_2$ pourrait avoir un
terme initial beaucoup plus petit que ceux de $f_1,f_2$ à cause d'une
annulation entre ceux-ci (dans ce cas, l'algorithme de division
appliqué à $g_1 f_1 + g_2 f_2$ par rapport à $f_1,f_2$ donnerait $g_1
f_1 + g_2 f_2$ lui-même comme reste, bien que ce polynôme appartienne
à $(f_1,f_2)$).  L'algorithme de Buchberger pour calculer les bases de
Gröbner se fonde sur l'idée qu'il suffit d'éviter ce phénomène.

\begin{exemple2}
Considérons dans $k[X,Y]$ muni de l'ordre lexicographique (avec $X
\preceq Y$) les polynômes $f_1 = X Y^2 + X^2 Y + 2$ et $f_2 = Y^2 + XY
+ Y^2$, et soit $f = X^3 - 2$.  L'algorithme de division explicité
en \ref{algorithme-division} conduit à l'écriture standard triviale $f
= \rho$ avec reste $\rho = X^3 - 2$ puisque le terme initial de ce
dernier n'est divisible ni par le terme initial $X Y^2$ de $f_1$ ni
par celui $Y^2$ de $f_2$.  Pourtant, il s'avère que $f$ appartient
bien à l'idéal engendré par $f_1$ et $f_2$, comme le prouve l'égalité
$f = - f_1 + X f_2$ : mais cette écriture n'est pas une écriture
standard.

Cet exemple se modifie assez facilement pour donner un exemple où il
n'y a pas d'unicité de l'écriture standard : si on pose $f^\% = X Y^2
+ f = X Y^2 + X^3 - 2$, alors l'algorithme explicité
en \ref{algorithme-division} conduit soit à l'écriture standard $f^\%
= f_1 + \rho$ avec $\rho = -X^2 Y + X^3 - 4$, soit à l'écriture
standard $f^\% = X f_2 + \rho'$ avec $\rho' = -X^2 Y - 2$.

L'un ou l'autre de ces phénomènes montre que $f_1,f_2$ ne forment pas
une base de Gröbner de l'idéal $I$ qu'ils engendrent.  En fait, il
s'avère que cet idéal $I$ est celui engendré par $f_2$ et $f = -f_1 +
X f_2$, et que ces polynômes-là en forment une base de Gröbner,
l'idéal initial $\initial_{\mathtt{lex}}(I)$ étant celui engendré par
$X^3$ et $Y^2$.  (Par ailleurs, si $k = \QQ$, alors $\QQ[X,Y]/I$ est
le corps $\QQ(\root3\of2, j\root3\of2)$ de décomposition de $X^3 - 2$
sur $\QQ$.)
\end{exemple2}


%
\subsection{Relations entre monômes}\label{section-relations-entre-monomes}

Si $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ sont des polynômes, on
appelle \textbf{relation} ou \textbf{syzygie} entre les $f_i$ un
$r$-uplet $(g_1,\ldots,g_r)$ de polynômes tels que $g_1 f_1 + \cdots +
g_r f_r = 0$ (on dira parfois abusivement que cette égalité est la
relation) ; lorsque les $g_i$ ne sont pas tous nuls, on parle de
relation non-triviale.  Le \textbf{module des relations} (ou
\textbf{des syzygies}) entre $f_1,\ldots,f_r$ est le sous-module
de $(k[Z_1,\ldots,Z_d])^r$ formé des $(g_1,\ldots,g_r)$ tels que $g_1
f_1 + \cdots + g_r f_r = 0$.

Si $\preceq$ est un ordre monomial, on appelle de plus \textbf{monôme
  initial} (ou multidegré), pour l'ordre $\preceq$, d'une relation
$(g_1,\ldots,g_r)$ non triviale entre $f_1,\ldots,f_r$ le
$\preceq$-plus grand des monômes initiaux des $g_i f_i$.

Comme on va le voir en \ref{section-algorithme-de-buchberger}, la
question de savoir si $f_1,\ldots,f_r$ constituent une base de Gröbner
est intimement liée à celle de trouver des générateurs du module des
relations entre eux.  Avant de nous pencher sur cette question en
général, nous commençons par étudier le cas où $f_1,\ldots,f_r$ sont
des monômes (ou des termes).

On définit le pgcd de deux monômes $s$ et $s'$ étant défini comme le
plus grand monôme (pour n'importe quel ordre admissible, ou pour
l'ordre partiel de divisibilité) parmi les monômes qui divisent à la
fois $s$ et $s'$, c'est-à-dire $\pgcd(s,s') =
Z_1^{\min(\ell_1,\ell'_1)} \cdots Z_d^{\min(\ell_d,\ell'_d)}$ si $s =
Z_1^{\ell_1} \cdots Z_d^{\ell_d}$ et $s' = Z_1^{\ell'_1} \cdots
Z_d^{\ell'_d}$.  On parlera parfois abusivement du pgcd (unitaire) de
deux termes $cs$ et $cs'$ (où $c,c' \in k^\times$ et $s,s'$ sont deux
monômes) pour désigner $\pgcd(s,s')$.  Le ppcm de deux monômes se
définit de façon analogue, ou bien par la formule $\ppcm(s,s') =
ss'/\pgcd(s,s')$.

Si $s_1,\ldots,s_r$ sont des monômes, on dispose entre eux de la
relation évidente $\sigma^{(i,j)}$ définie par $(s_j/s) s_i - (s_i/s)
s_j = 0$ où $s = \pgcd(s_i,s_j)$, c'est-à-dire $\sigma^{(i,j)}_u = 0$
sauf pour $u=i$ et $u=j$ auquel cas on a respectivement
$\sigma^{(i,j)}_i = s_j/s$ et $\sigma^{(i,j)}_j = -s_i/s$.  Plus
généralement, si $c_1,\ldots,c_r \in k^\times$, on appellera
$\sigma^{(i,j)}$ la relation entre $c_1 s_1,\ldots,c_r s_r$ définie
par $\sigma^{(i,j)}_u = 0$ sauf pour $u=i$ et $u=j$ auquel cas on a
respectivement $\sigma^{(i,j)}_i = c_j s_j/s$ et $\sigma^{(i,j)}_j =
-c_i s_i/s$ (toujours avec $s = \pgcd(s_i,s_j)$).  L'importance de ces
relations va apparaître, en lien avec le critère de Buchberger
(\ref{critere-de-buchberger} ci-dessous), dans la définition du
polynôme de syzygie standard et dans le résultat suivant :

\begin{proposition2}\label{relations-entre-monomes}
Si $s_1,\ldots,s_r$ sont des monômes, les relations $\sigma^{(i,j)}$
définies ci-dessus (pour $i<j$) engendrent le module des relations
entre les $s_i$.

De plus, si on appelle « relation purement de monôme $\mu$ »
(pour $\mu$ un monôme quelconque) une relation $(g_1,\ldots,g_r)$
entre $s_1,\ldots,s_r$ telle que chaque $g_i$ soit un terme de monôme
$\mu/s_i$ (ou bien $0$ si $s_i$ ne divise pas $\mu$), alors toute
relation entre les $s_1,\ldots,s_r$ s'écrit de façon unique comme
somme de relations purement de monôme $\mu$ où $\mu$ parcourt les
différents monômes (ces relations étant nulles sauf pour un nombre
fini de $\mu$).  Et une relation purement de monôme $\mu$ peut
s'écrire comme combinaison $\sum_{i<j} a^{(i,j)} \sigma^{(i,j)}$ des
relations $\sigma^{(i,j)}$ pour lesquelles $\ppcm(s_i,s_j)$ divise
$\mu$, le coefficient $a^{(i,j)}$ devant $\sigma^{(i,j)}$ étant un
terme de monôme $\mu/\ppcm(s_i,s_j)$.

(Ces énoncés sont bien entendu valables, \textit{mutatis mutandis},
pour des relations entre termes.)
\end{proposition2}
\begin{proof}
Commençons par expliquer pourquoi toute relation entre les monômes
s'écrit comme somme de relations purement de monôme $\mu$ pour les
différents $\mu$ : si $(g_1,\ldots,g_r)$ est une relation entre
$s_1,\ldots,s_r$, et si $g_i^{[\mu/s_i]}$ désigne le terme de $g_i$ de
monôme $\mu/s_i$ (ou bien $0$ si $s_i$ ne divise pas $\mu$), alors il
est clair que $\sum_{i=1}^r g_i^{[\mu/s_i]} s_i$ est la somme des
termes de monôme $\mu$ dans $\sum_{i=1}^r g_i s_i = 0$, donc vaut
elle-même $0$, i.e., $(g_1^{[\mu/s_1]}, \ldots, g_r^{[\mu/s_r]})$ est
une relation entre les $s_i$, et manifestement $(g_1,\ldots,g_r)$ est
la somme de ces relations.  L'unicité est claire.

Il est également évident que $\sigma^{(i,j)}$ est bien une relation
purement de monôme $\ppcm(s_i,s_j)$.

Soit maintenant $(g_1,\ldots,g_r)$ une relation purement de
monôme $\mu$ entre $s_1,\ldots,s_r$ : si la relation est nulle
(triviale), il n'y a rien à prouver.  Il n'est manifestement pas
possible qu'\emph{exactement un} des $g_i$ soit non nul : on peut donc
trouver $i,j$ distincts tels que $g_i \neq 0$ et $g_j \neq 0$, disons
$g_i = b_i \mu/s_i$ et $g_j = b_j \mu/s_j$.  Ceci suppose notamment
que $\mu$ divise à la fois $s_i$ et $s_j$, donc leur ppcm, disons $\mu
= \nu\, \ppcm(s_i,s_j)$.  (Remarquons que $\mu/s_i = \nu
s_j/\pgcd(s_i,s_j) = \nu \sigma^{(i,j)}_i$.)  Si on définit $\tilde
g_u$ par $\tilde g_u = g_u - b_i \nu \sigma^{(i,j)}_u$, alors $\tilde
g_i = 0$ et $\tilde g_u = g_u$ si $u\neq i,j$ : donc la relation
$(\tilde g_1,\ldots,\tilde g_r)$ a strictement moins de termes non
nuls que $(g_1,\ldots,g_r)$ --- une récurrence évidente permet de
conclure.
\end{proof}


%
\subsection{L'algorithme de Buchberger}\label{section-algorithme-de-buchberger}

\subsubsection{Le $S$-polynôme}\label{definition-s-polynome}
Soient $f_1,f_2\in k[Z_1,\ldots,Z_d]$ : on définit le \textbf{polynôme
  de syzygie standard} ou \textbf{$S$-polynôme} $S(f_1,f_2)$ entre
$f_1$ et $f_2$ de la manière suivante :
\[
\begin{array}{c}
\displaystyle
S(f_1,f_2) = \frac{\initial(f_2)}{s} f_1 - \frac{\initial(f_1)}{s} f_2\\
\hbox{où~}
\displaystyle
s = \pgcd(\initial(f_1),\initial(f_2))
\end{array}
\]
On rappelle que le pgcd de deux termes $c_1 s_1 = \initial(f_1)$ et
$c_2 s_2 = \initial(f_2)$ est simplement défini comme le pgcd de $s_1$
et $s_2$.  Le terme initial des deux polynômes dont on a fait la
différence est donc $c_1\, c_2\, \frac{s_1\,s_2}{s} = c_1\, c_2\,
\ppcm(s_1,s_2)$) : par construction, ces deux termes s'annulent, et le
terme initial de $S(f_1,f_2)$ (s'il est non nul) est donc strictement
plus petit que $\ppcm(s_1,s_2) = \frac{s_1\,s_2}{s}$.

Soit $\rho_{i,j}$ un reste (au sens de \ref{algorithme-division}) de
$S(f_i,f_j)$ par rapport aux $f_1,\ldots,f_r$ : si les
$f_1,\ldots,f_r$ forment une base de Gröbner alors $\rho_{i,j} = 0$
puisque $S(f_i,f_j) \in (f_1,\ldots,f_r)$.  Ce qui est plus surprenant
est que la réciproque est également vraie :

\begin{theoreme2}[critère de Buchberger]\label{critere-de-buchberger}
Sous les hypothèses et avec les notations définies ci-dessus, on a
$\rho_{i,j} = 0$ pour tous $i,j$ si et seulement $f_1,\ldots,f_r$ sont
une base de Gröbner (de l'idéal qu'ils engendrent).
\end{theoreme2}
\begin{proof}
Une implication est claire, comme il a déjà été remarqué.  Supposons
que $\rho_{i,j} = 0$ pour tous $i,j$, c'est-à-dire qu'on ait une
écriture standard $S(f_i,f_j) = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r
f_r$ (au sens de \ref{algorithme-division}), et supposons par
l'absurde que $f_1,\ldots,f_r$ ne sont pas une base de Gröbner de
l'idéal qu'ils engendrent, c'est-à-dire qu'il existe $h = g_1 f_1 +
\cdots + g_r f_r$ tel que $\initial(h)$ ne soit multiple d'aucun
des $\initial(f_i)$.

Soit $\mu$ le monôme maximal (pour l'ordre admissible $\preceq$ fixé)
parmi les $\initial(g_i f_i) = \initial(g_i)\, \initial(f_i)$ (si on
veut, il s'agit donc aussi du monôme maximal intervenant dans un
quelconque des $g_i f_i$).  On a évidemment $\initial(h) \preceq \mu$.
Mais si on avait $\initial(h) = a\mu$ pour $a \in k^\times$
c'est-à-dire que $\initial(h)$ soit proportionnel à l'un des
$\initial(g_i)\, \initial(f_i)$, alors il serait divisible par
$\initial(f_i)$, contredisant l'hypothèse faite sur $h$ : c'est donc
que $\initial(h) \prec \mu$ (strictement).  À présent, parmi les
expressions $h = g_1 f_1 + \cdots + g_r f_r$ (pour ce $h$ fixé),
choisissons-en une qui donne $\mu$ le plus petit possible : ceci a
bien un sens car $\preceq$ est un bon ordre
(cf. \ref{proprietes-ordres-admissibles}).

Soit $\$$ l'ensemble des $i$ tels que $\initial(g_i)\, \initial(f_i)$
soit de la forme $a\mu$.  On doit avoir $\sum_{i\in\$} \initial(g_i)\,
\initial(f_i) = 0$ puisque tout autre terme dans $\sum_{i=1}^r g_i
f_i$ a un monôme strictement inférieur à $\mu$.

Cette égalité $\sum_{i\in\$} \initial(g_i)\,\initial(f_i) = 0$
constitue une relation $\delta$ (au sens
de \ref{section-relations-entre-monomes}) entre les termes initiaux
$c_i s_i = \initial(f_i)$ (à savoir : $\delta_i = \initial(g_i)$ si $i
\in \$$ et $\delta_i = 0$ sinon).
D'après \ref{relations-entre-monomes}, cette relation est une
combinaison des $\sigma^{(i,j)}$ définis à cet endroit, disons $\delta
= \sum_{i<j} a^{(i,j)} \sigma^{(i,j)}$.  Remarquons que $\delta$ est
une relation purement de monôme $\mu$ (dans la terminologie
de \ref{relations-entre-monomes}) donc qu'on peut supposer chacun des
$a^{(i,j)}$ est un terme de monôme $\mu/\ppcm(s_j,s_j)$.

Si $\Phi\colon k[Z_1,\ldots,Z_d]^r \to k[Z_1,\ldots,Z_d]$ est
l'application qui envoie $(x_1,\ldots,x_r)$ sur $x_1 f_1 + \cdots +
x_r f_r$, alors on a $\Phi(\delta) = \sum_{i\in\$} \initial(g_i)\,f_i$
et d'autre part $\Phi(\sigma^{(i,j)}) = S(f_i,f_j)$.  Par conséquent,
l'égalité $\delta = \sum_{i<j} a^{(i,j)} \sigma^{(i,j)}$ permet
d'écrire $\sum_{i\in\$} \initial(g_i)\,f_i = \sum_{i<j} a^{(i,j)}
S(f_i,f_j)$.  En utilisant les écritures standards $S(f_i,f_j) =
g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r f_r$ qu'on a supposé exister,
on peut écrire $\sum_{i<j} a^{(i,j)} S(f_i,f_j) = \gamma_1 f_1 +
\cdots + \gamma_r f_r$ (avec $\gamma_u = \sum_{i<j} a^{(i,j)}
g^{(i,j)}_u$).  On a $\initial(S(f_i,f_j)) \prec \ppcm(s_i,s_j)$, donc
$\initial(\gamma_u f_u) \prec \mu$.  Si on remplace $g_i$ par $\tilde
g_i$ défini comme $g_i - \initial(g_i) + \gamma_i$ si $i \in \$$ et
$g_i + \gamma_i$ sinon, nous venons de montrer que $h = \tilde g_1 f_1
+ \cdots + \tilde g_r f_r$.  Or $\initial(\tilde g_i f_i) \prec \mu$
pour tout $i$, ce qui contredit la minimalité de $\mu$.
\end{proof}

Si $f_1,\ldots,f_r$ forment une base de Gröbner, le fait qu'on ait
$\rho_{i,j} = 0$ avec les notations ci-dessus signifie qu'on a une
écriture standard $S(f_i,f_j) = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r
f_r$ (au sens de \ref{algorithme-division}), donc une relation $c_j
\frac{s_j}{\pgcd(s_i,s_j)} f_i - c_i \frac{s_i}{\pgcd(s_i,s_j)} f_j -
\sum_u g^{(i,j)}_u f_u = 0$ entre les $f_i$ (c'est-à-dire
$(\sigma^{(i,j)}_1, \ldots, \sigma^{(i,j)}_r)$ où $\sigma^{(i,j)}_u =
- g^{(i,j)}_u$ sauf si $u=i$ ou $u=j$ auquel cas $\sigma^{(i,j)}_i =
c_j \frac{s_j}{\pgcd(s_i,s_j)} - g^{(i,j)}_i$, respectivement
$\sigma^{(i,j)}_j = - c_i \frac{s_i}{\pgcd(s_i,s_j)} - g^{(i,j)}_j$).

\begin{theoreme2}[Spear-Schreyer]
Avec les notations précédentes, si $f_1,\ldots,f_r$ forment une base
de Gröbner, les relations $c_j \frac{s_j}{\pgcd(s_i,s_j)} f_i - c_i
\frac{s_i}{\pgcd(s_i,s_j)} f_j - \sum_u g^{(i,j)}_u f_u = 0$, où
$f_{i,j} = g^{(i,j)}_1 f_1 + \cdots + g^{(i,j)}_r f_r$ est une
écriture standard de $f_{i,j}$, engendrent\footnote{En fait, les
  relations en question forment elles-même une base de Gröbner du
  module des relations, si on prend la peine de définir la notion de
  « base de Gröbner » d'un module et non seulement d'un idéal, pour un
  ordre admissible sur les monômes de $k[Z_1,\ldots,Z_d]^r$ qui se
  déduit facilement de $\preceq$.} le module des relations
entre $f_1,\ldots,f_r$.
\end{theoreme2}
\begin{proof}
Supposons par l'absurde que $(g_1,\ldots,g_r)$ soit une relation entre
$f_1,\ldots,f_r$ qui ne soit pas combinaison des $\sigma^{(i,j)}$.  On
rappelle que le $\preceq$-plus grand monôme $\mu$ parmi les
$\initial(g_i f_i) = \initial(g_i)\, \initial(f_i)$ s'appelle le
« monôme initial » de la relation : choisissons la relation (parmi
celles qui ne sont pas combinaison des $\sigma^{(i,j)}$) qui ait $\mu$
le plus petit possible.  De plus, à monôme initial $\mu$ fixé,
choisissons la relation telle que l'indice $t$ du premier coefficient
$g_t$ tel que $\initial(g_t) = b_t \mu/s_t$ soit le plus grand
possible (i.e., $g_1 f_1 \prec \mu$, ..., $g_{t-1} f_{t-1} \prec \mu$
avec $t$ aussi grand que possible).

Il doit exister $t < v \leq r$ tel que $\initial(g_v) = b_v \mu/s_v$
(sinon aucun terme ne pourrait annuler $\initial(g_t)\,
\initial(f_t)$).  Si on définit $\tilde g_1,\ldots,\tilde g_r$ par
$\tilde g_u = g_u - b_t \nu \sigma^{(t,v)}_u$ où $\mu =
\nu\,\ppcm(s_t,s_v)$, alors on a défini une relation entre
$f_1,\ldots,f_r$ telle que $\initial(\tilde g_u f_u) \prec \mu$ pour
$u \leq t$ (y compris si $u=t$, le coefficient $b_t$ ayant été choisi
précisément pour annuler le coefficient dominant de $g_t$) tandis que
$\initial(\tilde g_u f_u) \preceq \mu$ pour tout $u$.  D'après les
hypothèses de minimalité faites sur $(g_1,\ldots,g_r)$, cette relation
devrait être combinaison des $\sigma^{(i,j)}$, donc la relation
d'origine aussi.
\end{proof}

\begin{algorithme2}[algorithme de Buchberger]\label{algorithme-de-buchberger}
Donné $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$, on peut calculer
effectivement une base de Gröbner de l'idéal qu'ils engendrent.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Calculer les $\rho_{i,j}$ définis plus hauts : si les $\rho_{i,j}$
sont tous nuls, terminer (les $f_1,\ldots,f_r$ forment une base de
Gröbner).  Si un des $\rho_{i,j}$ est non nul, dès qu'on le trouve,
ajouter ce $\rho_{i,j}$ parmi les $f_1,\ldots,f_r$ (c'est-à-dire,
recommencer l'algorithme avec $f_1,\ldots,f_r,\rho_{i,j}$).
\end{proof}
\begin{proof}
L'algorithme termine car l'idéal engendré par
$\initial(f_1),\ldots,\initial(f_r)$ ne cesse de croître strictement : le
processus doit donc terminer, ce qui ne peut se produire que parce que
tous les $\rho_{i,j}$ sont tous nuls, et le
critère \ref{critere-de-buchberger} permet de dire qu'on a bien une
base de Gröbner.
\end{proof}

\begin{remarques2}
Nous ne nous livrerons pas à une analyse de la complexité de cet
algorithme, mais signalons au moins que \emph{dans le pire cas} elle
est doublement exponentielle en le nombre de variables, donc \textit{a
  priori} prohibitive (c'est d'ailleurs à l'origine de différentes
tentatives d'utilisation des bases de Gröbner en cryptographie), mais
que malgré cela, en pratique, sur beaucoup de problèmes utiles,
l'algorithme termine en un temps raisonnable (les raisons pour ça
n'étant pas toujours évidentes, et parfois même mal comprises).

Il existe différentes optimisations permettant de gagner un peu
d'efficacité sur l'algorithme tel qu'il a été présenté (sans,
toutefois, changer fondamentalement sa complexité) : par exemple, dans
l'application du critère \ref{critere-de-buchberger}, on peut se
contenter de tester si $\rho_{i,j} = 0$ pour les paires $i,j$ telles
que $\initial(f_i)$ et $\initial(f_j)$ aient un pgcd non trivial (car
si leur pgcd vaut $1$, on peut montrer qu'il est toujours possible de
mener la division de $S(f_i,f_j)$ par les $f_k$ de manière à avoir un
reste nul).
\end{remarques2}


%
\subsection{Bases de Gröbner réduites}

\begin{definition2}
Une base de Gröbner $f_1,\ldots,f_r$ est dite \textbf{réduite}
lorsque, pour $i\neq j$, le monôme du terme $\initial(f_i)$ ne divise
aucun des monômes apparaissant dans $f_j$, et si, de plus, chacun des
termes $\initial(f_i)$ est unitaire (=la constante devant le monôme
est $1$).
\end{definition2}

\begin{algorithme2}\label{algorithme-reduction-base-de-groebner}
Donné $f_1,\ldots,f_r \in k[Z_1,\ldots,Z_d]$ une base de Gröbner, on
peut calculer effectivement une base de Gröbner réduite de l'idéal
qu'ils engendrent.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Quitte à trier les éléments (et, évidemment, à effacer ceux qui sont
nuls), on peut supposer $\initial(f_1) \preceq \initial(f_2) \preceq
\cdots \preceq \initial(f_r)$.  On parcourt ces éléments dans cet
ordre et on efface de la liste tous dont le terme initial
$\initial(f_i)$ est multiple du terme initial $\initial(f_j)$ d'un
élément antérieur ($j<i$).  Ces effacements ne changent pas le fait
que les éléments forment une base de Gröbner, ni l'idéal $I$ engendré
(en effet, si $\initial(f_i)$ est multiple de $\initial(f_j)$ alors
l'idéal engendré par les $\initial(f_u)$ pour $u\neq i$ est le même
que celui engendré par tous les $\initial(f_u)$, et par hypothèse il
s'agit de $\initial(I)$).

On parcourt ensuite (ou dans la même boucle) les éléments dans cet
ordre et on remplace chaque $f_i$ par son reste $\tilde f_i$, donné
par l'algorithme \ref{algorithme-division}, par rapport à
$f_1,\ldots,f_{i-1}$, de manière à ce qu'aucun terme de $\tilde f_i$
ne soit divisible par l'un des $\initial(f_j)$ pour $j<i$ : cette
opération ne change pas $\initial(f_i)$ (puisque $\initial(f_i)$ n'est
multiple d'aucun des $\initial(f_j)$ pour $j<i$ d'après les opérations
du paragraphe précédent), et ne change pas le fait les éléments
forment une base de Gröbner ni l'idéal engendré ; puisque
$\initial(\tilde f_i) = \initial(f_i)$, le fait qu'on ait
$\initial(f_1) \preceq \cdots \preceq \initial(f_r)$ reste toujours
vrai.

Enfin (ou dans la même boucle) on parcourt les éléments et on remplace
$f_i$ par $f_i/c_i$ où $c_i$ est le coefficient initial de $f_i$.
\end{proof}

\begin{proposition2}\label{unicite-base-de-groebner-reduite}
Pour un idéal $I$ de $k[Z_1,\ldots,Z_d]$ et un ordre
admissible $\preceq$, il existe une unique base de Gröbner réduite (à
l'ordre des éléments près).
\end{proposition2}
\begin{proof}
L'existence a été prouvée dans le cadre de l'algorithme ci-dessus.

Supposons maintenant que $f_1,\ldots,f_r$ et $\tilde f_1,\ldots,\tilde
f_t$ soient deux bases de Gröbner réduites du même idéal, ordonnées
par $\initial(f_1) \preceq \initial(f_2) \preceq \cdots \preceq
\initial(f_r)$ et $\initial(\tilde f_1) \preceq \initial(\tilde f_2)
\preceq \cdots \preceq \initial(\tilde f_t)$.  On va montrer par
récurrence sur $i$ que $f_i = \tilde f_i$ pour $i \leq \min(r,t)$,
auquel cas il sera clair que $r=t$ (sinon les éléments supplémentaires
seraient engendrés par les précédents, ce qui contredit le fait que la
base est censément réduite).

Le monôme initial de $f_i$ est caractérisé par le fait qu'il s'agit du
plus petit monôme appartenant à $\initial(I)$ mais n'appartenant pas à
l'idéal engendré par $\initial(f_1),\ldots,\initial(f_{i-1})$.  Avec
l'hypothèse de récurrence, on voit donc qu'au moins $\initial(f_i) =
\initial(\tilde f_i)$ (les deux étant unitaires).

À présent, le polynôme $h = f_i - \tilde f_i$ appartient à $I$, et
$\initial(h) \prec \initial(f_i)$ : donc l'écriture standard de $h$
par rapport à $f_1,\ldots,f_r$ a un reste nul et ne fait intervenir
que $f_1,\ldots,f_{i-1}$ ; or l'hypothèse selon laquelle les bases
sont réduites interdit qu'il existe un terme de $h$ qui soit multiple
d'un $\initial(f_j)$ pour $j\neq i$ : donc on ne peut avoir que $h =
0$ et $\tilde f_i = f_i$.
\end{proof}

\begin{remarque2}
La base de Gröbner réduite d'un idéal $I$ (dans un anneau de polynômes
où on a fixé un ordre admissible) est évidemment minimale, pour
l'inclusion, parmi les bases de Gröbner de $I$ (si on en retire des
éléments, on ne peut plus avoir affaire à une base de Gröbner de $I$,
dans quoi les monômes initiaux de ces éléments seraient engendrés par
les monômes initiaux des autres).  Il faut se garder de croire,
cependant, qu'elle soit minimale pour l'inclusion parmi les familles
engendrant l'idéal $I$.  Par exemple, dans $\QQ[x,y]$ muni de l'ordre
lexicographique gradué pour lequel $x \succeq y$, les polynômes $x^2,
xy, y^2+x$ forment une base de Gröbner (de l'idéal qu'ils engendrent),
comme on le vérifie facilement avec le critère de Buchberger,
manifestement minimale, et pourtant le sous-ensemble $xy, y^2+x$
continue d'engendrer le même idéal puisque $x^2$ s'exprime comme
combinaison $\QQ[x,y]$-linéaire de ceux-ci.
\end{remarque2}

\XXX --- Question complètement gratuite, comme ça : peut-on
caractériser les idéaux $I$ tels qu'aucun sous-ensemble strict de la
base de Gröbner réduite $B$ de $I$ n'engendre $I$ ?

\begin{proposition2}\label{bases-de-groebner-et-extensions-de-corps}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $B$ une base de Gröbner
(resp. la base de Gröbner réduite) de $I$ pour un certain ordre
monomial $\preceq$.  Alors, pour n'importe quelle extension de corps
$K$ de $k$, l'idéal $I \cdot K[Z_1,\ldots,Z_d]$ engendré par $I$ dans
$K[Z_1,\ldots,Z_d]$ admet encore $B$ pour base de Gröbner (resp. base
de Gröbner réduite), pour le même ordre monomial $\preceq$.
\end{proposition2}
\begin{remarque2}
Il est clair que $B$ engendre $I \cdot K[Z_1,\ldots,Z_d]$ dans
$K[Z_1,\ldots,Z_d]$.  Comme le critère de
Buchberger \ref{critere-de-buchberger} ne dépend pas du corps utilisé,
il s'agit encore d'une base de Gröbner, et de même elle est réduite
car cette condition ne dépend pas du corps utilisé.
\end{remarque2}


%
\subsection{Algorithmes fondamentaux}

Nous reprenons maintenant certains des problèmes posés dans la
section \ref{section-motivations-groebner} pour montrer en quoi les
bases de Gröbner sont utiles à leur résolution :

\subsubsection{Système canonique de générateurs} Donné un idéal $I =
(f_1,\ldots,f_r)$ de $k[Z_1,\ldots,Z_d]$ (et une fois choisi une fois
pour toutes un ordre admissibile $\preceq$), on sait en trouver une
base de Gröbner réduite d'après
\ref{algorithme-de-buchberger} et \ref{algorithme-reduction-base-de-groebner}.
Cette base est unique (si on trie ses éléments d'après leur monôme
initial) d'après \ref{unicite-base-de-groebner-reduite} : il s'agit
donc d'une représentation canonique de l'idéal $I$, qui permet, par
exemple, de tester l'égalité entre deux idéaux.

De plus, au cours de l'application des algorithmes (et surtout, à
l'intérieur de ceux-ci, de l'algorithme de
division \ref{algorithme-division}), on peut exprimer, si on le veut,
chaque nouveau polynôme introduit (notamment les restes des divisions)
comme combinaison des générateurs $f_1,\ldots,f_r$ de départ : on peut
ainsi relier la base choisie comme canonique (la base de Gröbner
réduite) à la base initiale donnée, et dans tous les calculs effectués
ensuite on pourra toujours, si on le souhaite, exprimer les membres de
l'idéal sur la base initiale.  (A contrario, le point suivant permet
d'exprimer la base initiale en fonction de la base de Gröbner
réduite.)

\subsubsection{Test d'appartenance et décompositions} Donné un $f \in
k[Z_1,\ldots,Z_d]$ et une fois obtenue une base de Gröbner de
l'idéal $I$, l'algorithme de division \ref{algorithme-division} permet
de tester si $f \in I$ et, le cas échéant, de donner une écriture de
$f$ sur la base en question.

\subsubsection{Anneau quotient}\label{algorithmes-fondamentaux-anneau-quotient} Les
classes modulo $I$ des monômes qui ne sont divisibles par le monôme
initial d'aucun élément de la base de Gröbner constituent une base
comme $k$-espace vectoriel de $k[Z_1,\ldots,Z_d]/I$, toujours d'après
l'algorithme de division \ref{algorithme-division} qui permet, en
outre, d'écrire les coordonnées sur cette base de la classe modulo $I$
d'un polynôme $f$ quelconque.

Cette base n'est pas forcément finie ($k[Z_1,\ldots,Z_d]/I$ peut être
de dimension finie ou non : en fait, il sera de dimension finie ---
c'est-à-dire, artinien --- exactement lorsque $I$ sera « de
  dimension $0$ » au sens de l'objet géométrique qu'il décrit), mais
même si elle est infinie, la base possède une description suffisamment
simple (il s'agit de $d$-uplets d'entiers naturels vérifiant une
combinaison booléenne d'inégalités) pour être aisément manipulable.

Ceci permet en outre d'effectuer les opérations dans l'anneau quotient
$k[Z_1,\ldots,Z_d]/I$ : l'addition, bien sûr, se fait terme à terme
sur la base évoquée, et la multiplication se fait en relevant à
$k[Z_1,\ldots,Z_d]$, en effectuant la multiplication dans celui-ci, et
en réduisant de nouveau par l'algorithme de division.


%
\subsection{Bases de Gröbner et élimination}

\subsubsection{} Si $I = (f_1,\ldots,f_r)$ est un idéal de
$k[Z_1,\ldots,Z_d]$ et $t \leq d$, l'idéal $J = I \cap
k[Z_1,\ldots,Z_t]$ est appelé un \emph{idéal d'élimination} de $I$.
Une interprétation intuitive de cette opération, justifiant le nom,
consiste à imaginer que $I$ décrit un ensemble de relations
algébriques entre les indéterminées $Z_1,\ldots,Z_d$ (relations
engendrées par les relations données $f_1,\ldots,f_r$) et que l'idéal
$J$ consiste en celles qui ne concernent que les $t$ premières
indéterminées : trouver des générateurs de $J$ revient donc à
« éliminer » les variables $Z_{t+1},\ldots,Z_d$ d'entre les équations
$f_1{=}0,\ldots,f_r{=}0$, et trouver les meilleures relations
possibles entre les $t$ variables restantes.  (En admettant certains
résultats de géométrie algébrique notamment le Nullstellensatz \XXX,
lorsque $k$ est algébriquement clos, l'ensemble $\mathscr{Z}(J)$ des
$t$-uplets $(z_1,\ldots,z_t)$ vérifiant les équations en question est
simplement l'adhérence pour la topologie de Zariski (c'est-à-dire le
plus petit $\mathscr{Z}(J)$ possible la contenant) de la projection
sur les $t$ premières coordonnées de l'ensemble $\mathscr{Z}(I)$ des
$d$-uplets $(z_1,\ldots,z_d)$ vérifiant $f_i(z_1,\ldots,z_d)=0$.)  Ce
problème de trouver des générateurs de $J$ est le problème fondamental
de la théorie de l'élimination.  Les bases de Gröbner fournissent un
algorithme permettant de le résoudre :

\begin{proposition2}\label{base-de-groebner-elimination}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $t\leq d$ : notons $J = I
\cap k[Z_1,\ldots,Z_t]$.  Alors on a $\initial_{\mathtt{lex}}(J) =
\initial_{\mathtt{lex}}(I) \cap k[Z_1,\ldots,Z_t]$ (où on est convenu
d'ordonner les variables de la manière $Z_1 \preceq Z_2 \preceq \cdots
\preceq Z_d$) ; et si $B = \{f_1,\ldots,f_r\}$ est une base de Gröbner
de $I$ pour l'ordre $\mathrel{\preceq_{\mathtt{lex}}}$, alors $B \cap
k[Z_1,\ldots,Z_t]$ est une base de Gröbner de $J$.

Plus généralement, ces affirmations (à $t$ fixé) valent pour tout
ordre admissible $\preceq$ vérifiant la propriété suivante : si
$\initial_{\preceq}(f) \in k[Z_1,\ldots,Z_t]$ alors $f \in
k[Z_1,\ldots,Z_t]$ (autrement dit, il ordonne chacun de
$Z_{t+1},\ldots,Z_d$ après tout monôme en $Z_1,\ldots,Z_t$).
\end{proposition2}
\begin{proof}
La propriété énoncée dans le second paragraphe est bien vérifiée (pour
tout $t$) par l'ordre lexicographique
d'après \ref{caracterisation-ordre-lexicographique-pur} : on va donc
montrer les résultats sous cette hypothèse.

Quitte à réordonner les $f_i$, convenons que $B \cap k[Z_1,\ldots,Z_t]
= \{f_1,\ldots,f_u\}$.

Il est clair que $(\initial(f_1),\ldots,\initial(f_u)) \subseteq
\initial(J) \subseteq \initial(I) \cap k[Z_1,\ldots,Z_t]$.  On va
montrer que $\initial(f_1),\ldots,\initial(f_u)$ engendrent
$\initial(I) \cap k[Z_1,\ldots,Z_t]$, c'est-à-dire
$(\initial(f_1),\ldots,\initial(f_u)) = \initial(J) = \initial(I) \cap
k[Z_1,\ldots,Z_t]$ : ceci prouvera à la fois que $f_1,\ldots,f_u$
forment une base de Gröbner de $J$ et que $J = I \cap
k[Z_1,\ldots,Z_t]$.

Soit $s \in \initial(I) \cap k[Z_1,\ldots,Z_t]$ un monôme (il suffit
de montrer que $\initial(f_1),\ldots,\initial(f_u)$ engendrent les
tels $s$, cf. \ref{equivalences-ideaux-monomiaux}) : comme
$\initial(f_1),\ldots,\initial(f_t)$ engendrent $\initial(I)$, il
existe $i$ tel que $\initial(f_i)$
divise $s$ (\ref{composition-ideaux-monomiaux}).  Puisque $s \in
k[Z_1,\ldots,Z_t]$, on a aussi $\initial(f_i) \in k[Z_1,\ldots,Z_t]$,
et l'hypothèse faite sur $\preceq$ impose $f_i \in k[Z_1,\ldots,Z_t]$,
c'est-à-dire $i\leq u$.
\end{proof}

\XXX --- Eisenbud (proposition 15.29) prétend utiliser la
proposition \ref{inclusion-ideaux-et-egalite-ideaux-initiaux}
(lemme 15.5 chez lui).  Je ne vois pas où ça sert : me suis-je trompé
dans cette démonstration ?

(Une façon parfois plus efficace que l'ordre lexicographique pur,
\emph{si on connaît $t$ à l'avance}, consiste à prendre l'ordre sur le
degré total en les seules variables $Z_1,\ldots,Z_t$ comme premier
critère de comparaison, et en cas d'égalité comparer avec
$\mathrel{\preceq_{\mathtt{grevlex}}}$.)

\begin{corollaire2}\label{projection-et-extensions-de-corps}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et $t\leq d$ : notons $J = I
\cap k[Z_1,\ldots,Z_t]$.  Alors, pour n'importe quelle extension de
corps $K$ de $k$, on a $J \cdot K[Z_1,\ldots,Z_t] = (I \cdot
K[Z_1,\ldots,Z_d]) \cap K[Z_1,\ldots,Z_t]$.
\end{corollaire2}
\begin{proof}
C'est une conséquence immédiate de la proposition précédente et
de \ref{bases-de-groebner-et-extensions-de-corps}.
\end{proof}


%
\subsection{Ajout d'une variable et calcul d'inverse}

\XXX --- Il est tout pourri le titre de cette section !

\begin{proposition2}\label{borne-degre-base-groebner-sur-une-variable-dominante}
Soit $\preceq$ un ordre monomial sur $k[Z_1,\ldots,Z_d,Y]$ tel que $Y$
soit supérieur à tout monôme en $Z_1,\ldots,Z_d$.  Soient
$h_1,\ldots,h_n \in k[Z_1,\ldots,Z_d,Y]$ tels que $\deg_Y(h_i) \leq N$
pour tout $i$, où $N$ est une certaine constante (ici, $\deg_Y(h)$
désigne le degré partiel du polynôme $h$ en la variable $Y$).  Alors
la base de Gröbner $f_1,\ldots,f_r$ réduite de $I = (h_1,\ldots,h_n)$
vérifie également $\deg_Y(f_i) \leq N$ pour tout $i$.
\end{proposition2}
\begin{proof}
L'hypothèse effectuée sur l'ordre garantit que $\deg_Y(h) =
\deg_Y(\initial(h))$ pour tout $h$.  Il suffit de montrer que, dans
l'algorithme de Buchberger \ref{algorithme-de-buchberger}, aucun
polynôme de degré en $Y$ strictement supérieur à $N$ n'est jamais
ajouté à la base (et que, dans l'algorithme de
réduction \ref{algorithme-reduction-base-de-groebner} ou, en fait,
dans l'algorithme de division \ref{algorithme-division}, on n'augmente
jamais le degré en $Y$, mais c'est évident).  Le point essentiel à
vérifier est donc que si $h_i$ et $h_j$ vérifient $\deg_Y(h_i) \leq N$
alors le $S$-polynôme $S(h_i,h_j)$ défini
en \ref{definition-s-polynome} vérifie la même inégalité.  Mais son
terme initial est strictement inférieur à $\ppcm(\initial(h_i),
\initial(h_j))$, lequel a bien un degré en $Y$ majoré par $N$, donc
c'est le cas de $S(h_i,h_j)$.
\end{proof}

\XXX --- Ce serait mieux de donner une démontration qui n'utilise pas
la construction algorithmique.

\begin{algorithme2}\label{algorithme-calcul-inverse-algebre-de-type-fini}
Donné un idéal $I$ (défini par ses générateurs) de
$k[Z_1,\ldots,Z_d]$, et $x$ un élément de $k[Z_1,\ldots,Z_d]/I$, on
peut déterminer si $x$ est inversible dans cette algèbre et, le cas
échéant, en calculer un inverse.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Introduisons une nouvelle variable $Y$ : soit $\tilde I$ l'idéal de
$k[Z_1,\ldots,Z_d,Y]$ engendré par $I$ (c'est-à-dire, par les
générateurs donnés de $I$) et par $\hat x Y - 1$ (où $\hat x$ est un
relèvement quelconque de $x$ à $k[Z_1,\ldots,Z_d]$, étant évident que
$\tilde I$ ne dépend pas de ce choix).  On calcule la base de Gröbner
réduite $\tilde B$ de $\tilde I$ pour un ordre monomial $\preceq$
quelconque qui ordonne $Y$ après n'importe quel monôme en
$Z_1,\ldots,Z_d$.  Cette base est de la forme $B' \cup C$ où $B' =
\tilde B \cap k[Z_1,\ldots,Z_d]$ est la base de Gröbner réduite de $I'
= \tilde I \cap k[Z_1,\ldots,Z_d]$ (pour le même ordre monomial,
c'est-à-dire, pour sa restriction aux monômes en $Z_1,\ldots,Z_d$) et
$C$ est formé de polynômes dont le degré partiel en $Y$ vaut
exactement $1$.  L'élément $x$ est inversible si et seulement si $I' =
I$ (ce qui se teste en vérifiant que les bases de Gröbner réduites
coïncident) et que $C$ est (soit vide, soit) réduit à un unique
polynôme de la forme $Y - g$ avec $g \in k[Z_1,\ldots,Z_d]$ ; et
lorsque c'est le cas, la classe de $g$ modulo $I$ est l'inverse
recherché (quant au cas où $I'=I$ et $C$ est vide, il ne se produit
que lorsque $k[Z_1,\ldots,Z_d]/I$ est l'algèbre nulle, ce cas étant
trivial).
\end{proof}
\begin{proof}
On sait d'après \ref{base-de-groebner-elimination} que l'ensemble $B'
= \tilde B \cap k[Z_1,\ldots,Z_d]$ des éléments de $\tilde B$ ne
faisant intervenir que les variables $Z_1,\ldots,Z_d$ est la base de
Gröbner réduite de $I' = \tilde I \cap k[Z_1,\ldots,Z_d]$ (soulignons
que cet idéal contient $I$).  On sait aussi
d'après \ref{borne-degre-base-groebner-sur-une-variable-dominante} que
les degrés en $Y$ des éléments de $\tilde B$ sont majorés par $1$.  On
pose $C = \tilde B \setminus B'$ l'ensemble des éléments de $\tilde B$
faisant effectivement intervenir $Y$.

Notons $A = k[Z_1,\ldots,Z_d]/I$ : on a alors
$k[Z_1,\ldots,Z_d,Y]/\tilde I = A[Y]/(xY-1)$.  Soit $\varphi \colon A
\to A[Y]/(xY-1)$ le morphisme évident.  L'idéal $I'$ est l'image
réciproque dans $k[Z_1,\ldots,Z_d]$ du noyau de $\varphi$.

Supposons d'abord $x$ inversible dans $A$, d'inverse $x^{-1}$ : alors
$A[Y]/(xY-1) = A[Y]/(Y-x^{-1})$ et $\varphi$ est un isomorphisme.  En
particulier, $I' = I$ (puisque $\varphi$ est injectif).  D'autre part,
si $g \in k[Z_1,\ldots,Z_d]$ représente $x^{-1}$ modulo $I$, alors $Y
- g$ est dans $\tilde I$.  Cet élément a pour monôme initial $Y$ donc
il y a dans $\tilde B$ a un élément de monôme initial $Y$ (sauf si $A$
est l'algèbre nulle, cas que nous écarterons), donc dans $C$ ; et
comme la base de Gröbner $\tilde B$ était supposée réduite, cet
élément est l'unique élément de $C$, et il est manifestement de la
forme $Y - g$ avec $g$ représentant $x^{-1}$ modulo $I$.

Réciproquement, supposons que $I' = I$, c'est-à-dire que $\varphi$ est
injective, et que $C$ contient un élément de la forme $Y - g$ : alors
$\varphi$ envoie la classe de $g$ sur celle de $Y$, donc $\varphi$ est
surjectif, et c'est un isomorphisme.  En particulier, $x$ est
inversible d'inverse $\varphi^{-1}(Y)$.
\end{proof}


\section{Idéaux de dimension $0$}

\subsection{Fonction et polynôme de Hilbert-Samuel}

\begin{definition2}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  On appelle \emph{fonction
  de Hilbert-Samuel affine} de $I$ la fonction qui à un entier
naturel $\ell$ associe la dimension du $k$-espace vectoriel engendré
par les classes modulo $I$ de monômes de degré total $\leq\ell$.
\end{definition2}

Lorsque $I$ est l'idéal nul, la fonction de Hilbert-Samuel affine
de $I$ compte le nombre total de monômes de degré total $\leq\ell$
en $d$ variables, autrement dit, le nombre de $d$-uplets d'entiers
naturels de somme $\leq\ell$ : un raisonnement combinatoire classique
(\XXX --- l'expliciter ?)  montre que ce nombre vaut
$\frac{(\ell+d)!}{\ell!\,d!} =
\frac{1}{d!}\ell(\ell-1)\cdots(\ell-d+1)$, qui est un polynôme de
degré $d$ en $\ell$ et de terme dominant $\frac{1}{d!} \ell^d$.

De façon plus générale, si $I$ est un idéal quelconque et
$f_1,\ldots,f_r$ une base de Gröbner de $I$ dont on note $c_i s_i =
\initial(f_i)$ le terme dominant (avec $s_i$ un monôme), la fonction
de Hilbert-Samuel affine de $I$ compte (cf. par
exemple \ref{algorithmes-fondamentaux-anneau-quotient}) le nombre de
monômes de degré total $\leq\ell$ en $d$ variables qui ne sont
divisibles par aucun des monômes $s_1,\ldots,s_r$, autrement dit, le
nombre de $d$-uplets $(v_1,\ldots,v_d)$ d'entiers naturels de
somme $\leq\ell$ tels que pour tout $1\leq i\leq r$ il existe $1\leq
j\leq d$ avec $v_i < w_{ij}$, où on a noté $w_{ij}$ les exposants de
$s_i$, soit $s_i = Z_1^{w_{i1}} \cdots Z_d^{w_{id}}$.  Par un
raisonnement purement combinatoire, on peut montrer :
\begin{proposition2}\label{polynomialite-hilbert-samuel}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  Il existe un polynôme,
prenant des valeurs entières sur tous les entiers, dont le terme
dominant est de la forme $\frac{A}{\delta!} \ell^\delta$ avec
$0\leq\delta\leq d$ et $A$ un entier naturel, et de plus $\delta=d$ si
et seulement si $I=0$, qui coïncide pour $\ell$ assez grand avec la
fonction de Hilbert-Samuel affine de $I$.
\end{proposition2}

\XXX --- Le prouver ?

\begin{definition2}\label{definition-polynome-hilbert-samuel-affine}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  Le polynôme (manifestement
unique) coïncidant pour $\ell$ grand avec la fonction de
Hilbert-Samuel affine de $I$, et dont l'existence est garantie par la
proposition \ref{polynomialite-hilbert-samuel}, est appelé
\emph{polynôme de Hilbert-Samuel affine} de $I$.

Son degré $\delta$ est appelé \emph{dimension affine} de $I$, et
l'entier naturel $A$ tel que le coefficient dominant soit
$\frac{A}{\delta!} \ell^\delta$ est appelé \emph{degré} (affine en
dimension $\delta$) de $I$.
\end{definition2}


\subsection{Idéaux de dimension $0$ et algèbres finies}

\begin{proposition2}\label{equivalences-ideaux-affines-dimension-zero}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$.  Les affirmations suivantes
sont équivalentes :
\begin{itemize}
\item l'espace vectoriel quotient $k[Z_1,\ldots,Z_d]/I$ est de
  dimension finie sur $k$,
\item la dimension affine de $I$ (au sens
  de \ref{definition-polynome-hilbert-samuel-affine}) vaut $0$,
\item (pour $f_1,\ldots,f_r$ une base de Gröbner quelconque de $I$
  pour un ordre monomial quelconque :) pour tout $1\leq j\leq d$ il
  existe un $1\leq i\leq r$ tel que le monôme initial de $f_i$ soit
  une puissance de $Z_j$.
\end{itemize}
De plus, dans ces conditions, le degré de $I$ (au sens
de \ref{definition-polynome-hilbert-samuel-affine}) est égal à la
dimension du $k$-espace vectoriel $k[Z_1,\ldots,Z_d]/I$.
\end{proposition2}
\begin{proof}
Pour ce qui est de l'équivalence entre les deux premiers énoncés, il
est clair que la dimension de $k[Z_1,\ldots,Z_d]/I$ vaut (comme
élément de $\NN \cup \{+\infty\}$) la limite de la fonction de
Hilbert-Samuel affine de $I$, qui est bien sûr aussi la limite du
polynôme de Hilbert-Samuel affine de $I$ : ceci se produit si et
seulement si son degré $\delta$ vaut $0$, auquel cas sa limite est
égale à son coefficient constant (et unique) $A$.

Montrons maintenant l'équivalence avec le troisième énoncé.  Si
$k[Z_1,\ldots,Z_d]/I$ est de dimension finie, si $1\leq j\leq d$, la
famille (des classes) de $Z_j^u$ pour $u$ parcourant les entiers
naturels, ne peut pas être libre, donc il existe un polynôme en $Z_j$
qui appartienne à $I$, et si on appelle $Z_j^u$ son monôme initial,
celui-ci doit être divisible par le monôme initial d'un certain $f_i$
de la base de Gröbner donnée, qui est donc lui-même une puissance
de $Z_j$.  Réciproquement, si pour tout $j$ il existe $i$ tel que
$f_i$ ait pour monôme initial une puissance de $Z_j$, disons
$Z_j^{u_j}$, alors les monômes de la forme $Z_1^{v_1} \cdots
Z_d^{v_d}$, où $v_j<u_j$ pour chaque $j$, qui sont en nombre fini,
engendrent $k[Z_1,\ldots,Z_d]/I$ (cf. par
exemple \ref{algorithmes-fondamentaux-anneau-quotient}), donc
$k[Z_1,\ldots,Z_d]/I$ est bien de dimension finie.
\end{proof}

\begin{remarque2}
On verra ailleurs (\XXX) que dans le contexte de la proposition
ci-dessus sont encore équivalents les énoncés suivants :
\begin{itemize}
\item l'anneau quotient $k[Z_1,\ldots,Z_d]/I$ est artinien (i.e.,
  toute suite décroissante d'idéaux de cet anneau stationne),
\item tout idéal premier de $k[Z_1,\ldots,Z_d]/I$ est maximal (i.e.,
  sa dimension de Krull vaut $0$).
\end{itemize}
\end{remarque2}

\begin{remarque2}
La troisième propriété
de \ref{equivalences-ideaux-affines-dimension-zero} est
algorithmiquement triviale à tester dès lors qu'on dispose d'une base
de Gröbner de $I$ (en fait, de façon générale, la dimension affine ou
même le polynôme de Hilbert-Samuel affine sont calculables une fois
connue une base de Gröbner, mais le cas particulier de la
dimension $0$ est exceptionnellement simple avec le critère qu'on
vient de présenter).
\end{remarque2}

\begin{proposition2}\label{projection-de-dimension-0}
Soit $I$ un idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$.  Alors pour
tout $t\leq d$, l'idéal d'élimination $J = I \cap k[Z_1,\ldots,Z_t]$
est lui aussi de dimension $0$.  En particulier (pour $t\geq 1$), il
n'est pas nul.
\end{proposition2}
\begin{proof}
Une fois choisi un ordre convenable (par exemple l'ordre
lexicographique) sur les monômes, comme expliqué
en \ref{base-de-groebner-elimination}, une base de Gröbner de $J$
s'obtient en considérant ceux des éléments d'une base de Gröbner
de $I$ qui appartiennent à $k[Z_1,\ldots,Z_t]$.  Mais la dernière
condition de \ref{equivalences-ideaux-affines-dimension-zero} est
alors manifestement satisfaite de $J$ si elle l'est de $I$.
\end{proof}


\subsection{Algèbre de décomposition universelle d'un polynôme}\label{section-algebre-de-decomposition-universelle}

\begin{lemme2}\label{lemme-modules-de-cauchy}
Soit $\mathfrak{F}(W_1,\ldots,W_d|T) = \prod_{i=1}^d(T-W_i) \in
\ZZ[W_1,\ldots,W_d,T]$, et définissons par récurrence sur $i$
\[
\begin{array}{c}
\mathfrak{F}_1(\underline{W}|T_1) =
\mathfrak{F}(\underline{W}|T_1)\\[.75ex]
\displaystyle
\mathfrak{F}_{i+1}(\underline{W}|T_1,\ldots,T_{i+1})
= \frac{\mathfrak{F}_i(\underline{W}|T_1,\ldots,T_{i-1},T_i) -
  \mathfrak{F}_i(\underline{W}|T_1,\ldots,T_{i-1},T_{i+1})}{T_i - T_{i+1}}
\end{array}
\]
(où $\underline{W}$ est une abréviation pour $W_1,\ldots,W_d$).  Alors
$\mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)$ (défini pour $1\leq
i \leq d$) est un polynôme à coefficients entiers en les variables
$W_1,\ldots,W_d$ et $T_1,\ldots,T_i$, et il est complètement
symétrique en chacun de ces jeux de variables.  On a exactement
\[
\mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)
= \sum_{j=0}^{d-i+1} (-1)^j e_j(W_1,\ldots,W_d)\, h_{d-i+1-j}(T_1,\ldots,T_i)
\]
où $e_j$ désigne le $j$-ième polynôme symétrique élémentaire (et $e_0
= 1$) et $h_j$ le $j$-ième polynôme symétrique complet (c'est-à-dire
la somme de tous les monômes de degré $j$ en ses variables ; on pose
notamment $h_0 = 1$).

De plus, si $u_1,\ldots,u_i$ sont deux à deux distincts, alors
$\mathfrak{F}_i(W_1,\ldots,W_d | W_{u_1},\ldots,W_{u_i}) = 0$.

Enfin, l'unique polynôme $\mathfrak{C}_i(E_1,\ldots,E_d |
T_1,\ldots,T_i)$ à coefficients entiers en les variables
$E_1,\ldots,E_d$ et $T_1,\ldots,T_i$ qui vérifie
$\mathfrak{C}_i(e_1(\underline{W}),\ldots,e_d(\underline{W}) |
T_1,\ldots,T_i) = \mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)$ est
donné par
\[
\mathfrak{C}_i(E_1,\ldots,E_d | T_1,\ldots,T_i)
= h_{d-i+1}(T_1,\ldots,T_i) +
\sum_{j=1}^{d-i+1} (-1)^j E_j \, h_{d-i+1-j}(T_1,\ldots,T_i)
\]
et on a
\begin{align*}
X^d + \sum_{i=1}^d (-1)^i E_i X^{d-i} &=
\mathfrak{C}_1(\underline{E} | T_1) + (X-T_1)\,
\mathfrak{C}_2(\underline{E} | T_1,T_2) \\[-1.5ex]
& + \cdots + (X-T_1)\cdots(X-T_{d-1})\, \mathfrak{C}_d(\underline{E} |
T_1,\ldots,T_{d-1})\\
&+ (X-T_1)\cdots(X-T_d)
\end{align*}
(où $\underline{E}$ est une abréviation pour $E_1,\ldots,E_d$).
\end{lemme2}
\begin{proof}
Commençons par montrer la relation
\[
\mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)
= \sum_{j=0}^{d-i+1} (-1)^j e_j(W_1,\ldots,W_d)\, h_{d-i+1-j}(T_1,\ldots,T_i)
\]
par récurrence sur $i$.  Pour $i=1$, il s'agit simplement de la
relation $\prod_{i=1}^d(T-W_i) = \sum_{j=0}^d (-1)^j
e_j(W_1,\ldots,W_d)\, T^{d-j}$ entre coefficients d'un polynôme et
fonctions symétriques de ses racines.  La relation de récurrence
découle de
\[
(T_i - T_{i+1})\, h_n(T_1,\ldots,T_{i+1}) = h_{n+1}(T_1,\ldots,T_{i-1},T_i)
- h_{n+1}(T_1,\ldots,T_{i-1},T_{i+1})
\]
(ce qui traduit pour le membre de droite de l'égalité ci-dessus la
même relation de récurrence que pour $\mathfrak{F}_i$).  Pour montrer
cette relation, on écrit $h_{n+1}(T_1,\ldots,T_{i-1},T') =
\sum_{u=0}^{n+1} T^{\prime u} h_{n+1-u}(T_1,\ldots,T_{i-1})$, on
remplace $T'$ par $T_i$ et $T_{i+1}$ et on utilise $T_i^u - T_{i+1}^u
= (T_i - T_{i+1}) h_{u-1} (T_i,T_{i+1})$ ; enfin, $\sum_{u=1}^{n+1}
h_{u-1} (T_i,T_{i+1}) h_{n+1-u}(T_1,\ldots,T_{i-1}) =
h_n(T_1,\ldots,T_{i+1})$.

La relation en question montre bien que
$\mathfrak{F}_i(\underline{W}|\underline{T})$ est un polynôme à
coefficients entiers complètement symétrique en chaque jeu de
variables (\textit{a priori} il était défini comme fonction
rationnelle, à coefficients rationnels, de ces jeux de variables).

Le fait que $\mathfrak{F}_i$ s'annule identiquement si on substitute
aux $T_j$ un sous-ensemble des $W_j$ vient de ce que $\mathfrak{F}_1$
s'annule trivialement dans ce cas, et que la relation de récurrence
s'applique avec cette spécialisation (les dénominateurs $W_{u_i} -
W_{u_{i+1}}$ sont inversibles dans les fractions rationnelles sur
$W_1,\ldots,W_d$).

L'existence et l'unicité du polynôme $\mathfrak{C}_i$ tel que
$\mathfrak{C}_i(e_1(\underline{W}),\ldots,e_d(\underline{W}) |
T_1,\ldots,T_i) = \mathfrak{F}_i(W_1,\ldots,W_d | T_1,\ldots,T_i)$
découle du fait que $\mathfrak{F}_i$ est complètement symétrique dans
les variables $W_j$ et que les $e_j(\underline{W})$ egendrent
linéairement les polynômes en question.  L'expression trouvée pour
$\mathfrak{F}_i$ donne alors immédiatement l'expression annoncée pour
$\mathfrak{C}_i$.

Enfin, pour montrer la dernière expression annoncée, remarquons que
$X^d + \sum_{i=1}^d (-1)^i E_i X^{d-i} =
\mathfrak{C}_1(\underline{E}|X)$ (d'après l'expression qu'on vient de
montrer) et que pour chaque $i$ on a
$\mathfrak{C}_i(\underline{E}|T_1,\ldots,T_{i-1},X) =
\mathfrak{C}_i(\underline{E}|T_1,\ldots,T_i) + (X-T_i)\,
\mathfrak{C}_{i+1}(\underline{E}|T_1,\ldots,T_i,X)$ (d'après la
formule de récurrence des $\mathfrak{F}_i$), en convenant que
$\mathfrak{C}_{d+1}(E_1,\ldots,E_d|\ldots)$ vaut identiquement $0$ :
en appliquant successivement cette formule pour $i$ allant de $1$ à
$d$ on trouve ce qu'on voulait.
\end{proof}

\begin{proposition2}\label{relations-algebre-de-decomposition-universelle}
Soit $k$ un corps et $f \in k[X]$ un polynôme unitaire, disons $f =
X^d + a_1 X^{d-1} + \cdots + a_d$.  On considère l'idéal $I$ de
$k[Z_1,\ldots,Z_d]$ engendré par les relations $e_i = (-1)^i a_i$ où
$e_i$ désigne le $i$-ième polynôme symétrique élémentaire en
$Z_1,\ldots,Z_d$.  Alors $I$ est de dimension $0$, et la base de
Gröbner réduite de $I$ pour l'ordre lexicographique (où on est convenu
d'ordonner les variables de la manière $Z_1 \preceq Z_2 \preceq \cdots
\preceq Z_d$) est fournie par les
\[
q_i := h_i(Z_1,\ldots,Z_{d-i+1}) + \sum_{j=1}^i a_j h_{i-j}(Z_1,\ldots,Z_{d-i+1})
\]
où $h_n$ est le $n$-ième polynôme homogène symétrique complet de
$Z_1,\ldots,Z_d$, c'est-à-dire la somme de tous les monômes de degré
$i$ en ces variables (on pose notamment $h_0=1$), et
$h_n(Z_1,\ldots,Z_{d-i+1})$ signifie qu'il est évalué en remplaçant
les $i-1$ dernières variables par $0$.  (Notamment, une de ces
relations, $q_d$, est donnée par $f(Z_1) = 0$.)
\end{proposition2}
\begin{proof}
Avec les notations du lemme précédent, remarquons que $q_i =
\mathfrak{C}_{d-i+1}(-a_1,\ldots,(-a)^d\,a_d | Z_1,\ldots,Z_{d-i+1})$.

On en déduit l'observation suivante : si $C$ est une $k$-algèbre et si
on a $f(X)$ s'écrit comme $\prod_{i=1}^d (X - z_i) \in C[X]$ pour
certains $z_1,\ldots,z_d \in C$, alors $q_i(z_1,\ldots,z_{d-i+1}) = 0
\in C$.  En effet, on a $e_i(z_1,\ldots,z_d) = (-1)^i a_i$ donc
$q_i(z_1,\ldots,z_{d-i+1}) =
\mathfrak{C}_{d-i+1}(-a_1,\ldots,(-a)^d\,a_d | z_1,\ldots,z_{d-i+1}) =
\mathfrak{F}_{d-i+1}(z_1,\ldots,z_d | z_1,\ldots,z_{d-i+1}) = 0$.

Appelons maintenant $J$ l'idéal engendré par $q_1,\ldots,q_d$, et
posons $A = k[Z_1,\ldots,Z_d]/I$ et $B = k[Z_1,\ldots,Z_d]/J$.  Il est
clair que $f(X) = \prod_{i=1}^d (X-Z_i) \in A[X]$ en développant le
membre de droite : d'après ce qu'on vient de montrer, $q_i$ s'annule
dans $A$ (c'est-à-dire, appartient à $I$), donc $J \subseteq I$.

Mais d'autre part, si dans l'égalité $X^d + \sum_{i=1}^d (-1)^i E_i
X^{d-i} = \mathfrak{C}_1(\underline{E} | T_1) + (X-T_1)\,
\mathfrak{C}_2(\underline{E} | T_1,T_2) + \cdots +
(X-T_1)\cdots(X-T_{d-1})\, \mathfrak{C}_d(\underline{E} |
T_1,\ldots,T_{d-1}) + (X-T_1)\cdots(X-T_d)$ (qui a lieu dans
$\ZZ[E_1,\ldots,E_d,T_1,\ldots,T_d,X]$) on remplace chaque $E_i$ par
$(-1)^i a_i$ et chaque $T_i$ par $Z_i$, on trouve $f(X) = q_d +
(X-Z_1)\, q_{d-1} + \cdots + (X-Z_1)\cdots(X-Z_{d-1})\, q_1 +
(X-Z_1)\cdots(X-Z_d)$.  En particulier, dans $B$, on a $f(X) = (X-Z_1)
\cdot (X-Z_d)$, c'est-à-dire que $e_i(Z_1,\ldots,Z_d) = (-1)^i a_i$,
ou encore que cette relation est dans $J$.  On vient donc de montrer
$I \subseteq J$.

À ce stade, nous savons que $I$ coïncide avec l'idéal $J$ engendré par
$q_1,\ldots,q_d$.  Il reste encore à montrer que ceux-ci en sont une
base de Gröbner.  \XXX : ceci va résulter du fait que leurs termes de
tête, $Z_{d-i+1}^i$ sont premiers entre eux.
\end{proof}

\begin{exemple2}\label{exemple-algebre-de-decomposition-universelle-non-connexe}
Si $f = X^3 + X^2 -2 X -1$, la base de Gröbner donnée ci-dessus est
formée des trois relations : $q_3 = Z_1^3 + Z_1^2 - 2 Z_1 - 1$
(c'est-à-dire $f(Z_1)$), $q_2 = Z_2^2 + Z_1 Z_2 + Z_2 + Z_1^2 + Z_1 -
2$ et $q_1 = Z_3 + Z_2 + Z_1 + 1$.
\end{exemple2}

\begin{definition2}\label{definition-algebre-de-decomposition-universelle}
Si $k$ est un corps et $f \in k[X]$ un polynôme unitaire de degré $d$
dont on note $a_i$ le coefficient de degré $d-i$, l'algèbre
$k[Z_1,\ldots,Z_d]/I$, où $I$ est l'idéal (décrit
en \ref{relations-algebre-de-decomposition-universelle}) engendré par
les relations $\sigma_i = (-1)^i a_i$, est appelée \emph{algèbre de
  décomposition universelle} de $f$.
\end{definition2}

\begin{corollaire2}\label{algebre-de-decomposition-universelle-est-finie}
Soit $k$ est un corps et $f \in k[X]$ un polynôme unitaire.  Si
$k[Z_1,\ldots,Z_d]/I$ désigne son algèbre de décomposition universelle
définie en \ref{definition-algebre-de-decomposition-universelle},
alors celle-ci est de dimension finie comme $k$-espace vectoriel
(l'idéal $I$ est de dimension $0$).
\end{corollaire2}
\begin{proof}
Ceci découle immédiatement de
\ref{equivalences-ideaux-affines-dimension-zero} appliqué à la base de
Gröbner donnée par la proposition \ref{relations-algebre-de-decomposition-universelle}.
\end{proof}

\begin{proposition2}\label{algebre-de-decomposition-universelle-separe-les-racines}
Soit $k$ est un corps et $f \in k[X]$ un polynôme unitaire
\emph{séparable}.  Si $k[Z_1,\ldots,Z_d]/I$ désigne son algèbre de
décomposition universelle définie
en \ref{definition-algebre-de-decomposition-universelle}, alors les
éléments $Z_i - Z_j$ (modulo $I$, pour $i\neq j$) y sont inversibles.
\end{proposition2}
\begin{proof}
Par symétrie, il suffit de le montrer pour $Z_1 - Z_2$.  On a vu
en \ref{relations-algebre-de-decomposition-universelle} que $I$
contient le polynôme $q_d = f(Z_1)$ (donc aussi $f(Z_2)$), et aussi $g
:= q_{d-1} = h_{d-1}(Z_1,Z_2) + a_1 h_{d-2}(Z_1,Z_2) + \cdots +
a_{d-1}$ (où comme d'habitude $f = X^d + a_1 X^{d-1} + \cdots +
a_{d-1} X + a_d$).  Comme $h_e(Z_1,Z_2) = Z_1^e + Z_1^{e-1}\,Z_2 +
\cdots + Z_2^e$ s'écrit aussi $(Z_1^{e+1}-Z_2^{e+1})/(Z_1-Z_2)$, on
peut écrire $g = \frac{f(Z_1) - f(Z_2)}{Z_1-Z_2}$.  Autrement dit :
$(Z_1-Z_2) g = f(Z_1)-f(Z_2)$.  En dérivant cette relation par rapport
à $Z_1$, on trouve : $(Z_1-Z_2) g'_1 = f'(Z_1)$ où $g'_1$ désigne la
dérivée $\frac{\partial g}{\partial Z_1}$ de $g$ par rapport à $Z_1$.
Pour montrer que $Z_1 - Z_2$ est inversible modulo $I$, il suffit de
montrer que $f'(Z_1)$ l'est.  Or l'hypothèse que $f$ soit séparable
signifie qu'il existe une relation de Bézout $uf' + vf = 1$ avec $u,v
\in k[X]$, et notamment $u(Z_1)$ est l'inverse de $f'(Z_1)$ modulo $f$
donc modulo $I$.
\end{proof}


\subsection{Idéaux radicaux de dimension $0$}\label{section-ideaux-radicaux-de-dimension-0}

On rappelle (\XXX) qu'un idéal $J$ d'un anneau $R$ est dit
\emph{radical} lorsque $x^n \in J$ implique $x \in J$ (quel que
soit $n \in \NN$), autrement dit lorsque le quotient $R/J$ est réduit.

Soit maintenant $R = k[Z_1,\ldots,Z_d]$.  Si $I$ est à la fois radical
et de dimension $0$, autrement dit si $R/I$ est réduit et artinien,
d'après \refext{Spec}{artinien réduit=produit corps}, cet anneau est
un produit de corps (extensions finies de $k$), à savoir les
$R/\mathfrak{m}$ où $\mathfrak{m}$ parcourt les idéaux maximaux de $R$
contenant $I$, qui sont en nombre fini et dont $I$ est
l'intersection (\XXX).

Dans cette situation ($I$ un idéal de dimension $0$ de $R =
k[Z_1,\ldots,Z_d]$), on dira que $I$ est \emph{géométriquement
  radical} lorsque $I$ est encore radical après passage à la clôture
algébrique $k'$ de $k$, c'est-à-dire que $I \cdot k'[Z_1,\ldots,Z_d]$
est radical ; cela revient à demander la même chose pour $k'$ la
clôture parfaite de $k$ (\XXX).  Cela équivaut à dire que $R/I$ est un
produit de corps qui soient des extensions (finies) \emph{séparables}
de $k$.  On dit aussi que $R/I$ est \emph{géométriquement réduite}.

\begin{proposition2}[« lemme 92 » de Seidenberg]\label{critere-seidenberg-ideal-radical}
Soit $I$ un idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$ (où $k$ est
un corps) tel que, pour chaque $1\leq j\leq d$, l'idéal $I$ contienne
un polynôme $g \in k[Z_j]$ (ne faisant intervenir que de la
variable $Z_j$) \emph{séparable}.  Alors $I$ est géométriquement radical.
\end{proposition2}
\begin{proof}
Puisque l'hypothèse effectuée reste vérifiée si on remplace $k$ par sa
clôture algébrique (ou parfaite), il nous suffit de montrer que $I$
est radical.

On va montrer que $I$ est intersection finie d'idéaux maximaux.

On procède par récurrence sur $d$.  Si $d=1$, comme tout diviseur d'un
polynôme séparable est lui-même séparable, le générateur unitaire
de $I$ est séparable, donc s'écrit comme produit de polynômes
séparables irréductibles deux-à-deux étrangers entre eux
$g_1,\ldots,g_r$, de sorte que (par le lemme chinois) $I$ est
l'intersection des idéaux maximaux engendrés par les différents $g_i$.

Pour $d>1$, l'hypothèse assure l'existence d'un $g \in I \cap k[Z_d]$
séparable.  Écrivons $g = g_1 \cdots g_r$ où les $g_i$ sont séparables
irréductibles et deux-à-deux étrangers entre eux.  Alors $I$ est
l'intersection des idéaux $I+(g_i)$ (\XXX).  Puisqu'on cherche à
prouver que $I$ est intersection finie d'idéaux maximaux, il suffit de
le prouver pour un $I+(g_i)$, ce qui permet de supposer que $g$ est
irréductible (et toujours séparable).

Soit $K = k[Z_d]/(g)$ le corps de rupture de $g$.  On a un morphisme
$\varphi \colon k[Z_1,\ldots,Z_d] \to K[Z_1,\ldots,Z_{d-1}]$.  L'idéal
$\varphi(I)$ vérifie les hypothèses faites sur $I$ lui-même : il est
de dimension $0$ (car l'image par $\varphi$ d'une famille finie
génératrice comme $k$-espace vectoriel de $k[Z_1,\ldots,Z_d]/I$ est
génératrice comme $K$-espace vectoriel de
$K[Z_1,\ldots,Z_{d-1}]/\varphi(I)$), et si $g^\natural \in I \cap
k[Z_j]$ est séparable alors $\varphi(g^\natural) \in \varphi(I) \cap
K[Z_j]$.  Il existe donc un nombre fini d'idéaux maximaux
$\mathfrak{m}_i$ de $K[Z_1,\ldots,Z_{d-1}]$ dont $\varphi(I)$ soit
intersection.  Mais alors $\varphi^{-1}(\varphi(I))$, qui est égal
à $I + \ker\varphi = I$, est l'intersection des
$\varphi^{-1}(\mathfrak{m}_i)$, et comme $k[Z_1,\ldots,Z_d] /
\varphi^{-1}(\mathfrak{m}_i) = K[Z_1,\ldots,Z_{d-1}] / \mathfrak{m}_i$
(puisque $\varphi$ est surjectif), ces idéaux sont maximaux.
\end{proof}

\begin{proposition2}\label{algebre-de-decomposition-universelle-est-reduite}
Soit $k$ est un corps et $f \in k[X]$ un polynôme unitaire
\emph{séparable}.  Si $k[Z_1,\ldots,Z_d]/I$ désigne son algèbre de
décomposition universelle définie
en \ref{definition-algebre-de-decomposition-universelle}, alors
celle-ci est géométriquement réduite (l'idéal $I$ est géométriquement
radical).
\end{proposition2}
\begin{proof}
La proposition \ref{relations-algebre-de-decomposition-universelle} et
sa conséquence \ref{algebre-de-decomposition-universelle-est-finie}
assurent que $I$ est de dimension $0$ et contient le polynôme
$f(Z_1)$, et aussi, pour des raisons de symétrie entre les variables,
chacun des $f(Z_j)$.  Ceci fournit précisément les hypothèses de la
proposition précédente, qui permet de conclure.
\end{proof}

\begin{remarque2}
En principe, la preuve de la
proposition \ref{critere-seidenberg-ideal-radical} est constructive en
ce sens qu'elle fournit des idéaux maximaux dont $I$ soit
l'intersection, à condition d'être capable d'effectuer des
factorisations dans tous les corps de rupture qui interviennent.  Ceci
fournira, en fait, une méthode théorique pour calculer des groupes de
Galois, à rapprocher de \XXX.
\end{remarque2}

La réciproque de \ref{critere-seidenberg-ideal-radical} est également
vraie :
\begin{proposition2}\label{critere-seidenberg-ideal-radical-reciproque}
Soit $k$ un corps, et soit $I$ un idéal de dimension $0$ et
géométriquement radical de $k[Z_1,\ldots,Z_d]$.  Alors pour tout
$1\leq j\leq d$, l'idéal $I$ contient un polynôme $g \in k[Z_j]$ (ne
faisant intervenir que de la variable $Z_j$) séparable, autrement dit
$I \cap k[Z_j]$ est lui-même géométriquement radical (i.e., engendré
par un polynôme séparable).
\end{proposition2}
\begin{proof}
Sans perte de généralité on peut supposer $j=1$.
D'après \ref{projection-de-dimension-0}, il existe un polynôme $g$ non
nul qui engendre $I \cap k[Z_1]$.

Traitons d'abord le cas où $k$ est supposé \emph{parfait}.  Si $g_1$
est la partie sans facteur carré de $g$ (i.e., le produit de ses
facteurs irréductibles distincts), alors $g_1^N$ est multiple de $g$
pour $N$ assez grand, donc $g_1^N \in I$, donc $g_1 \in I$ puisque $I$
est radical.  Ceci montre $g_1 \in I \cap k[Z_1]$, et comme $g$ était
censé engendrer $I \cap k[Z_1]$, on a $g = g_1$ sans facteur carré.
Comme $k$ était supposé parfait, $g$ est séparable.

Si maintenant $k$ n'est plus supposé parfait, soit $k'$ sa clôture
algébrique ou sa clôture parfaite.
D'après \ref{projection-et-extensions-de-corps}, on a $(I\cdot
k'[Z_1,\ldots,Z_d]) \cap k'[Z_1] = (I\cap k[Z_1]) \cdot k'[Z_1]$.
Comme $I\cdot k'[Z_1,\ldots,Z_d]$ est radical (puisque $I$ est supposé
géométriquement radical), l'idéal $(I\cap k[Z_1]) \cdot k'[Z_1]$ est
donc radical, mais cet idéal vaut $g\cdot k'[Z_1]$ : donc $g$ est
séparable (dans $k'[Z_1]$ ou dans $k[Z_1]$, cela revient au même).
\end{proof}

De façon plus concise, un idéal de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ est géométriquement radical si et seulement si
tous ses idéaux d'élimination à une seule variable le sont.

Ceci nous permet de donner une conséquence algorithmique :
\begin{algorithme2}\label{algorithme-test-ideal-radical-dimension-0}
Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ de
$k[Z_1,\ldots,Z_d]$, on peut tester si $I$ est géométriquement
radical.  De plus, si $k$ est parfait, on peut calculer le radical
de $I$.
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
Pour chaque $j$, utiliser \ref{base-de-groebner-elimination} pour
calculer le générateur unitaire de $I \cap k[Z_j]$ (c'est-à-dire une
base de Gröbner réduite de cet idéal), et tester si ce générateur est
séparable.  S'ils le sont tous, alors $I$ est géométriquement radical,
sinon, il ne l'est pas.

Dans le cas où $k$ est parfait, si $g_j$ désigne la partie sans
facteur carré du générateur unitaire de $I \cap k[Z_j]$ (qu'on peut
calculer en évaluant de façon répétée des pgcd avec la dérivée \XXX),
le radical de $I$ est l'idéal engendré par $I$ et tous les $g_j$.
\end{proof}
\begin{proof}
Le premier paragraphe ne fait que reformuler
\ref{critere-seidenberg-ideal-radical} et
\ref{critere-seidenberg-ideal-radical-reciproque}.

Seule l'affirmation contenue dans le dernier paragraphe nécessite
encore une démonstration.  Chacun des $g_j$ est contenu dans le
radical de $I$ (puisque $g_j^N$ pour $N$ assez grand).  Si $J$ désigne
l'idéal engendré par $I$ et tous les $g_j$, alors $J$ est radical
d'après \ref{critere-seidenberg-ideal-radical} (puisque les $g_j$ sont
séparables, $k$ étant parfait) ; de plus $J$ contient $I$, et est
contenu dans le radical de $I$.  Il résulte que $J$ est le radical
de $I$ (ce dernier étant le plus petit idéal radical contenant $I$).
\end{proof}


\subsection{Idéaux premiers de dimension $0$}\label{section-ideaux-premiers-de-dimension-0}

Il revient au même de dire d'un idéal $I$ de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ qu'il est premier ou qu'il est maximal (puisqu'une
algèbre finie intègre sur un corps est un corps, cf. \refext{Alg}{fini
  integre=corps} ou \refext{Spec}{artinien connexe implique local}),
autrement dit que le quotient $k[Z_1,\ldots,Z_d]/I$ est un corps.
Comme on l'a rappelé dans la section précédente (\XXX), si $J$ est un
idéal de dimension $0$ et radical de $k[Z_1,\ldots,Z_d]$, alors
$k[Z_1,\ldots,Z_d]/J$ est le produit des $k[Z_1,\ldots,Z_d]/I$ où $I$
parcourt les idéaux premiers (donc maximaux) contenant $I$, dont $J$
est alors l'intersection.

Les deux questions suivantes vont nous préoccuper ici : comment tester
algorithmiquement si un idéal de dimension $0$ et géométriquement
radical est premier, et comment, dans le cas contraire, calculer les
idéaux premiers qui le contiennent.

\begin{remarque2}\label{remarque-projection-et-ideaux-premiers}
On a vu dans la section précédente que, sur $k$ un corps parfait, un
idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$ est radical si et
seulement si tous ses idéaux d'élimination à une seule variable le
sont : on peut se demander si le même critère fonctionne pour tester
la primalité.  Il n'en est rien : si $f \in k[X]$ est un polynôme
unitaire irréductible (donc séparable, $k$ étant supposé parfait) de
degré $d$ et $k[Z_1,\ldots,Z_d]/I$ son algèbre de décomposition
universelle telle que définie
en \ref{definition-algebre-de-decomposition-universelle}, chacun des
idéaux d'élimination $I \cap k[Z_j]$ est engendré par $f(Z_j)$ comme
on l'a vu en \ref{relations-algebre-de-decomposition-universelle} (et
utilisé en \ref{algebre-de-decomposition-universelle-est-reduite} pour
conclure que $I$ est radical) ; pourtant $k[Z_1,\ldots,Z_d]/I$ n'est
pas nécessairement un corps, comme l'exemple suivant va le montrer.

Dans la situation
de \ref{exemple-algebre-de-decomposition-universelle-non-connexe},
c'est-à-dire l'algèbre de décomposition universelle de $f = X^3 + X^2
-2 X -1$, aucun des deux polynômes $Z_2 - Z_1^2 + 2$ et $Z_2 + Z_1^2 +
Z_1 - 1$ n'appartient à l'idéal $I$ des relations de l'algèbre (vu que
son terme initial n'est pas divisible par aucun de ceux de la base de
Gröbner), et pourtant leur produit $Z_2^2 + Z_2 Z_1 + Z_2 - Z_1^4 -
Z_1^3 + 3 Z_1^2 + 2 Z_1 - 2$ appartient à $I$ (il s'écrit comme $q_2 -
Z_1 q_3$).

On verra en fait (en \ref{section-calcul-galois-par-base-de-groebner}
ci-dessous) que, si $f$ est un polynôme unitaire irréductible
séparable de degré $d$, son algèbre de décomposition universelle est
un corps si et seulement si le groupe de Galois de $f$ est
$\mathfrak{S}_d$, et plus généralement le sous-groupe des permutations
des variables préservant un idéal premier fixé contenant $I$ est
justement le groupe de Galois de $f$.
\end{remarque2}

Comme on vient de le dire, il ne suffit pas (pour $I$ un idéal, même
de dimension $0$ et géométriquement radical) que les idéaux
d'élimination de $I$ à une seule variable soient premiers pour pouvoir
conclure que $I$ l'est.  Il y a cependant une situation où c'est
possible, comme on va le voir :

\begin{definition2}\label{definition-ideal-en-position-nette}
Un idéal $I$ de dimension $0$ de $k[Z_1,\ldots,Z_d]$ est dit \emph{en
  position nette} par rapport à la variable $Z_j$ lorsque le morphisme
$k[Z_j]/(I \cap k[Z_j]) \to k[Z_1,\ldots,Z_d]/I$ induit par
l'inclusion de $k[Z_j]$ dans $k[Z_1,\ldots,Z_d]$ est un isomorphisme
(c'est-à-dire, est surjectif).
\end{definition2}

\begin{remarque2}
Cette définition peut se faire pour un idéal quelconque (c'est-à-dire,
non supposé de dimension $0$), mais si $I$ est de dimension $0$, ce
qui implique la même chose pour $I \cap k[Z_j]$
d'après \ref{projection-de-dimension-0}, on peut donner la condition
équivalente suivante : les $k$-espaces vectoriels
$k[Z_1,\ldots,Z_d]/I$ et $k[Z_j]/(I \cap k[Z_j])$ ont même dimension.

Cette dernière condition est testable algorithmiquement : on sait
calculer la dimension de $k[Z_1,\ldots,Z_d]/I$ à partir d'une base de
Gröbner en comptant les monômes qui ne sont divisibles par le monôme
de tête d'aucun élément de la base de Gröbner ; et l'algorithme
d'élimination \ref{base-de-groebner-elimination} permet de calculer le
générateur unitaire de $I \cap k[Z_j]$ dont le degré est la dimension
du $k$-espace vectoriel $k[Z_j]/(I \cap k[Z_j])$.
\end{remarque2}

On peut donner un critère algorithmique encore plus précis :
\begin{proposition2}\label{critere-nettete-dimension-0}
Soit $I$ un idéal de dimension $0$ de $k[Z_1,\ldots,Z_d]$.  Alors $I$
est en position nette par rapport à $Z_1$ si et seulement si, pour
l'ordre lexicographique (où on est convenu d'ordonner les variables de
la manière $Z_1 \preceq Z_2 \preceq \cdots \preceq Z_d$), ou plus
généralement pour un ordre admissible $\preceq$ quelconque tel que
$\initial_{\preceq}(f) \in k[Z_1]$ implique $f \in k[Z_1]$, la base de
Gröbner réduite de $I$ est de la forme $h(Z_1), Z_2-g_2(Z_1), \ldots,
Z_d-g_d(Z_1)$ où $h,g_2,\ldots,g_d$ sont des polynômes uniquement en
la variable $Z_1$.
\end{proposition2}
\begin{proof}
Si la base de Gröbner réduite de $I$ est de la forme indiquée, alors
$I \cap k[Z_1]$ est l'idéal engendré par $h \in k[Z_1]$, disons de
degré $N$, et les monômes $1,Z_1,\ldots,Z_1^{N-1}$ forment à la fois
une base de $k[Z_1]/(I \cap k[Z_1])$ et de $k[Z_1,\ldots,Z_d]/I$ (ou
si l'on veut, la flèche évidente de l'un vers l'autre a une rétraction
consistant à envoyer $Z_j$ sur $g_j(Z_1)$ pour $j>1$, donc elle est
bien surjective).

Supposons maintenant que $I$ soit en position nette par rapport
à $Z_1$.  On sait d'après \ref{base-de-groebner-elimination} que la
base de Gröbner réduite $B$ de $I$ doit contenir un polynôme $h$ en la
seule variable $Z_1$, et il ne peut en contenir qu'un seul puisque $B$
est réduite, et ce polynôme engendre $I \cap k[Z_1]$.  Pour tout
$j>1$, l'hypothèse de position nette assure qu'il existe $\tilde g_j
\in k[Z_1]$ tel que $Z_j - \tilde g_j(Z_1) \in I$, et le terme initial
de ce monôme est $Z_j$ par les hypothèses faite sur l'ordre.  Quitte à
remplacer $\tilde g_j$ par le reste de sa division par $h$ dans
$k[Z_1]$, on peut supposer que $\tilde g_j$ a un degré strictement
inférieur à celui de $h$.  Pour chaque $j$, la base $B$ doit contenir
un terme dont le monôme initial divise $Z_j$, et donc soit
exactement $Z_j$.  Par minimalité, chacun de ces termes est de la
forme $Z_j - g_j(Z_1)$, et il est alors clair que les $\tilde g_j$
coïncident exactement avec les $g_j$ (même si on n'en a pas besoin
dans cette démonstration).
\end{proof}

Intuitivement (et au moins pour $I$ de dimension $0$ et
géométriquement radical), il faut comprendre que « $I$ en position
  nette par rapport à la variable $Z_j$ » signifie que la projection
sur la coordonnée $Z_j$ de l'ensemble des points défini par $I$
(disons, sur la clôture algébrique de $k$) est un isomorphisme au sens
où elle n'identifie pas de points.

Trivialement, si $I$ (idéal de dimension $0$) est en position nette
par rapport à $Z_j$, l'idéal $I$ est premier si et seulement si $I
\cap k[Z_j]$ l'est.  Lorsque c'est le cas que $I$ soit en position
nette (et on sait le détecter d'après ce qu'on a dit), il est donc
facile de tester si $I$ est premier.  Malheureusement, il n'existe pas
forcément une variable par rapport à laquelle que $I$ soit en position
nette, comme on l'a vu
en \ref{remarque-projection-et-ideaux-premiers}.  On va maintenant
chercher à expliquer pourquoi on peut néanmoins toujours (au moins si
$k$ est infini), « fabriquer » une variable $Y = c_1 X_1 + \cdots +
c_d X_d$, telle que l'idéal complété par cette relation soit en
position nette par rapport à $Y$.

\begin{proposition2}\label{nettete-projection-generique-dimension-0}
Soit $I$ un idéal géométriquement radical de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ où $k$ est un corps quelconque.  Soient
$C_1,\ldots,C_d$ et $Y$ de nouvelles indéterminées, notons $K =
k(C_1,\ldots,C_d)$, et soit $\tilde I$ l'idéal de $K[Y,
  Z_1,\ldots,Z_d]$ engendré par $I$ et par $Y - (C_1 X_1 + \cdots +
C_d X_d)$.  Alors $\tilde I$ est en position nette par rapport à $Y$.
\end{proposition2}
\begin{proof}
Commençons par appeler $\dot I$ l'idéal de $K[Z_1,\ldots,Z_d]$
engendré par $I$.  Comme toute base de Gröbner de $I$ constitue une
base de Gröbner de $\dot I$
(cf. \ref{bases-de-groebner-et-extensions-de-corps}), les conditions
assurant que $I$ est géométriquement radical de dimension $0$
(\ref{equivalences-ideaux-affines-dimension-zero} ainsi que
\ref{critere-seidenberg-ideal-radical} et
\ref{critere-seidenberg-ideal-radical-reciproque}) assurent aussi
que $\dot I$ est géométriquement radical de dimension $0$.  Par
ailleurs, le quotient $K[Y, Z_1,\ldots,Z_d]/\tilde I$ est isomorphe à
$K[Z_1,\ldots,Z_d]/\dot I$, l'isomorphisme consistant à envoyer $Y$
sur $C_1 X_1 + \cdots + C_d X_d$ (modulo $\dot I$) ; ceci assure
notamment que $\tilde I$ est lui ausssi géométriquement radical de
dimension $0$.

Remarquons le fait suivant : si $h \in \dot I$ alors $\frac{\partial
  h}{\partial C_i} \in \dot I$ pour tout $1\leq i\leq d$.  En effet,
si $g_1,\ldots,g_r$ (dans $k[Z_1,\ldots,Z_d]$) sont des générateurs
de $I$, ils engendrent aussi $\dot I$ (dans $K[Z_1,\ldots,Z_d]$) et
peut écrire $h = h_1 g_1 + \cdots + h_r g_r$ pour certains $h_i \in
K[Z_1,\ldots,Z_d]$, et en dérivant cette égalité par rapport à $C_i$
(les $g_i$ ayant une dérivée nulle), on voit que $\frac{\partial
  h}{\partial C_i}$ s'écrit aussi comme combinaison des $g_i$.

Soit maintenant $f \in K[Y]$ le polynôme unitaire engendrant l'idéal
$\tilde I \cap K[Y]$, autrement dit, le polynôme minimal de (l'image
de) $Y$ dans $K[Y, Z_1,\ldots,Z_d]/\tilde I$.
D'après \ref{critere-seidenberg-ideal-radical-reciproque}, ce polynôme
est séparable : on peut donc écrire une relation $f'U + fV = 1 \in
K[Y]$.  Soit $g \in K[Z_1,\ldots,Z_d]$ défini en substituant $C_1 Z_1
+ \cdots + C_d Z_d$ à la variable $Y$ dans $f$ : ce polynôme $g$
appartient encore à $\tilde I$, et même $\dot I$, puisqu'il s'agit de
dire que son image s'annule dans $K[Y, Z_1,\ldots,Z_d]/\tilde I \cong
K[Z_1,\ldots,Z_d]/\dot I$, image qui est la même que celle de $f$.
D'après le fait remarqué plus haut, on a $\frac{\partial g}{\partial
  C_i} \in \dot I$ pour tout $1\leq i\leq d$.  Ceci signifie que
$\frac{\partial f}{\partial C_i} + Z_i f'$, une fois substitué $C_1
Z_1 + \cdots + C_d Z_d$ à $Y$, appartient à $\dot I$ (rappelons que
$f'$ désigne la dérivée de $f$ par rapport à $Y$).  Par conséquent,
$\frac{\partial f}{\partial C_i} + Z_i f'$ lui-même appartient
à $\tilde I$ (toujours en utilisant l'isomorphisme $K[Y,
  Z_1,\ldots,Z_d]/\tilde I \cong K[Z_1,\ldots,Z_d]/\dot I$).  En
multipliant par $U$, on a donc $U \frac{\partial f}{\partial C_i} +
Z_i - V f \in \tilde I$.  C'est-à-dire que $Z_i$ est congru,
modulo $\tilde I$, à un polynôme $U \frac{\partial f}{\partial C_i} -
V f \in K[Y]$, ce qui affirme bien que $K[Y]/(\tilde I \cap K[Y]) \to
K[Y, Z_1,\ldots,Z_d]/\tilde I$ est surjectif, autrement dit que
$\tilde I$ est en position nette par rapport à $Y$.
\end{proof}

\begin{proposition2}\label{existence-combinaison-lineaire-nette-des-variables}
Soit $I$ un idéal géométriquement radical de dimension $0$ de
$k[Z_1,\ldots,Z_d]$ où $k$ est un corps infini.  Alors il existe
$c_1,\ldots,c_d \in k$ tel que l'idéal de $k[Y,Z_1,\ldots,Z_d]$
engendré par $I$ et $Y - (c_1 Z_1 + \cdots + c_d Z_d)$ soit en
position nette par rapport à $Y$, et plus généralement dans n'importe
quelle partie infinie de $k$ on peut trouver de tels $c_i$.
\end{proposition2}
\begin{proof}
La proposition précédente montre que pour chaque $i$ il existe $F \in
k(C_1,\ldots,C_d)[Y]$ tel que $Z_i \equiv F(C_1,\ldots,C_d,Y)
\pmod{\tilde I}$ (avec le $\tilde I$ défini plus haut), c'est-à-dire
que $Z_i \equiv F(C_1,\ldots,C_d, (C_1 Z_1 + \cdots C_d Z_d))
\pmod{I}$.  Si $q \in k[C_1,\ldots,C_d]$ est un dénominateur commun
aux coefficients de $F$ en la variable $Y$, on a $q\cdot Z_i \equiv
q\cdot F(C_1,\ldots,C_d, (C_1 Z_1 + \cdots C_d Z_d))$ où $q \cdot F
\in k[C_1,\ldots,C_d,Y]$.  Puisque $k$ est infini, on peut trouver
$c_1,\ldots,c_d$ dans $k$ (ou dans n'importe quelle partie infinie
prescrite à l'avance de $k$) n'annulant pas $q$
(cf. \refext{Calculs}{un-ferme-de-zariski-strict-n-est-pas-plein}
\XXX) : on a alors $Z_i \equiv F(c_1,\ldots,c_d, (c_1 Z_1 + \cdots c_d
Z_d)) \pmod{I}$ en divisant par $q(c_1,\ldots,c_d)$.  C'est bien ce
qu'on voulait montrer.
\end{proof}

\begin{algorithme2}\label{algorithme-test-ideal-premier-dimension-0}
Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ et
géométriquement radical de $k[Z_1,\ldots,Z_d]$, avec $k$ un corps
infini, si on sait tester l'irréductibilité des polynômes à une
variable à coefficients dans $k$, on peut tester si $I$ est premier.

(En particulier, si $k$ est un corps infini parfait, et si on sait
tester l'irréductibilité des polynômes à une variable à coefficients
dans $k$, alors donné un idéal $I$ de dimension $0$, on peut tester si
$I$ est premier.)
\end{algorithme2}
\begin{proof}[Description de l'algorithme]
S'agissant du deuxième paragraphe, sur un corps parfait un idéal est
radical si et seulement si il est géométriquement radical, on sait
tester ce fait
d'après \ref{algorithme-test-ideal-radical-dimension-0}, et si l'idéal
n'est pas radical en particulier il n'est pas premier.  Décrivons
maintenant l'algorithme pour tester la primalité d'un idéal
géométriquement radical sur un corps infini quelconque.

On trouve $c_1,\ldots,c_d$ tels que l'idéal $I$ soit en position nette
par rapport à $c_1 Z_1 + \ldots + c_d Z_d$ (avec l'abus de langage
évident, c'est-à-dire, au sens de la proposition précédente) : d'après
la proposition précédente, en prenant $c_1,\ldots,c_d$ dans un
ensemble suffisamment grand, ce sera toujours possible (formellement,
on peut commencer par tester tous les $d$-uplets d'un ensemble fini,
puis agrandir cet ensemble fini si aucun ne convient, et répéter
jusqu'à trouver un $d$-uplet qui convient, ce qui se produira toujours
si l'idéal était bien radical) : à chaque fois, on teste si on est en
position nette en utilisant \ref{critere-nettete-dimension-0} ou la
remarque qui précède.

(Remarquons que si on trouve $c_1,\ldots,c_d$ tels que $I$ soit en
position nette, on peut passer à la suite même si on n'a pas testé que
$I$ est géométriquement radical.  Cependant, le fait que $I$ soit
géométriquement radical permet de garantir que cette étape terminera
bien.)

Une fois trouvé $c_1,\ldots,c_d$ tels que $I$ soit en position nette
par rapport à $Y = c_1 Z_1 + \ldots + c_d Z_d$, on calcule le
générateur unitaire $h(Y)$ de l'idéal d'élimination de $I$ sur la
variable $Y$ (cf. \ref{base-de-groebner-elimination} et
\ref{critere-nettete-dimension-0}) : il ne reste plus qu'à tester
l'irréductibilité de $h$ dans $k[Y]$ puisque $k[Y]/(h) \cong
k[Z_1,\ldots,Z_d]/I$ est intègre si et seulement si $h$ est
irréductible.
\end{proof}

La correction de cet algorithme est claire compte tenu de ce qui a
déjà été expliqué.  Si $k$ est fini, on peut passer à
$k(C_1,\ldots,C_d)$, auquel cas l'idéal sera en position nette par
rapport à $Y = C_1 Z_1 + \ldots + C_d Z_d$
d'après \ref{nettete-projection-generique-dimension-0}, mais les
calculs seront nettement plus complexes (il vaut mieux, au moins,
passer à $k[C_1,\ldots,C_d]$ et calculer l'idéal d'élimination par
rapport à $C_1,\ldots,C_d,Y$).  Remarquons que dans ce cas, il faudra
savoir factoriser (ou au moins tester la primalité de) polynômes à
plusieurs variables (\XXX).  Par ailleurs, sous-jacent à cette
variante de l'algorithme est le résultat facile suivant :
\begin{proposition2}
Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ (où $k$ est un corps
quelconque) et soient $C_1,\ldots,C_m$ de nouvelles indéterminées.
Alors l'idéal $\tilde I$ engendré par $I$ dans
$k(C_1,\ldots,C_m)[Z_1,\ldots,Z_d]$ ou bien dans $k[C_1,\ldots,C_m,
  Z_1,\ldots,Z_d]$ est premier si et seulement si $I$ l'est.
\end{proposition2}
\begin{proof}
Dans le cas de $k[C_1,\ldots,C_m, Z_1,\ldots,Z_d]$, le quotient de
celui-ci par $\tilde I$ est l'anneau des polynômes en $m$ variables
$C_1,\ldots,C_m$, à coefficients dans le quotient
$k[Z_1,\ldots,Z_d]/I$.  Or il est bien connu qu'un anneau de polynômes
est intègre si et seulement si son anneau de coefficients l'est.

Dans le cas de $k(C_1,\ldots,C_m)[Z_1,\ldots,Z_d]$, on obtient
l'anneau qui inverse les éléments non nuls de $k[C_1,\ldots,C_m]$ dans
l'anneau ci-dessus : lui aussi est intègre si $I$ est premier, et a
des diviseurs de $0$ s'il y en a déjà dans $k[Z_1,\ldots,Z_d]/I$.
\end{proof}

En fait, on a fait mieux : une fois trouvés $c_1,\ldots,c_d$ tels que
$I$ soit en position nette par rapport à $c_1 Z_1 + \cdots + c_d Z_d$
au sens où l'idéal $\tilde I$ engendré par $I$ et $Y - (c_1 Z_1 +
\cdots + c_d Z_d)$ est en position nette par rapport à $Y$ dans $k[Y,
  Z_1,\ldots,Z_d]$, si $h$ est le générateur de l'idéal d'élimination
$\tilde I \cap k[Y]$, on a $k[Y]/(h) = k[Y] / (\tilde I \cap k[Y])
\cong k[Y, Z_1,\ldots,Z_d] / \tilde I \cong k[Z_1,\ldots,Z_d]/I$ : si
$h = h_1 \cdots h_r$ est la décomposition en facteurs irréductibles
de $h$ (forcément étrangers puisque $h$ est sans facteur carré), alors
le théorème chinois assure que $k[Y]/(h)$ est le produit des
$k[Y]/(h_i)$, si bien que, en appelant $g_i$ le polynôme obtenu en
substituant $c_1 Z_1 + \cdots + c_d Z_d$ à $Y$ dans $h_i$, et $J_i$
l'idéal $I + (g_i)$ de $k[Z_1,\ldots,Z_d]$, on a $k[Y]/(h_i) \cong
k[Z_1,\ldots,Z_d]/J_i$, les $J_i$ sont donc premiers et $k[Y]/(h)
\cong \prod_i (k[Z_1,\ldots,Z_d]/J_i)$.  Ceci prouve :

\begin{algorithme2}\label{algorithme-decomposition-ideal-radical-dimension-0}
Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ et
géométriquement radical de $k[Z_1,\ldots,Z_d]$, avec $k$ un corps
infini, si on sait factoriser les polynômes en une variable à
coefficients dans $k$, on peut trouver les idéaux maximaux $J_i$
contenant $I$.
\end{algorithme2}

\begin{exemple2}
Reprenons l'exemple commencé en
\ref{exemple-algebre-de-decomposition-universelle-non-connexe}
et \ref{remarque-projection-et-ideaux-premiers} : soit $f = X^3 + X^2
-2 X -1$, dont l'algèbre de décomposition universelle est engendrée
par les relations $q_3 = Z_1^3 + Z_1^2 - 2 Z_1 - 1$, $q_2 = Z_2^2 +
Z_1 Z_2 + Z_2 + Z_1^2 + Z_1 - 2$ et $q_1 = Z_3 + Z_2 + Z_1 + 1$ (qui
en sont une base de Gröbner).  Si on considère $(c_1,c_2,c_3) =
(1,-1,0)$, c'est-à-dire qu'on ajoute la relation $Y - Z_1 + Z_2$,
l'idéal $\tilde I$ a alors pour base de Gröbner les éléments
suivants : $Y^6 - 14 Y^4 + 49 Y^2 - 49$, $Z_1 + \frac{3}{14} Y^4 -
\frac{5}{2} Y^2 - \frac{1}{2} Y + 5$, $Z_2 + \frac{3}{14} Y^4 -
\frac{5}{2} Y^2 + \frac{1}{2} Y + 5$ et $Z_3 - \frac{3}{7} Y^4 + 5 Y^2
- 9$.  Le premier polynôme $h(Y) = Y^6 - 14 Y^4 + 49 Y^2 - 49$ de
cette liste, se factorise comme $(Y^3 - 7 Y + 7) \penalty0\, (Y^3 - 7
Y - 7)$.  En appelant $h_1$ et $h_2$ ces deux facteurs (dans l'ordre
où on les a écrits), les deux idéaux maximaux de $\QQ[Y,Z_1,Z_2,Z_3]$
contenant $\tilde I$ sont $\tilde J_1 = \tilde I + (h_1)$ et $\tilde
J_2 = \tilde I + (h_2)$ (par exemple, $\tilde J_1$ a pour base de
Gröbner $Y^3 - 7 Y + 7$, $Z_1 - Y^2 - 2 Y + 5$, $Z_2 - Y^2 - Y + 5$ et
$Z_3 + 2 Y^2 + 3 Y - 9$), et les deux idéaux maximaux de
$\QQ[Z_1,Z_2,Z_3]$ contenant $I$ sont $J_1 = I + (g_1)$ et $J_2 = I +
(g_2)$ où $g_1 = h_1(c_1 Z_1 + c_2 Z_2 + c_3 Z_3) = h_1(Z_1-Z_2)$ et
de même pour $g_2$.  On peut bien sûr en calculer une base de Gröbner,
par exemple pour $J_1$ : $Z_1^3 + Z_1^2 - 2 Z_1 - 1$, $Z_2 - Z_1^2 +
2$ et $Z_3 + Z_1^2 + Z_1 - 1$.

Pour rendre cet exemple plus compréhensible, notons que les racines de
$f$ dans $\CC$ sont $\xi_1 = \cos\frac{2\pi}{7}$, $\xi_2 =
\cos\frac{4\pi}{7}$ et $\xi_3 = \cos\frac{6\pi}{7}$ : les relations
$q_1,q_2,q_3$ engendrent l'idéal $I$ de toutes les relations possibles
entre $\xi_1,\xi_2,\xi_3$ quelle que soit la manière dont on les nomme
$Z_1,Z_2,Z_3$, et le polynôme $h$ a pour racines les six différences
possibles $Y = Z_1 - Z_2$ où $Z_1,Z_2$ sont deux quelconques des
$\xi_i$.  Le fait de choisir d'annuler $h_1$ ou $h_2$ limite les choix
de nommages de $\xi_1,\xi_2,\xi_3$ en $Z_1,Z_2,Z_3$ à seulement trois
possibilités parmi les six : on va expliquer pourquoi ce qu'on a fait
revient exactement à calculer le groupe de Galois de $f$.
\end{exemple2}

\begin{remarque2}
On observera que si $k$ est un corps sur lequel on sait factoriser les
polynômes en une variable, sans l'hypothèse que $k$ est parfait, nous
n'avons pas donné d'algorithme permettant de décider si un idéal de
dimension $0$ de $k[Z_1,\ldots,Z_d]$ est radical, ou bien premier
(seulement pour savoir s'il est géométriquement radical, et pour
savoir s'il est premier en supposant qu'il est géométriquement
radical).  Ce n'est pas un oubli : un tel algorithme n'existe pas, car
le problème est \emph{indécidable} au sens de Church-Turing.

En effet, il existe (\XXX --- référencer Fröhlich \& Shepherdson
lemme 7.21 et th. 7.27) un corps $k$ de caractéristique $p>0$ tel
qu'on sache algorithmiquement factoriser les polynômes dans $k[X]$
mais que si $k' = k[Y]/(h)$ est une certaine extension algébrique
finie purement inséparable de $k$ alors il est indécidable de savoir
si un élément $\xi$ de $k'$ a une racine $p$-ième dans $k'$.  Or si
$I_\xi$ désigne l'idéal de $k[X,Y]$ engendré par $h \in k[Y]$ et par
$X^p - \tilde\xi$ (où $\tilde\xi \in k[Y]$ est un relevé quelconque
de $\xi$, dont le choix n'a pas d'importance), alors $k[X,Y]/I_\xi =
k'[X]/(X^p-\xi)$ est un corps, ou est réduit, si et seulement si $\xi$
a une racine $p$-ième.  Donc arriver à décider si $I_\xi$ est premier,
ou radical, revient à décider si $\xi$ a une racine $p$-ième, ce qui
n'est pas possible en général.
\end{remarque2}


\section{Quelques applications}

\subsection{Application au calcul d'un groupe de Galois}\label{section-calcul-galois-par-base-de-groebner}

\subsubsection{} Plaçons-nous dans la situation suivante : $f \in
k[X]$ est un polynôme unitaire séparable de degré $d$ sur un corps
$k$, et $k[Z_1,\ldots,Z_d]/I$ est son algèbre de décomposition
universelle telle qu'introduite
en \ref{section-algebre-de-decomposition-universelle}.  On a vu en
\ref{algebre-de-decomposition-universelle-est-finie} et
\ref{algebre-de-decomposition-universelle-est-reduite} que cette
algèbre est géométriquement réduite de dimension $0$.  Il s'agit donc
(cf. les remarques initiales
de \ref{section-ideaux-premiers-de-dimension-0}) du produit des corps
$k[Z_1,\ldots,Z_d]/J_i$ où les $J_i$ sont les idéaux maximaux
contenant $I$, et on a vu
en \ref{algorithme-decomposition-ideal-radical-dimension-0} comment
calculer les $J_i$ (au moins dans le cas où $k$ est infini et où on
sait factoriser les polynômes en une variable sur $k$).

Si $J$ est un quelconque de ces idéaux maximaux contenant $I$, alors
$K := k[Z_1,\ldots,Z_d]/J$ est un corps engendré par $k$ et par les
images de $Z_1,\ldots,Z_d$.  Mais comme $I$, donc $J$, contient le
polynôme $f(Z_1)$
(d'après \ref{relations-algebre-de-decomposition-universelle}), et
aussi, pour des raisons de symétrie entre les variables, chacun des
$f(Z_j)$, les images des $Z_j$ dans $K$ sont des racines du
polynôme $f$.  Mais de plus, ces images sont deux à deux distinctes
dans $K$ car
\ref{algebre-de-decomposition-universelle-separe-les-racines} implique
que les $Z_j - Z_{j'}$ (pour $j\neq j'$) sont inversibles modulo $I$,
donc \textit{a fortiori} modulo $J$ : donc ce sont exactement les
racines de $f$ dans $K$.  Bref, $K$ est un corps extension de $k$ et
engendré au-dessus de $k$ par les $d$ racines du polynôme $f$ :
c'est-à-dire que c'est « le » corps de décomposition de $f$ sur $k$.

Le groupe de Galois de $f$ étant donc (\XXX --- référence précise) le
groupe des automorphismes de $K$ au-dessus de $k$, il peut se voir
comme le groupe des permutations de $Z_1,\ldots,Z_d$ qui laissent
l'idéal $J$ invariant ; connaissant une base de Gröbner de $J$, il est
facile de tester si une permutation des variables le laisse invariant,
il suffit de tester si la permutation appliquée à chaque élément de la
base de Gröbner est encore dans l'idéal.  On a donc montré :

\begin{algorithme2}\label{algorithme-calcul-galois-par-base-de-groebner}
Donné un polynôme $f \in k[X]$, avec $k$ infini, si on sait
factoriser les polynômes en une variable à coefficients dans $k$, on
sait calculer le groupe de Galois de $f$ comme le groupe des
permutations de $Z_1,\ldots,Z_d$ qui fixent un idéal $J$ maximal
contenant l'idéal $I$ des relations de l'algèbre de décomposition
universelle de $f$ (explicité
en \ref{relations-algebre-de-decomposition-universelle}) ; et de façon
plus particulière (si on sait tester l'irréductibilité des polynômes à
une variable à coefficients dans $k$), on sait tester si ce groupe de
Galois est $\mathfrak{S}_d$ (en testant si $I$ est premier).
\end{algorithme2}

\begin{remarque2}
L'algorithme qu'on vient de présenter est à peu près équivalent au
calcul du groupe de Galois par le moyen des résolvantes
(\refext{Calculs}{strategie-algorithmique-generale-calcul-groupes-de-galois})
dans le cas des résolvantes \emph{linéaires}, à ceci près qu'on ne se
contente pas de chercher à savoir si le groupe de Galois est ou n'est
pas inclus dans tel ou tel groupe (disons, s'il est égal à
$\mathfrak{S}_d$) mais qu'on va plus loin pour le connaître
exactement, au prix de calculs de bases de Gröbner éventuellement très
lourds.
\end{remarque2}

\begin{remarque2}
Au cours de l'application de l'algorithme qu'on vient de présenter, si
on a utilisé la
proposition \ref{existence-combinaison-lineaire-nette-des-variables}
pour trouver une combinaison $k$-linéaire $c_1 Z_1 + \cdots + c_d Z_d$
des indéterminées par rapport à laquelle l'ideal $I$ (donc aussi $J$)
soit en position nette, alors l'image modulo $J$ de cette combinaison
$c_1 Z_1 + \cdots + c_d Z_d$, c'est-à-dire la combinaison
correspondante, dans $K$, des racines de $f$, fournit un \emph{élément
  primitif} de $K$.

Par ailleurs, on peut observer que
\ref{algorithme-calcul-inverse-algebre-de-type-fini} permet
d'effectuer dans le corps de décomposition $K$ des calculs d'inverse
(i.e., on en a une présentation algorithmique non seulement comme
anneau mais bien comme corps).
\end{remarque2}



\subsection{Application au calcul de racines d'un polynôme}

\subsubsection{} Plaçons-nous de nouveau dans la situation suivante : $f \in
k[X]$ est un polynôme unitaire séparable de degré $d$ sur un corps
$k$, et $k[Z_1,\ldots,Z_d]/I$ est son algèbre de décomposition
universelle telle qu'introduite
en \ref{section-algebre-de-decomposition-universelle}.  Si maintenant
$E$ est un corps extension de $k$ et dans lequel $f$ est scindé, la
donnée des racines $\xi_1,\ldots,\xi_d$ de $f$ dans $E$ définit un
morphisme $k[Z_1,\ldots,Z_d]/I \to E$ (envoyant $Z_i$ modulo $I$ sur
$\xi_i$ dans $E$).

À un tel niveau de généralité, on ne peut pas donner un sens précis à
ce qu'on veut dire par « calculer les $\xi_i$ », mais on peut
néanmoins donner une technique souvent intéressante dans ce contexte :
il s'agit de trouver une expression $\eta = P(\xi_1,\ldots,\xi_d)$ en
les $\xi_i$, où $P \in k[Z_1,\ldots,Z_d]$ qui soit d'une certaine
manière plus simple à calculer (le sens précis dépendant du type de
calcul qu'on cherche à mener) ; on peut alors séparer le calcul de la
façon suivante : d'abord calculer l'idéal d'élimination sur la
variable $Y$ de l'idéal $\tilde I = I + (Y-P)$ de
$k[Y,Z_1,\ldots,Z_d]$, ce qui fournit un polynôme $R_P$ annulateur de
$\eta$, trouver les racines de $R_P$ dans $E$ et identifier celle qui
est $\eta$, puis travailler dans l'algèbre
$k(\eta)[Z_1,\ldots,Z_d]/\hat I$ où cette fois $\hat I = I + (P -
\eta)$.  On appliquera typiquement cette idée avec $P$ un polynôme qui
soit « partiellement » symétrique en les $Z_j$ : on verra dans le
chapitre \refext{Calculs}{} que $R_P$ est une « résolvante » (\XXX) et
dans le chapitre \refext{Radicaux}{} que prendre $P = \sum \zeta^{ij}
\xi_j$, où $\zeta$ est une racine $d$-ième de l'unité, peut s'avérer
intéressant.

\XXX --- Tout ceci est assez vaseux.



\ifx\danslelivre\undefined
\bibliography{../configuration/bibliographie-livre}
\bibliographystyle{../configuration/style-bib-livre}
\end{document}
\fi