\documentclass{amsart}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
\usepackage[all]{xy}
\setlength{\parindent}{0pt}
\setlength{\parskip}{2ex}
\addtolength{\hoffset}{-1cm}
\addtolength{\textwidth}{2cm}
\title{Algebra III\\September 9, 2004}
\author{Gabriel C. Drummond-Cole}
\newtheorem{lemma}{Lemma}
\newtheorem{exercise}{Exercise}
\newtheorem{prop}{Proposition}
\newtheorem{example}{Example}
\newtheorem{defi}{Definition}
\newtheorem{rem}{Remark}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newcommand{\boundary}{\delta}
\newcommand{\interior}{\ ^\circ}
\newcommand{\percent}{\%}
\newcommand{\transpose}{t}
\newcommand{\zee}{\mathbb{Z}}
\newcommand{\crossing}[4]{\xymatrix{#1\ar[dr]|\hole&#2\\#3\ar[ur]&#4}}
%\newcommand{\prop}{\begin{prop}}
%\newcommand{\endprop}{\end{prop}}
%\newcommand{\exercise}{\begin{exercise}}
%\newcommand{\endexercise}{\end{exercise}}
\begin{document}
\noindent
\maketitle
Monomial ideals are easiest: $I=\langle m_i|i\in A\rangle\subset k[x_1,\ldots,x_n]=S.$  Monomials are $m=\underline{x}^{\underline{\alpha}}=x_1^{\alpha_1}\cdots x_n^{\alpha_n}.$  We can look at the staircase diagram that comes from $\alpha.$

So we want to look at the dimension of $R=k[x_1,\ldots,x_n]/I=\oplus_{i=0}^\infty R_i$ a $k$-vectorspace.  Note that $R_iR_j\subset R_{i+j}.$  

Now, $dim_k(R)=$ and $dim_k(R_i)$ is the number of monomials of degree $i$ in $S$ not in $I_i.$

Now say $J$ is a more general ideal.  We're going to find a monomial ideal $I$ such that all monomials not in $I$ form a basis for $S/J$ as a $k$-vector space.  This will prove the Hilbert basis theorem.
It will also eventually allow us to decide whether an element of $S$ lives in $J.$  If $J$ is homogeneous, I'll also be able to find the dimensions of the graded pieces.  
If $J$ is a homogeneous ideal $\langle f_1,\ldots, f_n\rangle,$ then $S/J$ is a graded vector space $\oplus_{i=0}^\infty V_j.$  We have a very important function $H:p\to dim)k(S/J)_p.$  It turns out that this agrees with a polynomial except at finitely many values.  

Now if $J$ were a monomial ideal, then counting this dimension would be easy.  So how do you find this monomial ideal?  You essentially want to pick monomials out of the polynomials you have.  So you need some sort of ordering.  

Now you need your monomial ideal to contain a monomial from each generator polynomial of $J.$
\begin{defi}
Given an order on the variables, a monomial order on $S=k[x_1,\ldots,x_n]$ is a relation $\succ$ on $\underline{x}^{\underline{\alpha}}$ such that \begin{enumerate}
\item $\succ$ is a total ordering
\item $\succ$ is compatible with $\cdot,$ so that $\underline{x}^{\underline{\alpha}}\succ \underline{x}^{\underline{\beta}}$ implies $\underline{x}^{\underline{\gamma}}\underline{x}^{\underline{\alpha}}\succ\underline{x}^{\underline{\gamma}} \underline{x}^{\underline{\beta}}(\succ\underline{x}^{\underline{\gamma}}$
\item $\succ$ is a well-ordering (redundant with the end of the previous line)
\end{enumerate}
\end{defi}
\begin{exercise}
Show that any selection function to give the monomial ideal $I$ must be a monomial order.
\end{exercise}
\begin{exercise}
Show that there is only one monomial order on $k[x],$ the order by degree.
\end{exercise}
Typically a monomial order will refine the degree.  Now say you are in $k[x_1,\ldots,x_n].$  Here are some orders:
\begin{itemize}
\item lex: Here, $\underline{x}^{\underline{\alpha}}\succ\underline{x}^{\underline{\beta}}$ if the leftmost nonzero entry of $\underline{\alpha}-\underline{\beta}$ is positive.
\item Grlex: Grade first by degree, i.e., by $\alpha\succ\beta$ if $|\alpha|>|\beta|$ and then if $|\alpha|=|\beta|$ you grade by lex.
\item This is a bad order, but is the best possible for doing computations.  You can eliminate variables.  revlex: $\underline{x}^{\underline{\alpha}}\succ\underline{x}^{\underline{\beta}}$ if either $|\alpha|>|\beta|$ or $|\alpha|=|\beta|$ and the rightmost nonzero entry of $\alpha-\beta$ is negative.
\end{itemize}
\begin{exercise}
There is one order refining degree in two variables.
\end{exercise}
So compare $x^3y^6$ with $x^3y^4z,$ then $x^3y^6$ is greater in glex.  This is also largest in revlex.

On the other hand, for $xz$ and $y^2$ we have $xz$ larger in glex and $y^2$ larger in revlex.

There are other orders you can build, which have some geometric interpretation.  You look at some weighted functional related to a polytope in some way.
\begin{defi}
If $f\in k[x_1,\ldots,x_n]$ and $\succ$ is a monomial ordering, then the initial $m_\succ(f)$ is the largest monomial in $f$ with respect to $\succ.$
\end{defi}
\begin{exercise}
\begin{enumerate}\item If $m_{lex}(f)\in k[x_s,\ldots,x_n],$ then $f\in k[x_s,\ldots,x_n].$ If $f$ is homogeneous then the same is true for $m_{Grlex}.$ 
\item If $m_{revlex}(f)\in (x_s,\ldots,x_n),$ then $f\in(x_s,\ldots,x_n).$  Note that this is an ideal whereas in the first case it was a subring.
\end{enumerate}
\end{exercise}
\begin{lemma}Dickson Lemma\\
Any set of monomials has only finitely many minimal elements in the partial order given by divisibility.  Equivalently, every monomial ideal is finitely generated (by a subcollection of any set of monomial generators)
\end{lemma}
Now take your favorite ideal $J\subset S$ and a monomial ordering $\succ.$  Now take from each polynomial in $J$ the initial monomial to get the initial ideal of $J,\ m_\succ(J)=\langle m_\succ(f)|f\in J\rangle.$  With the Dickson lemma this will give us the Hilbert basis theorem.  That is, $m_\succ(J)$ will be a monomial ideal.  Then a subcollection $\langle m_\succ(g_1),\ldots,m_\succ(g_m)\rangle$ will generate $m_\succ(J)$ and we can get that $\langle g_1,\ldots,g_m\rangle$ generates $J.$  Then $J$ is finitely generated.  If you want to be really picky, this works not just over a field, but over any Noetherian ring.  Now such a set $\{g_1,\ldots,g_m\}$ is called a Gr\"obner basis.

This shouldn't really be called a Gr\"obner basis because Gr\"obner didn't really work with these.  His student did.  Other people were already working with things like these, in, say, power series rings.

This is essentially Gordon's proof of Hilbert's basis theorem.  The standard proof was by induction and was nonconstructive.  Hilbert put the German mathematicians looking for these things out of business by saying that these were always finitely generated.  But he gave no way to find the generators.  Gordon gave you a way to find it.

You use this stuff to prove that $k[x_1,\ldots,x_n]^{\sigma_n}=k[y_1,\ldots,y_n]$ by $y_i\to\sigma_i,$ where these are the symmetric polynomials of degree $i.$

Now I'm going to give you an algorithm.  A lot of these are no good from a computer scientist standpoint.  If you work in Grlex, the degree of the Gr\"obner basis will be doubly exponential in the number of variables, whereas with revlex the degree will be roughly comparable with the number of variables.

By the way, this also solves the problem of ideal membership.  I give you a finite polynomial basis and I want to know if another polynomial, say $1$ for instance, is in their span.  You look instead at the initials.  It is a combination if and only if the initial term is in the initial ideal.

Now let's prove Dickson's lemma.
\\We'll proceed by induction on the number of variables.  If $n=1$ then the ideal is $\langle x_1^\alpha|\alpha\in A\subset \mathbb{N}\rangle=\langle x_1^{\alpha_{min}}|\alpha_{min}=\min\{\alpha|\alpha\in A\}\rangle$  So if $n=1$ then the ideal is principally generated.  

For the induction step, I'm going to use $\underline{x}$ to refer to the monomial factor in the first $n-1$ variables.  Now, we want to look at $(I:x_n^\infty)$ by which we mean $\langle \underline{x}^{\underline{\alpha}}|\exists m_\alpha, \underline{x}^{\underline{\alpha}}x_n^{m_\alpha}\in I\rangle.$  This is an ideal $J\subset k[x_1,\ldots,x_{n-1}]$ which is finitely generated (by $\{\underline{x}^{\underline{\alpha_1}},\ldots,\underline{x}^{\underline{\alpha_s}}\}$ by induction.  So take first $\underline{x}^{\underline{\alpha_i}}x_n^{m_i}$  For each $k<\max\{m_i\}$ let $J_k=(I:x_n^k)=\langle \underline{x}^{\underline{\alpha}}|\underline{x}^{\underline{\alpha}}x_n^k\in I\rangle\subset k[x_1,\ldots,x_{n-1}].$  This is finitely generated by $\{\underline{x}^{\underline{\alpha_{k1}}},\ldots,\underline{x}^{\underline{\alpha_{ks}}}\}.$  Then my Gr\"obner basis will be $\{\underline{x}^{\underline{\alpha_i}}x_n^{m_i},\underline{x}^{\underline{\alpha_{kj}}}x_n^k\}.$  So you just show that these generate $I,$ which is fairly straightforward.  

The only thing missing is that you can always get a subcollection.  Say $I=\langle \underline{x}^{\underline{\alpha}},\alpha\in A\rangle.$  We pick a Gr\"obner basis $\{\underline{x}^{\underline{\beta_i}}\};$ each of these must be a multiple of some $\underline{x}^{\underline{\alpha_i}}.$  Then this collection of corresponding $\underline{x}^{\underline{\alpha_i}}$ generates $I$ as well.

This triviality is called Macaulay's theorem:
\begin{thm}
A basis of $S/I$ is formed by all monomials not in $m_\succ(I).$
\end{thm} 
\end{document}
