MAT 338 Day 36 2011

2338 days ago by kcrisman

Recall that last time we were finishing up discussing long-term average values of certain arithmetic functions.  We had that 

  • The average value of $\tau(n)$ was $\ln(n)+2\gamma-1$.
  • The average value of $\sigma(n)$ was $\left(\frac{1}{2}\sum_{d=1}^\infty \frac{1}{d^2}\right)\; n$.

Because of Euler's amazing solution to the Basel problem, we know that $$\sum_{d=1}^\infty \frac{1}{d^2}=\frac{\pi^2}{6}$$ so the constant in question is $\frac{\pi^2}{12}$.   

We will discuss this computation again soon, when we return to the connection between number theory and such abstract series.

We ended with the question of yet another average value - that of the $\phi$ function.  You can try out various ideas below.  However, we aren't ready to prove anything about that quite yet.

def L(n): ls = [] out = 0 for i in range(1,n+1): out += euler_phi(i) ls.append((i,out/i)) return ls P = line(L(100)) 
@interact def _(a=.01,n=2): show(P+plot(a*x^n,0,100,color='black',linestyle="--")) html("Blue is the average value of $\phi$$") html("Red is $%s x^{%s}$"%(latex(a),n)) 

Click to the left again to hide and once more to show the dynamic interactive window

For now, we will be content to finally start to think about the most mysterious of all such functions.  This is the prime counting function $\pi(x)$ or $\Pi(x)$, defined as $$\pi(x)=\#\{p\leq x\mid p\text{ is prime }\}\, .$$  

We can find a very rudimentary bound on this function (a slight modification of something in Jones and Jones).

Fact:  There are at least $$\frac{\ln(\ln(x)/\ln(2))}{\ln(2)}+1$$ primes less than or equal to $x$.


  • Recall Saidak's proof of the infinitude of the primes. 
  • To be precise, in the proof he shows that in the sequence $2,(2+1),(2(2+1)+1),\ldots$ there is at least one new prime divisor in each element of the sequence.
  • So the $n$th prime can be no bigger than the $n$th element of this sequence.
  • By induction, we see that this element is less than $2^{2^{n-1}}$.
    • The case $n=1$ is clear.
    • The $n$th element is the previous elements multiplied together, plus 1, which is less than $$2^{2^0}2^{2^1}\cdots 2^{2^{n-2}}+1=2^{1+2+4+\cdots +2^{n-2}}+1=2^{2^{n-1}-1}+1\leq 2^{2^{n-1}}$$ (which uses our information from very early on about adding such numbers!).
  • So the number of primes less than $2^{2^{n-1}}$ can't be less than $n$.
  • Take two logs of this to get $$\ln(\ln(x))=\ln\left(2^{n-1}\right)+\ln(\ln(2))=(n-1)\ln(2)+\ln(\ln(2))$$
  • This simplifies to the given statement.

As you can see below, this is not a very useful bound, considering there are actually 25 primes less than 100, not 3!


There are exact formulas for this function, believe it or not.  The following formula is one of my favorites $$\pi(n)=-1+\sum_{j=3}^{n}\left((j-2)!-j\left\lfloor\frac{(j-2)!}{j}\right\rfloor\right)\, .$$  Can you see why this is not useful in practice?

def primeish(n): if n==1: return 0 elif n==2: return 1 elif n==3: return 2 else: result = -1 fact = 1 for j in range(3,n+1): fact = fact*(j-2) t = fact/j result += (fact - j*floor(fact/j)) return result 

But it works!


Somewhat remarkably, the first people we know of compiling substantial data about this are Gauss and Legendre.  See the handout.

  • Legendre tries to estimate that $\pi(x)\approx \frac{x}{\ln(x)-A}$, where he fudges the constant $A\approx 1.08366$.
    • In fact, he says something more precise - that $\pi(x)$ is asymptotic to this function.  That is, he suggested that $$\lim_{x\to\infty}\frac{\pi(x)}{x/(\ln(x)-A)}=1$$
    • Another way to think of this is that the average chance of a number of size $x$ being prime is about $\frac{1}{\ln(x)-A}$. 
  • Naturally, Gauss came up with a solution that was both more elegant and correct.  And he didn't tell anyone for over fifty years!
    • Gauss' conjecture was that $$\lim_{x\to\infty}\frac{\pi(x)}{x/\ln(x)}=1$$ - that $\pi(x)$ is asymptotic to $\frac{x}{\ln(x)}$.
    • So, roughly $1/\ln(x)$ integers near $x$ would be prime.
  • In fact, Gauss makes this more precise.  
    • If the probability density function is that $1/\ln(x)$ integers near $x$ are prime, then we should do as we always do with such functions, and integrate the function to get the cumulative amount!
    • That is, we should expect that $\pi(x)\approx \int_0^x\frac{dt}{\ln(t)}$.
    • Or, that $$\lim_{x\to\infty}\pi(x)/\int_0^x\frac{dt}{\ln(t)}=1\; .$$

This should sound 100% crazy!  But Gauss and Legendre were no fools, and the accuracy is astounding.  Let's call $Li(x)=\int_0^\infty \frac{dt}{\ln(t)}$ (yes, this is a convergent integral).

@interact def _(n=100): show(plot(prime_pi,3,n,color='black',legend_label='$\pi(x)$')+plot(x/ln(x),3,n,color='red',legend_label='$x/\ln(x)$')+plot(Li,3,n,color='green',legend_label='$Li(x)$')) 

Click to the left again to hide and once more to show the dynamic interactive window

Notice how much closer $Li(x)$ is than the $x/\ln(x)$ estimate.  It's usually closer by several orders of magnitude.

@interact def _(n=[100,1000,1000000,1000000000]): P = prime_pi(n) html("$\pi(%s)=%s$"%(n,prime_pi(n))) html("The error with $%s/\ln(%s)$ is $\\approx %s$"%(n,n,P-(n/ln(n)).n())) html("The error with $Li(%s)$ is $\\approx %s$"%(n,P-Li(n))) 

Click to the left again to hide and once more to show the dynamic interactive window

We'll pick up where this story left off next time!  There is a lot more exciting action coming.


  1. Show that $\sigma(n)$ is $O(n^2)$ (compare to the sum of all integers).
  2. Use the formula for the sum of the first $n$ perfect squares (from Transitions/Discrete or Calculus; it was probably in both for you) and the previous exercise to show that the average value of $\sigma(n)$ is Big Oh of $n^2$.  (This can be loosey-goosey.)
  3. Find a formula for the average value of the $u$ and $N$ functions we discussed earlier (up through $n$).
  4. Finish the details of the proof that $\tau$ is $O(\sqrt[3]{x})$
  5. Show that $\tau(n)$ is not $O(1)$.  (Hint: that means there is no constant $C$ such that $\tau(n)\leq C$ always.)
  6. Why would it not contradict our theorem above that $\frac{1}{n}\sum_{k=1}^n\tau(k)=O(\ln(n))$ to say that $\tau(n)$ is not $O(\ln(n))$?
  7. Show that $\tau(n)$ is not $O(\ln(n))$.  (Hint: look at numbers of the form $6^k$, and compare $\tau$ of these to any given multiple of the natural logarithm using calculus.)
  8. Find absolute bounds for $\phi(n)$ (simple polynomial or log formulas in terms of $n$).