In this chapter, we shall set up the basic theory of arithmetic functions. This theory will be seen in action in later chapters, but in particular in chapter 9.
An arithmetical function is a function .
Definition 2.2 (important arithmetical functions):
- The Kronecker delta:
- Euler's totient function:
- Möbius' -function:
- The von Mangoldt function:
- The monomials:
- The number of distinct prime divisors: ,
- The sum of prime factors with multiplicity: ,
- The Liouville function:
- Exercise 2.1.1: Compute , and .
- Exercise 2.1.2: Compute . Hint: .
- Exercise 2.1.3: Compute up to three decimal places. Hint: Use a Taylor expansion.
- Exercise 2.1.4: Prove that for each and .
The convolution and the ring of arithmetic functions[edit | edit source]
Let be arithmetical functions. Then the convolution of and is defined to be the function
In the following theorem, we show that the arithmetical functions form an Abelian monoid, where the monoid operation is given by the convolution. Further, since the sum of two arithmetic functions is again an arithmetic function, the arithmetic functions form a commutative ring. In fact, as we shall also see, they form an integral domain.
Theorem 2.4 (Abelian monoid properties of the arithmetical functions):
- The convolution is commutative, i. e. .
- The convolution is associative, i. e. .
- The function from definition 2.2 is an identity for the convolution, i. e. .
where is a bijection from the set of divisors of to itself.
where the last equality follows from the identity function
being a bijection. But
and hence associativity.
The ring of arithmetic functions is an integral domain.
Let be arithmetic functions, and let be minimal such that , . Then
We shall now determine the units of the ring of arithmetic functions.
Let be an arithmetic function. Then is invertible (with respect to convolution) if and only if .
Assume first . Then for any arithmetic function , .
Assume now . Then , given by the recursive formula
is an inverse (and thus the inverse) of , since and for inductively
- Exercise 2.2.1:
- Exercise 2.2.2:
An arithmetical function is called multiplicative iff it satisfies
- , and
Let be multiplicative arithmetical functions. Then is multiplicative.
Let . Then
since the function is a bijection from the divisors of to the Cartesian product of the divisors of and the divisors of ; this is because multiplication is the inverse:
- , .
To rigorously prove this actually is an exercise in itself. But due to the multiplicativity of and ,
Since is multiplicative, we conclude that the multiplicative functions form an Abelian submonoid of the arithmetic functions with convolution. Unfortunately, we do not have a subring since the sum of two multiplicative functions is never multiplicative (look at ).
Let be a multiplicative function such that converges absolutely. Then
Proof: Let be the ordered sequence of all prime numbers. For all we have
due to the multiplicativity of . For each , we successively take , ..., and then . It follows from the definitions and the rule that the right hand side converges to
We claim that
Indeed, choose such that
Then by the fundamental theorem of arithmetic, there exists an and such that
Then we have by the triangle inequality for , and arbitrary that
From this easily follows the claim.
It is left to show that the product on the left is independent of the order of multiplication. But this is clear since if the sequence is enumerated differently, the argument works in just the same way and the left hand side remains the same.
An arithmetical function is called strongly multiplicative iff it satisfies
- , and
Equivalently, a strongly multiplicative function is a monoid homomorphism .
Let be a strongly multiplicative function such that converges absolutely. Then
Due to theorem 2.9, we have
Due to strong multiplicativity and the geometric series, the latter expression equals
- Exercise 2.3.1: Let be an arithmetic function such that for all , and let . Prove that the function is multiplicative.
Let be an arithmetic function. Then for a prime the Bell series modulo is the formal power series
We shall here compute the Bell series for some important arithmetic functions.
We note that in general for a completely multiplicative function , we have
In particular, in this case the Bell series defines a function.
1. The Kronecker delta:
2. Euler' totient function (we use lemma 9.?):
3. The Möbius function:
4. The von Mangoldt function:
5. The monomials:
6. The number of distinct prime divisors:
7. The number of prime divisors including multiplicity:
8. The Liouville function:
Theorem 2.14 (compatibility of Bell series and convolution):
Let arithmetic functions, and be a prime. Then
In case of multiplicativity, we have the following theorem:
Theorem 2.15 (Uniqueness theorem):
Let be multiplicative functions. Then
Proof: is pretty obvious; : as formal power series is equivalent to saying . If now , then
due to the multiplicativity of and .
In chapter 9, we will use Bell series to obtain equations for number-theoretic functions.
Let be an arithmetic function. Then the derivative of is defined to be the function
Theorem 2.17 (rules for the derivative):
Let arithmetic functions. We have the following rules:
- if invertible, i.e.
Note that is not the inverse function of (this wouldn't make much sense anyway since arithmetic can not be surjective, since is uncountable), but rather the convolution inverse.
1. is easily checked.
We have and . Hence, by 2.
Convolving with and using yields the desired formula.
Note that a chain rule wouldn't make much sense, since arithmetic may map anywhere but to and thus doesn't make a lot of sense in general.