Exercise 4.3.21 (Variations on Möbius)

Proof.

• Suppose that for all positive integers $n$,

  $$\begin{array}{llllll}\hfill F(n)& =\underset{m\in [[1,N]],n\mid m}{\sum }f(m)& \hfill & & \hfill & \\ \hfill & =\underset{1\le k\le N∕n}{\sum }f(\mathit{kn})& \hfill (m=\mathit{kn}).& & \hfill & & \hfill \end{array}$$

  Then

  $$\begin{array}{lllllll}\hfill \underset{m\in [[1,N]],n\mid m}{\sum }\mu \left(\frac{m}{n}\right)F(m)& =\underset{1\le l\le N∕n}{\sum }\mu (l)F(\mathit{ln})& \hfill (m=\mathit{ln})& & \hfill & & \hfill \\ \hfill & =\underset{1\le l\le N∕n}{\sum }\mu (l)\underset{1\le k\le N∕(\mathit{ln})}{\sum }f(\mathit{kln})& \hfill & & \hfill & \\ \hfill & =\underset{1\le l\le N∕n}{\sum }\underset{1\le k\le N∕(\mathit{ln})}{\sum }\mu (l)f(\mathit{kln})& \hfill & & \hfill & \\ \hfill & =\underset{1\le \mathit{kl}\le N∕n}{\sum }\mu (l)f(\mathit{kln}),& \hfill & & \hfill & \end{array}$$

  because

  $$(1\le l\le N∕n,1\le k\le N∕(\mathit{ln}))⟺1\le \mathit{kl}\le N∕n.$$

  Next

  $$\begin{array}{llll}\hfill \underset{m\in [[1,N]],n\mid m}{\sum }\mu \left(\frac{m}{n}\right)F(m)& =\underset{1\le \mathit{kl}\le N∕n}{\sum }\mu (l)f(\mathit{kln})& \hfill & \\ \hfill & =\underset{1\le j\le N∕n}{\sum }\underset{\mathit{kl}=j}{\sum }\mu (l)f(\mathit{kln})& \hfill & \\ \hfill & =\underset{1\le j\le N∕n}{\sum }f(\mathit{jn})\underset{l\mid j}{\sum }\mu (l)& \hfill & \\ \hfill & =\underset{1\le j\le N∕n}{\sum }f(\mathit{jn})\delta (j)& \hfill & \\ \hfill & =f(n),& \hfill & \end{array}$$

  where by Theorem 4.7, ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{l\mid j}\mu (l)=\delta (j)=\{\begin{array}{cc}1\hfill & \text{if }j=1\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$

• Conversely, suppose that for all positive integers $n$,

  $$\begin{array}{llllll}\hfill f(n)& =\underset{m\in [[1,N]],n\mid m}{\sum }\mu \left(\frac{m}{n}\right)F(m)& \hfill & & \hfill & \\ \hfill & =\underset{1\le l\le N∕n}{\sum }\mu (l)F(\mathit{ln})& \hfill (m=\mathit{ln}).& & \hfill & & \hfill \end{array}$$

  Then

  $$\begin{array}{llll}\hfill \underset{m\in [[1,N]],n\mid m}{\sum }f(m)& =\underset{1\le k\le N∕n}{\sum }f(\mathit{kn})& \hfill & \\ \hfill & =\underset{1\le k\le N∕n}{\sum }\underset{1\le l\le N∕(\mathit{kn})}{\sum }\mu (l)F(\mathit{kln})& \hfill & \\ \hfill & =\underset{1\le \mathit{kl}\le N∕n}{\sum }\mu (l)F(\mathit{kln})& \hfill & \\ \hfill & =\underset{1\le j\le N∕n}{\sum }\underset{\mathit{kl}=j}{\sum }\mu (l)F(\mathit{kln})& \hfill & \\ \hfill & =\underset{1\le j\le N∕n}{\sum }F(\mathit{jn})\underset{l\mid j}{\sum }\mu (l)& \hfill & \\ \hfill & =\underset{1\le j\le N∕n}{\sum }F(\mathit{jn})\delta (j)& \hfill & \\ \hfill & =F(n).& \hfill & \end{array}$$

  In conclusion, the following assertions are equivalent:

  $$\begin{array}{llll}\hfill & (i)\forall <!--\; FUNCTION\; APPLICATION\; -->n\in {\mathbb{N}}^{\text{∗}},F(n)=\underset{m\in [[1,N]],n\mid m}{\sum }f(m).& \hfill & \\ \hfill & (\mathit{ii})\forall <!--\; FUNCTION\; APPLICATION\; -->n\in {\mathbb{N}}^{\text{∗}},f(n)=\underset{m\in [[1,N]],n\mid m}{\sum }\mu \left(\frac{m}{n}\right)F(m).& \hfill & \end{array}$$