\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage{cancel}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage{multicol}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\newcommand{\hl}[1]{%
  \colorbox{red!50}{$\displaystyle#1$}}            
            
\input{preamble.tex}

\begin{document}

\homework{14: Review}{Due Monday, Week 9}

This set is different from other sets.  For one, it is due on \textbf{Monday}, week 9, instead of Friday, week 8!  This is because of Thanksgiving.  For another, this set isn't focused only on the material of the past week!  Instead, it's designed to function as a \textbf{review} of the quarter so far.  The idea here is to give you all a chance to practice some of the skills/problems that we worked on in earlier weeks, because (as you may have noticed!) they keep coming up in class!

Do \textbf{three} of the \textbf{six} problems below! 


\begin{enumerate}
\item Counting and cosets!
\begin{enumerate}
\item Show that $H = \{id, (12), (13), (23), (123), (132)\}$ is a subgroup of $S_n$ for any $n \geq 3$.
\item How many elements are there in $S_{n},$ for $n = 24601$?
\item How many cosets of $H$ are there in $S_{n}$, for $n = 24601$?
\end{enumerate}
\item Catalan numbers and counting permutations!
\begin{enumerate}
\item Let $C_n$ denote the collection of all of the orderings of the set $\{1,2,\ldots n\}$ that do not have any 3-term increasing subsequences.  For example, $C_4$ contains the following elements:
\begin{align*}
&1432, 2143, 2413, 2431, 3142, 3214, 3241,\\
&3412, 3421, 4132, 4213, 4231, 4312, 4321.
\end{align*}
Alternately, if it helps, the orderings of $\{1,2,3,4\}$ that are \textbf{not} in the above list are the following, because they all have 3-term increasing subsequences. (Subsequences are highlighted in red below; where there were multiple such subsequences, I just picked one of the possible subsequences.)
\begin{align*}
&\hl{1}\hl{2}\hl{3}4, ~~\hl{1}\hl{2}\hl{4}3, ~~\hl{1}\hl{3}2\hl{4},~~ \hl{1}\hl{3}\hl{4}2,~~ \hl{1}4\hl{2}\hl{3}, \\
&\hl{2}1\hl{3}\hl{4}, ~~ \hl{2}\hl{3}1\hl{4},~~\hl{2}\hl{3}\hl{4}1, ~~
3\hl{1}\hl{2}\hl{4},~~ 4\hl{1}\hl{2}\hl{3}.
\end{align*}

Show that $C_n$ is counted by the Catalan numbers.
\item Using (a), determine the ratio of permutations of $\{1,2,\ldots 50\}$ with no 3-term increasing subsequence to the total number of such permutations: that is, find the fraction
\begin{align*}
\frac{\#(\textrm{permutations of }\{1,2\ldots 50\}\textrm{ with no 3-term increasing subsequence})}{\#(\textrm{permutations of }\{1,2\ldots 50\})}.
\end{align*}
What is this number, roughly?  (I.e. give me its first few digits and order of magnitude.)
\end{enumerate}

\item Righting wrongs!  To answer this problem,
\begin{enumerate}
\item Go through your old HW and quizzes!  
\item Find \textbf{one} problems that you attempted, but did not get full credit on.  (I.e. 0 or .5 scores on attempted work.)
\item Attach your old work (you should have it still in LaTeX!)
\item Attach a paragraph explaining why your old attempt didn't work / your proof was flawed / etc.
\item Then, \textbf{fix} your problem by attaching a new and correct solution!
\end{enumerate}
You need all of the parts above to receive credit here.

\item Groups and games!
\begin{enumerate}
\item Given any group $G$ and all of its subgroups, we can make a \textbf{lattice} out of these subgroups, as follows:
\begin{itemize}
\item Draw one vertex on our paper for each subgroup that we have.
\item Draw a line from one subgroup $H$ to another subgroup $K$ if and only if the following happens:
\begin{itemize}
\item $H$ is a subgroup of $K$.
\item There is no third subgroup $J$ such that $J \neq H, K$ and $H \subset J \subset K$.
\end{itemize} 
\end{itemize}
We draw an example for $G = \langle \mathbb{Z}/150\mathbb{Z}, +\rangle$ here:
\footnotesize
\begin{align*}
\xymatrix @R1em@C1em{
&&\mathbb{Z}/150\mathbb{Z}\ar@{-}[d] \ar@{-}[ld] \ar@{-}[rd] & &  \\
&\{0,5,10,\ldots 145\} \ar@{-}[ld]\ar@{-}[d] \ar@{-}[rd]&  \{0,3,6,\ldots 147\} \ar@{-}[ld] \ar@{-}[rd]&  \{0,2,4,\ldots 148\}\ar@{-}[d] \ar@{-}[ld]\\
\{0,25, 50, \ldots 125\}\ar@{-}[rd]\ar@{-}[rrd]&\{0,15, 30, \ldots 135\}\ar@{-}[d]\ar@{-}[rrd] &  \{0, 10, 20, \ldots 140 \}\ar@{-}[d] \ar@{-}[rd]&  \{0,6,12, \ldots 138\} \ar@{-}[d]\\
& \{0, 75\} \ar@{-}[rd]& \{ 0, 50, 100\} \ar@{-}[d]& \{0, 30, 60, 90, 120\}\ar@{-}[ld]\\
&& \{0\}\\
}
\end{align*}
\normalsize
Create such a lattice for $G = \langle \mathbb{Z}/168\mathbb{Z}, +\rangle$.
\item Consider the following two-player game on this lattice:
\begin{itemize}
\item Player 1 picks out a subgroup $H$ on the lattice, and deletes it, along with any subgroups contained within $H$.
\item Player 2 then picks out a remaining subgroup $H'$, and also deletes it along with any subgroups contained within $H'$.
\item The players repeat this process until there are no subgroups left.  The player who chose the last subgroup loses.
\end{itemize}
Find a winning strategy for either player 1 or player 2 on the lattice for $G = \langle \mathbb{Z}/84\mathbb{Z}, +\rangle$.  (Helpful hint: you already made this lattice as a sublattice in your answer to (a)!)
\end{enumerate}
\newpage

\item Generating functions and groups!
\begin{enumerate}
\item Show that in $\mathbb{F}_p[x]$, for any $n$, there are precisely $p^n$ many monic\footnote{If $f(x)$ is a degree-$n$ monic polynomial, then the coefficient of $x^n$ in $f(x)$ is just 1.} polynomials of degree $n$.
\item Let $A_n$ denote the number of monic polynomials of degree $n$ that you calculated in (a), and set
\begin{align*}
A(x) = \sum_{n=0}^\infty A_nx^n.
\end{align*}
Let $M_n(p) = M_n$ denote the number of irreducible monic polynomials of degree $n$.  Show\footnote{If you keep going with this problem, you'll get an alternate proof that $M_n > 0$ for all $n$!  Yay, generating functions.} that 
\begin{align*}
A(x) = \prod_{n = 1}^\infty \left( 1 + x^n + x^{2n} + \ldots + \right)^{M_n}.
\end{align*}
(Hint: show that the coefficients for both expressions are equal!)
\end{enumerate}


\item Polynomial problems!
\begin{enumerate}
\item Take any polynomial $f(x) \in \mathbb{Z}[x]$ with degree at least 2.  For any prime $p$, we can interpret $f(x)$ as a polynomial in $\mathbb{F}_p[x]$ by reducing all of its coefficients mod $p$.  For example, if $f(x) = 4x^2 + 3x - 7$, we could interpret $f(x)$ in $\mathbb{F}_2[x]$ as $x + 1$.  Conversely, if we interpreted $f(x)$ as an element of $\mathbb{F}_3[x]$, it would be $x^2 +2$.

For any such polynomial $f(x)$, show that there is some prime $p$ and value $n$ such that if we interpret $f(x)$ as a polynomial in $\mathbb{F}_p[x]$, then $f(n) = 0$.

\item Take any polynomial $f(x) \in \mathbb{Z}[x]$ with degree at least 2.  Using (a), prove that there is some prime $p$ such that $f(x)$ is \textbf{not} an irreducible polynomial when interpreted in $\mathbb{F}_p[x]$.  (For example, $x^2 + x + 1$ is not irreducible in $\mathbb{F}_3[x]$, because we can write it as $(x+2)(x+2) = x^2 + 4x + 4 = x^2 + x + 1$.)
\end{enumerate}

\end{enumerate}

\end{document}