Problem 2

Most people recognized that the $\lesssim$ relation is divisibility. In other words, $$n\lesssim m\iff n|m$$ and efficient solutions to this problem proved this first.

The most efficient way to prove this fact is to use the following proposition.

Proposition: If $G$ is cyclic of order $n$, then every subgroup of $G$ is cyclic of order $d|n$, and there is a unique such subgroup for each divisor. This is Theorem 7 of DF on page 58.

Since the image of an injective homomorphism is a subgroup, and, if $H$ is a subgroup of $G$ the inclusion map is an injective homomorphism, we see from the theorem that there is an injective homomorphism from $\Zn{d}$ to $\Zn{n}$ if and only if $d|n$.

If you use surjective homomorphisms instead of injective ones, the relation is reversed. That is to give a surjective homomorphism $f:\Zn{n}\to \Zn{m}$ is equivalent to specifying the kernel of $f$, which is a subgroup of $\Zn{n}$. So there is a surjective map $\Zn{n}\to\Zn{m}$ if and only if $m|n$.

Problem 3

The matrix problems are just a lot of calculations. A number of people observed that you can consider these problems over arbitrary fields, not just $\R$.

The last problem was the trickiest for most people. There are two parts to it. Let $H=\langle (1 2 \ldots n)\rangle.$ You have to show:

1. For all $(a,n)=1$ and all $b\in \Zn{n}$, you have $\sigma_{a,b}\in N_{G}(H)$.
2. If $\alpha\in N_{G}(H)$, then $\alpha=\sigma_{a,b}$ for some $a,b$ with $(a,n)=1$.

We view permutations as functions from $\Zn{n}$ to itself. The cycle $(1 2 \ldots n)$ is the function $f(x)=x+1\pmod{n}$ and $H$ consists all together of the functions $\sigma_{1,k}$ where $\sigma_{1,k}(x)=x+k\pmod{n}$ for $k=0,\ldots,n-1$.

Now if $(a,n)=1$, then $\sigma_{a,b}$ is a bijective function from $\Zn{n}$ to itself. Since the group action in $S(\Zn{n})$ is composition of function, for part 1 we need to check that, for each $k=0,\ldots, n-1$, we have $k’$ so that $$\sigma_{a,b}\sigma_{1,k}\sigma_{a,b}^{-1}=\sigma_{1,k'}$$ Since $\sigma_{a,b}^{-1}=\sigma_{a^{-1},-a^{-1}b}$ we have $$\sigma_{a,b}\sigma_{1,k}\sigma_{a,b}^{-1}(x)=a((x-b)/a+k)+b=x-b+ak=\sigma_{1,ak}$$ so $k’=ak$. This shows that $\sigma_{a,b}$ is in $N_{G}(H)$.

For the converse, suppose $\alpha:\Zn{n}\to\Zn{n}$ is in the normalizer of $H$. Then $$\alpha(1 2 \ldots n)\alpha^{-1}=(\alpha(1) \alpha(2) \ldots \alpha(n)).$$ Let $$b=\alpha(n).$$ Then there must be an $a$ so that $\alpha(1)=b+a$, $\alpha(2)=\alpha(1)+a=\alpha(n)+2a=b+2a$, and so on. In other words $$\alpha(x)=b+xa$$ or $\alpha(x)=\sigma_{a,b}$. Since $\sigma(x)=b+1$ for some $x$, we have $ax+b\equiv b+1\pmod{n}$ for this $x$, which means $ax=1\pmod{n}$ so $(a,n)=1$.

Problem 4

Although it wasn’t clear from the problem statement, the more interesting part of this problem is to actually verify that you have the correct subgroup lattice. The three given subgroups of order 8 consist of two cyclic groups of order 8 (generated by v and by uv) and a group of order 8 isomorphic to $\Zn{2}\times\Zn{4}$. As many of you noticed, the subgroup $H$ generated by $v^{2}$ commutes with everything in the group so the cyclic group of order 4 it generates is normal.

The quotient $M/H$ has order $16/4=4$ and isn’t cyclic, so it must be $\Zn{2}\times \Zn{2}$. The three subgroups of this quotient group are generated by $vH$, $uH$, and $uvH$.

If you lift the subgroup $vH$ of $G/H$ back to $H$, you get the subgroup generated by $v$. If you lift the subgroup $uvH$ you get the subgroup generated by $uv$. And if you lift the subgroup generated by $u$ you get the subgroup generated by $u$ and $v^{2}$.

Each of these subgroups contains \$v^{4}, so you can consider their quotients by this subgroup, and so on to construct the lattice.