divisor sum identities
   HOME

TheInfoList



OR:

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 In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
over the divisors of a natural number n, or equivalently the
Dirichlet convolution In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet. Definition If f , g : \mathbb\to\mathbb are two arithmetic fun ...
of an arithmetic function f(n) with one: :g(n) := \sum_ f(d). These identities include applications to sums of an arithmetic function over just the proper prime divisors of n. We also define periodic variants of these divisor sums with respect to the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
function in the form of :g_m(n) := \sum_ f(d),\ 1 \leq m \leq n Well-known inversion relations that allow the function f(n) to be expressed in terms of g(n) are provided by the
Möbius inversion formula In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius. A large genera ...
. Naturally, some of the most interesting examples of such identities result when considering the average order summatory functions over an arithmetic function f(n) defined as a divisor sum of another arithmetic function g(n). Particular examples of divisor sums involving special
arithmetic functions In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their de ...
and special
Dirichlet convolution In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet. Definition If f , g : \mathbb\to\mathbb are two arithmetic fun ...
s of arithmetic functions can be found on the following pages:
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a TV ...
,
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a TV ...
,
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a TV ...
,
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a TV ...
, and
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a TV ...
.


Average order sum identities


Interchange of summation identities

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 f,g,h,u,v: \mathbb \rightarrow \mathbb are any prescribed
arithmetic functions In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their de ...
and that G(x) := \sum_ g(n) denotes the summatory function of g(n). A more common special case of the first summation below is referenced
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a TV ...
. # \sum_^x v(n) \sum_ h(d) u\left(\frac\right) = \sum_^x h(n) \sum_^ u(k) v(nk) # \begin \sum_^x \sum_ f(d) g\left(\frac\right) & = \sum_^x f(n) G\left(\left\lfloor \frac \right\rfloor\right) = \sum_^x \left(\sum_ f(n)\right) G(i) + \sum_ G(d) f\left(\frac\right) \end # \sum_^x f(d) \left(\sum_ g(r) h\left(\frac\right)\right) = \sum_ g(r) \left(\sum_ h(d) f(rd)\right) # \sum_^x \left(\sum_ f(d) g\left(\frac\right)\right) = \sum_ f(d) g\left(\frac\right) \cdot \frac # \sum_^x \left(\sum_ f(d) g\left(\frac\right)\right) t^m = (t^x-1) \cdot \sum_ \frac g\left(\frac\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 In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Diric ...
notes and techniques and the papers and work of the contributors. The identities themselves are not difficult to prove and are an exercise in standard manipulations of series inversion and divisor sums. Therefore, we omit their proofs here.


The convolution method

The convolution method is a general technique for estimating average order sums of the form :\sum_ f(n) \qquad\text \qquad \sum_ f(q), where the multiplicative function ''f'' can be written as a convolution of the form f(n) = (u \ast v)(n) for suitable, application-defined
arithmetic function In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
s ''u'' and ''v''. A short survey of this method can be foun
here


Periodic divisor sums

An
arithmetic function In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
is ''periodic (mod k)'', or ''k''-periodic, if f(n+k) = f(n) for all n \in \mathbb. Particular examples of ''k''-periodic number theoretic functions are the
Dirichlet character In analytic number theory and related branches of mathematics, a complex-valued arithmetic function \chi:\mathbb\rightarrow\mathbb is a Dirichlet character of modulus m (where m is a positive integer) if for all integers a and b: :1)   \chi ...
s f(n) = \chi(n) modulo ''k'' and the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
function f(n) = (n, k). It is known that every ''k''-periodic arithmetic function has a representation as a ''finite'' discrete
Fourier series A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or ''p ...
of the form :f(n) = \sum_^k a_k(m) e\left(\frac\right), where the
Fourier coefficients A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or ''p ...
a_k(m) defined by the following equation are also ''k''-periodic: :a_k(m) = \frac \sum_^k f(n) e\left(-\frac\right). We are interested in the following ''k''-periodic divisor sums: :s_k(n) := \sum_ f(d) g\left(\frac\right) = \sum_^k a_k(m) e\left(\frac\right). It is a fact that the Fourier coefficients of these divisor sum variants are given by the formula :a_k(m) = \sum_ g(d) f\left(\frac\right) \frac.


Fourier transforms of the GCD

