O and o Functions

Date: 01/08/99 at 06:06:24
From: Michael Kuhn
Subject: Twin-Prime Theorem

I'm a German high school student doing research on primes and twin 
primes. One part of my research is the proof of a theorem that shows 
you how many twin primes exist below n. I found the theorem at Eric 
Weisstein's CRC Concise Encyclopedia of Mathematics:

   http://mathworld.wolfram.com/TwinPrimes.html   

Unfortunately, this site is not always available, so I'm going to do 
my best to describe what Weisstein is saying. Let pi_2(x) be the 
number of twin primes p and p+2 that are less than x. (Note the "_" 
means "subscript.") It's been shown that 

                          x             ln ln x
   pi_2(x) <= c * pi_2 -------- [ 1 + O(-------) ]
                       (ln x)^2          ln x
 
where pi_2 is the twin primes constant, and c is another constant. The 
O is the capital letter O and is some kind of a function. My problem 
is, I couldn't find out what this big O notation means.

Can you please explain it to me? Thank you very much!

Yours sincerely,
Michael Kuhn

Date: 01/08/99 at 09:47:07
From: Doctor Rob
Subject: Re: Twin-Prime Theorem

Thanks for writing to Ask Dr. Math!

f(n) = O(g(n)) means that there exists some C independent of n and
some N > 0 such that |f(n)| <= C*g(n) for all n > N.

Another way of saying this is that:

   lim sup |f(n)|/g(n) < infinity
        n

It means that the rate of growth of f(n) is no more than a constant 
times the rate of growth of g(n).

Example:  5*n^3 + 17*n + 1000 = O(n^3), with C = 6 and N = 10.

You may also encounter o(f(n)). f(n) = o(g(n)) means that:

       lim    f(n)/g(n) = 0.
   n->infinity

Example:  987*ln(n) = o(n).

It means that the rate of growth of f(n) is strictly less than any 
constant times the rate of growth of g(n).

Notice that there is an important difference between O and o in
this context!

There is a clearer way to express the pi_2(x) function, as a constant 
times an integral:

   pi_2(x) =~ 1.320323632 int[dx/(ln x)^2] from 2 to x

(Note that =~ means "approximately equal to.") You can find more 
information on this version at Chris Caldwell's page:

   http://www.utm.edu/research/primes/lists/top20/twin.html   

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/