slides (PowerPoint)
Download
Report
Transcript slides (PowerPoint)
“On the Number of Primes Less
Than a Given Magnitude”
Eric Barkan
[email protected]
Bruce Cohen
Lowell High School, SFUSD
[email protected]
http://www.cgl.ucsf.edu/home/bic
David Sklar
San Francisco State University
[email protected]
Asilomar - December 2009
Ver. 20.00
Worksheet
0 if x 0
(d) u x is a unit step function , u x
. Sketch a graph of u x 9 .
1
if
x
0
x
J x
x
u x
Worksheet
-1 1 -1 0
0
1
-1
0
-1
1
1
Worksheet
and a 0,
a
x
dx lim
s 1
b
b a
xs
s 1
x dx lim
b s
b
a
b s a s
as
as
lim
0
b s
s
s
s
x
1
x
lim 1 lim
x
x 1
x log x
x
log x as x lim
b Li x
x
2
1
dt
log t
1
1
dt
Li x
dx 2 log t
1
log x
lim
lim
1
lim
lim
x
x d
x
x
x
1
x
1
1 1
1
x
log x
log x
log x
dx log x
log x 2 x
d
c
1
2 t dt as x
x
x
Hence Li x
x
log x
Riemann and Prime Numbers
Georg Friedrich Bernhard Riemann (18261866) was one of the greatest mathematicians of
the 19th century. Most of his work concerns
analysis and its developments, but in 1859 he
published his only paper on number theory. It
was entitled “Über die Anzahl der Primzahlen
unter einer gegebenen Grösse” (On the Number
of Primes less than a given Magnitude). In this
eight page paper, he obtained a formula for the
function (x) (the number of primes less than or
equal to x).
The methods he introduced became the
foundation of modern analytic number theory.
This presentation is an attempt to provide a
comprehensible overview of the essential
content of Riemann’s paper.
What Are Prime Numbers and Why Do We Care About Them?
Answer: A Prime number is an integer greater than 1 whose only divisors are
1 and itself. (Note: 1 is not prime.)
The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... , 91, 97, 101
Answer: Primes are important because they may be viewed as the multiplicative
“building blocks” of the natural numbers. This idea is embodied in
The Fundamental Theorem of Arithmetic:
Every integer greater than one can be written as a product of prime numbers
in one and only one way (aside from a reordering of the factors).
2
Example: 60 4 15 2 2 3 5 2 3 5
60 3 20 3 4 5 3 2 2 5 2 2 3 5
An important function describing the distribution of primes among the natural
numbers is
x the number of primes less than or equal to x
Note: this is a step function whose value is zero for real x less than 2
and jumps up by one at each prime.
1 0, 2 1, 2.5 1, 3 2, 4 2, 5 3, 6 3,
Analytic Number Theory
Analysis: The theory of functions of a real or complex variable, especially using
methods of the calculus and its generalizations
Analytic Number Theory: The study of the integers using the methods of analysis
f ( x)
1.
Notation:
x g ( x )
If f ( x) g ( x) we say that f (x) is asymptotically equal to g(x) or simply
that f (x) is asymptotic to g(x).
f ( x)
g ( x) means lim
A central result of analytic number theory concerns the distribution of primes.
Specifically it concerns smooth approximations to (x) for large x.
The Prime Number Theorem:
x
Li( x)
x
log x
, where Li x
x
2
dt
log t
(Note: The theorem was conjectured by Gauss in 1796 and proved in 1896 using
methods that were introduced by Riemann 1859.)
( x)
Li( x )
x
log x
Prime Numbers and the Zeta Function
One of the most important objects in analytic number theory is the zeta function,
usually denoted by z (s). This notation is due to Riemann, but the function was
first studied by Euler in the 1730’s. The most basic definition for this function,
and the one first considered by Euler, is in terms of an infinite series:
1
For s 1, z ( s ) s
n 1 n
Example: z (2)
1
1 1
1
2
2
2
2 3
n 1 n
Note that here the independent variable s appears as the exponent of each term.
This is in contrast to the situation in Taylor series, in which the independent
n
variable is the base in each term an s .
The importance of the zeta function in the theory of prime numbers is due to a
remarkable alternative representation of z (s) discovered by Euler in 1737. This
new version, known today as Euler’s product, takes the form of an infinite
product over the prime numbers p:
z ( s)
1
s
n 1 n
p
1
1
1
ps
1
1
1
1
1
1
1
1
1
1
1
1
2s
3s
5s
7s
A Brief Outline of Riemann’s Paper
I. He begins with Euler's product representation for z(s) (the zeta function). He
points out that the sum and product define the same function of a complex
variable s where they converge, but “They converge only when the real part
of s is greater than 1”.
II. Then, with the phrase “however, it is easy to find an expression of the function
which is always valid” he sketches a theory of the zeta function in which he:
A. Extends the domain of z to include all complex numbers s except s 1
B. Shows that the extended z (s) has zeros ( all with Re s 1 )
C. Proves, states and conjectures certain results about these zeros
(including the Riemann Hypothesis)
D. Obtains a product representation of z in terms of its zeros
III. He obtains log z(s) as an integral involving a step function J(x) that jumps at
prime powers
IV. Uses Fourier inversion to express J(x) as an integral involving log z(s)
V. Evaluates the integral to obtain a formula for J(x)
VI. Uses Möbius inversion to obtain a formula for (x) in terms of J(x)
VII. Proposes an improved approximation to (x) in terms of Li(x)
A Ramble Through of Riemann’s Paper
(V
VI
III
IV
I
II
V
VI
VII ? )
Riemann’s main formula is an expression for J (x) a step function that jumps
only at prime powers. The height of the jump at pn is 1/n .
J ( x) Li( x)
x
Li x
dt
log
2
Li
x
t (t 2 1) log t
( first movie )
, a sum over the “mysterious” zeros of zeta is a sum of “oscillating”
functions (“the music of the primes”), provides the terms that converge to the jumps.
Assuming the Riemann Hypothesis this sum can expressed in terms of the
imaginary parts of the zeros of zeta.
Li x
J ( x) Li( x)
x
x
sin( log x)
2
log x
dt
log
2
Li
x
t (t 2 1) log t
Euler’s Product for z(s)
In 1737 Euler discovered a remarkable product representation for the zeta function.
Specifically, he found (stated in modern terms) for s 1
z (s)
n 1
1
ns
p
1
1
1
ps
, where p ranges over all primes.
Euler noted that this result implies that there are infinitely many primes.
Consider what happens as s approaches 1 (from the right). This would give
1
n 1 n
p
1
1
1
p
1
1
1
1
1
1
1
1
1
1 1 1
2
3
5
7
Now, the sum on the left is just the harmonic series, which diverges. Hence,
the product on the right must have infinitely many factors (or it would be finite).
But there is exactly one prime for each factor in the product, so there must be
infinitely many primes. This was the first new proof of this fact since Euclid’s
proof, 2000 years earlier.
A Derivation of Euler’s Product for z(s)
1
1
1
1
s
s
s
s
2
3
4
5
1
1
1
1
1
1
z
(
s
)
s
s
s
s
s
s
2
2
4
6
8 10
1
1
1
1
1
1
1
z
(
s
)
1
s
s
s
s
s
s
2
3
5
7
9 11
1
1
1
1
1
1
1
1
z
(
s
)
s
s
s
s
s
s
s
3
2
3
9
15
21
27
1
1
1
1
1
1
1
1
1
z
(
s
)
1
s
s
s
s
s
s
s
3
2
5
7
11
13 17
z ( s) 1
1
2
At the k th step in this process all of the terms with denominators ns, where
the smallest prime factor of n is the k th prime, are subtracted from the sum.
The Fundamental Theorem of Arithmetic implies that every n has a unique
smallest prime factor. Uniqueness implies that no term is subtracted twice,
and existence implies that every term (except 1) is eventually eliminated.
A Derivation of Euler’s Product for z(s)
1
1
1
1
1
1
1
1 s 1 s 1 s z ( s) 1 s s s s
5
3
2
7
11
13
17
1
1
1
1
1
1
1
1
z ( s) 1
s
s
s
s
7
5
3
2
So
1
z (s)
1
1
1
1
1
1
1
1
2s
3s
5s
7s
and
z s
1
s
n 1 n
p prime
1
1
1
ps
3
Riemann’s formula for log z(s) in terms of J(x)
Riemann begins his 1859 paper by deriving a formula for log z ( s) in terms of the
prime-power step-function J ( x). He starts by taking the log of Euler's product:
log z ( s) log
p
1
log 1 s
p
p
1
1
1
ps
Now, recall the Taylor series for log 1 x ,
1 n
log 1 x x
n 1 n
1
Riemann uses this with x s to obtain a series for log 1
p
n
1
ps
in prime powers:
1
1 1
1
1 ns
log 1 s s p p n
p
n 1 n p
n 1 n
n 1 n
s
He substitutes this in the RHS of his result above for log z ( s) and gets
1 n s
log z ( s) p .
p n 1 n
Riemann’s formula for log z(s) in terms of J(x)
At this stage, Riemann has
1 n s
log z ( s) p .
p n 1 n
Next, he notes that each prime power p n occurs exactly once in this double sum,
and also that the prime powers may be placed in a natural order, ie., in order of
increasing numerical value: 21 31 22 51 71 23 32 111
.
These facts allow him to rewrite his double sum as a single sum over prime powers,
1 n s
with terms of the form p , in order of increasing numerical value of p n :
n
log z ( s)
prime powers p n
1 n s
p
n
1 1 s 1 1 s 1 2 s 1 1 s 1 1 s 1 3 s 1 2 s
2 3 2 5 7 2 3
1
1
2
1
1
3
2
Riemann’s formula for log z(s) in terms of J(x)
Riemann now converts his single sum to an integral essentially as follows.
(Actually, we have made the argument slightly more modern, but equivalent,
by use of the unit step function). First, note that for s 1
a
s
x
x s 1dx
s
and therefore
a
as
as
0
s
s
p
n s
so
a s x s 1dx
s
a
s n x s 1dx.
p
Now, if we define u(x), the unit step function, by
0, x 0
u ( x)
1, x 0
u(x)
x
then we may write
p
n s
s u x p n x s 1dx
1
Riemann’s formula for log z(s) in terms of J(x) IV
Using
p
n s
s u x p n x s 1dx
1
We may substitute in Riemann's single sum for log z ( s) which we obtained
earlier, and then exchange order of summation and integration, to get
1 n s
log z ( s) p
pn n
s 1
1
1
n
n
s 1
u x p x dx
n n s 1 u x p x dx s 1
p
pn n
??
J x
J ( x)
1
the number of primes x the number of prime squares x
2
1
the number of prime cubes x
3
1
1
1
u x 21 u x 31 u x 22
1
1
2
1
1
u x pn u x pn
pn x n
pn n
1 2 u x 22
u x 3
u x 2
Riemann’s formula for log z(s) in terms of J(x) IV
Using
p
n s
s u x p n x s 1dx
1
We may substitute in Riemann's single sum for log z ( s) which we obtained
earlier, and then exchange order of summation and integration, to get
1 n s
log z ( s) p
pn n
s 1
1
1
n
n
s 1
u x p x dx
n n s 1 u x p x dx s 1
p
pn n
Since the sum in the integrand is the step function J(x) we have arrived at
Riemann’s formula for log z (s) in terms of J(x)
log z (s) s J ( x) x s 1dx
1
Riemann’s Formula for J(x) in terms of log z(s)
Riemann had now obtained a formula for log z(s) in terms of the prime-power step
function J(x):
log z (s) s J ( x) x s 1dx
1
Now, if he could just solve this equation to get J(x) in terms of log z (s) he would
have obtained complete information about prime powers (and thus about primes)
from an expression involving only the smooth function z (s) and some elementary
functions.
He was able to do this by the method of Fourier inversion, yielding
J ( x)
1 a i log z ( s) s
x ds, a Real and 1.
a
i
2 i
s
The integral on the right is a contour integral along a path in the complex plane.
We can’t develop the theories of contour integration and Fourier inversion in this
talk, but the details of these theories will not be needed to understand the essentials
of what follows. What matters is that Riemann was able to evaluate this integral
by using certain special properties of z (s) that he discovered.
Integration Contour for Riemann’s Formula
1 a i log z ( s) s
J ( x)
x ds, a
a
i
2 i
s
and a 1
a i
Im
Re
1
a
a i
Riemann’s Plan to Evaluate His Integral
Riemann now had his integral formula for J(x):
1 a i log z ( s) s
J ( x)
x ds, a Real and 1.
a
i
2 i
s
First, note that the path of integration is not the real line. Thus the integrand must be
evaluated for complex values of s. The original definition of z (s) as an infinite series
would allow a direct evaluation, but is not sufficient to support Riemann’s attack on the
integral. He was able to construct an analytic continuation of z s) which has meaning
throughout the complex plane, except at s = 1.
To actually evaluate the integral, his idea was to write z (s) as a product of simpler
functions. Then log z(s), and the integral, would break up into a sum of terms simple
enough that the individual integrals could be evaluated more easily.
Riemann’s Plan to Evaluate His Integral
Before he could write z (s) as a product, he needed to clean it up a bit. Recall that z (s)
blows up at s = 1. This behavior is a problem if one is to factor a function in the way
Riemann had in mind. In short, he ended up defining a new function x (s) that is well
behaved throughout the complex plane:
x ( s)
s 1
s
2
s
1 z s
2
where refers to the Gamma function. The details of this choice were driven by a
certain symmetry (the “functional equation”) that Riemann had discovered, as well as by
the need for a function well behaved throughout the complex plane.
This function has the further property that its only zeros are the zeros of z (s) that don’t
lie on the real line. These are known as the non-trivial zeros of z (s).
The Zeros of the Zeta Function
For s 1, z s
1
s
n 1 n
p prime
1
1
1
ps
The two specific forms for the zeta function (infinite series and Euler product) are
intrinsically incomplete due to the fact that they are only defined for s > 1. In
fact, both the series and product blow up for s 1 .
This is a problem, because a central property of the zeta function is its set of roots
or “zeros”, ie. values of s where the function value is zero. However, a glance at
either of the two representations reveals that the zeta function is never zero for
s > 1 (every term of the sum and every factor of the product is > 0). Thus the zeta
function has no zeros for s 1 .
Now, Riemann was able to find an analytic continuation of the zeta function to the
entire real line and, in fact, to the entire complex plane, except for the point s 1.
He found that this extended function does have zeros on the negative real axis
(the “trivial” zeros) and in the strip of the complex plane with real part between 0
and 1. It is these latter “non-trivial” zeros which play a major part in the theory.
The Zeta Function in the Complex Plane and The Riemann Hypothesis
Non-Trivial
Im
Zeros
5 32.9
4 30.4
3 25.0
2 21.0
1
14.1
Trivial Zeros
-2
-1
0
1
2
1
The Riemann Hypothesis
All of the non-trivial zeros of the
zeta function have real part 1/2
(ie., they lie on the critical line).
1
2
3
4
5
Region Represented
Extended
by the
Region
Infinite Series
Critical Line
Re( s )
1
2
Re
Riemann’s Plan to Evaluate His Integral
s
1 z s is defined and well behaved
2
throughout the complex plane, Riemann could factor it in terms of its zeros
1 , 2 … (the nontrivial zeros of zeta):
Since x ( s) s 1
s
2
1
s
x ( s ) 1
2 k 1 k
This is directly analogous to factorization of a polynomial ps) in terms of
its roots l1 , l2 , … , ln in the form
n an1 n1
a0
n
n 1
p( s) an s an1s
a1s a0 an s
s
an
an
an s l1 s l2
s ln
an 1 l1
n
n
s
s
ln 1 a0 1
lk
lk
k 1
k 1
n
Riemann’s Plan to Evaluate His Integral
At this point Riemann had written his new function x s) in two ways:
x (s) s 1
s
2
s
1 z s .
2
1
s
x ( s) 1
2
He then used these results to eliminate x s) and to solve for z s):
z (s)
1
s
1
2
s 1
s
2
s
1
2
This is the desired factorization of z s). It yields immediately
log z ( s ) log s 1
s
s
s
log log 1 log 2 log 1
2
2
Evaluation of Riemann’s Integral
So, to evaluate his formula
1 a i log z ( s) s
J ( x)
x ds
a
i
2 i
s
Riemann could substitute
s
s
s
log z ( s) log s 1 log log 1 log 2 log 1
2
2
k 1
k
and evaluate term by term to get
1 a i log( s 1) s
1 a i
J ( x)
x ds
a
i
2 i
s
2 i a i
s
s
log
1
log
a
i
1
2 x s ds
2
x s ds
s
2 i a i
s
1 a i log 2 s
1 a i 1
s
x
ds
log
1
a i s
2 i a i s
2
i
k 1
k
s
x ds.
Evaluation of Riemann’s Integral
Riemann was a master of complex analysis. He was able to evaluate each of
these complex contour integrals with the following results:
1 a i log( s 1) s
x ds Li( x )
a
i
2 i
s
s
log
1 a i 2
log a i s
s
x ds
x ds 0
a
i
a
i
2 i
s
4 i
s
log 1
a
i
1
2 x s ds
2 i a i
s
x
dt
t (t 2 1) log t
log 2 a i x s
1 a i log 2 s
ds log 2
x ds
a
i
a
i
2 i
s
2 i
s
1 a i 1
s s
log
1
x ds
a
i
2 i
s
Li( x )
Riemann’s formula for J(x)
Putting all this together he had
J ( x) Li( x) 0
x
dt
log
2
Li
x
t (t 2 1) log t
Or, rearranging slightly
J ( x) Li( x)
x
dt
log
2
Li
x
t (t 2 1) log t
This is Riemann's formula for J ( x). Note that all the "wiggles" are in the
term Li x . Thus the smooth part of J ( x), which we'll call J s ( x), is
J s ( x) Li( x)
x
dt
log 2
2
t (t 1) log t
Riemann’s Formula’s for J and
J ( x) Li( x)
x
dt
log
2
Li
x
2
t (t 1) log t
J s ( x) Li( x)
x
dt
log 2
2
t (t 1) log t
Riemann pointed out that
J x x 12 x1 2 13 x1 3 14 x1 4 15 x1 5
and used Möbius inversion to obtain
x J x 12 2 J x1 2 13 3 J x1 3 14 4 J x1 4 15 5 J x1 5
x J x 12 J x1 2 13 J x1 3 15 J x1 5 16 J x1 6 17 J x1 7
Riemann then suggested an improved version of the Prime Number Theorem
x
Li( x) 12 Li( x1 2 ) 13 Li( x1 3 ) 15 Li( x1 5 ) 16 Li( x1 6 ) 17 Li( x1 7 )
Bibliography
[1] M. Abramowitz, I. Stegun, Handbook of Mathematical Functions,
Dover, New York, 1965
[2] T. Apostol, Introduction to Analytic Number Theory, Springer-Verlag,
New York, 1976
[3] Brian Conrey, The Riemann Hypothesis, Notices of the AMS, March 2003
[4] H. M. Edwards, Riemann’s Zeta Function, Dover, New York, 2001
(Republication of the 1974 edition from Academic Press)
[5] Andrew Granville, Greg Martin, Prime Number Races, American
Mathematical Monthly, Volume 113, January 2006
[6] Bernhard Riemann, Gesammelte Werke, Teubner, Leipzig, 1892.
(Reprinted by Dover Books, New York, 1953.)
[7] http://www.claymath.org/millennium/
[8] http://en.wikipedia.org/wiki/Prime_number_theorem
[9] http://en.wikipedia.org/wiki/Riemann_zeta_function
END OF MAIN TALK
Oscillations and Li(x)
2 Re Li x
x cos( log x) i sin( log x)
x sin( log x) i cos( log x)
log x
i
log x
J ( x)
x sin( log x)
2
log x
2 Re Li x
k 1
1
i
2
x
x
x
x xi
xei log x
(assuming RH)
log x
log x 1
i log x i log x
i
log
x
2
Li x
k
x sin( k log x)
2
log x k 1
k
x sin( k log x)
dt
Li( x) 2
log 2
2
x
log x k 1
k
t (t 1) log t
Using (x) to Count Prime Powers
2
2
2
2
2
2
2
Example prime squares less than or equal to 225 are 2 3 5 7 11 13 17
primes less than or equal to 225 15 are 2 3 5 7 11 13 17
Hence the number of prime squares 225
225
15 6
More generally, the number of prime squares x x1 2
The same reasoning leads us to the general result,
The number of prime nth powers x x1 n
We can use this result to write J(x) in terms of (x).
J (x) the number of primes x 1/2 the number of prime squares x
1/3 the number of prime cubes x
12
13
14
15
J x x 12 x 13 x 14 x 15 x
Relating (x) and J(x)
12
13 x1 3 14 x1 4 15 x1 5
We have J x x 12 x
Möbius inversion, a technique from elementary number theory, can be used to
write (x) in terms of J(x).
x J x 12 2 J x1 2 13 3 J x1 3 14 4 J x1 4 15 5 J x1 5
where the Möbius
function is defined as
1
n 0
k
1
if n 1
if n is divisible by the square of a prime
if n is the product of k distinct primes
x J x 12 J x1 2 13 J x1 3 15 J x1 5 16 J x1 6 17 J x1 7
1/ n
Note: These sums contain only finitely many terms, they terminate when x 2
since for x 2 J ( x) (x) 0 . Thus the number of terms is log2 x .
Zeta Between 0 and 1
For s 1
1
z ( s) s
n 1 n
( s)
n 1
k 1
1
ns
n 1
1
2k 1
k 1
s
k 1
2k 1
z ( s) ( s)
1
2k
1
s
1
k 1
1
s
2s
k 1 2k 1
s
1
2k
s
1
1
s
k 1 k
l ( s)
1
z ( s)
s
2
l ( s)
1
z (s)
s
2
2
z ( s)
s
2
1
1
z ( s) 1 s 1 ( s) 1 s 1
2
2
1
n 1
1
n 1
ns
The sum on the right converges for 0 s 1 and provides an
analytic continuation of z into the interval between 0 and 1.
Speculations About Riemann’s Motivation
“Music of the Primes”
An example from classical Fourier (harmonic) analysis
Start with a simple staircase function, find a nice smooth approximation,
subtract to get a periodic “sawtooth function”, expand in a Fourier series
x2
x
x x 12
x x 2
sin 2 nx
2 n
n 1
2
sin 2 x
sin 4 x
sin 6 x
2
3
Speculations About Riemann’s Motivation
“Music of the Primes”
In our example from classical Fourier (harmonic) analysis
We started with a simple staircase function, found a nice smooth approximation,
subtracted to get a periodic “sawtooth function”, expanded in a Fourier series
sin 4 x
sin 6 x
sin 2 nx
sin 2 x
2
4
6
2 n
2
n 1
x x 12 2
Note: the sine function plays two roles in this example; it provides the
periodic oscillations, and its zeros provide the frequencies.
By analogy
Start with a step function that describes the distribution of primes, find a nice
smooth approximation, subtract to get an oscillatory “sawtooth function”,
find appropriate oscillatory functions, and a function whose zeros provide
the appropriate frequencies, expand in a Fourier-like series
x
s x
( x) s x
2 Re Li x
k 1
k
2 Re Li x
k 1
1 i
k
2
x
2
log x
k 1
sin( k log x)
k
z
The Gamma Function
z 1 t
t
e dt
, for Re(z) > 0
0
1 1
z 1 z z
( by integration by parts )
( the functional equation for the gamma function )
n 1 n !
z ! z 1
( gamma interpolates the factorial function )
The functional equation provides an analytic continuation for the gamma function
z n z n 1 z n 1 z n 1 z n 2 z 1 z z
z n
z
z z 1 z n 1
z z 1 z n 1
1
z
z n
, for all z except 0, -1, -2, -3, …
1
0,
z
z 0, 1, 2,
Definitions
k 1
n
r _ J ( x) Li( x) Li x k
k 1
dt
log 2
x t (t 2 1) log t
dt
log 2
x t (t 2 1) log t
J ( x) Li( x) Li x k
x J x 12 2 J x1 2 13 3 J x1 3 14 4 J x1 4 15 5 J x1 5
r _ x r _ J x 12 2 r _ x1 2 13 3 r _ J x1 3
Riemann (1859): ( x)
n 1
n 1
( n)
n
Li x
1
n
( n)
n
Li x
1
n
1
log x
1
n 1 kz k 1 k !
arctan
log x
m1 3 r _ J x1 m
1
log x
k
pi _ smooth S x
( n)
n
n 1
Li( x) cpv
,
x
0
Li x
1
n
1
arctan
x dt
dt
1.045...
2
log t
log t
log x
1
log x
log x
1
1
1
arctan
log x log x
n 1 kz k 1 k !
k