Description

Probabilistic Number Theory Dr. Jörn Steuding Dedicated to Prof. Jonas Kubilius and the members of his working group at Vilnius University, for their outstanding work in probabilistic number theory and

Information

Category:
## Law

Publish on:

Views: 47 | Pages: 29

Extension: PDF | Download: 0

Share

Transcript

Probabilistic Number Theory Dr. Jörn Steuding Dedicated to Prof. Jonas Kubilius and the members of his working group at Vilnius University, for their outstanding work in probabilistic number theory and their kind hospitality! This is a first introduction to Probabilistic Number Theory, based on a course given at the Johann Wolfgang Goethe-Universität Frankfurt in 00. We focus ourselves to some classical results on the prime divisor counting function ω(n) which were discovered in the first half of the 0th century. Nowadays, these facts are the basics for heuristical arguments on the epected running time of algorithms in cryptography. Furthermore, this gives a first view inside the methods and problems in this modern field of research. Especially the growing interest in probabilistic algorithms, which give with a certain probability the right answer (e.g. probabilistic prime number tests), underlines the power and influence of doing number theory from a probability theoretical point of view. For our studies we require only a small background in elementary number theory as well as in probability theory, and, for the second half additionally, the fundamentals of comple analysis; good recommendations to refresh the knowledge on these topics are [6], [4] and []. We will use the same standard notations as in [30], which is also the main source of this course. I am very grateful to Rasa Šleževičienė for her interest and her several helpful comments, remarks and corrections. Jörn Steuding, Frankfurt 0/30/00. Contents Introduction 3 Densities on the set of positive integers 8 3 Limiting distributions of arithmetic functions 5 4 Epectation and variance 5 Average order and normal order 5 6 The Turán-Kubilius inequality 3 7 The theorem of Hardy-Ramanujan 37 8 A duality principle 4 9 Dirichlet series and Euler products 44 0 Characteristic functions 50 Mean value theorems 56 Uniform distribution modulo 59 3 The theorem of Erdös-Kac 6 4 A zero-free region for ζ(s) 66 5 The Selberg-Delange method 7 6 The prime number theorem 77 Chapter Introduction Instead of probabilistic number theory one should speak about studying arithmetic functions with probabilistic methods. First approaches in this direction date back to Gauss, who used in 79 probabilistic arguments for his speculations on the number of products consisting of eactly k distinct prime factors below a given bound; the case k = led to the prime number theorem (see [0], vol.0, p.) - we shall return to this question in Chapter 6; Cesaro, who observed in 88 that the probability that two randomly chosen integers are coprime is 6 (see []) - we will prove this result in Chapter 4. π In number theory one is interested in the value distribution of arithmetic functions f : N C (i.e. comple-valued sequences). An arithmetic function f is said to be additive if f(m n) =f(m)+f(n) for gcd(m, n) =, and f is called multiplicative if f(m n) =f(m) f(n) for gcd(m, n) =; f is completely additive- andcompletely multiplicative, resp., when the condition of coprimality can be removed (the symbol gcd(m, n) stands, as usual, for the greatest common divisor of the integers m and n). Obviously, the values of additive or multiplicative functions are determined by the values on the prime powers, or even on the primes when the function in question is completely additive or completely multiplicative. But prime number distribution is a difficult task. We shall give two important eamples. Let the prime divisor counting functions ω(n) andω(n) of a positive integer n (with and without multiplicities, resp.) 3 be defined by ω(n) = and Ω(n) = ν(n; p), p n p n resp., where ν(n; p) is the eponent of the prime p in the unique prime factorization of n: n = p ν(n;p) ; p here and in the sequel p denotes always a prime number (we recall that p n means that the prime p divides the integer n, and when this notation occurs under a product or a sum, then the product or the summation is taken over all p which divide n). Obviously, n is a prime number if and only if Ω(n) =. Therefore, the distribution of prime numbers is hidden in the values of Ω(n). We note Lemma. ω(n) is an additive, and Ω(n) is a completely additive arithmetic function. Eercise. (i) Prove the lemma above. (ii) Give eamples of multiplicative and completely multiplicative arithmetic functions. When we investigate arithmetic functions we should not epect eact formulas. Usually, the values f(n) are spread too widely. For eample, Euler s totient ϕ(n) counts the number of prime residue classes mod n: ϕ(n) := { a n :gcd(a, n) =}. It was proved by Schinzel [6] that the values ϕ(n+),n N, lie everywhere dense ϕ(n) on the positive real ais. Further, it is easy to see that (.) lim inf n ϕ(n) n = 0 and lim sup n ϕ(n) n =. Eercise. (i) Prove the identity ϕ(n) =n ( ). p p n In particular, ϕ(n) is multiplicative. (Hint: remind that am + bn runs through a complete residue system modmn when a and b run through complete residue systems mod n and mod m, resp., if m and n are coprime; see for this and for some basics on congruences and residues [4], V.) 4 (ii) Prove formulae (.). (Hint: make use of formula (.3) below.) (iii) Try to find lower and upper bounds for ω(n) and Ω(n). In our studies on the value distribution of arithmetic functions we are restricted to asymptotic formulas. Hence, we need a notion to deal with error terms. We write f() =O(g()) and f() g(), resp., when there eists a positive function g() such that lim sup f() g() eists. Then the function f() grows not faster than g() (up to a multiplicative constant), and, hopefully, the growth of the function g() is easier to understand than the one of f(), as. This is not only a convenient notation due to Landau and Vinogradov, but, in the sense of developping the right language, an important contribution to mathematics as well. We illustrate this with an easy eample. What is the order of growth of the truncated (divergent) harmonic series n as? Obviously, for n, n n dt n t n. Denote by [] the maimum over all integers, then, by summation over n [], [] n= [] n Therefore integration yields (.) n n = dt + O() = log + O(); t here and in the sequel log denotes always the natural logarithm, i.e. the logarithm to the base e = ep(). We learned above an important trick which we will use in the following several times: the sum over a sufficiently smooth function can be considered - up to a certain error - as a Riemann sum and its integral, resp., which is hopefully calculable. 5 n, dt t [] n= n. Eercise.3 Prove for that (i) the number of squares n is + O(); (ii) log ε for any ε 0; (iii) m ep() for any m 0; (iv) n n = + O(). We return to number theory. In 97 Hardy and Ramanujan [3] discovered the first deep result on the prime divisor counting function, namely that for fied δ (0, )andn 3 (.3) N {n N : ω(n) log log n (log log n) +δ } (log log N) δ. Since the right hand side above tends to zero, as N,thevaluesofω(n) with n N are concentrated around log log n (the set of integers n, forwhichω(n) deviates from log log n, has zero density, in the language of densities; see Chapter ). For eample, a 50-digit number has on average only about 5 distinct prime divisors! Moreover, Hardy and Ramanujan proved with similar arguments the corresponding result for Ω(n). Unfortunately, their approach is complicated and not etendable to other functions. In 934 Turán [3] found a new proof based on the estimate (.4) (ω(n) log log n) N log log N, n N and an argument similar to Čebyšev s proof of the law of large numbers in probability theory (which was unknown to the young Turán). His approach allows generalizations (and we will deduce the Hardy-Ramanujan result (.3) as an immediate consequence of a much more general result which holds for a large class of additive functions, namely the Turán-Kubilius inequality; see Chapter 6). The effect of Turán s paper was epoch-making. His ideas were the starting point for the development of probabilistic number theory in the following years. To give finally a first glance on the influence of probabilistic methods on number theory we mention one of its highlights, discovered by Erdös and Kac [7] in 939, namely that ω(n) satisfies (after a certain normalization) the Gaussian error law: { } lim N N ω(n) log log N n N : = ( ep τ ) (.5) dτ. log log N π 6 Therefore, the values ω(n) are asymptotically normally distributed with epectation log log n and standard deviation log log n (this goes much beyond (.3); we will prove a stronger version of (.5) in Chapter 3). This classical result has some important implications to cryptography. For an analysis of the epected running time of many modern primality tests and factorization tests one needs heuristical arguments on the distribution of prime numbers and so-called smooth numbers, i.e. numbers which have only small prime divisors (see [7], ). For a deeper and more detailed history of probabilistic number theory read the highly recommendable introductions of [6] and [8]. 7 Chapter Densities on the set of positive integers It is no wonder that probabilistic number theory has its roots in the 930s. Only in 933 Kolmogorov gave the first widely accepted aiomization of probability theory. We recall these basics. A probability space is a triple (Ω, B, P) consisting of the sure event Ω (a non-empty set), a σ-algebra B (i.e. a system of subsets of Ω, for eample, the power set of Ω), and a probability measure P, i.e. a function P : B [0, ] satisfying P(Ω) =, P(A) 0 for all A B, P ( n= A n )= n= P(A n ) for all pairwise disjoint A n B. Then, P(A) istheprobability of A B. We say that two events A, B Bare independent if P(A B) =P(A) P(B). Based on Kolmogorov s aioms one can start to define random variables, their epectations and much more to build up the powerful theory of probability (see [6] for more details). But our aim is different. We are interested to obtain knowledge on the value distribution of arithmetic functions. The first idea is to define a probability law on the set of positive integers. However, we are restricted to be very careful as the following statement shows: by intuition we epect that the probability, thata randomly chosen integer is even, equals, but: 8 Theorem. There eists no probability law on N such that (.) P(aN) = a (a N), where an := {n N : n 0mod a}. Proof via contradiction. By the Chinese remainder theorem (see [4], VIII.), one has for coprime integers a, b an bn = abn. Now assume additionally that P is a probability measure on N satisfying (.), then P(aN bn) =P(abN) = ab = P(aN) P(bN). Thus, the events an and bn, and their complements resp., are independent. Furthermore N a := N \ an and N b := N \ bn, P(N a N b )=( P(aN))( P(bN)) = By induction, we obtain for arbitrary integers m P({m}) P N p = ( ) (.) ; p m p m p ( )( ). a b here the inequality is caused by m N p for all p m). In view to the unique prime factorization of the integers and (.) we get (+ p + p ) +... =log + O(). p n n Hence, by the geometric series epansion, ( ) (.3) p log + O(). p This leads with in formula (.) to P({m}) = 0, giving the contradiction. In spite of that we may define a probability law on N as follows. Assume that λ n = with 0 λ n, n= 9 then we set for any sequence A N P(A) = n A λ n. Obviously, this defines a probability measure. Unfortunately, the probability of a sequence depends drastically on its initial values (since for any ε 0 there eists N N such that P({,,...,N}) ε). To construct a model which fits more to our intuition we need the notion of density. Introducing a divergent series λ n = with λ n 0, n= we define the density d(a) of a sequence A of positive integers to be the limit (when it eists) (.4) n ;n A λ n d(a) = lim. n λ n This yields not a measure on N (since sequences do not form a σ-algebra, and densities are not subadditive). Nevertheless, the concept of density allows us to build up a model which matches to our intuition. Putting λ n = in (.4), we obtain the natural density (when it eists) da = lim {n : n A}; moreover, the lower and upper natural density are given by da = lim inf {n : n A} and da = lim sup {n : n A}, respectively. We give some eamples. Any arithmetic progression n b mod a has the natural density ([ ] ) lim + O() = a a, corresponding to our intuition. Eercise. Show that (i) the sequence a a ... has natural density α [0, ] if, and only if, lim n n a n = α; (Hint: for the implication of necessity note that n = {j : a j a n }.) 0 (ii) the sequence A of positive integers n with leading digit in the decimal epansion has no natural density, since da = 9 5 9 = da. We note the following important(!) connection between natural density and probability theory: if ν N denotes the probability law of the uniform distribution with weight on {,,...,N}, i.e. N ν N A = { if n N, λ n with λ n = N 0 if n n, n A then (when the limit eists) lim ν NA = lim {n N : n A}= da. N N N Therefore, the natural density of a sequence is the limit of its frequency in the first N positive integers, as N. Setting λ n = in (.4), we obtain the logarithmic density n δa := lim log n n A n ; the lower and upper logarithmic density are given by δa = lim inf log n n A n and δa = lim sup log n n A n, respectively; note that the occuring log comes from (.). Eercise. Construct a sequence which has no logarithmic density. The following theorem gives a hint for the solution of the eercise above. Theorem. For any sequence A N, da δa δa da. In particular, a sequence with a natural density has a logarithmic density as well, and both densities are equal. Before we give the proof we recall a convenient technique in number theory. Lemma.3 (Abel s partial summation) Let λ λ ... be a divergent sequence of real numbers, define for α n C the function A() = λ n α n, and let f() be a comple-valued, continuous differentiable function for λ. Then λ n α n f(λ n )=A()f() λ A(u)f (u) du. For those who are familiar with the Riemann-Stieltjes integral there is nearly nothing to show. Nevertheless, Proof. We have A()f() α n f(λ n )= α n (f() f(λ n )) = λ n λ n λ n λ n α n f (u)du. Since λ λ n u, changing integration and summation yields the assertion. Proof of Theorem.. Defining A() = n,n A, partial summation yields, for, (.5) L() := n n A n = A() + A(t) dt t For any ε 0eistsat 0 such that, for all t t 0, da ε A(t) da + ε. t Thus, for t 0, and A(t) t (da ε)(log log t 0 )=(da ε) t 0 dt t0 In view to (.5) we obtain ( (da ε) log t ) 0 log dt t +(da + ε) t 0 dt t dt t A(t) t dt, =(da + ε)(log log t 0 )+logt 0. L() log A() ( (da + ε) log t ) 0 + log t 0 log log log. Taking lim inf and lim sup, as, and sending then ε 0, the assertion of the theorem follows. Eercise.3 Show that the eistence of the logarithmic density does not imply the eistence of natural density. (Hint: have a look on the sequence A in Eercise..) Taking λ n = λ n (σ) =n σ in (.4), we define the analytic density of a sequence A N by the limit (when it eists) (.6) lim σ + ζ(σ) n A n σ, where ζ(s) := n= n = ( p ) (.7) s p s is the famous Riemann zeta-function; obviously the series converges for s (resp., from the comple point of view, in the half plane Re s ). Note that the equality between the infinite series and the infinite product is a consequence of the unique prime factorization in Z (for more details see [30], II.). By partial summation it turns out that one may replace the reciprocal of ζ(σ) in (.6) by the factor σ. We leave this training on the use of Lemma.3 to the interested reader. Eercise.4 Write s = σ + it with i := and σ, t R. Prove for σ 0 ζ(s) = s s s [] d. s+ In particular, ζ(s) has an analytic continuation to the half plane σ 0 ecept for a simple pole at s =with residue. (Hint: partial summation with N n M n s ; the statement about the analytic continuation requires some fundamentals from the theory of functions.) The analytic and arithmetic properties of ζ(s) make the analytic density very useful for a plenty of applications. We note Theorem.4 A sequence A of positive integers has analytic density if and only if A has logarithmic density; in this case the two densities are equal. A proof can be found in [30], III.. We conclude with a further density, which differs from the above given eamples, but is very useful in questions concerning the addition of sequences of positive integers, defined by A + B := {a + b : a A,b B}. 3 The Schnirelmann density is defined by σ(a) =inf {m n : m A}. n n σ(a) stresses the initial values in the sequence A. For the addition of sequences one has Mann s inequality σ(a + B) min{,σ(a)σ(b)}; the interested reader can find a proof of this result and its implication to problems in additive number theory (for eample, Waring s problem of the representation of posiitve integers as sums of k-th powers, or the famous Goldbach conjecture which asks whether each even positive integer is the sum of two primes or not) in [], I.. As we will see in the sequel, the concept of density makes it possible in our investigations on the value distribution of an arithmetic function to eclude etremal values, and to have a look on its normal behaviour. 4 Chapter 3 Limiting distributions of arithmetic functions We recall from probability theory some basic notions. A random variable on a probability space (Ω, B, P) is a measurable function X defined on Ω. When, for eample, Ω = R, then the function F () :=P(X(ω) (,]) contains a lot of information about the random variable X and its values X(ω),ω Ω. A distribution function is a non-decreasing, right-continuous function F : R [0, ], satisfying F( ) =0 and F(+ ) =. Denote by D(F) andc(f) the set of discontinuity points and continuity points of F, respectively. Obviously, D(F) C(F) =R. Each discontinuity point z has the property F(z + ε) F(z ε) for any ε 0 (the converse is not true). Write D(F) ={z k }, then the function F(z) = (F(z k ) F(z k )) z k z increases eclusively for z = z k, and is constant in any closed interval free of discontinuity points z k (it is a step-function). If D(F) is not empty, then F is up to a multiplicative constant a distribution function; such a distribution function is called atomic. Obviously, the function F F is continuous. A distribution function F is said to be absolutely continuous if there eists a positive, Lebesgue-integrable function h with z F(z) = h(t)dt. 5 Finally, a distribution function F is purely singular iff is continuous with support on a subset N R with Lebesgue measure zero, i.e. df(z) =. We note: N Theorem 3. (Lebesgue) Each distribution function F has a unique representation F = α F + α F + α 3 F 3, where α,α,α 3 are non-negative constants with α + α + α 3 =, and where F is absolutely continuous, F is purely singular and F 3 is atomic. The proof follows from the observations above and the Theorem of Radon- Nikodym; see[30], III. and [6], 8. The net important notion is weak convergence. We say that a sequence {F n } of distribution functions converges weakly to a function F if lim F n(z) =F(z) for all z C(F), n i.e. pointwise convergence on the set of continuity points of the limit. We give an interesting eample from probability theory (without details). Let (X j ) be a sequence of independent and identically distributed random variables with epectation µ and variance σ (0, ). By the central limit theorem (see [6], ), the distribution functions of the sequence of random variables Y n := nσ n X j nµ j= converge weakly to the standard Normal distribution Φ() := ( ep τ ) (3.) dτ π (with epectation 0 and variance ). In particular, we obtain for a sequence of independent random variables X j with P(X j = ) = P(X j =+)= for the random walk {Z n },givenby Z 0 := 0 and Z n+ := Z n + X n (n N), 6 that (3.) ( ) lim P Zn = Φ(). n n The distribution functions of the Z n are atomic whereas their limit is absolutely continuous. Note that one can const

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks