\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}{20} % lecture number
\newcommand{\lecturetitle}{Ideal Membership Problem and Gr\"{o}bner Basis} % topic of lecture
\newcommand{\lecturedate}{April 22, 2015} % date of lecture
\newcommand{\studentname}{Chennah Heroor} % 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. Gr\"{o}bner bases were introduced in the last lecture, but today we will see the math behind them. The Gr\"{o}bner bases algorithm was due to Buchberger. It solves the ideal membership question, and suggests the notion of a canonical remainder.
\section{Ideal Membership Problem}
We begin by defining the Ideal Membership Problem
\begin{definition} \textbf{Ideal Membership Problem}:
Given a target polynomial $f$ and polynomials $f_1,\ldots,f_m\in\K[x_1,\ldots,x_n]$, is $f\in\la f_1,\ldots,f_m\ra$, where $\la f_1,\ldots,f_m\ra$ denotes the ideal generated by the $f_i$
\end{definition}
We note that an equivalent formulation of the problem is: Does there exist polynomials $g_1, ... g_m$ such that $f = \sum f_i g_i$.
We will solve this question by using Gr\"{o}bner bases. The Gr\"{o}bner basis gives us a representation of an ideal, that allows us to easily decide membership, and the basis is constructed via Buchberger's algorithm. An important question regarding Buchberger's algorithm is its complexity, or given a set of n polynomials with degree m, what is the running time of the algorithm. In order to learn the complexity of this problem, it becomes necessary to determine the degree of the polynomials $g_i$. However, we leave the discussion of the algorithm's complexity to the next lecture.
First, we focus on the idea of finding the remainder of a polynomial modulo an ideal. This problem is simple if we restrict ourselves to univariate polynomials. We order the polynomials by the highest degree and repeatedly take the remainder modulo the highest degree we can remove.
However, with multivariate polynomials, we have a notion of preference: which terms would we prefer to reduce? For example, consider the polynomial $x^2y + y^2x$ divided by $x +y$. It is unclear what answer should be, as the remainder can be written as either a polynomial purely in x or purely in y, or we can reduce the total degree of the polynomial.
% (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.
The Gr\"{o}bner basis seeks to solve this question by imposing an order on the division for multivariate polynomials. 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 $m_1< m_2\implies m_1 * m < m_2 * m$
\item $1\le m$ $\forall m$, so 1 is the canonical smallest element
\end{itemize}
We note that there are many possible orders, but we must fix a single order. An example of an admissible total ordering is lexicographic ordering in which $x_i \geq x_{i-1}^d$ $\forall d$. Thus we prioritize all powers of $x_i$ before any power of $x_{i-1}$. Another admissible total ordering is one where $\sum d_i \leq \sum e_i$ implies $x^d < x^e$, and ties are broken in lexicographic order.
The choice of monomial orderings is important to the complexity of the solution. Certain orderings might quickly reveal that a function is not in the ideal, while other orderings will reveal this after more work has been completed. Furthermore, there exist ideals such that even an optimal ordering of the monomials cannot be used to solve the membership problem faster than doubly exponential time. Thus Buchberger's algorithm attempts to limit the amount of work done given a particular monomial ordering.
However, even with the monomial ordering, we have not completed the notion of dividing a polynomial by an ideal. This problem can be tricky to solve, even in the univariate case. Consider x(x+1) and x(x+2). This is the ideal generated by x. However, until we realize this, it is difficult to answer what the remainder should be when we divide $x^2$. We can report a remainder of x or 2x, but neither is the correct answer, since $x^2$ is in the ideal generated by x.
Thus we need to understand the relationship between the polynomials. This brings us to the notion of GCD. If we are able to compute the GCD of x(x+1) and x(x+2), we can learn that x is generating these polynomials.
However, the GCD is defined primarily for univariate polynomials because they can belong to a principal ideal domain. This is not true for multivariate polynomials.
For example, consider the set \{$x^i y^{d-i} | 0 \leq i \leq d$\} which generates polynomials of total degree at least d. It is clear that this is a minimal generating set. Every other monomial $x^iy^j$ for $i+j < d$ is not in there, and no member of this set can be generated by any other. Thus d monomials are necessary for ideal, even if the polynomial has at most 2 variables. This illustrates that there is no a priori bound on the number of elements necessary to generate the ideal that is based on the number of variables. Thus every ideal has a finite generating set, but the size can be arbitrarily large.
Thus when we are discussing ideals, we need to describe the notion of the canonical remainder, and we want the remainder calculation to be "not too variable". The Gr\"{o}bner basis gives us a very nice, unique remainder, once we fix the ordering of the polynomials.
The Gr\"{o}bner basis is useful by reducing the complexity of the polynomials by not focusing on the entire polynomial at once. Instead, it focuses on the leading term in polynomial first, and considers the ideal formed by the leading terms of the polynomials.
Thus, we describe the useful properties of the Gr\"{o}bner basis in more detail.
\section{Gr\"{o}bner Basis}
We begin by formally defining the leading term of a polynomial
\begin{definition} \textbf{Leading Term}: Given a polynomial f = sum $c_d x^d$, the leading term or LT(f) = $c_d x^d$ where $x^d$ is maximal monomial according to the total ordering. The leading monomial, denoted LM(f), is thus $x^d$.
\end{definition}
Then we can use the leading terms to define a weak notion of a canonical remainder. Given a monomial f and polynomials $$, we want to repeatedly reduce the power of f by scaling out the powers of $g_i$. This gives us a remainder $r = f - \sum \alpha_i g_i$ such that for every monomial m $\in$ f $\forall i \in [t]$, m is not divisible by $LT(g_i)$. Due to the total ordering of the $g_i$, we guarantee that the remainder has a strictly decreasing leading term.
Considering our earlier example, with $x^2$, and the ideal of x(x+1) and x(x+2), it is clear that $x^2$ should not be a remainder because its power has not strictly decreased. However, r = x and r = 2x are valid remainders.
Now, we consider monomial ideals, which are simply ideals generated by monomials. If we have a collection of monomials M = ${m_1, ... m_t}$ it is trivial to determine whether a particular monomial $m$ is in the ideal generated by $(M)$ since $m \in (M) \iff \exists $i such that $m_i$ $ | $ $m$
This gives us an intuition for Dickenson's Lemma.
\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