\documentclass{amsart}
\usepackage{verbatim,ae}
\usepackage[margin=0.5 in]{geometry}
\usepackage{rotating} %for \includegraphix[angle=270]
\usepackage{amssymb}
%\usepackage{amsmath,amssymb,epsfig,amscd,xy,amsthm}
%\xyoption{all}
%\usepackage[active]{srcltx}
%\CompileMatrices


\hyphenation{arch-i-med-e-an}


%%Change to Roman for enumerate
%\renewcommand{\labelenumi}{(\roman{enumi})}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{quest}[theorem]{Question}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{exercise}{Exercise}
\newtheorem{conjecture}[theorem]{Conjecture}

%Main thms
\theoremstyle{plain}
%\newtheorem*{I1}{Theorem \ref{periodic}}
%\newtheorem*{I2}{Theorem \ref{per height}}
\numberwithin{equation}{theorem}


\theoremstyle{remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{exam}[theorem]{Example}
\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{assume}[theorem]{Assumption}
\newtheorem{conclude}[theorem]{Conclusion}
\newcommand{\C}{{\mathbb C}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\Fp}{{\mathbb F}_p}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\oQ}{{\overline{\mathbb Q}}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\M}{{\mathcal M}}
\newcommand{\cX}{{\mathcal X}}
\newcommand{\cY}{{\mathcal Y}}
\newcommand{\cXb}{{\overline \cX}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cA}{{\mathcal A}}
\newcommand{\cV}{{\mathcal V}}
\newcommand{\cW}{{\mathcal W}}
\newcommand{\cK}{{\mathcal K}}
\newcommand{\cZ}{{\mathcal Z}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\matO}{{\mathcal O}}
\newcommand{\OO}{{\mathcal O}}
\newcommand{\Ltilde}{{\tilde{\mathcal L}}}
\newcommand{\tensor}{\otimes}
\newcommand{\abcd}{\left( \begin{array}{cc} a & b \\ c & d \end{array} \right)}
\newcommand{\too}{\longrightarrow}
\newcommand{\bij}{\longleftrightarrow}
\newcommand{\bs}{\backslash}
\newcommand{\fO}{\mathfrak o}
\newcommand{\fo}{\mathfrak o}
\newcommand{\fq}{\mathfrak q}
\newcommand{\fr}{\mathfrak r}
\newcommand{\fm}{\mathfrak m}
\newcommand{\fp}{\mathfrak p}
\newcommand{\pp}{\mathfrak p}
\newcommand{\fZ}{\mathfrak Z}
\newcommand{\tfp}{\tilde \fp}
\newcommand{\Cs}{{\mathcal C}}
\renewcommand{\H}{{\mathcal H}}
\renewcommand{\L}{{\mathcal L}}
\newcommand{\inj}{\hookrightarrow}
\newcommand{\ba}{ {\bar \alpha} }
\newcommand{\bL} {\overline L }

\newcommand{\ffp}{{\mathbb F}_p}

\newcommand{\vb}{\vec{\beta}}
\newcommand{\Kbar}{\overline K}
\newcommand{\kbar}{\overline{k}}
\DeclareMathOperator{\length}{length}
\DeclareMathOperator{\Alg}{Alg}
\DeclareMathOperator{\Per}{Per}
\DeclareMathOperator{\Fin}{Fin}
\DeclareMathOperator{\Orb}{Orb}
\DeclareMathOperator{\PSL}{PSL}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\mymod}{mod}
\def\Frac{\operatorname{Frac}}
\newcommand{\Pl}{{\mathbb P}}
\newcommand{\Qbar}{\bar{\Q}}
\newcommand{\Zbar}{\bar{\Z}}
\newcommand{\fbar}{\bar{f}}
\newcommand{\surj}{\twoheadrightarrow}
\DeclareMathOperator{\Spec}{Spec} \DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\Proj}{Proj} \DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\fin}{fin}
\DeclareMathOperator{\bNorm}{Norm}

\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Disc}{Disc}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\N}{N}
\DeclareMathOperator{\Norm}{Norm}
\DeclareMathOperator{\tth}{^{th}}
\DeclareMathOperator{\trdeg}{trdeg}
\DeclareMathOperator{\sep}{sep}
\DeclareMathOperator{\red}{red}
\DeclareMathOperator{\tor}{tor}
\DeclareMathOperator{\car}{char}
\DeclareMathOperator{\group}{\GL_d\left(\widehat{A}\right)}
\DeclareMathOperator{\aut}{Gal(K^{\sep}/K)}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\CC}{\mathbb{C}_{\infty}}
\DeclareMathOperator{\Pic}{Pic}
\DeclareMathOperator{\bNum}{Num}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\smooth}{smooth}
\DeclareMathOperator{\order}{order}
\DeclareMathOperator{\hor}{hor}
\DeclareMathOperator{\ver}{ver}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\Div}{div}
\DeclareMathOperator{\Ar}{Ar}
\DeclareMathOperator{\mg}{MG}
\DeclareMathOperator{\finite}{finite}
\DeclareMathOperator{\bN}{\mathbb{N}}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\PGL}{PGL}
\newcommand{\isomto}{\overset{\sim}{\rightarrow}}
\newcommand{\prob}{{\operatorname{Prob}}}
\newcommand{\cycle}{{\mathcal{C}}}
\newcommand{\ramification}{{\mathcal{R}}}
\newcommand{\erfc}{{\operatorname{erfc}}}
\newcommand{\A}{{\mathbb A}}
%\newcommand{\fp}{{\mathbb F}_p}

