World Library  
Flag as Inappropriate
Email this Article

Arithmetic function

Article Id: WHEBN0000003170
Reproduction Date:

Title: Arithmetic function  
Author: World Heritage Encyclopedia
Language: English
Subject: Multiplicative function, Möbius inversion formula, Number theory, Euler's totient function, Arithmetic functions
Collection: Arithmetic Functions
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Arithmetic function

In number theory, an arithmetic, arithmetical, or number-theoretic function[1][2] is a real or complex valued function f(n) defined on the set of natural numbers (i.e. positive integers) that "expresses some arithmetical property of n".[3]

An example of an arithmetic function is the non-principal character (mod 4) defined by

\chi(n) = \left(\frac{-4}{n}\right)= \begin{cases} \;\;\,0 & \text{if } n \text{ is even}, \\ \;\;\, 1 & \text{if } n \equiv 1 \mod 4, \\ -1 & \text{if } n \equiv 3 \mod 4, \end{cases}    

where (\tfrac{-4}{n})\ is the Kronecker symbol.

To emphasize that they are being thought of as functions rather than sequences, values of an arithmetic function are usually denoted by a(n) rather than an.

There is a larger class of number-theoretic functions that do not fit the above definition, e.g. the prime-counting functions. This article provides links to functions of both classes.

Contents

  • Notation 1
  • Multiplicative and additive functions 2
  • Ω(n), ω(n), νp(n) – prime power decomposition 3
  • Multiplicative functions 4
    • σk(n), τ(n), d(n) – divisor sums 4.1
    • φ(n) – Euler totient function 4.2
    • Jk(n) – Jordan totient function 4.3
    • μ(n) – Möbius function 4.4
    • τ(n) – Ramanujan tau function 4.5
    • cq(n) – Ramanujan's sum 4.6
  • Completely multiplicative functions 5
    • λ(n) – Liouville function 5.1
    • χ(n) – characters 5.2
  • Additive functions 6
    • ω(n) – distinct prime divisors 6.1
  • Completely additive functions 7
    • Ω(n) – prime divisors 7.1
    • νp(n) – p-adic valuation of an integer n 7.2
  • Neither multiplicative nor additive 8
    • π(x), Π(x), θ(x), ψ(x) – prime count functions 8.1
    • Λ(n) – von Mangoldt function 8.2
    • p(n) – partition function 8.3
    • λ(n) – Carmichael function 8.4
    • h(n) – Class number 8.5
    • rk(n) – Sum of k squares 8.6
  • Summation functions 9
  • Dirichlet convolution 10
  • Relations among the functions 11
    • Dirichlet convolutions 11.1
    • Sums of squares 11.2
    • Divisor sum convolutions 11.3
    • Class number related 11.4
    • Prime-count related 11.5
    • Menon's identity 11.6
    • Miscellaneous 11.7
  • Notes 12
  • References 13
  • Further reading 14
  • External links 15

Notation

\sum_p f(p)\;   and   \prod_p f(p)\;   mean that the sum or product is over all prime numbers:

\sum_p f(p) = f(2) + f(3) + f(5) + \cdots     \prod_p f(p)= f(2)f(3)f(5)\cdots.

Similarly,   \sum_{p^k} f(p^k)\;   and   \prod_{p^k} f(p^k)\;   mean that the sum or product is over all prime powers with strictly positive exponent (so 1 is not included):

\sum_{p^k} f(p^k) = f(2) + f(3) + f(4) +f(5) +f(7)+f(8)+f(9)+\cdots

\sum_{d\mid n} f(d)\;   and   \prod_{d\mid n} f(d)\;   mean that the sum or product is over all positive divisors of n, including 1 and n. E.g., if n = 12,

\prod_{d\mid 12} f(d) = f(1)f(2) f(3) f(4) f(6) f(12).\

The notations can be combined:   \sum_{p\mid n} f(p)\;   and   \prod_{p\mid n} f(p)\;   mean that the sum or product is over all prime divisors of n. E.g., if n = 18,

\sum_{p\mid 18} f(p) = f(2) + f(3),\

