\documentclass[landscape]{slides}
\usepackage[landscape]{geometry}
\usepackage{graphicx}
%\usepackage{color}
\usepackage{cancel}
\usepackage[usenames,dvipsnames]{color}
\usepackage{amsmath,amsfonts,amssymb,amsthm}

% the following produces 1 inch margins all around with no header or footer
\topmargin	=0.mm %  -15.mm		% beyond 25.mm
\oddsidemargin	=0.mm		% beyond 25.mm
\evensidemargin	=0.mm		% beyond 25.mm
\headheight	=0.mm
\headsep	=0.mm
\textwidth	=220.mm
\textheight	=165.mm

\def \<{\langle} 
\def \>{\rangle}

\def \bproof{\noindent \textbf{Proof:\ \ }}
\def \eproof{$\blacksquare$\\}

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}
\newcommand{\divides}{\,\Big|\,}
\newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.35in}{\hfill}}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}
\newcommand{\so}{\hspace*{-0.065in}X}
\newcommand{\soo}{\hspace*{-0.13in}XX}
\newcommand{\force}{{$\mbox{\;}$}}

\begin{document}

%\definecolor{myName}{named}{Apricot}
%\definecolor{myName}{named}{Aquamarine} 	
%\definecolor{myName}{named}{Bittersweet} 	
%\definecolor{myName}{named}{Black}
%\definecolor{myName}{named}{Blue} 	
%\definecolor{myName}{named}{BlueGreen} 	
%\definecolor{myName}{named}{BlueViolet} 	
%\definecolor{myName}{named}{BrickRed}
%\definecolor{myName}{named}{Brown} 	
%\definecolor{myName}{named}{BurntOrange} 	
%\definecolor{myName}{named}{CadetBlue} 	
%\definecolor{myName}{named}{CarnationPink}
%\definecolor{myName}{named}{Cerulean} 	
%\definecolor{myName}{named}{CornflowerBlue} 	
%\definecolor{myName}{named}{Cyan} 	
%\definecolor{myName}{named}{Dandelion}
%\definecolor{myName}{named}{DarkOrchid} 	
%\definecolor{myName}{named}{Emerald} 	
%\definecolor{myName}{named}{ForestGreen} 	
%\definecolor{myName}{named}{Fuchsia}
%\definecolor{myName}{named}{Goldenrod} 	
%\definecolor{myName}{named}{Gray} 	
%\definecolor{myName}{named}{Green} 	
%\definecolor{myName}{named}{GreenYellow}
%\definecolor{myName}{named}{JungleGreen} 	
%\definecolor{myName}{named}{Lavender} 
%\definecolor{myName}{named}{LimeGreen} 	
%\definecolor{myName}{named}{Magenta}
%\definecolor{myName}{named}{Mahogany} 	
%\definecolor{myName}{named}{Maroon} 	
%\definecolor{myName}{named}{Melon} 	
%\definecolor{myName}{named}{MidnightBlue}
%\definecolor{myName}{named}{Mulberry} 	
%\definecolor{myName}{named}{NavyBlue} 	
%\definecolor{myName}{named}{OliveGreen} 	
%\definecolor{myName}{named}{Orange}
%\definecolor{myName}{named}{OrangeRed} 	
%\definecolor{myName}{named}{Orchid} 	
%\definecolor{myName}{named}{Peach} 	
%\definecolor{myName}{named}{Periwinkle}
%\definecolor{myName}{named}{PineGreen} 	
%\definecolor{myName}{named}{Plum} 	
%\definecolor{myName}{named}{ProcessBlue} 	
%\definecolor{myName}{named}{Purple}
%\definecolor{myName}{named}{RawSienna} 	
%\definecolor{myName}{named}{Red} 	
%\definecolor{myName}{named}{RedOrange} 	
%\definecolor{myName}{named}{RedViolet}
%\definecolor{myName}{named}{Rhodamine} 	
%\definecolor{myName}{named}{RoyalBlue} 	
%\definecolor{myName}{named}{RoyalPurple} 	
%\definecolor{myName}{named}{RubineRed}
%\definecolor{myName}{named}{Salmon} 	
%\definecolor{myName}{named}{SeaGreen} 	
%\definecolor{myName}{named}{Sepia} 	
%\definecolor{myName}{named}{SkyBlue}
%\definecolor{myName}{named}{SpringGreen} 	
%\definecolor{myName}{named}{Tan} 	
%\definecolor{myName}{named}{TealBlue} 	
%\definecolor{myName}{named}{Thistle}
%\definecolor{myName}{named}{Turquoise} 	
%\definecolor{myName}{named}{Violet} 	
%\definecolor{myName}{named}{VioletRed} 	
%\definecolor{myName}{named}{White}
%\definecolor{myName}{named}{WildStrawberry} 	
%\definecolor{myName}{named}{Yellow} 	
%\definecolor{myName}{named}{YellowGreen} 	
%\definecolor{myName}{named}{YellowOrange}

