Arithmetic functions: definitions and some properties

Posted on

In this article we’ll discuss arithmetic functions, that are functions defined on positive integers; the value of such functions, however, may not always be an integer. Some arithmetic functions are well-known and recurrent in number theory, and we have introduced them in our articles where appropriate. Here we’ll summarize their definitions and then we’ll see some of their properties that can potentially be of common use, also with regard to the techniques used in some proofs.

Definitions of some arithmetic functions

In the article The Möbius function and its connection with the function Λ we introduced the Möbius function, of which we report the definition for convenience:

Möbius function

We define the function \mu: \mathbb{N}^{\star} \rightarrow \{-1, 1, 0\} such that:

\mu(d) := \begin{cases} 1 & \text{if $d$ is square-free and is the product of an even number of prime factors} \\ -1 & \text{if $d$ is square-free and is the product of an odd number of prime factors} \\ 0 & \text{if $d$ is not square-free} \end{cases}

for every d \in \mathbb{N}^{\star}. The function \mu is called the Möbius function.

Recall that a positive integer is said to be square-free when it is not divisible by any number greater than 1 that is a square, or, equivalently, when in its factorization no exponent is greater than 1.

In the article The factorial function and the \Lambda^{\star} function we introduced the \Lambda^{\star} function, from which, by applying the logarithm, we obtain the von Mangoldt’s \Lambda function:

\Lambda function

We define the function \Lambda: \mathbb{N}^{\star} \rightarrow \mathbb{R} such that:

\Lambda(x) := \begin{cases} \log p & \text{if $x = p^m$ for some prime $p$ and some positive integer $m$} \\ 0 & \text{otherwise}\end{cases}

Other arithmetic functions have simpler definitions, so we have used them when necessary even without formally defining them. We report their definitions here, for reference purposes:

d function

We define the function d: \mathbb{N}^{\star} \rightarrow \mathbb{N}^{\star} such that:

d(n) := \textrm{number of positive divisors of $n$}

For example, d(6) = 4 because 6 has 4 positive divisors: 1, 2, 3 and 6.

\omega function

We define the function \omega: \mathbb{N}^{\star} \rightarrow \mathbb{N} such that:

\omega(n) := \textrm{number of distinct prime factors of $n$}

For example, \omega(45) = 2 because 45 = 3^2 \cdot 5 has 2 distinct prime factors, 3 and 5; the function counts the prime factors only once regardless of their exponent, so for example 3, which has exponent 2, is counted only once.

Another very important function is the Euler function, to which we’ll dedicate an article in the future. It can be defined in various ways, but we propose here the simplest:

Euler’s \phi function

We define the function \phi: \mathbb{N}^{\star} \rightarrow \mathbb{N}^{\star} such that:

\phi(n) := \textrm{number of positive integers coprime to $n$ and less than it}

For example, \phi(10) = 4 because there are exactly 4 positive integers that are coprime to 10 and less than 10: 1, 3, 7, and 9; the other positive integers less than 10 have at least one prime factor in common with 10, either 2 or 5 as the case may be.

Multiplicative and completely multiplicative arithmetic functions

A characteristic that an arithmetic function can have is that of being multiplicative:

Multiplicative function

A function f: \mathbb{N}^{\star} \rightarrow \mathbb{R} is defined as multiplicative when it satisfies the following conditions at the same time:

  • f(1) = 1
  • For any pair of positive coprime integers a and b: f(ab) = f(a)f(b)

Multiplicative functions are easy to calculate, because you can help yourself by breaking the argument of the function into coprime factors.

If f is a multiplicative function:

f(60) = f(4 \cdot 15) = f(4) \cdot f(15) = f(4) \cdot f(3 \cdot 5) = f(4) \cdot f(3) \cdot f(5)

The values of f(4), f(3) and f(5) cannot be further factored, because 4, 3 and 5 cannot be expressed as a product of two coprime numbers (the reason is that all three have a single prime factor, repeated in the case of 4).
The following image illustrates the decomposition process performed:

Figure 1: Calculating a value of a multiplicative function
Figure 1: Calculating a value of a multiplicative function

As you can see from the example, the calculation of a multiplicative function on any number can always be traced back to the calculation of the function on prime numbers or on powers of prime numbers:

Calculating the values of a multiplicative function

Let f: \mathbb{N}^{\star} \rightarrow \mathbb{R} be a multiplicative function and let n be a positive integer. Let n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k} be the factorization of n (with p_1, \ldots, p_k distinct prime factors and a_1, \ldots, a_k positive integers). Then:

