% Time-stamp: <modified on  3 Jan 2005 at 14:49 by Pierre Lescanne>
%% /MIM-1/REECRITURE/grobner.tex
\documentclass[%
  slidesonly,%  Pour sortir les transparents seuls
  semrot,%      Permettre des rotations eventuelles
  semhelv,%    Helvetica
  a4%           A4 paper
  ]{seminar}

\def\printlandscape{\special{landscape}}     % pour sortir en landscape
\slidesmag{5}

\usepackage{amsfonts,amsmath,amsthm,amssymb,stmaryrd}
\usepackage{fancybox}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage{color}
%\usepackage{amsmath}
\usepackage[all]{xy}
\usepackage{qsymbols}

%% Time-stamping  
%% compute the time in hours and minutes; 
 \newcount\timehh\newcount\timemm \timehh=\time 
 \divide\timehh by 60 \timemm=\time
 \count255=\timehh\multiply\count255 by -60 \advance\timemm by \count255
 \newcommand{\timestamp}
 { {\protect\small\sl\today\ -- 
 \ifnum\timehh<10 0\fi\number\timehh\,h\,
   \ifnum\timemm<10 0\fi\number\timemm}}
                                          % avec dvips


\articlemag{1}

\rotateheaderstrue       % si tu combines slide et slide*

\title{\color{red}{\textit{Réécriture}}}

\author{Bases de Gröbner}

\date{}

\pagestyle{}

\slidestyle{empty}

\slideframe{}   

%--- couleurs ----
\input{mes_couleurs}