and similarly   \sum_{p^k\mid n} f(p^k)\;   and   \prod_{p^k\mid n} f(p^k)\;   mean that the sum or product is over all prime powers dividing n. E.g., if n = 24,

\prod_{p^k\mid 24} f(p^k) = f(2) f(3) f(4) f(8).\

Multiplicative and additive functions

An arithmetic function a is

Two whole numbers m and n are called coprime if their greatest common divisor is 1; i.e., if there is no prime number that divides both of them.

Then an arithmetic function a is

  • additive if a(mn) = a(m) + a(n) for all coprime natural numbers m and n;
  • multiplicative if a(mn) = a(m)a(n) for all coprime natural numbers m and n.

Ω(n), ω(n), νp(n) – prime power decomposition

The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes:   n = p_1^{a_1}\cdots p_k^{a_k}   where p1 < p2 < ... < pk are primes and the aj are positive integers. (1 is given by the empty product.)

It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define νp(n) as the exponent of the highest power of the prime p that divides n. I.e. if p is one of the pi then νp(n) = ai, otherwise it is zero. Then

n=\prod_p p^{\nu_p(n)}.

In terms of the above the functions ω and Ω are defined by

ω(n) = k,
Ω(n) = a1 + a2 + ... + ak.

To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding pi, ai, ω, and Ω.

ω(n)
n +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0+ 0 1 1 1 1 2 1 1 1 2 1
12+ 2 1 2 2 1 1 2 1 2 2 2 1
24+ 2 1 2 1 2 1 3 1 1 2 2 2
36+ 2 1 2 2 2 1 3 1 2 2 2 1
48+ 2 1 2 2 2 1 2 2 2 2 2 1
60+ 3 1 2 2 1 2 3 1 2 2 3 1
72+ 2 1 2 2 2 2 3 1 2 1 2 1
84+ 3 2 2 2 2 1 3 2 2 2 2 2
96+ 2 1 2 2 2 1 3 1 2 3 2 1
108+ 2 1 3 2 2 1 3 2 2 2 2 2
120+ 3 1 2 2 2 1 3 1 1 2 3 1
132+ 3 2 2 2 2 1 3 1 3 2 2 2
Ω(n)
n +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0+ 0 1 1 2 1 2 1 3 2 2 1
12+ 3 1 2 2 4 1 3 1 3 2 2 1
24+ 4 2 2 3 3 1 3 1 5 2 2 2
36+ 4 1 2 2 4 1 3 1 3 3 2 1
48+ 5 2 3 2 3 1 4 2 4 2 2 1
60+ 4 1 2 3 6 2 3 1 3 2 3 1
72+ 5 1 2 3 3 2 3 1 5 4 2 1
84+ 4 2 2 2 4 1 4 2 3 2 2 2
96+ 6 1 3 3 4 1 3 1 4 3 2 1
108+ 5 1 3 2 5 1 3 2 3 3 2 2
120+ 5 2 2 2 3 3 4 1 7 2 3 1
132+ 4 2 2 4 4 1 3 1 4 2 2 2
The chaotic course of Ω(n) through the natural numbers (A001222): Beginning on the height of the red line the two least significant binary digits of Ω(n) of all positive odd n below 1200 are represented by a line up (digit 1) or a line down (digit 0). The additional replacement of the “↗↘” of the semiprimes without prime factors below 5 by only one line down (here blue) even almost brings a balance between the ups and downs. The prime numbers are marked orange: orange lines for the Gaussian primes and for the other primes p additional the number x in orange so that p = x2 + y2 = (x + yi) (xyi) = –i (x + yi) (y + xi) and x < y for natural x and y (A002331).

Multiplicative functions

σk(n), τ(n), d(n) – divisor sums

σk(n) is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.

σ1(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).

Since a positive number to the zero power is one, σ0(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).

\sigma_k(n) = \prod_{i=1}^{\omega(n)} \frac{p_i^{(a_i+1)k}-1}{p_i^k-1} = \prod_{i=1}^{\omega(n)} \left(1 + p_i^k + p_i^{2k} + \cdots + p_i^{a_i k}\right).

Setting k = 0 in the second product gives

\tau(n) = d(n) = (1 + a_{1})(1+a_{2})\cdots(1+a_{\omega(n)}).