f(n) = f\left(p_1^{a_1}\right) \cdot \ldots \cdot f\left(p_k^{a_k}\right) \tag{1}

We’ll proceed by induction on k, that is, on the number of distinct prime factors of n. If k = 1, then n = p_1^{a_1}: in this case, to obtain the thesis, it is sufficient to apply f to both members.
Now let’s suppose that the property holds for all numbers that have k distinct prime factors, and let’s show that it holds for a number m that has k+1 distinct prime factors.
Let m = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k} \cdot p_{k+1}^{a_{k+1}} be the factorization of m (with p_1, \ldots, p_k, p_{k+1} distinct prime factors and a_1, \ldots, a_k, a_{k+1} positive integers). Then we can write m as m = \left(p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}\right) \cdot p_{k+1}^{a_{k+1}}; this way m is the product of two coprime factors, so:

f(m) = f\left(p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}\right) \cdot f\left(p_{k+1}^{a_{k+1}}\right) \tag{a}

But the number p_1^{a_1} \cdot \ldots \cdot p_k^{a_k} has k distinct prime factors, so we can apply the induction hypothesis, obtaining:

f\left(p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}\right) = f\left(p_1^{a_1}\right) \cdot \ldots \cdot f\left(p_k^{a_k}\right)

from which, substituting into (a), we’ll have that the property also holds for k+1:

f(m) = f\left(p_1^{a_1}\right) \cdot \ldots \cdot f\left(p_k^{a_k} \right) \cdot f\left(p_{k+1}^{a_{k+1}}\right)

We can understand the previous property in this way: if we know the values of a multiplicative function on all powers of prime numbers, then we know its values on all positive integers. In fact, as we can see from formula (1), the calculation of f(n) for any n can be traced back to the calculation of the function on powers of prime numbers. Therefore, if we know the values of a multiplicative function on all powers of prime numbers, we consequently know its values on all other numbers, that is, we know the entire function; in other words, the values assumed by a multiplicative function on powers of prime numbers uniquely determine the function itself. For this reason, when defining a multiplicative function, it is sufficient to define it only on powers of prime numbers.

The case n = 1 does not fit into (1), because 1 cannot be factorized into prime factors, and even if we wanted to express it in the form p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}, all the exponents would be zero, a condition that is excluded by hypothesis. However, this is not a problem, because, if f is multiplicative, f(1) = 1 by definition.

In the previous example we can observe that, if we had expressed the number 60 as 6 \cdot 10 instead of 4 \cdot 15, we would not have been able to continue with the decomposition, since to use Definition N.27 the two factors must be coprime, while 6 and 10 are not. However, there are arithmetic functions that do not have this constraint in order to be calculated on a product: these are the completely multiplicative functions.

Completely multiplicative function

A function f: \mathbb{N}^{\star} \rightarrow \mathbb{R} is defined to be completely multiplicative when it satisfies the following conditions:

  • f(1) = 1
  • For any pair of positive integers a and b: f(ab) = f(a)f(b)

As you can see, the definition is the same as the previous one, except for the lack of the word “coprime”. So, a completely multiplicative function is also multiplicative, but the converse is not always true, because two positive integers are not always coprime.

If f is a completely multiplicative function:

f(60) = f(4 \cdot 15) = f(4) \cdot f(15) = f(2 \cdot 2) \cdot f(3 \cdot 5) = f(2) \cdot f(2) \cdot f(3) \cdot f(5)

The values f(2), f(3) and f(5) cannot be further decomposed, because 2, 3 and 5 are prime numbers; the only way they can be expressed as the product of two positive integers is as if they were times 1, but that wouldn’t change anything: for example, f(2) = f(2 \cdot 1) = f(2) \cdot f(1) = f(2) \cdot 1 = f(2) (in the penultimate equality we used the property f(1) = 1 given by the first point of the definition).
The following image illustrates the decomposition process performed:

Figure 2: Calculating a value of a completely multiplicative function.
Figure 2: Calculating a value of a completely multiplicative function.

As you can see from the example, the calculation of a completely multiplicative function on any number greater than 1 can always be traced back to the calculation of the function on prime numbers (while f(1) = 1 by definition):

Calculating the values of a completely multiplicative function

