Definition23.4.1
A commutative monoid is a set with multiplication (an operation) that has an identity, is associative and commutative.
Section23.4Generalizing Moebius¶ permalink
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
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.)
Theorem23.4.2
Let \(A\) be the set of all arithmetic functions. Then \(\star\) turns the set \(A\) into a commutative monoid.
Can you think of other commutative monoids? What sets have an operation and an identity, but no inverse?
Subsection23.4.2Bringing in group structure
Let's get deeper in the algebraic structure behind the \(\star\) operation. Remember, \(f\star g\) is defined by \begin{equation*}(f\star g)(n)=\sum_{de=n}f(d)g(e)\; .\end{equation*}
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\), then \(f\) has an inverse in the set \(A\) under the operation \(\star\). We call this inverse \(f^{-1}\). It is given by the following recursive definition: \begin{equation*}\begin{cases} f^{-1}(1)=\frac{1}{f(1)} & n=1\\ \sum_{d\mid n}f^{-1}(d)f\left(\frac{n}{d}\right)=\sum_{de=n}f^{-1}(d)f(e)=0& n>1\end{cases}\end{equation*}
Corollary23.4.4
This says exactly that the Moebius function \(\mu\) is \(\mu=u^{-1}\).
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.
Corollary23.4.5
The subset of \(A\) which consists of all arithmetic functions with \(f(1)\neq 0\) is actually a group.
Subsection23.4.3More dividends from structure¶ permalink
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.6
The Moebius inversion formula that if \(f=g\star u\) then \(g=f\star \mu\) can be proved concisely by \begin{equation*}g=g\star I=g\star u\star \mu=f\star \mu\end{equation*} (We need no parentheses, since \(\star\) is associative).
Fact23.4.7
Conversely, if \(g=f\star \mu\), then \begin{equation*}f=f\star I=f\star \mu\star u=g\star u\end{equation*} so the inversion formula is true in both directions.
Proposition23.4.8
If \(g\) and \(h\) are multiplicative, then \(f=g\star h\) is also multiplicative.
The next result has a long proof, but most of it is following the definitions and keeping careful track of indices.
Proposition23.4.9
If \(f\) is multiplicative and \(f(1)\neq 0\), then \(f^{-1}\) is also multiplicative.
Lemma23.4.10
We know that both \(f^{-1}(1)=\frac{1}{f(1)}\) and \(f(1)=1=f^{-1}(1)\)
Lemma23.4.11
Assume as above that \(f^{-1}\) is multiplicative for inputs less than \(mn\), with \(\gcd(m,n)=1\). Then \begin{equation*}f^{-1}(mn)=-\sum_{(ac)(bd)=(m)(n),\; ab < mn}f^{-1}(a)f^{-1}(b)f(c)f(d)\end{equation*}
Lemma23.4.12
Under the same hypotheses as before, \(f^{-1}(mn)=f^{-1}(m)f^{-1}(n)\).
Finally, we get the following promised corollary from the beginning of the chapter, Fact 23.1.6.
Corollary23.4.13
The function \(\mu\) is multiplicative.