φ(n) – Euler totient function

φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.

\varphi(n) = n \prod_{p\mid n} \left(1-\frac{1}{p}\right) =n \left(\frac{p_1 - 1}{p_1}\right)\left(\frac{p_2 - 1}{p_2}\right) \cdots \left(\frac{p_{\omega(n)} - 1}{p_{\omega(n)}}\right) .

Jk(n) – Jordan totient function

Jk(n), the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, φ(n) = J1(n).

J_k(n) = n^k \prod_{p\mid n} \left(1-\frac{1}{p^k}\right) =n^k \left(\frac{p^k_1 - 1}{p^k_1}\right)\left(\frac{p^k_2 - 1}{p^k_2}\right) \cdots \left(\frac{p^k_{\omega(n)} - 1}{p^k_{\omega(n)}}\right) .

μ(n) – Möbius function

μ(n), the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below.

\mu(n)=\begin{cases} (-1)^{\omega(n)}=(-1)^{\Omega(n)} &\text{if }\; \omega(n) = \Omega(n)\\ 0&\text{if }\;\omega(n) \ne \Omega(n).\end{cases}

This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

τ(n) – Ramanujan tau function

τ(n), the Ramanujan tau function, is defined by its generating function identity:

\sum_{n\geq 1}\tau(n)q^n=q\prod_{n\geq 1}(1-q^n)^{24}.

Although it is hard to say exactly what "arithmetical property of n" it "expresses",[4] (τ(n) is (2π)−12 times the nth Fourier coefficient in the q-expansion of the modular discriminant function)[5] it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σk(n) and rk(n) functions (because these are also coefficients in the expansion of modular forms).

cq(n) – Ramanujan's sum

cq(n), Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity:

c_q(n)= \sum_{\stackrel{1\le a\le q}{ \gcd(a,q)=1}} e^{2 \pi i \tfrac{a}{q} n} .

Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

If q and r are coprime, c_q(n)c_r(n)=c_{qr}(n).\;

Many of the functions mentioned in this article have expansions as series involving these sums; see the article Ramanujan's sum for examples.

Completely multiplicative functions

λ(n) – Liouville function

λ(n), the Liouville function, is defined by

\lambda (n) = (-1)^{\Omega(n)}.\;

χ(n) – characters

All Dirichlet characters χ(n) are completely multiplicative. An example is the non-principal character (mod 4) defined in the introduction. Two characters have special notations:

The principal character (mod n) is denoted by χ0(a) (or χ1(a)). It is defined as

\chi_0(a) = \begin{cases} 1 & \text{if } \gcd(a,n) = 1, \\ 0 & \text{if } \gcd(a,n) \ne 1. \end{cases}

The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n.):

\Bigg(\frac{a}{n}\Bigg) = \left(\frac{a}{p_1}\right)^{a_1}\left(\frac{a}{p_2}\right)^{a_2}\cdots \left(\frac{a}{p_{\omega(n)}}\right)^{a_{\omega(n)}}.


In this formula (\tfrac{a}{p}) is the Legendre symbol, defined for all integers a and all odd primes p by

\left(\frac{a}{p}\right) = \begin{cases} \;\;\,0\text{ if } a \equiv 0 \pmod{p} \\+1\text{ if }a \not\equiv 0\pmod{p} \text{ and for some integer }x, \;a\equiv x^2\pmod{p} \\-1\text{ if there is no such } x. \end{cases}

Following the normal convention for the empty product, \left(\frac{a}{1}\right) = 1.

Additive functions

ω(n) – distinct prime divisors

ω(n), defined above as the number of distinct primes dividing n, is additive.

Completely additive functions

Ω(n) – prime divisors

Ω(n), defined above as the number of prime factors of n counted with multiplicities, is completely additive.

νp(n) – p-adic valuation of an integer n

For a fixed prime p, νp(n), defined above as the exponent of the largest power of p dividing n, is completely additive.

Neither multiplicative nor additive

π(x), Π(x), θ(x), ψ(x) – prime count functions

These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the prime number theorem. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

