Arithmetic function Information & Arithmetic function Links at HealthHaven.com

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

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

$\chi(n) =\left(\frac{-4}{n}\right)= \left\{\begin{array}{cl} 0 & \mbox{if } n \mbox{ is even}, \\ 1 & \mbox{if } n \equiv 1 \mod 4, \\ -1 & \mbox{if } n \equiv 3 \mod 4. \end{array}\right.$ where $(\tfrac{-4}{n})\$ is the Kronecker symbol.

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

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.

1 Notation
2 Multiplicative and additive functions
3 Ω(n), ω(n), ν_p(n) - prime power decomposition
4 Multiplicative functions
5 Completely multiplicative functions
- 5.1 λ(n) - Liouville function
- 5.2 χ(n) - characters
6 Additive functions
- 6.1 ω(n) - distinct prime divisors
7 Completely additive functions
- 7.1 Ω(n) - prime divisors
- 7.2 ν_p(n) - prime power dividing n
8 Neither multiplicative nor additive
9 Summation functions
10 Dirichlet convolution
11 Relations among the functions
12 Notes
13 References
14 External links

[edit] 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)\ldots.$

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

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

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

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

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

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

and similarly $\sum_{p^k|n} f(p^k)\;$ and $\prod_{p^k|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|24} f(p^k) = f(2) f(3) f(4) f(8).\$

[edit] Multiplicative and additive functions

An arithmetic function a is

completely additive if a(mn) = a(m) + a(n) for all natural numbers m and n;

completely multiplicative if a(mn) = a(m)a(n) for all natural numbers m and n;

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.

[edit] Ω(n), ω(n), ν_p(n) - prime power decomposition

The fundamental theorem of arithmetic states that any positive integer n can be factorised uniquely as a product of powers of primes: $n = p_1^{a_1}\ldots p_k^{a_k}$ where p₁ < p₂ < ... < p_k are primes and the a_j 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 p_i then ν_p(n) = a_i, 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) = a₁ + a₂ + ... + a_k.

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

[edit] Multiplicative functions

[edit] σ_k(n), τ(n), d(n) - divisor sums

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

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

Since a positive number to the zero power is one, σ₀(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)} (1 + p_{i}^k + p_{i}^{2k} + \cdots + p_{i}^{a_i k}).$

Setting k = 0 in the second product gives

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

[edit] φ(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|n} \left(1-\frac{1}{p}\right) =n \left(\frac{p_1 - 1}{p_1}\right)\left(\frac{p_2 - 1}{p_2}\right) \ldots \left(\frac{p_{\omega(n)} - 1}{p_{\omega(n)}}\right) .$

[edit] μ(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)} &\mbox{if }\; \omega(n) = \Omega(n)\\ 0&\mbox{if }\;\omega(n) \ne \Omega(n).\end{cases}$

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

[edit] τ(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",^[2] (τ(n) is (2π)⁻¹² times the n^th Fourier coefficient in the q-expansion of the modular discriminant function)^[3] it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σ_k(n) and r_k(n) functions (because these are also coefficients in the expansion of modular forms).

[edit] c_q(n) - Ramanujan's sum

c_q(n), Ramanujan's sum, is the sum of the n^th powers of the primitive q^th 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.

[edit] Completely multiplicative functions

[edit] λ(n) - Liouville function

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

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

[edit] χ(n) - characters

All Dirichlet characters χ(n) are completely multiplicative; e.g. the non-principal character (mod 4) defined in the introduction, or the principal character (mod n) defined by

$\chi_0(k) = \begin{cases} 1 & \mbox{if } \gcd(k,n) = 1, \\ 0 & \mbox{if } \gcd(k,n) \ne 1. \end{cases}$

[edit] Additive functions

[edit] ω(n) - distinct prime divisors

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

[edit] Completely additive functions

[edit] Ω(n) - prime divisors

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

[edit] ν_p(n) - prime power dividing n

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

[edit] Neither multiplicative nor additive

[edit] π(x), Π(x), θ(x), ψ(x) - prime count functions

Unlike the other functions listed in this article, these are defined for non-negative real (not just integer) arguments. They are used in the statement and proof of the prime number theorem.

π(n), the prime counting function, is the number of primes not exceeding x.

$\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, ...

$\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.$

[edit] Λ(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 &\mbox{if } n = 2,3,4,5,7,8,9,11,13,16,\ldots=p^k \mbox{ is a prime power}\\ 0&\mbox{if } n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;\mbox{ is not a prime power}. \end{cases}$

[edit] 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 \ldots \le a_k\; \and \;n=a_1+a_2+\cdots +a_k \right\}|.$

[edit] λ(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) &\mbox{if }n = 2,3,4,5,7,9,11,13,17,19,23,25,27,\dots\\ \tfrac12\phi(n)&\mbox{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)}}) ].$

