From: Robin Chapman Newsgroups: sci.math Subject: Re: Distribution of primes Date: Thu, 17 Sep 1998 09:45:45 GMT In article <36005dd5.12999374@news.lamar.edu>, cs_guf@sal.lamar.edu.sal.lamar.edu (Greg Falcon) wrote: > I'm sorry if the question I'm posing here is blatantly obvious, but I > have to know. For background: I'm an undergraduate CS student but I > take math courses for electives wherever I can, and I enjoy math > thoroughly, although I don't know near as much as I wish I did. > > Anyway, while mucking around last night, I stumbled across a limit > which struck me as very strange and profound. Let F(x) be the sum of > the natural logarithms of all primes less than or equal to x. By > examination up to 1.5 million, I feel pretty confident about the limit > > lim x->inf { F(x) / x } = 1. > > This knocked me out of my seat. What's up with this? Am I correct > about this limit? If so, who discovered it? Where can I read more > about it? Yes. This is correct, and it is profound and non-obvious. It's related to the celebrated prime number theorem, namely that if pi(x) is the number of primes up to x then pi(x)log x/ x --> 1 as x --> infinity. (I.e., from the PNT you can easily prove your observation and vice versa). The prime number theorem was conjectued by Gauss (on the basis of numerical evidence) and first proved (independently) by Hadamard and de la Valee Possin in 1896. They both used methods from complex variable theory. The sum of the logarithms of the primes (your F(x)) up to x is usually denoted as theta(x). Before PNT was proved Chebyshev proved upper and lower bounds on theta(x)/x. For an illustration I'll show how to prove the upper bound. I claim that theta(x) < x log 4 for all x>0. It suffices to prve this for integer x, so use induction. It's OK for x = 1 and x = 2, so assume it's true for values below x. It's OK for x > 2 unless x is prime; in this case write x = 2r + 1. Consider the binomial coefficient C = (2r+1)!/r!(r+1)!. For primes p with r+1 < p <= 2r+1, p divides (2r+1)! but not r!(r+1)!. Thus all such p divide C and so their product divides C. Hence log C >= the sum of the log p for prime p with r+1 < p <= 2r+1. This sum is theta(2r+1) - theta(r+1). But in the binomial expansion of 2^{2r+1} = (1+1)^{2r+1} the term C appears twice so that C <= 2^{2r}. Hence theta(2r+1) - theta(r+1) <= 2r log 2 = r log 4. By induction theta(r+1) < (r+1)log 4 so that theta(x) = theta(2r+1) < (r+1)log 4 + r log 4 = x log 4. In the late 1940s Erdos and Selberg developed a method of proving PNT, which avoids the use of complex variable theory. Around 1980 Newman found a much simpler complex variable proof. One can find proofs of PNT in the more comprehensive textbooks on elementary number theory and in any text on analytic number theory. I first read about it in Hardy and Wright's An Introduction to the Theory of Numbers (later editions of) which include the Erdos-Selberg method. A short accound of Newman's proof written by Don Zagier appeared in the American Mathematical Monthly in 1996 (to celebrate the result's centenary). Robin Chapman + "They did not have proper Room 811, Laver Building - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum