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
, 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
with one:
:
These identities include applications to sums of an arithmetic function over just the proper prime divisors of
.
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
:
Well-known inversion relations that allow the function
to be expressed in terms of
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
defined as a divisor sum of another arithmetic function
. 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
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
denotes the summatory function of
. 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 ...
.
#
#
#
#
#
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
:
where the multiplicative function ''f'' can be written as a convolution of the form
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
for all
. 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
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
. 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
:
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 ...
defined by the following equation are also ''k''-periodic:
:
We are interested in the following ''k''-periodic divisor sums:
:
It is a fact that the Fourier coefficients of these divisor sum variants are given by the formula
:
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
using the following result where
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):
:
Thus by combining the results above we obtain that
:
Sums over prime divisors
Let the function
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.,
''if and only if''
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
:
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
:
where
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
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
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 ...
:
#
#
#
# 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
with a Dirichlet convolution yields
.
#
# If
and ''n'' has more than ''m''
distinct prime factors, then
The Dirichlet inverse of an arithmetic function
We adopt the notation that
denotes the multiplicative identity of Dirichlet convolution so that
for any arithmetic function ''f'' and
. The Dirichlet inverse of a function ''f'' satisfies
for all
. 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 ...
of a function ''f'' by induction given in the form of
:
For a fixed function ''f'', let the function
Next, define the following two multiple, or nested, convolution variants for any fixed arithmetic function ''f'':
:
The function
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''.
:
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.]
:
A table of the values of
for
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''!!
!! ''n''!!
!! ''n''!!
, -
, 2 , ,
, , 7 , ,
, , 12 , ,
, -
, 3 , ,
, , 8 , ,
, , 13 , ,
, -
, 4 , ,
, , 9 , ,
, , 14 , ,
, -
, 5 , ,
, , 10 , ,
, , 15 , ,
, -
, 6 , ,
, , 11 , ,
, , 16 , ,
Let
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
given by
:
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