\documentclass[letterpaper]{article}
\usepackage{geometry}
\usepackage{amsmath}
\begin{document}

\noindent Geoffrey Thomas \\
\noindent 18.781 pset 8 \\
\noindent Collaborators: Liz Denys

\def\floor#1{\ensuremath{\left[#1\right]}}

\begin{enumerate}
\item[4.1 15.] Define $k$ as the unique integer satisfying $\frac{k}{n} \le \xi < \frac{k+1}{n}$. Note that $\floor{\xi} = \floor{\frac{k}{n}}$, since $n\floor{\xi} = k$. Therefore we can write the summation as $$\floor{\frac{k}{n}} + \floor{\frac{k+1}{n}} + \cdots{} + \floor{\frac{k+n-1}{n}}$$ Write $k = qn+r$ where $q, r$ are integers and $0 \le r < n$. Then the summation becomes $$\floor{\frac{qn+r}{n}} + \floor{\frac{qn+r+1}{n}} + \cdots{} + \floor{\frac{\left(q+1\right)n+r-1}{n}}$$ The first $(n-r)$ terms of this summation, $\floor{\frac{qn+r}{n}}$ through $\floor{\frac{qn + \left(n-1\right)}{r}}$, all equal $q$. The remaining $r$ terms, $\floor{\frac{\left(q+1\right)n}{n}}$ through $\floor{\frac{\left(q+1\right)n + r - 1}{n}}$, all equal $q+1$. Therefore the summation is $q\left(n-r\right) + \left(q+1\right)r = qn + 1$. Meanwhile, the right hand side of the equation is $\floor{n\xi} = \floor{k} = k = qn+1$, so the equation holds.

\item[4.1 21.] 
WLOG let $u, v$ be positive so we can safely take principal square roots. From the stipulation $u-v \le \sqrt[4]{64n}$,
\begin{align*}
\left(u+v\right)^2 - \left(u-v\right)^2 & = 4uv \\ 
\left(u+v\right)^2 - \sqrt{64uv} & \le 4uv \\
\left(u+v\right)^2 & \le 4uv + 8\sqrt{uv} \\
\frac{\left(u+v\right)}{2} & \le \sqrt{uv + 2\sqrt{uv}} \le \sqrt{uv + 2\sqrt{uv} + 1} = \sqrt{\left(\sqrt{uv}+1\right)^2} = \sqrt{uv} + 1
\end{align*}
Meanwhile,
\begin{align*}
4uv = & \left(u+v\right)^2 - \left(u-v\right)^2 \\
4uv < & \left(u+v\right)^2 \\
\sqrt{uv} < & \frac{\left(u+v\right)}{2}
\end{align*}
Now $u+v$ is even because $u$ and $v$ are both factors of an odd integer (and so are both odd), and so $\frac{\left(u+v\right)}{2}$ is an integer. The two results bound $\frac{\left(u+v\right)}{2}$ to a unique integer, specifically $\floor{\sqrt{uv} + 1}$. Therefore, the equation in question is $x^2 - \left(u+v\right)x + uv$, whose roots are $u$ and $v$, both of which are positive integers.

\item[4.2 5.]
Represent $n = \prod_ p^{\alpha}$. Then consider $\prod_{d|n} d$ in the form $\prod_p p^\beta$. For a given $p$, the divisors of $n$ are the divisors of $\frac{n}{p^\alpha}$ times all possible powers of $p$, $1$ through $\alpha$. So the power of $p$ is given by the sum of the possible powers of $p$ in $n$ times the number of divisors of $\frac{n}{p^\alpha}$, i.e., $\beta = \frac{1}{2}\alpha\left(\alpha+1\right)\frac{d(n)}{\alpha+1} = \frac{d(n)}{2}\alpha$, so $\prod_{d|n} d = \prod_p p^{\frac{d(n)}{2}\alpha} = {\prod_p p^\alpha}^\frac{d(n)}{2} = n^\frac{d(n)}{2}$.