We can also express the Fourier coefficients in the equation immediately above in terms of the
Fourier transform A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed, ...
of any function ''h'' at the input of \operatorname(n, k) using the following result where c_q(n) is a
Ramanujan sum In number theory, Ramanujan's sum, usually denoted ''cq''(''n''), is a function of two positive integer variables ''q'' and ''n'' defined by the formula : c_q(n) = \sum_ e^, where (''a'', ''q'') = 1 means that ''a'' only takes on values coprime ...
(cf. Fourier transform of the totient function): :F_h(m, n) = \sum_^ h((k,n)) e\left(-\frac\right) = (h \ast c_(m))(n). Thus by combining the results above we obtain that :a_k(m) = \sum_ g(d) f\left(\frac\right) \frac = \sum_ \sum_ f(r) g(d) c_(m).


Sums over prime divisors

Let the function a(n) denote the
characteristic function In mathematics, the term "characteristic function" can refer to any of several distinct concepts: * The indicator function of a subset, that is the function ::\mathbf_A\colon X \to \, :which for a given subset ''A'' of ''X'', has value 1 at points ...
of the
primes A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, i.e., a(n) = 1 ''if and only if'' 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 :\sum_^x \sum_ f(p) = \sum_^x a(p) f(p) \left\lfloor \frac \right\rfloor = \sum_^x f(p) \left\lfloor \frac \right\rfloor. We also have an integral formula based on
Abel summation In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a finite limit. If a series converges, the individual terms of the series mus ...
for sums of the form :\sum_^x f(p) = \pi(x) f(x) - \int_2^x \pi(t) f^(t) dt \approx \frac - \int_2^x \frac f^(t) dt, where \pi(x) \sim \frac denotes the
prime-counting function In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number ''x''. It is denoted by (''x'') (unrelated to the number ). History Of great interest in number theory is t ...
. Here we typically make the assumption that the function ''f'' is
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous ...
and
differentiable In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in its ...
.


Some lesser appreciated divisor sum identities

We have the following divisor sum formulas for ''f'' any arithmetic function and ''g''
completely multiplicative In number theory, functions of positive integers which respect products are important and are called completely multiplicative functions or totally multiplicative functions. A weaker condition is also important, respecting only products of coprime ...
where \varphi(n) is
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
and \mu(n) is the
Möbius function The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most oft ...
: # \sum_ f(d) \varphi\left(\frac\right) = \sum_^n f(\operatorname(n, k)) # \sum_ \mu(d) f(d) = \prod_ (1-f(p)) # f(m)f(n) = \sum_ g(d) f\left(\frac\right). # If ''f'' is
completely multiplicative In number theory, functions of positive integers which respect products are important and are called completely multiplicative functions or totally multiplicative functions. A weaker condition is also important, respecting only products of coprime ...
then the pointwise multiplication \cdot with a Dirichlet convolution yields f \cdot (g \ast h) = (f \cdot g) \ast (f \cdot h). # \sum_ \mu(d) = \Biggl\{\begin{array}{ll} 0, & \text{ if } m^k\mid n \text{ for some } m>1; \\ 1, & \text{otherwise.}\end{array} # If m \geq 1 and ''n'' has more than ''m'' distinct prime factors, then \sum_{d\mid n} \mu(d) \log^m(d) = 0.


The Dirichlet inverse of an arithmetic function