Let f: \mathbb{N}^{\star} \rightarrow \mathbb{R} be a completely multiplicative function and let n be an integer greater than 1. Let n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k} be the factorization of n (with p_1, \ldots, p_k distinct prime factors and a_1, \ldots, a_k positive integers). Then:

f(n) = \left(f(p_1)\right)^{a_1} \cdot \ldots \cdot \left(f(p_k)\right)^{a_k} \tag{2}

Let p be a prime number and h be a positive integer. We’ll prove that:

f(p^h) = \left(f(p)\right)^h \tag{b}

We’ll proceed by induction on h.
If h = 1, the equality is trivial. Assuming that equality holds for h, we can prove it for h+1 using the induction hypothesis as follows:

f(p^{h+1}) = f(p \cdot p^h) = f(p) \cdot f(p^h) = f(p) \cdot \left(f(p)\right)^h = \left(f(p)\right)^{h+1}

where in the second equality we used the second point of the definition, and in the next one we used the induction hypothesis.

Now that we have proved (b) for all h \gt 0, let’s consider the number n of the statement. By Property N.25:

f(n) = f\left(p_1^{a_1}\right) \cdot \ldots \cdot f\left(p_k^{a_k}\right)

Now, applying (b) to each factor, we’ll have that f\left(p_1^{a_1}\right) = \left(f(p_1)\right)^{a_1}, \ldots, f\left(p_k^{a_k}\right) = \left(f(p_k)\right)^{a_k}; substituting in the previous formula we’ll obtain the thesis.

As we can see, the role that powers of prime numbers had for multiplicative functions is assumed by prime numbers for completely multiplicative functions. In fact, as we can see from formula (2), the calculation of f(n) for any n is reduced to the calculation of the function on prime numbers. Therefore, the values assumed by a completely multiplicative function on prime numbers uniquely determine the function itself. For this reason, when defining a completely multiplicative function, it is sufficient to define it on prime numbers.

None of the functions we defined above are completely multiplicative, as we can see from the following counterexamples:

  • \mu(3) = -1 but \mu(3 \cdot 3) = 0 \neq \mu(3) \cdot \mu(3); in fact, 9 is not square-free while 3 is;
  • \Lambda(3) = \log 3 but \Lambda(3 \cdot 3) = \log 3 \neq \Lambda(3) \cdot \Lambda(3); in fact, for any power of 3 with a positive exponent, \Lambda takes the value \log 3;
  • d(2) = 2 but d(2 \cdot 2) = 3 \neq d(2) \cdot d(2); in fact 4 has divisors 1, 2 and 4 (3 in total), while 2 has 2 divisors, 1 and 2;
  • \omega(2) = 1 but \omega(2 \cdot 2) = 1 \neq \omega(2) \cdot \omega(2); in fact, the number of distinct prime factors of a prime number or of a power of it is always 1;
  • \phi(2) = 1 but \phi(2 \cdot 2) = 2 \neq \phi(2) \cdot \phi(2); in fact, the only positive integer coprime to 2 is 1, while there exist 2 positive integers coprime to 4 and smaller than it: 1 and 3.

However, with the exception of \Lambda, it can be shown that all the functions mentioned are multiplicative. Proofs will be added later, as they are needed in our articles. As for \Lambda, multiplicativity does not hold because the function has been defined to be used in sums rather than products; however, it can be shown that, if we were to consider its exponential function, namely e^{\Lambda}, we would obtain a multiplicative function.

Some properties of the arithmetic functions we have defined

In this section we’ll see some properties of the arithmetic functions defined previously. These properties will be used in our articles to prove specific theorems, but in themselves they can be of general interest, both because they can be used in different contexts, and for the techniques used in their proofs. The list is therefore constantly expanding, because we’ll insert new properties as we need them in our articles.

Properties of the Möbius function

Some properties of the Möbius function have been presented in the article The Möbius function and its connection with the function Λ and we’ll not repeat them here. The same applies to the article The Möbius inversion formula, devoted to another property of the same function. Let’s now look at a less known property, which we used to prove Selberg’s sieve, in particular in the article Selberg’s sieve: study of the parameters λ.

Dual Möbius inversion formula

Let n be a positive natural number and let f be a function defined on the divisors of n.
Let g be the following function defined on the divisors of n:

g(d) := \sum_{d \mid d^{\prime} \mid n} f(d^{\prime})

Then, for every k \mid n:

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

Before going into the details of the proof, let’s see an example to understand what calculations are performed:

Suppose that n = 30 and k = 2. Then, by the Möbius dual inversion formula, it should be:

