Arithmetic Function

Euler's totient function from 1 to 1000.^[1]

Arithmetic functions are real- or complex-valued functions defined on the set \(\mathbb{Z^+}\) of positive integers. They describe arithmetic properties of numbers and are widely used in the field of number theory. Arithmetic functions are different from typical functions in that they cannot usually be described by simple formulas, so they are often evaluated in terms of their average or asymptotic behavior.

An example of an arithmetic function is the divisor function \(\tau(n)\), which, for a given positive integer \(n\), returns the number of positive divisors of \(n\). For example, \(12\)'s positive divisors are \(\{1, 2, 3, 4, 6, 12\}\), so \(\tau(12) = 6\). On the other hand, any prime number \(p\) has only two divisors, \(1\) and itself, so \(\tau(p)=2\) for any prime \(p\). Since the number of divisors of a number is dependent on its prime factorization, which is very irregular, the divisor function is more easily analyzed in terms of its average order \(\log n\) and its limit superior \(e^{\gamma} n \log \log n\).

Like the divisor function, many arithmetic functions can't be expressed by simple formulas. Luckily, number theorists are often less interested in the value of an arithmetic function for any particular input than they are in the behavior of that function on average or in the asymptotic limit. This is partially motivated by historical connections to the prime number theorem as well as proving theoretical guarantees for cryptographic applications, which usually rely on very large numbers to provide security. The two main methods of analyzing arithmetic functions are asymptotic analysis and average order analysis.

Asymptotic Limits of Arithmetic Functions

Simply put, the asymptotic limit of an arithmetic function \(f(n)\) is a function \(g(n)\) such that

\[\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1.\]

Intuitively, it is an approximate value of the function for very large inputs. In the case that a function is either too complicated to evaluate directly or the input is too large to compute, the asymptotic analysis provides a way to analyze the essential behavior of the function. The relationship is usually denoted \(f(n) \sim g(n)\).

For example, the partition function \(p(n)\), which counts the number of unique ways of writing an integer \(n\) as a sum of positive integers, is most easily defined by the recurrence relation

\[p(n) = \sum_{k = 1}^n (-1)^{k+1}\left[p\left(n- \frac{k}{2}(3k -1)\right)\ p\left(n- \frac{k}{2}(3k +1)\right)\right],\]

where \(p(n) = 0\) for \(n \le 0\) and \(p(1) = 1\). This is a difficult function to evaluate exactly for large numbers. Luckily, the asymptotic limit is much simpler to analyze. It is

\[f(n) \sim \frac {1}{4n\sqrt3} \exp \left({\pi \sqrt {\frac{2n}{3}}} \right),\]

which implies

\[\log p(n) \sim C \sqrt n,\]

where \(C = \pi \sqrt \frac{2}{3}\). So, for very large numbers, the log of the partition function \(p(n)\) behaves like the square root of \(n\). This is much easier to interpret than the recurrence relation and shows that the partition function grows very, very quickly.

Average Order of Arithmetic Functions

The average order of an arithmetic function \(f(n)\) is a function \(g(n)\) such that

\[\sum_{n \le x} f(n) \sim \sum_{n \le x} g(n)\]

as \(x \to \infty\). \(g(n)\) is conventionally chosen to be a continuous function and monotonic. Intuitively, it takes the same values as \(f(n)\) on average. The average order is not, in general, unique for a given arithmetic function \(f(n)\) and often takes a different form than the asymptotic limit.

For example, Euler's totient function \(\varphi(n)\) counts the number of positive integers less than \(n\) that are relatively prime to \(n\). It is most easily defined by

\[\varphi(n) = n \prod_{p\mid n} \left(1-\frac{1}{p}\right),\]

Euler's totient function from 1 to 1000 with average order in red

where \(p \mid n\) denotes "prime \(p\) divides \(n.\)" Since the primes are irregularly spaced, evaluating this formula exactly for large integers \(n\) requires either testing whether \(n\) is divisible by every prime less than \(n\) (there are a huge number of these, by the prime number theorem) or finding the prime factorization for \(n\), which is very difficult. Since finding the exact value of the totient function is not always necessary, sometimes determining the average behavior will suffice. In the case of the totient function,

\[\sum_{n \le x} \varphi(n) \sim \sum_{n \le x} \frac{6}{\pi^2}n\]

as \(x \to \infty\). Thus, the totient function grows roughly at the same rate as \(n\). Put another way, since \(\frac{6}{\pi^2} \approx 0.6079\), on average an integer is coprime to 61% of the positive integers less than it. Obviously, this rule only holds on average since a prime \(p\) will be coprime to every positive integer less than it (i.e. 100% of positive integers less than it), while primorials will be coprime to much fewer than 61%.