π(x), the prime counting function, is the number of primes not exceeding x. It is the summation function of the characteristic function of the prime numbers.

\pi(x) = \sum_{p\le x}1

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, … It is the summation function of the arithmetic function which takes the value 1/k on integers which are the k-th power of some prime number, and the value 0 on other integers.

\Pi(x) = \sum_{p^k\le x}\frac{1}{k}.

θ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x.

\vartheta(x)=\sum_{p\le x} \log p,
\psi(x) = \sum_{p^k\le x} \log p.

The Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.

Λ(n) – von Mangoldt function

Λ(n), the von Mangoldt function, is 0 unless the argument is a prime power, in which case it is the natural log of the prime:

\Lambda(n) = \begin{cases}\log p &\text{if } n = 2,3,4,5,7,8,9,11,13,16,\ldots=p^k \text{ is a prime power}\\ 0&\text{if } n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;\text{ is not a prime power}. \end{cases}

p(n) – partition function

p(n), the partition function, is the number of ways of representing n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:

p(n) = |\left\{ (a_1, a_2,\dots a_k): 0 < a_1 \le a_2 \le \cdots \le a_k\; \and \;n=a_1+a_2+\cdots +a_k \right\}|.

λ(n) – Carmichael function

λ(n), the Carmichael function, is the smallest positive number such that a^{\lambda(n)}\equiv 1 \pmod{n}   for all a coprime to n. Equivalently, it is the least common multiple of the orders of the elements of the multiplicative group of integers modulo n.

For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n:

\lambda(n) = \begin{cases} \;\;\phi(n) &\text{if }n = 2,3,4,5,7,9,11,13,17,19,23,25,27,\dots\\ \tfrac12\phi(n)&\text{if }n=8,16,32,64,\dots \end{cases}

and for general n it is the least common multiple of λ of each of the prime power factors of n:

\lambda(p_1^{a_1}p_2^{a_2} \dots p_{\omega(n)}^{a_{\omega(n)}}) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_{\omega(n)}^{a_{\omega(n)}}) ].

h(n) – Class number

h(n), the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminant n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.

rk(n) – Sum of k squares

rk(n) is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.

r_k(n) = |\{(a_1, a_2,\dots,a_k):n=a_1^2+a_2^2+\cdots+a_k^2\}|

Summation functions

Given an arithmetic function a(n), its summation function A(x) is defined by

A(x) := \sum_{n \le x} a(n) .

A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m < x < m + 1, and has a jump discontinuity at each integer for which a(m) ≠ 0.

Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:

A_0(m) := \frac12\left(\sum_{n < m} a(n) +\sum_{n \le m} a(n)\right) = A(m) - \frac12 a(m) .

Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to find asymptotic behaviour for the summation function for large x.

A classical example of this phenomenon[6] is given by the divisor summatory function, the summation function of d(n), the number of divisors of n:

\liminf_{n\to\infty}d(n) = 2
\limsup_{n\to\infty}\frac{\log d(n) \log\log n}{\log n} = \log 2
\lim_{n\to\infty}\frac{d(1) + d(2)+ \cdots +d(n)}{\log(1) + \log(2)+ \cdots +\log(n)} = 1.

An average order of an arithmetic function is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average". We say that g is an average order of f if

\sum_{n \le x} f(n) \sim \sum_{n \le x} g(n)

as x tends to infinity. The example above shows that d(n) has the average order log(n).[7]

Dirichlet convolution

Given an arithmetic function a(n), let Fa(s), for complex s, be the function defined by the corresponding Dirichlet series (where it converges):[8]

F_a(s) := \sum_{n=1}^{\infty} \frac{a(n)}{n^s} .

Fa(s) is called a generating function of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ς(s) the Riemann zeta function.

The generating function of the Möbius function is the inverse of the zeta function:

\zeta(s)\,\sum_{n=1}^\infty\frac{\mu(n)}{n^s}=1, \;\;\mathfrak{R} \,s >0.

Consider two arithmetic functions a and b and their respective generating functions Fa(s) and Fb(s). The product Fa(s)Fb(s) can be computed as follows:

