\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection, NoEqCountersInSection, ThmDefs]{cedram}
\usepackage{xups97-01}
\setcounter{tocdepth}{2}
\hyphenation{Noether}

\makeatletter
\def\lsectionpart{\let\l@section\l@part}
\makeatother

\begin{document}
\frontmatter

\title[Bases standard, élimination et complexité]{Bases standard, élimination~et~complexité}

\author[\initial{M.} \lastname{Giusti}]{\firstname{Marc} \lastname{Giusti}}

\address{Laboratoire GAGE, GDR de Calcul Formel MEDICIS, Centre de Mathématiques, École Polytechnique, 91128 Palaiseau cedex}
\email{Marc.Giusti@Polytechnique.fr}
\urladdr{http://www.lix.polytechnique.fr/~giusti/}

\thanks{Journées X-UPS 1997. Calcul formel. Prépublication du Centre de mathématique de l'École polytechnique, 1997}


\begin{abstract}
Étant donné un système d'équations linéaires
homogènes à $n+1$ variables, les formules de Cramer permettent de
paramétrer les solutions en fonction d'un certain nombre de
variables que l'on peut choisir arbitrairement.

Nous nous proposons d'établir un résultat analogue pour des
systèmes d'équations non linéaires: il s'agit du
lemme de normalisation de Noether. Nous allons nous
poser à son sujet des questions d'algorithmique et de
complexité. Tout ce qui suit provient essentiellement des deux
articles \cite{G88}, \cite{GH93}.
\end{abstract}

\dedicatory{%
``The purpose of computing is insight, not numbers.''\\
\textup{Richard W. Hamming}, Numerical Methods for Scientists and
Engineers, \textup{McGraw-Hill, New-York (1962), p.\,v.}\\
``The purpose of computing is insight, not formulas.''\\
\textup{in} Future Directions for Research in Symbolic Computation, \textup{SIAM
Reports on Issues in the Mathematical Sciences, Philadelphia (1990),
p.\,29.}\vspace*{\baselineskip}
}
\maketitle

\tableofcontents
\mainmatter
\vspace*{-3\baselineskip}
\mbox{}
\part{Le lemme de normalisation de Noether}

\section{La situation linéaire}

Soient $f_{1},\ldots ,f_{s}$ des formes linéaires homogènes à $n+1$
variables $x_{0},\ldots ,x_{n}$, à coefficients dans un corps $k$:
$$
f_{i}(x_{0},\ldots ,x_{n}) = \sum_{j=0}^{n} f_{ij} x_{j} \; \; \;
i=1,\ldots ,s .
$$

\subsection{Point de vue de l'algèbre}

Si la $s\times (n+1)$ matrice $F$ qui leur est associée est de rang
$n-r$, il existe un sous-mineur $M$ non nul d'ordre $n-r$. Après
changement de variables (en fait une renumérotation), nous pouvons
supposer qu'il est bâti sur les dernières colonnes $r+1,\ldots
,n$, et après une autre renumérotation des indices des formes,
que ce sont les $n-r$ premières qui sont linéairement
indépendantes. Soient $M_{j}$ ($j=r+1,\ldots ,n$) les mineurs
obtenus en substituant à la colonne $j$ de $M$ la colonne
formée par les $-\sum_{j=0}^{r} f_{ij} x_{j}$ ($i=1,\ldots ,n-r$). Ce
sont des formes linéaires homogènes en $x_{0},\ldots
,x_{r}$. Les solutions du système linéaire homogène
associé se paramètrent alors par les formules de Cramer:
$$
M x_{j} = M_{j} (x_{0},\ldots ,x_{r}), \quad j=r+1,\ldots ,n
$$
qui donnent les $n-r$ dernières coordonnées (variables {\em
liées}) en fonction des $r+1$ premières arbitrairement choisies
(variables {\em libres}). L'espace vectoriel des solutions devient ainsi
le graphe d'une application linéaire $k^{r+1} \rightarrow
k^{n-r}$.

\subsection{Point de vue de la géométrie}

Rappelons que l'{\em espace projectif} ${\bf P}_{k}^n$ (ou plus
simplement ${\bf P}^n$) est l'ensemble des classes d'équivalence des
$(n+1)$-uples $(a_0,\ldots , a_n)$ d'éléments de $k$, non tous
nuls, pour la relation d'équivalence identifiant les points d'une
même droite de $k^{n+1}$ passant par l'origine. Nous appellerons
encore les éléments de ${\bf P}^n$ des {\it points}.\enlargethispage{\baselineskip}

Une {\em sous-variété linéaire} de ${\bf P}^n$ est
définie par un système d'équations linéaires
homogènes. Si le rang de ce dernier est $n-r$, sa {\em dimension}
est par définition $r$.

Soient $L_{i+1}$ et $B^i$ deux sous-variétés linéaires de ${\bf
P}^n$, respectivement de codimension $i+1$ et de dimension $i$, qui ne
se coupent pas. À tout point qui n'est pas dans $L_{i+1}$, on peut
successivement associer la sous-variété linéaire de codimension
$i$ qu'il engendre avec $L_{i+1}$, puis l'unique point d'intersection de
cette dernière avec la sous-variété $B^i$. L'application ainsi
définie est {\it la projection linéaire} de centre $L_{i+1}$ sur~$B^i$.

L'interprétation géométrique des formules de Cramer est
alors la suivante: si le rang est $n-r$, nous pouvons partitionner
l'ensemble des variables en deux paquets, après renumérotation
$x_{0},\ldots ,x_{r}$ (varia\-bles libres) et $x_{r+1},\ldots ,x_{n}$
(variables liées). Définissons les deux sous-variétés
linéaires $L_{r+1}$ d'équations $x_{0} = \cdots = x_{r} = 0$ et
$B^{r}$ d'équations $x_{r+1} = \cdots = x_{n} = 0$. La
sous-variété linéaire d'équations $f_{1}= \cdots = f_{s}
= 0$ ne coupe pas $L_{r+1}$, et la projection de centre $L_{r+1}$
l'envoie surjectivement sur $B^{r}$.

\subsection{Point de vue de l'algorithmique}

Supposons maintenant que nous voulions faire effectuer à une machine
le paramétrage ci-dessus. Il faut déjà avoir à faire
à un corps {\em effectif}, c'est-à-dire un corps
représentable en machine dont les quatre opérations
arithmétiques $+,-,*,/$ sont réalisables par des algorithmes,
sans oublier le test d'égalité. Par exemple, nous apprenons tous à
l'école primaire comment représenter les entiers par leur
écriture décimale, et des algorithmes d'addition, soustraction,
multiplication et division (réfléchissons un peu au cas de cette
dernière...); quant au test d'égalité, il se
révèle trivial sur cette écriture unique. Après
extensions, le corps des rationnels devient ainsi le premier exemple de
corps effectif. Il est néanmoins relativement aisé de rencontrer
en calcul formel des corps non effectifs: cf. \cite{R68}.

À partir de la matrice $F$, l'algorithme du pivot de Gauss permet
d'exhiber un mineur non nul de taille maximale, avec un nombre
d'opérations arithmétiques polynomial en $s,n$.

\section{La situation générale}

Soient $f_{1},\ldots ,f_{s}$ des formes homogènes à $n+1$
variables $x_{0},\ldots ,x_{n}$, de degrés $d_{1},\ldots ,d_{s}$,
à coefficients dans un corps $k$:
$$
f_{i}(x_{0},\ldots ,x_{n}) = \sum_{|a|=d_i} f_{ia} x_{0}^{a_0}\ldots
x_{n}^{a_n},\quad i=1,\ldots ,s
$$
où $a=(a_{0},\ldots ,a_{n})$ est un élément de ${\bf
N}^{n+1}$ de degré $|a| = a_{0} + \cdots + a_{n}$.

\subsection{Point de vue de l'algèbre}

L'anneau $R = k[x_0,\ldots , x_n]$ peut être muni d'une structure d'anneau
gradué par la décomposition canonique $R = \bigoplus _{s \geq 0} R_s$
où $R_s$ est l'ensemble des polynômes homogènes de degré
$s$. L'idéal $I$ de $R$ engendré par les formes $f_{1},\ldots
,f_{s}$ est {\it homogène} et respecte la graduation puisque
$I=\bigoplus _{s \geq 0} I \cap R_s$.\enlargethispage{\baselineskip}

\begin{vera}
Après un changement liné\-aire de variables, que nous noterons encore
$x_{0},\ldots ,x_{n}$, il existe un indice $r$ tel que la
composée
$$
0 \to k[x_0,\ldots , x_r] \to k[x_0,\ldots , x_n] \to k[x_0,\ldots ,
x_n]/I \to 0
$$
de l'injection et de la surjection canoniques soit encore injective et
réalise une extension entière d'anneaux.
\end{vera}

Dit autrement, nous pouvons après changement de variables
partitionner ces dernières en deux paquets: les $r+1$ premières
seront dites {\em libres} et les $n-r$ dernières {\em liées},
telles que:
\begin{itemize}
\item[--] il n'existe pas dans l'idéal $I$ de polynôme ne
dépendant que des variables libres;
\item[--] il existe des polynômes $p_{r+1},\ldots ,p_{n}$ de $k[x_0,
\ldots , x_r][t]$, unitaires en $t$, tels que
$p_{r+1}(x_0,\ldots ,
x_r)(x_{r+1}),\ldots ,p_{n}(x_0,\ldots , x_r)(x_{n})$ appartiennent
à l'idéal $I$ (relations de dépendance intégrale).
\end{itemize}

\subsection{Point de vue de la géométrie}

Étant donné une extension~$K$ de $k$, un zéro dans ${\bf P}_{K}^{n}$
d'un polynôme homogène est un point qui l'annule, et cette
notion est bien définie. Dorénavant nous supposerons quand nous
parlerons de géométrie que l'extension est suffisamment grosse;
pour simplifier définitivement que $k$ est algébriquement clos
et nous noterons le projectif ${\bf P}^{n}$.

L'ensemble des zéros de l'idéal homogène $I$ est l'ensemble
des zéros des éléments homogènes de $I$, ou ce qui revient au
même, l'ensemble des zéros des générateurs de $I$:
$$
Z(I) = \{ a \in {\bf P}^n \mid f(a) = 0 \;\;\forall f \in I \}.
$$

Un sous-ensemble de ${\bf P}^n$ est {\it algébrique} s'il existe un
idéal homogène tel qu'il en soit l'ensemble des
zéros. L'intersection de toute famille d'ensembles algébriques
$Z(I_{\alpha})$ est encore algébrique, puisque c'est $Z(\sum _\alpha
I_{\alpha})$. On dit que deux ensembles algébriques s'évitent
(\resp se coupent) si leur intersection est vide (\resp n'est pas vide).
Les sous-variétés linéaires définies ci-dessus sont les
premiers exemples d'ensembles algébriques.

La version algébrique implique alors:

\begin{verg}
Il exis\-te deux sous-variétés linéaires $L_{r+1}$ de codimension $r+1$ et~$B^{r}$ de dimension $r$ telles que:
\begin{itemize}
\item[--] les deux ensembles $Z(I)$ et $L_{r+1}$ ne se coupent pas;
\item[--] la restriction à $Z(I)$ de la
projection $\pi$ de centre $L_{r+1}$ et de base~$B^{r}$ est surjective et
finie, c'est-à-dire que pour tout point $b$ de~$B^{r}$, la~fibre
$\pi^{-1}(b)$ est constitué d'un nombre fini non nul de points.
\end{itemize}
\end{verg}

En fait cette assertion même affaiblie par la
suppression de l'hypothèse de finitude implique en retour la version
algébrique.

\subsection{Point de vue de l'algorithmique}

Afin d'exhiber un algorithme qui rend à partir d'un système de
générateurs de l'idéal $I$ les objets promis par le lemme de
normalisation, il faut d'abord étendre à l'algèbre de
polynômes $R=k[x_{0},\ldots ,x_{n}]$ l'effectivité des
opérations possibles et le test d'égalité, ce qui s'effectue
sans difficulté particulière en développant sur la base des
monômes.

Les ennuis commencent avec la structure quotient: la question de
l'effectivité de l'anneau quotient bute sur le test de
nullité. Si additionner ou multiplier des classes se résoud
immédiatement par la pensée, ce n'est plus le cas pour le
problème de l'appartenance à un idéal.

Le but du premier chapitre est d'y répondre; les outils introduits
seront même assez puissants pour résoudre totalement la question
de l'effectivisation du lemme.\enlargethispage{1.5\baselineskip}

\part{Du côté de l'écriture}

Passons en revue quelques cas particuliers du problème
d'appartenance à un idéal. Dans le cas principal des idéaux
(non nécessairement homogènes) de $k[x]$, le vénérable
algorithme d'Euclide exhibe un plus grand commun diviseur de la famille,
et la question de l'appartenance se réduit au test de nullité du
reste de la division par ce PGCD.

L'algèbre linéaire nous permet de conclure quand le degré
des générateurs (toujours non nécessairement homogènes)
est au plus $1$.

Dans les deux cas, observons que nous avons implicitement
considéré que les polynômes étaient représentés
par leur {\em écriture} sur la base des monômes, introduit un
{\em ordre total} sur les monômes et fabriqué des règles de
{\em réécriture}, que nous avons appliquées à un
polynôme candidat à l'appartenance: et celle-ci est
réalisée si et seulement si le processus de réécriture
aboutit au polynôme nul, qui est facile à reconnaître\ldots
avec cette représentation.

Précisons les choses. Dans le premier cas, un polynôme
est représenté par le vecteur de ses coefficients, les
monômes sont rangés par ordre décroissant. Nous
considérons tout polynôme non nul de l'idéal, de degré
$d$, écrit (congru à) $x^{d}-r$, où $r$ est de degré
strictement inférieur à $d$. Diviser par ce polynôme n'est
pas autre chose qu'appliquer récursivement et autant de fois qu'il
est possible aux monômes du dividende la règle de
réécriture $x^{d} \to r$. Le processus s'arrête
sur le reste de la division euclidienne.

Dans le deuxième cas, un polynôme est toujours
représenté par le vecteur de ses coefficients. S'il existe parmi
les données une constante non nulle, l'idéal est trivial. Sinon,
nous considérons un générateur de l'idéal, de degré
au plus $1$ mais non constant, après renumérotation des
variables écrit (congru à)
$x_{n}-\ell(x_{1},\ldots,x_{n-1})$. L'application répétée de la
règle de réécriture $x_{n} \to \ell$ permet de se ramener à
une situation avec une variable de moins. À la réflexion, ceci
correspond à choisir un ordre lexicographique pour ordonner les
monômes.

Résumons nous: dans les deux cas, nous avons choisi un ordre total
sur les monômes, permettant de réécrire le monôme
dominant en un polynôme formé de monômes dominés. Vient
d'abord une phase de préparation ou {\em compilation} de l'idéal:
en combinant ces règles entre elles, nous avons abouti à un
système particulier de générateurs, promus diviseurs: le
critère d'appartenance est la nullité du reste par une {\em
division}.

Cette construction va se généraliser à tout idéal
engendré par des générateurs non nécessairement
linéaires.

\section{Bases standard}

Nous retournons ici à l'algèbre des polynômes $R=k[x_0, x_1,
\ldots , x_n]$ graduée par le degré total. Pour étudier ses
idéaux, l'idée de
considérer un ordre total sur les monômes de $R_d$ remonte au
moins à \cite{M27}.

Par monôme on entend ici le produit de puissances. L'ensemble des
monômes de $k[x_{0},\ldots,x_{n}]$ est muni d'une structure de
monoïde multiplicatif. Il est parfois commode de considérer le
monoïde additif ${\bf N}^{n+1}$ isomorphe via $x_{0}^{a_{0}} \cdots
x_{n}^{a_{n}} \mapsto (a_{0},\ldots,a_{n})$.

Un ordre total sur les monômes est dit {\em admissible} ou {\em
compatible} s'il respecte la structure du monoïde, c'est-à-dire
si l'ordre d'une paire ordonnée de monômes ne change pas en
multipliant par un troisième. En fait, il faut aussi indiquer dans
quel sens utiliser l'ordre pour élire le monôme dominant d'un
polynôme.

Il existe un théorème de classification des ordres totaux
compatibles. Mais les exemples fondamentaux suivants, admettant
une interprétation géométrique, suffiront à nos besoins.

\skippointrait
\begin{defi}[ordre lexicographique inférieur (\resp supérieur)]
Un point $a = (a_{0},\ldots , a_{n})$ de ${\bf N}^{n+1}$ sera dit plus
petit qu'un point $b = (b_{0},\ldots , b_{n})$ pour l'ordre
lexicographique inférieur (\resp plus grand pour l'ordre
lexicographique supérieur) si et seulement s'il existe un indice $i$
($0 \leq i \leq n$) tel que:
\begin{displaymath}
a_0 = b_0 ,\ldots ,\: a_{i-1} = b_{i-1} ,\: a_i < b_i
\end{displaymath}
resp.
\begin{displaymath}
a_n = b_n ,\ldots ,\: a_{i+1} = b_{i+1} ,\: a_i > b_i .
\end{displaymath}
\end{defi}

\skippointrait
\begin{defi}[filtration lexicographique inférieure (\resp supérieure)]
À tout polynôme homogène non nul:
\[f = \sum_{a \in {{\bf N}^{n+1}}} f_a \, x^a \] est associé son
support $\{a \in {{\bf N}^{n+1}} \mid f_a \neq 0\}$ dans
${\bf N}^{n+1}$.
Le plus petit (\resp plus grand) élément du support de $f$ pour
l'ordre lexicographique inférieur (\resp supérieur) est
appelé son {\em monôme dominant} $\exp(f)$. La {\em forme
dominante} ou {\em initiale} $\In(f)$ est le terme
\begin{displaymath}
f_{\exp(f)} \, x^{\exp(f)}
\end{displaymath}
\end{defi}
Ainsi nous parlerons désormais de la filtration lexicographique
inférieure (\resp supérieure) de $R$.

\begin{defi}[parties stables]
Étant donné un idéal homogène $I$ non réduit à
$(0)$, l'ensemble $E(I)$ de tous les monômes dominants de tous ses
éléments non nuls forment une partie dite {\it stable} de
${\bf N}^{n+1}$ , c'est-à-dire:
\begin{displaymath}
a \in E(I) \implies a + {\bf N}^{n+1} \subseteq E(I)
\end{displaymath}
\end{defi}

Par convention, l'ensemble vide (\resp ${\bf N}^{n+1}$ tout entier) est
associé à l'idéal trivial $(0)$ (\resp $R$ tout entier).

\begin{lemm}[de Dickson]
Toute partie stable $E$ de ${\bf N}^{n+1}$ est finiment
engendrée, c'est-à-dire il existe une famille unique minimale
$a^{(1)},\ldots , a^{(p)}$ telle que
\begin{displaymath}
E = \bigcup_{i=1}^p (a^{(i)} + {\bf N}^{n+1})
\end{displaymath}
\end{lemm}

La démonstration de cette {\em noethérianité} de ${\bf
N}^{n+1}$ se fait par récurrence sur $n$. L'assertion est
immédiate pour $n = 0$.
Ensuite soit $\pi : {\bf N}^{n+1} \rightarrow {\bf N}^{n}$ la projection
canonique
sur ${\bf N}^{n}$ (identifié à ${\bf N}^{n} \times\nobreak \{ 0 \}$).
$\pi (E)$ est alors
une partie stable de ${\bf N}^{n}$, engendrée par hypothèse de
récurrence par une famille finie $a^{(1)},\ldots , a^{(p)}$.
Pour tout~$i$ \hbox{($1\leq i \leq p$)} il existe donc un entier $a_{n+1}^{(i)}$ tel que
$(a_1^{(i)},\ldots , a_{n}^{(i)}, a_{n+1}^{(i)})$ appartienne à~$E$.
Posons $m =\sup_{1 \leq i \leq p} (a_{n+1}^{(i)})$.
Maintenant chacune des sections~$E_j$ de $E$ par l'hyperplan de
coordonnées $x_{n+1} = j$ s'identifie par $\pi$ à une partie stable de
${\bf N}^{n}$, engendrée par une famille finie. Les $\pi (E_j)$ forment
une suite croissante de parties stables qui stationnent, égales à
$\pi (E)$, pour $j$ assez grand (en fait pour $j \geq m$). On en déduit
l'existence d'une famille finie de générateurs de $E$.

\begin{defi}[bases standard]
Soit $I$ un idéal homogène de $R$. D'après le lemme de
Dickson, $E(I)$ est minimalement engendré.
Suivant la terminologie d'Hironaka \cite{H64}, nous appelons {\em base
standard} de~$I$ une famille d'éléments de $I$ dont les
monômes dominants forment cette famille génératrice minimale.
\end{defi}

Si $E$ est une partie stable de ${\bf N}^{n+1}$, nous noterons $D(E)$ le
degré maximum des éléments engendrant minimalement $E$.

\begin{theo}[de division d'Hironaka]
Soit $I$ un polynôme homogène de $R$. Tout polynôme de
$R$ est congru module $I$ à un unique polynôme appelé reste
de la division par l'idéal, soit nul soit dont le support est
extérieur à $E(I)$.
\end{theo}

\begin{proof}
Si le polynôme dividende $f$ est nul, le
reste est nul. Sinon, il est de degré $d$ et possède un
monôme dominant. Si ce dernier appartient à $E(I)$, c'est qu'il
est divisible par le monôme dominant d'un élément de $I$,
disons $g$. Le polynôme de départ $f$ est alors congru à
$f-(\In(f)/\In(g))g$, qui est soit nul soit de monôme dominant
strictement dominé par celui de $f$. Comme il n'y a qu'un
nombre fini de monômes en degré $d$, ce processus s'arrête
sur un polynôme soit nul soit à monôme dominant
extérieur à $E(I)$; auquel cas il suffit de le priver de son
terme dominant et d'appliquer récursivement la même
procédure pour conclure.
L'unicité provient trivialement de la partition de ${\bf N}^{n+1}$
en $E(I)$ et son complémentaire.
\end{proof}

\begin{coro}[noethérianité de l'anneau des polynômes]
Toute base standard d'un idéal l'engendre.
\end{coro}

\begin{proof}
En fait, le reste de la division d'un
élément de l'idéal par une base standard
ne peut être que nul puisque sinon, son monôme dominant devrait être
à la fois à l'extérieur de $E(I)$ (par construction du
reste) et dans $E(I)$ (par définition de ce dernier).
Ce corollaire établit la noethérianité de l'anneau de
polynômes.
\end{proof}

\begin{coro}[décomposition du quotient]
\label{comp}
\mbox{ } En tant que $k$-espace vectoriel, le quotient $R/I$ est isomorphe
à la somme directe\vspace*{-3pt}\enlargethispage{\baselineskip}
\begin{displaymath}
R/I = \bigoplus_{a \not \in E(I)} kx^a.
\end{displaymath}
\end{coro}

\section{Fonction et polynôme de Hilbert}

Le {\em degré} d'un point $a = (a_0,\ldots , a_n)$ de ${\bf
N}^{n+1}$ est l'entier $| a | = a_0 + \cdots + a_n$.

\begin{defi}[fonction de Hilbert]
Soit $E$ une partie stable de ${\bf N}^{n+1}$; la fonction $HF_E$, qui
associe à tout entier $u$ le nombre de points de degré $u$
n'appartenant pas à $E$, est appelé {\em fonction de Hilbert} du
complémentaire de $E$:\vspace*{-3pt}
\begin{displaymath}
HF_{E}(u) = \# \{ a \in {\bf N}^{n+1}
\mid a \not \in E , | a | = u \}
\end{displaymath}
\end{defi}

\begin{theo}[polynôme de Hilbert]
\label{HP}
Pour $u$ assez grand, la fonction $HF_E$ est égale à un polynôme $HP_E$
(dit de Hilbert). De plus, il existe des entiers $d$ et $c_0,\ldots , c_d$
tels que:\vspace*{-3pt}
\begin{displaymath}
HP_E (u) = \sum_{i=0}^{d} c_i \binom{u}{d-i}
\end{displaymath}
où $\binom{u}{r} =
u(u-1)(\cdots)(u-r+1)/r!$ est la fonction binomiale.
\end{theo}

Par
définition, $d$ est la {\em dimension} du complémentaire de $E$,
et $c_{0}$ son {\em degré}. Finalement nous attribuerons par
convention le degré $-1$ au polynôme nul.

\begin{defi}[régularité de la fonction de Hilbert]
La {\em régularité} $H(E)$ de la fonction de Hilbert est le plus
petit entier à partir duquel la fonction de Hilbert coïncide
avec le polynôme de Hilbert.
\end{defi}

Nous noterons $D(E)$ le
degré maximum des éléments engendrant minimalement $E$.

\subsubsection*{Démonstration du théorème et d'une borne supérieure de la régularité: $H(E) \leq (n+1)(D(E)-1) + 1$}
\label{regbound}

Par récurrence sur $n$. L'assertion est
claire pour $n=0$. Puis d'après le lemme de Dickson, la section
$E_i$ de $E$ par l'hyperplan $\{ x_{n+1} = i\}$ est constant dès que
l'indice $i$ dépasse un certain entier disons $e$ et pas auparavant.
Considérons alors le développement suivant de la fonction de Hilbert:
\begin{displaymath}
HF_E (u) = \sum_{i=0}^{u} HF_{E_i} (u-i)
\end{displaymath}
qui se casse en trois morceaux dès que $u$ est assez grand:
\begin{eqnarray*}
HF_E (u) & = & \sum_{0 \leq i \leq e-1} HF_{E_i} (u-i)
+ \sum_{e \leq i \leq u-H(E_e)} HF_{E_e} (u-i)\\
&&\hphantom{\sum_{0 \leq i \leq e-1} HF_{E_i} (u-i)} + \sum_{u-H(E_e)+1 \leq i \leq u} HF_{E_e} (u-i)\\
& = & \sum_{0 \leq i\leq e-1} HF_{E_i} (u-i)
+ \sum_{H(E_e) \leq i \leq u-e} HF_{E_e} (i)\\
&&\hphantom{\sum_{0 \leq i \leq e-1} HF_{E_i} (u-i)} +
\sum_{0 \leq i \leq H(E_e)-1} HF_{E_e} (i)
\end{eqnarray*}
Pour $u$ suffisamment grand la fonction devient:
\begin{multline*}
HF_E (u) = \sum_{0 \leq i \leq e-1} HP_{E_i} (u-i)
+ \sum_{H(E_e) \leq i \leq u-e} HP_{E_e} (i)\\
+ \sum_{0 \leq i \leq H(E_e)-1} HF_{E_e} (i)
\end{multline*}
qui n'est autre que le polynôme de Hilbert $HP_E$ puisque
\[
\sum_{H(E_e) \leq i \leq u-e} HP_{E_e} (i)
\]
est effectivement un
polynôme en $u$, d'après le lemme classique:

{\it Soit $P$ un polynôme à une variable de degré $d$
à coefficients rationnels. Étant donnés deux entiers $r$ et
$s$, $\sum_{r \leq i \leq s} P(i)$ est un polynôme de
degré $d+1$, à coefficients entiers si c'était le cas pour
$P$.}

La démonstration est immédiate sur la base binomiale
$\binom{i}{d}$.
Plus précisément, cette expression est vraie dès que $u$
dépasse $$\max \{i + H(E_i) \mid 0 \leq i \leq e \},$$ ce qui est une
conséquence de l'hypothèse de récurrence dès que $u$
dépasse $$(n+1)(D(E)-1)+1.$$

\begin{exem}\label{regex}
Étant donnés $n+1$ entiers positifs $a_{0},\ldots , a_{n}$,
considérons l'idéal engendré par $x_{0}^{a_{0}},\ldots , x_{n}^{a_{n}}$,
dont ces générateurs monomiaux forment évidemment une base
standard. La partie stable associée $E$ est le complément d'un
parallélépipède dont l'élément de degré maximal
est $(a_{0}-1,\ldots , a_{n}-1)$. La régularité est donc
$1+\sum_{i=0}^{n} (a_{i}-1)$; dans le cas où tous les $a_{i}$ sont
égaux, ceci prouve que la borne ci-dessus peut être atteinte.
\end{exem}

\begin{enonce}[remark]{Remarque historique}
Si $I$ est un idéal homogène de $R$, la fonction de Hilbert de
Hilbert de $E(I)$ est indépendante de l'ordre par~\ref{comp} et on
l'appelle la fonction de Hilbert associée à
l'idéal. Hilbert avait en fait introduit historiquement
la fonction $u \mapsto \dim_{k} I\cap R_{u} $ (\og nombre de formes
homogènes de degré $u$ linéairement indépendantes \fg)
complémentaire au polynôme $\binom{u+n}{n}= \binom{u+n}{u}$ de
celle étudiée ci-dessus.
\end{enonce}

\enlargethispage{2\baselineskip}
\section{Syzygies et algorithmes de construction}

L'algèbre linéaire permet de calculer a priori la fonction de
Hilbert en étudiant l'application $k$-linéaire $R_{u-d_{1}}
\times \cdots \times R_{u-d_{s}} \to R_{u}$ induite en degrés
adéquats par $(g_1,\ldots , g_s) \to \sum_{i} g_{i} f_{i}$. Le
même algorithme de triangulation permet en grimpant de degré en
degré de construire une base standard. Le processus s'arrête par
noethérianité, mais pour transformer cette idée en
algorithme il faut assurer effectivement la terminaison par une borne
supérieure a priori du degré maximal $D(E)$ à atteindre.

Ce qui précède consiste à considérer la structure
$k$-vectorielle de~$I$. Du point de vue $R$-module, le conoyau de la
même application \hbox{$R^{s}\!\to\!R$} est $R/I$ et son noyau est par
définition le {\it module des relations} entre $f_1,\ldots , f_s$,
ou premier {\it module de syzygie}, qu'on peut par le même
algorithme de triangulation construire en degré donné.

Il se trouve que le module des relations entre les éléments
d'une base standard se construit facilement; en retour ceci nous
conduira à un algorithme de construction d'une base standard à
partir d'un système donné de générateurs.

\begin{defi}[polynôme de syzygie]
Soit $(f_1,\ldots , f_s)$
une base standard de $I$. Pour $i$ différent de $j$, formons le polynôme
(dit de {\it syzygie}):
\begin{eqnarray*}
S(f_i, f_j) = (\In(f_j) f_i - \In(f_i) f_j)/m_{ij}
\end{eqnarray*}
où $m_{ij}$ est le monôme plus grand commun diviseur des monômes
dominants de $f_i$ et $f_j$. Divisant $S(f_i, f_j)$ par $(f_1,\ldots ,
f_s)$, on obtient un reste nul et donc une relation entre les
polynômes de la base standard; ce que nous conviendrons d'appeler
{\it relation bilatérale évidente}.
\end{defi}

L'ensemble de celles-ci n'est pas aussi particulier qu'on pourrait le
penser, à cause du théorème suivant:

\begin{theo}[de Spears-Schreyer]
Les relations bilatérales évidentes en\-gen\-drent le module des
relations entre les éléments d'une base standard.
\end{theo}

\begin{proof}
Donnons-nous une relation entre les générateurs:
$\sum _{i=1}^p g_i f_i = 0$. Posons $a_{i}=exp(g_i f_i)$, $a$ le
dominant des $\{a_{i}\}$, la tête $T$ comme l'ensemble des indices
$i$ tels que $a_i$ soit
égal à $a$, et $t = \sup(T)$. Remarquons que la tête ne peut
pas être réduite au seul élément $t$.
Soit donc $s$ un autre élément de $T$ différent de $t$; $x^a$ est un
multiple commun de $\exp (f_{s})$ et $\exp (f_{t})$, donc à l'aide de la relation bilatérale évidente entre $f_{s}$ et $f_{t}$ on peut
réécrire la relation initiale en une nouvelle où soit $t$
n'intervient plus dans plus dans la tête soit celle-ci est nouvelle,
et on conclut.
\end{proof}

\subsection{L'algorithme de construction de Buchberger}

Inspiré par ce qui précède, on peut imaginer un algorithme de
construction d'une base standard de $I$, à partir
d'un système donné $F$ de générateurs, basé par adjonctions
successives de restes de divisions non nulles de polynômes de
syzygie. Mais cet idée revient historiquement à \cite{B65} qui
l'a introduite pour d'autres raisons et exprimé dans
le cas affine, en appelant le résultat {\em base de Gr{\"o}bner}:

{\bf Algorithme de Buchberger}:

Entrée: un système de générateurs $F$.

Sortie: une base de Gr{\"o}bner $G$.

$G \gets F$

RÉPÉTER

\quad $G' \gets G$

\quad POUR toute paire $p,q$ ($p \not = q$) de $G'$ FAIRE

\quad\quad Diviser $S(p,q)$ par $G'$

\quad\quad SI le reste $r$ est non nul ALORS $G \gets G\cup \{ r\}$

JUSQU'À $G = G'$.

\begin{proof}[Formulation et preuve]
Voir \cite[p.\,59]{CLO92}; mais c'est essentiellement la même que ci-dessus.
\end{proof}

\section{Théorie de la dimension}

Examinons d'abord les interprétations géométriques des
filtrations introduites ci-dessus.

\begin{prop}[section par une sous-variété linéaire]\label{secthyper}
Soit $p$ un indice entre $0$ et $n-1$. Soit $f_1,\ldots , f_s$ une
base standard de $I$ pour la filtration lexicographique
inférieure. Alors les $f_i$ dont les monômes dominants ne
dépendent pas de $x_0,\ldots , x_{p}$, auxquels on ajoute $x_0,
\ldots , x_{p}$, forment une base standard de $I+(x_0,\ldots , x_p)$
pour la même filtration. Ceci correspond à couper $Z(I)$ par la
sous-variété $x_0 = \cdots = x_{p} = 0$.
\end{prop}

\begin{proof}
Elle découle de la remarque que si $x_0$
divise le monôme dominant d'un polynôme, il divise ce dernier;
et d'une récurrence triviale.
\end{proof}

\begin{prop}[projection sur une sous-variété linéaire] \label{projhyper}
Soit $p$ un indice entre $0$ et $n-1$. Soit $f_1,\ldots , f_s$ une
base standard de $I$ pour la filtration lexicographique
supérieure. Alors les $f_i$ dont le monôme dominant dépend
uniquement des variables $x_0,\ldots , x_{p}$ forment une base standard
de $I \cap k[x_0,\ldots , x_{p}]$ relativement à la même
filtration.

Si la variété linéaire définie par $x_0,\ldots , x_{p}$
ne coupe pas $Z(I)$, ces polynômes définissent la projection de
$Z(I)$ sur la sous-variété $x_{p+1} = \cdots = x_{{n}} = 0$.
\end{prop}

\begin{proof}[Esquisse de preuve]
Pour $p=n-1$, observons que si un polynôme
possède un monôme dominant qui ne dépend pas de $x_{n}$, lui
non plus. Maintenant soit $\pi$ la restriction à $Z(I)$ de la
projection de centre le point $(0,\ldots ,0,1)$ sur l'hyperplan $x_n =
0$. Le Nullstellensatz permet de d'affirmer que l'adhérence de
Zariski de $\pi(Z(I))$ est défini par l'idéal $I \cap
k[x_0,\ldots , x_{n-1}]$ et en situation projective un argument de
propreté permet de conclure (voir \cite[I.2 et 4.9]{H77}). Le cas
général suit par récurrence.
\end{proof}

\subsection{Différentes notions de dimension}
D'abord une définition {\it algébrique}: la {\em dimension de
Hilbert} $\delta$ est le degré du polynôme de Hilbert
associé à $R/I$.\enlargethispage{\baselineskip}

Puis deux définitions {\em géométriques}: la {\em dimension
de section} est le plus petit entier $\sigma$ tel qu'il existe une
sous-variété linéaire de codimension $\sigma +1$ évitant
$Z(I)$; la {\em dimension de projection} est le plus grand entier $\pi$
tel qu'il existe une projection envoyant surjectivement $Z(I)$ sur une
base de dimension $\pi$.

Ces trois notions coïncident classiquement, ce que nous allons
prouver via leur égalité avec deux autres notions qui se lisent
sur les bases standard.

\skippointrait
\begin{defi}[dimension lexicographique inférieure (\resp supérieure)]
\mbox{}\label{lexdim}
Soit $x$ un système de coordonnées de ${\bf P}^n$. Nous
appellerons $\linf_x$ (\resp $\lsup_x$) le plus petit (\resp le plus
grand) entier $e$ tel que $E_x (I)$ relativement à la filtration
lexicographique inférieure (\resp supérieure) rencontre les
derniers $n-e$ axes de coordonnées de ${\bf N}^{n+1}$ (\resp ne
rencontre pas le plan des $e+1$ premières coordonnées).

Le minimum $\linf$ des $\linf_x$ (\resp le maximum $\lsup$ des $\lsup_x$)
pris sur tous les systèmes de coordonnées est appelé la
dimension lexicographique inférieure (\resp supérieure).
\end{defi}

\begin{thdim}
Les cinq notions ci- dessus coïncident.
\end{thdim}

Ceci établit la
version géométrique du lemme de normalisation de Noether.

\begin{proof}
Par cinq inégalités successives.

\subsubsection{$\delta \geq\lsup$}
\label{d2lsup}

Supposons qu'il existe des coordonnées de ${\bf P}^n$ pour
lesquelles, relativement à un ordre compatible, par exemple le
lexicograhique supérieur, $E(I)$ ne rencontre pas le plan des
$e+1$ premières coordonnées. Ainsi la fonction de Hilbert $HF(u)$ est
minorée par le nombre de monômes de degré $u$ sur $e+1$
lettres, qui est un $O(u^e)$ quand $u$ tend vers l'infini. Donc $\delta$
est minoré par $\lsup$.

\subsubsection{$\lsup \geq \pi$}

\label{lsupp}

Supposons que $Z(I)$ puisse être projeté surjectivement sur un
plan $P$ de dimension $p$. Nous pouvons choisir des coordonnées
telles que ce plan soit défini par les équations $x_{p+1} =
\cdots = x_n = 0$. Ainsi l'idéal $I \cap k[x_0,\ldots , x_p]$ se
réduit à $0$; sinon il existerait un polynôme non nul
$f(x_0,\ldots , x_p)$ dans $I$ qui ne peut s'annuler sur tout le plan,
et l'ensemble algébrique $Z(I)$ ne peut se projeter
surjectivement. Considérons par rapport à de telles
coordonnées la partie stable $E(I)$ relativement à la filtration
lexicographique supérieure: elle ne peut rencontrer le plan des
$p+1$ premières variables d'après~\ref{projhyper}.\enlargethispage{\baselineskip}

\subsubsection{$\pi \geq \sigma$}

\label{ps}

Par définition de $\sigma$, il existe une sous-variété
linéaire $L$ de codimension $\sigma +1$ évitant $Z(I)$. Par ailleurs
nous pouvons choisir une sous-variété linéaire $B$ de
dimension $\sigma$ évitant $L$. La projection de centre $L$ envoie
surjectivement $Z(I)$ sur $B$, puisque $\sigma$ est minimal; car si $b$
est un point de $B$, la sous-variété linéaire qu'il engendre
avec~$L$ est de codimension $\sigma$, donc coupe $Z(I)$ en au moins un
point qui se projette sur $b$.

\subsubsection{$\sigma \geq \linf$}

\label{slinf}

Par définition de $\sigma$, il existe une sous-variété
linéaire $L$ de codimension $\sigma +1$ évitant $Z(I)$. Nous
pouvons choisir des coordonnées telles que $L$ soit définie par
les équations \hbox{$x_0 = \cdots = x_{\sigma} = 0$}. L'idéal $J = I
+ (x_0,\ldots , x_{\sigma})$ définit la variété vide, donc
d'après le Nullstellensatz contient une puissance de l'idéal
maximal $(x_0,\ldots , x_n)$ (\cite[Ex. 2.1]{H77}). Quelque soit
l'ordre, en particulier l'ordre lexicographique inférieur, $E(J)$
coupe tous les axes de coordonnées. Considérons un polynôme
dont le monôme dominant est sur un des axes $x_{\sigma +1},\ldots ,
x_n$; il est congru modulo $(x_0,\ldots , x_{\sigma})$ à un
polynôme de $I$, non nul et de même monôme dominant. C'est
donc que la section de $E(I)$ par le plan des $n-\sigma$ dernières
coordonnées recoupe tous les axes.

\subsubsection{$\linf \geq \delta$}

Supposons qu'il y ait des coordonnées de ${\bf P}^n$ telles que,
relativement à l'ordre lexicographique inférieur, $E(I)$ coupe
les derniers $n-\linf$ axes. En degré $u$ suffisamment grand, le
complémentaire de $E(I)$ ne contient que des monômes dont les
$n-\linf$ derniers exposants sont majorés par un un entier fixé;
à une constante multiplicative près, la fonction de Hilbert
$HF(u)$ est donc majorée par le nombre de monômes sur $\linf+1$
lettres, soit un $O(u^{\linf})$ quand $u$ tend vers l'infini.
\end{proof}

\subsection{Remarque sur la calculabilité de la dimension}

Soit $I$ un idéal engendré par des polynômes
de degré inférieur à $d$. Une fois construite une base standard,
on peut calculer la dimension de Hilbert. Mais il existe une famille
d'idéaux, donnés par des générateurs de
degré au plus $d$, dont le degré des éléments d'une base
standard est minoré par $C d^{a^n}$, $C\!>\!0$, $a\!>\!1$ (exemple
de \cite{MM82}, voir aussi~\cite{D87}).

Il est proposé dans \cite{G88} un algorithme de mise en position
de Noether géométrique, avec un nombre d'opérations
arithmétiques polynomial en $d^{n^{2}}$, toujours basé sur des
constructions de bases standard mais tronqués en degré. Pour
faire mieux il faut s'y prendre autrement\ldots


\part{Du côté de l'évaluation}
Soient $f_{1},\ldots , f_{s}$ une famille de polynômes homogènes de l'anneau
$k[x_{0}, x_{1},\ldots , x_{n}]$, de degré $d$ au
moins égal à $n$.
Ecrits dans la représentation dense, ils peuvent
donc être décrits par un vecteur dont les coordonnées sont
dans l'anneau de base $k$. La taille de cette entrée est la place
mémoire nécessaire pour les stocker, que nous pouvons estimer.
En effet le nombre de monômes sur
$n+1$ lettres de degré $d$
est le coefficient binomial $(d+n)!/d!\, n!$
quantité majorée par $ed^{n}$, qui est donc un $O(d^{n})$ ($n$
fixé, $d$ tendant vers l'infini). Comme nous convenons de coder les
polynômes d'entrée par leurs coefficients dans la représentation dense,
il faut stocker $O(sd^{n})$ coefficients.

\section{Description des modèles d'algorithmes et de complexité}

\label{modeles}

\subsection{Modèles d'algorithmes}

Les algorithmes que nous allons utiliser ou introduire seront
décrits par un {\it réseau arithmétique} à entrées dans $k$,
représenté par un graphe orienté acyclique \cite{G86}.
A chaque sommet interne correspond un processeur qui effectue
une opération élémentaire de l'anneau
de base $k$, et chaque arête indique l'envoi d'une sortie d'un processeur
comme entrée du second.

Un algorithme admet un déroulement séquentiel ou parallèle. La~{\it complexité séquentielle} (ou temps séquentiel) est la
taille du réseau, c'est-à-dire le nombre de processeurs ou sommets
du graphe. La {\it complexité parallèle} (ou temps parallèle)
est la profondeur du réseau, c'est-à-dire la longueur du plus long
chemin dans le graphe orienté. Pour une discussion plus approndie de
ce modèle de complexité, nous renvoyons à \cite{G86}
et \cite{FGM90}.

Il existe des réseaux arithmétiques particuliers
spécialement intéressants: ce sont ceux qui ne font
intervenir ni tests d'égalité ni branchements. Nous les
appellerons {\em calculs
d'évaluation} (généralement sans divisions) ou {\em
circuits arithmétiques}
({\em straight line programs} en basic english). Nous
renvoyons à \cite{S72}, \cite{G86}, \cite{S89} ou \cite{H89} pour plus de précisions sur ces
réseaux particuliers. La {\em complexité séquentielle} ou
{\em longueur} d'un
tel calcul d'évaluation sera le nombre d'opérations arithmétiques
qu'il contient. Ils peuvent servir à coder des polynômes
à plusieurs variables, calculant leur valeur en un point.

\subsection{Définition de bonnes classes de complexité}

\label{complexpol}

Dans le cadre défini ci-dessus, nous dirons qu'un algorithme est
de complexité
séquentielle {\em polynomiale en la taille de l'entrée} si le
réseau correspondant de paramètres $(d,n,s)$ admet une
complexité séquentielle
$s^{O(1)} d^{O(n)}$.\enlargethispage{\baselineskip}


Cette terminologie est justifiée quand on considère
la taille $O(sd^{n})$ de notre entrée $f_{1}
,\ldots ,f_{s}$
pour la structure de données choisie (la représentation dense
des polynômes), puisqu'un polynôme en $O(sd^{n})$
est bien un $s^{O(1)}\, d^{O(n)}$.

Nous dirons que l'algorithme est {\em bien parallélisable} si la
profondeur du réseau est en $O(n^{2} \log ^{2}(sd))$. Ceci signifie
bien, conformément au sens général, que la complexité
parallèle est d'ordre le carré du logarithme de la
complexité séquentielle.

La complexité d'un algorithme peut aussi être mesurée
{\em par rapport à la taille de la sortie}. Si celle-ci
consiste par exemple en $s$ polynômes en $n$ variables de
degré $d^{n}$ (comme c'est souvent le cas), donnés par leur
écriture dans une représentation dense, la taille de la sortie pour
la représentation choisie est un $O(sd^{n^{2}})$. Un algorithme de
complexité séquentielle $s^{O(1)} d^{O(n^{2})}$ et
parallèle $O(n^{4} \log ^{2} sd)$ est alors à juste titre
polynomial en la taille de la sortie et bien parallélisable.

\section{Des outils plus sophistiqués}

Dans l'étude algorithmique des sous-variétés algébriques
apparaissent systématiquement des polynômes intermédiaires
ou des sorties dont le meilleur majorant de leur degré qu'on puisse
avoir est un $d^{O(n)}$ ou $sd^{O(n)}$. Nos algorithmes ne font pas
exception, et c'est sans doute de toute fa{\c c}on inévitable, par
exemple, dès lors qu'un dévissage par projection est
utilisé.

L'usage de la représentation dense ne peut alors que conduire
à des complexités polynomiales en la taille de la sortie. Mais
il serait évidemment si agréable de rester dans la meilleure des
bonnes classes de complexités, à savoir polynomiales par
rapport à la taille de l'entrée~! La solution ne peut alors
que passer par un changement de la structure
de données choisie pour représenter polynômes
intermédiaires et sorties.\enlargethispage{2.5\baselineskip}

\subsection{Extensions de l'anneau de base}

\label{extension}

L'idée principale consiste à introduire des
paramètres auxiliaires sous
forme de nouvelles indétermi\-nées, par exemple $T_{1},\ldots
,T_{n}$. Nous remplacerons alors provisoirement
l'anneau de base $k$ par $k[T_{1},\ldots ,T_{n}]$. Les résultats
intermédiaires représentent des polynômes considérés
comme dépendant de variables principales à coefficients
eux-mêmes des polynômes en les paramètres $T_{1},\ldots ,T_{n}$.
Par rapport aux variables principales les polynômes sont
codés par leur écriture dans la représentation dense, mais les
polynômes coefficients sont eux-mêmes représentés par des
calculs d'évaluation dans $k[T_{1},\ldots ,T_{n}]$.

Nos algorithmes exécutent alors des opérations
arithmétiques (en général sans divisions) et des
comparaisons dans $k[T_{1},\ldots ,T_{n}]$. Le point essentiel pour la
complexité de cette nouvelle arithmétique va résider dans
ces comparaisons, et plus exactement les tests de non-nullité. Par
exemple, si des paramètres auxiliaires
différents des variables d'origine
$x_{0}, x_{1},\ldots , x_{n}$
apparaissent encore dans les polynômes finaux, ils devront être
éliminés par spécialisation en des valeurs appropriées
de $k$, mais bien sûr sans donner lieu à des annulations.
Ainsi, tous les algorithmes pourront être réalisés par des
réseaux sur l'anneau $k$ (voir aussi \cite{HS81} et
\cite{K88} pour l'utilisation de cette représentation des
polynômes en calcul formel).

Voyons maintenant comment traiter la question cruciale des comparaisons.

\subsection{Un test de nullité et ses conséquences pour la complexité}

Nous utiliserons de manière essentielle un théorème de
\cite[Th.\,4.4]{HS82}), dont nous rappelons
l'énoncé par commodité pour le lecteur:

\begin{theorem*}
Considérons l'ensemble $W(D,n,v)$ des
polynômes de l'anneau $k[T_{1},\ldots ,T_{n}]$, de degré au plus $D$ et
qui peuvent être évalués par un calcul de longueur au plus
$v$. Soit $\Gamma$ un sous-ensemble de $k$ de cardinal $2v(1+D)^{2}$.

Alors il existe un sous-ensemble $Q(D,n,v,\Gamma) = \{ \gamma_{1},\ldots ,
\gamma_{m} \}$ de~$\Gamma^{n}$ (où $m = 6(v+n)(v+n+1)$), vérifiant la
propriété suivante: tout polynôme de $W(D,n,v)$ s'y
s'annulant est identiquement nul.
\end{theorem*}

Suivant une jolie terminologie introduite par \cite[7.2]{HM87} dans une situation du même type, nous appellerons {\em
questeur} un tel ensemble, terme qui traduit avantageusement ``correct
test sequence''.

Appliqué au cadre du paragraphe précédent où $D$ sera
toujours en $sd^{O(n)}$ ou $d^{O(n)}$, et $v$ en $s^{O(1)}\,
d^{O(n)}$ (sans divisions), ceci nous permettra
d'exécuter les comparaisons nécessaires d'éléments de
$k[T_{1},\ldots ,T_{n}]$ en effectuant seulement $s^{O(1)}\, d^{O(n)}$
opérations arithmétiques dans $k$, puisque le cardinal de
$\Gamma$ et de l'ensemble questeur sont en $s^{O(1)}\, d^{O(n)}$.\enlargethispage{2\baselineskip}

La question du choix de l'ensemble questeur dans $\Gamma^{n}$ est
essentielle pour l'évaluation de complexité.
Bien sûr, il peut se faire au coup par coup algorithmiquement,
mais à un coût élevé qui dépend surtout du
paramètre $n$. Il serait dommage de ne pas
tirer parti du fait qu'il ne dépend que des paramètres $d$,
$s$ et $n$ mais ni de $t$ ni des coefficients d'une entrée particulière
$f_{1},\ldots , f_{s}$. Pourquoi ne pas décider de rejeter ce
coût dans les ténèbres extérieures, là où il y a des
pleurs et des grincements de dents~? Pour $d$, $n$ et $s$ fixés,
nous penserons donc que nous l'avons déterminé une fois pour
toute par une préparation préalable ({\em preprocessing}),
dont le coût n'a pas à intervenir dans un calcul particulier.
En quelque sorte, nous considérons qu'il est réparti sur
toutes les entrées possibles. Autrement dit, pour chaque triplet
$d$, $s$, $n$, nous construisons un réseau arithmétique qui
résout une certaine tâche en temps séquentiel $s^{O(1)}\,
d^{O(n)}$ et en temps parallèle $O(n^{2} \log ^{2} sd)$, mais le
coût lui-même de cette construction n'est pas compté. En ce
sens, nous dirons que nos algorithmes ne sont pas {\em uniformes}.\enlargethispage{\baselineskip}%

Pour être exhaustif, revenons au traitement algorithmique complet.
Le choix des ensembles questeurs peut se faire de manière
aléatoire, selon
\cite[Th.\,4.4]{HS82}. Le temps séquentiel de
déroulement de nos algorithmes est alors une variable
aléatoire dont l'espérance est en $s^{O(1)}\, d^{O(n)}$. Enfin la borne
supérieure de complexité, celle obtenue dans le pire des cas
({\em worst case complexity}) atteint $s^{O(1)}\, d^{O(n^{2})}$.\enlargethispage{\baselineskip}

\Subsection{Algèbre linéaire effective à la Berkowitz-Mul\-muley}
\label{berkomulmul}

Les questions d'a\-ri\-thmétique étant réglées, nos
résultats sont basés sur des techniques d'algèbre
linéaire effective qui utilisent des algorithmes bien parallélisables
et sans divisions. L'ingrédient fondamental est l'algorithme de
\cite{B84} qui calcule en temps polynomial tous les
coefficients du polynôme caractéristique d'une matrice
carrée à
coefficients dans un anneau intègre. Ces coefficients sont
représentés par un calcul d'évaluation {\em sans
divisions}.

Pour calculer le rang d'une matrice quelconque nous combinons
l'algorithme de Berkowitz avec un résultat de \cite{M86} qui
exprime ce rang comme valuation du polynôme caractéristique
d'une matrice carrée auxiliaire. Ainsi, nous pouvons décider
en temps polynomial par un algorithme bien parallélisable
et sans effectuer de divisions si un système d'équations
linéaires admet des solutions et, en cas de réponse positive,
les calculer en ne faisant appel qu'à une seule division par un
élément précalculé.

\section{Calcul de la dimension et mise en position de Noether}

Le but de cette partie est de conforter les conjectures suivant
lesquelles, une variété algébrique étant donnée par
équations, le calcul d'une mise en position de Noether et donc le
calcul de sa dimension peuvent se faire en temps polynomial par rapport
à l'entrée, et ce de manière uniforme.\enlargethispage{\baselineskip}%

Nous résolvons ici ces questions par des
algorithmes bien parallélisables de complexité
séquentielle en $s^{O(1)}\, d^{O(n)}$, à condition que le degré
maximum des équations ne soit pas trop bas ($d \geq n$ et que ces
équations soient données par une écriture dans la
représentation dense. Le
point est que nos algorithmes
{\em ne sont pas uniformes par rapport à $n$}, puisqu'ils
dépendent du choix d'un ensemble questeur, ce qui aboutit à un
coût élevé par rapport à la classe de complexité
$s^{O(1)}\, d^{O(n)}$.

Néanmoins, tous nos algorithmes possèdent une version uniforme
et bien parallélisable
dont la complexité séquentielle est $s^{O(1)}\, d^{O(n^{2})}$.
Cette borne de complexité uniforme est déjà
connue pour les problèmes considérés ici (voir
\cite{DFGS91}, où cette borne a
été obtenue directement).

Enfin, un choix aléatoire des ensembles questeurs ne change pas le
caractère déterministe de nos algorithmes et
les rend uniformes. Comme nous l'avons déjà dit, la
complexité séquentielle devient une variable aléatoire
d'espérance un $s^{O(1)}\, d^{O(n)}$,
alors que la complexité dans le pire des cas est un $s^{O(1)}\,
d^{O(n^{2})}$, ce qui correspond à la complexité uniforme.

Du point de vue pratique, notre méthode nous semble prometteuse.
La version probabiliste et uniforme de notre algorithme calculant la
dimension est de type aléatoire ({\em randomized}). C'est surtout
la complexi\-té qui devient aléatoire, avec une espérance en
$s^{O(1)}\, d^{O(n)}$
polynomiale en la taille de l'entrée. Un premier résultat dans
cet esprit est contenu dans \cite{LL91}.

Cependant, nos algorithmes souffrent encore d'un
inconvénient pratique et théorique: ils reposent sur le codage
des polynômes d'entrée par leur écriture en
principe dans la représentation dense. C'est d'ailleurs le plus
grave des défauts présentés par la plupart des algorithmes
actuels implantés en calcul formel.

Nous noterons $V$ l'ensemble algébrique défini par $f_{1},
\ldots , f_{s}$.
Dans toute la suite, $z$ sera une nouvelle indéterminée qui nous
servira de variable d'ho\-mo\-gé\-néi\-sa\-tion. Du point de vue
géométrique, nous l'utiliserons pour effectuer des
éclatements.

Soient $\lambda = (\lambda_{0},\ldots , \lambda_{m})$, $\lambda_{0}
\leq\cdots \leq \lambda_{m}$ et $\overline{\lambda} = (\lambda_{m+1},
\ldots , \lambda_{n})$, $\lambda_{m+1} \leq\cdots \leq \lambda_{n}$
deux familles complémentaires d'indices entre~$0$ et~$n$
(c'est-à-dire $\{ \lambda_{0},\ldots , \lambda_{m} \} \cup \{
\lambda_{m+1},\ldots , \lambda_{n} \} = \{ 0,\ldots , n \}$ et $\{
\lambda_{0},\ldots , \lambda_{m} \} \cap \{ \lambda_{m+1},\ldots ,
\lambda_{n} \} = \emptyset $).
Nous utilisons les notations suivantes, à comparer avec
\cite[3.2]{GH91}:\vspace*{-5pt}
\begin{gather*}
x^{\lambda} := (x_{\lambda_{0}},\ldots , x_{\lambda_{m}}), \quad
x^{\overline{\lambda}} := (x_{\lambda_{m+1}},\ldots,x_{\lambda_{n}}), \\ R^{(\lambda)} := k[x^{\lambda}]\quad \mbox{et}\quad K^{(\lambda)}
:= k'(x^{\lambda}).
\end{gather*}
Fixons aussi une clôture algébrique $\overline{K^{(\lambda
)}}$ de $K^{(\lambda)}$. Notons que $R^{(\lambda)}$ est un anneau
de polynômes
à coefficients dans $k$ et que $K^{(\lambda)}$ est son corps de
fractions.
Les anneaux
$R^{(\lambda)} [z, x^{\overline{\lambda}}] \!=\!
k[z,x_{0},\ldots , x_{n}]$ et \hbox{$K^{(\lambda)}
[z,x^{\overline{\lambda}}] \!=\! k'(x^{\lambda})[z,x^{\overline{\lambda}}]$}
sont des anneaux (gradués) de polynômes en les variables $z,
x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}$ et à coefficients
dans $R^{(\lambda)}$ et $K^{(\lambda)}$. Les variables
$x_{\lambda_{0}},\ldots , x_{\lambda_{m}}$ seront considérées
comme des paramètres.

Soit $f$ un polynôme homogène de $k[x_{0},\ldots , x_{n}]$.
Nous notons $f^{(\lambda)}$ le polynôme de $R^{(\lambda)} [z,
x^{\overline{\lambda}}]$ que nous obtenons en substituant dans~$f$ les
variables $x_{\lambda_{0}},\ldots , x_{\lambda_{m}}$ respectivement par
$zx_{\lambda_{0}},\ldots , zx_{\lambda_{m}}$, ou autrement dit
$$f^{(\lambda)} := f(zx_{\lambda_{0}},\ldots , zx_{\lambda_{m}},
x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}).$$
Observons que
$f^{(\lambda)}$ est homogène de degré $\deg f$ en les
variables $z, x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}$. Par rapport
à ces variables, nous représentons $f^{(\lambda)}$ par son
écriture dense, comme vecteur de ses coefficients qui sont des
éléments de $R^{(\lambda)}$. Nous représentons ceux-ci,
qui sont des polynômes de $k[x^{\lambda}]$, par un calcul
d'évaluation bien parallélisable (et sans divisions) dans
$k[x^{\lambda}]$. Observons aussi que $f$ est le
déshomogénéisé de~$f^{(\lambda)}$ par rapport à
la variable $z$.

Appelons respectivement $I$ et $J$ les idéaux engendrés par
$f_{1},\ldots , f_{s}$ dans les anneaux $k[x_{0},\ldots , x_{n}]$ et
$k'[x_{0},\ldots , x_{n}]$, tandis que
$I^{(\lambda)}$ et $J^{(\lambda)}$ sont ceux engendrés par
$f^{(\lambda)}_{1},\ldots , f^{(\lambda)}_{s}$ dans $R^{(\lambda
)}[z,x^{\overline{\lambda}}]$ et $K^{(\lambda
)}[z,x^{\overline{\lambda}}]$. Nous dirons que $x_{\lambda}$ (ou le
système des variables $x_{\lambda_{0}},\ldots , x_{\lambda_{m}}$)
est {\em dépendant} par rapport à $V$, s'il existe un
polynôme homogène non constant $g$ de $k[x^{\lambda}]$ qui
s'annule sur $V$ (ce qui revient à dire que l'intersection
$k[x^{\lambda}] \cap I$ ne se réduit pas à $(0)$). Si
$x^{\lambda}$ n'est pas dépendant par rapport à $V$, nous
l'appellerons {\em indépendant}.

Enfin, nous dirons que la variable $y := x_{\lambda_{i}}$ ($m < i
\leq n$) est en position de Noether par rapport à $x^{\lambda}$ et
$V$ s'il existe un polynôme homogène de $k[x^{\lambda}, y]$
qui soit unitaire en $y$ et qui s'annule sur $V$. Ceci équivaut
à dire que l'intersection $k[x^{\lambda}, y] \cap I$ contient un
polynôme unitaire en $y$. Si $x^{\lambda}$ est un système
maximal indépendant et si toutes les variables $x_{\lambda_{i}}$
($m < i \leq n$) sont en position de Noether par rapport à $V$,
nous dirons que le système de variables $x_{0},\ldots , x_{n}$
est lui-même en position de Noether par rapport à $V$.

Notre algorithme de mise en position de Noether pour les
variétés projectives est basé sur le critère
géométrique suivant (comparer à \cite{G88} et
\cite{GH91}).

\subsection{Le critère du centre de projection}

\label{centreproj}

Soit $W$ la sous-variété projective de l'espace projectif ${\bf
P}^{n-m}(\overline{K^{(\lambda)}})$ définie par les
polynômes $f_{1}^{(\lambda)},\ldots ,f_{s}^{(\lambda)}$.
Supposons que les variables $x_{\lambda_{m+1}},\ldots ,
x_{\lambda_{n}}$ soient en position de Noether par rapport à
$x^{\lambda}$ et $V$. Alors nous avons le critère suivant:

\noindent{\em Le système des variables $x^{\lambda}$ est dépendant par
rapport à $V$ si et seulement si la sous-variété $W$ est
vide.}

Avant de commencer la démonstration du critère, explicitons-en la
signification géométrique. A la famille $x^{\lambda} =
(x_{\lambda_{0}},\ldots , x_{\lambda_{m}}$) correspond une
application rationnelle $\pi : {\bf P}^{n} \longrightarrow {\bf
P}^{m}$ qu'on appelle {\em projection} de ${\bf P}^{n}$ sur ${\bf
P}^{m}$ de centre $\{ x_{\lambda_{0}} = \cdots = x_{\lambda_{m}} = 0 \}$.
Elle induit une application rationnelle $\phi : V \longrightarrow {\bf
P}^{m}$. Le fait que les variables $x_{\lambda_{m+1}},\ldots ,
x_{\lambda_{n}}$ soient en position de Noether par rapport à
$x^{\lambda}$ et $V$ garantit que les
équations $f_{1}^{(\lambda)},\ldots ,f_{s}^{(\lambda)}$
décrivent la fibre générique de $\phi$, d'où le
critère (comparer à \cite{GH91}).

\begin{proof}
Supposons que la famille $x^{\lambda}$ soit
dépendante par rapport à $V$. Il existe alors un polynôme
non constant $g$ de $k[x^{\lambda}]$ et des polynômes $p_{1},
\ldots , p_{s}$ de $k[x_{0},\ldots , x_{n}]$ tels que l'équation
$$
g = \sum_{1 \leq i \leq s} p_{i} f_{i}
$$
soit satisfaite. Nous en déduisons immédiatement une
deuxième équation
$$
g^{(\lambda)} = \sum_{1 \leq i \leq s}
p^{(\lambda)}_{i} f^{(\lambda)}_{i} \leqno{(*)}
$$
dans l'anneau $R^{(\lambda)} [z,x^{\overline{\lambda}}]$. Observons
que $g^{(\lambda)}$ est égal à $z^{\deg g} g$ et que~$g$ est
un élément non nul et de degré strictement positif de
$R^{(\lambda)}$.

L'identité $(*)$ implique que $W$ est inclus dans l'hyperplan $\{ z
= 0 \}$ de ${\bf P}^{n-m}(\overline{K^{(\lambda)}})$. Soit $m < i
\leq n$ et $y := x_{\lambda_{i}}$. Comme $y$ est
en position de Noether par rapport à $x^{\lambda}$ et $V$, il
existe un polynôme homogène $q$ de $k[x^{\lambda},y] \cap I$
qui soit unitaire en $y$. Comme précédemment, nous obtenons
que $q^{(\lambda)}$ appartient à $I^{(\lambda)}$, donc s'annule
sur $W^{(\lambda)}$. Ce polynôme de $R^{(\lambda)}[z,y]$ est
unitaire en $y$. Comme $W$ est contenu dans l'hyperplan à
l'infini, nous en concluons qu'il est aussi dans l'hyperplan $\{ y = 0
\}$ de ${\bf P}^{n-m}(\overline{K^{(\lambda)}})$. De cette manière,
nous en déduisons que
$W$ est dans l'intersection de tous les hyperplans $\{ z = 0 \}$, $\{
x_{\lambda_{m+1}} = 0 \},\ldots ,\{ x_{\lambda_{n}} = 0 \}$, qui
est vide.

Réciproquement, supposons maintenant que $W$ soit vide. Ceci veut
dire que les éléments $z, x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}$ appartiennent
au radical de l'idéal $J^{(\lambda)}$ engendré par $f_1^{(\lambda)},
\ldots , f_s^{(\lambda)}$ dans $K^{(\lambda)}[z,x^{\overline{\lambda}}]$.
Il existe donc un élément non nul $g$ de $R^{(\lambda)} =
k[x^{\lambda}]$, un entier $N \geq 1$ et des polynômes $p'_1,\ldots ,
p'_s$ de $R^{(\lambda)}[z, x^{\lambda}]$ tels que l'équation
$$
gz^N = \sum_{1 \leq i \leq s} p'_i f_i^{(\lambda)} \leqno{(**)}
$$
soit satisfaite.

En déshomogénéisant $(**)$ par la substitution de $1$ à $z$,
les poly\-nô\-mes $p'_i$ ($1 \leq i \leq s$) se spécialisent en des
polynômes $p_i$ de $k[x_0,\ldots , x_n]$ et les $f_i^{(\lambda)}$ en
$f_i$. Le polynôme $g$ ne change pas et nous pouvons le supposer constant
et homogène. Quant à l'équation $(**)$, elle se transforme en
$$
g = \sum_{1 \leq i \leq s} p_i f_i
$$
Comme $g$ appartient à $k[x_{\lambda}]$, ceci implique que
$k[x^{\lambda}] \cap I \not = 0$. Le système de variables $x^{\lambda}$
est donc dépendant par rapport à $V$.
\end{proof}

Nous allons maintenant transformer notre critère géométrique en
algorithme.

\subsection{Une bonne équation satisfaite par la projection}\label{subsec:9.2}

Conservons l'hypothèse que
les variables $x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}$ sont en position
de Noether par rapport à $x^{\lambda}$ et à $V$.

\begin{lemme*}
Au prix d'une préparation préalable, nous pouvons décider
en temps $s^{O(1)}\, d^{O(n)}$ par un algorithme bien parallélisable et
sans divisions si les variables $x_{\lambda_{0}},\ldots , x_{\lambda_{m}}$
sont dépendantes par rapport à~$V$. Si c'est le cas, l'algorithme
calcule un polynôme homogène non constant $g$ de $k[x^{\lambda}]$ qui
s'annule sur la variété $V$. Son degré est un~$d^{O(n)}$. Le
poly\-nôme $g$ est représenté par un calcul d'évaluation
bien parallélisable sans divisions de longueur $s^{O(1)}\, d^{O(n)}$.
\end{lemme*}


\begin{proof}
D'après le critère \ref{centreproj} et le
Nullstellensatz projectif effectif \cite{L77} (voir aussi \cite{B83}) les assertions suivantes sont équivalentes:
\begin{enumerate}
\item[(1)]
les variables $x_{\lambda_{0}},\ldots , x_{\lambda_{m}}$ sont dépendantes
par rapport à $V$.
\item[(2)]
les variables $z, x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}$ appartiennent
au radical de l'idéal $J^{(\lambda)}$ engendré par
$f_1^{(\lambda)},
\ldots , f_s^{(\lambda)}$ dans $K^{(\lambda)}[z,x^{\overline{\lambda}}]$.
\item[(3)]
tous les monômes en $z, x_{\lambda_{m+1}},\ldots , x_{\lambda_{n}}$ de
degré $N := nd$ appar\-tiennent à $J^{(\lambda)}$.
\end{enumerate}

