\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{5: M\"obius Inversion}{Due Friday, Week 7}

In this HW set, there are \textbf{two} sections: a \textbf{noncollaboration} section and a \textbf{collaboration} section.  For the noncollaboration 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 Let $P$ be a finite poset, and $f \in \mathbb{A}(P)$ be a function in the incidence algebra of $P$.  Prove that the following properties are all equivalent:
\begin{enumerate}[(i.)]
\item For any $x \in P$, we have $f(x,x) = 1$, and for any $x < y \in P$, we have
\begin{align*}
\sum_{z: x \leq z \leq y} f(z,y) = 0. 
\end{align*}
\item For any $x \in P$, we have $f(x,x) = 1$, and for any $x < y \in P$, we have
\begin{align*}
\sum_{z: x \leq z \leq y} f(x,z) = 0. 
\end{align*}
\item For any $x \in P$, we have $f(x,x) = 1$, and for any $x < y \in P$, we have
\begin{align*}
\sum_{z: x < z \leq y} f(z,y) = -f(x,y). 
\end{align*}
\item For any $x \in P$, we have $f(x,x) = 1$, and for any $x < y \in P$, we have
\begin{align*}
\sum_{z: x \leq z < y} f(x,z) = -f(x,y). 
\end{align*}
\item $f$ is $\mu$, the M\"obius function on $P$.
\end{enumerate}
\end{enumerate}


\newpage
\section{Collaboration Section}

Do \textbf{two} of the four problems below!
 
\begin{enumerate}
\item Take any two finite posets $P, Q$.  We can define the \textbf{direct product} $P \times Q$ of $P$ and $Q$ as the following partially ordered set:
\begin{itemize}
\item The elements of $P \times Q$ is the set $\{(p, q) ~|~ p \in P, q \in Q\}$. 
\item Given any two elements $(p_1, q_1), (p_2, q_2) \in P \times Q$, we say that $(p_1, q_1) < (p_2, q_2)$ if and only if $p_1 \leq p_2$ and $q_1 \leq q_2$, with $(p_1, q_1) \neq (p_2, q_2)$.
\end{itemize}
Let $\mu_P$ be the M\"obius function of $P$, $\mu_Q$ be the M\"obius function of $Q$, and $\mu_{P \times Q}$ be the M\"obius function of $P \times Q$.  Prove that for any $a, b \in P, c, d \in Q$, we have
\begin{align*}
\mu_{P \times Q} ((a,c), (b,d)) = \mu_P(a,b) \cdot \mu_Q(c,d).
\end{align*}

(Hint: try using some of the equivalent characterizations of the M\"obius function that you've proven in the non-collab section!)


\item Consider the poset $P$ visualized as follows:
\begin{center}
\includegraphics[width=3in]{poset_hw.pdf}
\end{center}
If you prefer symbols to pictures, $P$ is simply a poset on the set $\{1,2,3,\ldots n\} \cup \{1',2',3',\ldots n'\} \cup \{0\}$.  The relation $<$ on $P$ is defined as follows: for any $x, y$ in our set, we can say that $x < y$ in our set precisely whenever $x < y$ as a pair of natural numbers (i.e. $2 < 3', 4' < 16, 3<5, 7<12$ are all true in our poset!)  

Find a closed form for the M\"obius function $\mu$ of this poset $P$.


\item In our inclusion-exclusion lectures from week 4, we defined the \textbf{Euler $\varphi$-function} as follows:
\begin{align*}
\varphi(n) = \textrm{ the number of integers in }\{1, \ldots n\}\textrm{ that are relatively prime to }n.
\end{align*}
\begin{enumerate}
\item Show that for any $n \in \mathbb{N}$,
\begin{align*}
n = \sum_{d \in \mathbb{N} : d | n} \varphi(d).
\end{align*}
\item Use M\"obius inversion on the above to prove that for any $n \in \mathbb{N}$,
\begin{align*}
\frac{\varphi(n)}{n} = \sum_{d \in \mathbb{N} : d | n} \frac{\mu(1,d)}{d}.
\end{align*}
\end{enumerate}


\item Prove the following ``multiplicative'' version of the M\"obius inversion theorem: suppose that $P$ is a finite poset with a unique minimal element $0$.  Let $f$ be any function from $P$ to $\mathbb{R}^+$; using $f$, create the function $g: P \to \mathbb{R}^+$ by setting
\begin{align*}
g(a) = \prod_{x \leq a} f(x).
\end{align*}
Prove that
\begin{align*}
f(a) = \prod_{x \leq a} (g(x))^{\mu(x,a)}.
\end{align*}
\end{enumerate}
\end{document}

