1.2: Arithmetic Functions

The next topic we shall consider is that of arithmetic functions. These form the main objects of concern in number theory. We have already mentioned two such functions of two variables, the g.c.d. and l.c.m. of \(m\) and \(n\), denoted by \((m, n)\) and \([m, n]\) respectively, as well as the functions \(c(n)\) and \(p(n)\). Of more direct concern at this stage are the functions

\(\begin{array} {lcl} {\pi(n) = \sum_{p \le n} 1} & & {\text{the number of primes \(n\) not exceeding \(n\);}}\\ {w(n) = \sum_{p | n} 1} & & {\text{the number of distinct primes factors of \(n\);}} \\{\omega(n) = \sum_{p \le n} 1} & & {\text{the number of primes \(n\) not exceeding \(n\);}} \\{\Omega(n) = \sum_{p^{i} \le n} 1} & & {\text{the number of prime factors of \(n\);}}\\ {\tau(n) = \sum_{d | n} 1} & & {\text{the number of divisors \(n\);}}\\ {\sigma(n) = \sum_{d|n} d} & & {\text{the sum of the divisors of \(n\)}} \\ {\varphi(n) = \sum_{(a,n) = 1 \\ 1 \le a \le n} 1} & & {\text{the Euler totient function;}} \end{array}\)

the Euler totient function counts the number of integers \(\le n\) and relatively prime to \(n\).

In the section we shall be particularly concerned with the functions \(\tau(n)\), \(\sigma(n)\), and \(\varphi(n)\). These have the important property that if

\(n = ab\) and \((a, b) = 1\)

then

\(f(ab) = f(a) f(b)\).

Any function satisfying this condition is called weakly multiplicative, or simply multiplicative.

A generalization of \(\tau(n)\) and \(\sigma(n)\) is afforded by

\(\sigma_k (n) = \sum_{d|n} d^k\). then the sum of the \(k^{\text{th}}\) powers of the divisors of \(n\),

since \(\sigma_0 (n) = \tau(n)\) and \(\sigma_1 (n) = \sigma (n)\).

The \(\varphi\) function can also be generalized in many ways. We shall consider later the generalization due to Jordan, \(\varphi_k(n) =\) number of \(k\)-tuples \(\le n\) whose g.c.d. is relatively prime to n. We shall derive some elementary properties of these and closely related functions and state some special solved and unsolved problems concerning them. We shall then discuss a theory which gives a unified approach to these functions and reveals unexpected interconnections between them. Later we shall discuss the magnitude of these functions. The functions \(\omega(n)\), \(\Omega(n)\), and, particularly, \(\pi(n)\) are of a different nature and special attention will be given to them.

Suppose in what follows that the prime power factorization of \(n\) is given by

\(n = p_{1}^{\alpha_1} p_{2}^{\alpha_2} \cdot\cdot\cdot p_{s}^{\alpha_s}\) or briefly \(n = \prod p^{\alpha}\).

We note that 1 is not a prime and take for granted the provable result that, apart from order, the factorization is unique.

In terms of this factorization the functions \(\sigma_{k}(n)\) and \(\varphi(n)\) are easily determined. It is not difficult to see that the terms in the expansion of the product

\(\prod_{p|n} (1 + p^k + p^{2k} + \cdot\cdot\cdot + p^{\alpha k})\)

