<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% -*- coding: utf-8 -*-
%!TEX encoding = UTF-8 Unicode
\documentclass{scrreprt}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\newif\ifbezwei
\bezweifalse % did not read B2 for these students
%\bezweitrue % did read B2 for these students

%\usepackage{lmodern}
\usepackage[sc]{mathpazo}

\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{hyperref}

\usepackage{calrsfs} % improve mathcal

% \usepackage{tikz-cd} % for commutative diagrams

\usepackage{stmaryrd} % for \mapsfrom or \lightning
\renewcommand{\i}{\overset\circ\imath} % the complex imaginary unit

\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{\&amp;}}
\newcommand\id{\text{id}}

\theoremstyle{plain}
\newtheorem{sat}{Satz}[section]
\newtheorem{satdef}[sat]{Satz und Definition}
\newtheorem{notsprpro}[sat]{Notation, Sprechweise und Proposition}
\newtheorem{lem}[sat]{Lemma}
\newtheorem{pro}[sat]{Proposition}
\newtheorem{nt}[sat]{Notation}
\newtheorem{notpro}[sat]{Notation und Proposition}
\newtheorem{kor}[sat]{Korollar}
\theoremstyle{definition}
\newtheorem{alg}[sat]{Algorithmus}
\newtheorem{df}[sat]{Definition}
\newtheorem{notation}[sat]{Notation}
\newtheorem{defprop}[sat]{Definition und Proposition}
\newtheorem{propdef}[sat]{Proposition und Definition}
\newtheorem{defex}[sat]{Definition und Ãœbung}
\theoremstyle{remark}
\newtheorem{eri}[sat]{Erinnerung}
\newtheorem{bem}[sat]{Bemerkung}
\newtheorem{bsp}[sat]{Beispiel}
\newtheorem{exo}[sat]{Ãœbung}
\newtheorem{mot}[sat]{Motivation}

\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}

%\usepackage{xcolor}
%\usepackage{datetime}
%\usepackage{xwatermark}
%\newwatermark[allpages,color=blue!50,angle=45,scale=0.8,coordunit=cm,xpos=-1,ypos=1]{unverifizierter Entwurf}
%\newwatermark[allpages,color=blue!50,angle=45,scale=1,xpos=0,ypos=0]{\today, \currenttime}
%\newwatermark[allpages,color=red!35,angle=45,scale=0.8,coordunit=cm,xpos=-1,ypos=1]{Entwurf}
%\newwatermark[allpages,color=red!35,angle=45,scale=1,xpos=0,ypos=0]{\today, \currenttime}

\begin{document}
\noindent
UniversitÃ¤t Konstanz\hfill Algorithmische Algebraische Geometrie\\
Fachbereich Mathematik und Statistik\hfill Wintersemester 2015/2016\\
Markus Schweighofer
\medskip
\hrule
\begin{center}
\section*{Â§2.6 Minimale und reduzierte GrÃ¶bnerbasen}
\setcounter{chapter}{2}
\setcounter{section}{6}
\end{center}
\hrule

\bigskip\noindent
In diesem Abschnitt sei stets $K$ ein KÃ¶rper. Ferner sei eine Monomordnung $\le$ auf $[\x]$ fixiert.