Soit $Q$ la matrice à coefficients dans $R^{(\lambda)}$, de l'application
linéaire qui à $(h_{1},\ldots , h_{s})$ associe $h_{1} f_{1} + \cdots +
h_{s} f_{s}$ ($h_{i}$ étant un polynôme de $k[z, x^{\overline{\lambda}}]$
de degré $N - \deg f_{i}$, $1 \leq i \leq s$). C'est une matrice
rectangulaire à $O(sN^n) = sd^{O(n)}$ lignes et $O(N^n) = d^{O(n)}$
colonnes.
La~condition (3) est équivalente à:
\begin{enumerate}
\item[(4)]
la matrice $Q$ est de rang maximal.
\end{enumerate}

En utilisant les techniques d'algèbre linéaire effective rappelées dans
\ref{berkomulmul}, nous pouvons calculer le rang de $Q$ par un algorithme
bien parallélisable et sans divisions, en effectuant $s^{O(1)}\, d^{O(n)}$
opérations arithmétiques et comparaisons dans $R^{(\lambda)}$. De
cette manière, nous pouvons vérifier si
la condition (4) est satisfaite, et si c'est le cas, l'algorithme calcule le
déterminant $g'$ d'une sous-matrice carrée de~$Q$ de rang maximal.
Ce déterminant est un polynôme de $k[x^{\lambda}]$ de degré
$d^{O(n)}$, donné par un calcul d'évaluation bien parallélisable et
sans divisions de longueur $s^{O(1)}\, d^{O(n)}$. Il se décompose en une
somme de polynômes homogènes non nuls; soit $g$ l'un d'entre eux.
Nous voyons immédiatement que $g$ est un polynôme homogène de
$k[x^{\lambda}]$
de degré $d^{O(n)}$, s'annule sur $V$ et est donné d'après
\cite{S73} par un calcul d'évaluation bien parallélisable et
sans divisions de longueur $s^{O(1)}\, d^{O(n)}$. En~utilisant
un ensemble questeur $(\gamma_1,\ldots ,\gamma_\ell)$ de
$\ell = s^{O(1)}\, d^{O(n)}$ points appropriés de $k^{m+1}$, nous transformons
l'algorithme de détermination du rang de $Q$ qui se déroule en
principe dans $R^{(\lambda)}$ par un algorithme qui s'exécute
dans $k$. Il ne contient pas de divisions, et bien parallélisable
et reste de complexité $s^{O(1)}\, d^{O(n)}$.
\end{proof}