F_a(s)F_b(s) = \left( \sum_{m=1}^{\infty}\frac{a(m)}{m^s} \right)\left( \sum_{n=1}^{\infty}\frac{b(n)}{n^s} \right) .

It is a straightforward exercise to show that if c(n) is defined by

c(n) := \sum_{ij = n} a(i)b(j) = \sum_{i\mid n}a(i)b\left(\frac{n}{i}\right) ,

then

F_c(s) =F_a(s) F_b(s).\;

This function c is called the Dirichlet convolution of a and b, and is denoted by a*b.

A particularly important case is convolution with the constant function a(n) = 1 for all n, corresponding to multiplying the generating function by the zeta function:

g(n) = \sum_{d\mid n}f(d).\;

Multiplying by the inverse of the zeta function gives the Möbius inversion formula:

f(n) = \sum_{d\mid n}\mu\left(\frac{n}{d}\right)g(d).

If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.

Relations among the functions

There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions.

Here are a few examples:

Dirichlet convolutions

\sum_{\delta\mid n}\mu(\delta)= \sum_{\delta\mid n}\lambda\left(\frac{n}{\delta}\right)|\mu(\delta)|= \begin{cases} &1\text{ if } n=1\\ &0\text{ if } n\ne1. \end{cases}     where λ is the Liouville function.    [9]
\sum_{\delta\mid n}\varphi(\delta)= n.      [10]
\varphi(n) =\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\delta =n\sum_{\delta\mid n}\frac{\mu(\delta)}{\delta}.       Möbius inversion
\sum_{d \mid n } J_k(d) = n^k. \,      [11]
J_k(n) =\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\delta^k =n^k\sum_{\delta\mid n}\frac{\mu(\delta)}{\delta^k}.       Möbius inversion
\sum_{\delta\mid n}\delta^sJ_r(\delta)J_s\left(\frac{n}{\delta}\right) = J_{r+s}(n)      [12]
\sum_{\delta\mid n}\varphi(\delta)d\left(\frac{n}{\delta}\right)= \sigma(n).      [13][14]
\sum_{\delta\mid n}|\mu(\delta)|= 2^{\omega(n)}.      [15]
|\mu(n)|=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)2^{\omega(\delta)}.       Möbius inversion
\sum_{\delta\mid n}2^{\omega(\delta)}= d(n^2).      
2^{\omega(n)}=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)d(\delta^2).       Möbius inversion
\sum_{\delta\mid n}d(\delta^2)= d^2(n).      
d(n^2)=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)d^2(\delta).       Möbius inversion
\sum_{\delta\mid n}d\left(\frac{n}{\delta}\right)2^{\omega(\delta)}= d^2(n).      
\sum_{\delta\mid n}\lambda(\delta)=\begin{cases} &1\text{ if } n \text{ is a square }\\ &0\text{ if } n \text{ is not square.} \end{cases}     where λ is the Liouville function.
\sum_{\delta\mid n}\Lambda(\delta)= \log n.      [16]
\Lambda(n)=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\log(\delta).       Möbius inversion

Sums of squares

