Probabilistic Number Theory
The field of probabilistic number theory has its origins in a famous 1917 paper of Hardy and Ramanujan. In that paper, they studied the “normal order” of the arithmetic function ω(n), defined as the number of distinct prime divisors of n. They showed that
- PDF / 175,273 Bytes
- 5 Pages / 441 x 666 pts Page_size
- 121 Downloads / 239 Views
Probabilistic Number Theory
1 The Normal Order Method In their fundamental paper of 1917, Hardy and Ramanujan [69] introduced the concept of “normal order” of an arithmetical function. To be precise, this means the following. Given an arithmetical function g(n) and an increasing function φ(n), we say that g(n) has normal order φ(n) if for any > 0, the number of n ≤ x such that g(n) − φ(n) > φ(n) (52) is o(x) as x → ∞. In other words, for almost all natural numbers n (in the sense of natural density), we have (1 − )φ(n) < g(n) < (1 + )φ(n). Some arithmetical functions like the divisor function, for example, may not possess a normal order. But other functions like ω(n), defined as the number of distinct prime factors of n, do have a normal order. In fact, the main result of [69] is that the normal order of ω(n) is log log n. The paper of Hardy and Ramanujan laid the foundations of a new subject called probabilistic number theory. Since then, the subject expanded into a major discipline at the hands of P. Erdös, M. Kac, J. Kubilius and P.D.T.A. Elliott, to name a few. In fact, by 1972, the subject became so enormous that Elliott wrote a two-volume treatise explaining the developments since the time of the Hardy–Ramanujan paper. In the recent past, there have been further developments especially to the study of Fourier coefficients of modular forms. We summarize these at the end of this chapter. In their seminal paper, Hardy and Ramanujan make use of Brun’s sieve to prove that ω(n) has normal order log log n. In 1934, Turan [196] showed how one can derive the Hardy–Ramanujan theorem without Brun’s sieve and using what can be viewed as Tchebycheff’s inequality. Apparently, this paper of Turan was part of his doctoral thesis written under the direction of L. Féjer, and it seems that Turan was unaware of Tchebycheff’s inequality or probability theory. As the proof is quite simple, we reproduce it here. M.R. Murty, V.K. Murty, The Mathematical Legacy of Srinivasa Ramanujan, DOI 10.1007/978-81-322-0770-2_11, © Springer India 2013
149
150
11
Probabilistic Number Theory
It is fairly straightforward to show that ω(n) = x log log x + O(x) n≤x
and
ω2 (n) = x(log log x)2 + O(x log log x).
n≤x
Putting these two together, we get 2 ω(n) − log log n = O(x log log x). n≤x
Thus, for any function θ with θ (n) → ∞ as n → ∞, we have the number of n ≤ x for which |ω(n) − log log n| > θ (n)(log log n)1/2 is O(x/θ (x)), which is o(x). One can actually sharpen this and create a sieve method. This was done in [113] and [115] and expanded to a combinatorial setting in [114]. The method therefore has immense potential and applications beyond number theory.
2 The Erdös–Kac Theorem It is interesting that Hardy and Ramanujan chose the word “normal” to describe (52) since, as it transpired later on, there is an intimate connection to the normal distribution in probability theory. To elaborate, let θ (n) be any function tending to infinity as n tends to infinity. Hardy and Ramanujan proved that the number of n ≤ x suc
Data Loading...
