Café Math : Arithmetic Functions (Part 1)
1, 1, 2, 2, 1, 8, 6, 7, 14, 27, 26, 80, 133, 170, 348, 765, 1002, 2176, 4682, ...   (A121350)
Math Blog
Articles
Talks
Teaching
Phd Thesis
Financial Maths
About me
PrevNext

Arithmetic Functions (Part 1)

Thu, 31 May 2012 23:56:12 GMT


1. Foreword

In the last blog article we touched a word on the Möbius function $\mu$ and the Möbius inversion formula. Another interesting way to see the topic is through arithmetic multiplicative functions.

Today I want to give an account of some of the most basic notions and results of this last subject. I hope you'll enjoy reading it as much as enjoyed writing it. As always, If you have any comment, suggestion, correction or want to say Hi! Use the comment section at the bottom of this page and/or send me an email.

2. Arithmetic Multiplicative Functions

Definition 1.

  1. An arithmetic function $f$ is an application $$f: \mathbb{N}^* \rightarrow \mathbb{C}.$$
  2. An arithmetic function is multiplicative if $f(1) = 1$ and $f(rs) = f(r)f(s)$ for all pairs of coprime integers $r$ and $s$.
  3. It is completely multiplicative if the relation, $$ f(rs) = f(r)f(s) $$ holds for every pair of positive integers $r$ and $s$, not necessarily coprime.

Multiplicative functions are fully determined by their value at the powers of prime numbers. For if the unique prime factorization of an integer $n$ is $p_1^{\alpha_1} \dots p_k^{\alpha_k}$ then, for any multiplicative function $f$ we have, $$f(n) = f(p_1^{\alpha_1}) \dots f(p_k^{\alpha_k}).$$ If the function $f$ is completely multiplicative, it is fully determined by its values at the prime alone, $$f(n) = f(p_1)^{\alpha_1} \dots f(p_k)^{\alpha_k}.$$

Examples.

  1. The function $I$ given by $I(n) = 1$ for all $n \ge 1$ is completely multiplicative. This one looks trivial but its Dirichlet series is none other than the celebrated Riemann function.
  2. The function $e$ given by $e(n) = \delta_{1,n}$ for all $n \ge 1$ is completely multiplicative. $$ e(n) = \begin{cases} 1 & \text{if $n = 1$,} \\ 0 & \text{else.} \end{cases} $$
  3. The function $\mathrm{Id}(n) = n$ is completely multiplicative and so is $\mathrm{Id}^\alpha(n) = n^\alpha$.
  4. The Möbius $\mu$ function is multiplicative, $$ \mu(n) = \begin{cases} 0 & \text{if $n$ isn't square free.} \\ (-1)^k & \text{if $n$ is square free with $k$ distinct prime factors.} \end{cases} $$
  5. The function $\sigma_\alpha(n)$ that gives the sum of $\alpha$-th power of divisors of $n$ is multiplicative. $$ \sigma_\alpha(n) = \sum_{d \,|\, n} d^\alpha . $$ Special cases: $d(n) = \sigma_0(n)$ the number of divisors of $n$, $\sigma(n) = \sigma_1(n)$ the sum of divisors of $n$.
  6. The Euler totient function $\phi(n)$ giving the number of positive integer $k \le n$ coprime to $n$ is multiplicative, $$ \phi(n) = n\,\prod_{p \,|\, n} \left(1 - \frac{1}{p}\right), $$ where the product runs over the set of prime divisors of $n$.
  7. The Ramanujan $\tau$ function is multiplicative. It is defined by the following identity, $$ \sum_{n \ge 1} \tau(n)\, q^n = q \, \prod_{n \ge 1} (1 - q^n)^{24}. $$
  8. The Ramanujan sum $c_q(n)$, is multiplicative in $q$ for every fixed $n$ and multiplicative in $n$ for every fixed $q$. It is the sum of the $n$-th powers of the primitive $q$-th roots of unity, $$ c_q(n) = \sum_{1 \le k \le q \atop (k,q) = 1} e^{2i\pi \frac{k}{q} n}, $$ Here $(k,q)$ denotes the greatest common divisor $a$ and $q$ and $(a,q) = 1$ means $a$, $q$ coprime.

Remark. This list is far from exhaustive.

The set of multiplicative functions have two interesting structures. It is a group under the Dirichlet convolution. And a monoid under the pointwise multiplication.

Definition 2. The Dirichlet convolution $f \star g$ of two arithmetic functions $f$ and $g$ is defined for all positive integer $n$ by, $$ (f \star g) (n) = \sum_{rs = n} f(r)\, g(s). $$

Exercise. Prove that the Dirichlet convolution is associative and find its unit element.

Theorem 1. An arithmetic function $f$ is invertible (for the convolution product) if $f(1)$ is invertible. The convolutional inverse $f^{-1}$ of an arithmetic functions is given inductively by, \begin{align*} \begin{array}{rcl} f^{-1}(1) &= & \displaystyle\frac{1}{f(1)} \\ \\ f^{-1}(n) &= &\displaystyle - \frac{1}{f(1)} \sum_{uv = n \atop v < n} f(u) \, f^{-1}(v), \end{array} \end{align*} for all $n > 1$.

Proof. As $(f \star g)(1) = f(1)\, g(1)$ it is clear that the condition that $f(1)$ is invertible is a necessary condition for $f$ to be invertible. We now prove that $f \star f^{-1} = e$.

For $n = 1$: \begin{align*} (f \star f^{-1})(1) &= f(1) f^{-1}(1) = 1 \end{align*}

For $n > 1$: \begin{align*} (f \star f^{-1})(n) &= \sum_{uv = n} f(u)\,f^{-1}(v) \\ &= f(1)\, f^{-1}(n) + \sum_{uv = n \atop v < n} f(u)\,f^{-1}(v) \\ &= f(1) \Biggl(- \frac{1}{f(1)} \sum_{uv = n \atop v < n} f(u) \, f^{-1}(v)\Biggr) + \sum_{uv = n \atop v < n} f(u)\,f^{-1}(v) \\ &= 0 \end{align*}   ☐

The set of arithmetic multiplicative function is stable under Dirichlet convolution and convolutional inverse and hence a subgroup of the group of invertible arithmetic functions. This statement is most easily proved by introducing Dirichlet series and their representations as Euler products.

3. Dirichlet Series

Definition 3. A (formal) Dirichlet series is an expression of the form, $$ L_a(s) = \sum_{n \ge 1} \frac{a_n}{n^s} $$ where $(a_n)_{n \ge 1}$ is a sequence of complex numbers.

Examples.

  1. The Dirichlet series $L_I(s)$ of the function $I(n) = 1$ is the celebrated Riemann zeta function, $$ L_I(s) = \sum_{n \ge 1} \frac{1}{n^s} \overset{def.}{=} \zeta(s) $$
  2. The Dirichlet series $L_e(s)$ of the function $e$ given by $e(1) = 1$ and $e(n) = 0$ all $n>1$ is just $1$, $$ L_e(n) = 1. $$
  3. The Dirichlet series of the function $\mathrm{Id}(n) = n$ is, $$ L_\mathrm{Id}(s) = \sum_{n \ge 1} \frac{n}{n^s} = \zeta(s-1) $$
  4. The Dirichlet series of the function $\mathrm{Id}^\alpha(n) = n^\alpha$ is, $$ L_{\mathrm{Id}^\alpha}(s) = \sum_{n \ge 1} \frac{n^\alpha}{n^s} = \zeta(s-\alpha) $$

Theorem 2. Dirichlet series are stable by product. Moreover, the coefficients of the product of two Dirichlet series is the Dirichlet convolution of their coefficients. $$ L_a(s) \cdot L_b(s) = L_{a \star b}(s) $$

Proof. The proof is by direct computation, \begin{align*} L_a(s) \cdot L_b(s) &=\Biggl( \sum_{u \ge 1} \frac{a_u}{u^s} \Biggr) \Biggl( \sum_{v \ge 1} \frac{b_v}{v^s} \Biggr) \\ &= \sum_{u \ge 1 \atop v \ge 1} \frac{a_u\,b_v}{(uv)^s} \\ &= \sum_{n \ge 1} \Biggl(\sum_{uv = n} a_u\,b_v \Biggr) \frac{1}{n^s} \\ &= \sum_{n \ge 1} \frac{(a \star b)(n)}{n^s} = L_{a \star b}(s). \end{align*}   ☐

Corollary. The coefficients of the multiplicative inverse of a Dirichlet series is the convolutional inverse of its coefficients, $$ \frac{1}{L_a(s)} = L_{a^{-1}}(s) $$

Proof. $ L_{a}(s) \cdot L_{a^{-1}}(s) = L_{a \star a^{-1}}(s) = L_e(s) =1 $   ☐

Corollary. We recover easily that Dirichlet convolution is associative, $$ (a \star b) \star c = a \star (b \star c) $$

Proof. \begin{align*} L_{(a \star b) \star c}(s) &= L_{(a \star b)}(s) \cdot L_{c}(s) \\ &= L_{a}(s) \cdot L_{b}(s) \cdot L_{c}(s) \\ &= L_{a}(s) \cdot L_{(b \star c)}(s) \\ &= L_{a \star (b \star c)}(s) \end{align*}   ☐

Theorem 3. Let $f$ be an application $\mathbb{N}^* \rightarrow \mathbb{C}$. The two following properties are equivalent.

  1. The function $f$ is multiplicative.
  2. The associated Dirichlet series has an Euler product representation, $$ L_f(s) = \sum_{n \ge 1} \frac{f(n)}{n^s} = \prod_{\text{$p$ prime}} \sum_{k \ge 0} \frac{f(p^k)}{(p^k)^s} $$ where each factor is a power series in $p^{-s}$ with unit constant term.

Proof. This is a restatement of the fundamental theorem of arithmetic: any positive integer $n$ admit a unique factorization as a product of distinct prime powers. $$ n = p_1^{\alpha_1} \cdots p_r^{\alpha_n} $$   ☐

Please take a moment to think about this last proof.

Corollary. The set of multiplicative arithmetic functions is stable by Dirichlet convolution and convolutional inverse. It is a subgroup of the group of invertible arithmetic functions.

Proof. We prove first stability by convolution. Let $f$ and $g$ be two arithmetic multiplicative functions. As such, their Dirichlet series have Eulerian product representations, \begin{align*} L_f(s) &= \prod_{p} \, F_p(p^{-s}), \\ L_g(s) &= \prod_{p} \, G_p(p^{-s}), \end{align*} where $(F_p)_p$ and $(G_p)_p$ are families of power series with unit constant term. It follows that the Dirichlet series of $f \star g$ is also representable as an Euler product, with each factor $H_p$ satisfying $$H_p(p^{-s}) = F_p(p^{-s})\, G_p(p^{-s})$$ as the following direct computation shows, \begin{align*} L_{f \star g}(s) &= \Biggl( \prod_{p} F_p(p^{-s}) \Biggr) \Biggl( \prod_{p} G_p(p^{-s}) \Biggr) \\ &= \prod_{p} \, F_p(p^{-s}) \, G_p(p^{-s}) \\ &= \prod_{p} \, H_p(p^{-s}) \end{align*} Observe that the product of two power series with unit constant term is again a power series with unit constant term and apply the Euler criteria to conclude the argument.

We now prove by the same method that the convolutional inverse of $f$ is multiplicative, \begin{align*} L_{f^{-1}}(s) &= \Biggl( \prod_{p} F_p(p^{-s}) \Biggr)^{-1} \\ &= \prod_{p} F_p(p^{-s})^{-1} \end{align*} The following observation together with $F_p(z) = 1 + o(z)$ imply $1 - F_p(z) = o(z)$ proves that the reciprocal of a power series with unit constant term is again a power series with unit constant term, $$ \frac{1}{F_p(z)} = \frac{1}{1 - (1 - F_p(z))} = \sum_{k \ge 0} (1-F_p(z))^k $$ End of the demonstration.   ☐

The case of completely multiplicative functions gives the following useful specialization.

Corollary. Let $f$ be an application $\mathbb{N}^* \rightarrow \mathbb{C}$. The two following properties are equivalent.

  1. The function $f$ is completely multiplicative.
  2. The associated Dirichlet series has the following Euler product representation, $$ L_f(s) = \prod_{\text{$p$ prime}} \frac{1}{1-\frac{f(p)}{p^s}} $$

Proof. In the case of a complete multiplicative function, the Euler factors reduce to mere geometric series, $$ L_f(s) = \prod_{p}\,\sum_{k \ge 0} \frac{f(p^k)}{(p^k)^s} = \prod_{p}\,\sum_{k \ge 0} \left(\frac{f(p)}{p^s}\right)^k = \prod_{p} \frac{1}{1-\frac{f(p)}{p^s}}. $$ where of course the products run over the set of all prime number $p$.   ☐

Just as combinatorial identities can often be proved using two different styles of reasoning, either directly of through the use of generating functions, the arithmetic identities can also be proved using two different styles of reasoning, either directly or through the use of Dirichlet series.

Example 1. The Riemann zeta function is given by the following Dirichlet series, $$ \zeta(s) \overset{def.}{=} \sum_{n\ge 1} \frac{1}{n^s}. $$ Notice that $\zeta(s)$ is the Dirichlet series associated to the complete multiplicative function $I(n) = 1$. As such it has a representation as an Euler product, $$ \zeta(s) = \prod_{p} \frac{1}{1 - \frac{1}{p^s}}. $$

Example 2. Another interesting example of Euler product is the Dirichlet series of the Möbius function. As $\mu$ is multiplicative and for all prime $p$, $$ \mu(p^k) = \begin{cases} 1 & \text{if $k = 0$,}\\ -1 & \text{if $k = 1$,}\\ 0 & \text{else,} \end{cases} $$ we have, $$ L_\mu(s) = \prod_{p} \left(1 - \frac{1}{p^s}\right). $$

Application 1. From that last observation, it turns out that, $$ L_\mu(s) = \frac{1}{\zeta(s)} $$ And so, that $I \star \mu = e$. This is the content of the lemma saying, $$ \sum_{d \,|\, n} \mu(d) = \begin{cases} 1 & \text{if $n=1$,} \\ 0 & \text{else.} \end{cases} $$

Application (Möbius Inversion Reprise). The two infinite systems of equations involved in the Möbius inversion formula can be reinterpreted in term of their Dirichlet series,

  1. The first infinite system of equations, $$ b_{n} = \sum_{d \,|\, n} a_{d} , \text{ for all $n \ge 1$,} $$ means that, $$b = I \star a,$$ and, $$ L_b(s) = \zeta(s) \, L_a(s). $$
  2. And the second infinite system of equations, $$ a_{n} = \sum_{uv = n} \mu(u) \, b_{v}, \text{ for all $n \ge 1$.} $$ means that, $$ a = \mu \star b,$$ and, $$ L_a(s) = \zeta(s)^{-1}\, L_b(s). $$
which are obviously equivalent.

Example 3. From the definition of the sum of divisor powers function, $$ \sigma_\alpha(n) \overset{def.}{=} \sum_{d \,|\, n} d^\alpha. $$ it's not at all obvious that it is multiplicative. That expression can nevertheless be interpreted as, $$\sigma_\alpha = I \star \mathrm{Id}^\alpha$$ and this formulation gives us, well... several things,

  1. As both functions $I(n) = 1$ and $\mathrm{Id}^\alpha = n^\alpha$ are multiplicative, so is $\sigma_\alpha$. For the Dirichlet convolution of two multiplicative functions is itself multiplicative.
  2. The expression of the corresponding Dirichlet series in terms of the Riemann zeta function, \begin{align*} L_{\sigma_\alpha}(s) = \zeta(s)\, \zeta(s-\alpha) . \end{align*}
  3. The Euler product, \begin{align*} L_{\sigma_\alpha}(s) &= \prod_p \Biggl(\frac{1}{1-\frac{1}{p^{-s}}}\Biggr) \Biggl( \frac{1}{1-\frac{1}{p^{-s+\alpha}}}\Biggr) \\ &= \prod_p \frac{1}{1-p^{-s}-p^{-s+\alpha}+p^{-2s+\alpha}}. \end{align*}
  4. In the particular case $\alpha = 0$ we get, $$ L_{d}(s) = \zeta(s)^2 $$ and, \begin{align*} L_{d}(s) &= \prod_p \Biggl(\frac{1}{1-\frac{1}{p^{-s}}}\Biggr)^2 \\ &= \prod_p \frac{1}{1-2\,p^{-s}+p^{-2s}}. \end{align*}
  5. In the particular case $\alpha = 1$ we get, $$ L_{\sigma}(s) = \zeta(s)\, \zeta(s-1) $$ and, \begin{align*} L_{\sigma}(s) &= \prod_p \Biggl(\frac{1}{1-\frac{1}{p^{-s}}}\Biggr) \Biggl( \frac{1}{1-\frac{1}{p^{-s+1}}}\Biggr) \\ &= \prod_p \frac{1}{1-p^{-s}-p^{-s+1}+p^{-2s+1}}. \end{align*}

7 Comments

Perplexed  posted 2012-07-04 17:07:49

Hi: I think that this is a very nice contribution to the initial study of arithmetic functions. I saw the an identity on the relationship between the summatory function of \sigma_a(n) and the zeta function at a+1 here: http://mathworld.wolfram.com/DivisorFunction.html How does one prove that?

Samuel VIDAL  posted 2012-07-04 23:57:15

Hi ! Thank you Perplexed. I think you are talking about formula (39), for $a > 1$, $$ \sum_{k = 1}^n \sigma_a(k) = \frac{\zeta(a+1)}{a+1}\, n^{a+1} + O(n^a). $$ I know no proof of it ;-) but if you look at the book of Hardy and Wright p.266 there is a very simple proof of formula (40), $$ \sum_{k = 1}^n \sigma(k) = \frac{1}{12}\,\pi^2\,n^2+O(n \, \log \,n). $$ Maybe I can reproduce it here as soon as I find some time to type it. Maybe we can get inspiration from that proof to prove the former formula.