\subsection{Mise en position de Noether effective pour les variétés
projectives}

Soit $r$ la dimension de $V$.

\begin{theorem*}[comparer à {\cite[5.6]{G88}}]
Au prix d'une
préparation préalable, nous
pouvons déterminer la dimension $r$ de $V$ en temps
\[
s^{O(1)}\, d^{O(n)}
\]
par un algorithme bien parallélisable et sans divisions. De plus, nous
pouvons trouver une $(n+1)\times (n+1)$-matrice non singulière à
coefficients dans $k$ telle que si $y_{0},\ldots , y_{n}$ sont par
définition de nouvelles variables $M(x_{0},\ldots , x_{n})$, les $r+1$
premières d'entre elles $y_{0},\ldots , y_{r}$ sont indépendantes
par rapport à $V$. Les nouvelles variables $y_{0},\ldots ,y_{n}$
sont en position de Noether par rapport à $V$.
\end{theorem*}

\begin{proof}
Nous construisons $M$ par récurrence.
Comme $f_1$ est non constant, nous pouvons le supposer unitaire en $x_n$
au prix d'une première transformation linéaire sur les variables
$x_{0},\ldots ,x_{n}$. Ceci signifie que la variable $x_n$ est en position
de Noether par rapport à $x_{0},\ldots , x_{n-1}$ et à $V$. Cette
transformation de variables peut être réalisée par un
algorithme bien parallélisable en temps $O(sd^{n})$.