% FONT SIZES...
%\tiny
%\scriptsize
%\footnotesize
%\small
%\normalsize (default)
%\large
%\Large (capital "L")
%\LARGE (all caps)
%\huge
%\Huge (capital "H")

%\definecolor{highlight}{named}{Blue} 
%\definecolor{backgroundColor}{named}{White}
%\definecolor{regcolor}{named}{LimeGreen}

%\definecolor{regcolor}{rgb}{0.5,0.75,1}
\definecolor{regcolor}{rgb}{1,1,1}
\definecolor{highlight}{named}{Yellow}
\definecolor{backgroundColor}{rgb}{0.05,0.1,0.15}


\pagestyle{empty}
\pagecolor{backgroundColor}

\color{regcolor}

\begin{slide}
\begin{center}
\LARGE \textcolor{highlight}{\textcolor{highlight}{Gr\"obner Bases}\\ } 

\vspace{0.75in}
%\vfill

\normalsize

\begin{tabular}{rcl}
Holly Cook & $\Leftrightarrow$ &
\texttt{cookh@appstate.edu}\\
Michael Kelley & $\Leftrightarrow$ &
\texttt{kelleyma1@appstate.edu}\\
Woody Madison & $\Leftrightarrow$ &
\texttt{madisonrt@appstate.edu}\\
Samwise Migirditch & $\Leftrightarrow$ &
\texttt{migirditchsv@appstate.edu}\\
Elisabeth Moore & $\Leftrightarrow$ &
\texttt{mooreej@appstate.edu}\\
\end{tabular}

\vspace{0.1in}

[Please, no unsolicited emails.]

\vspace{0.25in}       
       
\textcolor{highlight}{\large Thursday, May $1^{\mathrm{st}}$ 2014}  % at ???pm
\end{center}
\end{slide}

\begin{slide}

In 1965 {\color{highlight}Bruno Buchberger} introduced the notion of a {\color{highlight}Gr\"obner basis} as well as his algorithm for computing them. Gr\"obner bases are incredibally useful tools for solving all sorts of algebraic problems. They are used in a wide variety of applications in areas such as computational biology and are even used in encryption schemes for many cell phones.

To indicate how important Buchberger's algorithm is, this algorithm simulataneously generalizes both the {\color{highlight}Euclidean algorithm} (for finding GCD's of polynomials) and {\color{highlight}Gauss-Jordan elimination} (for solving linear systems). 

\end{slide}


\begin{slide}

Although {\color{highlight}Gr\"obner bases} can be discussed in a very general context, we will primarily stick to polynomials with complex coefficients in 3 variables: $\mathbb{C}[x,y,z]$.

{\color{highlight}Definition:} A {\color{highlight}monomial ordering} on $\mathbb{C}[x,y,z]$ is a linear orderings (think ``less than'') such that if {\color{highlight}$A<B$} for monomials $A$ and $B$, then {\color{highlight}$CA<CB$} for any monomial $C$ and in addition {\color{highlight}$1<A$} for all monomials $A\not=1$. 

Two popular monomial orderings are the lexicographic and total degree orderings.

\vspace{-0.4in}

\begin{description}
\item[\color{highlight}Lexicographic] This is essentially alphabetic ordering:\\ $x^2y>xy^2>xyz>xy>x>y^2>z^3$. 
\item[\color{highlight}Degree Lex] This ordering first considers the total degree and then defaults to lexicographic ordering:\\
$   x^2y>xy^2>xyz>z^3>xy>y^2>x$. 
\end{description}

\end{slide}


\begin{slide}

{\color{highlight}Multivariate division} extends standard single variable polynomial division. 

We can {\color{highlight}reduce} $f$ by $g$ to $h$, written as {\color{highlight}$f \underset{g}{\to} h$} if $f$ contains a term which is a multiple of the leading term of $g$, say $mg$'s leading term appears in $f$, and $h=f-mg$.

Given a set $S$ of polynomials, we write {\color{highlight}$f \underset{S}{\to} h$} if $f \underset{g}{\to} h$ for some $g \in S$. 

Finally, we write {\color{highlight}$f {\underset{S\ \ }{\to_+}} \  h$} if $f \underset{g_1}{\to} h_1 \underset{g_2}{\to} h_2 \cdots \underset{g_\ell}{\to} h_\ell=h$ for some $g_1,\dots,g_\ell \in S$ and polynomials $h_1,\dots,h_\ell$. 

If there is no $g \in S$ and polynomial $h$ such that $f \underset{g}{\to} h$, we say $f$ is {\color{highlight}reduced (mod $S$)}. 

If $f$ reduces to $r$ (mod $S$), we call $r$ a {\color{highlight}remainder} of division of $f$ by $S$.

{\color{highlight}Definition:} A {\color{highlight}Gr\"obner basis} $S$ is a collection of polynomials such that division by $S$ yields unique remainders.

{\color{highlight}Buchberger's algorithm} allows one to take an arbitrary finite set of polynomials and find an equivalent {\color{highlight}Gr\"obner basis}. (By equivalent we mean that they share a common solution set when treated as polynomial equations.)

\end{slide}


\begin{slide}

{\color{highlight}Example of division:} Let's divide $f=x^3y^3+2y^2$ by $S = \{g_1 = 2xy^2+4y^2+3x, g_2 = y^2-2y-2 \}$.

\begin{itemize}\setlength{\itemsep}{0pt}
\item $f-\frac{1}{2}x^2yg_1 = -2x^2y^3-\frac{3}{2}x^3y+2y^2=h_1$
\item $h_1+xyg_1 = -\frac{3}{2}x^3y+4xy^3+3x^2y+2y^2=h_2$
\item $h_2-2yg_1 = -\frac{3}{2}x^3y+3x^2y-8y^3-6xy+2y^2=h_3$
\item $h_3+8yg_2 = -\frac{3}{2}x^3y+3x^2y-6xy+18y^2+16y=h_4$
\item $h_4-18g_2= -\frac{3}{2}x^3y+3x^2y-6xy+52y+36=r$
\end{itemize}
$$\mbox{Therefore,} \qquad f\underset{g_1}{\to}h_1\underset{g_1}{\to}h_2\underset{g_1}{\to}h_3\underset{g_2}{\to}h_4\underset{g_2}{\to}r.$$

So $f\underset{S}{\to_+} r$ where {\color{highlight}$r$ is reduced mod $S$}. 
\end{slide}


\begin{slide}

{\color{highlight}An application:} Making change. $p^5=n$, $p^{10}=d$, $p^{25}=q$, $p^{100}=b$. Then the {\color{highlight}Gr\"obner basis} equivalent to
$S = \{ p^5-n,p^{10}-d,p^{25}-q,p^{100}-b\}$ is $B = \{p^5-n,d-n^2,nq-d^3,q-d^2n,q^4-b\}$ (using the {\color{highlight}degree lex} ordering).

Then 2 bucks (i.e. dollars), 5 quarters, 2 dimes, 3 nickels, and 8 pennies. Are represented by {\color{highlight}$f=b^2q^5d^2n^3p^8$}.

$f$ divided by $B$ is {\color{highlight}$r=b^3q^2dnp^3$} which is 3 bucks, 2 quarters, 1 dime, 1 nickel, and 3 pennies (equivalent change with fewer "coins").

If we change to {\color{highlight}pure lexicographic} ordering, we get $B = \{ p^5-n,n^2-d,d^2n-q,nq-d^3,bn-d^3q^3,d^5-q^2,q^4-b\}$. When $f$ is divided by this {\color{highlight}Gr\"obner basis}, we get {\color{highlight}$r=b^3qd^4p^3$}. This is 3 bucks, 1 quarter, 4 dimes, no nickels, and 3 pennies. Again we have equivalent change, but we used more "coins". However, we avoided the use of lower denomination coins {\it if possible}. In particular, we have no nickels.

\end{slide}


\begin{slide}

We also discussed {\color{highlight}Gr\"obner bases} for non-commutative rings and how these can be used to "compute proofs" of otherwise difficult statements. 

We also discussed doomsday weapons and our future red-headed overlords.

References: {\small
\begin{itemize}
\item {\it Ideals, Varieties, and Algorithms} by Cox, Little, and O'Shea
\item {\it A First Course in Abstract Algebra} by Fraleigh ($7^{\mbox{th}}$ edition)
\item {\color{highlight}{\it An Introduction to Gr\"obner Bases} by Adams and Loustaunau}
\item {\it Commutativity Theorems: Examples in Search of Algorithms} by Wavrik 
\item {\it An Introduction to Commutative and Non-Commutative Gr\"obner Bases} by Mora
\end{itemize}
}

Thank you Cobra Commander!

\end{slide}

\begin{slide}

\begin{center}
{\color{highlight}\Large\sc $\mathcal{A}$ny $\mathcal{Q}$uestions?}
\end{center}

\end{slide}



\end{document}