Samuel VIDAL  posted 2012-07-05 01:21:54

So as to formula (40) here it goes: take the generating series of the function $\sigma$, $$ \sum_{k \ge 1} \sigma(k) \, z^k = \sum_{k \ge 1 \atop \ell \ge 1} \ell \, z^{k\ell} $$ use it to compute the summatory function of $\sigma$, \begin{align*} \sum_{k = 1}^n \sigma(k) &= \sum_{1 \le k \ell \le n} \ell \\ &= \sum_{k = 1}^n \sum_{\ell = 1}^{n/k} \ell \\ &= \sum_{k = 1}^n \frac{1}{2} \left[\frac{n}{k}\right] \left(\left[\frac{n}{k}\right] + 1\right) \\ &= \frac{1}{2}\sum_{k = 1}^n \left(\frac{n}{k} + O(1)\right)^2 \\ &= \frac{n^2}{2}\sum_{k = 1}^n \frac{1}{k^2} + O\left(n \,\sum_{k=1}^n \frac{1}{k}\right) +O(n) \end{align*}

Now we make two remarks,

  1. $ \displaystyle \sum_{k=1}^n \frac{1}{k^2} = \sum_{k=1}^\infty \frac{1}{k^2} +O\left(\frac{1}{n}\right) = \frac{1}{6} \pi^2 +O\left(\frac{1}{n}\right) $
  2. $ \displaystyle \sum_{k=1}^n \frac{1}{k} = O(\log \, n)$