Supposons maintenant par hypothèse de récurrence que pour un indice $m$
($0 \leq m < n$) tel que $x_{m+1},\ldots , x_{n}$ soient en position de
Noether par rapport à $x_{0},\ldots , x_{m}$ et à $V$. Testons à
l'aide du lemme~\ref{subsec:9.2} en temps séquentiel $s^{O(1)}\, d^{O(n)}$ et
parallèle $O(n^{2} \log^{2} sd)$ si les variables
$x_{0},\ldots ,x_{m}$ sont indépendantes par rapport à $V$.

Si c'est le cas, il nous suffit de prendre la matrice identité pour
$M$. Les variables $x_{0},\ldots ,x_{n}$ sont en position de Noether par
rapport à $V$ et la dimension de $V$ est $m$.

Dans le cas contraire, supposons que les variables $x_{0},\ldots ,x_{m}$
soient dépendantes par rapport à $V$. L'algorithme du lemme \ref{subsec:9.2}
calcule un polynôme homogène non constant $g$ de $k[x_{0},\ldots ,x_{m}]$
qui s'annule sur~$V$. Il est de degré $d^{cm}$ pour une constante $c$
approprié et s'évalue par un algorithme bien parallélisable et
sans divisions en $v = s^{O(1)}\, d^{O(n)}$ opérations
arithmétiques.