\item[4.2 15.]
Since $\sigma_k$ is multiplicative, it suffices to show this for prime powers, since then $\sigma_k\left(p^{a_1} q^{a_2} p^{b_1} q^{b_2}\right) = \sigma_k\left(p^{a_1 b_1}\right) \sigma_k\left(q^{a_2 b_2}\right) < \sigma_k\left(p^{a_1}\right) \sigma_k\left(p^{b_1}\right) \sigma_k\left(q^{a_2}\right) \sigma_k\left(q^{b_2}\right) = \sigma_k\left(p^{a_1} q^{a_2}\right) \sigma_k\left(p^{b_1} q^{b_2}\right)$, and similarly for more prime factors.

Let $a = p^n$ and $b = q^m$ for primes $p, q$ and for $n, m$ positive integers. Since $(a, b) > 1$, it follows that $p = q$. $\sigma_k\left(p^{nm}\right) = 1 + p^k + \cdots{} + \left(p^k\right)^{nm}$. $\sigma_k\left(p^n\right)\sigma_k\left(p^m\right) = \left(1 + p^k + \cdots{} + \left(p^k\right)^n\right)\left(1 + p^k + \cdots{} + \left(p^k\right)^n\right)$, which expands to a polynomial of $p^k$ whose first and last terms have coefficient 1, but with all middle terms having greater coefficients. Therefore the second expression is greater than the first.

\item[4.2 16.]
If $2^n-1$ is prime, then the sum of the divisors of $2^{n-1}\left(2^n-1\right)$ is $\left(2^n-1\right)\left(1 + 2^n - 1\right) = 2^n\left(2^n-1\right) = 2p$. Since 3, 7, and 31 are primes of the form $2^n-1$, we can say that 6, 28, and 496 are perfect.

\item[4.2 19.]
If $x$ is an even perfect number, then $x = 2^{a-1} b$ for some $a \ge 2$ and odd $b \ge 3$. The sum of its divisors is $\left(2^a-1\right)\sigma(b) = 2^a b$ by definition. Since $2^a-1 \not | 2^a$, $b = c\left(2^a-1\right)$ for some integer $c$. So, again, we have $\left(2^a-1\right)\sigma(b)=2^ac\left(2^a-1\right)$. Cancelling, we have $\sigma(b) = 2^a c$. Since $\sigma(b)$ is the sum of all divisors, we know that $\sigma(b) \ge c\left(2^a-1\right) + c = c 2^a$. But we previously found that this is an equality, so there must be no other divisors --- i.e., $c = 1$, and $b = c\left(2^a-1\right) = 2^a - 1$ is prime, as we wanted to show.

\item[4.2 20.]
$\Omega(n)$ is totally multiplicative, so $\lambda(n)$ is too, since $\lambda(ab) = (-1)^{\Omega(a)\Omega(b)} = (-1)^{\Omega{a}} (-1)^{\Omega{b}} = \lambda(a) \lambda(b)$.

By theorem 4.4, $\sum_{d|n} \lambda{d}$ is also multiplicative, so we can just consider prime powers. $\sum_{d|p^a} \lambda{p^a} = \sum_{i=1}^a (-1)^i$, which is $1$ if $a$ is even and $0$ if $a$ is odd, that is, $1$ if $p^a$ is a perfect square and $0$ otherwise. Since the property of being a perfect square is also multiplicative, the claim holds.

\item[4.2 24.]
$f(x)^n$ is multiplicative if $f(x)$ is; this, plus theorem 4.4, plus $d(n)$ being multiplicative tells us that both sides of this equation are multiplciative. So we only need show that for prime powers,
\begin{align*}
\sum_{d|p^a} d(d)^3 & = \left(\sum_{d|p^a} d(d)\right)^2 \\
\sum_{i=1}^a i^3 & = \left(\sum_{i=1}^a i\right)^2
\end{align*}
which is a known fact about summations of natural numbers.

\item[4.]

