# Arithmetic Functions & Normal Order

Share on

## What Are Arithmetic Functions?

An arithmetic function is any function from the set of natural numbers (whole, non-negative numbers that we use to count) to the set of complex numbers. In other words, it’s a complex-valued function that is defined on the set of natural numbers. In notation, that’s:

f: ℕ → ℂ

Arithmetic functions are mostly theoretical, used to investigate properties of natural numbers. As a general idea, you can think of an arithmetic function as a sequence of real numbers or complex numbers (although, as A.J. Hildebrand points out, looking at the functions in this way isn’t very useful).

## Examples of Arithmetic Functions

Arithmetic functions are primarily used in number theory, where they are sometimes called number-theoretic functions. Their behavior can be strange and difficult to predict, but some of the simpler and well known functions are very useful in number theory.

Two of the most important arithmetic functions are Euler’s totient function and the Möbius function. However, the functions don’t have to have proper names. For example, the following are all arithmetic functions (Wong, n.d.):

• The number of divisors of a certain number n,
• The number of primes less than n,
• The number of ways n can be represented as a sum of two squares.

## Normal Order of an Arithmetic Function

Roughly speaking, an arithmetic function has the normal order F(n) if f(n) is approximately equal to F(n) for almost all values of n.

More precisely ((Hardy & Wright, 1979), the normal order of F(n) is f(n) if, for every positive ε and almost all values of n

Another way to put this (Porubský, 2020): a function f has normal order F if a set of positive integers S exists of asymptotic density 1 such that

## History of Normal Order

The concept was first introduced by Hardy and Ramunujan (1917, as cited in Indlekofer, 2001), where they proved that two arithmetical functions ω and Ω have the normal order “log log n”, where:

• ω(n) = the number of different prime divisors,
• Ω(n) = all prime divisors (counted with multiplicity).

## References

Hardy, G. and Ramanujan, S. The normal number of prime factors of a number n, Quart. Journ. Math.Oxford 40, 76-92 ( 1917).
Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Oxford University Press, p. 356, 1979.
Hildebrand, A. (2005). Introduction to Analytic Number Theory. Math 531 Lecture Notes, Fall 2005. Retrieved December 11, 2019 from:
https://faculty.math.illinois.edu/~hildebr/ant/main1.pdf
Indlekofer, K. Number Theory -Probabilistic, Heuristic, and Computational Approaches.Computers and Mathematics with Applications 43 (2002) 1035-1061.
Iwaniec, H. (2014). Lectures on the Riemann Zeta Function. American Mathematical Society.
Miller, S. & Takloo-Bigash. (2006). An Invitation to Modern Number Theory. Princeton University Press.
Porubský, S. Normal Order. Retrieved 2020/6/3 from Interactive Information Portal for Algorithmic Mathematics, Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic, web-page https://www.cs.cas.cz/portal/AlgoMath/NumberTheory/ArithmeticFunctions/NormalOrder.htm
Schachner, M. Algebraic and Analytic Properties of Arithmetic Functions. Retrieved December 11, 2019 from: http://math.uchicago.edu/~may/REU2018/REUPapers/Schachner.pdf
Wong, R. Average Values of Arithmetic Functions. Retrieved December 11, 2019 from: https://ocw.mit.edu/courses/mathematics/18-104-seminar-in-analysis-applications-to-number-theory-fall-2006/projects/wong.pdf

CITE THIS AS:
Stephanie Glen. "Arithmetic Functions & Normal Order" From CalculusHowTo.com: Calculus for the rest of us! https://www.calculushowto.com/arithmetic-functions/
------------------------------------------------------------------------------

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!