\text{If }k \ge 4,\;\;\; r_k(n) > 0.     (Lagrange's four-square theorem).
r_2(n) = 4\sum_{d\mid n}\chi(d),\;     where χ is the non-principal character (mod 4) defined in the introduction.[17]

There is a formula for r3 in the section on class numbers below.

r_4(n) = 8 \sum_{\stackrel{d\mid n}{ 4\, \nmid \,d}}d = 8 (2+(-1)^n)\sum_{\stackrel{d\mid n}{ 2\, \nmid \,d}}d = \begin{cases} 8\sigma(n)&\text{if } n \text{ is odd }\\ 24\sigma\left(\frac{n}{2^{\nu}}\right)&\text{if } n \text{ is even } \end{cases},     where ν = ν2(n).    [18][19][20]
r_6(n) = 16 \sum_{d\mid n} \chi\left(\frac{n}{d}\right)d^2 - 4\sum_{d\mid n} \chi(d)d^2.    [21]

Define the function σk*(n) as[22]

\sigma_k^*(n) = (-1)^{n}\sum_{d\mid n}(-1)^d d^k= \begin{cases} \sum_{d\mid n} d^k=\sigma_k(n)&\text{if } n \text{ is odd }\\ \sum_{\stackrel{d\mid n}{ 2\, \mid \,d}}d^k -\sum_{\stackrel{d\mid n}{ 2\, \nmid \,d}}d^k&\text{if } n \text{ is even}. \end{cases}

That is, if n is odd, σk*(n) is the sum of the kth powers of the divisors of n, i.e. σk(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

r_8(n) = 16\sigma_3^*(n).\;    [21][23]

Adopt the convention that Ramanujan's τ(x) = 0 if x is not an integer.

r_{24}(n) = \frac{16}{691}\sigma_{11}^*(n) + \frac{128}{691}\left\{ (-1)^{n-1}259\tau(n)-512\tau\left(\frac{n}{2}\right)\right\}    [24]

Divisor sum convolutions

Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:

\left(\sum_{n=0}^\infty a_n x^n\right)\left(\sum_{n=0}^\infty b_n x^n\right) = \sum_{i=0}^\infty \sum_{j=0}^\infty a_i b_j x^{i+j} = \sum_{n=0}^\infty \left(\sum_{i=0}^n a_i b_{n-i}\right) x^n = \sum_{n=0}^\infty c_n x^n .

The sequence c_n = \sum_{i=0}^n a_i b_{n-i}\; is called the convolution or the Cauchy product of the sequences an and bn.
See Eisenstein series for a discussion of the series and functional identities involved in these formulas.[25]

\sigma_3(n) = \frac{1}{5}\left\{6n\sigma_1(n)-\sigma_1(n) + 12\sum_{0    [26]
\sigma_5(n) = \frac{1}{21}\left\{10(3n-1)\sigma_3(n)+\sigma_1(n) + 240\sum_{0    [27]
\begin{align} \sigma_7(n) &=\frac{1}{20}\left\{21(2n-1)\sigma_5(n)-\sigma_1(n) + 504\sum_{0    [27][28]
\begin{align} \sigma_9(n) &= \frac{1}{11}\left\{10(3n-2)\sigma_7(n)+\sigma_1(n) + 480\sum_{0    [26][29]
\tau(n) = \frac{65}{756}\sigma_{11}(n) + \frac{691}{756}\sigma_{5}(n) - \frac{691}{3}\sum_{0     where τ(n) is Ramanujan's function.    [30][31]

Since σk(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences[32] for the functions. See Tau-function for some examples.

Extend the domain of the partition function by setting p(0) = 1.

p(n)=\frac{1}{n}\sum_{1\le k\le n}\sigma(k)p(n-k).    [33]   This recurrence can be used to compute p(n).

Class number related

Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number h of quadratic number fields to the Jacobi symbol.[34]

An integer D is called a fundamental discriminant if it is the discriminant of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is squarefree and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4).[35]

Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol:

\left(\frac{a}{2}\right) = \begin{cases} \;\;\,0&\text{ if } a \text{ is even} \\(-1)^{\frac{a^2-1}{8}}&\text{ if }a \text{ is odd. } \end{cases}

Then if D < −4 is a fundamental discriminant[36][37]

\begin{align} h(D) & = \frac{1}{D} \sum_{r=1}^{|D|}r\left(\frac{D}{r}\right)\\ & = \frac{1}{2-\left(\tfrac{D}{2}\right)} \sum_{r=1}^{|D|/2}\left(\frac{D}{r}\right). \end{align}

There is also a formula relating r3 and h. Again, let D be a fundamental discriminant, D < −4. Then[38]

r_3(|D|) = 12\left(1-\left(\frac{D}{2}\right)\right)h(D).

Prime-count related

Let H_n = 1 + \frac12 + \frac13 + \cdots +\frac{1}{n}   be the nth harmonic number.   Then

\sigma(n) \le H_n + e^{H_n}\log H_n   is true for every natural number n if and only if the Riemann hypothesis is true.    [39]

The Riemann hypothesis is also equivalent to the statement that, for all n > 5040,

\sigma(n) < e^\gamma n \log \log n \,     (where γ is the Euler–Mascheroni constant).     This is Robin's theorem.
\sum_{p}\nu_p(n) = \Omega(n).\;
\psi(x)=\sum_{n\le x}\Lambda(n). \;    [40]
\Pi(x)= \sum_{n\le x}\frac{\Lambda(n)}{\log n}.\;    [41]
e^{\theta(x)}=\prod_{p\le x}p.\;    [42]
e^{\psi(x)}= \operatorname{lcm}[1,2,\dots,\lfloor x\rfloor].\;    [43]

Menon's identity

In 1965 P. Kesava Menon proved[44]

\sum_{\stackrel{1\le k\le n}{ \gcd(k,n)=1}} \gcd(k-1,n) =\varphi(n)d(n).

This has been generalized by a number of mathematicians, e.g.:

B. Sury[45]

\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{ \gcd(k_1,n)=1}} \gcd(k_1-1,k_2,\dots,k_s,n) =\varphi(n)\sigma_{s-1}(n).

N. Rao[46]

\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{ \gcd(k_1,k_2,\dots,k_s,n)=1}} \gcd(k_1-a_1,k_2-a_2,\dots,k_s-a_s,n)^s =J_s(n)d(n),

where a1, a2, ..., as are integers, gcd(a1, a2, ..., as, n) = 1.

L. Tóth[47]

\sum_{\stackrel{1\le k\le m}{ \gcd(k,m)=1}} \gcd(k^2-1,m_1)\gcd(k^2-1,m_2) =\varphi(n)\sum_{\stackrel{d_1\mid m_1} {d_2\mid m_2}} \varphi(\gcd(d_1, d_2))2^{\omega(\operatorname{lcm}(d_1, d_2))},

where m1 and m2 are odd, m = lcm(m1, m2).

In fact, if f is any arithmetical function[48][49]

\sum_{\stackrel{1\le k\le n}{ \gcd(k,n)=1}} f(\gcd(k-1,n)) =\varphi(n)\sum_{d\mid n}\frac{(\mu*f)(d)}{\varphi(d)},

where * stands for Dirichlet convolution.

Miscellaneous

Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the Law of Quadratic Reciprocity:

\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) = (-1)^{(m-1)(n-1)/4}.    

Let λ(n) be Liouville's function. Then we have

|\lambda(n)|\mu(n) =\lambda(n)|\mu(n)| = \mu(n),     and
\lambda(n)\mu(n) = |\mu(n)| =\mu^2(n).    

Let λ(n) be Carmichael's function. Then we have

\lambda(n)\mid \phi(n).     Further,
\lambda(n)= \phi(n) \text{ if and only if }n=\begin{cases}1,2, 4;\\ 3,5,7,9,11, \ldots \text{ i.e. } p^k \text{ where }p\text{ is an odd prime};\\ 6,10,14,18,\ldots \text{ i.e. } 2p^k\text{ where }p\text{ is an odd prime}. \end{cases}      [50]
2^{\omega(n)}\le d(n)\le2^{\Omega(n)}.\;    [51][52]
\frac{6}{\pi^2}<\frac{\phi(n)\sigma(n)}{n^2}<1.\;    [53]
\begin{align} c_q(n) &=\frac{\mu\left(\frac{q}{\gcd(q, n)}\right)}{\phi\left(\frac{q}{\gcd(q, n)}\right)}\phi(q)\\ &=\sum_{\delta\mid \gcd(q,n)}\mu\left(\frac{q}{\delta}\right)\delta. \end{align}    [54]     Note that  \phi(q) = \sum_{\delta\mid q}\mu\left(\frac{q}{\delta}\right)\delta.    [55]
c_q(1) = \mu(q).\;
c_q(q) = \phi(q).\;
\sum_{\delta\mid n}d^{\;3}(\delta) = \left(\sum_{\delta\mid n}d(\delta)\right)^2.\;    [56]   Compare this with 13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2
d(uv) = \sum_{\delta\mid \gcd(u,v)}\mu(\delta)d\left(\frac{u}{\delta}\right)d\left(\frac{v}{\delta}\right).\;    [57]
\sigma_k(u)\sigma_k(v) = \sum_{\delta\mid \gcd(u,v)}\delta^k\sigma_k\left(\frac{uv}{\delta^2}\right).\;    [58]
\tau(u)\tau(v) = \sum_{\delta\mid \gcd(u,v)}\delta^{11}\tau\left(\frac{uv}{\delta^2}\right),\;     where τ(n) is Ramanujan's function.    [59]

Notes

  1. ^ Long (1972, p. 151)
  2. ^ Pettofrezzo & Byrkit (1970, p. 58)
  3. ^ Hardy & Wright, intro. to Ch. XVI
  4. ^ Hardy, Ramanujan, § 10.2
  5. ^ Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6
  6. ^ Hardy & Wright, §§ 18.1–18.2
  7. ^
  8. ^ Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.
  9. ^ Hardy & Wright, Thm. 263
  10. ^ Hardy & Wright, Thm. 63
  11. ^ see references at Jordan's totient function
  12. ^ Holden et al in external links The formula is Gegenbauer's
  13. ^ Hardy & Wright, Thm. 288–290
  14. ^ Dineva in external links, prop. 4
  15. ^ Hardy & Wright, Thm. 264
  16. ^ Hardy & Wright, Thm. 296
  17. ^ Hardy & Wright, Thm. 278
  18. ^ Hardy & Wright, Thm. 386
  19. ^ Hardy, Ramanujan, eqs 9.1.2, 9.1.3
  20. ^ Koblitz, Ex. III.5.2
  21. ^ a b Hardy & Wright, § 20.13
  22. ^ Hardy, Ramanujan, § 9.7
  23. ^ Hardy, Ramanujan, § 9.13
  24. ^ Hardy, Ramanujan, § 9.17
  25. ^ The paper by Huard, Ou, Spearman, and Williams in the external links also has proofs.
  26. ^ a b Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146
  27. ^ a b Koblitz, ex. III.2.8
  28. ^ Koblitz, ex. III.2.3
  29. ^ Koblitz, ex. III.2.2
  30. ^ Koblitz, ex. III.2.4
  31. ^ Apostol, Modular Functions ..., Ex. 6.10
  32. ^ Apostol, Modular Functions..., Ch. 6 Ex. 10
  33. ^ G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279
  34. ^ Landau, p. 168, credits Gauss as well as Dirichlet
  35. ^ Cohen, Def. 5.1.2
  36. ^ Cohen, Corr. 5.3.13
  37. ^ see Edwards, § 9.5 exercises for more complicated formulas.
  38. ^ Cohen, Prop 5.10.3
  39. ^ See Divisor function.
  40. ^ Hardy & Wright, eq. 22.1.2
  41. ^ See prime counting functions.
  42. ^ Hardy & Wright, eq. 22.1.1
  43. ^ Hardy & Wright, eq. 22.1.3
  44. ^ László Tóth, Menon's Identity and Arithmetical Sums ..., #External links, eq. 1
  45. ^ Tóth, eq. 5
  46. ^ Tóth, eq. 3
  47. ^ Tóth, eq. 35
  48. ^ Tóth, eq. 2
  49. ^ Tóth states that Menon proved this for multiplicative f in 1965 and V. Sita Ramaiah for general f.
  50. ^ See Multiplicative group of integers modulo n and Primitive root modulo n.
  51. ^ Hardy Ramanujan, eq. 3.10.3
  52. ^ Hardy & Wright, § 22.13
  53. ^ Hardy & Wright, Thm. 329
  54. ^ Hardy & Wright, Thms. 271, 272
  55. ^ Hardy & Wright, eq. 16.3.1
  56. ^ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p.133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.
  57. ^ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p.134
  58. ^ Apostol, Modular Functions ..., ch. 6 eq. 4
  59. ^ Apostol, Modular Functions ..., ch. 6 eq. 3

References

Further reading

External links

  • Matthew Holden, Michael Orrison, Michael Varble Yet another Generalization of Euler's Totient Function
  • Huard, Ou, Spearman, and Williams. Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions Elementary (i.e. not relying on the theory of modular forms) proofs of divisor sum convolutions, formulas for the number of ways of representing a number as a sum of triangular numbers, and related results.
  • Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions
  • László Tóth, Menon's Identity and arithmetical sums representing functions of several variables
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.