There is a more serious side to the panoply of new functions, though. This is our key to arithmetic functions. We will now turn to algebra again, with a goal of generalizing the Moebius result.
Subsection23.4.1The monoid of arithmetic functions
Definition23.4.1.
A commutative monoid is a set with multiplication (an operation) that has an identity, is associative and commutative.
You can think of a commutative monoid as an Abelian group without requiring inverses. (That means it’s not necessarily a group, though it could be; see Definition 8.3.3.)
Theorem23.4.2.
Let \(A\) be the set of all arithmetic functions. Then \(\star\) turns the set \(A\) into a commutative monoid.
Proof.
The function \(I(n)\text{,}\) which is equal to zero except when \(n=1\text{,}\) plays the role of identity. Then one would need to prove the following three statements.
\(\displaystyle f\star g=g\star f\)
\(\displaystyle (f\star g)\star h = f\star (g\star h)\)
\(\displaystyle f\star I=f = I\star f\)
We include one of the proofs. The others are similar – see Exercise 23.5.2. Note that for the second one, one can use the fact that \(dc=n,ab=d\) implies \(abc=n\text{.}\)
This structure is so neat is because it actually allows us to generalize the idea behind the Moebius function!
Theorem23.4.3.
If \(f\) is an arithmetic function and \(f(1)\neq 0\text{,}\) then \(f\) has an inverse in the set \(A\) under the operation \(\star\text{.}\) We call this inverse \(f^{-1}\text{.}\) It is given by the following recursive definition:
As in all the best theorems, there is really nothing to prove. The definitions for \(n>1\) are equivalent ways of representing the same thing. We can always get the next value of \(f^{-1}(n)\) by knowledge of \(f^{-1}(d)\) for \(d\mid n\text{,}\) and that is enough for an induction proof, since we do have a formula given for \(f^{-1}(1)\text{.}\) (See Exercise 23.5.9)
Corollary23.4.4.
This can be immediately used to show that the Moebius function \(\mu\) is \(\mu=u^{-1}\) (and hence \(u=\mu^{-1}\)).
Corollary23.4.5.
Since \(\omega(1)=0\text{,}\) the function \(\omega\) has no inverse.
This is a good time to try to figure out what the inverse of \(N\) or \(\phi\) is with paper and pencil. See Exercises Exercise 23.5.4 and Exercise 23.5.5.
In general, we can also say that
\begin{equation*}
f\star f^{-1}=I=f^{-1}\star f
\end{equation*}
There is another, more theoretical, implication too, hearkening back to Section 8.3.
Corollary23.4.6.
The subset of \(A\) which consists of all arithmetic functions with \(f(1)\neq 0\) is actually a group.
Remark23.4.7.
Much of this chapter is done in slightly variant ways in introductory books, at a similar level. For a higher-level but useful and readable account of the ring theory of arithmetic functions (including valuations and derivations), see [E.2.8, Chapters 3 and 4]. For good exercises see [E.4.6, Chapter 2] or [E.2.9, Chapter 2]; for instance, the latter asks for identifying the idempotents of \(A\text{.}\)
Subsection23.4.3More dividends from structure
This new way of looking at things yields an immediate slew of information about arithmetic functions. The following results will yield dividends about number theory and analysis/calculus (no, we haven’t forgotten that!) in the next chapter on Infinite Sums and Products.
Fact23.4.8.
The Moebius inversion formula that if \(f=g\star u\) then \(g=f\star \mu\) can be proved concisely by
The next result has a long proof, but most of it is following the definitions and keeping careful track of indices. See [E.2.1, Exercise 8.20] or [E.2.13, Chapter 5.3] for similar approaches.
Proposition23.4.11.
If \(f\) is multiplicative and \(f(1)\neq 0\text{,}\) then \(f^{-1}\) is also multiplicative.
Proof.
This basically can be done by induction, but each step is somewhat involved so we will break this into several lemmata. Throughout, recall that the inverse is defined by
First, in Lemma 23.4.12 we will show that \(f^{-1}(1)\) behaves well.
Then, assuming as an inductive hypothesis that \(f^{-1}\) is multiplicative for inputs less than \(mn\text{,}\) with \(\gcd(m,n)=1\text{,}\) we will show in Lemma 23.4.13 that
\begin{equation*}
f^{-1}(mn)=-\sum_{\substack{(ac)(bd)=(m)(n)\\ab < mn,\; a\mid m, \; b\mid n}}f^{-1}(a)f^{-1}(b)f(c)f(d)
\end{equation*}
Finally, in Lemma 23.4.14 we will show how to rewrite this as
By assumption, every function in this expression (both \(f\) and \(f^{-1}\)) is multiplicative on the values in question, with the possible exception of \(f^{-1}(mn)\text{.}\)
We can use this effectively because each summand is for a divisor \(x\mid mn\text{,}\) which we can write as \(xy=mn\text{.}\) Since \(m\) and \(n\) are coprime, both \(x\) and \(y\) are themselves products of coprime divisors dividing \(m\) and \(n\) respectively.
So let \(x=ab\) and \(y=cd\text{,}\) where \(a,c\mid m\) and \(b,d\mid n\text{.}\) Then, as everything is multiplicative, \(f^{-1}(x)f(y)=f^{-1}(a)f^{-1}(b)f(c)f(d)\text{.}\)
Since by the previous lemma \(f(1)=1\text{,}\) we can subtract the summation from both sides of the equation whose left-hand side is zero at the beginning of this lemma’s proof, yielding
\begin{equation*}
f^{-1}(mn)=-\sum_{\substack{(ac)(bd)=(m)(n)\\ab < mn,\; a\mid m, \; b\mid n}}f^{-1}(a)f^{-1}(b)f(c)f(d)\text{.}
\end{equation*}
Lemma23.4.14.
Under the same hypotheses as before, \(f^{-1}(mn)=f^{-1}(m)f^{-1}(n)\text{.}\)
Proof.
We now write all this in terms of things we already can evaluate.
If the sum in question were summed over every \(ab\leq mn\) instead of \(ab<mn\text{,}\) it would easily simplify as a product:
\begin{equation*}
\sum_{\substack{(ac)(bd)=(m)(n)\\a\mid m, \; b\mid n}}f^{-1}(a)f^{-1}(b)f(c)f(d)=\sum_{ac=m}f^{-1}(a)f(c)\sum_{bd=n}f^{-1}(b)f(d)
\end{equation*}
The sum in Lemma 23.4.13 only lacks the term with \(a=m,b=n\text{,}\) in fact. So
\begin{equation*}
\sum_{\substack{(ac)(bd)=(m)(n)\\ab < mn,\; a\mid m, \; b\mid n}}f^{-1}(a)f^{-1}(b)f(c)f(d)=
\end{equation*}