The purpose of this page is to catalog new, interesting, and useful identities related to number-theoretic divisor sums, i.e., sums of an arithmetic function over the divisors of a natural number ${\displaystyle n}$, or equivalently the Dirichlet convolution of an arithmetic function ${\displaystyle f(n)}$ with one:

${\displaystyle g(n):=\sum _{d|n}f(n).}$

These identities include applications to sums of an arithmetic function over just the proper prime divisors of ${\displaystyle n}$. We also define periodic variants of these divisor sums with respect to the greatest common divisor function in the form of

${\displaystyle g_{m}(n):=\sum _{d|(m,n)}f(n),\ 1\leq m\leq n}$

Well-known inversion relations that allow the function ${\displaystyle f(n)}$ to be expressed in terms of ${\displaystyle g(n)}$ are provided by the Mobius inversion formula. Naturally, some of the most interesting examples of such identities result when considering the average order summatory functions over an arithmetic function ${\displaystyle f(n)}$ defined as a divisor sum of another arithmetic function ${\displaystyle g(n)}$. For particular examples of divisor sums involving special arithmetic functions and special Dirichlet convolutions of arithmetic functions can be found on the following pages: here, here, here, here, and here.

The following identities are the primary motivation for creating this topics page. These identities do not appear to be well-known, or at least well-documented, and are extremely useful tools to have at hand in some applications. In what follows, we consider that ${\displaystyle f,g,h,u,v:\mathbb {N} \rightarrow \mathbb {C} }$ are any prescribed arithmetic functions and that ${\displaystyle G(x):=\sum _{n\leq x}g(n)}$ denotes the summatory function of ${\displaystyle g(n)}$. Note that a more common special case of the first summation below is referenced here.

1. ${\displaystyle \sum _{n=1}^{x}\sum _{d|n}h(d)u\left({\frac {n}{d}}\right)v(n)=\sum _{d=1}^{x}h(d)\left(\sum _{n=1}^{\left\lfloor {\frac {x}{d}}\right\rfloor }u(k)v(dk)\right)}$
2. ${\displaystyle {\begin{aligned}\sum _{n=1}^{x}\sum _{d|n}f(n)g\left({\frac {n}{d}}\right)&=\sum _{d=1}^{x}f(d)G\left(\left\lfloor {\frac {x}{d}}\right\rfloor \right)=\sum _{i=1}^{x}\left(\sum _{\left\lceil {\frac {x+1}{i+1}}\right\rceil \leq n\leq \left\lfloor {\frac {x-1}{i}}\right\rfloor }f(n)\right)G(i)+\sum _{d|x}G(d)f\left({\frac {x}{d}}\right)\end{aligned}}}$
3. ${\displaystyle \sum _{d=1}^{x}f(d)\left(\sum _{r|(d,x)}g(r)h\left({\frac {d}{r}}\right)\right)=\sum _{r|x}g(r)\left(\sum _{1\leq d\leq x/r}h(d)f(\operatorname {gcd} (x,r)d)\right)}$
4. ${\displaystyle \sum _{m=1}^{x}\left(\sum _{d|(m,x)}f(d)g\left({\frac {x}{d}}\right)\right)=\sum _{d|x}f(d)g\left({\frac {x}{d}}\right)\cdot {\frac {x}{d}}}$
5. ${\displaystyle \sum _{m=1}^{x}\left(\sum _{d|(m,x)}f(d)g\left({\frac {x}{d}}\right)\right)t^{m}=(t^{x}-1)\cdot \sum _{d|x}{\frac {t^{d}f(d)}{t^{d}-1}}g\left({\frac {x}{d}}\right)}$

In general, these identities are collected from the so-called "rarities and b-sides" of both well established and semi-obscure analytic number theory notes and techniques and the papers and work of the contributors. The identities themselves are not difficult to prove and are and exercise in standard manipulations of series inversion and divisor sums. Therefore we omit their proofs here.

The convolution method is a general technique for estimating average order sums of the form

${\displaystyle \sum _{n\leq x}f(n)\qquad {\text{ or }}\qquad \sum _{\stackrel {q\leq x}{q{\text{ squarefree}}}}f(q),}$

where the multiplicative function f can be written as a convolution of the form ${\displaystyle f(n)=(u\ast v)(n)}$ for suitable, application-defined arithmetic functions u and v. A short survey of this method can be found here.

An arithmetic function is periodic (mod k), or k-periodic, if ${\displaystyle f(n+k)=f(n)}$ for all ${\displaystyle n\in \mathbb {N} }$. Particular examples of k-periodic number theoretic functions are the Dirichlet characters ${\displaystyle f(n)=\chi (n)}$ modulo k and the greatest common divisor function ${\displaystyle f(n)=(n,k)}$. It is known that every k-periodic arithmetic function has a representation as a finite discrete Fourier series of the form