Soit $(\gamma_{1},\ldots , \gamma_{\ell})$
un ensemble questeur de
\[
\ell = 6(v+m+1)(v+m+2) = s^{O(1)}\, d^{O(n)}
\]
points appropriés de $k^{m+1}$. D'après \cite[Th.\,4.4]{HS82}, il existe
un point $\gamma_{i} = (\gamma_{0}^{(i)},\ldots , \gamma_{m}^{(i)})$
($1 \leq i \leq \ell$) de cet ensemble qui n'annule pas~$g$. Nous pouvons
trouver un tel point en évaluant $g$ en tous les points de l'ensemble
questeur, ce qui nécessite un temps séquentiel en $s^{O(1)}\,
d^{O(n)}$ et un temps parallèle en $O(n^{2} \log^{2} sd)$.
Il suffit maintenant de transformer les variables $x_0,\ldots ,x_m$
à l'aide des coordonnées de~$\gamma_i$ en nouvelles variables
$y_0,\ldots ,y_m$ telles que $g$, qui est un polynôme de
$k[x_0,\ldots ,x_m] = k[y_0,\ldots ,y_m]$ devienne unitaire en $y_m$.
Posons $y_{m+1} := x_{m+1},\ldots , y_{n} := x_{n}$. Nous obtenons
ainsi en temps séquentiel $s^{O(1)}\, d^{O(n)}$ par un algorithme
bien parallélisable et sans divisions
une $(n+1)\times (n+1)$-matrice non singulière
à coefficients dans $k$ qui décrit la transformation de variables
recherchée. Par construction, les nouvelles variables $y_m,\ldots ,
y_n$ sont en position de Noether par rapport à $y_0,\ldots ,y_{m-1}$ et
$V$.

L'itération du processus précédent nous conduit au résultat.
\end{proof}

\backmatter
\addtocontents{toc}{\protect \lsectionpart}
\bibliographystyle{jepalpha+eid}
\bibliography{xups97-01}
\end{document}