Skip to main content

Section 23.4 Generalizing Moebius

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.

Subsection 23.4.1 The monoid of arithmetic functions

Definition 23.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.)

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{.}\)

Proof of commutativity:

\begin{equation*} (f\star g)(n)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)=\sum_{de=n}f(d)g(e) \end{equation*}
\begin{equation*} =\sum_{de=n}g(e)f(d)=\sum_{e\mid n}g(e)f\left(\frac{n}{e}\right) = (g\star f)(n) \end{equation*}

Can you think of other commutative monoids? What sets have an operation and an identity, but no inverse?

Subsection 23.4.2 Bringing 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)\text{.} \end{equation*}

This structure is so neat is because it actually allows us to generalize the idea behind the Moebius function!

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)

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.

Remark 23.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{.}\)

Subsection 23.4.3 More 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.

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.

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

\begin{equation*} f^{-1}(1)=\frac{1}{f(1)} \end{equation*}

and, for \(n>1\text{,}\) the condition

\begin{equation*} \sum_{d\mid n}f^{-1}(d)f\left(\frac{n}{d}\right)=\sum_{de=n}f^{-1}(d)f(e)=0\text{.} \end{equation*}

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

\begin{equation*} f^{-1}(mn)=f^{-1}(m)f^{-1}(n) \end{equation*}

which finishes the induction argument.

Assume that \(m,n>1\) and coprime. By the definition of inverse, we have

\begin{equation*} 0=(f^{-1}\star f)(mn)=\left[\sum_{x<mn,\; xy=mn}\left(f^{-1}(x)f(y)\right)\right]+f^{-1}(mn)f(1)\text{.} \end{equation*}

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*}

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*}
\begin{equation*} \left[\sum_{ac=m}f^{-1}(a)f(c)\sum_{bd=n}f^{-1}(b)f(d)\right]-\left(f^{-1}(m)f^{-1}(n)f(1)f(1)\right) \end{equation*}

Now we can plug this back into the previous characterization of \(f^{-1}(mn)\text{:}\)

\begin{equation*} 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] \end{equation*}

Since \(m,n>1\text{,}\) the individual sums may be rewritten as

\begin{equation*} (f^{-1}\star f)(m)=I(m)=0=I(n)=(f^{-1}\star f)(n) \end{equation*}

That means we achieve the desired result

\begin{equation*} f^{-1}(mn)=f^{-1}(m)f^{-1}(n)f(1)f(1)=f^{-1}(m)f^{-1}(n) \end{equation*}

Finally, we get the following promised corollary from the beginning of the chapter, Fact 23.1.7.

This follows since \(u\) is multiplicative (trivially) and \(\mu=u^{-1}\text{.}\)