f(2) = \sum_{2 \mid d \mid 30} \mu \left(\frac{d}{2}\right) g(d) = \sum_{2 \mid d \mid 30} \mu \left(\frac{d}{2}\right) \sum_{d \mid d^{\prime} \mid 30}.

Let’s check that this is actually the case:

\begin{aligned} \sum_{2 \mid d \mid 30} \mu \left(\frac{d}{2}\right) \sum_{d \mid d^{\prime} \mid 30} f(d^{\prime}) &= \\\sum_{d \in \{2, 6, 10, 30\}} \mu \left(\frac{d}{2}\right) \sum_{d \mid d^{\prime} \mid 30} f(d^{\prime}) &= \\\mu \left(\frac{2}{2}\right) \sum_{2 \mid d^{\prime} \mid 30} f(d^{\prime}) + \mu \left(\frac{6}{2}\right) \sum_{6 \mid d^{\prime} \mid 30} f(d^{\prime}) + \mu \left(\frac{10}{2}\right) \sum_{10 \mid d^{\prime} \mid 30} f(d^{\prime}) + \mu \left(\frac{30}{2}\right) \sum_{30 \mid d^{\prime} \mid 30} f(d^{\prime}) &= \\\ mu(1) \sum_{d^{\prime}\in\{2, 6, 10, 30\}} f(d^{\prime}) + \mu(3) \sum_{d^{\prime}\in\{6, 30\}} f(d^{\prime}) + \mu(5) \sum_{d^{\prime} \in \{10, 30\}} f(d^{\prime}) + \mu(15) \sum_{d^{\prime} \in \{30\}} f(d^{\prime}) &= \\\left(f(2) + f(6) + f(10) + f(30)\right) - \left(f(6) + f(30) \right) - \left(f(10) + f(30) \right) + f(30) &= \text{(*)} \\ f(2) \cdot 1 + f(6) \cdot (1 - 1) + f(10) \cdot (1 - 1) + f(30) \cdot (1 - 1 - 1 + 1) &= \\ f(2) \cdot 1 + f(6) \cdot 0 + f(10) \cdot 0 + f(30) \cdot 0 &=\\ f(2) \end{aligned}.

The proof is based on the passage (*) of the example: putting the values of the function f together, we can see that they are multiplied by algebraic sums that always result zero, except f(k) which is always multiplied by 1; this happens by virtue of Property N.11.