\begin{align*}
(f\ast (g\ast h))(n) &= \sum_{d_1|n}f(d_1)(g\ast h)\left(\frac{n}{d_1}\right)\\
                     &= \sum_{d_1|n}f(d_1)\left(\sum_{d_2| \left(\frac{n}{d_1}\right)}g(d_2) h\left(\frac{n}{d_1 d_2}\right)\right)\\
                     &= \sum_{\substack{d_1 d_2 d_3 =n\\ d_1,d_2,d_3\geq 1}}f(d_1)g(d_2)h(d_3)
\end{align*}
since iterating through all divisors $d_1$ of $n$, all remaining divisors $d_2$, and the final quotient in order is the same as iterating through all $d_1, d_2, d_3$ that multiply to $n$.

Similarly,
\begin{align*}
((f\ast g) \ast h)(n) &= \sum_{d_3|n}(f\ast g)\left(\frac{n}{d_3}\right)h(d_3)\\
                      &= \sum_{d_3|n}\left(\sum_{d_1| \left(\frac{n}{d_3}\right)}f(d_1) g\left(\frac{n}{d_1 d_3}\right)\right)h(d_3)\\
                      &= \sum_{\substack{d_1 d_2 d_3 =n\\ d_1,d_2,d_3\geq 1}}f(d_1)g(d_2)h(d_3)
\end{align*}

Since both orders produce the same result, the convolution operator is associative.

\item[5.]
\begin{align*}
Z(f\ast g,s) & = \sum_{n=1}^{\infty}\frac{(f\ast g)(n)}{n^s}\\
             & = \sum_{n=1}^{\infty}\frac{\sum_{a|n}f(a)g(\frac{n}{a})}{n^s}\\
             & = \sum_{n=1}^{\infty}\sum_{a|n}\frac{f(a)g(\frac{n}{a})}{n^s}\\
             & = \sum_{a=1}^{\infty}\sum_{b=1}^{\infty}\frac{f(a)g(b)}{(ab)^s}\text{~~~~~~~~~
~~~~~~(1)}\\
             & = \sum_{a=1}^{\infty}\sum_{b=1}^{\infty}\frac{f(a)}{a^s}\frac{g(b)}{b^s}\\
             & = \left(\sum_{a=1}^{\infty}\frac{f(a)}{a^s}\right)\left(\sum_{b=1}^{\infty}\frac{g(b)}{b^s}\right)\\
             & = Z(f,s)Z(g,s)
\end{align*}

At equation (1), we note that we can write $n$ from the left summation in the form $ab$ for each of its divisors $a$ (in fact, this is the form we've written it in in the previous step, as $a$ and $n/a$). Enumerating these by all integers $a$ times all integers $b$ is valid, since this will generate all factorizations $ab$ of every integer (by closure of multiplication and factoring), no more, no less. So we can change variables at this point.

For the second part of this problem, we note that since we want $1 = (f \ast f^{-1})(1) = f(1) f^{-1}(1)$, $f(1)$ cannot be zero, proving one direction of the iff. For the other direction, we can build up each value of $f^{-1}(n)$ given $f(n)$. We have already determined $f^{-1}(1)$. We then can proceed by induction, since $f^{-1}(2)$ is the only as-yet-unconstrained value in the constraint $0 = (f \ast f^{-1})(2) = f(1)f^{-1}(2) + f(2)f^{-1}(1)$, and once we constrain it we can do the same for higher values of $n$ in $f^{-1}(n)$. Specifically, with strong induction, we have for any $n$
\begin{align*}
0 = & \sum_{d|n} f\left(\frac{n}{d}\right) f^{-1}\left(d\right) \\
  = & f(1) f^{-1}(n) + \sum_{d|n,\,d\neq n} f\left(\frac{n}{d}\right) f^{-1}\left(d\right)
\end{align*}
where the summation in the second line only includes $f^{-1}$ of proper divisors of $n$, and the other term multiplies the unknown $f^{-1}(n)$ by a nonzero coefficient. So this unknown can be calculated provided you know $f^{-1}$ of its proper divisors, which given the base case of $f^{-1}(1) = f(1)^{-1}$ completes the determination of $f^{-1}(n) \forall n \in Z^+$.

\end{enumerate}
\end{document}