\newcommand{\kb}{{\bar k}}
\newcommand{\bP}{{\mathbb P}}
\newcommand{\bZ}{{\mathbb Z}}
\newcommand{\bG}{{\mathbb G}}
\newcommand{\Zp}{{\mathbb{Z}_p}}
\newcommand{\bM}{{\mathbb M}}
\newcommand{\bC}{{\mathbb C}}
\newcommand{\bR}{{\mathbb R}}
\newcommand{\bA}{{\mathbb A}} 
\newcommand{\bQ}{{\mathbb Q}}
\newcommand{\bF}{{\mathbb F}}
\newcommand{\Fq}{\bF_q}
\newcommand{\lra}{\longrightarrow}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\bQb}{\bar{\bQ}}
\newcommand{\bK}{\overline{K}}
\newcommand{\hhat}{{\widehat h}}

\newcommand{\Drin}{{\bf \varphi}}

\newcommand{\Cp}{\bC_p}
\newcommand{\PCp}{\bP^1(\bC_p)}
\newcommand{\PCv}{\bP^1(\bC_v)}

\newcommand{\Dbar}{\overline{D}}


\begin{document}

\section*{Assignment 1: Due Jan. 31, 2019}

\begin{enumerate}
\item Let $X$ be a set and let $V\subseteq k\langle X\rangle$ denote the $k$-span of the elements of $X$.  For each $i\ge 1$, let $V^i$ denote the $k$-span of all products of $i$ elements of $V$.  Show that $$k\langle X\rangle = k\oplus V\oplus V^2 \oplus V^3 \oplus \cdots .$$
\item A Lie algebra is a $k$-vector space $V$ with a $k$-bilinear map $[\, \cdot \, , \, \cdot \, ]: V\times V\to V$ (called a Lie bracket) that satisfies $[v,w]=-[w,v]$ for $v,w\in V$ and $[[v,w],u] = [[v,u],w] + [v,[w,u]]$ (the Jacobi identity) for all $v,w,u\in V$.  Show that if $R$ is an associative algebra then $[r,s]:=rs-sr$ is a Lie bracket and makes $R$ a Lie algebra.
\item   Let $X$ be a set with order $<$, and suppose that we extend $<$ to a degree lexicographic order on $X^*$ and let $V\subseteq k\langle X\rangle$ denote the $k$-span of the elements of $X$.  Suppose that $V$ has a Lie bracket $[\, \cdot \, , \, \cdot \, ]$. Show that the set $S$ given by
$\{yx - xy - [x,y] \colon y>x, ~{\rm with}~ y,x\in X\}$ is a Gr\"obner-Shirshov basis with respect to $<$.
\item  Let $X$ be a set with order $<$, and suppose that we extend $<$ to a degree lexicographic order on $X^*$ and let $V\subseteq k\langle X\rangle$ denote the $k$-span of the elements of $X$.  Suppose that $V$ has a Lie bracket $[\, \cdot \, , \, \cdot \, ]$. Show that if $I$ Is the ideal generated by 
$\{yx - xy - [x,y] \colon y>x, ~{\rm with}~y,x\in X\}$ then $k\langle X\rangle/I$ has a basis consisting of images of monomials of the form $x_1 x_2 \cdots x_s$ with $s\ge 0$ and $x_1,\ldots ,x_s\in X$ with $x_1\le x_2\le \cdots \le x_s$.
\item Let $X=\{A,C,T,G\}$ and let $f(n)$ denote the number of words of length $n$ over the alphabet $A,C,T,G$ that do not have $GAT$ or $TAG$ as subwords. Find a linear recurrence satisfied by $f(n)$.
\item  Let $k$ be a field and let $R=k[x,y]/I$ (so $R$ is commutative!) where $I$ is generated by the polynomials $x^2+y^3-2$ and $x^3+y^2-2$.  Show that $R$ is finite-dimensional and find its dimension.  
\item For the next few exercises, we'll work with a commutative ring $R=k[x_1,\ldots ,x_d]/I$.  Suppose that we put some order on $\{x_1,\ldots ,x_d\}$ and use this to impose a degree lexicographic order on (commutative) monomials in $x_1,\ldots ,x_d$.  Let $V$ be the image of the space $k+kx_1+\cdots +kx_d$ in $R$.  Show that $V^n$ has dimension given by the size of the set of monomials $m$ in ${\rm Irr}(S)$ of degree at most $n$.  
\item  The Hilbert series of the commutative ring $R=k[x_1,\ldots ,x_d]/I$ is defined as follows.  One puts a degree lexicographic order on monomials in $x_1,\ldots ,x_d$ and computes a Gr\"obner basis $S$ for $I$. Then one lets $T$ denote the set of monomials in ${\rm Irr}(S)$ and finally one lets $f(n)$ denote the number of monomials of length $n$ in ${\rm Irr}(S)$.  Then one defines the Hilbert series to be the formal power series
$$\sum_{n\ge 0} f(n) t^n\in \mathbb{Z}[[t]].$$ Show that the Hilbert series is independent of how one assigns the order on $x_1,\ldots ,x_d$ when giving the degree lexicographic order. (Hint: use the preceding question).
\item Show that the Hilbert series of the ring $R$ is the power series expansion of a function of the form $P(t)/Q(t)$ where $P(t)$ and $Q(t)$ are integer polynomials, $Q(0)=1$, and all the roots of $Q(t)$ are roots of unity.  (Hint: first use the fact that in the commutative case that Gr\"obner bases are finite to show that $f(n)$ satisfies a linear recurrence.  Next use this fact to show that the Hilbert series is of the form $P(t)/Q(t)$ with $P$ and $Q$ integer polynomials and $P(0)=1$.  Finally, show that if $f(n)$ is the coefficient of $t^n$ in the Hilbert series of $R$ then $f(n)\le n^d$ and use this to show that $Q(t)$ must have all of its roots as roots of unity.


\end{enumerate}
\end{document}
