Prerequisite:
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:
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:
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:
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:
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:
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:
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:
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:
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:
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:
from which, substituting into (a), we’ll have that the property also holds for k+1:
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:
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:
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:
Let p be a prime number and h be a positive integer. We’ll prove that:
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:
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:
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:
Then, for every k \mid n:
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:
Let’s check that this is actually the case:
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.
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:
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:
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.
Properties of the function d
Asymptotic order of the sum of d(n) for the first positive integers
Let x be a positive integer. Then:
The sum \sum_{n \leq x} d(n) can be displayed using a table with columns and rows numbered from 1 to x, where we put a dash in correspondence with the cells such that the row number is a divisor of the column number. For example, for n = 10 we’ll have the following table:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|
1 | – | – | – | – | – | – | – | – | – | – |
2 | – | – | – | – | – | |||||
3 | – | – | – | |||||||
4 | – | – | ||||||||
5 | – | – | ||||||||
6 | – | |||||||||
7 | – | |||||||||
8 | – | |||||||||
9 | – | |||||||||
10 | – |
For how the table was constructed, d(n) is, for each n, the number of dashes in column n. For example, column 10 of the table contains 4 dashes because the number 10 has 4 divisors (1, 2, 5 and 10, which are the numbers of the rows that contain the dashes in that column).
Consequently, the sum \sum_{n \leq x} d(n) is the sum of the number of dashes in all the columns of the table, that is, the total number of dashes. However, we can also count the same dashes by reading the table by rows instead of by columns. In fact, as you can see from the table, row i contains a dash for each multiple of i between 1 and x. To count these multiples, we can just use the formula \left\lfloor \frac{x}{i} \right\rfloor (that is, the integer part rounded down to \frac{x}{i}). For example, if x = 10 and i = 3 we’ll have \left\lfloor \frac{10}{3} \right\rfloor = 3 multiples of 3 between 1 and 10, corresponding to the three dashes in the third row of the table. Since \left\lfloor \frac{x}{i} \right\rfloor is the number of dashes in the i-th row, to calculate the total number of dashes in the table, we need to add this formula as i varies for all rows: \sum_{i = 1}^{x} \left\lfloor \frac{x}{i} \right\rfloor. However, since the number of dashes is always the same, regardless of whether they are counted by rows or columns, the results of the two formulas must coincide, therefore:
To find the asymptotic order of the right-hand summation, we can observe that the value of \left\lfloor \frac{x}{i} \right\rfloor, being a defect approximation, is always between \frac{x}{i} (inclusive) and \frac{x}{i} + 1 (excluded); in general we can say that \left\lfloor \frac{x}{i} \right\rfloor = \frac{x}{i} + O(1), because the difference between \left\lfloor \frac{x}{i} \right\rfloor and \frac{x}{i} is a bounded function, between 0 included and 1 excluded, therefore by Property A.7 it is a O(1). So we’ll have that:
The sum \sum_{i = 1}^{x} \frac{1}{i}, by Theorem N.6, is equal to \log x + \gamma + O\left(\frac{1}{x}\right), an expression that we can simplify as \log x + O(1) because both \gamma and O\left(\frac{1}{x}\right) are O(1): \gamma by the Corollary of Property A.7, O\left(\frac{1}{x}\right) because, according to Properties A.16 and A.10, O\left(\frac{1}{x}\right) = O(o(1)) = o(1) = O(1).
By making this substitution and applying the properties of asymptotic orders Corollary 1 of Property A.8 and Corollary of Property A.9 we’ll finally obtain:
Asymptotic order of the sum of d(n) over n for the first positive integers
Let x be a positive integer. Then:
To compute the asymptotic order of the sum we apply the Lemma N.5 by setting c_n := d(n) and f(n) := \frac{1}{n}. This function f(n) can be understood as defined on all positive real numbers, so that it is of class C^1 in the interval [1,x], as required by the hypotheses of the Lemma (it will therefore coincide with its extension which in the Lemma is called \widetilde{f}). Furthermore, using the notations of the Lemma, we define the cumulative sum function:
Then the thesis of the Lemma tells us that:
But, by Proposition N.30, we have C(x) = x \log x + O(x). As for the simple extension \overline{C}, it coincides by definition with the function C applied to the integer part of its argument, so \overline{C}(t) = C(\left\lfloor t \right\rfloor) = \left\lfloor t \right\rfloor \log \left\lfloor t \right\rfloor + O(\left\lfloor t \right\rfloor) = \left\lfloor t \right\rfloor \log \left\lfloor t \right\rfloor + O(t), where the last step is a consequence of the relation \left\lfloor t \right\rfloor \leq t. We can rewrite the resulting expression as t \log t + O(t) + (\left\lfloor t \right\rfloor \log \left\lfloor t \right\rfloor - t \log t); the function in parentheses is always less in absolute value than (t + 1) \log (t + 1) - t \log t, but since t \geq 1 the previous expression is in turn less than or equal to (t + 1) \log 2t - t \log t = (t + 1) (\log 2 + \log t) - t \log t = t \log 2 + \log 2 + \log t = O(t); so we can conclude that \overline{C}(t) = t \log t + O(t) + O(t) = t \log t + O(t) (in the last step we applied the Corollary of Property A.9). Substituting, we’ll have:
where in steps (a) and (b) we applied the Corollary 1 of Property A.8, while in step (c) we applied the Property A.17.
To sum up, since the equalities started from \sum_{n \leq x} \frac{d(n)}{n}, we have that \sum_{n \leq x} \frac{d(n)}{n} \gg \log^2 x.