\bigskip
\begin{lem}\label{mono}
Sei $M\subseteq[\x]$ und $I:=(M)$. Dann ist die Menge \[M':=\{v\in M\mid\nexists u\in M:(u\ne v~\&amp;~u| v)\}\] der bezÃ¼glich der Teilerrelation
minimalen Elemente von $M$ das kleinste aus Monomen bestehende Erzeugendensystem von $I$, das heiÃŸt $I=(M')$ und fÃ¼r alle $M''\subseteq[\x]$ mit $I=(M'')$ gilt $M'\subseteq M''$. Insbesondere ist $M'$ endlich \emph{[$\to$2.1.9]}.
\end{lem}

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

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

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

\begin{lem} Sei $I\subseteq K[\x]$ ein monomiales Ideal \emph{[$\to$2.1.11]}. Dann besitzt $I$ genau ein aus Monomen bestehendes Erzeugendensystem $M$ derart, dass kein Element von $M$ ein anderes Element von $M$ teilt. Es ist $M$ endlich und das kleinste aus Monomen bestehende Erzeugendensystem von $I$. 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.
\end{lem}

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

\begin{df} Eine GrÃ¶bnerbasis $G\subseteq K[\x]$ heiÃŸt \emph{minimal}, wenn sie (bezÃ¼glich Inklusion) minimal unter allen GrÃ¶bnerbasen des von $G$ erzeugten Ideals ist.
\end{df}

\begin{pro}\label{minchar}
Sei $G\subseteq K[\x]\setminus\{0\}$ endlich und $I:=(G)$. Dann sind Ã¤quivalent:
\begin{enumerate}[(a)]
\item $G$ ist eine minimale GrÃ¶bnerbasis.
\item $G$ ist eine GrÃ¶bnerbasis derart, dass kein Leitmonom eines Elements von $G$ das Leitmonom eines anderen Elements von $G$ teilt.
\item Je zwei verschiedene Elemente von $G$ haben verschiedene Leitmonome und \[\{\LM(g)\mid g\in G\}\] ist das kleinste aus Monomen bestehende Erzeugendensystem von $L(I)$ \emph{[$\to$2.4.2(j)]}.
\end{enumerate}
\end{pro}

\begin{proof}
(a)$\implies$(b) und (c)$\implies$(a) folgen aus 2.4.7(g), (b)$\implies$(c) aus 2.6.2.
\end{proof}

\begin{sat}\label{mincomp}
Sei $I\subseteq K[\x]$ ein Ideal. Dann besitzt $I$ eine minimale GrÃ¶bnerbasis. Sind $G$ und $H$ zwei minimale GrÃ¶bnerbasen von $I$
(bezÃ¼glich derselben Monomordnung $\le$), so gilt $\#G=\#H=\#\{\LM(g)\mid g\in G\}$ und $\{\LM(g)\mid g\in G\}=\{\LM(h)\mid h\in H\}$.
\end{sat}

\begin{proof} Die zweite Aussage ist klar mit 2.6.4(c). Um die Existenz einer minimalen GrÃ¶bnerbasis von $I$ zu zeigen, wÃ¤hle man zunÃ¤chst
gemÃ¤ÃŸ Satz 2.4.8 eine beliebige GrÃ¶bnerbasis $G\subseteq K[\x]\setminus\{0\}$ von $I$. 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. Wegen $(\{\LM(h)\mid h\in H\})=(\{\LM(g)\mid g\in G\})=L(I)$ ist mit 2.4.7(g) auch $H$ eine GrÃ¶bnerbasis von $I$. Nach
\ref{minchar} ist $H$ eine minimale GrÃ¶bnerbasis.
\end{proof}

\begin{bem} Es ist klar, wie man zu einer gegebenen endlichen Menge $F\subseteq K[\x]$ eine minimale GrÃ¶bnerbasis $H$ von $(F)$ berechnet: Berechne mit dem Buchberger-Algorithmus 2.5.6 eine GrÃ¶bnerbasis $G$ von $(F)$ und verkleinere $G$ zu $H$ wie im Beweis von Satz \ref{mincomp}.
\end{bem}

\begin{df}
\begin{enumerate}[(a)]
\item Ein Polynom $f\in K[\x]$ heiÃŸt \emph{normiert} (bezÃ¼glich $\le$), wenn $f\ne0$ und $\LC(f)=1$.
\item Eine Menge $F\subseteq K[\x]$ heiÃŸt \emph{normiert} (bezÃ¼glich $\le$), wenn jedes ihrer Elemente normiert ist.
\item Eine Menge $F\subseteq K[\x]$ heiÃŸt \emph{reduziert} (bezÃ¼glich $\le$), wenn $F$ normiert ist und jedes $f\in F$ reduziert modulo
$F\setminus\{f\}$ ist [$\to$2.4.1(b)].
\end{enumerate}
\end{df}

\begin{pro}\label{redmin}
Jede reduzierte GrÃ¶bnerbasis ist minimal.
\end{pro}

\begin{proof} Sei $G\subseteq K[\x]$ eine reduzierte GrÃ¶bnerbasis. Dann gilt $G\subseteq K[\x]\setminus\{0\}$ und \ref{minchar}(b) ist erfÃ¼llt.
\end{proof}

\begin{sat} Jedes Ideal von $K[\x]$ besitzt eine eindeutig bestimmte reduzierte GrÃ¶bnerbasis.
\end{sat}

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

\underline{Eindeutigkeit} Seien $G$ und $H$ reduzierte GrÃ¶bnerbasen von $I$. Da $G$ und $H$ nach \ref{redmin} minimal sind, gilt nach
\ref{mincomp} $\#G=\#H=\#\{\LM(g)\mid g\in G\}$ und \[(*)\qquad\{\LM(g)\mid g\in G\}=\{\LM(h)\mid h\in H\}.\] Sei $g\in G$. Es reicht $g\in H$ zu zeigen.
WÃ¤hle $h\in H$ mit $u:=\LM(g)=\LM(h)$. Wir behaupten $g=h$. Wegen $(*)$ gilt offenbar
(zum Beispiel mit 2.4.11) $\red(G)=\red(H)$ [$\to$2.4.1(b)]. Wegen $g\in\red(G\setminus\{g\})$ gilt $M(g)\setminus\{u\}\subseteq\red(G)$.
Analog $M(h)\setminus\{u\}\subseteq\red(H)$. Da $g$ und $h$ normiert sind, haben wir $M(g-h)\subseteq(M(g)\cup M(h))\setminus\{u\}
\subseteq\red(G)=\red(H)$ und daher $g-h\in\red(G)$. Andererseits $g-h\in I$ und daher $g-h\underset G{\overset*\longrightarrow}0$. Es folgt
$g-h=0$, also $g=h\in H$.

\underline{Existenz} WÃ¤hle mit \ref{mincomp} eine minimale GrÃ¶bnerbasis $G$ von $I$. WÃ¤hle zu jedem $g\in G$ ein $g'\in\red(G\setminus\{g\})$ mit $g\underset{G\setminus\{g\}}{\overset*\longrightarrow}g'$. Wegen der MinimalitÃ¤t von $G$ gilt $\LM(g')=\LM(g)$ fÃ¼r alle
$g\in G$ [$\to$\ref{minchar}(b)]. Nach 2.4.7(g) ist mit $G$ auch $H:=\{g'\mid g\in G\}$ eine GrÃ¶bnerbasis von $I$. Wieder mit 2.4.11 sieht man
$\red(G\setminus\{g\})=\red(H\setminus\{g'\})$ fÃ¼r alle $g\in G$. Somit $g'\in\red(H\setminus\{g'\})$ fÃ¼r alle $g\in G$, das heiÃŸt $H$ ist reduziert.
\end{proof}

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

\begin{proof} \underline{Terminierung} Angenommen der Algorithmus terminiert nicht. WÃ¤hle dann $s\in\N$ und
$g_1^{(0)},\dots,g_s^{(0)}\in K[\x]$ mit $F=\{g_1^{(0)},\dots,g_s^{(0)}\}$. Dann gilt zu Beginn des ersten Schleifendurchlaufs
$G=\{g_1^{(0)},\dots,g_s^{(0)}\}$. Wir nehmen an zu Beginn des $i$-ten Schleifendurchlaufs ($i\in\N$) gelte $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]$. Sind $g$ und $h$ wie in diesem Durchlauf gewÃ¤hlt, dann definieren wir
$g_1^{(i)},\dots,g_s^{(i)}\in K[\x]$ durch
\[g_j^{(i)}:=\begin{cases}g_j^{(i-1)}&amp;\text{falls }g_j^{(i-1)}\ne g\\h&amp;\text{falls }g_j^{(i-1)}=g\end{cases}\qquad(j\in\{1,\dots,s\}).\]
Auf diese Weise stellen wir sicher, dass zu Ende des $i$-ten Schleifendurchlaufs gilt $G=\{g_1^{(i)},\dots,g_s^{(i)}\}$ und
\[(*)\qquad(M(g_1^{(i-1)}),\dots,M(g_s^{(i-1)}))\succ(M(g_1^{(i)}),\dots,M(g_s^{(i)})),\] wobei $\preceq$ die Halbordnung auf
$(\mathcal P_{\text{fin}}([\x]))^s$ [$\to$2.1.20] ist, die definiert ist durch
\[(U_1,\dots,U_s)\preceq(V_1,\dots,V_s)\iff\forall i\in\{1,\dots,s\}:U_i\le'V_i\]
und $\le'$ die in 2.1.21 definierte Wohlordnung auf $\mathcal P_{\text{fin}}([\x])$ ist (siehe Beweis von 2.1.24). Dass mit $&gt;'$ auch $\succ$
noethersch ist, ist ein Widerspruch dazu, dass wir rekursiv eine Folge $(g_1^{(i)},\dots,g_s^{(i)})_{i\in\N_0}$ erhalten
mit $(*)$ fÃ¼r $i\in\N$. $\lightning$

\bigskip\noindent
\underline{Korrektheit} Folgende Aussagen sind Schleifeninvarianten, das heiÃŸt sie gelten am Ende eines Schleifendurchlaufs, sofern sie
am Anfang desselben Durchlaufs gegolten haben:
\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) sei nun $F$ eine GrÃ¶bnerbasis. Dann reicht es gemÃ¤ÃŸ 2.4.2(j) zu zeigen, dass \[(**)\qquad L(I)=(\{\LM(f)\mid f\in G\setminus\{0\}\})\] mit $I:=(F)$
eine Schleifeninvariante ist. Sei also $G\subseteq K[\x]$ mit $(G)=I$ und $(**)$ und seien
$g\in G$ und $h\in K[\x]$ mit $g\underset{G\setminus\{g\}}\longrightarrow h$. Wir zeigen
\[L(I)=(\{\LM(f)\mid f\in((G\setminus\{g\})\cup\{h\})\setminus\{0\}\})=:J.\] Falls $h\ne0$ und $\LM(g)=\LM(h)$, so ist dies wegen $(**)$ trivial.
Andernfalls haben wir $g\underset{G\setminus\{g\}}\longrightarrow h\  [\LM(g)]$, weswegen
\[\LM(g)\in(\{\LM(f)\mid f\in(G\setminus\{g\})\setminus\{0\}\})=:L\] und daher $L(I)\overset{(**)}\subseteq L\subseteq J\overset{G\cup\{h\}\subseteq I}\subseteq L(I)$, also insbesondere $L(I)=J$.
\end{proof}

\begin{bem} Wie versprochen sehen wir jetzt, dass GrÃ¶bnerbasen gleichzeitig den euklidischen Algorithmus fÃ¼r Polynome in einer Variablen
[$\to$2.1.1(a)] als auch den GauÃŸ-Algorithmus fÃ¼r lineare Polynome [$\to$2.1.1(b)] verallgemeinern: Seien nÃ¤mlich $f_1,\dots,f_s\in K[\x]$
und $I:=(f_1,\dots,f_s)$.
\begin{enumerate}[(a)]
\item Gelte $n=1$, also $\x=X$. Dann gibt es genau ein $g\in K[\x]$ mit $I=(g)$ und $g$ normiert oder $g=0$\ifbezwei [$\to$LA Â§10.2]\fi. Dann
ist $\{g\}\setminus\{0\}$ die eindeutig bestimmte reduzierte GrÃ¶bnerbasis von $I$.
\item 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}$ und \[b:=\begin{pmatrix}b_1\\\vdots\\b_s\end{pmatrix}\] 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\] [$\to$LA Â§5.1, Â§5.3]. 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 2.5.4 zusammen mit dem folgenden Lemma.
\end{enumerate}
\end{bem}

\begin{lem}
Seien $f,g\in K[\x]\setminus\{0\}$ derart, dass kein $X_i$ gleichzeitig $\LM(f)$ und $\LM(g)$ teilt (man sagt, "`f und g haben disjunkte Leitterme"'). Dann $\spol(f,g)\underset{\{f,g\}}{\overset*\longrightarrow}0$.
\end{lem}

\begin{proof} Schreibe $f=\sum_{i=1}^ka_iu_i$ und $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&gt;\ldots&gt;u_k$ und $v_1&gt;\ldots&gt;v_\ell$ gelte. Nach Voraussetzung gilt $\lcm(u_1,v_1)=u_1v_1$ und daher nach 2.5.3
\[\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}.\]
Es gilt $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
$u_1v_1=\lcm(u_1,v_1)\mid v_1u_i$ und damit $u_1v_1\le v_1u_i\le v_1u_1=u_1v_1$, was $u_1v_1=u_iv_1$ also $u_1=u_i$ implizierte
$\lightning$. 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: In der Tat, hat man schon $b_\ell v_\ell f+\ldots+b_jv_jf$ ($2&lt;j\le\ell$) addiert, so sind die Monome $v_{j-1}u_1,\dots,v_2u_1$
immer noch vorhanden, denn jedes von ihnen ist echt grÃ¶ÃŸer als jedes Monom von $b_\ell v_\ell f+\dots+b_jv_jf$. Daher
\begin{align*}
\spol(f,g)\underset f{\overset{\ell-1}\longrightarrow}p+\left(\sum_{i=2}^ka_iu_i\right)\sum_{j=2}^\ell b_jv_j
&amp;=\left(\sum_{i=2}^ka_iu_i\right)\left(b_1v_1+\sum_{j=2}^\ell b_jv_j\right)\\
&amp;=\left(\sum_{i=2}^ka_iu_i\right)g\underset g{\overset{k-1}\longrightarrow}0.
\end{align*}
\end{proof}

\end{document}</pre></body></html>