\documentclass[10pt]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[all]{xy}

\title{\sol{}{Solutions to }Final Exam}
\author{Math 401}
\date{\sol{April 26, 2015}{}}

\newcommand \Q {\mathbb Q}
\newcommand \R {\mathbb R}
\newcommand \Z {\mathbb Z}

\renewcommand \phi \varphi

\renewcommand \labelenumi {(\alph{enumi})}

\newcommand \sol[2] {#1}

\begin{document}
\maketitle

\paragraph{1.} Recall that a group $G$ is called \emph{cyclic} if there is an element $g \in G$ such that every element of $G$ is a power of $g$:
\[ G = \{ 1, g^{\pm 1}, g^{\pm 2}, g^{\pm 3}, \dotsc \}. \]
\begin{enumerate}
\item Show that if $G$ is cyclic and $H$ is a subgroup of $G$ then $H$ is cyclic.  Hint: Let $k$ be the least positive integer such that $g^k \in H$.  If $g^l$ is any other element of $H$ then $k \mid l$; otherwise by long division we can write $l = qk + r$ for some $0 < r < k$, so\dots

\sol{}{{\bf Solution:} Following the hint, let $k$ be the least positive integer such that $g^k \in H$.  If $g^l$ is any other element of $H$ then $k \mid l$; otherwise by long division we can write $l = qk + r$ for some $0 < r < k$, but then $g^r = g^l \cdot (g^k)^{-q}$ is in $H$, contradicting the minimality of $k$.  Thus every element of $H$ is a power of $g^k$, so $H$ is cyclic.}

\renewcommand \thefootnote {\fnsymbol{footnote}}
\item Consider a Rubik's cube.  You might hope there is some clever sequence of moves such that if you take any mixed-up cube and make this sequence of moves over and over, you will eventually get to the ``solved'' position, no matter where you started.  Show that this is not the case by observing that the symmetry group $G$ of the Rubik's cube contains a copy of $\Z_4 \times \Z_4$, given by rotating the top and the bottom, and this is not a cyclic group.\footnote{There is an algorithm for solving the Rubik's cube, but it is not as simple as ``make this sequence of moves over and over.''}

\sol{}{{\bf Solution:} Suppose on the contrary that there were such a sequence of moves $g = g_1 g_2 \dotsm g_k \in G$.  Then we could get from the ``solved'' position to any mixed-up position by some power $g^{-m}$, so $G$ would be cyclic.  But the (injective) map $\Z_4 \times \Z_4 \to G$ which sends $(a,b)$ to ``rotate the top through $a$ quarter-turns and the bottom through $b$ quarter-turns'' is a homomorphism, since rotating the top commutes with rotating the bottom.  Thus $G$ has a subgroup that is not cyclic -- indeed, if $\Z_4 \times \Z_4$ were cyclic then it would have an element of order 16, but in fact all its elements have order dividing 4.  Thus $G$ is not cyclic.

You can also see that $G$ is not cyclic by observing that it is not abelian: rotating the top does not commute with rotating the left side, for example; but this is harder to see without a cube in hand.

The Rubik's cube group is actually very far from being cyclic: its order is $2^{27}3^{14} 5^3 7^2 11 \approx 4.3 \times 10^{19}$, but the largest cyclic subgroup has order $1260$.}

\end{enumerate}


\paragraph{2.} Let $S_n$ denote the symmetric group on $n$ letters.
\begin{enumerate}
\item Show that an $m$-cycle $(a_1\,a_2\,\dotsm\,a_m)$ is an even permutation if and only if $m$ is odd.  Hint: The point is just to remember how to factor $\sigma$ as a product of transpositions.

\sol{}{{\bf Solution:} We have
\[ (a_1\ a_2\ \dotsm\ a_m) = (a_1\ a_m)\dotsm(a_1\ a_3)(a_1\ a_2), \] as we saw in class, or alternatively,
\[ (a_1\ a_2\ \dotsm\ a_m) = (a_1\ a_2)(a_2\ a_3) \dotsm (a_{m-1}\ a_m). \]
Either way this is a product of $m-1$ transpositions, and $m-1$ is even if and only if $m$ is odd.}

\item Let $A_n \subset S_n$ be the subgroup of even permutations; then the order of $A_n$ is half that of $S_n$.  Why?

\sol{}{{\bf Solution:} Fix a transposition $\tau$.  I claim that there are only two cosets of $A_n$ in $S_n$: the even permutations $A_n$ and the odd permutations $\tau A_n$.  Indeed, suppose that $\sigma$ is odd; then we can write $\sigma = \tau \cdot \tau \sigma$, and $\tau\sigma$ is even, so $\sigma \in \tau A_n$.}

\item List the 12 elements of $A_4$, in cycle notation.

\sol{}{{\bf Solution:} By part (a) we can skip the 2-cycles and the 4-cycles, which leaves the identity, the 3-cycles, and the products of two 2-cycles:
\[ \xymatrix@R=5pt@C=5pt{
\operatorname{id} \\
(1\ 2\ 3) & (1\ 2\ 4) & (1\ 3\ 4) & (2\ 3\ 4) \\
(1\ 3\ 2) & (1\ 4\ 2) & (1\ 4\ 3) & (2\ 4\ 3) \\
(1\ 2)(3\ 4) & (1\ 3)(2\ 4) & (1\ 4)(2\ 3)
} \]}

\item Let $A_4$ act on itself by conjugation.  How many orbits are there?  How many elements are in each orbit?  Hint: To save time, it is enough to see how $(1\ 2)(3\ 4)$, $(1\ 3)(2\ 4)$, and $(1\ 4)(2\ 3)$ act on the 3-cycles, and how $(1\ 2\ 3)$ acts on the products of 2-cycles; then note that conjugation preserves cycle type, and there is no orbit of order eight (why?), so the orbits can't get any bigger than what you've already found at this point.  \sol{Further hint: If this is taking you forever, go work on another problem and maybe come back later.}{

{\bf Solution:} Conjugating by $(1\ 2)(3\ 4)$ acts as follows:
\[ \xymatrix@R=2pt@C=5pt{
\operatorname{id} \ar@(ur,dr)[] \\ \\
(1\ 2\ 3) \ar@{<->}[ddr] & (1\ 2\ 4) \ar@{<->}[ddl] & (1\ 3\ 4) \ar@{<->}[ddr] & (2\ 3\ 4) \ar@{<->}[ddl] \\ \\
(1\ 3\ 2) & (1\ 4\ 2) & (1\ 4\ 3) & (2\ 4\ 3) \\ \\
(1\ 2)(3\ 4) \ar@(dl,dr)[]& (1\ 3)(2\ 4) \ar@(dl,dr)[] & (1\ 4)(2\ 3) \ar@(dl,dr)[]
} \]
Conjugating by $(1\ 3)(2\ 4)$ acts as follows:
\[ \xymatrix@R=2pt@C=5pt{
\operatorname{id} \ar@(ur,dr)[] \\ \\
(1\ 2\ 3) \ar@{<->}@/^1em/[rr] & (1\ 2\ 4) \ar@{<->}@/_1em/[rr] & (1\ 3\ 4) & (2\ 3\ 4) \\ \\
(1\ 3\ 2) \ar@{<->}@/^1em/[rr] & (1\ 4\ 2) \ar@{<->}@/_1em/[rr] & (1\ 4\ 3) & (2\ 4\ 3) \\ \\
(1\ 2)(3\ 4) \ar@(dl,dr)[]& (1\ 3)(2\ 4) \ar@(dl,dr)[] & (1\ 4)(2\ 3) \ar@(dl,dr)[] \\
&
} \]
Conjugating by $(1\ 4)(2\ 3)$ acts as follows:
\[ \xymatrix@R=2pt@C=5pt{
\operatorname{id} \ar@(ur,dr)[] \\ \\
(1\ 2\ 3) \ar@{<->}[ddrrr] & (1\ 2\ 4) \ar@{<->}[ddr] & (1\ 3\ 4) \ar@{<->}[ddl] & (2\ 3\ 4) \ar@{<->}[ddlll] \\ \\
(1\ 3\ 2) & (1\ 4\ 2) & (1\ 4\ 3) & (2\ 4\ 3) \\ \\
(1\ 2)(3\ 4) \ar@(dl,dr)[]& (1\ 3)(2\ 4) \ar@(dl,dr)[] & (1\ 4)(2\ 3) \ar@(dl,dr)[] \\
&
} \]
Conjugating by $(1\ 2\ 3)$ acts as follows:
\[ \xymatrix@R=2pt@C=5pt{
\operatorname{id} \ar@(ur,dr)[] \\ \\
(1\ 2\ 3) \ar@(ul,dl)[] & (1\ 2\ 4) \ar@/^1em/[rr] & (1\ 3\ 4) \ar[ddl] & (2\ 3\ 4) \ar[ddl] \\ \\
(1\ 3\ 2) \ar@(ul,dl)[] & (1\ 4\ 2) \ar@/_1em/[rr] & (1\ 4\ 3) \ar[uul] & (2\ 4\ 3) \ar[uul] \\ \\
(1\ 2)(3\ 4) \ar@/_1em/[rr] & (1\ 3)(2\ 4) \ar[l] & (1\ 4)(2\ 3) \ar[l]
} \]
Thus there are at most four orbits:
\begin{gather*}
\{\ \operatorname{id}\ \} \\
\{\ (1\ 2\ 3),\ (1\ 3\ 4),\ (1\ 4\ 2),\ (2\ 4\ 3)\ \} \\
\{\ (1\ 2\ 4),\ (2\ 3\ 4),\ (1\ 3\ 2),\ (1\ 4\ 3)\ \} \\
\{\ (1\ 2)(3\ 4),\ (1\ 3)(2\ 4),\ (1\ 4)(2\ 3)\ \}.
\end{gather*}
Now we might worry that one of the other seven 3-cycles will connect up two or more of these orbits to make a bigger one.  But conjugation preserves cycle type, that is, it cannot turn a 3-cycle into a product of two 2-cycles, so the worst that could happen is that the two middle orbits (of four 3-cycles each) might become one.  But by the orbit-stabilizer theorem, the order of an orbit divides the order of the group, and 8 does not divide 12, so these two orbits will not become one big one. }
\end{enumerate}


\paragraph{3.} Let $R$ be a ring and $S$ a subring.  Show that if $I$ is an ideal of $R$ then $J = I \cap S$ is an ideal of $S$.  Show that if $I$ is a prime ideal of $R$ then $J$ is a prime ideal of $S$.

\sol{}{{\bf Solution:} First we argue that $J$ is an ideal.  Let $j \in J$ and $s \in S$ be given.  Then $j \in S$, so $sj \in S$ because $S$ is a subring.  And $s \in R$ and $j \in I$, so $sj \in I$ because $I$ is an ideal.  Thus $sj \in I \cap S = J$; so $J$ is an ideal of $S$.

Next we suppose that $I$ is prime -- that is, for all $a, b \in R$ we have $ab \in I \Rightarrow a \in I$ or $b \in I$ -- and we argue that $J$ is prime.  Let $c,d \in S$ be given, and suppose that $cd \in J$; then $cd \in I$, so $c \in I$ or $d \in I$, and still $c, d \in S$, so $c \in I \cap S = J$ or $d \in I \cap S = J$.  Thus $J$ is a prime ideal of $S$.}

\paragraph{4.} Let $S = \Z[\sqrt{-3}]$, and let $R = \Z[\omega]$, where $\omega = e^{2\pi i/3} = \frac{-1 + \sqrt{-3}}{2}$ is a cube root of unity.  Observe that $\sqrt{-3} = 2\omega+1$, so $S$ is a subring of $R$, and that both are subrings of $\mathbb C$ and thus in particular integral domains.  Here is a picture of $R$, with the subring $S$ shown in heavier dots:
\begin{center}
\setlength \unitlength {3pt}
\begin{picture}(60,40)(-30,-20)
  \put(-20,17.32){\circle* 2}
  \put(-10,17.32){\circle* 2}
  \put(0,17.32){\circle* 2}
  \put(10,17.32){\circle* 2}
  \put(20,17.32){\circle* 2}

  \put(-25,8.66){\circle* 1}
  \put(-15,8.66){\circle* 1}
  \put(-5,8.66){\circle* 1}
  \put(5,8.66){\circle* 1}
  \put(15,8.66){\circle* 1}
  \put(25,8.66){\circle* 1}

  \put(-20,0){\circle* 2}
  \put(-10,0){\circle* 2}
  \put(0,0){\circle* 2}
  \put(10,0){\circle* 2}
  \put(20,0){\circle* 2}

  \put(-25,-8.66){\circle* 1}
  \put(-15,-8.66){\circle* 1}
  \put(-5,-8.66){\circle* 1}
  \put(5,-8.66){\circle* 1}
  \put(15,-8.66){\circle* 1}
  \put(25,-8.66){\circle* 1}

  \put(-20,-17.32){\circle* 2}
  \put(-10,-17.32){\circle* 2}
  \put(0,-17.32){\circle* 2}
  \put(10,-17.32){\circle* 2}
  \put(20,-17.32){\circle* 2}
 
  \put(-25,0){\line(1,0){50}}
  \put(0,-20){\line(0,1){40}}

  \put(-7,9.66){$\omega$}
  \put(11,1){1}
  \put(21,1){2}
  \put(-7,-7.66){$\bar\omega$}
  \put(-2,19.32){$\scriptstyle \sqrt{-3}$}
  \put(7,19.32){$\scriptstyle 1+\sqrt{-3}$}
  \put(7,-15.32){$\scriptstyle 1-\sqrt{-3}$}
\end{picture}\end{center}

\begin{enumerate}
\item Observe that if $z = a + b \sqrt{-3} \in S$ then $|z|^2 = a^2 + 3b^2$, which is a non-negative integer for all $a,b \in \Z$.  Conclude that $z$ is a unit in $S$ if and only if $|z| = 1$.  List the units in $S$.  Hint: There are two.

\sol{}{{\bf Solution:} It is clear that $a^2+3b^2$ is a non-negative integer.

If $z$ is a unit then there is a $w \in R$ such that $zw = 1$, so $|z|^2|w|^2 = 1$, and since $|z|^2$ and $|w|^2$ are both non-negative integers this implies that $|z|^2=1$.  Conversely, if $|z|^2 = 1$ then $z \bar z = 1$, so $\bar z = a - b\sqrt{-3} \in S$ is an inverse for $z$, so $z$ is a unit.

From the picture we see that the only elements $z \in R$ with $|z| = 1$ are $\pm 1$.}

\item Observe that if $z = a + b\omega \in R$ then $|z|^2 = a^2-ab+b^2$, which is a non-negative integer for all $a,b\in \Z$: non-negative because it's $|z|^2$, and an integer because it's $a^2-ab+b^2$.  Conclude that $z$ is a unit in $R$ if and only if $|z| = 1$.  List the units in $R$.  Hint: There are six.

\sol{}{{\bf Solution:} If $z = a+b\omega$ then
\[ |z|^2 = z\bar z = (a+b\omega)(a+b\bar\omega) = a^2 + ab(\omega + \bar\omega) + b^2 \omega\bar\omega = a^2 - ab + b^2 \]
as claimed.  Or if you prefer, $z = (a - \frac{b}{2}) + \frac{b\sqrt{-3}}{2}$, so
\[ |z|^2 = (a - \tfrac{b}{2})^2 + \tfrac{3b^2}{4} = a^2 - ab + b^2. \]
Thus $|z|^2$ is a non-negative integer by the argument in the statement of the problem.

The argument that $z$ is a unit if and only if $|z|^2 = 1$ is the same as in part (a), except that it is less obvious that $\bar z \in S$ for $z = a + b\omega \in S$.  But we can see this from the picture -- it is symmetric under reflecting top-to-bottom -- or we can write $\bar\omega = -1-\omega$, so $\bar z = (a-b) -b\omega$ which is indeed in $S$.

From the picture we find six points on the unit circle: $\pm 1$ and $\frac{\pm 1 \pm \sqrt{-3}}{2}$. }

\item Show that 2 is irreducible in $S$.  Hint: Argue that there is no $z \in S$ with $|z|^2 = 2$.  Thus if $2 = zw$ then\dots

\sol{}{{\bf Solution:} There are no $a,b \in \Z$ with $a^2+3b^2 = 2$: indeed, if $b \ne 0$ then $a^2+3b^2 \ge 3$, so we must have $b = 0$, but then $a^2 = 2$ which is impossible.  Thus there is no $z \in S$ with $|z|^2 = 2$.

Now if $2 = z \cdot w$ then we have $4 = |z|^2 |w|^2$, so either $|z|^2 = 1$ and $|w|^2 = 4$, so $z$ is a unit, or $|z|^2 = |w|^2 = 2$, which we just saw is impossible, or $|z|^2 = 4$ and $|w|^2 = 1$, so $w$ is a unit.  Thus 2 is irreducible in $S$.}

\item Observe that $4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3})$.  Conclude that 2 is not prime in $S$.

\sol{}{{\bf Solution:} We have $2 \mid 4 = (1 + \sqrt{-3})(1-\sqrt{-3})$, but clearly $1 \pm \sqrt{-3}$ are not of the form $2(a + b\sqrt{-3})$, that is, $2 \nmid 1 \pm \sqrt{-3}$. }

\item I was going to ask you to show that 2 is prime (and hence irreducible) in $R$, but this turns out to be a pain.

\sol{}{{\bf Solution:} On the one hand you can make a high-tech argument: $\omega$ is a root of $x^2+x+1 \in \Z[x]$, so $R \cong \Z[x]/(x^2+x+1)$, so $R/(2) \cong \Z_2[x]/(x^2+x+1)$, and $x^2+x+1$ is irreducible in $\Z_2[x]$, so this is a field.  But arguing that $R \cong \Z[x]/(x^2+x+1)$ requires some care because $\Z$ is not a field; and you have to remember the day in lecture when we showed that the kernel of a map to a field is a prime ideal, and apply this to $R \to R/(2)$.

On the other hand you can make a low-tech argument, fiddling with coefficients for a long time to show that if $2 \nmid z$ and $2 \nmid w$ then $2 \nmid zw$.

On the third hand you could show that there are no $z \in R$ with $|z|^2 = 2$, so 2 is irreducible in $R$, and then prove that $R$ has a division algorithm, so irreducible implies prime.}

\item Show that the ideals generated by 2 and $1-\sqrt{-3}$ in $R$ are the same, but that the ideals they generate in $S$ are different.  Hint: Recall from homework that $(a) = (b)$ if and only if there is a unit $u$ such that $a = ub$.  Warning: Consider writing $(2)_R$ and $(2)_S$ rather than just $(2)$ to avoid confusion.

\sol{}{{\bf Solution:} We know that $-\omega = \frac{1-\sqrt{-3}}{2}$ is a unit in $R$, so we have $1-\sqrt{-3} = -2\omega$, so $(1-\sqrt{-3})_R = (2)_R$ by the homework problem recalled in the hint.  In $S$ however, $1-\sqrt{-3}$ is not a multiple of $2$, because its coefficients are odd, so $1-\sqrt{-3} \notin (2)_S$ and thus $(1-\sqrt{-3})_S \ne (2)_S$.}

\item Let $I = (2)_R \subset R$ and $J = I \cap S$.  Show that $J = (2,1-\sqrt{-3})_S$, and that this is not a principal ideal.  Hint: It is clear that $2 \in I \cap S$ and $1-\sqrt{-3} \in I \cap S$; for the reverse containment, note that a general element of $I$ is of the form $2(a + b\omega)$, and multiply that out.

\sol{}{{\bf Solution:} Clearly $2 \in J$, and we just saw that $1-\sqrt{-3} \in I$, so it is in $J = I \cap S$ as well.  For the reverse containment, a general element of $I$ is of the form
\[ 2a + 2b \omega = 2a + b(-1 + \sqrt{-3}) = a\cdot 2 - b \cdot(1-\sqrt{-3}) \]
for $a, b \in \Z$, and this is in $(2,1-\sqrt{-3})_S$.

Suppose we could write $J = (z)_S$ for some $z \in S$.  We have $2 \in J$, so $z = 2s$ for some $s \in S$; but $2$ is irreducible in $S$, so its only factorizations are $2 \cdot 1$ and $(-2) \cdot (-1)$, 
so $z = \pm 1$ or $\pm 2$.  We have $1 - \sqrt{-3} \in J$, so $1 - \sqrt{-3} = zs'$ for some $s' \in S$, which rules out $z = \pm 2$.  But we also have $z \in I = (2)_R$, so $z = 2r$ for some $r \in R$, which rules out $z = \pm 1$.  Thus $J$ is not principal. }

\end{enumerate}

\end{document}