Over the last 400 years, number theorists have studied dozens of different arithmetic functions. Prominent examples include the divisor function \(\tau(n)\), Euler's totient function \(\varphi(n)\), Möbius function \(\mu(n)\), Liouville function \(\lambda(n)\), Dirichlet characters \(\chi(n)\), prime counting function \(\pi(n)\), von Mangoldt function \(\Lambda(n)\), and partition function \(p(n)\).

Most of the important arithmetic functions exhibit convenient behavior under addition or multiplication. This is not too surprising since arithmetic functions describe properties of positive integers \(\mathbb{Z^+}\), which are closed under addition and multiplication. Arithmetic functions that exhibit these properties under addition are known as additive functions, while those under multiplication are known as multiplicative functions.

Additive Functions

An additive function is defined as an arithmetic function \(f(n)\) such that the function of a product of coprime positive integers is the sum of the function on those integers. A completely additive function is an additive function without the restriction that the operands are coprime. Formally, they are defined as follows:

An arithmetic function \(f(n)\) is an additive function if, for coprime \(a\) and \(b\),

\[f(ab) = f(a) + f(b).\]

An arithmetic function \(f(n)\) is a completely additive function if, for all positive integers \(a\) and \(b\),

\[f(ab) = f(a) + f(b).\]

Multiplicative Functions

A multiplicative function is defined as an arithmetic function \(f(n)\) such that the function of a product of coprime positive integers is the product of the function on those integers. A completely multiplicative function is an additive function without the restriction that the operands are coprime. Formally, they are defined as follows:

An arithmetic function \(f(n)\) is a multiplicative function if, for coprime \(a\) and \(b\), \(f(1) = 1\) and

\[f(ab) = f(a) \cdot f(b).\]

An arithmetic function \(f(n)\) is a completely multiplicative function if, for all positive integers \(a\) and \(b\), \(f(1) = 1\) and

\[f(ab) = f(a) \cdot f(b).\]

Prime Connection

Because of the coprimality constraint on the definition of additive and multiplicative functions, by the fundamental theorem of arithmetic they are completely determined by their values on prime powers. For example, \(90\)'s prime factorization is \(2^{1} \cdot 3^{2} \cdot 5^{1}\). For an additive function \(f(n)\), \(f(90) = f(2) + f(3^2) + f(5)\).

Given a prime factorization for \(n = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_k^{\alpha_k}\),

an additive function \(f(n)\) has the property

\[f(n) = f(p_1^{\alpha_1}) + f(p_2^{\alpha_2}) + \cdots + f(p_k^{\alpha_k})\]

and a multiplicative function \(f(n)\) has the property

\[f(n) = f(p_1^{\alpha_1}) \cdot f(p_2^{\alpha_2}) \cdots f(p_k^{\alpha_k}).\]

Furthermore, completely additive functions and completely multiplicative functions have no coprimality constraint, so they are completely defined by their values on the prime numbers.

Given a prime factorization for \(n = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_k^{\alpha_k}\),

a completely additive function \(f(n)\) has the property

\[f(n) = \alpha_1 f(p_1) + \alpha_2 f(p_2) + \dots + \alpha_k f(p_k)\]

and a completely multiplicative function \(f(n)\) has the property

\[f(n) = f(p_1)^{\alpha_1} \cdot f(p_2)^{\alpha_2} \cdots f(p_k)^{\alpha_k}.\]

The additive and multiplicative properties of certain arithmetic functions greatly simplify their analysis since they are determined solely by their values at primes and prime powers. The average and asymptotic behavior of prime numbers has been well studied, so additive and multiplicative functions are more easily analyzed than non-additive and non-multiplicative arithmetic functions.

In addition, many series over the natural numbers can be simplified when factored into a product over the primes. One example is the Euler product, which expresses a Dirichlet series as an infinite product over the primes, assuming the series terms have certain multiplicative properties. The Euler product is historically important as it was introduced by Leonhard Euler in his proof of the connection between the Riemann zeta function and the prime numbers.

Furthermore, the values of additive or multiplicative functions can be efficiently calculated in computational number theory using memoization for arguments which are smooth numbers. This is especially useful for functions which might otherwise take linear time in naive implementations, such as Euler's totient function, which is a multiplicative function.

The computational convenience of such functions is central to the development of modern cryptographic methods. Specifically, many cryptographic applications rely on using very large numbers (often in the hundreds of digits) to encode information, and their security often depends on the difficulty of inverting the value of certain number theoretic functions. These functions are often chosen to be multiplicative since this allows fast and memory-efficient computation on very large values, crucial to applications such as network encryption. However, because these functions are easy to compute given the prime factorization of a number, they are also relatively easy to invert given the prime factorization. Luckily, determining the prime factorization of a large number is difficult, so cryptographic methods can utilize the strengths of multiplicative functions without succumbing to their weaknesses.

1. Battiston, P. EulerPhi. Retrieved May 24, 2009, from https://commons.wikimedia.org/wiki/File:EulerPhi.svg