Section23.4Generalizing Moebius
There is a more serious side as well, though, and 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 inverses. (That means it's not a group.)
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)\), which is equal to zero except when \(n=1\), plays the role of identity. Then one would need to prove the following.
- \(f\star g=g\star f\)
- \((f\star g)\star h = f\star (g\star h)\)
- \(f\star I=f = I\star f\)
The only one of these that's even a little hard is the second one, but one can use the fact that \(dc=n,ab=d\) implies \(abc=n\) to do it. Here is an example; the others are similar.
Proof of commutativity: \[f\star g=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)=\sum_{de=n}f(d)g(e)\] \[=\sum_{de=n}g(e)f(d)=\sum_{e\mid n}g(e)f\left(\frac{n}{e}\right)\]
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 \[(f\star g)(n)=\sum_{de=n}f(d)g(e)\; .\]
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{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}\]Proof
As in the best theorems, there is really nothing to prove; we can always get the next \(f^{-1}(n)\) by knowledge of \(f^{-1}(d)\) for \(d\mid n\), and that is induction since we do have a formula given for \(f^{-1}(1)\).
Notice that means exactly that the Moebius function \(\mu\) is \(\mu=u^{-1}\). In general, we can also say that \[f\star f^{-1}=I=f^{-1}\star f\] There is another, more theoretical, implication.
Try to figure out what the inverse of \(N\) or \(\phi\) is with paper and pencil.
Corollary23.4.4
The subset of \(A\) where \(f(1)\neq 0\) is actually a group.
Subsection23.4.3More dividends from structure
This new way of looking at things yields a slew of information about arithmetic functions which will yield dividends about analysis/calculus (no, we haven't forgotten that!) immediately.
Fact23.4.5
The Moebius inversion formula that if \(f=g\star u\) then \(g=f\star \mu\) can be proved concisely by \[g=g\star I=g\star u\star \mu=f\star \mu\] (We need no parentheses, since \(\star\) is associative).
Fact23.4.6
Conversely, if \(g=f\star \mu\), then \[f=f\star I=f\star \mu\star u=g\star u\] so the inversion formula is true in both directions.
Proposition23.4.7
If \(f\) is multiplicative and \(f(1)\neq 0\), then \(f^{-1}\) is also multiplicative.Proof
This basically can be done by induction. First, recall that the inverse is defined by \[f^{-1}(1)=\frac{1}{f(1)}\] and, for \(n>1\), the condition \[\sum_{d\mid n}f^{-1}(d)f\left(\frac{n}{d}\right)=\sum_{de=n}f^{-1}(d)f(e)=0\, .\] Some preliminary facts for \(n=1\) are first useful.
- First, \[f^{-1}(1)=\frac{1}{f(1)}\neq 0\; .\]
- Also, \[f(1\cdot n)=f(1)f(n)\text{ so }f(1)=1=f^{-1}(1)\; .\]
Next, assume that \(f^{-1}\) is multiplicative for inputs less than \(mn\), with \(gcd(m,n)=1\). Then let \(m,n>1\) and coprime. We will be able to dissolve everything.
- By the definition of inverse, we have \[0=(f^{-1}\star f)(mn)=\sum_{x<mn,\; xy=mn}\left(f^{-1}(x)f(y)\right)+f^{-1}(mn)f(1)\; .\]
- Note that the only piece we do not know is multiplicative here is \(f^{-1}(mn)\); all the others (\(x,y\), and anything to do with \(f\)) are multiplicative by induction or by assumption.
- Each summand is over \(xy\). Each \(xy\) is itself, by coprimeness of \(m\) and \(n\), itself a product \(x=ab\) and \(y=cd\) of things that are coprime - \(a,c\mid m\) and \(b,d\mid n\).
- So multiplicativity implies \[f^{-1}(x)f(y)=f^{-1}(a)f^{-1}(b)f(c)f(d)\; .\]
This gives, along with \(f(1)=1\) and the sum being zero, \[f^{-1}(mn)=-\sum_{(ac)(bd)=(m)(n),\; ab < mn}f^{-1}(a)f^{-1}(b)f(c)f(d)\] So now we have to figure out how to write this sum in terms of things we already know.
- Notice that if we didn't have \(ab<mn\), the sum would easily simplify as a product: \[\sum_{(ac)(bd)=(m)(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)\]
- We are only missing the term with \(a=m,b=n\) from this sum, in fact.
- So \[\sum_{(ac)(bd)=(m)(n),\; ab < mn}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)-f^{-1}(m)f^{-1}(n)f(1)f(1)\]
Now we plug this back into the previous characterization of \(f^{-1}(mn)\): \[f^{-1}(mn)=- \left[\sum_{ac=m}f^{-1}(a)f(c)\sum_{bd=n}f^{-1}(b)f(d)-f^{-1}(m)f^{-1}(n)f(1)f(1)\right]\] And since \(m,n>1\), the sums are just \[(f^{-1}\star f)(m)=I(m)=0=I(n)=(f^{-1}\star f)(n)\] That means \[f^{-1}(mn)=f^{-1}(m)f^{-1}(n)\] as well.
We promised the following corollary at the beginning of this chapter.
Corollary23.4.8
The function \(\mu\) is multiplicative.Proof
This follows since \(u\) is multiplicative (trivially) and \(\mu=u^{-1}\).
Proposition23.4.9
If \(g\) and \(h\) are multiplicative, then \(f=g\star h\) is also multiplicative.Proof
