1.2 Arithmetic functions

Formally, an arithmetic function is simply a sequence, with real or complex values. A sequence is, of course, a function on the set $\mathbb{N}$ of positive integers. To emphasize that we are thinking of them as functions, we shall usually use notation like $a(n)$, rather than $a_n$, for the value corresponding to the integer $n$. The term ``arithmetic function" is used especially when $a(n)$ is defined using number-theoretic properties in some way. A large part of number theory consists, in one way or another, of the study of these functions.

We list some examples. First, two very simple ones, mainly to establish the notation we will use:

    $u(n) = 1$  for all $n$     (the ``unit function");

     $\dis{ e_j(n) = \left\{ \begin{array}{ll} 1 & \mbox{if } n = j, \\ 0 & \mbox{if } n \neq j. \end{array}\right. }$

Next, given any subset $E$ of $\mathbb{N}$ (for example, the set $P$ of primes), define

     $\dis{ u_E(n) = \left\{ \begin{array}{ll} 1 & \mbox{if } n \in E, \\ 0 & \mbox{if } n \notin E. \end{array} \right. }$

Clearly, $u$ itself is the case $E = \mathbb{N}$. Thirdly, three more obviously number-theoretic examples:

     $\tau (n) =$  the number of (positive) divisors of $n$, including 1 and $n$;

     $\omega (n) =$  the number of prime divisors of $n$;

     $\Omega (n) =$  the number of prime factors of $n$, counted with repetitions.

(This notation is more or less standard, though some writers use $d$ instead of $\tau$.) Note that  $\tau (1) = 1$ and $\omega (1) = \Omega (1) = 0$. For $n > 1$, these functions can easily be described in terms of the prime factorization of $n$:

Proposition 1.2.1. Suppose that $n > 1$, with prime factorization

$$n = \prod_{j=1}^m p_j^{k_j}.$$

Then

$$\tau (n) = \prod_{j=1}^m (k_j +1), \quad \omega (n) = m, \quad \Omega (n) = \sum_{j=1}^m k_j.$$

Proof. The expressions for $\omega (n)$ and $\Omega (n)$ are just the definition. Divisors of $n$ are of the form  $\prod_{j=1}^m p_j^{r_j}$, where for each $j$, the possible values of $r_j$ are $0, 1, \ldots ,k_j$. This gives the expression for $\tau (n)$. $\Box$

In particular, if $p$ is prime, then $\tau (p^k) = k+1$,   $\omega (p^k) = 1$  and  $\Omega (p^k) = k$. To give another example, since $72 = 2^3.3^2$, we have $\tau (72) = 12$,   $\omega (72) = 2$  and  $\Omega (72) = 5$.

Given arithmetic functions $a$,$b$, we denote the pointwise product by $ab$, so that $(ab)(n) = a(n)b(n)$. Obviously, $au = a$ for any $a$.

Summation functions. Given an arithmetic function $a(n)$, its ``summation function" $A(x)$ is defined by

$$A(x) = \sum_{n \leq x} a(n).$$

It is useful to regard $A(x)$ as a function of a real variable $x$. As such a function, it is, of course, constant between integers and has a jump discontinuity at each integer where $a(n) \neq 0$. Clearly, $\pi (x)$ is the summation function of $u_P(n)$ (note: in particular cases, the established notation will not usually allow a notational device like the substitution of $A$ for $a$).

Individual values of arithmetic functions may fluctuate wildly - as in most of the examples just given. However, in many cases summation smooths out the fluctuation, and it may be possible to find an asymptotic expression for the summation function for large $x$. In the case of $\tau (n)$ and $\omega (n)$, the first step is to apply a bit of ``lateral thinking" to obtain alternative expressions for the summation functions, as in the next result. The notation $[x]$ means the largest integer not greater than $x$. We shall use the notation $P[x]$ to mean the set of primes not greater than $x$ (but there is no generally agreed notation for this). Also, $j\vert n$ means that $j$ divides into $n$.

Proposition 1.2.2. Write $S_\tau (x) = \sum_{n \leq x} \tau (n)$ and $S_\omega (x) = \sum_{n \leq x} \omega (n)$. Then

$$S_\tau (x) = \sum_{j \leq x} \left[ \frac{x}{j} \right], \qquad S_\omega (x) = \sum_{p \in P[x]} \left[ \frac{x}{p} \right].$$

Proof. Clearly, $S_\tau (x)$ is the number of ordered pairs $(j,n)$ such that $j\vert n$ and $n \leq x$. For fixed $j$ (instead of fixed $n$), the number of such pairs is the number of multiples $rj$ not greater than $x$. This number is obviously $[x/j]$. The stated expression follows.

The argument for $S_\omega (x)$ is similar, counting the number of pairs $(p,n)$ as above, but with $p$ prime. $\Box$.

The ``double counting" principle seen in this proof is often useful. We shall see later how the identities in 1.2.2 can be used to derive asymptotic expressions for $S_\tau (x)$ and $S_\omega (x)$, and similar results will be obtained for some other arithmetic functions. Since $\pi (x)$ is itself a summation function, our main objective, the prime number theorem, is a result of exactly this type. But as the reader may suspect, this case will cost us a lot more effort than most of the others.

Multiplicative functions. We denote by $(m,n)$ the greatest common divisor of $m$ and $n$. An arithmetic function $a$ is said to be

    completely multiplicative if  $a(mn) = a(m)a(n)$ for all $m,n$;

    multiplicative if  $a(mn) = a(m)a(n)$ whenever $(m,n) = 1$.

Clearly, if $a$ is multiplicative and not identically zero, then $a(1) = 1$. Also, $a$ is fully determined by the values $a(p^k)$ for prime $p$, since if the prime factorization of $n$ is  $\prod_{j=1}^r p_j^{k_j}$, then $a(n) = \prod_{j=1}^r a(p_j^{k_j})$. Of course, if $a$ is completely multiplicative, then  $a(p^k) = a(p)^k$, and the function is already fully determined by the values $a(p)$.

We list some examples.

As the reader may already know, there are many further interesting examples of arithmetic functions. Some will make their appearance in later sections.

Exercises

1. Find the smallest $n$ such that  (i) $\Omega (n) = 4$,  (ii) $\omega (n) = 4$,  (iii) $\tau (n) = 4$.

2. Show that  $\sum_{n=1}^{30} \tau (n) = 111$  without calculating individual values of $\tau (n)$.

3. Calculate  $\sum_{n=1}^{100} \omega (n)$  without calculating individual values of $\omega (n)$.

4. Show that for any $n \geq 2$,

$$2^{\omega (n)} \leq \tau (n) \leq 2^{\Omega (n)} \leq n.$$

[You may assume that $k+1 \leq 2^k$ for all $k \geq 0$.]

5. Let $S$ be the set of squares. Show that $u_S$ is multiplicative.

6. Let  $a(n) = (-1)^{n-1}$  for $n \geq 1$. Show that $a$ is multiplicative.

7. Prove that for any $\varep > 0$, we have  $\tau (n)/n^\varep \to 0$  as $n \to \infty$. [Again use $k+1 \leq 2^k$. For each prime  $p < 2^{1/\varep }$, show that there is a constant $C_p$ such that  $k+1 \leq C_p\: p^{\varep k}$  for all $k$. ]