% -*- coding: utf-8 -*-
%!TEX encoding = UTF-8 Unicode
\documentclass[xcolor=svgnames,leqno]{beamer}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[ngerman]{babel}

\usepackage[shortlabels]{enumitem} % allows to underline counters in enumerate environment (contrary to enumerate), shortlabels option provides compatibility with enumerate package

\usepackage{ushort}
\newcommand\x{\ushort X}

\usepackage{stmaryrd} % for \mapsfrom or \lightning

\usepackage{calrsfs} % improve mathcal

%\usepackage{tikz} % for commutative diagrams
%\usetikzlibrary{cd,calc}

\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\Q{\mathbb Q}
\newcommand\R{\mathbb R}
\newcommand\C{\mathbb C}
\renewcommand\H{\mathbb H}
\renewcommand\P{\mathbb P}
\newcommand\F{\mathbb F}

\newcommand\p{\mathfrak p}
\newcommand\q{\mathfrak q}
\renewcommand\O{\mathcal O}

\newcommand\al{\alpha}
\newcommand\de{\delta}
\newcommand\si{\sigma}
\newcommand\ph{\varphi}
\newcommand\ps{\psi}

\newcommand\et{\mathbin{\&}}
\newcommand\id{\text{id}}

\newcommand\cc[2]{\overline{#1}^{\substack{\\\\#2}}}

\newcommand{\case}[2]{$\begin{Bmatrix}\text{#1}\\\text{#2}\end{Bmatrix}$}

\DeclareMathOperator\Aut{Aut}
\DeclareMathOperator\lcm{lcm}
\DeclareMathOperator\rk{rk}
\DeclareMathOperator\red{red}
\DeclareMathOperator\spol{spol}
\DeclareMathOperator\LM{LM}
\DeclareMathOperator\LC{LC}
\DeclareMathOperator\Hom{Hom}
\DeclareMathOperator\constr{\mathrel \wedge \joinrel \hspace{-1.47ex}\smile}

\setbeamertemplate{navigation symbols}{}
\setbeamersize{text margin left = 1em}
\setbeamercolor{title}{fg=red!70!black}
\setbeamercolor{frametitle}{fg=red!70!black}
\setbeamercolor{framesubtitle}{fg=green!30!black}
\setbeamercolor{institute}{fg=green!30!black}
\setbeamercolor{date}{fg=blue!50!black}
\renewcommand\a{\alert}
\newcommand\s{\structure}
\renewcommand\b[1]{\textcolor{Brown}{#1}}
\newcommand\hide[1]{}

\begin{document}
\title{§2.6 Minimale und reduzierte Gröbnerbasen}
\date{}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}{Generalvoraussetzung}
In diesem Abschnitt sei stets \s{$K$ ein Körper}.

\bigskip
Ferner sei eine \s{Monomordnung $\le$ auf $[\x]$} fixiert.
\end{frame}

\begin{frame}
\s{Lemma.}
Sei $M\subseteq[\x]$ und $I:=(M)$. \pause
Dann ist die Menge \[\s{M':=\{v\in M\mid\a{\nexists u\in M:(u\ne v~\&~u| v)}\}}\pause\] der bezüglich der Teilerrelation
minimalen Elemente von $M$ \pause \s{das \a{kleinste} aus Monomen bestehende Erzeugendensystem von $I$}, \pause das heißt $I=(M')$ und für alle $M''\subseteq[\x]$ mit $I=(M'')$ gilt $M'\subseteq M''$. \pause\s{Insbesondere ist $M'$ endlich.}\pause

\begin{proof} Zu zeigen:
\begin{enumerate}[(a)]
\item $M\subseteq(M')$
\item $\forall M''\subseteq[\x]:(I=(M'')\implies M'\subseteq M'')$
\end{enumerate}\pause

Zu (a). Sei $w\in M$. Wähle $v\in M'$ mit $v|w$. \pause Dann $w\in(M')$.\pause

\smallskip
Zu (b). Sei $M''\subseteq[\x]$ mit $I=(M'')$. Sei $v\in M'$. \s{Zu zeigen ist $v\in M''$.} \pause
Wegen $v\in M\subseteq I=(M'')$ gibt es $w\in M''$ mit $w|v$. \pause
Wegen $M''\subseteq I=(M)$ gibt es $u\in M$ mit $u|w$. \pause
Also $u|w|v$, woraus wegen $v\in M'$ und $u\in M$ folgt $u=w=v$, insbesondere
$v=w\in M''$.
\end{proof}
\end{frame}

\begin{frame}
\s{Lemma.}
Sei $I\subseteq K[\x]$ ein monomiales Ideal. \pause \s{Dann besitzt $I$ \a{genau ein} aus Monomen bestehendes Erzeugendensystem $M$ derart, dass kein Element von $M$ ein anderes Element von $M$ teilt.} \pause
Es ist $M$ endlich und das kleinste aus Monomen bestehende Erzeugendensystem von $I$. \pause
Man erhält $M$ aus jedem anderen aus Monomen bestehenden Erzeugendensystem
$M'$ von $I$, indem man die bezüglich der Teilerrelation auf $M'$ nicht minimalen Elemente aus $M'$ entfernt.\pause

\begin{proof} \s{Um die \a{Eindeutigkeit} zu zeigen, sei $M\subseteq[\x]$ mit $I=(M)$ und
$\forall u,v\in M:(u\ne v\implies {u{\not|}~v})$.} \pause Mit der Notation des letzten Lemmas gilt dann offenbar $M=M'$ und $M'$ ist nach dem
letzten Lemma durch $I$ eindeutig bestimmt. \pause Die \a{Existenz} und die restlichen Aussagen folgen ebenfalls aus dem letzten Lemma.
\end{proof}
\end{frame}

\begin{frame}{Minimale Gröbnerbasen}
\s{Definition.} Eine Gröbnerbasis $G\subseteq K[\x]$ heißt \a{minimal}, wenn sie minimal unter allen Gröbnerbasen
\a{des von $G$ erzeugten Ideals} ist.\pause

\bigskip
\s{Proposition.} Sei \s{$G\subseteq K[\x]\setminus\{0\}$} endlich und \s{$I:=(G)$}.\\
\a{Dann sind äquivalent:}\pause
\begin{enumerate}[(a)]
\item $G$ ist eine minimale Gröbnerbasis.\pause
\item $G$ ist eine Gröbnerbasis derart, dass kein Leitmonom eines Elements von $G$ das Leitmonom eines anderen Elements von $G$ teilt.\pause
\item Je zwei verschiedene Elemente von $G$ haben verschiedene Leitmonome und \[\s{\{\LM(g)\mid g\in G\}}\] ist das
\a{kleinste} aus Monomen bestehende Erzeugendensystem von \a{$L(I)$}.
\end{enumerate}
\end{frame}

\begin{frame}
\s{Satz.}
Sei \s{$I\subseteq K[\x]$} ein Ideal. \a{Dann besitzt $I$ eine minimale Gröbnerbasis.} \pause
Sind \a{$G$ und $H$ zwei minimale Gröbnerbasen von $I$}, so gilt \s{$\#G=\#H=\#\{\LM(g)\mid g\in G\}$} \pause und \s{$\{\LM(g)\mid g\in G\}=\{\LM(h)\mid h\in H\}$}.\pause

\begin{proof} \s{Die zweite Aussage ist klar mit (c) aus der letzten Proposition.} \pause
Um die \a{Existenz} einer minimalen Gröbnerbasis von $I$ zu zeigen, wähle man zunächst
eine beliebige Gröbnerbasis $G\subseteq K[\x]\setminus\{0\}$ von $I$. \pause Offensichtlich gibt es $H\subseteq G$ mit
\[(\{\LM(g)\mid g\in G\})=(\{\LM(h)\mid h\in H\})\] derart, dass kein Leitmonom eines Elements von $H$ das Leitmonom eines anderen Elements
von $H$ teilt. \pause Wegen $(\{\LM(h)\mid h\in H\})=(\{\LM(g)\mid g\in G\})=L(I)$ ist auch $H$ eine Gröbnerbasis von $I$. \pause
Nach der Proposition ist $H$ eine minimale Gröbnerbasis.\pause
\end{proof}

\s{Bemerkung.}
Es ist jetzt klar, wie man zu einer gegebenen endlichen Menge $F\subseteq K[\x]$ eine minimale Gröbnerbasis $H$ von $(F)$ berechnet.
\end{frame}

\begin{frame}{Reduzierte Gröbnerbasen}
\s{Definition.}
\begin{enumerate}[(a)]
\item Ein Polynom \s{$f\in K[\x]$} heißt \a{normiert} (bezüglich $\le$),\\wenn \s{$f\ne0$} und \s{$\LC(f)=1$}.\pause
\item Eine Menge \s{$F\subseteq K[\x]$} heißt \a{normiert} (bezüglich $\le$),\\wenn jedes ihrer Elemente normiert ist.\pause
\item Eine Menge \s{$F\subseteq K[\x]$} heißt \a{reduziert} (bezüglich $\le$),\\wenn $F$ normiert ist und \s{jedes $f\in F$ reduziert modulo
$F\a{\setminus\{f\}}$} ist.\pause
\end{enumerate}

\bigskip
\s{Proposition.} \a{Jede reduzierte Gröbnerbasis ist minimal.}
\end{frame}

\begin{frame}
\s{Satz.} Jedes Ideal von $K[\x]$ besitzt eine eindeutig bestimmte \a{reduzierte} Gröbnerbasis.

\begin{proof}
Sei $I\subseteq K[\x]$ ein Ideal.

\begin{overprint}
\onslide<2-10>
\a{\underline{Eindeutigkeit}} \s{Seien $G$ und $H$ reduzierte Gröbnerbasen von $I$.} Da $G$ und $H$ nach der letzten Proposition
minimal sind, \uncover<3->{gilt nach
dem letzten Satz \s{$\#G=\#H=\#\{\LM(g)\mid g\in G\}$} und \[\s{(*)\qquad\{\LM(g)\mid g\in G\}=\{\LM(h)\mid h\in H\}}.\]}
\uncover<4->{Sei $g\in G$. \a{Es reicht $g\in H$ zu zeigen.}
Wähle $h\in H$ mit $\s{u:=\LM(g)=\LM(h)}$. \a{Wir behaupten $g=h$.}}
\uncover<5->{Wegen $(*)$ gilt offenbar \a{$\red(G)=\red(H)$}.}
\uncover<6->{\s{Wegen $g\in\red(G\setminus\{g\})$ gilt $M(g)\setminus\{u\}\subseteq\red(G)$.\\}}
\uncover<7->{\s{Analog $M(h)\setminus\{u\}\subseteq\red(H)$.}}
\uncover<8->{Da $g$ und $h$ normiert sind, haben wir $\s{M(g-h)\subseteq(M(g)\cup M(h))\setminus\{u\}
\subseteq\red(G)=\red(H)}$ und daher \a{$g-h\in\red(G)$}.}
\uncover<9->{Andererseits $g-h\in I$ und daher
$\s{g-h\underset G{\overset*\longrightarrow}0}$.\\}
\uncover<10->{Es folgt $g-h=0$, also \a{$g=h\in H$}.}

\onslide<11-15>
\a{\underline{Existenz}} \s{Wähle mit dem letzten Satz eine minimale Gröbnerbasis $G$ von $I$.}
\uncover<11->{Wähle zu jedem $g\in G$ ein $g'\in\red(G\setminus\{g\})$ mit $\s{g\underset{G\setminus\{g\}}{\overset*\longrightarrow}g'}$.}\uncover<12->{ \a{Wegen der Minimalität von $G$ gilt $\LM(g')=\LM(g)$ für alle
$g\in G$.}}
\uncover<13->{\s{Mit $G$ ist auch $H:=\{g'\mid g\in G\}$ eine Gröbnerbasis von $I$.}}
\uncover<14->{Man sieht
$\red(G\setminus\{g\})=\red(H\setminus\{g'\})$ für alle $g\in G$.}
\uncover<15->{Somit \a{$g'\in\red(H\setminus\{g'\})$} für alle $g\in G$, das heißt \a{$H$ ist reduziert}.}
\end{overprint}
\end{proof}
\end{frame}

\begin{frame}{Interreduktionsalgorithmus}
\begin{tabbing}
\a{Eingabe:} \ \=\s{$F\subseteq K[\x]$ endlich}\\[0.2em]
\a{Ausgabe:} \>\s{$G\subseteq K[\x]$ endlich und reduziert mit $(G)=(F)$ derart,}\\
\>\a{dass $G$ eine Gröbnerbasis ist, falls $F$ eine ist.}\pause\\[0.2em]
$G\leftarrow F;$\\[0.2em]
solange es $g\in G$ gibt mit $g\notin\red(G\setminus\{g\})$\\[0.4em]
\>\big(\=wähle $g\in G$ mit $g\notin\red(G\setminus\{g\})$;\\[0.2em]
\>\>wähle $h\in K[\x]$ mit $g\underset{G\setminus\{g\}}\longrightarrow h$; $G\leftarrow(G\setminus\{g\})\cup\{h\}$\big);\\[0.4em]
$G\leftarrow\{\frac g{\LC(g)}\mid g\in G\setminus\{0\}\}$\pause
\end{tabbing}

\begin{overprint}
\onslide<3>
\s{Beweis}. \a{\underline{Terminierung}} \s{Angenommen} der Algorithmus \s{terminiert \a{nicht}}. Wähle dann $s\in\N$ und
$g_1^{(0)},\dots,g_s^{(0)}\in K[\x]$ mit $\s{F=\{g_1^{(0)},\dots,g_s^{(0)}\}}$. Dann gilt zu Beginn des ersten Schleifendurchlaufs
$\s{G=\{g_1^{(0)},\dots,g_s^{(0)}\}}$. Wir nehmen an zu Beginn des $i$-ten Durchlaufs ($i\in\N$) gelte $\s{G=\{g_1^{(i-1)},\dots,g_s^{(i-1)})}$
für schon definierte $g_1^{(i-1)},\dots,g_s^{(i-1)}\in K[\x]$. \a{[\dots]}
\onslide<4>
\s{Beweis.} \a{\underline{Korrektheit}} \a{Schleifeninvarianten:}
\begin{enumerate}[(a)]
\item $G\subseteq K[\x]$ ist endlich mit $(G)=(F)$.
\item $G$ ist eine Gröbnerbasis, falls $F$ eine war.
\end{enumerate}
Für (a) ist das schnell zu sehen. Für (b) reicht es zu zeigen, dass $\s{L(I)=(\{\LM(f)\mid f\in G\setminus\{0\}\})}$ mit $I:=(F)$
eine Invariante ist. \a{[\dots]}\qed
\end{overprint}
\end{frame}

\begin{frame}
\s{Bemerkung.}
Wie versprochen sehen wir jetzt, dass Gröbnerbasen \a{gleichzeitig} \s{den euklidischen Algorithmus für Polynome in \a{einer} Variablen}
als auch den \s{Gauß-Algorithmus für \s{lineare} Polynome} verallgemeinern: \pause Seien nämlich \s{$f_1,\dots,f_s\in K[\x]$}
und \s{$I:=(f_1,\dots,f_s)$}.
\begin{overprint}
\onslide<3>
\begin{enumerate}[(a)]
\item Gelte $n=1$, also $\x=X$. Dann gibt es \a{genau ein} $g\in K[\x]$ mit \a{$I=(g)$} und \s{$g$ normiert oder $g=0$}. Dann
ist $\{g\}\setminus\{0\}$ die eindeutig bestimmte reduzierte Gröbnerbasis von $I$.
\end{enumerate}
\onslide<4-5>
\begin{enumerate}[(a)]
\item[(b)] Gelte $\deg f_i\le1$ für alle $i\in\{1,\dots,s\}$. Dann gibt es eindeutig bestimmte
\[g_i=\sum_{j=1}^na_{ij}X_j+b_i\qquad(i\in\{1,\dots,s\},a_{ij},b_i\in K)\] derart, dass mit $A:=(a_{ij})_{1\le i\le s,1\le j\le n}$ die Matrix
$(A\ b)\in K^{s\times(n+1)}$ in reduzierter Stufenform ist und \[Kf_1+\ldots+Kf_s=Kg_1+\ldots+Kg_s.\]
\uncover<5->{
Ist $\le$ eine
Termordnung mit $X_1\ge X_2\ge\dots\ge X_n$, so ist im Fall $1\notin\{g_1,\dots,g_s\}$ die Menge $\{g_1,\dots,g_s\}\setminus\{0\}$ und sonst
$\{1\}$ eine reduzierte Gröbnerbasis von $I$. Dies sieht man mit dem Buchberger-Kriterium zusammen mit dem folgenden Lemma.}
\end{enumerate}
\end{overprint}
\end{frame}

\begin{frame}
\s{Lemma.} Seien $f,g\in K[\x]\setminus\{0\}$ derart, dass \s{kein $X_i$ gleichzeitig $\LM(f)$ und $\LM(g)$ teilt}. Dann
\a{$\spol(f,g)\underset{\{f,g\}}{\overset*\longrightarrow}0$}.\pause

\begin{proof} Schreibe \s{$f=\sum_{i=1}^ka_iu_i$} und \s{$g=\sum_{j=1}^\ell b_jv_j$} mit $k,\ell\in\N$, $a_i,b_j\in K^\times$ und $u_i,v_j\in[\x]$, wobei
$u_1>\ldots>u_k$ und $v_1>\ldots>v_\ell$ gelte.\pause\\
Nach Voraussetzung gilt \a{$\lcm(u_1,v_1)=u_1v_1$} und daher
\[\s{\spol(f,g)=b_1v_1f-a_1u_1g=\underbrace{b_1v_1\sum_{i=2}^ka_iu_i}_{=:p}-\underbrace{a_1u_1\sum_{j=2}^\ell b_jv_j}_{=:q}}.\pause\]
Es gilt \a{$M(p)\cap M(q)=\emptyset$}, denn sonst gäbe es $i\in\{2,\dots,k\}$ und $j\in\{2,\dots,\ell\}$ mit $v_1u_i=u_1v_j$ und es gälte
$\s{u_1v_1=\lcm(u_1,v_1)\a\mid v_1u_i}$ und damit $\s{u_1v_1\a\le v_1u_i\le v_1u_1=u_1v_1}$, was $u_1v_1=u_iv_1$ also $u_1=u_i$ implizierte
$\a\lightning$. \pause
\s{Jedes der $\ell-1$ Monome von $q$ ist also ein Monom von $\spol(f,g)$ und wird von $u_1=\LM(f)$ geteilt.} Wir addieren nun
nacheinander $b_\ell v_\ell f,b_{\ell-1}v_{\ell-1}f,\dots,b_2v_2f$ zu $\spol(f,g)$ und überlegen uns, dass dies jeweils ein Reduktionsschritt
modulo $f$ ist \a{[\dots]}
\end{proof}
\end{frame}
\end{document}