%--- symboles ---
\renewcommand{\phi}{\varphi}
%\newcommand{\llbracket}{\ensuremath{|\![}}
%\newcommand{\rrbracket}{\ensuremath{]\!|}}
\newcommand{\PP}{\bl{\ensuremath{\cal P}}}
\newcommand{\gec}{\ensuremath{\succ_C}}
\newcommand{\Emb}{\bl{\ensuremath{\cal EMB}}}
\newcommand{\ali}{\newline\hspace*{20pt}}
\newcommand{\shat}{\ensuremath{\hat{\sigma}}}
\newcommand{\pref}{\mathop{\textbf{\textsl{prefix}}}}
\newcommand{\IN}{\ensuremath{\mathcal{IN}}}
\newcommand{\gtmult}{\ensuremath{>_{mult}}}
\newcommand{\dminus}{\mbox{\ensuremath{\stackrel{\raisebox{+.01ex}{.}}{-}}}}
%\newcommand{\Nat}{\textsf{I}\hspace{-.7pt}\textsf{N}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\Natstar}{\Nat_\star}
\newcommand{\A}{\ensuremath{\bl{\cal A}}}
\newcommand{\M}{{\cal M}}
\newcommand{\U}{{\cal U}}
\newcommand{\Ra}{\ensuremath{\mathop{\Rightarrow}}}
\newcommand{\et}{\mathop{\&}}
\newcommand{\sh}{\mathop{|}}
\newcommand{\set}[2]{\{#1~|~#2\}}
\newcommand{\da}{\downarrow}
\newcommand{\jgbl}{\mathop{\da}}
\newcommand{\lpo}{<_{lpo}}
\newcommand{\lepo}{\le_{lpo}}
\newcommand{\eq}{\stackrel{?}{=}}
\newcommand{\aco}{\{\!\!\{}
\newcommand{\acf}{\}\!\!\}}
\newcommand{\ench}{\mbox{\small \tt |}\hspace{-2.9pt}{\stackrel{\scriptscriptstyle _\bullet}{}\hspace{-5pt}>}}
\newcommand{\encheq}{\mbox{\raisebox{+0.2ex}{\small \tt |}
    \hspace{-5pt}\raisebox{+.5ex}{$\scriptscriptstyle \bullet$}\hspace{-5pt}$\ge$}}

%%%%%%%%% ajout special pour la completion %%%%%%%%%%%%
\newcommand{\la}{\leftarrow}
%\newcommand{\rastar}{\stackrel{\ast}{\rightarrow}}
\newcommand{\hligne}{\rule{\textwidth}{2pt}}
\newcommand{\subsum}{\mbox{\small \tt |}\!\!{\stackrel{\scriptscriptstyle _\bullet}{}\!\!\!>}}
\newcommand{\eqone}{\mbox{\mysymb \symbol{1}}}
\newcommand{\tri}{\mbox{\mysymb \symbol{2}}}
%%%%%%%% fin ajout %%%%%%%%%

\newcommand{\inferTwoLabel}[4]{\bl{
 {#1} \quad 
 \begin{array}{c}
   #2 \hspace{2em} #3\\
   \hline \noalign{\vskip 1pt}#4
  \end{array}}}

\newcommand{\leafLabel}[2]{\bl{
 {#1} \quad
  \begin{array}{c}
  #2
  \end{array} }}


%\newcommand{\inferLabel}[3]{\emph{#1}\ali #2 \Mapsto #3}

\newcommand{\inferLabel}[3]{
    \rouge{#1} \quad 
    \bl{\begin{array}{c}
      #2\\
      \hline \noalign{\vskip 1pt}#3
    \end{array}
  }}
\newenvironment{displaymathbleu}[1]{\begin{displaymath}\color{blue}#1}{\end{displaymath}}
    
%% ==============================================================
%%                   Reductions and other relations
%% ==============================================================

%\newcommand{\ra}{\xymatrix{\ar@{>}[r] &}}
\newcommand{\ra}{\rightarrow}
\newcommand{\ranorm}{\xymatrix{\ar@{>>|}[r] &}}
\newcommand{\rara}{\xymatrix{\ar@{>>}[r] &}}
\newcommand{\longequiv}{\xymatrix{\ar@3{-}[r] &}}

%%%%%%%%%%%%%%%%%%%% iteration of arrows  %%%%%%%%%%%%%%%%%%%%
\newcommand{\rastar}{\rasup{*}}
\newcommand{\raplus}{\rasup{+}}

%%%%%%%%%%%%%%%%%%%% fleches avec souscrit et superscrit %%%%%%%%%%%%%
% par exemple -- B, p --> s'ecrit \rasub{B,p}

\newcommand{\rasub}[1]{\xymatrix{\ar@{>}[r]_{#1} &}}
\newcommand{\subar}[1]{\xymatrix{\ar@{<-}[r]_{#1} &}}
\newcommand{\ranormsub}[1]{\xymatrix{\ar@{>>|}[r]_{#1} &}}
\newcommand{\rarasub}[1]{\xymatrix{\ar@{>>}[r]_{#1} &}}
\newcommand{\rasup}[1]{\xymatrix{\ar@{>}[r]^{#1} &}}
\newcommand{\supar}[1]{\xymatrix{\ar@{<-}[r]^{#1} &}}
\newcommand{\rarasup}[1]{\xymatrix{\ar@{>>}[r]^{#1} &}}
\newcommand{\rasupsub}[2]{\xymatrix{\ar@{>}[r]^{#1}_{#2} &}}
\newcommand{\rarasupsub}[2]{\xymatrix{\ar@{>>}[r]^{#1}_{#2} &}}
\newcommand{\cv}[1]{\xymatrix{\ar@{<->}[r]_{#1} &}}
\newcommand{\conv}[1]{\xymatrix{\ar@{<->}[r]_{#1}^{*} &}}
\newcommand{\convplus}[1]{\xymatrix{\ar@{<->}[r]_{#1}^{+} &}}

%%%%%%%%%%%%%%%%%%%% Les fleches %%%%%%%%%%%%%

\newcommand{\rabeta}{\rasub{\beta}}
\newcommand{\rarabeta}{\rarasub{\beta}}
\newcommand{\raE}{\rasub{E}}
\newcommand{\raR}{\rasub{R}}
\newcommand{\Rar}{\subar{R}}
\newcommand{\rastarR}{\rasupsub{*}{R}}
\newcommand{\raraR}{\rarasub{R}}
\newcommand{\plusararR}{\xymatrix{&\ar@{>>}[l]^{R}_+}}
\newcommand{\plusraraR}{\rarasupsub{+}{R}}
\newcommand{\rapar}{\xymatrix @ -1.5pc {\ar@{>}[rr]&||&}}
\newcommand{\rarapar}{\xymatrix @ -1.5pc {\ar@{>>}[rr]&||&}}
\newcommand{\remb}{\rasub{\Emb}}
\newcommand{\plgt}{\rasupsub{+}{\Emb}}
\newcommand{\plonge}{\xymatrix{\ar@{<-}[r]_{\Emb}^{*} &}}

%%%%%%%%%%%%%%%%% Headings %%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\heading}[1]{%
{\color{cyanp}\textbf{\large #1}}{\color{yellow}\\\rule{\textwidth}{2pt}
}}

\newcommand{\subheading}[1]{%
  \begin{center}
    \color{vertfonce}{\bf\Ovalbox{#1}}
  \end{center}}

\begin{document}
%------------------------------------------------------
\begin{slide}
    \maketitle
    \addtocounter{slide}{-1}
    \slidepagestyle{empty}

\vfill 
\hfill\textit{\footnotesize version du \timestamp}

\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Les monômes à $n$-variables}

Soit \bleu{K} un corps.

Un \emph{monôme} est une formule  \bleu{X_1^{d_1}...X_n^{d_n}}.

Le \emph{degré} d'un monôme est \bl{\[deg(X_1^{d_1}...X_n^{d_n}) =
  \sum_{i=1}^n d_i.\]}

Un \emph{monôme affecté d'un coefficient} \bleu{c\in K} est une
formule \bleu{c X_1^{d_1}...X_n^{d_n}}.  \vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{L'anneau des polynômes à $n$-variables sur \bleu{K}}

Un \emph{polynôme} \bleu{f} est un somme finie d'un
\emph{ensemble}\footnote{pas d'un multiensemble, donc il ne doit pas y
  avoir de répétitions.} de monômes \bleu{\{m_1,...,m_k\}} affectés
de coefficients: \bl{\[f= \sum_{j=1}^k c_j m_j\]}

C'est surtout un ensemble de paires
\bleu{\{(c_1,m_1),...,(c_k,m_k)\}}, sans répétition de \bleu{m_i}.

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{L'anneau des polynômes à $n$-variables sur \bleu{K}}

Les polynômes à coefficients dans \bleu{K} forment un anneau \ali noté
\bleu{K[X_1,...,X_n]}, \ali c'est l'\emph{anneau des polynômes à
  $n$-variables}.

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}

\heading{Exemples}

\bl{\[X_1^2 X_2 - 2X_1 X_2 + 3 X_2\]} est un polynôme dont les monômes
sont \quad \bleu{X_1^2 X_2, \quad X_1 X_2, \quad X_2}.

\vspace*{20pt}

\verdir{Remarquons} que dans les polynômes en tant que formules, les \bleu{X_1,
  ..., X_n} jouent le rôle de constantes.

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Idéaux}
Un \emph{idéal} est un sous-ensemble \bleu{J\subseteq K[X_1,...,X_n]} tel
que
\begin{enumerate}
\item \bleu{f,g\in J} \quad \emph{$\Longrightarrow$} \quad \bleu{f + g\in J}.
\item \bleu{f\in J} et \bleu{g\in K[X_1,...,X_n]}
  \quad \emph{$\Longrightarrow$} \quad \bleu{f\cdot g\in J}. 
\end{enumerate}

L'\emph{idéal engendré par} \bleu{f_1,..., f_k\in K[X_1,...,X_n]} est
l'ensemble \bl{\[\langle f_1, ...,f_k\rangle = \{f_1\cdot g_1+\cdots+
  f_k\cdot g_k ~|~ g_1,..., g_k\in K[X_1,...,X_n]\}.\]} 

C'est le plus petit idéal qui contient l'ensemble \bleu{\{f_1,...,
  f_k\}}. 


\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Liens entre congruences et idéaux}
%
Une \emph{congruence} est une relation d'équivalence \quad
\bleu{\equiv} \quad telle que \ali
\begin{small} pour tous \bleu{g, g'\in
    K[X_1,...,X_n]}, \ali \bleu{f_1\equiv f_2} et \bleu{f_1'\equiv
    f_2'} \emph{$\Longrightarrow$} \bleu{f_1\cdot g + f_1'\cdot g'
    \equiv f_2 \cdot g + f_2' \cdot g'}.
\end{small} 

L'ensemble des polynômes congrus à $0$ forment un \emph{idéal}.

Si \bleu{J} est un idéal, la relation \bleu{\equiv_J} définie par
 \bl{\[ f\equiv_J g \qquad \Longleftrightarrow \qquad f - g \in J\]}
est une congruence %
\ali dont la classe de congruence du polynôme \bleu{0} est précisément
\bleu{J}.


\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{L'appartenance à un idéal}
Le problème de l'appartenance à un idéal est le suivant :
\begin{description}
\item[\verdir{Instance :}] \bleu{f, f_1, ..., f_k \in K[X_1,...,X_n]}
\item[\verdir{Question :}] Est-ce que \bleu{f\in\langle  f_1, ..., f_k\rangle} ?
\end{description}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Comment utiliser les congruences pour réduire ?}
%
Puisque les idéaux sont liés aux congruences.  On va d'abord parler en
termes de congruences.  

Étant donné un polynôme \bleu{f}, pour savoir s'il appartient à un
idéal, il suffit de trouver un «polynôme plus simple» et de tester
l'appartenance à l'idéal  sur ce polynôme plus simple.

\verdir{«Idéalement»}, \bleu{0} est bon candidat pour ce polynôme plus
simple. 

Il faut donc utiliser les congruences pour \verdir{réduire}.

\emph{Question :}   Comment ?


\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Comment utiliser les congruences pour réduire ?}
%
Étant donné un idéal \bleu{J} qui contient un polynôme %
\bl{\[f= \sum_{j=1}^k c_j m_j\]} congru à \bleu{0} et dont le monôme
\verdir{le plus «grand»} est \bleu{m_k}, on a %
\bl{\[m_k  \equiv_J - c_k^{-1} \sum_{j=1}^{k-1} c_j m_j.\]}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
et on peut utiliser la règle %
\bl{\[m_k \ra - c_k^{-1} \sum_{j=1}^{k-1} c_j m_j.\]}

Tout instance de \bleu{m_k} peut-être remplacée par
\bleu{- c_k^{-1} \sum_{j=1}^{k-1} c_j m_j}. 

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
Si on revient à l'exemple :
\bl{\[X_1^2 X_2 - 2X_1 X_2 + 3 X_2\]}
Le monôme le  plus grand est clairement \bleu{X_1^2 X_2} et la règle que
l'on engendre est
\bl{\[X_1^2 X_2 \ra 2X_1 X_2 - 3 X_2.\]}
Dans le polynôme
\bl{\[2X_1^2 X_2^2 + 2X_1 X_2^2 + X_1 X_2\]}
cela revient à remplacer le monôme \bleu{X_1^2 X_2^2 = (X_1^2 X_2)X_2}
par \bleu{2X_1 X_2^2 - 3 X_2^2}, 

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
ce qui donne
\bl{\[4X_1 X_2^2 - 6 X_2^2 + 2X_1 X_2^2 + X_1 X_2\]}
soit
\begin{displaymathbleu}
  6X_1 X_2^2 - 6 X_2^2 + X_1 X_2
\end{displaymathbleu}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
ce qui donne
\bl{\[4X_1 X_2^2 - 6 X_2^2 + 2X_1 X_2^2 + X_1 X_2\]}
soit
\bl{\[6X_1 X_2^2 - 6 X_2^2 + X_1 X_2\]}
au lieu de 
\bl{\[2X_1^2 X_2^2 + 2X_1 X_2^2 + X_1 X_2\]}
qui est «manifestement» plus simple. \hfill \emph{$`(:-)$}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
ce qui donne
\bl{\[4X_1 X_2^2 - 6 X_2^2 + 2X_1 X_2^2 + X_1 X_2\]}
soit
\bl{\[6X_1 X_2^2 - 6 X_2^2 + X_1 X_2\]}
au lieu de 
\bl{\[2X_1^2 X_2^2 + 2X_1 X_2^2 + X_1 X_2\]}
qui est «manifestement» plus simple. \hfill \emph{$`(:-)$}
\vfill
\textcolor{vertfonce}{Les coefficients et le nombre de monômes
  peuvent augmenter,} 
\ali mais \emph{le degré diminue}!
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Les ordres sur les monômes}
Les ordres que l'on considère sont totaux,
\ali mais on a le choix entre plusieurs et c'est crucial pour
\verdir{l'efficacité de la complétion.}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Ordres admissibles sur les monômes}
Un ordre \bleu{\prec} sur les monômes est \emph{admissible} si 
\begin{enumerate}
\item il est total,
\item il est contient l'ordre \emph{divise} sur les monômes,
\bl{\[m_1 | m_2 \qquad \emph{"=>"} \qquad m_1\prec m_2,\]}
\item il est compatible avec le produit:
\bl{\[m_1\prec m_2 \qquad \emph{"=>"} \qquad m\cdot m_1
  \prec m\cdot m_2.\]}
\end{enumerate}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\doublebox{\parbox{5cm}{\emph{Lemme :}  Tout ordre admissible termine.}}

L'ordre \verdir{divise} sur les monômes est l'ordre produit (composante par
composante) de l'ordre naturel sur \bleu{\Nat}.

C'est  donc un \verdir{beau préordre}.  

Donc comme les ordres admissibles contiennent un beau préordre, ils
sont aussi de beaux préordres, donc ils terminent.

\vfill

N. B. Ce résultat est parfois appelé le lemme de Dixon (1910).
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Ordres admissibles sur les monômes (exemple)}
L'ordre défini par 
\begin{enumerate}
\item \bleu{deg(X_1^{d_1}...X_n^{d_n}) > deg(X_1^{e_1}...X_n^{e_n})},
\item ou \bleu{deg(X_1^{d_1}...X_n^{d_n}) = deg(X_1^{e_1}...X_n^{e_n})}
  et \bleu{(d_1,...,d_n) >_{lex} (e_1,...,e_n)}.
\end{enumerate}
est admissible.
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Quelques définitions}
On se donne un ordre admissible \bleu{\prec}.

Étant donné un polynôme \bleu{f}, on définit
\begin{itemize}
\item le \emph{monôme de tête} \bleu{t_f}, c'est le plus grand monôme pour
  l'ordre \bleu{\prec} qui apparaît dans \bleu{f},
\item le \emph{coefficient de tête} \bleu{c_f}, c'est le coefficient dans
  \bleu{f} de \bleu{t_f},
\item le \emph{reliquat} du polynôme \bleu{r_f}.
\end{itemize}
Typiquement on a \bl{\[ f = c_f  t_f + r_f.\]}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Quelques définitions (suite)}
Dans la suite on ne s'intéressera qu'aux polynômes \bleu{f} avec
\bleu{c_f = 1}.

En effet, \bl{\[\langle f_1, ..., f_k\rangle = \langle
  c_{f_1}^{-1}  f_1, ..., c_{f_k}^{-1}  f_k\rangle.\]}

On peut aussi supposer qu'aucun \bleu{f_i} n'est le polynôme \bleu{0}.
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
  \heading{Règle} 
  %
  Si \bleu{f} est un polynôme de coefficient de tête \bleu{1}, alors
  on définit une règle \bl{\[t_f \rasub{f} -r_f.\]}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
  \heading{Réduction} 
  %
  La règle \bleu{t_f \rasub{f} -r_f} engendre une réduction
  \bleu{g\rasub{f} g'} ainsi
\begin{enumerate}
\item \bleu{g} contient un monôme \bleu{m} avec coefficient \bleu{a}
  tel que,
\item \bleu{m = t_f \cdot m'}
\item  et \bleu{g'  = g - a m' \cdot r_f}. 
\end{enumerate}

\vfill

Si \bleu{F = \{f_1, ..., f_k\}} alors %
\bl{\[\rasub{F} \quad \emph{=} \quad  \bigcup_{i=1}^{n}
  \rasub{f_i}\quad \emph{=} \quad  \rasub{f_1} \cup \ldots \cup
  \rasub{f_k}.\]} 

\end{slide}
%------------------------------------------------------
\begin{slide}
\doublebox{\parbox{6.5cm}{\emph{Lemme :}  Soient \bleu{f, g, g', h
      \in K[X_1,...,X_n]}, \ali \bleu{m} un monôme, \ali \bleu{b\in
      K^*}. 
    
    Supposons que \bleu{f} a \bleu{1} comme coefficient de tête.
    \begin{enumerate}
    \item \bleu{f\rasub{f} 0},
    \item \bleu{g\rasub{f} g'\quad \emph{\Longrightarrow} \quad b m
      \cdot g \rasub{f} b m \cdot g'},
    \item \bleu{g\rasub{f} g'\quad \emph{\Longrightarrow} \quad h + g
        \rasub{f}  h + g'}.
    \end{enumerate}
}}
  
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\doublebox{\parbox{6.5cm}{\emph{Lemme :}  Soient \bleu{f, g, g', h
      \in K[X_1,...,X_n]}, \ali \bleu{m} un monôme, \ali \bleu{b\in
      K^*}. 
    
    Supposons que \bleu{f} a \bleu{1} comme coefficient de tête.
    \begin{enumerate}
    \item \bleu{f\rasub{f} 0},
    \item \bleu{g\rasub{f} g'\quad \emph{\Longrightarrow} \quad b m
      \cdot g \rasub{f} b m \cdot g'},
    \item \bleu{g\rasub{f} g'\quad \emph{\Longrightarrow} \quad h + g
        \rasub{f}  h + g'}.
    \end{enumerate}
}}

\vspace*{20pt}

En exercice.

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\bl{
  \begin{eqnarray*}
    F &=& \{f_1, ..., f_k\}\\
    J &=& \langle  f_1, ..., f_k\rangle
  \end{eqnarray*}
}

\doublebox{\parbox{4,5cm}{\emph{Théorème :} \bleu{\equiv_J \quad = \quad
      \conv{F}} }}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{Bases de Gröbner}
%
\bleu{G = \{f_1, ..., f_k\}} est une base de Gröbner de l'idéal
\bleu{J} si 
\begin{enumerate}
\item \bleu{J = \langle  f_1, ..., f_k\rangle},
\item \bleu{\rasub{G}} est confluent.
\end{enumerate}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\heading{S-polynômes}
%
\begin{small}
Les \emph{S-polynômes} sont en quelque sorte les \verdir{paires critiques} des
règles. 
\end{small}

Soient deux polynômes \bleu{f} et \bleu{g} de coefficients de tête
\bleu{1}.

Soit \bleu{m = ppcm(t_f, t_g)}.

Soient 
\begin{itemize}
\item \bleu{m_f} tel que \bleu{m = m_f \cdot t_f},
\item \bleu{m_g} tel que \bleu{m = m_g \cdot t_g},
\end{itemize}
Le S-polynôme de \bleu{f} et \bleu{g} est défini par \bl{\[S(f, g) =
m_f \cdot f - m_g \cdot g.\]} \vfill
  
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\doublebox{\parbox{7cm}{\emph{Théorème:}  Soit \bleu{G = \{f_1, ...,
      f_k\}}.
\ali \bleu{G} est une base de Gröbner de \bleu{J = \langle  f_1, ...,
  f_k\rangle} %
\ali \qquad \verdir{ssi} %
\ali tous les S-polynômes de \bleu{G} se réduisent à \bleu{0}.
}}

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
  \begin{center}
    {\large \bf \color{vertfonce}{\textit{L'algorithme de Buchberger}}}
\end{center}
\end{slide}
%------------------------------------------------------
\begin{slide}
\begin{footnotesize}

\verdir{Données}

Un ensemble fini de polynômes \bleu{\{ f_1,..., f_k\}} de
coefficient de tête 1. 

Un ordre admissible 

\vspace*{20pt}

\verdir{Résultat}

Un ensemble fini de polynômes \bleu{G_i} qui est une base de Gröbner de
\bleu{\langle f_1,..., f_k\rangle}. 
\end{footnotesize}
\end{slide}
%------------------------------------------------------
\begin{slide}
\begin{footnotesize}

\verdir{Initialisation} 
\begin{itemize}
\item \bleu{i:=0};
\item \bleu{G_0 := F};
\item \bleu{B_0:= \{(f,g) ~|~ f,g\in F, f\not=g\}};
\end{itemize}


\end{footnotesize}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\begin{footnotesize}

\verdir{Initialisation} 
\begin{itemize}
\item \bleu{i:=0};
\item \bleu{G_0 := F};
\item \bleu{B_0:= \{(f,g) ~|~ f,g\in F, f\not=g\}};
\end{itemize}

\emph{Tant que} \bleu{B_i \not= \emptyset} \emph{faire}
\begin{itemize}
\item Choisir une paire \bleu{(f,g)\in B_i},
\item Calculer le S-polynôme \bleu{S(f, g)},
\item Calculer une \bleu{\rasub{G_i}} forme normale \bleu{h} de
  \bleu{S(f, g)},
\item Si \bleu{h\not=0}, alors
  \begin{itemize}
  \item \bleu{B_{i+1} := (B_i - (f, g)) \cup \{(k, c_h^{-1} h) ~|~
      k\in G_i\}};
    \item \bleu{G_{i+1} := G_i \cup \{c_h^{-1} h\}};
    \item \bleu{ i := i+1;}
  \end{itemize}
\item Si \bleu{h=0}, alors 
  \begin{itemize}
  \item \bleu{B_{i+1} := (B_i - (f, g))}; 
  \item \bleu{G_{i+1} := G_i}; 
  \item \bleu{i := i+1}.
\end{itemize}
\end{itemize}
\end{footnotesize}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\begin{footnotesize}

\verdir{Retourne} \bleu{G_i}
\end{footnotesize}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\doublebox{\parbox{7cm}{\emph{Théorème:}  L'algorithme de Buchberger
    termine \ali et retourne une base de Gröbner.
}}
\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\doublebox{\parbox{7cm}{\emph{Théorème:}  L'algorithme de Buchberger
    termine \ali et retourne une base de Gröbner.
}}

\vspace*{20pt}
\emph{Démonstration :}

Soit \bleu{J = \langle f_1,..., f_k\rangle}.

On remarque que pour chaque étape on a \bleu{\langle G_i\rangle = J}.
\begin{itemize}
\item Les \bleu{S(f, g)\in J}, car \bleu{f, g \in J}.
\item De même si \bleu{S(f, g)\in J = \langle G_i\rangle} et
  \bleu{S(f, g) \subar{G_i} h}, on a \bleu{c_h^{-1}\in J}.
\end{itemize}
Le résultat est une base de Gröbner

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
\verdir{L'algorithme termine}.

Considérons les monômes de tête \bleu{m_i} des polynômes \bleu{h_i}
créés à chaque étape par réduction des S-poynomes calculés. 

Clairement \bleu{t_{f_j}\not |~ m_i } pour aucun des \bleu{j}
(\bleu{1\le j\le k}) \ali et \bleu{m_{i'} \not |~ m_{i}} pour \bleu{i'< i}.

Comme l'ordre \emph{divise} est un bel ordre sur les monômes, la suite
des \bleu{m_i} ne peut pas être infinie.

\vfill
\end{slide}
%------------------------------------------------------
\begin{slide}
  
  Remarquons que l'algorithme présenté \emph{n'interréduit pas} les
  polynômes.
  
  Même après interréduction, l'algorithme est \emph{sensible à l'ordre
    admissible} choisi.
  
  Il aussi indispensable d'implanter des \emph{critères} pour ne pas
  calculer toutes les S-polynômes.

\vfill
\end{slide}

\end{document}

% LocalWords:  multiensemble Dixon deg lex S-polynômes ppcm Gr bner ssi
% LocalWords:  Buchberger n'interréduit  interréduction
