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