\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath}
\usepackage[dvips]{graphicx}
\usepackage[dvips]{color}

 \theoremstyle{plain}
 \newtheorem{thm}{Theorem}[section]
 \theoremstyle{plain}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Definition}
 \theoremstyle{plain}
 \newtheorem*{thm*}{Theorem}
 \theoremstyle{remark}
 \newtheorem*{rem*}{Remark}
 \theoremstyle{plain}
 \newtheorem*{lem*}{Lemma}
 \theoremstyle{plain}
 \newtheorem*{prop*}{Proposition}
 \theoremstyle{remark}
 \newtheorem*{claim*}{Claim}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

\lecture{18}{November 14, 2005}{Madhu Sudan}{Alexey Spiridonov}

\section{Today}

\begin{itemize}
\item We cover Gr\"{o}bner basis recognition, generation, and the resulting
algorithm for ideal membership.
\item We won't produce any complexity estimates this lecture, but only a
finite time decision procedure for testing membership in ideals.
\end{itemize}

\section{Notation and Definitions}

Some of these overlap with the previous lecture, but I repeat them
here for the sake of completeness.

\begin{description}
\item [Ambient~polynomial~ring]We'll take $k$ to be an algebraically
closed field, and take all our polynomials in $k[x_{1},\dots,x_{n}]$.
\item [Monomial~ordering]A total ordering $\ge$ on monomials $x^{\alpha}=x_{1}^{\alpha_{1}}\dots x_{n}^{\alpha_{n}}$
satisfying

\begin{enumerate}
\item $x^{\alpha}\ge1$ for al
\item $x^{\alpha}\ge x^{\beta}\Rightarrow x^{\alpha+\gamma}\ge x^{\beta+\gamma}$
\end{enumerate}
For our purposes the lexicographic ordering will suffice (but there
are many other useful ones). We compare $x^{\alpha}$ and $x^{\beta}$
thus: if the first $k$ indices agree: $\alpha_{i}=\beta_{i},i\le k$
and the $k$th differ, we decide based on that index $\alpha_{i}\le\beta_{i}\Rightarrow\alpha\le\beta$,
and the reverse.

\item [Leading~monomial]Denoted $LM(f)$, this is the greatest monomial
of $f\in k[x_{1},\dots,x_{n}]$ according to our chosen ordering.
\item [Leading~coefficient]The coefficient in front of $LM(f)$, denoted
$LC(f)$.
\item [Leading~term]$LT(f)=LC(f)LM(f).$
\end{description}

\section{Ideal Membership Problem}

Given an ideal $J=(f_{1},f_{2},\dots,f_{m})$ and a polynomial $f_{0}$
in the ring, we would like to decide whether $f\in J$. The idea is
simple: $f_{0}$ is in $J$ if and only if it can be written $\sum p_{i}f_{i}$.
If we {}``divide'' the latter by representation by $f_{i}$ and
take the remainder, we eliminate the term containing $f_{i}$; dividing
out by all $f_{i}$ we ought to get $0$, if and only if $f_{0}\in J$.
However, generically, division is poorly defined: remainders depend
on the order of the division, choice of basis. Ideally, we'd like
to divide by the entire (infinite) ideal $J$; that's impractical,
but last time we saw that dividing by a Gr\"{o}bner basis is well-behaved.

So, here's an outline of our algorithm:

\begin{enumerate}
\item Fix a monomial ordering (say, lexicographic).
\item Find a Gr\"{o}bner basis $g_{1},\dots,g_{t}$ for $J$. (\emph{a priori},
it's not clear that a finite one exists given our starting basis $f_{1},\dots f_{m}$).
Dividing by this basis in order is a well-behaved operation.
\item Divide $f_{0}$ by $g_{1},\dots,g_{t}$.
\item If the remainder is $0$ then $f_{0}\in J$, else $f_{0}\in J$.
\end{enumerate}

