\documentclass[11pt]{article} \usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim} \usepackage{enumitem} \usepackage{url} \usepackage[margin=1in]{geometry} \usepackage[all]{xy} \theoremstyle{plain} \theoremstyle{definition} \newtheorem{theorem}{Theorem} \newtheorem{fact}[theorem]{Fact} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{definition}[theorem]{Definition} \newtheorem*{definition-nonum}{Definition} \newtheorem{innerq}{Question} \newenvironment{final-question}[1]{\renewcommand\theinnerq{#1}\innerq}{\endinnerq} \newtheorem{innera}{Answer} \newenvironment{final-answer}[1]{\renewcommand\theinnera{#1}\innera}{\endinnera} \newcommand{\nextpage}[4]{ \newpage \noindent #1 \begin{final-answer}{#3} #4 \end{final-answer} \vfill \noindent\begin{tabular}{lllll} Recall:\quad #2 \end{tabular} } \newcommand{\x}{\ \ \ \ \ \ } \newcommand\rightjustify[1]{{% \unskip\nobreak\hfil\penalty50 \hskip2em\hbox{}\nobreak\hfil{#1}% \parfillskip=0pt \finalhyphendemerits=0 \par}} \newcommand\cleartooddpage{\clearpage \ifodd\value{page}\else\null\clearpage\fi} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\abs}[1]{\left\vert #1\right\vert} \newcommand{\iso}{\cong} \renewcommand{\phi}{\varphi} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Stab}{Stab} \newcommand{\YourName}[1]{ \thispagestyle{empty} \begin{center} {\Large Math 120 -- Spring 2018 -- Prof. Church\\ Final Exam: due \textbf{11:30am} on Wednesday, June 13} % %Please put your name on the \emph{next page}, not this one. \end{center} \vfill \begin{center}There are 9 questions worth 100 points total on this exam.\end{center} \begin{align*} \hspace{-20pt}\underset{\substack{\phantom{x}\\\text{100 points}}}{\begin{tabular}{||c||} \hline Total\\ \hline \x\ \ \ \ \\ \x\ \ \ \ \\ \hline \end{tabular}}~~~~~~~~~~~% &\underbrace{\begin{tabular}{||c|c|c|c||} \hline 1a&1b&1c&1d\\ \hline \x&\x&\x&\x\\ \x&\x&\x&\x\\ \hline \end{tabular}}_{\text{20 points}}~~~% \underbrace{\begin{tabular}{||c||} \hline 2\\ \hline \x\\ \x\\ \hline \end{tabular}}_{\text{5 points}}~~~% \underbrace{\begin{tabular}{||c||} \hline 3\\ \hline \x\\ \x\\ \hline \end{tabular}}_{\text{10 points}}~~~% \underbrace{\begin{tabular}{||c|c||} \hline 4a&4b\\ \hline \x&\x\\ \x&\x\\ \hline \end{tabular}}_{\text{15 points}}\\\\%~~~% &\underbrace{\begin{tabular}{||c||} \hline 5\\ \hline \x\\ \x\\ \hline \end{tabular}}_{\text{5 points}}~~~\,% \underbrace{\begin{tabular}{||c||} \hline 6\\ \hline \x\\ \x\\ \hline \end{tabular}}_{\text{5 points}}~~~\,% \underbrace{\begin{tabular}{||c||} \hline 7\\ \hline \x\\ \x\\ \hline \end{tabular}}_{\text{15 points}}~~~~% \underbrace{\begin{tabular}{||c|c||} \hline 8a&8b\\ \hline \x&\x\\ \x&\x\\ \hline \end{tabular}}_{\text{10 points}}~~~~% \underbrace{\begin{tabular}{||c|c||} \hline 9a&9b\\ \hline \x&\x\\ \x&\x\\ \hline \end{tabular}}_{\text{15 points}}% \end{align*} \newpage\hfill Name:\ #1\\ \noindent \textbf{About this exam:} {\small \noindent Your exam \textbf{must} be submitted on Canvas by 11:30am (just \textbf{before noon}) on Wednesday, June 13 or you will receive a zero.\\ This exam is open-book and open-notes, but closed-everything-else. (Needless to say, you should not discuss this exam with anyone.) In your proofs you may use any theorem from class; please \emph{contact Prof.\ Church} if you have questions about whether you can use something. You can also use any theorem or proposition from the chapters of Dummitt--Foote that we covered:\vspace{-10pt} \begin{center} \begin{tabular}{llll} Chapter 1;&Chapter 2;&Chapter 3;\\ Chapter 4;&Chapter 5.1, 5.4, 5.5;&Chapter 6.3.\\ Chapter 7;&Chapter 8\end{tabular}\end{center} {\footnotesize (We did not cover 2.5 or 4.6, but there's nothing there that helps with the exam so you don't have to avoid them.)}\\ You can use the statements of any question or exercise that was assigned as homework, but not any other exercises in the book (nor things in the book labeled as "examples"). You can read the homework solutions if you like, but you cannot quote them as a reference. You do not have to give citations from the book for every result you use, but if you are at all unsure about the statement or why the result applies, it might be a good idea to look it up and make sure.} \vfill \noindent {\small If a question says ``You do not have to prove your answer is correct", you do not have to include any proof at all if your answer is correct. However you are welcome to include justification if you want, which can be helpful for partial credit if your answer is not completely correct.} \vfill \noindent {\small If a question says ``Give a \textbf{concrete} description'' of a subset, I am looking for a self-contained explicit description of precisely which elements are in that subset, \emph{not} a restatement of the definition. For example: \newline \indent Q: ``Give a concrete description of the units in $\Z$.'' \begin{enumerate}[itemsep=0pt] \item[BAD:] ``elements of $\Z$ which have a multiplicative inverse in $\Z$.'' \item[BAD:] ``$\{x\in \Z\,|\,\exists y\in \Z\text{ s.t. }xy=1\}$'' \item[GOOD:] $\{\pm 1\}$ \end{enumerate} Q: ``Give a concrete description of the ideal $(1+i)\subset \Z[i]$.'' \begin{enumerate}[itemsep=0pt] \item[BAD:] ``all the multiples of $1+i$.'' \item[BAD:] ``the set of elements $a+bi$ for which there exists some $c+di\in \Z[i]$ such that $(a+bi)=(1+i)(c+di)$'' \item[GOOD:] $\big\{a+bi\in \Z[i]\,\big|\,a+b\equiv 0\bmod2\big\}$ \end{enumerate} If you are not sure whether your description is concrete, you can ask Prof.\ Church. \vfill \begin{center} {\large Questions? E-mail Prof.\ Church at \url{tfchurch@stanford.edu}\newline or post a \textbf{private, non-anonymous} question on Piazza.} \end{center} } \cleartooddpage } \newcommand{\QuestionOnePartA}[1]{ \begin{final-question}{1}[{{\small 20 points}}] For each $a\in \R$, there is exactly one ring homomorphism $\phi_a\colon \Z[x]\to \R$ satisfying $\phi_a(x)=a$. Consider the ideal $K_a=\ker(\phi_a)$ which is the kernel of this ring homomorphism. \begin{enumerate} \item[(a)] {\small(6 points)} For $a=\frac{2}{3}$, the ideal $K_a$ is principal.\newline Prove this by finding a generator $f(x)\in \Z[x]$ for this ideal and proving that $K_a=\big(f(x)\big)$. \end{enumerate} \end{final-question} \begin{final-answer}{1(a)} #1 \end{final-answer} } \newcommand{\QuestionOnePartB}[1]{ \vspace{30pt} \begin{enumerate} \item[(b)] {\small(4 points)} Give an explicit $a\in \R$ for which $\phi_a$ is injective. \newline In a sentence or two, explain which features of the real number $a$ are relevant here.\newline {\footnotesize (You do not have to prove it has those features.)} \end{enumerate} \begin{final-answer}{1(b)} #1 \end{final-answer} } \newcommand{\QuestionOnePartC}[1]{ \clearpage \begin{enumerate} \item[(c)] {\small(4 points)} Prove that for any $a\in \R$, the ideal $K_a$ is a prime ideal. \end{enumerate} \begin{final-answer}{1(c)} #1 \end{final-answer} } \newcommand{\QuestionOnePartD}[1]{ \vspace{30pt} \begin{enumerate} \item[(d)] {\small(6 points)} Prove that $K_a$ is never a maximal ideal for any $a\in \R$. \end{enumerate} \begin{final-answer}{1(d)} #1 \end{final-answer} } \newcommand{\QuestionTwo}[1]{ \cleartooddpage \begin{final-question}{2}[{{\small 5 points}}] Suppose that $G$ is a group generated by three elements $a,b,c\in G$.\newline Prove that $G$ has at most 8 normal index-2 subgroups. \end{final-question} \begin{final-answer}{2} #1 \end{final-answer} } \newcommand{\QuestionThree}[1]{ \clearpage \begin{final-question}{3}[{{\small 10 points}}] Let $R=\Z[y]$, and let $I$ be the ideal $(100000000003,y^{100000000002}-1)$. Prove that $I$ is not a prime ideal.\newline {\footnotesize(Note: 100000000003 is a prime number, intentionally chosen to be too large for you to do much with.)} \end{final-question} \begin{final-answer}{3} #1 \end{final-answer} } \newcommand{\QuestionFourPartA}[1]{ \cleartooddpage \begin{final-question}{4}[{{\small 15 points}}] Let $G$ be a group of order $\abs{G}=700$, and suppose you are given a transitive action of $G$ on a set $X=\{x_1,\ldots,x_{100}\}$ of size 100. Let $g\in G$ be an element of order 7. \begin{enumerate} \item[(a)] {\small(7 points)} Prove that $g$ fixes some element of $X$ {\small (i.e.\ there exists some $x_i\in X$ such that $g\cdot x_i=x_i$).} \end{enumerate} \end{final-question} \begin{final-answer}{4(a)} #1 \end{final-answer} } \newcommand{\QuestionFourPartB}[1]{ \clearpage \begin{enumerate} \item[(b)] {\small(8 points)} Moreover, prove that one of the following holds: \begin{enumerate} \item[I.] $g$ fixes all 100 elements of $X$, or \item[II.] $g$ fixes exactly 2 elements of $X$. \end{enumerate} \end{enumerate} \begin{final-answer}{4(b)} #1 \end{final-answer} } \newcommand{\QuestionFive}[1]{ \clearpage \begin{final-question}{5}[{{\small 5 points}}] Let $C(\R)$ be the ring of continuous functions on the real line: \[C(\R)=\{f\colon \R\to \R\,|\,f\text{ is continuous}\}.\] Give a concrete description of which elements of this ring are units. {\small (You do not need to prove your answer is correct.)} \end{final-question} \begin{final-answer}{5} #1 \end{final-answer} } \newcommand{\QuestionSix}[1]{ \clearpage \begin{final-question}{6}[{{\small 5 points}}] Let $\text{OddDenom}$ ($\text{OD}$ for short) be the subring of $\Q$ consisting of all rational numbers whose denominator (when in lowest terms) is odd: \[\text{OD}=\text{OddDenom}=\left\{\left.\ \frac{p}{q}\in \Q\ \right\vert\ q\text{ is odd }\ \right\}.\]Prove that $\text{OddDenom}$ is a PID. \end{final-question} \begin{final-answer}{6} #1 \end{final-answer} } \newcommand{\QuestionSeven}[1]{ \clearpage \begin{final-question}{7}[{{\small 15 points}}] Let $A$ and $B$ be the groups with presentations \begin{align*}A&=\langle x,t\,|\,t^2=1,txt^{-1}=x^{-1}\rangle\\ B&=\langle r,s\,|\,r^2=1,s^2=1\rangle \end{align*} Prove that $A$ is isomorphic to $B$. \end{final-question} {\footnotesize (Possible hint: the group $A$ can be identified with the group $APB(\Z)$ of adjacency-preserving bijections of $\Z$, where $x$ corresponds to a translation and $t$ corresponds to a reflection. The group $B$ can also be identified with $APB(\Z)$, where $r$ and $s$ correspond to e.g.\ $f(x)=3-x$ and $g(x)=2-x$. Note: you do \textbf{not} have to use this approach at all. Or, you can just rely on this idea for motivation without actually using it in your proof. But if you do want to use it in your proof, you need to prove everything that you use. The one exception is that every element of $APB(\Z)$ either has the form $f(x)=n+x$ or $f(x)=n-x$ for a unique $n\in \Z$; you may use this without proof.)} \begin{final-answer}{7} #1 \end{final-answer} } \newcommand{\QuestionEightPartA}[1]{ \clearpage \begin{final-question}{8}[{{\small 10 points}}] Fix some $n\geq 3$, and let $R=\Z[\sqrt{-n}]=\{a+b\sqrt{-n}\,|\,a,b\in \Z\}$.\newline {\footnotesize (You may use without proof that $N\colon R\to \N$ given by $N(a+b\sqrt{-n})=a^2+nb^2$ satisfies $N(xy)=N(x)N(y)$.)} \begin{enumerate} \item[(a)] {\small(3 points)} Prove that $R^\times=\{\pm 1\}$, and that 2 is irreducible in $R$. \end{enumerate} \end{final-question} \begin{final-answer}{8(a)} #1 \end{final-answer} } \newcommand{\QuestionEightPartB}[1]{ \vspace{30pt} \begin{enumerate} \item[(b)] {\small(7 points)} Prove that $R$ is not a UFD. \end{enumerate} \begin{final-answer}{8(b)} #1 \end{final-answer} } \newcommand{\QuestionNinePartA}[1]{ \clearpage \begin{final-question}{9}[{{\small 15 points}}] Let $G$ be the group of physically-realizable symmetries of a cube,\footnote{If it helps, you can use the concrete cube $C=\{(x,y,z)\in \R^3\,|\,-1\leq x,y,z\leq 1\}$, or any other~description~you~like.} which has $\abs{G}=24$ elements.\footnote{If you are getting 48 elements, it's because you're including symmetries that aren't physically realizable, like ``turn the cube inside out''; we are only interested in the symmetries that you could actually do to a physical cube by picking it up, moving it around in your hand, then putting it back where it started.} For this question, it might be worth actually getting a physical cube that you can experiment with (a cardboard box, some dice, a really really thick book, etc.) \begin{enumerate} \item[(a)] {\small(10 points)} Give a concrete description of the conjugacy classes $C_1=\{\text{id}\}$, $C_2$, $\ldots,$ $C_k$ of $G$.\newline Your description should allow me to easily tell:\begin{enumerate}[label={\ },topsep=0pt,itemsep=0pt,parsep=0pt] \item How many conjugacy classes are there? \item What is the size of each conjugacy class? \item For a given group element, which of your conjugacy classes does it belong to?\footnote{Note that you do not necessarily have to label all the elements of $G$, as long as you can correctly describe which things are in which conjugacy class. For example, if this were Q2 from the midterm, a perfectly fine answer would be ``the next conjugacy class $C_2$ consists of all reflections across lines $y=a$ for $a\in \Z$ or $x=b$ for $b\in \Z$'', and so on.} \end{enumerate} {\small (You do not need to prove your answer is correct.)} \end{enumerate} \end{final-question} \begin{final-answer}{9(a)} #1 \end{final-answer} } \newcommand{\QuestionNinePartASizes}[1]{ #1 } \newcommand{\QuestionNinePartB}[1]{ \clearpage \begin{enumerate} \item[(b)] {\small(5 points)} Suppose the six faces of the cube are labeled by the numbers 1, 2, 3, 4, 5, 6. (I will let you choose which numbers to put where, but you need to fix one labeling once and for all.) The action of $G$ on the numbered faces then determines a homomorphism $f\colon G\to S_6$. This homomorphism is injective (you may assume this without proof), so its image is a subgroup $H