**An ant in our community** has taken a trip on a hyperbolic tree, which on the large scale looks like a pair of pants. In his struggle to understand the combinatorics of very long geodesics at its surface, he is encountering monstruous looking formulas involving arithmetical beasts. Let’s help him identify those creatures.

**Our journey starts with Eulers totient function **$\phi(n)$ which counts the number of positive intergers $m$ smaller and coprime with $n$.

This function satisfies pleasing formulas like $\sum_{d|n}{\phi(d)}=n$ where the sum is on all positive divisors of $n$. This can be seen by writting down all the fractions between $\frac{1}{n}$ and $\frac{n}{n}$ with denominator $n$, and then reducing them. Partitionning them by the values $d$ of their denominators, we shall get $\phi(d)$ fractions with lower denominator $d$. Can you make this rigorous ?

Another nice formula is $\phi(n)=n\prod_{p|n}{(1-p^{-1})}$ where the product is on prime factors of $n$. This can be understood working on the finite probability space $[1,n]$ with uniform distribution, and noticing that being coprime with $n$ is equivalent to being divisible by none of its prime divisors. So the probability of picking a coprime element with $n$ can be computed in two ways. It is by definition $\frac{\phi(n)}{n}$. And it is also the product over $n$’s prime divisors of the probabilities of not being divisible by $p$. But the probability of being divisible by $p$ is the number of multiples of $p$ in $[1,n]$ divided by $n$. Putting all this together yields the formula. One must just be carefull that we have supposed independance of the events “being divisible by $p$” for each prime divisor of $p$. Why is this true ?

This so called Euler totient function is quite a fascinating insect. The tree we are on is full of them, we might encounter some more later on…

**The next creature on our path is Riemann’s zeta function** $\zeta(s)=\sum_{n>0}\frac{1}{n^s}$. It is named after Riemann because he was interested in its behaviour on the complex plane but we shall only be considering $s$ real. Euler had already found a famous product formula: $$\zeta(s)=\prod_{p}{\sum_{k \geq 0}{p^{-ks}}} = \prod_{p}{\frac{1}{(1-p^{-s})}}$$

The second equality is just rewritting the geometric sums, but the first equality is crucial, and it is essentially equivalent to Gauss’s therem of unique decomposition of intergers into a product of prime powers. A good way to get the feeling of how it works is to try and expand the first few terms on the right side:

$$ (1+2^{-s}+2^{-2s}+\dots) \cdot (1+3^{-s}+3^{-2s}+\dots) \cdot (1+5^{-s}+5^{-2s}+\dots) \cdot \dots $$

Ignoring the $s$ for now, you have to choose one term in each parenthesis (the power of the prime). If the sequence of powers stagnates to zero then you get a term which is the inverse of the intger with associated prime power decomposition (to the power $s$). If the sequence doesn’t stagnate with zero powers then you get the inverse of infinity, which is zero. It is actually more subtle than this and one should be carefull about the convergence of series, but if $s$ has real part greater than $1$ then one can prove the product formula along those lines.

Before we introduce the next creature on our path, lets refer to our pocket bestiary which will enable us to better understand the features of all the Tree’s inhabitants.

**Arithmetical functions **are maps on the positive integers and we shall suppose thay take integer or real values. The Euler totient function is one of them, but you can define many other intersting ones like the constant function equal to one denoted $\mathbb{1}$, or the function which counts the number of divisors of an integer: $\sigma_{0}(n)=\sum_{d|n}{d^{0}}$. All those functions $f$ satisfy a tremenduous amount of curious identities and a good way of combining all those identities is to look at their Dirichlet series: $F(s)=\sum_{n>0}{\frac{f(n)}{n^{s}}}$. Note that Riemann’s zeta function is the Dirichlet series of $\mathbb{1}$, and that the Dirichlet series of the arithmetic function $\delta(n)$ which returns $1$ if $n=1$ and $0$ otherwise is the constant function of $s$ equal to $\Delta(s)=1$.

The sum of Dirichlet series simply corresponds to the sum of the associated arithmetic functions. The product of Dirichlet series $H=F.G$ induces an convoluted product on the corresponding arithmetical functions: $h(n)=(f\star g)(n)=\sum_{d|n}{f(d).g(n/d)}$. This at first seemingly awkward operation will enable to unify the variety of number theoretic identities. The philosophy is the following: a polynomial identity (like a product) on the Dirichlet series gives a convolution identity in the arithmetical functions. And as we shall see, it is sometimes straigthforward to get such formulas on the series, whereas the corresponding equality in terms of arithmetic functions is rather unnatural.

Let’s call an arithmetic function $f$ multiplicative if $f(mn)=f(m)f(n)$ when $m \wedge n =1$ (meaning $m$ and $n$ are coprime) and strongly multiplicative if this is true even without the coprimality assumption. In the latter case, one has a factorisation of its Dirichlet series into an Euler product, but in the former only the first equality holds:

$$F(s)=\prod_{p}{\sum_{k \geq 0}{\frac{f(p^{k})}{p^{-ks}}}} = \prod_{p}{\frac{1}{(1-f(p).p^{-s})}}$$

But this Euler product formula is also a way to define multiplicative functions, and obtain immediately its generating series. One just has to choose any values on the powers of primes and then declare it’s multiplicative. We can now introduce ourselves to the next monster on our path.

**Möbius function** $\mu$ can be defined on the powers of prime numbers: $\mu(p^{k})$ is one if $k$ is zero or one, and zero otherwise, and then declaring it to be multiplicative. One has immediately access to its Dirichlet function $M$ by the afforementionned process and we discover that it is the inverse of Riemann’s zeta function ! So $M.\zeta=1$ which translates to $\sum_{d|n}{\mu(d)}=\delta$.

The same process gives Möbius inversion formula. Suppose two arithmetic functions $f$ and $g$ are related by $g(n)=\sum_{d|n}{f(d)}$ then we can inverse this formula to get $f(n)=\sum_{d|n}{g(d).\mu(n/d)}$.

**We are now up on a high branch of our tree**, so lets admire the view and look back upon the trail we made. Remember the first formula about Euler’s totient function. Can you spot a convolution product to find that its Dirichlet series is $\frac{\zeta(s-1)}{\zeta(s)}$ ? What does that say on the eventual (strong) multiplicativity of $\phi$ ?

Here are a few questions to conclude. Can you prove that the Dirichlet series of $\sigma_{0}$ is $\zeta^{2}$ ? Can you find the generating series of $\sigma_{k}(n)=\sum_{d|n}{d^{k}}$ ?