[edit] 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.

[edit] r_k(n) - Sum of k squares

r_k(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\}|$

[edit] 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(x) := \frac12\left(\sum_{n < x} a(n) +\sum_{n \le x} a(n)\right) .$

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^[4] is given by 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.$

[edit] Dirichlet convolution

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

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

F_a(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 F_a(s) and F_b(s). The product F_a(s)F_b(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|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|n}f(d).\;$

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

$f(n) = \sum_{d|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. The article multiplicative function has a short proof.

[edit] Relations among the functions

There are a great many formulas connecting arithmetical functions with each other and with the other functions of analysis - in fact, a large part of elementary and analytic number theory is a detailed study of these relations. See the articles on the individual functions for details.

Here are a few examples:

[edit] Dirichlet convolutions

$\sum_{\delta\mid n}\mu(\delta)= \sum_{\delta\mid n}\lambda\left(\frac{n}{\delta}\right)|\mu(\delta)|= \begin{cases} &1\mbox{ if } n=1\\ &0\mbox{ if } n\ne1. \end{cases}$ where λ is the Liouville function. ^[6]

$\sum_{\delta\mid n}\varphi(\delta)= n.$ ^[7]

$\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_{\delta\mid n}\varphi(\delta)d\left(\frac{n}{\delta}\right)= \sigma(n).$ ^[8]

$\sum_{\delta\mid n}|\mu(\delta)|= 2^{\omega(n)}.$ ^[9]

$|\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\mbox{ if } n \mbox{ is a square }\\ &0\mbox{ if } n \mbox{ is not square.} \end{cases}$ where λ is the Liouville function. ^[10]

$\sum_{\delta\mid n}\Lambda(\delta)= \log n.$ ^[11]

$\Lambda(n)=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\log(\delta).$ Möbius inversion

[edit] Sums of squares

$\mbox{If }k \ge 4,\;\;\; r_k(n) > 0.$ (Lagrange's four-square theorem).

$r_2(n) = 4\sum_{d|n}\chi(d),\$ where χ is the non-principal character (mod 4) defined in the introduction.^[12]

$r_4(n) = 8 \sum_{\stackrel{d\,|\,n}{ 4\, \nmid \,d}}d = 8 (2+(-1)^n)\sum_{\stackrel{d\,|\,n}{ 2\, \nmid \,d}}d = \begin{cases} 8\sigma(n)&\mbox{if } n \mbox{ is odd }\\ 24\sigma\left(\frac{n}{2^{\nu}}\right)&\mbox{if } n \mbox{ is even } \end{cases},$ where ν = ν₂(n). ^[13]^[14]^[15]

$r_6(n) = 16 \sum_{d|n} \chi\left(\frac{n}{d}\right)d^2 - 4\sum_{d|n} \chi(d)d^2.$ ^[16]

Define the function σ_k^*(n) as^[17]

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

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

$r_8(n) = 16\sigma_3^*(n).\;$ ^[16]^[18]

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\}$ ^[19]

[edit] 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 seqences a_n and b_n. See Eisenstein series for a discussion of the series and functional identities involved in these formulas.

$\sigma_3(n) = \frac{1}{5}\left\{6n\sigma_1(n)-\sigma_1(n) + 12\sum_{1<k<n}\sigma_1(k)\sigma_1(n-k)\right\}.\;$ ^[20]

$\sigma_5(n) = \frac{1}{21}\left\{10(3n-1)\sigma_3(n)+\sigma_1(n) + 240\sum_{1<k<n}\sigma_1(k)\sigma_3(n-k)\right\}.\;$ ^[21]

$\begin{align} \sigma_7(n) &=\frac{1}{20}\left\{21(2n-1)\sigma_5(n)-\sigma_1(n) + 504\sum_{1<k<n}\sigma_1(k)\sigma_5(n-k)\right\}\\ &=\sigma_3(n) + 120\sum_{1<k<n}\sigma_3(k)\sigma_3(n-k). \end{align}$ ^[21]^[22]

$\begin{align} \sigma_9(n) &= \frac{1}{11}\left\{10(3n-2)\sigma_7(n)+\sigma_1(n) + 480\sum_{1<k<n}\sigma_1(k)\sigma_7(n-k)\right\}\\ &= \frac{1}{11}\left\{21\sigma_5(n)-10\sigma_3(n) + 5040\sum_{1<k<n}\sigma_3(k)\sigma_5(n-k)\right\}.\; \end{align}$ ^[20]^[23]

$\tau(n) = \frac{65}{756}\sigma_{11}(n) + \frac{691}{756}\sigma_{5}(n) - \frac{691}{3}\sum_{1<k<n}\sigma_5(k)\sigma_5(n-k),\;$ where τ(n) is Ramanujan's function. ^[24]^[25]

Since σ_k(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences^[26] 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).$ ^[27] This recurrence can be used to compute p(n).

[edit] Prime-count related

Let $H_n = 1 + \frac12 + \frac13 + \cdots +\frac{1}{n}$ be the n^th 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. ^[28]

$\sum_{p}\nu_p(n) = \Omega(n).\;$ ^[29]

$\psi(x)=\sum_{n\le x}\Lambda(n). \;$ ^[30]

$\Pi(x)= \sum_{n\le x}\frac{\Lambda(n)}{\log n}.\;$ ^[31]

$e^{\theta(x)}=\prod_{p\le x}p.\;$ ^[32]

$e^{\psi(x)}= \operatorname{lcm}[1,2,\dots,\lfloor x\rfloor].\;$ ^[33]

[edit] Miscellaneous

$\begin{align}&|\lambda(n)|\;\mu(n) \\&=\lambda(n)\;|\mu(n)|\\& = \mu(n), \end{align}$ and $\begin{align}&\lambda(n)\mu(n) \\&= |\mu(n)| \\&=\mu^2(n).\end{align}$ where λ(n) is Liouville's function. ^[29]

$2^{\omega(n)}\le d(n)\le2^{\Omega(n)}.\;$ ^[34]^[35]

$\lambda(n)\mid \phi(n)$ where λ(n) is Carmichael's function. ^[36] Further,

$\lambda(n)= \phi(n) \mbox{ if and only if }n=\begin{cases}1,2, 4\\ 3,5,7,9,11, \ldots \mbox{ i.e. } p^k \mbox{ where }p\mbox{ is an odd prime}\\ 6,10,14,18,\ldots \mbox{ i.e. } 2p^k\mbox{ where }p\mbox{ is an odd prime} \end{cases}$ ^[37]

$\frac{6}{\pi^2}<\frac{\phi(n)\sigma(n)}{n^2}<1.\;$ ^[38]

$\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|\gcd(q,n)}\mu\left(\frac{q}{\delta}\right)\delta. \end{align}$ ^[39] Note that $\phi(q) = \sum_{\delta|q}\mu\left(\frac{q}{\delta}\right)\delta.$ ^[40]

$c_q(1) = \mu(q).\$

$c_q(q) = \phi(q).\$

$\sum_{\delta|n}d^{\;3}(\delta) = \left(\sum_{\delta|n}d(\delta)\right)^2.\;$ ^[41] Compare this with 1³ + 2³ + 3³ + ... + n³ = (1 + 2 + 3 + ... + n)²

$d(uv) = \sum_{\delta\;|\gcd(u,v)}\mu(\delta)d\left(\frac{u}{\delta}\right)d\left(\frac{v}{\delta}\right).\;$ ^[42]

$\sigma_k(u)\sigma_k(v) = \sum_{\delta\;|\gcd(u,v)}\delta^k\sigma_k\left(\frac{uv}{\delta^2}\right).\;$ ^[43]

$\tau(u)\tau(v) = \sum_{\delta\;|\gcd(u,v)}\delta^{11}\tau\left(\frac{uv}{\delta^2}\right),\;$ where τ(n) is Ramanujan's function. ^[44]

[edit] Notes

^ Hardy & Wright, intro. to Ch. XVI
^ Hardy, Ramanujan, § 10.2
^ Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6
^ Hardy & Wright, §§ 18.1–18.2
^ 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.
^ Hardy & Wright, Thm. 263
^ Hardy & Wright, Thm. 63
^ Hardy & Wright, Thm. 288–290
^ Hardy & Wright, Thm. 264
^ See Liouville function
^ Hardy & Wright, Thm. 296
^ Hardy & Wright, Thm. 278
^ Hardy & Wright, Thm. 386
^ Hardy, Ramanujan, eqs 9.1.2, 9.1.3
^ Koblitz, Ex. III.5.2
^ ^a ^b Hardy & Wright, § 20.13
^ Hardy, Ramanujan, § 9.7
^ Hardy, Ramanujan, § 9.13
^ Hardy, Ramanujan, § 9.17
^ ^a ^b Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146
^ ^a ^b Koblitz, ex. III.2.8
^ Koblitz, ex. III.2.3
^ Koblitz, ex. III.2.2
^ Koblitz, ex. III.2.4
^ Apostol, Modular Functions ..., Ex. 6.10
^ Apostol, Modular Functions..., Ch. 6 Ex. 10
^ G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279
^ See Divisor function.
^ ^a ^b follows from the definitions
^ Hardy & Wright, eq. 22.1.2
^ See prime counting functions.
^ Hardy & Wright, eq. 22.1.1
^ Hardy & Wright, eq. 22.1.3
^ Hardy Ramanujan, eq. 3.10.3
^ Hardy & Wright, § 22.13
^ follows from the definition of λ(n) and Euler's theorem.
^ See Multiplicative group of integers modulo n and Primitive root modulo n.
^ Hardy & Wright, Thm. 329
^ Hardy & Wright, Thms. 271, 272
^ Hardy & Wright, eq. 16.3.1
^ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p.133
^ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p.134
^ Apostol, Modular Functions ..., ch. 6 eq. 4
^ Apostol, Modular Functions ..., ch. 6 eq. 3

[edit] References

Tom M. Apostol (1976). Introduction to Analytic Number Theory. Springer Undergraduate Texts in Mathematics. ISBN 0387901639.

Apostol, Tom M. (1989), Modular Functions and Dirichlet Series in Number Theory (2nd Edition), New York: Springer, ISBN 0-387-97127

Hardy, G. H. (1999), Ramanujan: Twelve Lectures on Subjects Suggested by his Life and work, Providence RI: AMS / Chelsea, ISBN 978-0821820230

Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715

G. J. O. Jameson (2003). The Prime Number Theorem. Cambridge University Press. ISBN 0-521-89110-8.

Koblitz, Neal (1984), Introduction to Elliptic Curves and Modular Forms, New York: Springer, ISBN 0-387-97966-2

William J. LeVeque (1996). Fundamentals of Number Theory. Courier Dover Publications. ISBN 0486689069.

Elliott Mendelson (1987). Introduction to Mathematical Logic. CRC Press. ISBN 0412808307.

Ramanujan, Srinivasa (2000), Collected Papers, Providence RI: AMS / Chelsea, ISBN 978-0821820766

[edit] External links

Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions PDF of a paper by Huard, Ou, Spearman, and Williams. Contains 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.

[0] Hardy & Wright, intro. to Ch. XVI

[1] Hardy, Ramanujan, § 10.2

[2] Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6

[3] Hardy & Wright, §§ 18.1–18.2

[4] 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.

[5] Hardy & Wright, Thm. 263

[6] Hardy & Wright, Thm. 63

[7] Hardy & Wright, Thm. 288–290

[8] Hardy & Wright, Thm. 264

[9] See Liouville function

[10] Hardy & Wright, Thm. 296

[11] Hardy & Wright, Thm. 278

[12] Hardy & Wright, Thm. 386

[13] Hardy, Ramanujan, eqs 9.1.2, 9.1.3

[14] Koblitz, Ex. III.5.2

[Hardy_.26_Wright.2C_.C2.A7_20.13-15] Hardy & Wright, § 20.13

[16] Hardy, Ramanujan, § 9.7

[17] Hardy, Ramanujan, § 9.13

[18] Hardy, Ramanujan, § 9.17

[Ramanujan.2C_p._146-19] Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146

[Koblitz.2C_ex._III.2.8-20] Koblitz, ex. III.2.8

[21] Koblitz, ex. III.2.3

[22] Koblitz, ex. III.2.2

[23] Koblitz, ex. III.2.4

[24] Apostol, Modular Functions ..., Ex. 6.10

[25] Apostol, Modular Functions..., Ch. 6 Ex. 10

[26] G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279

[27] See Divisor function.

[follows_from_the_definitions-28] ws from the definitions

[29] Hardy & Wright, eq. 22.1.2

[30] See prime counting functions.

[31] Hardy & Wright, eq. 22.1.1

[32] Hardy & Wright, eq. 22.1.3

[33] Hardy Ramanujan, eq. 3.10.3

[34] Hardy & Wright, § 22.13

[35] ws from the definition of λ(n) and Euler's theorem.

[36] See Multiplicative group of integers modulo n and Primitive root modulo n.

[37] Hardy & Wright, Thm. 329

[38] Hardy & Wright, Thms. 271, 272

[39] Hardy & Wright, eq. 16.3.1

[40] Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p.133

[41] Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p.134

[42] Apostol, Modular Functions ..., ch. 6 eq. 4

[43] Apostol, Modular Functions ..., ch. 6 eq. 3

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

Contents