§ Dirichlet inversion

We call all functions f:ZRf: \mathbb Z \rightarrow \mathbb R as arithmetic functions, since they operate on the integers. We introduce an operator fg:ZRf \star g: \mathbb Z \rightarrow \mathbb R. It is defined by:
  • (fg)(n)dnf(d)g(n/d)(f \star g)(n) \equiv \sum_{d \vert n} f(d) g(n/d)
We will show that the set of arithmetic functions forms a group under the operator \star, with identity:
id(n)1/n={1n=10otherwiseid_\star(n) \equiv \lfloor 1/n \rfloor = \begin{cases} 1 & n = 1 \\ 0 & \text{otherwise} \end{cases}
The reason all of this is interesting is that the inverse of the constant function 1(n)11(n) \equiv 1 is going to be this function called as the mobius function μ\mu:
μ(n=p1α1p2α2prαr){0if any αi>1(1)α1+α2++αrif all αi{0,1} \mu(n=p_1^{\alpha_1} p_2^{\alpha_2} \dots p_r^{\alpha_r}) \equiv \begin{cases} 0 & \text{if any $\alpha_i > 1$} \\ (-1)^{\alpha_1 + \alpha_2 + \dots + \alpha_r} & \text{if all $\alpha_i \in \{ 0, 1 \}$} \end{cases}
The mobius function will allow us to perform mobius inversion:
f(n)dng(d)=dng(d)1(n/d)=g1f11=g111fμ=g \begin{aligned} f(n) &\equiv \sum_{d \vert n} g(d) = \sum_{d \vert n} g(d) 1(n/d) = g \star 1 \\ f \star 1^{-1} &= g \star 1 \star 1^{-1} \\ f \star \mu &= g \end{aligned}
That is, we originally had ff defined in terms of gg. We can recover an expression for gg in terms of ff.

§ The algebra of multiplicative functions

We claim that the set of functions {ZC}\{ \mathbb Z \rightarrow \mathbb C \} is a commutative group, with the group operation \star such that:
  • (fg)(n)dnf(d)g(n/d)(f \star g)(n) \equiv \sum_{d \vert n} f(d) g(n/d).
with the identity element being id(n)1/nid_\star(n) \equiv \lfloor 1 / n \rfloor. The idea is that if (n=1)(n = 1), then 1/1=1\lfloor 1/1 \rfloor = 1, and for any other number n>0n > 0, 1/n<11/n < 1, hence 1/n=0\lfloor 1/n \rfloor = 0.

§ verification of istaristar being the identity

(fid)(n)dnf(d)id(n/d)=f(n)id(1)+dn,d>1f(n)id(d)=f(n)1+dn,d>1f(n)0=f(n) \begin{aligned} &(f \star id_\star)(n) \equiv \sum_{d \vert n} f(d) id_\star(n/d) \\ &= f(n) id_\star(1) + \sum_{d \vert n, d > 1} f(n) id_\star(d) \\ &= f(n) \cdot 1 + \sum_{d \vert n, d > 1} f(n) \cdot 0 \\ &= f(n) \\ \end{aligned}

§ associativity, commutativity of \star

To prove associativity, it's better to write the formula as:
(fg)(n)dnf(n)g(n/d)=xy=nf(x)g(y) (f \star g)(n) \equiv \sum_{d \vert n} f(n) g(n/d) = \sum_{xy = n} f(x) g(y)
From this rewrite, it's clear that (fgh)(n)(f \star g \star h)(n) will unambiguously sum over tripes (x,y,z)(x, y, z) such that xyz=nxyz = n. I leave the working-this-out to you. This should also make the commutativity immediate. Summing over pairs of the form f(x)g(y):xy=nf(x) g(y) : xy = n is the same as summing over f(y)g(x):yx=nf(y) g(x) : yx = n.

§ Existence of inverse

We can show that an inverse exists by showing that a formula for it exists; The idea is to construct one by induction. Clearly, for a given function ff, we need the inverse f1f^{-1} to be such that (ff1)(n)=id(f \star f^{-1})(n) = id_\star. Hence:
(ff1)(1)=id(1)=1f(1)f1(1)=1f1(1)1/f(1) \begin{aligned} &(f \star f^{-1})(1) = id_\star(1) = 1 \\ &f(1) f^{-1}(1) = 1 \\ & f^{-1}(1) \equiv 1 / f(1)\\ \end{aligned}
Great, we have a base case; We can now compute f1(n)f^{-1}(n) inductively, assuming we know the value of f1(d)f^{-1}(d) for all dnd \vert n.
(ff1)(n)=id(1)=0dnf(d)f1(n/d)=0f(1)f1(n)+dn,d<nf(d)f1(n/d)=0f1(n)=dn,d<nf(d)f1(n/d)f(1) \begin{aligned} &(f \star f^{-1})(n) = id_\star(1) = 0 \\ &\sum_{d \vert n} f(d) f^{-1}(n/d) = 0 \\ &f(1) f^{-1}(n) + \sum_{d \vert n, d < n} f(d) f^{-1}(n/d) = 0 \\ &f^{-1}(n) = -\frac{\sum_{d \vert n, d < n} f(d) f^{-1}(n/d)}{f(1)} \end{aligned}

§ μ\mu as the inverse of the oneone function

§ Mobius inversion

Now that we know that μ=const 11\mu = \texttt{const 1}^{-1}, we can use this fact to perform mobius inversion:
f(n)dng(n/d)=const 1g f(n) \equiv \sum_{d \vert n} g(n/d) = \texttt{const 1} \star g
We have ff written in terms of gg. We can now write gg in terms of ff:
f(n)=const 1gfconst 11=gg=fμg=dnf(d)μ(n/d) \begin{aligned} &f(n) = \texttt{const 1} \star g \\ &f \star \texttt{const 1}^{-1} = g \\ &g = f \star \mu \\ &g = \sum_{d \vert n} f(d) \mu(n/d) \end{aligned}

§ n=dnϕ(d)n = \sum_{d \vert n} \phi(d)

d{1x12:(x,12)=d}{1x12:(x/d,12/d)=1}size of set1{1,5,7,11}(x,12)=142{2,10}(x/2,6)=123{3,9}(x/3,4)=124{4,8}(x/4,3)=126{6}(x/6,2)=1112{12}(x/12,1)=11 \begin{array}{|c|c|c|c|} d & \{ 1 \leq x \leq 12 : (x, 12) = d \} & \{ 1 \leq x \leq 12: (x/d, 12/d) = 1\} & \text{size of set} \\ 1 & \{ 1, 5, 7, 11 \} & (x, 12) = 1 & 4 \\ 2 & \{2, 10 \} & (x/2, 6) = 1& 2 \\ 3 & \{3, 9 \} & (x/3, 4) = 1 & 2 \\ 4 & \{4, 8 \} & (x/4, 3) = 1 & 2 \\ 6 & \{ 6 \} & (x/6, 2) = 1 & 1 \\ 12 & \{ 12 \} (x/12, 1) = 1 & 1 \end{array}
Notice that the sizes of sets that we are calculating, for example, {1x12:(x/2,6)=1}=ϕ(6)|\{ 1 \leq x \leq 12 : (x/2, 6) = 1 \}| = \phi(6). Summing over all of what we have, we've counted the numbers in [1,2,,12][1, 2, \dots, 12] in two ways --- one directly, and the other by partitioning into equivalence classes:
12=ϕ(1)+ϕ(2)+ϕ(3)+ϕ(4)+ϕ(6)+ϕ(12)=d12ϕ(12/d) 12 = \phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(12) = \sum_{d \vert 12} \phi(12/d)
In general, the same argument allows us to prove that:
n=dnn/d n = \sum_{d \vert n} n/d

§ Using mobius inversion on the euler totient function

§ Other arithmetical functions and their relations