\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{enumerate}
\usepackage{url}
\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};}}

\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
            
\input{preamble.tex}

\begin{document}

\homework{6: More M\"obius Inversion; Group Actions}{Due Friday, Week 8}

In this HW set, there are \textbf{two} sections: a \textbf{non-collaboration} section and a \textbf{collaboration} section.  For the non-collaboration section, use only your notes/class notes, and don't work with others.  For the collaboration section, work as normal!  

\section{Non-Collaboration Section}

Do the one problem below!
\begin{enumerate}
\item Take a poset $P$.  In this poset, we can define the concepts of least upper bounds and greatest lower bounds:
\begin{itemize}
\item Given any set $S \subset P$, we say that $z$ is an \textbf{upper bound} of $S$ if $z \geq s$ for all $s \in S$.  Similarly, we say that $z$ is a \textbf{least upper bound} of $S$ if $z$ is an upper bound and for any other upper bound $w$, $z \leq w$.
\item Given any set $S \subset P$, we say that $z$ is a \textbf{lower bound} of $S$ if $z \leq s$ for all $s \in S$.  Similarly, we say that $z$ is a \textbf{greatest lower bound} of $S$ if $z$ is an lower bound and for any other lower bound $w$, $z \geq w$.
\end{itemize} 
We call a poset a \textbf{lattice} if for any $x, y \in P$, the set $\{x, y\}$ has a least upper bound and a greatest lower bound.
\begin{enumerate}
\item Show that the divisor posets and the Boolean posets we defined in class are lattices.
\item Is the poset from problem 2 on HW5 a lattice?  Prove your claim.
\item Suppose that $P$ is a lattice.  For any $x, y \in P$, let $x \wedge y$ denote the greatest lower bound of $x, y$.  Show that if $t \in P$ satisfies $x, y \geq t$, then $x \wedge y \geq t$ as well.
\item Similarly: suppose that $P$ is a lattice.  For any $x, y \in P$, let $x \vee y$ denote the least upper bound of $x, y$.  Show that if $t \in P$ satisfies $x, y \leq t$, then $x \vee y \leq t$ as well.
\end{enumerate}
\end{enumerate}

\section{Collaboration Section}

Do \textbf{two} of the four problems below!
 
\begin{enumerate}

\item For any finite poset $P$, let $\mu(P)$ denote the maximum value of the M\"obius function $\mu$ on the poset $P$.  More generally, for any $n$, let $\mu(n)$ denote the maximum value of $\mu(P)$ amongst all finite posets $P$ containing $n$ elements.

For each of the following claims about $\mu(n)$, decide whether it is true or false, and offer a proof for each claim.
\begin{enumerate}
\item For all sufficiently large $n$, $\mu(n) > n $.
\item For all sufficiently large $n$, $\mu(n) > n^2$.
\item For all sufficiently large $n$, $\mu(n) > n^n$.
\end{enumerate}

\item Suppose that $L$ is a finite lattice with minimum element $\hat{0}$ and maximum element $\hat{1}$; that is, for any $x \in L$, we have $\hat{0} \leq x \leq \hat{1}$.

Prove that for any $a \in L, a \neq \hat{1}$, we have
\begin{align*}
 \sum_{x: x \wedge a = \hat{0}} \mu(x, \hat{1}) = 0.
\end{align*}

(Hint: for any $y, b \leq a$, let $N(y) = \sum_{x: x \wedge a = y} \mu(x, \hat{1})$ and $S(b) = \sum_{y: b \leq y \leq a} N(y)$.  Show that $S(b) = 0$ for all $b \leq a$; then use M\"obius inversion to prove the same thing for $N(y)$ for all $y \leq a$.)

\item Suppose you have a collection of seashells in $k$ different colors, with as many as you could want of each color.  You want to arrange them in a necklace like we did in class, where we consider two necklaces to be the same if one can be rotated around so that it becomes the other.  
\begin{enumerate}
\item Prove that when $n$ is prime, there are
\begin{align*}
\frac{k^n + k(n-1)}{n}
\end{align*}
many such necklaces.  
\item Use the observation above to prove Fermat's little theorem: for any prime number $k$, we have $k^n \equiv k \mod n$.
\end{enumerate}

\item Suppose that you have a regular tetrahedron and $n$ different colors of paint  In how many ways can you paint each of the sides of your tetrahedron a color, where we regard two tetrahedra as being the ``same'' if we can rotate one tetrahedron in space to get the other?  (\href{https://www.youtube.com/watch?v=qAR8BFMS3Bc}{This oddly awkward YouTube video} might be helpful for visualizing the rotations here; there are more than you may think!)
\end{enumerate}



\section{Extra-Credit Section}

Solve any problem below for extra credit!  (Warning: harder.)
 
\begin{enumerate}
\item For any $n$, let $\mu_L(n)$ denote the largest possible value of the M\"obius function $\mu$ on any lattice poset $L$ on $n$ elements.  Show that for sufficiently large $n$ and any $\epsilon > 0$, $\mu_L(n) \geq n^{2-\epsilon}$.
\item (Open.)  Prove that $\mu_L(n) \approx n^2$.
\end{enumerate}
\end{document}