are precisely the divisors of \(n\) raise to the \(k^{\text{th}\) power. Hence we have the desired expansion for \(\sigma_{k}(n)\). In particular

\(\tau (n) = \sigma_0 (n) = \prod (\alpha + 1)\),

and

\(\sigma(n) = \sigma_1 (n) = \prod_{p|n} (1 + p + p^{2} + \cdot\cdot\cdot + p^{\alpha}) = \prod_{p|n} \dfrac{p^{\alpha + 1} - 1}{p - 1}\),

e.g., \(60 = 2^2 \cdot 3^1 \cdot 5^1\),

\(\tau(60) = (2 + 1)(1 + 1)(1 + 1) = 3 \cdot 2 \cdot 2 = 12\),

\(\sigma(60) = (1 + 2 + 2^2) ( 1+ 3) ( 1+ 5) = 7 \cdot 4 \cdot 6 = 168.\)

These formulas reveal the multiplicative nature of \(\sigma_k(n)\).

To obtain an explicit formula for \(\varphi (n)\) we make use of the following well-known combinatorial principle.

The principle of inclusion and exclusion

Given \(N\) objects each of which which may or may not possess any of the characteristics

\(A_1, A_2, ... .\)

Let \(N(A_i, A_j, ...)\) be the number of objects having the characteristics \(A_i, A_j, ...\) and possibly. othes. Then the number of objects which have none of these properties is

\(N - \sum N(A_i) + \sum_{i < j} N(A_i, A_j) - \sum_{i < j < k} N(A_i, A_j, A_k) +\cdot\cdot\cdot,\)

where the summation is extended over all combinations of the subscripts 1, 2, ... , \(n\) in groups of one, two, three and so on, and the signs of the terms alternate.

An integer will be relatively prime to \(n\) only if it is not divisible by any of the prime factors of \(n\). Let \(A_1, A_2 , ... , A_s\) denote divisibility by \(p_1, p_2, ... , p_s\) respectively. Then, according to the combinatorial principle stated above

\(\varphi(n) = n - \sum_i \dfrac{n}{p_i} + \sum_{i < j} \dfrac{n}{p_i p_j} - \sum_{i < j < k} \dfrac{n}{p_i p_j p_k} + \cdot\cdot\cdot\).

This expression can be factored into the form

\(\varphi (n) = n \prod_{p|n} (1 - \dfrac{1}{p}),\)

e.g.

\(\varphi (60) = 60 (1 - \dfrac{1}{2}) (1 - \dfrac{1}{3}) (1 - \dfrac{1}{5}) = 60 \cdot \dfrac{1}{2} \cdot \dfrac{2}{3} \cdot \dfrac{4}{5}. = 16.\)

A similar argument shows that

\(\varphi_{k}(n) = n^{k} \prod_{p|n} ( 1- \dfrac{1}{p^{k}}).\)

The formula for \(\varphi(n)\) can also be written in the form

\(\varphi(n) = n \sum_{d |n} \dfrac{\mu (d)}{d},\)

where \(\mu (d)\) takes on the values 0, 1, −1. Indeed \(\mu (d) = 0\) if \(d\) has a square factor, \(\mu (1) = 1\), and \(\mu(p_1p_2 \cdot\cdot\cdot p_s) = (−1)^s\). This gives some motivation for defining a function \(\mu(n)\) in this way. This function plays an unexpectedly important role in number theory.

Our definition of \(\mu(n)\) reveals its multiplicative nature, but it it still seems rather artificial. It has however a number of very important properties which can be used as alternative definitions. We prove the most important of these, namely

\(\sum_{d | n} \mu(d) = \begin{cases} 1 & \text{if} n = 1,\\ 0 & \text{if} n \ne 1. \end{cases}\)

Since \(\mu(d)= 0\) if \(d\) contains a squared factor, it suffices to suppose that \(n\) has no such factor, i.e., \(n = p_1p_2 \cdot\cdot\cdot p_s\). For such an \(n > 1\)

\(\sum_{d | n} \mu(d) = 1 - {n \choose 1} + {n \choose 2} - \cdot\cdot\cdot = (1 - 1)^n = 0\).

By definition \(\mu(1) = 1\) so the theorem is proved.

If we sum this result over \(n = 1, 2, ..., x\), we obtain

\(\sum_{d = 1}^{x} [\dfrac{x}{d}] \mu(d) = 1\),

which is another defining relation.

Another very interesting defining property, the proof of which I shall leaveas an exercise, is that if

\(M(x) = \sum_{d = 1}{x} \mu (d)\)

then

\(\sum_{d = 1}^{x} M([\dfrac{x}{d}]) = 1.\)

This is perhaps the most elegant definition of \(\mu\). Still another very important property is that

\((\sum_{n = 1}^{\infty} \dfrac{1}{n^{s}}) (\sum_{n = 1}^{\infty} \dfrac{\mu(n)}{n^s} ) = 1.\)

We now turn our attention to Dirichlet multiplication and series.

Consider the set of arithmetic functions. These can be combined in various ways to give new functions. For example, we could define \(f + g\) by

\((f + g) (n) = f(n) + g(n)\)

and

\((f \cdot g)(n) = f(n) \cdot g(n)\)

A less obvious mode of combination is given by \(f \times g\), defined by

\((f \times g) (n) = \sum_{d|n} f(d) g(\dfrac{n}{d}) = \sum_{dd' = n} f(d) g(d').\)

This may be called the divisor product or Dirichlet product.

This motivation for this definition os as follows. If

\(F(s) = \sum_{n = 1}^{\infty} f(n) n^{-s}\), \(F(s) = \sum_{n = 1}^{\infty} g(n) n^{-s}\), and \(F(s) \cdot G(s) = \sum_{n = 1}^{\infty} h(n) n^{-s},\)

then it is readily checked that \(h = f \times g\). Thus Dirichlet multiplication of arithmetic functions corresponds to the ordinary multiplication of the corresponding Dirichlet series:

\(f \times g = g \times f\), \((f \times g) \times h = f \times (g \times h)\),

i.e., our multiplication is commutative and associative. A purely arithmetic proof of these results is easy to supply.

Let us now define the function

\(\ell = \ell(n) : 1, 0, 0, ... .\)

It is easily seen that \(f \times \ell = f\). Thus the function \(ell\) is the unity of our multiplication.

It can be proved without difficulty that if \(f(1) \ne 0\), then \(f\) has an inverse with repect to \(ell\). Such functions are called regular. Thus the regular functions form a group with respect to the operation \(\times \).

Another theorem, whose proof we shall omit, is that the Dirichlet product of multiplicative functions is again multiplicative.

We now introduce the functions

\(I_k : 1^k, 2^k, 3^k, ... .\)

It is interesting that, starting only with the functions \(\ell\) and \(I_k\), we can build up many of the arithmetic functions and their important properties.

To begin with we may define \(\mu(n)\) by \(\mu = I_{0}^{-1}\). This means, of course, that \(\mu \times I_0 = \ell\) or

\(\sum_{d | n} \mu(d) = \ell (n)\).

and we have already seen that this is a defining property of the \(\mu\) function. We can define \(\sigma_{k}\) by

\(\sigma_k = I_0 \times I_k\).

This means that

\(\sigma_k(n) = \sum_{d|n} (d^k \cdot 1),\)

which corresponds to our earlier definition. Special cases are

\(\tau = I_0 \times I_0 = I_0^2\) and \(\sigma = I_0 \times I_1\)

Further, we can define

\(\varphi_k = \mu \times I_k = I_0^{-1} \times I_k\).

This means that

\(\varphi_k(n) = \sum_{d|n} \mu(d) (\dfrac{n}{d})^k,\)

which again can be seen to correspond to our earlier definition.

The special case of interest here is

\(\varphi = \varphi_1 = \mu \times I_1.\)

Now, to obtain some important relations between our functions, we note the so-called M\(\ddot{\text{o}}\)bius inversion formula. From our point of view this says that

\(g = f \times I_0 \iff f = u \times g\)

This is, of course, quite transparent. Written out in full it states that

\(g(n) = \sum_{d|n} f(d) \iff f(n) = \sum_{d | n} \mu(d) g(\dfrac{n}{d}).\)

In this form it is considerably less obvious.

Consider now the following applications. First

\(\sigma_k = I_0 \times I_k \iff I_k = \mu \times \sigma_k\).

This means that

\(\sum_{d|n} \mu(d) \sigma_k(\dfrac{n}{d}) = n^k.\)

Important special cases are

\(\sum_{d | n} \mu(d) \tau(\dfrac{n}{d}) = 1,\)

and

\(\sum_{d | n} \mu(d) \sigma(\dfrac{n}{d}) = 1.\)

Again

\(\varphi_k = I_0^{-1} \times I_k \iff I_k = I_0 \times \varphi_k,\)

so that

\(\sum_{d|n} \varphi_k (d) = n^k,\)

We can obtain identities of a somewhat different kind. Thus

\(\sigma_k \times \varphi_k = I_0 \times I_k \times I_0^{-1} \times I_k = I_k \times I_k,\)

and hence

\(\sum_{d|n} \sigma_k(d) \varphi_k (\dfrac{n}{d}) = \sum_{d|n}d^{k}(\dfrac{n}{d})^k = \sum_{d|n} n^k = \tau(n) n^k.\)

A special case of interest here is

\(\sum_{d|n} \sigma(d) \varphi (\dfrac{n}{d}) = n \tau(n).\)

In order to make our calculus applicable to problems concerning distribution of primes, we introduce a unary operation on our functions, called differentiation:

\(f'(n) = -f(n)\) log \(n\)

The motivation for this definition can be seen from

\(\dfrac{d}{ds} (\sum \dfrac{f(n)}{n^s}) = -\sum \dfrac{(\text{log} n) f(n)}{n^s}.\)

Now let us define

\(\Lambda(n) = \begin{cases} \text{log} p & \text{if} n = p^{\alpha}, \\ 0 & \text{if} n \ne p^{\alpha}. \end{cases}\)

It is easily seen that

\(\sum_{d|n}\Lambda(d) = \text{log} n\)

In our Dirichlet multiplication notation we have

\(\Lambda \times I_0 = -I_0^{'},\)

so that

\(\Lambda = I_0^{-1} \times ( -I_0^{'}) = \mu \times ( -I_0^{'})\)

or

\(\Lambda(n) = \sum_{d|n} \mu(d) \text{ log } (\dfrac{n}{d}) = - \sum_{d|n} \mu(d) \text{ log } d.\)

Let us now interpret some of our results in terms of Dirichlet series. We have the correspondence

\(F(s) \leftrightarrow f(n)\) if \(F(s) = \sum \dfrac{f(n)}{n^s},\)

and we know that Dirichlet multiplication of arithmetic functions corresponds to ordinary multiplication for Dirichlet series. We start with

\(f \leftrightarrow F, 1 \leftrightarrow 1\), and \(I_0 \leftrightarrow \zeta(s).\)

Furthermore

\(I_k \leftrightarrow \sum_{n = 1}^{\infty} \dfrac{n^k}{n^s} = \zeta (s - k).\)

Also

\(\mu \leftrightarrow \dfrac{1}{\zeta (s)}\) and \(I_0^{'} \leftrightarrow \sum \dfrac{-\text{ log }n}{n^s} = \zeta '(s).\)

This yields

\(\sum \dfrac{\sigma_k(n)}{n^s} = \zeta (s) \zeta (s - k).\)

Special cases are

\(\sum \dfrac{\tau (n)}{n^s} = \zeta^2 (s)\)

and

\(\sum \dfrac{\sigma (n)}{n^s} = \zeta(s) \zeta (s - 1).\)

Again

\(\sum \dfrac{\mu(n){n^s) = \dfrac{1}{\zeta(s)}\)

and

\(\sum \dfrac{\varphi_k (n)}{n^s} = \dfrac{\zeta (s - k)}{\zeta (s)},\)

with the special case

\(\sum \dfrac{\varphi (n)}{n^s} = \dfrac{\zeta (s - 1)}{\zeta (s)}.\)

To bring a few of these down to quite numerical results we have

\(\begin{array} {rcl} {\sum \dfrac{\tau (n)}{n^2}} & = & {\zeta^2 (2) = \dfrac{\pi ^4}{36},} \\ {\sum \dfrac{\sigma_4 (n)}{n^2}} & = & {\zeta (2) \cdot \zeta (4) = \dfrac{\pi^2}{6} \cdot \dfrac{\pi^4}{90} = \dfrac{\pi^6}{540}.} \\ {\sum \dfrac{\mu (n)}{n^2}} & = & {\dfrac{6}{\pi^2}} \end{array}\)

As for our \(\Lambda\) function, we had

\(\Lambda = I_{0}^{-1} \times I_0^{'};\)

this means that

\[\sum_{n -= 1}^{\infty} \dfrac{\Lambda (n)}{n^s} = \dfrac{-\zeta'(s)}{\zeta (s)}.\]

The prime number theorem depends on going from this to a reasonable estimate for

\(\Psi (x) = \sum_{n = 1}^{x} \Lambda(n).\)

Indeed we wish to show that \(\Psi(x) \thicksim x\).

Any contour integration with the right side of (1) involves of course the need for knowing where \(\zeta (s)\) vanishes. This is one of the central problems of number theory.

Let us briefly discuss some other Dirichlet series.

If \(n = p_{1}^{\alpha_1} p_{2}^{\alpha_2} \cdot\cdot\cdot p_{s}^{\alpha_s} \) define

\(\lambda (n) = (-1)^{\alpha_1 + \alpha_2 + \cdot\cdot\cdot + \alpha_s}.\)

The \(\lambda\) function has properties similar to those of the \(\mu\) function. We leave as an exercise to show that

\(\sum_{d|n} \lambda (d) = \begin{cases} 1 & \text{if } n = r^2. \\ 0 & \text{if } n \ne r^2.\end{cases}\)

Now

\(\zeta (2s) = \sum \dfrac{s(n)}{n^s}\) where \(s(n) = \begin{cases} 1 & \text{if } n = r^2. \\ 0 & \text{if } n \ne r^2.\end{cases}\)

Hence \(\lambda \times I_0 = s\), i.e.,

\(\sum \dfrac{\lambda (n)}{n^s} \cdot \zeta (s) = \zeta(2s)\)

or

\(\sum \dfrac{\lambda (n)}{n^s} = \dfrac{\zeta (2s)}{\zeta (s)}.\)

For example

\(\sum \dfrac{\lambda (n)} {n^2} = \dfrac{\pi^4}{90} / \dfrac{\pi^2}{6} = \dfrac{\pi^2}{15}.\)

We shall conclude with a brief look at another type of generating series, namely Lambert series. These are series of the type

\(\sum \dfrac{f(n) x^n}{1 - x^n}.\)

It is easily shown that if \(F = f \times I_0\) then

\(\sum \dfrac{f(n)x^n}{1 - x^n} = \sum F(n) x^n.\)

Interesting special cases are

\(f = I_0, \sum \dfrac{x^n}{1 - x^n} = \sum \tau(n) x^n\);

\(f = \mu, \sum \mu(n) \dfrac{x^n}{1 - x^n} = x\);

\(f = \varphi, \sum \varphi (n) \dfrac{x^n}{1 - x^n} = \sum n x^n = \dfrac{x}{(1 - x)^2}.\)

For example, taking \(x = \dfrac{1}{10}\) in the last equality, we obtain

\(\dfrac{\varphi(1)}{9} + \dfrac{\varphi(2)}{99} + \dfrac{\varphi(3)}{999} + \cdot\cdot\cdot = \dfrac{10}{81}.\)

Exercise \(\PageIndex{1}\)

Prove that \(\sum_{n = 1}^{\infty} \dfrac{\mu(n) x^n}{1 + x^n} = x - 2x^2.\)

Prove that \(\sum_{n = 1}^{\infty} \dfrac{\lambda(n) x^n}{1 - x^n} = \sum_{n = 1}^{\infty} x^{n^2}.\)

Answer

Add texts here. Do not delete this text first.