\section{Gr\"{o}bner Bases}

\begin{defn*}
A \emph{Gr\"{o}bner basis (GB)} is a set of polynomials $g_{1},\dots,g_{t}\in k[x_{1},\dots,x_{n}]$
satisfying the following properties: (we give two version of property
\ref{prop1} -- \ref{prop1old} from the previous lecture, and \ref{prop1new}
which we will show is equivalent)
\end{defn*}
\begin{enumerate}
\item \label{prop1}$g_{1},\dots,g_{t}\in J$ (last time: generate $J$;
we'll see these are equivalent)

\begin{enumerate}
\item \label{prop1old}Old variant: $g_{1},\dots,g_{t}$ generate $J$
\item \label{prop1new}New variant: $g_{1},\dots,g_{t}\in J$
\end{enumerate}
\item \label{prop2}$I(LT(g_{1}),\dots,LT(g_{t}))=I(LT(J))$, where $LT(J)$
is the set of leading terms of $J$. (Note that it's also an ideal.)
\end{enumerate}
So, we need a set of monomials generating the monomial ideal $I(LT(J))$.
The set of generators $LT(J)$ is infinite, so we'd better make sure
that we can actually produce a finite GB for this ideal. That's the
subject of the next section.

In the process, we will also see that \ref{prop1new} implies that
$g_{1},\dots,g_{t}$ generate $J$.


\section{Hilbert Basis Theorem}

\begin{thm*}
[Hilbert Basis Theorem] Every ideal in $k[x_{1},\dots,x_{n}]$ has
a finite basis.
\end{thm*}
\begin{rem*}
Though we assumed at the start of the lecture that $k$ is a field,
this theorem holds for $k$ any N\"{o}therian ring (ring in which every
ideal is finitely generated).
\end{rem*}
The proof follows easily from the following lemma.

\begin{lem*}
[Dickson's Lemma] Every monomial ideal $J$ in $K[x_{1},\dots,x_{n}]$
has a finite basis.
\end{lem*}
\begin{proof}
We will work by induction on $n$, the number of variables.

The case $n=1$ is trivial. If our ideal is generated by $\{ x^{i_{1}},x^{i_{2}},\dots,x^{i_{n}},\dots\}$,
it is also generated by $x^{i_{0}}$, with $i_{0}=\min\{ i_{1},\dots,i_{n}\}$.

%
\begin{figure}
\begin{center} \input{dicksons_lemma.pstex_t} \end{center}


\caption{\label{dickson}The two-variable case of Dickson's Lemma.}
\end{figure}


For two variables, $J=\{ x^{i_{1}}y^{j_{1}},x^{i_{2}}y^{j_{2}},\dots\}$,
we can draw a picture; see Figure \ref{dickson}. It depicts all monomials
on an integer grid (e.g. $x^{5}y^{2}$ is at $(5,2)$). Pick a monomial
$x^{i}y^{j}$ from the generating set such that $i+j$ is minimal.
Then, it generates all monomials in the dashed region in the figure.
That leaves a vertical strip $i$ wide and a horizontal strip $j$
wide. There's room only for $i+j$ more generating monomials in those
strips, so the ideal has at most $i+j+1$ generators.

In more variables, the bounds stop having a nice form and we can't
draw pictures any more. So, we'll settle for arguing, in the same
vein, that the generating set is finite.

Suppose that all $n-1$-variable ideals are finitely generated. Consider
an $n$-variable ideal $J$. Now, take $x^{\alpha}=x_{1}^{\alpha_{1}}\dots x_{n}^{\alpha_{n}}\in LT(J)$.
For an index $i$ and a degree $\beta$, define
$$
J_{(i,\beta)}=\{ x_{1}^{\gamma_{1}}x_{2}^{\gamma_{2}}\dots x_{i-1}^{\gamma_{i-1}}x_{i+1}^{\gamma_{i+1}}\dots x_{n}^{\gamma_{n}}\text{ such that }x_{1}^{\gamma_{1}}x_{2}^{\gamma_{2}}\dots x_{i-1}^{\gamma_{i-1}}x_{i}^{\beta}x_{i+1}^{\gamma_{i+1}}\dots x_{n}^{\gamma_{n}}\}.
$$
 Now, $J_{(i,\beta)}$ is a set of monomials in $n-1$ variables,
so the corresponding ideal is finitely generated. Let $C$ be the
union of all sets of generators of $J_{(i,\beta)}$ for $i=1\dots n,\beta=0\dots\alpha_{i}-1$.
Then, we claim that $C\cup\{\alpha\}$ generates $J$. Indeed, take
a monomial $x^{\delta}$ in $J$; if all $\delta_{i}\ge\alpha_{i}$,
then $x^{\alpha}$ is a generator. Otherwise, there's some $i$ such
that $\delta_{i}<\alpha_{i}$, and in that case $x^{\delta}\in J_{i,\delta_{i}}$.
That finishes the proof of the lemma.
\end{proof}
That doesn't give any nice complexity bound on the size of the generating
set. We will not show this, but the complexity of the resulting ideal
membership algorithm is very bad (EXPSPACE).

Now, we use Dickson's lemma to prove Hilbert's Basis Theorem. Actually,
we will prove more:

\begin{thm}
Every polynomial ideal has a finite Gr\"{o}bner basis.
\end{thm}
\begin{proof}
The idea of the proof is: we will pick out some polynomials from the
ideal $J$, such that $\{ LT(g_{i})\}$ generate $LT(J)$. This requires
this lemma we promised we'd prove:
\begin{lem*}
In the definition of the Gr\"{o}bner basis, $g_{1},\dots,g_{t}\in J\Rightarrow(g_{1},\dots,g_{t})=J$
(assuming part $2$ of the definition).
\end{lem*}
\begin{proof}
We will prove this by contradiction. Take $g_{1},\dots,g_{t}$ as
in the statement of the theorem.

Last lecture we proved the following helpful fact: if we have polynomials
$g_{1},\dots,g_{t}$ satisfying \ref{prop1old} and \ref{prop2},
it follows we can canonically divide by these polynomials. As discussed
before, this is an ideal membership test: if a polynomial $f$ is
in $I(g_{1},\dots,g_{t})$, the division returns $0$, otherwise a
nonzero remainder.

Suppose $\exists f\in J$ such that $f\notin I(g_{1},\dots,g_{t})$.
Let's compute the remainder after dividing $f$ by $g_{1},\dots,g_{t}$;
we get $f=r+\sum g_{i}q_{i}$. Moreover (again from last lecture),
no monomial of $r$ is divisible by $LT(g_{i})$, for any $i$. Now,
consider $LT(r)$; since $r\in J$, we get $LT(r)\in LT(J)$, so $LT(r)=I(LT(g_{1}),\dots,LT(g_{t}))=LT(J)$,
so there exists $i$ such that $LT(g_{i})|LT(r)$. Contradiction.
\end{proof}
So, we saw that \ref{prop1new} implies \ref{prop1old}.

Now, consider $LT(J)$; by the lemma, this is generated by a finite
set $g_{1}',g_{2}',\dots,g_{t}'$. By definition of $LT(J)$, every
$g_{i}'$ was obtained from $J$ by taking the leading term of some
$g_{i}\in J$. Look at the set $g_{1},\dots,g_{t}$; by the lemma,
this Gr\"{o}bner basis generates $J$, and so we are done.
\end{proof}
Next, we will see that a Gr\"{o}bner basis is \emph{essentially} unique.
There are two obvious problems that get in the way of uniqueness.
First, a GB plus arbitrary element is still a GB, so we need the following
condition.

\begin{defn*}
$(g_{1},\dots,g_{t})$ is a \emph{minimal} Gr\"{o}bner basis for $J=I(g_{1},\dots,g_{t})$
if for all $i$,
$$LT(g_{i})\notin I(LT(g_{1}),\dots,LT(g_{i-1}),LT(g_{i+1}),\dots,LT(g_{t})).$$
\end{defn*}
So, in our quest for a unique GB, we will drop elements $g_{i}$ such
that \[
LT(g_{i})\in I(LT(g_{1}),\dots,LT(g_{i-1}),LT(g_{i+1}),\dots,LT(g_{t})),\]
 one-by-one, until our GB becomes minimal.

Is the resulting basis unique? No. For instance, $\{ x,y\}$ and $\{ x,x+y\}$
are minimal bases for the same ideal. The second one obviously looks
{}``worse'' than the first. The following definition makes the meaning
clear.

\begin{defn*}
A minimal GB $(g_{1},\dots,g_{t})$ is \emph{reduced} if \[
g_{i}=Rem(g_{i};g_{1},\dots,g_{i-1},g_{i+1},\dots,g_{t})\]
 for all $i$.
\end{defn*}
We leave it as an exercise to show that if we have two minimal GB
for $J$: $(g_{1},\dots,g_{t})$ and $(g'_{1},\dots,g_{t'}')$, then
\[
\{ LT(g_{1}),\dots,LT(g_{t})\}=\{ LT(g'_{1}),\dots,LT(g'_{t})\}\]
 This implies that $t'=t$. To make a reduced basis, we take a minimal basis, and for
every $g_{i}$ replace it by $$Rem(g_{i};g_{1},\dots,g_{i-1},g_{i+1},\dots,g_{t}).$$
It's not difficult to check that this procedure does not alter the
leading terms, and so the result is a Gr\"{o}bner basis. It also follows
that a reduced GB is unique; take two bases $g_{i}$ and $g_{i}'$,
and arrange the indices so that leading terms are pairwise equal.
Then, for some $j$, $g_{j}\ne g_{j}'\Rightarrow g_{j}-g_{j}'\in J$.
But, the bases are reduced means that $LT(g_{i})\not|LT(g_{j}-g_{j}')\forall i$,
and hence $LT(g_{j}-g_{j}')\notin I(LT(J))$, which contradicts $g_{i}$
being a Gr\"{o}bner basis.

\begin{rem*}
The notion of a reduced GB is somewhat parallel to the notion of a
strong generating set from earlier in the course.
\end{rem*}

\section{Recognizing Gr\"{o}bner Bases}

The above proof is almost, but not quite constructive: we didn't specify
how to construct a finite monomial basis (although that's not difficult),
and it isn't immediately obvious how to get an inverse image in $J$
of a given monomial.

However, we will get an actual algorithm for constructing a GB by
answering the question: how do we recognize whether a given basis
is a GB?

We'll start by making division by a Gr\"{o}bner basis even more canonical:
we already know that the remainder is unique, but we'd like to also
regularize the quotients. To do this, we will consider $Rem(f_{0};g_{1},\dots,g_{t})$
with $g_{1},\dots,g_{t}$ an ordered sequence. The procedure is: take
the smallest $i$ such that $LT(g_{i})$ divides the largest (in our
monomial ordering) monomial of $f$. That yields $f=f'+m_{1}g_{1}$
with $m_{1}$ a monomial. Then, we iterate, each time taking the smallest
$i$ so that $LT(g_{i})$ divides the largest monomial of $f^{(j)}$.
Once there is no such $i$, we are left with the usual remainder $r$,
and $m_{i}$ monomials such that: \[
f=r+\sum m_{i}g_{i}.\]
 However, the pieces of the quotient are special in that they are
{}``reduced'' -- $m_{i}g_{i}\ne q_{j}g_{j}+\dots$ with $j<i$ and
{}``$\dots$'' denoting a remainder with smaller leading monomials.
This regularized division will be used in a proof shortly.

Next, we need a special polynomial called the \emph{syzygy} of $f$
and $g$. It's a special polynomial in $I(f,g)$ of the form:\[
S(f,g)=f\cdot X-g\cdot Y\]
 with $X$ and $Y$ chosen so that the leading terms of the two pieces
are equal. We can write it explicitly:\[
S(f,g)=\frac{LC(g)LCM(LM(f),LM(g))}{LM(f)}\cdot f-\frac{LC(f)LCM(LM(f),LM(g))}{LM(g)}\cdot g.\]
 The key claim now is:

\begin{prop*}
The polynomials $g_{1},\dots,g_{t}$ form a Gr\"{o}bner basis iff $\forall i,j$,
\[
Rem(S(g_{i},g_{j});g_{1},\dots,g_{t})=0.\]

\end{prop*}
Once we prove the proposition, constructing a Gr\"{o}bner basis is straightforward.
Start with some basis $g_{1},\dots,g_{t}$; if there are $i,j$ such
that $Rem(S(g_{i},g_{j});g_{1},\dots,g_{t})\ne0$, add this remainder
to the basis. Any such remainder $r$ has to be such that $LM(r)$
isn't generated by the $LM(g_{i})$, so the monomial ideal $I(\{ LM(g_{i})\})$
gets bigger with every step. But, we have seen that any monomial ideal
is finitely generated, so this algorithm must terminate. Thus, proving
the proposition will give us a finite-time decision procedure for
finding a Gr\"{o}bner basis, and by proxy, a finite-time ideal membership
procedure.

The proof of the proposition follows from

\begin{claim*}
If $\forall i,j$, $Rem(S(g_{i},g_{j});g_{1},\dots,g_{t})=0$, then
$\{ LM(g_{i})\}$ generate $LM(J)$.
\end{claim*}
The proof of this claim was left to the next lecture.

\end{document}