${\displaystyle f(n)=\sum _{m=1}^{k}a_{k}(m)e\left({\frac {mn}{k}}\right),}$

where the Fourier coefficients ${\displaystyle a_{k}(m)}$ defined by the following equation are also k-periodic:

${\displaystyle a_{k}(m)={\frac {1}{k}}\sum _{n=1}^{k}f(n)e\left(-{\frac {mn}{k}}\right).}$

We are interested in the following k-periodic divisor sums:

${\displaystyle s_{k}(n):=\sum _{d|(n,k)}f(d)g\left({\frac {k}{d}}\right)=\sum _{m=1}^{k}a_{k}(m)e\left({\frac {mn}{k}}\right).}$

It is a fact that the Fourier coefficients of these divisor sum variants are given by the formula ^[1]

${\displaystyle a_{k}(m)=\sum _{d|(m,k)}g(d)f\left({\frac {k}{d}}\right){\frac {d}{k}}.}$

We can also express the Fourier coefficients in the equation immediately above in terms of the Fourier transform of any function h at the input of ${\displaystyle \operatorname {gcd} (n,k)}$ using the following result where ${\displaystyle c_{q}(n)}$ is a Ramanujan sum (cf. Fourier transform of the totient function) ^[2]:

${\displaystyle F_{h}(m,n)=\sum _{k=1}^{n}h((k,n))e\left(-{\frac {km}{n}}\right)=(f\ast c_{\cdot }(m))(n).}$

Thus by combining the results above we obtain that

${\displaystyle a_{k}(m)=\sum _{d|(m,k)}g(d)f\left({\frac {k}{d}}\right){\frac {d}{k}}=\sum _{d|k}\sum _{r|d}f(r)g(d)c_{\frac {d}{r}}(m).}$

Let the function ${\displaystyle a(n)}$ denote the characteristic function of the primes, i.e., ${\displaystyle a(n)=1}$ if and only if ${\displaystyle n}$ is prime and is zero-valued otherwise. Then as a special case of the first identity in equation (1) in section interchange of summation identities above, we can express the average order sums

${\displaystyle \sum _{n=1}^{x}\sum _{\stackrel {p|n}{p{\text{ prime}}}}f(p)=\sum _{p=1}^{x}a(p)f(p)\left\lfloor {\frac {x}{p}}\right\rfloor =\sum _{\stackrel {p=1}{p{\text{ prime}}}}^{x}f(p)\left\lfloor {\frac {x}{p}}\right\rfloor .}$

We also have an integral formula based on Abel summation for sums of the form ^[3]

${\displaystyle \sum _{\stackrel {p=1}{p{\text{ prime}}}}^{x}f(p)=\pi (x)f(x)-\int _{2}^{x}\pi (t)f^{\prime }(t)dt\approx {\frac {xf(x)}{\log x}}-\int _{2}^{x}{\frac {t}{\log t}}f^{\prime }(t)dt,}$

where ${\displaystyle \pi (x)\sim {\frac {x}{\log x}}}$ denotes the prime counting function. Here we typically make the assumption that the function f is continuous and differentiable.

We have the following divisor sum formulas for f any arithmetic function and g completely multiplicative where ${\displaystyle \varphi (n)}$ is Euler's totient function and ${\displaystyle \mu (n)}$ is the Mobius function ^{[4] [5]}:

1. ${\displaystyle \sum _{d|n}f(d)\varphi \left({\frac {n}{d}}\right)=\sum _{k=1}^{n}f(\operatorname {gcd} (n,k))}$
2. ${\displaystyle \sum _{d|n}\mu (d)f(d)=\prod _{\stackrel {p|n}{p{\text{ prime}}}}(1-f(p))}$
3. ${\displaystyle f(m)f(n)=\sum _{d|(m,n)}g(d)f\left({\frac {mn}{d^{2}}}\right).}$

This section needs expansion with: Give recursive formula for the Dirichlet inverse of any arithmetic function Give the formula from the recent paper involving the function ${\displaystyle D}$ Note the property that: ${\displaystyle (f\ast g)^{-1}=f^{-1}\ast g^{-1}}$. You can help by adding to it. (April 2018)

This section needs expansion with: See p. 14 of Apostol's book. You can help by adding to it. (April 2018)

• Arithmetic function
• Dirichlet convolution
• Average order of an arithmetic function
• Dirichlet series
• Summation
• List of mathematical series

• Apostol, T. (1976). Introduction to Analytic Number Theory. New Yorl: Springer. ISBN  0-387-90163-9.
• Digital Library of Mathematical Functions (DLMF). NIST. 2018. Retrieved 24 April 2018.
• Tao, Terrence. "Dirichlet concolution: What's new?".