\documentclass[11pt]{article}

\usepackage[authoryear]{natbib}
\setlength{\bibsep}{6pt}


%\usepackage[dvipdfmx]{graphicx}  %Janet always seems to need to use this command to process graphis.
\usepackage{graphicx}

\usepackage{caption}
\usepackage{geometry}
% To avoid hard coding the names of individual parts of multi-part task and any later references to those individual parts, include the optional "shortlabels" argument as part of the enumitem package.
\usepackage[shortlabels]{enumitem}
\usepackage{setspace}
\usepackage{float}
\usepackage{placeins}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}
\usepackage{framed}
\usepackage{url}




% In case an author wants to include a very wide matrix.
\setcounter{MaxMatrixCols}{30}

% The following commands will set up the page geometry according to the default TRIUMPHS style.  Please modify them wisely, if at all.  As needed for a specific PSP, please address bad page and line breaks using commands such as \newpage and\or otherwise inserting/deleting space between lines.

\setlength{\topmargin}{-.7in}
\setlength{\oddsidemargin}{-.1in}
\setlength{\evensidemargin}{-.1in}
\setlength{\textwidth}{6.6in}
\setlength{\textheight}{9.3in}

\addtolength{\skip\footins}{10pt}
\linespread{1.1}

% The new command \sep defined here will produce the `extended infinity' symbol used to separate PSP narrative from primary source text within the `source' environment defined below.
\newcommand{\sep}{\vspace{-3pt}
\begin{center}
{\mathversion{normal}
$\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}
\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}\infty \mspace{-5.5mu}$}
\end{center} \vspace*{-5pt}}

