§ Dirichlet inversion

We call all functions f:Z→Rf: \mathbb Z \rightarrow \mathbb R as arithmetic functions , since they operate on the integers. We introduce an operator f⋆g:Z→Rf \star g: \mathbb Z \rightarrow \mathbb R. It is defined by:
  • (f⋆g)(n)≡∑d∣nf(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α2…prα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)≡∑d∣ng(d)=∑d∣ng(d)1(n/d)=g⋆1f⋆1−1=g⋆1⋆1−1f⋆μ=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 {Z→C}\{ \mathbb Z \rightarrow \mathbb C \} is a commutative group, with the group operation ⋆\star such that:
  • (f⋆g)(n)≡∑d∣nf(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/n⌋id_\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

(f⋆id⋆)(n)≡∑d∣nf(d)id⋆(n/d)=f(n)id⋆(1)+∑d∣n,d>1f(n)id⋆(d)=f(n)⋅1+∑d∣n,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:
(f⋆g)(n)≡∑d∣nf(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 (f⋆g⋆h)(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 f−1f^{-1} to be such that (f⋆f−1)(n)=id⋆(f \star f^{-1})(n) = id_\star. Hence:
(f⋆f−1)(1)=id⋆(1)=1f(1)f−1(1)=1f−1(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 f−1(n)f^{-1}(n) inductively, assuming we know the value of f−1(d)f^{-1}(d) for all d∣nd \vert n.
(f⋆f−1)(n)=id⋆(1)=0∑d∣nf(d)f−1(n/d)=0f(1)f−1(n)+∑d∣n,d<nf(d)f−1(n/d)=0f−1(n)=−∑d∣n,d<nf(d)f−1(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 1−1\mu = \texttt{const 1}^{-1}, we can use this fact to perform mobius inversion :
f(n)≡∑d∣ng(n/d)=const 1⋆g 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 1⋆gf⋆const 1−1=gg=f⋆μg=∑d∣nf(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=∑d∣nϕ(d)n = \sum_{d \vert n} \phi(d)

d{1≤x≤12:(x,12)=d}{1≤x≤12:(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, ∣{1≤x≤12:(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)=∑d∣12ϕ(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=∑d∣nn/d n = \sum_{d \vert n} n/d

§ Using mobius inversion on the euler totient function

§ Other arithmetical functions and their relations