\documentclass[runningheads, 11pt]{article}
\usepackage{graphicx,verbatim,xspace,color}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{fullpage}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}



\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[6]{
  \renewcommand{\thepage}{\arabic{page}}
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { \textbf{#2} \hfill #3 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #6  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { \textit{Instructor: #4 \hfill #5} }
    }
  }
  \end{center}
  \vspace*{4mm}
}
%
%\newenvironment{proof}{\noindent{\bf Proof:} \hspace*{1mm}}{
%	\hspace*{\fill} $\Box$ }
%\newenvironment{proof_of}[1]{\noindent {\bf Proof of #1:}
%	\hspace*{1mm}}{\hspace*{\fill} $\Box$ }
%\newenvironment{proof_claim}{\begin{quotation} \noindent}{
%	\hspace*{\fill} $\diamond$ \end{quotation}}

\newcommand{\lecturenotes}[4]{\heading{#1}{6.S897 Algebra and Computation}{#2}{Madhu Sudan}{Scribe: #3}{#4}}

\newcommand{\lecturenum}{15}          % lecture number
\newcommand{\lecturetitle}{Ideal Membership Problem} % topic of lecture
\newcommand{\lecturedate}{April 4, 2012}  % date of lecture
\newcommand{\studentname}{Michael Forbes}    % full name of student (i.e., you)



\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\DeclareMathOperator{\mdeg}{mdeg}
\newcommand{\from}{\leftarrow}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%555
\begin{document}
\lecturenotes{\lecturenum}{\lecturedate}{\studentname}{\lecturetitle}

\section{Overview}

Today we will discuss an algorithm for solving the ideal membership problem: the method of Gr\"{o}bner bases.  In particular, we will define this notion, show how constructing such objects solves the ideal membership question, and then give the construction.  There is also a notion of uniqueness, which we may cover in future lectures.

\section{Ideal Membership Problem}

The Ideal Membership Problem is as follows: given $f_0,f_1,\ldots,f_m\in\K[x_1,\ldots,x_n]$, is $f_0\in\la f_1,\ldots,f_m\ra$, where $\la f_1,\ldots,f_m\ra$ denotes the ideal generated by the $f_i$?  An equivalent formulation is: are there $q_1,\ldots,q_m\in\K[x_1,\ldots,x_n]$ such that $f_0=\sum_{i=1}^mq_if_i$?  We will solve this question by using Gr\"{o}bner bases.  That is, a  Gr\"{o}bner basis is a ``nice'' representation of an ideal, that allows us to easily decide membership.  The difficult part of the analysis is to construct  Gr\"{o}bner bases, and we will do so using Buchberger's algorithm (Buchberger's work essentially started the field of  Gr\"{o}bner bases, and he named the notion after his advisor, Gr\"{o}bner).  The  Gr\"{o}bner basis technique has turned out to be fairly successful in practice, although its theoretical guarantees are quite weak (and provably so).  However, it is still a nice theory, and in particular unifies two otherwise disparate topics: solving linear systems of equations, and computing greatest common divisors of univariate polynomials.  We now discuss these two relations.

Suppose the polynomials $f_i$ are all linear with no constant term, and we still want to solve the ideal membership question.  One can then show that it is enough to assume the $q_i$ are in fact constants from the field $\K$, instead of general polynomials in $\K[x_1,\ldots,x_n]$.  Thus, in this case the ideal membership question is just that of solving a linear system, which can be solved by Gaussian elimination.  In this case, the notion of a Gr\"{o}bner basis in fact reduces to the notion of row-reduced echelon form.  Further, recall that solving a linear system is quite easy given the row-reduced echelon form.  Constructing the echelon form can be done via Gaussian Elimination, which is comparably more expensive.  The same notions will be true of Gr\"{o}bner bases.

In another simple case of ideal membership, suppose we have all univariate polynomials, so $n=1$.  In this case, we can recall that $\la f_1,\ldots,f_m\ra=\la \gcd(f_1,\ldots,f_m)\ra$.  So to test if $f_0\in\la f_1,\ldots,f_m\ra$, it suffices to test if $\gcd(f_1,\ldots,f_m)$ divides $f_0$. Constructing this gcd seems the comparably more expensive part of this test, and once given the gcd the division is quite quick.

Now that we have discussed two subcases of this question, let us consider the entire ideal membership question.  The starting point is that given $f_0$, we want to compute its ``remainder'' modulo the $f_i$.  This requires some notion of division for multivariate polynomials.  This notion can be described as follows.  We first order the monomials in $\K[x_1,\ldots,x_n]$ by some total order (called an \textit{admissible order}) $<$ such that
\begin{itemize}
	\item $\vec{x}^{\vec{a}}<\vec{x}^{\vec{b}}\implies\vec{x}^{\vec{a}+\vec{d}}<\vec{x}^{\vec{b}+\vec{d}}$
	\item $1\le \vec{x}^{\vec{a}}$
\end{itemize}
This naturally generalizes the ordering on univariate monomials, where we order by degree, and on linear forms, where we pick some ordering on the variables such as $x_1>x_2>\ldots>x_n$, which corresponds to some ordering on the columns in the matrix when performing Gaussian Elimination.  Once given this ordering, we do the same thing in univariate division (and Gaussian Elimination): given polynomials $f$ and $g$, we can reduce $f$ by $g$ be scaling $g$ to cancel out the ``largest'' part of $f$.  Specifically, recall the notion of a \textit{leading term} of a polynomial $f$, denoted $LT(f)$, which is the monomial (along with its coefficient) of $f$ which is largest according to the ordering $<$.  So if $LT(g)$ divides $LT(f)$, then we can perform the reduction $f\mapsto f-g\cdot LT(f)/LT(g)$.  By using the first property of our admissible ordering, we see that the result has strictly decreased the leading term (with respect to the leading term).

Let's consider an example.  Suppose $f_1=x^d+g_1$, $f_2=x^{d-1}+g_2$.  Then we can take $f_1$ and reduce it with $f_2$ to get $f_1-xf_x=g_1-xg_2$, which is ``smaller''.  One would hope that to determine if $f\in\la g_1,\ldots,g_t\ra$ we could perform this reduction step over and over. However, one difficulty in the above reduction step of $f$ by polynomials $g_1,\ldots,g_t$ is that it might be that $LT(g_i)$ fails to divide $LT(f)$ for all $i$, but that $f\in\la g_1,\ldots,g_t\ra$.Note that this can even happen in univariate polynomials, as the $g_i$ might have large degree while $f$ might have small degree.  Thus, we must do some work to ensure that for any $f\in\la g_1,\ldots,g_t\ra$ there is some $i$ such that $LT(g_i)$ divides $LT(f)$.  We can do this by enlarging the set of $g_i$.  Once we have done so, we have a Gr\"{o}bner basis.

\begin{definition}
	$\la g_1,\ldots,g_t\la$ is a \textbf{Gr\"{o}bner basis} for the ideal $J:=\la f_1,\ldots,f_m\ra$ if: $g_1,\ldots,g_t\in J$, and $\la LT(g_1),\ldots,LT(g_t)\ra=\la LT(J)\ra$.
\end{definition}

This second condition means that if we take the ideal generated by the leading terms of all of the polynomials in $J$, then this ideal is also generated by the leading terms of the $g_i$ alone.  Such an ideal generated by monomials is called a \textit{monomial ideal}.  They have a special structure, and in particular the following, easily proven, fact holds.  Given a monomial $\vec{x}^{\vec{a}}$ in a monomial ideal generated by $\{\vec{x}^{\vec{b}}\}_{\vec{b}\in S}$, where $S$ is possibly infinite, it must be that there is some $\vec{b}\in S$ such that $\vec{x}^{\vec{b}}$ divides $\vec{x}^{\vec{a}}$. Thus, these conditions imply that our above reduction step $f\mapsto f-g\cdot LT(f)/LT(g)$ can always make progress when working on a Gr\"{o}bner basis, as there will always some $g$ so that $LT(g)$ divides $LT(f)$.  We will show shortly that these conditions on the Gr\"{o}bner basis also imply that the $g_i$ also generate $J$.

\section{Membership Testing}

We now put some of the above ideals on a more firm basis.  We start with the question: do Gr\"{o}bner bases exist at all?  To show this, we start with the so-called \textit{Hilbert's Basis Theorem}, which states that any ideal in $\K[x_1,\ldots,x_n]$ is finitely generated.  To see that this implies that Gr\"{o}bner bases exist, observe that for an ideal $J=\la f_1,\ldots,f_m\ra$ if we take a finite set of generates for $\la LT(J)\ra$, we get that $\la LT(J)\ra=\la LT(g_1),\ldots,LT(g_t)\ra$ for $g_i\in J$, which gives us the Gr\"{o}bner basis.  We will sketch a special case of Hilbert's Basis theorem, called Dickson's lemma, which proves that monomial ideals are finitely generated. This is sufficient for our purposes as the ideals we consider, $\la LT(J)\ra$, are monomial ideals.

\begin{lemma}[Dickson's Lemma]
	Let $J\subseteq \K[x_1,\ldots,x_n]$ be a monomial ideal, that is, an ideal generated be a (possibly infinite) set of monomials.  Then $J$ is finitely generated, by a finite set of monomials.
\end{lemma}
\begin{proof}[Proof Sketch]
	The proof is by induction on the number of variables.  We will sketch how the proof goes for $n=2$.  Consider an ideal $J$, with monomial $x^iy^j$.  Now observe that if we have another monomial $x^ky^l$ which is a multiple $x^iy^j$, then the monomial $x^ky^l$ is ``covered'' by $x^iy^j$.  In particular, in the set of monomial generators for $J$, we can discard any such $x^ky^l$.

	Now consider those monomials of the form $x^ky^l$ for any fixed $k<i$.  These monomials are only really on one variable, $y$, so we can appeal to induction to show that for any fixed $k<i$ that set of monomials is also finitely generated.  We can also make the same argument for any fixed $l<j$.  As there are a finite number of $k<i$, and a finite number of $l<j$, we can simply union all of these generators together, and thus generate the entire space of monomials.
\end{proof}

Note that the above proof gives no effective bound on the size of the generating set of monomials, the proof only shows that the set is finite.  We may see in later lectures how to get a finite bound on the size of the generating set of $\la LT(J)\ra$ for $J=\la f_1,\ldots,f_m\ra$, given degree bounds on the $f_i$.

We now show how to derive ideal membership testing from Gr\"{o}bner bases. For this, we will use the following notation.  The multi-degree, denoted $\mdeg$, of a polynomial $f$ is the multi-degree of its leading term, and the multi-degree of $\vec{x}^{\vec{a}}=\vec{a}$.  We will also assume that all polynomials are monic, unless otherwise specified.  This is without loss of generality as we work over a field.  We now begin formalize the reduction notion from above.

\begin{definition}
	Consider $f,h_1,\ldots,h_l\in\K[x_1,\ldots,x_n]$.  The \textit{weak remainder} of $f$ with respect to the $h_i$ is the polynomial $r=f-\sum q_i h_i$ such that no monomial of $r$ is divisible by any $LT(h_i)$.
\end{definition}

This can be seen as a local optimum of the division algorithm.  That is, we have reduced $f$ modulo the $h_i$ as far as possible, by cancelling out monomials divisible by the $LT(h_i)$.  However, it is possible that we ``got stuck''.  That is, we perhaps could make the remainder $r$ smaller, but fails, as there are no monomials divisible by any $LT(h_i)$.  One example of this is $f=r=x$, and $h_1=x(x+1)$, $h_2=x(x+2)$.  Clearly $\la h_1,h_2\ra=\la x\ra$, and so the remainder of $f$ by $h_1,h_2$ should be zero.  But we get $r=f=x$ because we cannot reduce any further by cancelling out monomials by the $LT(h_i)$.  Thus, we see that the weak remainders are not unique in general.  However, if the $h_i$ form a Gr\"{o}bner basis, then we can show that weak remainders are unique.

\begin{lemma}
	Let $g_1,\ldots,g_t$ be a Gr\"{o}bner basis for the ideal $J=\la g_1,\ldots,g_t\ra$.  Then for any $f$, the weak remainder with respect to the $g_i$'s is unique.
\end{lemma}
\begin{proof}
	Suppose $f=r+\sum q_ig_i=r'+\sum q_i'g_i$ are two weak remainder decompositions of $f$.  Then $r-r'=\sum (q_i-q_i')g_i\in J$.  As the $g_i$ are a Gr\"{o}bner basis, it follows that if $r-r'$ is non-zero then its leading monomial of $r-r'$ must be divisible by some $LT(g_i)$.  But the monomials of $r-r'$ are a subset of the union of the monomials of $r$ and $r'$, and none of those monomials are divisible by any $g_i$.  Thus, it follows that $r-r'$ must be zero, so $r=r'$.
\end{proof}

We can now establish that Gr\"{o}bner bases are indeed bases. To do so, we need to argue that weak remainders exist.  We do so via a constructive argument.  That is, define the \textit{canonical remainder algorithm} on input $f,h_1,\ldots,h_l$ as follows.  We first express $f=r+\sum q_ih_i$, with $r=f$ and all $q_i=0$.  We then find the highest multi-degree of a monomial $m$ in $f$ such that for some $i$, there is a monomial $m_i$ $LT(h_im_i)=m$.  We then set $r\from r-h_im_i$ and $q_i\from q_i+m_i$.  Thus, the equation $f=r+\sum q_ih_i$ is invariant under this process.  Further, as we pick the highest multi-degree monomial at each point and this process does not ``mess up'' higher multi-degree monomials, we see that at each stage we make progress, and so will eventually terminate.  When we terminate it is not hard to see that we get a weak remainder.

We now note a property of the canonical weak remainder, that will be important for the analysis of our Gr\"{o}bner basis algorithm.  We note that in $f=r+\sum q_ig_i$, we will always have that the multi-degree of $q_ig_i$ will be at most the multi-degree of $f$.  This is true by analyzing the algorithm above.  The importance of this fact is that this shows that there is no ``high degree cancellation'' in the summation $r+\sum q_ig_i$.

\begin{lemma}
	Let $g_1,\ldots,g_t$ be a Gr\"{o}bner basis for $J=\la f_1,\ldots,f_m\ra$.  Then $J=\la g_1,\ldots,g_t\ra$.
\end{lemma}
\begin{proof}
	Consider any $f\in J$, we wish to show $f\in\la g_1,\ldots,g_t\ra$.  Let $f=r+\sum q_ig_i$ be the weak remainder (as constructed above) for $f$ over the $g_i$.  Now we see that $r=f-\sum q_ig_i\in J$.  Thus, if $r\ne 0$ it must be that there is an $i$ with $LT(g_i)$ dividing $LT(r)$.  However, the construction of the weak remainder says this is impossible, so it must be that $r=0$, implying that $f\in\la g_1,\ldots,g_t\ra$.
\end{proof}

Thus, we now have our test for ideal membership, given a Gr\"{o}bner basis.  We see that $f\in\la g_1,\ldots,g_t\ra$ iff the weak remainder of $f$ over $\la g_1,\ldots,g_t\ra$ is zero.  We constructed this remainder above, and it is fairly efficient (for polynomials in the dense representation).

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

Having shown that Gr\"{o}bner bases solve the ideal membership problem, we now show an algorithm, that runs in finite time, for constructing these objects.  A paramount concept in this algorithm is that of a \textit{syzygy}.  This word refers to the alignment of three celestial objects in a straight line.  For us, this concept refers to high-multi-degree cancellation of two polynomials.  That is, we refer to two polynomials $f$ and $g$, each of the same multi-degree.  When we consider $f-g$ we observe that this difference has strictly smaller multi-degree, because of cancellation.  More formally, we have the following definition.

\begin{definition}
	Let $f$ and $g$ be two monic polynomials.  Let $m$ be the least common multiple of $LT(f)$ and $LT(g)$, so that $m$ is a monic monomial.  Define $S(f,g)$, the \textit{syzgy} of $f$ and $g$, to be $S(f,g)=mf/LT(f)-mg/LT(g)$.
\end{definition}

Note that this produces the desired cancellation, and does so in a minimal way.  Also note that ideals are closed under syzygies.

We now give the Gr\"{o}bner basis algorithm, starting with the polynomials $f_1,\ldots,f_t$.  We use the operator $\bmod$ to denote the canonical weak remainder.
\begin{itemize}
	\item $B\from\{f_1,\ldots,f_t\}$
	\item iterate until no additions: if $\exists g_i,g_j\in B$ so $r:=S(g_i,g_j)\bmod B$ has $r\ne 0$, then $B\from B\cup\{r\}$.
	\item output $B$.
\end{itemize}
Note that this is quite similar to the group membership algorithm we saw early on, in that both algorithms find a ``good'' representation of an algorithmic object, from which membership testing is easy.  And to find this object, both cases add new polynomials or group-elements by ensuring that the current set is closed under some binary operation.  Once the set is closed under this binary operation, the desired object is found.  It would be interesting to see if there is a formal connection between these two objects.

We first argue that this algorithm terminates. To see this, consider the ideal $\la LT(B)\ra$ over the course of the algorithm.  Clearly $\la LT(B)\ra\subseteq \la LT(J)\ra$ always.  Note that in each step, the $r$ we add to $B$ has a leading term not currently in $\la LT(B)\ra$.  For, the reason the weak remainder algorithm gives $r\ne 0$ is that the leading term of $r$ cannot be canceled out by any leading term in $B$, and this implies $LT(r)\notin \la LT(B)\ra$, since we have the membership of a monomial in monomial ideal is determined solely be division, as mentioned above.  Thus, we see that $\la LT(B)\ra$ is growing over time, by expanding the number of generators.  As $\la LT(B)\ra\subseteq \la LT(J)\ra$, and by Dickson's lemma we have that $\la LT(J)\ra$ is finitely generated, it must be that $\la LT(B)\ra$ is finitely generated at each point, and this implies that $\la LT(B)\ra$ cannot grow forever.  That is, the algorithm must halt.  So far this does not establish that $\la LT(B)\ra=\la LT(J)\ra$, but that will be given by the following lemma.

\begin{lemma}
	Let $J=\la g_1,\ldots,g_t\ra$.  If $S(g_i,g_j)\bmod \{g_1,\ldots,g_t\}=0$ for all $i,j$, then $\la LT(J)\ra=\la LT(g_1),\ldots,LT(g_t)\ra$.
\end{lemma}
\begin{proof}
	Consider any $f\in J$.  It will suffice to show that $LT(f)\in\la LT(g_1),\ldots,LT(g_t)\ra$.  Express $f=\sum_{j=1}^k m_jg_{i_j}$, where each $m_j$ is a monomial (possibly non-monic), and the following conditions hold
	\begin{itemize}
		\item The multi-degree of $m_ig_{i_j}$ is monotonically decreasing with $i$
		\item For all $\vec{a}$, the number of $i$ such that $m_ig_{i_j}$ has multi-degree $\vec{a}$ is minimal, given all of the monomials of multi-degree $>\vec{a}$.
	\end{itemize}
	Note that the existence of such summations (even without the conditions) follows from the fact that $f\in J$.  That the first condition can be met is clear from sorting.  That the second condition can be met follows from the ability to pick out minimal elements from a non-empty set.

	Now consider the following.  If $\mdeg(m_1g_{i_1})>\mdeg(m_2g_{i_2})$ then we are done.  That is, if this occurs, then there is no cancellation of $LT(m_1g_{i_1})$, as the $\mdeg$ monotonically decrease.  This implies that $LT(m_1g_{i_1})=LT(f)$, and so $LT(g_{i_1})$ divides $LT(f)$ as desired.

	Thus, suppose $\mdeg(m_1g_{i_1})=\mdeg(m_2g_{i_2})$.  We will show this cannot happen, by the minimality condition we imposed.  That is, we will show that $m_2g_{i_2}=m_1g_{i_1}+\text{lower mdeg terms}$, so that we can write $f=2m_1g_{i_1}+\sum_{j=2}^k m_jg_{i_j}+\text{lower mdeg terms}$, so we have decreased the number of terms with multi-degree equal to the multi-degree of $m_1g_{i_1}$, which contradicts our minimality.  Thus, it remains to show this relation.

	Note that $m_1g_{i_1}-m_2g_{i_2}$ has cancellation at the leading term, as these two polynomials have the same multi-degree.  Thus, there exists a monomial $w$ such that $m_1g_{i_1}-m_2g_{i_2}=wS(g_{i_1},g_{i_2})$.  As $S(g_{i_1},g_{i_2})\bmod \{g_1,\ldots,g_t\}=0$ we have that $S(g_{i_1},g_{i_2})=\sum q_ig_i$, and as this is by the weak remainder algorithm, we have $\mdeg(w)+\mdeg(q_ig_i)\le\mdeg(w)+\mdeg(S(g_{i_1},g_{i_2}))<\mdeg(m_1g_{i_1})$.  So we can express \[m_1g_{i_1}-m_2g_{i_2}=\sum (q_iw)g_i\] as desired, as the right hand side has lower multi-degree than the $\mdeg(m_2g_{i_2})$.
\end{proof}

So putting this all together, the algorithm must terminate with a set of polynomials, whose syzygies have zero weak remainder on this set.  This then implies the set is a Gr\"{o}bner basis for itself, and as it contains the $f_i$, is a basis for the $f_i$.  We can then use this basis for testing membership in the ideal $\la f_1,\ldots,f_m\ra$.

\section{Next Time}

Next time we will discuss the complexity theory of the ideal membership question, such as deriving degree bounds on the polynomials needed to certify ideal membership.  We will also discuss the EXPSPACE-hardness of the ideal membership question, using ideas from the commutative word problem.


\end{document}
