%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%                                %%%%%%%%%%%
%%%%%%%%%%% This is a template for quizzes %%%%%%%%%%%
%%%%%%%%%%%                                %%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsfonts,amsthm,graphicx}
\DeclareGraphicsExtensions{.pdf}
%\centerline {\includegraphics[width=3in]{PICTURE}}

\usepackage{geometry}
%\usepackage{fullpage}

\newtheoremstyle{problem}{\topsep}{\topsep}%%% space between body and thm
		{}                      %%% Thm body font
		{}                              %%% Indent amount (empty = no indent)
		{\bfseries}            %%% Thm head font
		{}                    %%% Punctuation after thm head
		{ }                           %%% Space after thm head
		{\thmnumber{#2}\thmnote{ \bfseries (#3)}}%%% Thm head spec
\theoremstyle{problem}
\newtheorem{p}{}

\textwidth6in
\textheight8.5in

\newcommand{\V}[1]{\mathbf{#1}}
\renewcommand{\d}{\,{\mathrm d}}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\newcommand{\lcm}{\mathop{\mathrm{lcm}}\nolimits}

\renewcommand{\labelenumi}{($\mathrm{\alph{enumi}}$)}
\newcommand{\pr}[1]{{{\bf P}^{#1}}}
\newcommand{\Aff}[1]{{{\bf A}^{#1}}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\Shf}[1]{\mathcal{#1}}
\newcommand{\field}{K}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\NN}{\mathbb{N}}

\newcommand{\GB}{Gr\"obner basis }
\newcommand{\G}{Gr\"obner }
\newcommand{\PE}{\begin{proof}EXERCISE\end{proof}}
\newcommand{\I}{{\bf I}}
%\newcommand{\V}{{\bf V}}
\newcommand{\bx}{{\bf x}}
\newcommand{\md}{\rm{multideg}}
\newcommand{\multideg}{\rm{multideg}}


\newcommand{\M}{{\em Macaulay2 }}

\begin{document}
\markright{\Large\textup\textbf{Math 918 -- Computational Algebra}\hfill 
%%%%%%%%%%% Quiz Name is Here %%%%%%%%%%%
\Large\textup{\textbf{Homework 2}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagestyle{empty}

\thispagestyle{myheadings}
\pagenumbering{gobble}


\noindent{\bf Due (tentatively) Friday, September 27.}
\bigskip 

\noindent{\em Work in groups (of 1 or more). Each group should turn in ONE solution set, preferably by email in LaTeX format. Each group should solve at least {\bf $\max($\# of group members, 2)} problems. 
\bigskip 

\noindent{\em AG=alg.~geom., CO=comb., AP=applied, M2= computational, B=beginner, *=advanced.}
\bigskip 

\begin{p}[B - Hilbert Basis Theorem] Give a proof by contradiction of the Hilbert Basis Theorem (this is a different proof than the one given in class). Proceed by induction on the number of variables. Let $I$ be an ideal and assume that $I$ is not finitely generated. Inductively construct a sequence $f_1, f_2, \ldots $ of elements of $I$ such that $f_{i+1}$ has minimal degree in $I \setminus J_i$, where $J_i$ is the ideal generated by $f_1, \ldots , f_i$. Use the inductive hypothesis to derive a contradiction.
\end{p}

%\vfill

\begin{p} [B - Discard criterion for S-polynomials]
Let $G=\{g_1,\ldots ,g_s\}$ be a set of polynomials (not assumed to be a \GB). Let $f,g\in G$ be such that the leading monomials of $f$ and $g$ are coprime, i.e.
$$LCM(LM(f),LM(g))=LM(f)\cdot LM(g).$$
Show that  there are polynomials $a_i$ such that $S(f,g)=\sum_{i=1}^s a_ig_i$ and $\multideg(a_ig_i)\leq \multideg(S(f,g))$ whenever $a_i\neq 0$. \end{p}

\begin{p}[B - Construction of reduced \G bases] Prove that the result of the following procedure is a reduced \GB: start with any \GB $G=\{g_1,\ldots, g_s\}$ of  $I$. 
\begin{itemize}
\item \textbf{Step 1:} for $i$  from 1 to $s$ do: if $LT(g_i)\in \langle LT(G\setminus\{g_i\})\rangle$, then set $G=G\setminus\{g_i\}$;
\item \textbf{Step 2:} Suppose that at the end of Step 1 you have a new $G=\{g'_1,\ldots, g'_t\}$. \\
\quad \quad  For $i$ from 1 to $t$ do : $G=(G\setminus\{g_i\})\cup \{g_i\%(G\setminus\{g_i\})\}$.
\end{itemize}
\end{p}

%\vfill

\begin{p} [B - LCM criterion for \G bases]
Fix a monomial order $<$. Show that a finite set $G=\{g_i,\ldots, g_s\}$ is a \GB of $I=\left<g_i,\ldots, g_s\right>$ if and only if for every
$f,h \in G$, $S(g,h) = \sum_{i=1}^s a_i\cdot g_i$, where $a_i\neq 0$ implies
$LT(a_i\cdot g_i) < LCM(LM(f), LM(h))$. 
\end{p}


%\vfill

\begin{p} [B - Standard representation criterion for \G bases]
Fix a monomial order $>$. Show that a finite set $G=\{g_i,\ldots, g_s\}$ is a \GB of $I=\left<g_i,\ldots, g_s\right>$ if and only if every
$f\in I$, can be written as $f= \sum_{i=1}^s a_i\cdot g_i$, where $LT(f)=\max_>\{LT(a_i ) LT(g_i ) | a_i\neq 0\}$.\end{p}


%\vfill



\begin{p} [CO, AP - Binomial ideals]
A polynomial is called a binomial if it has at most two terms. An ideal  is called a binomial ideal if it
is generated by binomials. Given any  monomial order $>$ and an ideal $I$, show
that the following are equivalent:
\begin{enumerate}
\item $I$ is a binomial ideal.
\item $I$ has a binomial \GB, that is, a \GB consisting of binomials
\item the normal form with respect to $I$ of any monomial is a term (a term is a constant times a monomial).
\end{enumerate}
\end{p}
%\noindent{\it Compare with the ideals appearing in the  monomial curves or  coins problem.  }

%\vfill


\begin{p}[*, AG - Ideals of minors]
Consider the ideal generated by the two by two minors of the matrix
$$A = \left( \begin{matrix} x_1& x_2& \ldots & x_n \\ y_1& y_2 & \ldots & y_n \end{matrix}\right)$$. 
\begin{enumerate}
\item Show that the minors  form a \GB with respect to the lexicographic order with $x_1>x_2>\ldots >x_n>y_1>y_2>\ldots >y_n$? 
\item Can you think of a different term order for which your proof holds?
\end{enumerate}
\end{p}


\begin{p} [* - Artinian test]
Let $>$ be a fixed  monomial order  on a polynomail ring $R=k[x_1,\ldots, x_n]$. Let  $I\subset R$ be an ideal
 and let $G$ be a \GB of $I$ with respect to $>$. Show that
the following are equivalent:
\begin{enumerate}
\item $\dim_k(R/I) < \infty$,
\item  $\forall \ 1\leq i \leq n, \exists \ n_i \in \mathbb{Z}_{\geq 0}$ such that $x_i^{n_i}$
 is a leading monomial of an element of $G$.
\end{enumerate}
\end{p}





%\vfill
 \end{document}  

 %\vfill
\begin{p}
Let | be innite. Consider the ideal
I = hxz ?? y2; x2 ?? yi  |[x; y; z]:
1. Observe that the line V(x; y) is contained in V(I)  A3(|).
2. Compute that I : hx; yi = I : hx; yi1 = I(C), where I(C) = hx2??y; xy??zi is the vanishing ideal of the twisted cubic curve C  A3(|).
3. Compute that I = hx; yi \ I(C). Conclude that this intersection is a primary
decomposition of I and that V(I) = V(x; y) [ C is the decomposition
of V(I) into its irreducible components.
\end{p}

 

 
 