% This defines the environment for setting off primary source material with the `infinity' symbol before and after the source material. The source material itself will be set in a quote environment in sans serif font. For very short primary source excerpts, use your discretion concerning whether this environment makes sense, but please always use sans serif font (\sf) for primary source excerpts.

  \newenvironment{source}%
 {\bigskip \sep \vspace*{-6pt} \begin{quote}
          \begin{sf}   }
   {   \end{sf}     \end{quote} \vspace*{-6pt} \sep \bigskip}%


% This defines a new environment for student tasks.  A double box will be placed around 'Task xx', where the  number xx is updated with each new task.

\newcounter{tasknumb}
\newcommand{\tasknumb}[1]{\refstepcounter{tasknumb}\textmd{\textbf{$\fbox{$\fbox{Task \thetasknumb}$}$}}#1}

\newenvironment{task}[1][]%
 {\begin{itemize}
 \item[\tasknumb{#1}] }
{
    \end{itemize}    }%

%\usepackage{showlabels}
%\showlabels{}

%\usepackage{showkeys}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%IMPORTANT NOTES:                                                                                                                                       %%
%% 1.  This Template file is designed for use by authors of TRIUMPHS PSPs.                                                                               %%
%% 2. THIS TEMPLATE FILE WILL NOT PROPERLY COMPILE without access (in the same file directory) to the Creative Commons BY-SA logo (see line #267 below). %%

%% 3. FOR A STUDENT-ONLY VERSION OF THIS PSP (which omits the Notes to Instructors section), remove the % from the beginning of line #179.               %%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{The M\"{o}bius Function and M\"{o}bius Inversion}
\author{Carl Lienert\thanks{Department of Mathematics, Fort Lewis College, Durango, CO, 81301; \texttt{lienert\_c@fortlewis.edu.}}}
\date{\today}


\maketitle


\vspace*{-8pt}

August Ferdinand M\"{o}bius (1790--1868) is perhaps most well known for the one-sided {\it M\"{o}bius strip} and, in geometry and complex analysis, for the {\it M\"{o}bius transformation}.   In number theory, M\"{o}bius' name can be seen in the important technique of {\it M\"{o}bius inversion}, which utilizes the important {\it M\"{o}bius} function. In this PSP we'll study the problem that led M\"{o}bius to consider and analyze the M\"{o}bius function.  Then, we'll see how other mathematicians, Dedekind, Laguerre, Mertens, and Bell, used the M\"{o}bius function to solve a {\it different} inversion problem.\footnote{All translations of excerpts from the German works of M\"{o}bius, Dedekind, and Mertens in this project were done by David Pengelley, New Mexico State University (retired), 2021. The author of this PSP is responsible for the translation of the French excerpt from the work of Laguerre.}  Finally, we'll use M\"{o}bius inversion to solve a problem concerning Euler's totient function.



\vspace*{-8pt}
\section{M\"{o}bius: the M\"{o}bius function}


\vspace*{-8pt}
All excerpts of M\"{o}bius' work in this project are from {\it \:{U}ber eine besondere Art von Umkehrung der Reihen} ({\it On a special type of series inversion}). The following excerpt, from the beginning of M\"{o}bius' paper, sets up the basic form of M\"{o}bius' inversion problem:


\vspace*{-8pt}
\begin{source}
The famous problem of series inversion is that, when a function of a variable
is given as a consecutive series of powers of the variable, one inversely
requires the variable itself, or even any other function of it, expressed as
an ongoing series of powers of the original function. One knows that it
requires no small analytical ingenuity to discover the rule according to which
the coefficients of the second series depend on the coefficients of the first.
The following task is much easier to solve.

Suppose a function $f(x)$ of a variable $x$ is given as a series according to
the powers of $x$:%

\begin{equation}
\label{MobEqtn1}
f(x)=a_1x+a_2x^2+a_3x^3+a_4x^4+ \dots
\end{equation}



One should represent $x$ as an ongoing series, not according to the powers of
the function $f(x)$, but rather according to the function $f$ of the powers of
$x$:%
\begin{equation}
\label{MobEqtn2}
x=b_1f(x)+b_2f(x^2)+b_3f(x^3)+b_4f(x^4)+\dots
\end{equation}


\vspace*{-8pt}



\end{source}

\begin{task}[\label{Day0HWS}]
Where have you seen a function written in the form in (\ref{MobEqtn1})?
\end{task}

\begin{task}
The expression in (\ref{MobEqtn2}) is the inversion of the expression in (\ref{MobEqtn1}).  Why would this be called an {\it inversion}?
\end{task}

M\"{o}bius continued, and stated the goal of the problem:
\begin{source}
The main demand of our problem is: Express the coefficients $b_{1},b_{2}%
,b_{3},\dots$ of the series (\ref{MobEqtn2}) as functions of the coefficients $a_{1}%
,a_{2},a_{3},\dots$ of the series (\ref{MobEqtn1}); and this occurs through the following
very easy calculation.
\end{source}

\begin{task}[\label{Day0HWE}]
In your own words, what is the objective?
\end{task}

Ok, now it's time to get our hands dirty.  Given that $$f(x)=a_1x+a_2x^2+a_3x^3+a_4x^4+ \dots,$$ we'll find expressions for $b_1, b_2, b_3, b_4, \dots$ in terms of the given coefficients $a_1, a_2, a_3, a_4, \dots.$

The symbolic equations have been removed from the following two excerpts.  The tasks that follow ask you to fill in the missing sets of equations.

\begin{source}

 From (\ref{MobEqtn1}) flows:%
 \begin{center}
 \framebox{Equation Set A}
\end{center}

%\[
%\mathrm{Equation\ Set\ A}
%\]
If one substitutes these values of $f\left(  x^{2}\right)  ,f\left(
x^{3}\right)  ,\dots$ and of $fx$ itself from (\ref{MobEqtn1}) into the equation (\ref{MobEqtn2}), one
gets:%

 \begin{center}
 \framebox{Equation B}
\end{center}

%\[
%\mathrm{Equation\ B}
%\]


%The law of progression of the coefficients in this series is clear. Namely, to
%determine the coefficient of $x^{m}$, partition the number $m$ in all possible
%ways into two positive whole factors. Each of these products then gives a term
%of the coefficient sought, in that one takes the two factors of the product as
%indices of an $a$ and $b$ to multiply together.
%
%Because the equation above must hold for every value of $x$, we have:%
%\[
%\mathrm{Equation\ Set\ C}
%\]
%through which every $b$ can be calculated with the aid of the previous $b$'s.
%
%In order therefrom to find the individual $b$'s independently from one
%another, one sets $a_{1}=1$ for the sake of greater simplicity, and obtains:%
%\[
%\mathrm{Equation\ Set\ D}
%\]
%
\end{source}

\begin{task} [\label{Step1}]

Give expressions for $f(x^2)$, $f(x^3)$, $f(x^4)$, $f(x^5)$, and $f(x^6)$. These are Equation Set A.
\end{task}

\begin{task} [\label{Step2}]
Do what M\"{o}bius instructed: ``substitute these values of $f\left(  x^{2}\right)  ,f\left(
x^{3}\right)  ,\dots$ and of $f(x)$ itself from (\ref{MobEqtn1}) into the equation (\ref{MobEqtn2})" {\it and} then rearrange the expression you obtain on the right so that it's in the form
\begin{equation}
\label{expansion}
\underline{\hspace{.7cm}} x + \underline{\hspace{.7cm}} x^2+ \underline{\hspace{.7cm}} x^3+ \underline{\hspace{.7cm}} x^4+ \underline{\hspace{.7cm}} x^5+\underline{\hspace{.7cm}} x^6+\dots.
\end{equation} This is Equation B.
\end{task}

%\begin{task}
%Substitute the given definition for $f(x)$ into $$b_1f(x)+b_2f(x^2)+b_3f(x^3)+b_4f(x^4)+\cdots$$
%to find an expression in $a_1, a_2, a_3, a_4, \dots$; $b_1, b_2, b_3, b_4, \dots$; and powers of $x$.   Do this, at least, through the $b_4f(x^4)$ term; a couple more terms might help you to see the pattern later.
%\end{task}

%\begin{task}
%  Rearrange the expression you obtained in the previous task so that it's in the form $$\underline{\hspace{.7cm}} x + \underline{\hspace{.7cm}} x^2+ \underline{\hspace{.7cm}} x^3+ \underline{\hspace{.7cm}} x^4+ \underline{\hspace{.7cm}} x^5+\cdots$$
%\end{task}

%The paragraph that starts ``The law of progression \dots" explains how to obtain the coefficient of  $x^m$ in this expansion.

\begin{task}[\label{23rd}]
Give the coefficient of  $x^{23}$ in terms of $a$'s and $b$'s.
\end{task}


\begin{task}[\label{24th}]
Give the coefficient of  $x^{24}$ in terms of $a$'s and $b$'s.
\end{task}

\bibliographystyle{plainnat}
      \bibliography{MobiusBib}{}   


M\"{o}bius continued:

\begin{source}

% From (\ref{MobEqtn1}) flows:%
%\[
%\mathrm{Equation\ Set\ A}
%\]
%If one substitutes these values of $f\left(  x^{2}\right)  ,f\left(
%x^{3}\right)  ,\dots$ and of $fx$ itself from (\ref{MobEqtn1}) into the equation (\ref{MobEqtn2}), one
%gets:%
%\[
%\mathrm{Equation\ B}
%\]


The law of progression of the coefficients in this series is clear. Namely, to
determine the coefficient of $x^{m}$, partition the number $m$ in all possible
ways into two positive whole factors. Each of these products then gives a term
of the coefficient sought, in that one takes the two factors of the product as
indices of an $a$ and $b$ to multiply together.

Because the equation above must hold for every value of $x$, we have:%
 \begin{center}
 \framebox{Equation Set C}
\end{center}

%\[
%\mathrm{Equation\ Set\ C}
%\]
through which every $b$ can be calculated with the aid of the previous $b$'s.

In order therefrom to find the individual $b$'s independently from one
another, one sets $a_{1}=1$ for the sake of greater simplicity, and obtains:%
 \begin{center}
 \framebox{Equation Set D}
\end{center}

%\[
%\mathrm{Equation\ Set\ D}
%\]

\end{source}

\begin{task}
M\"{o}bius  explained how to obtain the coefficient of  $x^m$ in this expansion in the first paragraph of this excerpt.  Compare his explanation to your answers {\it and} to your work for Tasks \ref{23rd} and \ref{24th}.
\end{task}

Remember, the expression you found, (\ref{expansion}), is the right hand side of (\ref{MobEqtn2}):
$$x=b_1f(x)+b_2f(x^2)+b_3f(x^3)+b_4f(x^4)+\dots.$$

\begin{task}[\label{Step3}]
Next, M\"{o}bius stated ``Because the equation above must hold for every value of $x$\dots" So, match (\ref{expansion}) with the left hand side of (\ref{MobEqtn2}) in order to obtain conditions on all the coefficients you found in (\ref{expansion}).  This will be a list of {\it equations} with $a$'s and $b$'s on the one side of the equality, and a number on the other.  This is  Equation Set C.
\end{task}

At this point, M\"{o}bius decided to let $a_1=1$ for convenience. We'll do the same.  There's no harm done; if the function you are interested in doesn't have $a_1=1$ use the function $\frac{1}{a_1}f(x)$ instead and adjust accordingly in the end.

From Equation Set C, you can now find values for the $b$'s in terms of the $a$'s.

\begin{task}
What is $b_1$?
\end{task}

\begin{task}[\label{bs}]
Use the value of $b_1$ to find the value of $b_2$ in terms of $a$'s.  Continue: find $b_3$, $b_4$,  $b_5$, $b_6$, $b_7$, and $b_8$ in terms of $a$'s (no $b$'s).  These are Equation Set D.
\end{task}



Next, M\"{o}bius made an observation about how to form the $b$'s without the need to extend the process above indefinitely:

\begin{source}
These few developments are sufficient to take away how also the values of the
succeeding $b$'s are put together from $a_{2},a_{3},\dots$ . Namely one
decomposes the index $m$ of $b_{m}$ in all possible ways into factors, in
which one takes $m$ itself as the largest factor, but omitting $1$, and also
considers any two decompositions, that differ only in the order of their
factors, as different; or as one can express briefly in the language of
combinatorial theory: One builds all variations with repetition to the product
$m$. Each of these variations then gives a term in the value of $b_{m}$,
taking the elements of the variation as the indices of $a$'s, and this term
receives the positive or negative sign, according to whether the number of
elements is even or odd.

So for example all variations of the product $12$ are:%
\[
12,\ 2\cdot6,\ 3\cdot4,\ 4\cdot3,\ 6\cdot2,\ 2\cdot2\cdot3,\ 2\cdot3\cdot2,\ 3\cdot2\cdot2,
\]
and thus%
\[
b_{12}=-a_{12}+2a_2a_6+2a_3a_4-3a_2a_2a_3.%
\]


The general correctness of this rule flows from the recurrence formula ($\mathrm{Equation\ Set\ C}$) so
easily that it would be superfluous for us to tarry for a proof.
\end{source}

\begin{task}
Use M\"{o}bius' observation to give an expression for $b_{8}$ in terms of $a$'s.  Compare both your answer and your process to those of Task \ref{bs}.
\end{task}

\begin{task}
Use M\"{o}bius' observation to give an expression for $b_{31}$ in terms of $a$'s.
\end{task}

\begin{task}[\label{Day1E}]
Give an expression for $b_{45}$ in terms of $a$'s.
\end{task}



M\"{o}bius presented several generalizations of the basic problem stated in the first excerpt.  We'll look at one of these to get the idea.

\begin{source}
The same relations between the coefficients $a$'s and $b$'s would incidentally
also be obtained if, like (\ref{MobEqtn1}) and (\ref{MobEqtn2}), one had in the same way compared the
general equalities %



\begin{align*}
fx  & = a_1Fx+a_2F(x^2)+a_3F(x^3)+ \dots\\
Fx  & = b_1fx+b_2f(x^2)+b_3f(x^3)+\dots
\end{align*}
with one another. Supposing therefore that the relations ($\mathrm{Equation\ Set\ C}$) hold between the
$a$'s and the $b$'s, then for these two equalities the second is a consequence
of the first, and the first a consequence of the second, where in the first
case $Fx$, and in the latter $fx$, may be a function of $x$.

\end{source}

\begin{task}[\label{Day1HWS}]
What function, $F(x)$, would make this generalized problem the same as the basic problem presented in the first excerpt?
\end{task}

\begin{task}[\label{Day1HWE}]
M\"{o}bius wrote ``Supposing therefore that the relations ($\mathrm{Equation\ Set\ C}$) hold between the
$a$'s and the $b$'s\dots."  Verify that this is, in fact, true. That is, repeat the analysis of Tasks \ref{Step1}, \ref{Step2}, and \ref{Step3} for this generalized problem.
\end{task}


Perhaps the fact that Equation Set C is the same for the basic problem as it is for the generalized problem made M\"{o}bius think something interesting was happening.  In fact, M\"{o}bius presented two further generalizations in which the same pattern continued to occur.

What M\"{o}bius did next is a valuable lesson: work out a simple example. Maybe the example will provide insight, maybe the example will be important in its own right.  That is, he didn't try to analyze the most general case he had presented, which would have been very difficult.  Instead he returned to the basic example, and in fact made it even easier for himself and for his readers:  %He considers the case where $a_1=a_2=a_3=\dots=1$.

\begin{source}
In order now to give a very simple example of this new kind of series
inversion, we want to set
\[
a_{1}=a_2=a_3=\dots=1,%
\]
so that from (\ref{MobEqtn1})
\[
fx=x+x^2+x^3+\dots\ \mathrm{and\ therefore\ } fx=\frac{x}{1-x}%
\]
But with these values for $a$'s, according to ($\mathrm{Equation\ Set\ D}$):%
\[
b_{1}=1, b_2=-1, b_3=-1, b_4=0, b_5=-1, b_6=1, b_7=-1, b_8=0, \text{ etc,}%
\]
and thus from (\ref{MobEqtn2}):%
\begin{equation}
\label{MobSeries}
 x=\frac{x}{1-x}-\frac{x^2}{1-x^2}-\frac{x^3}{1-x^3}-\frac{x^5}{1-x^5}+\frac{x^6}{1-x^6}-\frac{x^7}{1-x^7}+\frac{x^{10}}{1-x^{10}}-\frac{x^{11}}{1-x^{11}}-\frac{x^{13}}{1-x^{13}}+\dots
\end{equation}

\end{source}


\begin{task}[\label{Day2S}]
M\"{o}bius claimed $$f(x)=x+x^2+x^3+\dots=\frac{x}{1-x}.$$ What kind of series is $x+x^2+x^3+\dots?$ Show that, in fact, $$x+x^2+x^3+\dots=\frac{x}{1-x}.$$

\end{task}

\begin{task}
Show how the result from Task \ref{Day2S} yields (\ref{MobSeries}).
\end{task}

\begin{task}
What are the next 3 non-zero terms in (\ref{MobSeries})?
\end{task}



\begin{task} [\label{prediction}]
Can you predict $b$ values without going through the entire process?  Try to predict values for $b_{37}$, $b_{64}$, $b_{65}$, $b_{105}$, and $b_{128}$.  Explain how you arrived at your predictions.
\end{task}

Here is the observation M\"{o}bius gave for  $b$ values:

\begin{source}
In the series (\ref{MobSeries}), whose general term is $\frac{x^{m}}{1-x^{m}}$ and whose
sum is $=x$, the law therefore reigns, that for $m=1$ and for every $m$ that
is a product of an even number of distinct prime numbers, the coefficient of
the term is $=1$, that every term, whose $m$ is itself a prime number, or a
product of an odd number of distinct primes, has the coefficient $-1$, and
finally that all terms are dropped, whose exponents have quadratic or higher
powers of prime numbers as factors.
\end{source}

\begin{task}
Compare your predictions in Task \ref{prediction} to M\"{o}bius' observation.  Do they agree?  If not, explain how your prediction method differs from that of M\"{o}bius.
\end{task}

These $b$ values are the values of what is known today as the M\"{o}bius function.
\begin{task}
The M\"{o}bius function, $b_i$, is defined for positive integers, $i$.  Write the function that M\"{o}bius described using modern notation.
\end{task}



M\"{o}bius dedicated the middle portion of his paper to a careful and thorough examination of the this function. Having found the $b$ values, M\"{o}bius had solved the inversion problem, but not what is known today as M\"{o}bius Inversion.  He then used this inversion technique to  produce interesting series results.  Some examples are:

\begin{source}
\begin{align*}
e&=2^{1/2}\cdot3^{1/3}\cdot5^{1/5}\cdot6^{-1/6}\cdot7^{1/7}\cdot10^{-1/10}\cdot11^{1/11}\cdots\\
\frac{4}{\pi}&=1+\frac{1}{3}-\frac{1}{5}+\frac{1}{7}+\frac{1}{11}-\frac{1}{13}-\frac{1}{15}-\frac{1}{17}+\dots\\
\frac{4}{\pi}&=\frac{3}{4}\cdot \frac{5}{4} \cdot \frac{7}{8} \cdot \frac{11}{12} \cdot \frac{13}{12} \cdot \frac{17}{16} \cdot \frac{19}{20} \cdot \frac{23}{24} \cdots.\\
\end{align*}
\end{source}

Notice, these examples give a method to approximate the transcendental numbers $e$ and $\pi$.

\begin{task}[\label{Day2E}]
In the product expansion given above for $e$ what are the next 3 {\it missing} factors? Why?
\end{task}

%\begin{task}(Optional)
%Use technology to experiment with how quickly these series converge to $e$ or to $\pi$.  How many %factors or terms do you need to achieve 5 decimal places of accuracy?
%\end{task}
The development of these examples can be found at the end of M\"{o}bius' paper and with a little work you can follow it, even if you don't read German.  However, this type of inversion is not what is known today at {\it M\"{o}bius inversion} and so we won't follow that detour here.


\section{Dedekind: M\"{o}bius inversion}

 Today, M\"{o}bius inversion concerns a different kind of sum: a divisor sum of an arithmetic function.

An {\it arithmetic function} is one whose domain is positive integers only.  You might notice that the M\"{o}bius function is an arithmetic function.  In fact, the values $a_i$ in the first excerpt from M\"{o}bius define an arithmetic function: the domain is $i=1,2,3, \dots$.  If $f(k)$ is an arithmetic function, then a {\it divisor sum} is: $$F(n)=\sum_{d|n} f(d).$$ For example, if $n=6$, $$F(6)=f(1)+f(2)+f(3)+f(6).$$

Julius Wilhelm Richard Dedekind (1831--1916) studied mathematics under Carl Friedrich Gauss (1777--1855) and later worked closely with Peter Gustav Lejeune Dirichlet (1805--1859) who took Gauss' chair upon his death.  Dedekind was the first to state and prove M\"{o}bius inversion in his paper {\it Abrifs einer Theorie der h\"{o}hern Congruenzen in Bezug auf einen reelen Primzahl-Modulus} (Outline of a theory of higher congruences in connection with a real prime-modulus) \citep{Dedekind}:

\begin{source}


The shared source of the theorem in section 18 and the analogous theorem just
now used is the following. Let $m$ be any whole number; further $a,b,c,\dots
,k$ all the distinct prime numbers that divide into $m$; one forms two
separate complexes $D,D^{\prime}$ of divisors of the number $m$ according to
the following principle. In the complex $D$ one initially includes all
divisors of the number $m$; in the complex $D^{\prime}$ all divisors of
$\frac{m}{a}$, all divisors of $\frac{m}{b}$ and so on; then again in the
complex $D$ all divisors of $\frac{m}{ab}$, of $\frac{m}{ac}$, of $\frac
{m}{bc}$ and so on; then again in the complex $D^{\prime}$ all divisors of
$\frac{m}{abc}$ and so on, until finally one has included also all divisors of
$\frac{m}{abc\cdots k}$ either in the complex $D$ or in the complex
$D^{\prime}$, depending on whether the number of prime numbers $a,b,c,\dots,k$
is even or odd. Then it is easy to show that each divisor of the number $m$
occurs just as often in one complex as in the other, with the exception of the
divisor $m$ itself, which occurs solely and only once in the complex $D$. It
requires only one look to derive from this the inversion of the equalities%

$$\sum f(\delta)=F(m) \text{  or  } \prod f(\delta) = F(m)$$
%\[
%\sum\text{ or }\prod\text{,}%
%\]
in which the sum or product sign $\sum$ or $\prod$ refers to all divisors
$\delta$ of an arbitrary number $m$; these solutions are contained in the
formulas%
%\[
%f\left(  m\right)  =
%\]
%or%
%\[
%f\left(  m\right)  =\text{.}%
%\]

\begin{equation}
\label{MobInv1}
f(m)=F(m)-\sum F\left(\frac{m}{a}\right)+\sum F\left(\frac{m}{ab}\right)-\mathrm{etc.} \dots
\end{equation}
%or
%\begin{equation*}
%f(m)=F(m):\prod F\left(\frac{m}{a}\right)\times \prod F\left(\frac{m}{ab}\right) : \dots
%\end{equation*}







%$$f(m)=F(m)-\sum F\left(\frac{m}{a}\right)+\sum F\left(\frac{m}{ab}\right)-\mathrm{etc.}$$ \label{MobInv1}
\end{source}

We are only interested in the equations involving summation, and not those with products.


\begin{task}[\label{WhyMob}]
What does this have to do with M\"{o}bius?!  Rewrite the expression on right hand side of (\ref{MobInv1}) using the M\"{o}bius function.
\end{task}

\begin{task}
What did Dedekind mean by ``complex?"
\end{task}

\begin{task}
Determine $D$ and $D^\prime$ for $m=60$.
\end{task}

\begin{task}[\label{DedStrat}]
Explain Dedekind's strategy.  What does Dedekind's discussion about the complexes $D$ and $D^\prime$ have to do with (\ref{MobInv1})?
\end{task}

\begin{task}[\label{evid1}]
Write the expression on the right side of (\ref{MobInv1}) for $m=6$, without summation notation.  Simplify and confirm that, in fact, you obtain $f(6)$.
\end{task}

\begin{task}[\label{evid2}]
Write the expression on the right side of (\ref{MobInv1}) for $m=2^3\cdot3^2$ without summation notation.  Simplify and confirm that, in fact, you obtain $f(2^3\cdot 3^2)$. Try to pay careful attention to how many times a given term $f(k)$, for any divisor $k$ of $m$, is added or subtracted in the expression (\ref{MobInv1}).
\end{task}

Dedekind's setup of the statement with ``$a,b,c, \dots k$" would, today, be replaced by writing $m$ in its prime factor form: $$m=p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_l^{\alpha_l}$$ where $p_i$ is prime.
\begin{task}
Translate the theorem that Dedekind stated using modern ``if \dots then \dots" presentation and modern notation.  In particular use $\sum_{d|m}$ notation and write $m$ in its prime factor form.  \end{task}

Dedekind claimed that ``it only requires one look" to see that   \begin{equation} \label{DedSum} F(m)-\sum F\left(\frac{m}{a}\right)+\sum F\left(\frac{m}{ab}\right)-\mathrm{etc.} \end{equation} simplifies to $f(m)$.

Tasks \ref{evid1} and \ref{evid2} provide reason to believe that Dedekind's claim is, in fact, true, but certainly do not constitute a proof.  Let's try a slightly more complicated example with the hope that it will give us an idea how to prove (\ref{MobInv1}) is true for {\it any} value of $m$.

\begin{task}[\label{messyex}]
Let $m=2^4\cdot3^{12}\cdot5^3\cdot7^{11}$.  Let $k=2^2 \cdot 3^{12} \cdot 5^2 \cdot 7^{10}$.  We'll count how many times $f(k)$ appears in each of the sums in (\ref{DedSum}).
\begin{enumerate}[(a)]
\item Remember $F(m)=\sum_{d|m} f(d)$. How many times does $f(k)$ appear in this sum?
\item How many times does $f(k)$ appear in $$\sum_{a} F\left(\frac{m}{a}\right)=\sum_{a} \sum_{d|\frac{m}{a}} f(d)?$$
The sum on the left of the equality is over distinct primes, $a$, in the factorization of $m$.

\smallskip

(The way to read double sums like this is to fix a prime $a$ in the outer sum, then work through the inner sum for that value of $a$.  Then change to another value of $a$, work through the inner sum, etc., until you've exhausted all the primes that divide $m$.)

\smallskip
\item How many times does $f(k)$ appear in $$\sum_{a,b} F\left(\frac{m}{ab}\right)=\sum_{a,b} \sum_{d|\frac{m}{ab}} f(d)?$$
The sum on the left of the equality is over pairs of distinct primes in the factorization of $m$.
\item How many times does $f(k)$ appear in $$\sum_{a,b,c} F\left(\frac{m}{abc}\right)=\sum_{a,b,c} \sum_{d|\frac{m}{abc}} f(d)?$$

\item How many times does $f(k)$ appear in $$\sum_{a,b,c,e} F\left(\frac{m}{abce}\right)=\sum_{a,b,c,e} \sum_{d|\frac{m}{abce}} f(d)?$$
\item This is where (\ref{DedSum}) ends for this example. Why?
\item Finally, add and subtract your answers to parts 1, 2, 3, 4, and 5 appropriately.   Do you obtain the value you expected?
\item There is only one divisor of $m$ for which something similar {\it won't} happen.  What divisor is this?
\end{enumerate}
\end{task}

\begin{task}
Repeat Task \ref{messyex} with $k=2^4 \cdot 3^{12}.$
\end{task}

  We're ready to make the idea above general.   Let $$m=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_l^{\alpha_l}.$$ We may as well assume that $\alpha_i>0$ for each $i$.  Any divisor of $m$ is of the form $$k=p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_l^{\beta_l}$$ where $0 \leq \beta_i \leq \alpha_i$ for each $i$.

\begin{task}
We've allowed the $\beta$'s to be zero, but not the $\alpha$'s. Why?
\end{task}

Notice, the key to the counting in Task \ref{messyex} was to look at the exponents in the prime factorizations of $m$ and $k$.

One of two things happens for any given $i$: either $\beta_i < \alpha_i$ or $\beta_i=\alpha_i$.

\begin{task}
If  $\beta_i < \alpha_i$ for $M$ different values of $i$, how many terms in (\ref{DedSum}) will count $f(k)$? That is, in how many of the sums in (\ref{DedSum}) does $f(k)$ appear? It doesn't matter whether the difference $\alpha_i-\beta_i$ is 1 or 21.  Why?
\end{task}

\begin{task}
In the case $\beta_i=\alpha_i$ for all values of $i$, which of the terms in (\ref{DedSum}) will count $f(k)$?  Why?
\end{task}

Now, let $M$ be the size of the set $\{\alpha_i - \beta_i \neq 0\}$.  That is, $M$ is the number exponents in the prime factorization of $k$ that are smaller than those of $m$. Keep in mind, we are focusing on one particular divisor, $k$, at a time.

In order to count effectively we'll use a function from combinatorics.  The function  ${M \choose t}$ \footnote{read ``$M$ choose $t$"} is the number of ways to choose $t$ items from a collection of $M$ items when the order in which they are chosen doesn't matter.

\begin{task}[\label{DedekindProof}]
We're ready to repeat the idea in Task \ref{messyex} in general. For any particular divisor $k$, of $m$:
\begin{enumerate}[(a)]
\item Remember $F(m)=\sum_{d|m} f(d)$. How many times does $f(k)$ appear in this sum?
\item How many times does $f(k)$ appear in $$\sum_{p_i} F\left(\frac{m}{p_i}\right)=\sum_{p_i} \sum_{d|\frac{m}{p_i}} f(d)?$$
\item How many times does $f(k)$ appear in $$\sum_{p_i, p_j} F\left(\frac{m}{p_ip_j}\right)=\sum_{p_i,p_j} \sum_{d|\frac{m}{p_ip_j}} f(d)?$$ ($p_i \neq p_j$)
\item How many times does $f(k)$ appear in $$\sum_{p_i, p_j, p_r} F\left(\frac{m}{p_ip_jp_r}\right)=\sum_{p_i, p_j, p_r} \sum_{d|\frac{m}{p_ip_jp_r}} f(d)?$$
\item How many times does $f(k)$ appear in $$\sum_{p_i, p_j, p_r,p_s} F\left(\frac{m}{p_ip_jp_rp_s}\right)=\sum_{p_i, p_j, p_r,p_s} \sum_{d|\frac{m}{p_ip_jp_rp_s}} f(d)?$$
\item What is the form of the last, non-empty sum?  That is, what is the last term in (\ref{DedSum}) that counts an occurrence of $f(k)$? How many times does $f(k)$ appear in this last sum?
\item \label{finalsum} Add and subtract your answers appropriately to the above parts.
\end{enumerate}


\end{task}

To finish we'll need the Binomial Theorem:
$$(x-y)^M=1-{M \choose 1}x^{M-1}y+{M \choose 2}x^{M-2}y^2-{M \choose 3}x^{M-3}y^3+\dots +(-1)^M{M \choose M}y^M.$$

\begin{task}
Compare your answer in part (\ref{finalsum}) above to the Binomial Theorem.  Pick values for $x$ and for $y$ that make the two expressions the same, and hence compute the sum.
\end{task}

\begin{task}[\label{Day4E}]
If you haven't already taken into account the case when $k=m$, explain what happens in this case.
\end{task}

This ends a proof of Dedekind's presentation of M\"{o}bius inversion.




\section{Laguerre and Mertens: evolution of M\"{o}bius inversion}

Next, Edmond Laguerre (1834--1886) and Franz Carl Joseph Mertens (1840--1927)   contributed to the story of M\"{o}bius inversion.  Their papers appeared at similar times; we'll look at Laguerre's work first.

Laguerre was the first to present the theorem of M\"{o}bius inversion in the format used today. This excerpt is from his paper {\it Sur quelques th\'{e}or\`{e}mes d'arithm\'{e}tique} ({\it On several theorems of arithmetic}) \citep{Laguerre}.

\newpage

\vspace*{-40pt}
\begin{source}
Let $\lambda(n)$ designate a number equal to 0 if $n$ is divisible by a square, and in the other case, equal to $\pm 1$ according to whether the number of factors of $n$ is even or odd. Suppose two functions $f(m)$ and $\varphi(m)$ are connected by the following relation $$f(m)=\sum\varphi(d)$$ where in the second part the summation extends over all the divisors of the integer $m$.  Reciprocally, one has
\begin{equation}
\label{MobInv2}
\varphi(m)=\sum\lambda\left(\frac{m}{d}\right)f(d),
\end{equation}
 the summation also extending over all the divisors of $m$.
\end{source}

\begin{task}[\label{Day4HWS}]
Which function in Laguerre's statement is the M\"{o}bius function?
\end{task}

\begin{task}[\label{Day4HWE}]
The first sentence in this excerpt should be more precise.  How?
\end{task}

\begin{task}[\label{Day5S}]
Explain how the right hand sides of equations (\ref{MobInv1}) and (\ref{MobInv2}) are the same.
\end{task}

Laguerre used the letter $\varphi$   because he was, in particular, interested in deriving a formula for Euler's totient function $\varphi(n)$.  However, the statement holds for any arithmetic function. \footnote{We'll return to $\varphi(n)$ a little later.}


Mertens introduced the modern notation for the M\"{o}bius function, namely the choice of the letter $\mu$, and provided a more succinct definition than that of M\"{o}bius.  You might notice he also took advantage of prime factor notation. The following excerpt is from {\it Ueber einige asymptotische Gesetze der Zahlentheorie} (On several asymptotic laws in number theory) \citep{Mertens}.

\begin{source}
Denote by $\mu n$ a number depending on $n$ in such a way that $\mu n=0$ if
$n$ admits a quadratic divisor (other than $1$), but otherwise possesses the
value $+1$ or $-1$, according to whether $n$ is composed of an even (the case
of $1$ belongs here) or odd number of different prime factors. If $m$ is
decomposed into its prime factors $=a^{\alpha}b^{\beta}\dots$, then $\varphi
m$, as is generally known, is given via the formula%
\begin{align*}
\varphi m  &  =m\left(  1-\frac{1}{a}\right)  \left(  1-\frac{1}{b}\right)  \cdots\\
&  =\sum\mu T\ \frac{m}{T},
\end{align*}
where the summation extends over all divisors of $m$.
\end{source}





\begin{task} [\label{factor}]
There is an interesting result at the end of the excerpt.  Don't worry about the first equality; we'll come back to that later.  The second equality is known as an Euler product.  Prove this equality by expanding the product $$m\left(1-\frac{1}{a}\right)\left(1-\frac{1}{b}\right)\cdots.$$ In particular, make sure to explain why the M\"{o}bius function appears.
\end{task}

\end{document}
