NTIC Generalizing Moebius

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

🔗

Theorem 23.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.

$f\star g=g\star f$
$(f\star g)\star h = f\star (g\star h)$
$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!

🔗

Theorem 23.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:

$\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}\text{.} \end{equation*}$

🔗

Proof.

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)

🔗

Corollary 23.4.4.

This can be immediately used to show that the Moebius function $\mu$ is $\mu=u^{-1}$ (and hence $u=\mu^{-1}$ ).

🔗

Corollary 23.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.

🔗

Corollary 23.4.6.

The subset of $A$ which consists of all arithmetic functions with $f(1)\neq 0$ is actually a group.

🔗

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 [C.2.8, Chapters 3 and 4]. For good exercises see [C.4.6, Chapter 2] or [C.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.

🔗

Fact 23.4.8.

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

🔗

Fact 23.4.9.

Conversely, if $g=f\star \mu\text{,}$ 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.

🔗

Proposition 23.4.10.

If $g$ and $h$ are multiplicative, then $f=g\star h$ is also multiplicative.

🔗

Proof.

See Exercise 23.5.8.

🔗

The next result has a long proof, but most of it is following the definitions and keeping careful track of indices. See [C.2.1, Exercise 8.20] or [C.2.13, Chapter 5.3] for similar approaches.

🔗

Proposition 23.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

\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.

🔗

Lemma 23.4.12.

We know that both $f^{-1}(1)=\frac{1}{f(1)}$ and $f(1)=1=f^{-1}(1)$

🔗

Proof.

Left to the reader in Exercise 23.5.10; use everything you know about $f\text{.}$

🔗

Lemma 23.4.13.

Assume as above that $f^{-1}$ is multiplicative for inputs less than $mn\text{,}$ with $\gcd(m,n)=1\text{.}$ Then

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

🔗

Proof.

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

🔗

Lemma 23.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*}

\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.6.

🔗

Corollary 23.4.15.

The function $\mu$ is multiplicative.

🔗

Proof.

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