We adopt the notation that \varepsilon(n) = \delta_{n,1} denotes the multiplicative identity of Dirichlet convolution so that (\varepsilon \ast f)(n) = (f \ast \varepsilon)(n) = f(n) for any arithmetic function ''f'' and n \geq 1. The Dirichlet inverse of a function ''f'' satisfies (f \ast f^{-1})(n) = (f^{-1} \ast f)(n) = \varepsilon(n) for all n \geq 1. There is a well-known recursive convolution formula for computing the
Dirichlet inverse In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet. Definition If f , g : \mathbb\to\mathbb are two arithmetic f ...
f^{-1}(n) of a function ''f'' by induction given in the form of :f^{-1}(n) = \Biggl\{\begin{array}{ll} \frac{1}{f(1)}, & \text{ if } n = 1; \\ -\frac{1}{f(1)} \sum_{\stackrel{d\mid n}{d>1 f(d) f^{-1}\left(\frac{n}{d}\right), & \text{ if } n>1. \end{array} For a fixed function ''f'', let the function f_{\pm}(n) := (-1)^{\delta_{n,1 f(n) = \Biggl\{\begin{matrix} -f(1), & \text{ if } n=1; \\ f(n), & \text{ if } n>1 \end{matrix} Next, define the following two multiple, or nested, convolution variants for any fixed arithmetic function ''f'': : \begin{align} \widetilde{\operatorname{ds_{j,f}(n) & := \underbrace{\left(f_{\pm} \ast f \ast \cdots \ast f\right)}_{j\text{ times(n) \\ \operatorname{ds}_{j,f}(n) & := \Biggl\{\begin{array}{ll} f_{\pm}(n), & \text{ if } j=1; \\ \sum\limits_{\stackrel{d\mid n}{d>1 f(d) \operatorname{ds}_{j-1,f}(n/d), & \text{ if } j > 1. \end{array} \end{align} The function D_f(n) by the equivalent pair of summation formulas in the next equation is closely related to the
Dirichlet inverse In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet. Definition If f , g : \mathbb\to\mathbb are two arithmetic f ...
for an arbitrary function ''f''. :D_f(n) := \sum_{j=1}^n \operatorname{ds}_{2j,f}(n) = \sum_{m=1}^{\left\lfloor \frac{n}{2} \right\rfloor} \sum_{i=0}^{2m-1} \binom{2m-1}{i} (-1)^{i+1} \widetilde{\operatorname{ds_{i+1,f}(n) In particular, we can prove that This identity is proved in an unpublished manuscript by M. D. Schmidt which will appear on ArXiv in 2018. :f^{-1}(n) = \left(D + \frac{\varepsilon}{f(1)}\right)(n). A table of the values of D_f(n) for 2 \leq n \leq 16 appears below. This table makes precise the intended meaning and interpretation of this function as the signed sum of all possible multiple ''k''-convolutions of the function ''f'' with itself. {, class="wikitable" , - ! ''n''!! D_f(n) !! ''n''!! D_f(n) !! ''n''!! D_f(n) , - , 2 , , -\frac{f(2)}{f(1)^2} , , 7 , , -\frac{f(7)}{f(1)^2} , , 12 , , \frac{2 f(3) f(4)+2 f(2) f(6)-f(1) f(12)}{f(1)^3}-\frac{3 f(2)^2 f(3)}{f(1)^4} , - , 3 , , -\frac{f(3)}{f(1)^2} , , 8 , , \frac{2 f(2) f(4)-f(1) f(8)}{f(1)^3}-\frac{f(2)^3}{f(1)^4} , , 13 , , -\frac{f(13)}{f(1)^2} , - , 4 , , \frac{f(2)^2-f(1) f(4)}{f(1)^3} , , 9 , , \frac{f(3)^2-f(1) f(9)}{f(1)^3} , , 14 , , \frac{2f(2) f(7)-f(1) f(14)}{f(1)^3} , - , 5 , , -\frac{f(5)}{f(1)^2} , , 10 , , \frac{2f(2) f(5)-f(1) f(10)}{f(1)^3} , , 15 , , \frac{2f(3) f(5)-f(1) f(15)}{f(1)^3} , - , 6 , , \frac{2 f(2) f(3)-f(1) f(6)}{f(1)^3} , , 11 , , -\frac{f(11)}{f(1)^2} , , 16 , , \frac{f(2 )^4}{f(1)^5}-\frac{3 f(4) f(2)^2}{f(1)^4}+\frac{f(4)^2+2 f(2) f(8)}{f(1)^3}-\frac{f(16)}{f(1)^2} Let p_k(n) := p(n-k) where ''p'' is the
Partition function (number theory) In number theory, the partition function represents the number of possible partitions of a non-negative integer . For instance, because the integer 4 has the five partitions , , , , and . No closed-form expression for the partition function is ...
. Then there is another expression for the Dirichlet inverse given in terms of the functions above and the coefficients of the
q-Pochhammer symbol In mathematical area of combinatorics, the ''q''-Pochhammer symbol, also called the ''q''-shifted factorial, is the product (a;q)_n = \prod_^ (1-aq^k)=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^), with (a;q)_0 = 1. It is a ''q''-analog of the Pochhammer symb ...
for n > 1 given by :f^{-1}(n) = \sum_{k=1}^{n} \left p_k \ast \mu)(n) + (p_k \ast D_f \ast \mu)(n)\right\times ^{k-1}\frac{(q; q)_{\infty{1-q}.


Variants of sums over arithmetic functions


See also

*
Summation In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, mat ...
*
Bell series In mathematics, the Bell series is a formal power series used to study properties of arithmetical functions. Bell series were introduced and developed by Eric Temple Bell. Given an arithmetic function f and a prime p, define the formal power seri ...
*
List of mathematical series This list of mathematical series contains formulae for finite and infinite sums. It can be used in conjunction with other tools for evaluating sums. *Here, 0^0 is taken to have the value 1 *\ denotes the fractional part of x *B_n(x) is a Bernoul ...


Notes


References

* * *{{cite web, last1=Tao, first1=Terrence, title=Dirichlet convolution: What's new?, url=https://terrytao.wordpress.com/tag/dirichlet-convolution/ Number theory Integer sequences Summability methods Arithmetic