\begin{aligned} \sum_{k \mid d \mid n} \mu \left(\frac{d}{k}\right) \sum_{d \mid d^{\prime} \mid n} f(d^{\prime}) &= \text{[let's say $r := \frac{d}{k}$, hence $d = kr$]} \\\sum_{kr \mid n} \mu(r) \sum_{kr \mid d^{\prime} \mid n} f(d^{\prime}) &= \text{[$kr \mid d^{\prime} \Rightarrow d^{\prime} = krs$]} \\\sum_{kr \mid n} \mu(r) \sum_{krs \mid n} f(krs) &= \\\sum_{r \mid \frac{n}{k}} \mu(r) \sum_{rs \mid \frac{n}{k}} f(krs) &= \\\sum_{r \mid \frac{n}{k}} \sum_{rs \mid \frac{n}{k}} \mu(r) f(krs) &= \\\sum_{r \mid rs \mid \frac{n}{k}} \mu (r) f(krs) &= \text{[$a := rs$]} \\\sum_{r \mid a \mid \frac{n}{k}} \mu(r) f(ka) &= \\\sum_{a \mid \frac{n}{k}} \sum_{r \mid a} \mu(r) f(ka) &= \\\sum_{a \mid \frac{n}{k}} f(ka) \sum_{r \mid a} \mu(r) &= \text{[by Property N.11, $\sum_{r \mid a} \mu(r) \neq 0 \Leftrightarrow a = 1$]} \\ f(k)\end{aligned}

Properties of the \omega function

Number of integers pairs having a fixed square-free least common multiple

Let d be a square-free positive integer. The number of ordered pairs of positive integers having least common multiple d is equal to:

3^{\omega(d)}

The property counts ordered pairs in the sense that, for example, the pairs (2, 3) and (3, 2) are to be considered distinct, and both have a least common multiple of 6.

If d = 15 = 3 \cdot 5, the ordered pairs of positive integers that have as their least common multiple d are the following:

(15, 1), (3, 5), (15, 5), (5, 3), (1, 15), (5, 15), (15, 3), (3, 15), (15, 15)

The number of pairs is 9 = 3^2 = 3^{\omega(15)}, as expected by the Property.

To count how many pairs of positive integers have least common multiple d, we need to remember a method of calculating the least common multiple based on factorization: after factoring the two numbers, their least common multiple is given by the product of their common and non-common prime factors, with the maximum exponent. For example, if the two numbers are d_1 = 2^2 \cdot 3 and d_2 = 2 \cdot 5^2, their least common multiple will be d = 2^2 \cdot 3 \cdot 5^2. This example, however, cannot occur in our case, because we started from a square-free number d, which is the product of distinct prime factors; so, in the factorization of d we can only find prime numbers with exponent 1.
Given these premises, to count how many possible pairs of integers have d as their least common multiple, we must reason in reverse: that is, if all the prime factors of d have exponent 1, being therefore 1 the maximum exponent with which such factors appear in d_1 or in d_2, it means that for each prime factor p only three cases can occur:

  • p is present in d_1 with exponent 1 and is not present in d_2;
  • p is present in d_2 with exponent 1 and is not present in d_1;
  • p is present in both d_1 and d_2, both with exponent 1.

In fact, if p were absent in both, it would also be absent in the least common multiple, while, if it had in one of the two numbers an exponent greater than 1, it would have an exponent greater than 1 also in the least common multiple; but both of these circumstances are to be excluded, so only the three cases listed are possible.
This is true for all prime factors p of d: if there is more than one, the three cases get combined for each factor, multiplying. For example, if in the least common multiple there are two factors p and q, the possible cases become 9, because each of the three possible cases for p can combine with each of the three possible cases for q. In general, if in d there are k prime factors, the number of possible cases is 3 multiplied by itself k times, or 3^k.
Each of the cases thus obtained says exactly which prime factors appear in d_1 and in d_2: in fact, d_1 and d_2 cannot have prime factors that are not in d. So the two numbers are uniquely determined by which prime factors of d they contain, which is exactly what each case establishes. Therefore, the number of possible pairs coincides with the number of possible cases, that is 3^k, where k is the number of prime factors of d.

Suppose that d = 3 \cdot 5, a product of k = 2 distinct primes. Then, if \mathrm{lcm}(d_1, d_2) = d, there are 3^2 = 9 cases:

  • 3 is present in d_1 with exponent 1 and is not present in d_2; 5 is present in d_1 with exponent 1 and is not present in d_2;
  • 3 is present in d_1 with exponent 1 and is not present in d_2; 5 is present in d_2 with exponent 1 and is not present in d_1;
  • 3 is present in d_1 with exponent 1 and is not present in d_2; 5 is present in both d_1 and d_2, both with exponent 1;
  • 3 is present in d_2 with exponent 1 and is not present in d_1; 5 is present in d_1 with exponent 1 and is not present in d_2;
  • 3 is present in d_2 with exponent 1 and is not present in d_1; 5 is present in d_2 with exponent 1 and is not present in d_1;
  • 3 is present in d_2 with exponent 1 and is not present in d_1; 5 is present in both d_1 and d_2, both with exponent 1;
  • 3 is present in both d_1 and d_2, in both with exponent 1; 5 is present in d_1 with exponent 1 and is not present in d_2;
  • 3 is present in both d_1 and d_2, in both with exponent 1; 5 is present in d_2 with exponent 1 and is not present in d_1;
  • 3 is present in both d_1 and d_2, both with exponent 1; 5 is present in both d_1 and d_2, both with exponent 1.

In each case, we obtain the following ordered pairs of integers having as least common multiple d:

  • (d_1, d_2) = (15, 1)
  • (d_1, d_2) = (3, 5)
  • (d_1, d_2) = (15, 5)
  • (d_1, d_2) = (5, 3)
  • (d_1, d_2) = (1, 15)
  • (d_1, d_2) = (5, 15)
  • (d_1, d_2) = (15, 3)
  • (d_1, d_2) = (3, 15)
  • (d_1, d_2) = (15, 15)

We have thus found the pairs seen in the previous example.

Leave a Reply

Your email address will not be published. Required fields are marked *

Quest'opera è distribuita con Licenza Creative Commons Attribuzione - Condividi allo stesso modo 3.0 Unported

Seamless Theme Keith, made by Altervista

Create a website and earn with Altervista - Disclaimer - Report Abuse - Privacy Policy - Customize advertising tracking