We can conclude, $$ \sum_{k = 1}^n \sigma(k) = \frac{1}{12}\,\pi^2\,n^2+O(n \, \log \,n) $$

Samuel VIDAL  posted 2012-07-05 22:43:24

Ok let's do formula (39). We start with this relation, \begin{align*} \int_{0}^{\frac{n}{k} - 1} x^a \, dx \le \sum_{\ell = 1}^{n/k} \ell^a \le \int_{1}^{\frac{n}{k}+1} x^a \, dx \end{align*} Which means, $$ \frac{1}{a+1}\left(\frac{n}{k} - 1 \right)^{a+1} \le \sum_{\ell = 1}^{n/k} \ell^a \le \frac{1}{a+1}\left[\left(\frac{n}{k}+1\right)^{a+1}-1\right] $$ We use the binomial theorem, $$ \frac{1}{a+1} \frac{n^{a+1}}{k^{a+1}} + O\left(\frac{n^a}{k^a}\right) \le \sum_{\ell = 1}^{n/k} \ell^a \le \frac{1}{a+1} \frac{n^{a+1}}{k^{a+1}} + O\left(\frac{n^a}{k^a}\right) $$ From that we deduce, \begin{align*} \sum_{\ell = 1}^{n/k} \ell^a &= \frac{1}{a+1} \frac{n^{a+1}}{k^{a+1}} + O\left(\frac{n^a}{k^a}\right) \end{align*} We sum it from $1$ to $n$, \begin{align*} \sum_{k=1}^n \sum_{\ell = 1}^{n/k} \ell^a &= \frac{n^{a+1}}{a+1}\sum_{k=1}^n \frac{1}{k^{a+1}} + O\left(n^a \sum_{k=1}^n \frac{1}{k^a}\right) \\ &= \frac{n^{a+1}}{a+1}\sum_{k=1}^n \frac{1}{k^{a+1}} + O\left(n^a\right) \end{align*} We remark that, $$ \sum_{k=1}^n \frac{1}{k^{a+1}} = \sum_{k=1}^\infty \frac{1}{k^{a+1}} + O\left(\frac{1}{n^a}\right) = \zeta(a+1) + O\left(\frac{1}{n^a}\right) $$ Finally, $$ \sum_{k = 1}^n \sigma_a(k) = \frac{\zeta(a+1)}{a+1}\, n^{a+1} + O(n^a). $$ I've learned something ;-) Hope this is useful.

Cyrus  posted 2012-07-06 11:06:38

The proof is elegant and very simple to understand. The use of calculus is flawless which causes the proof to flow beautifully. You've made it very easy for the reader. Excellent work, friend!

No longer perplexed  posted 2012-07-10 18:52:36

Thank you very much Samuel. It is indeed a wonderful argument!

Samuel VIDAL  posted 2012-07-12 22:26:06

Thank you guys. I'm very happy you enjoyed !

Comment:

Name:

Email:

Website: