MAT 338 Day 41 2011

3251 days ago by kcrisman

Last time we ended with two new concepts.  

  • One is that of a Dirichlet series, which essentially is a series gotten from an arithmetic function $f(n)$ by making the series $\sum_{n=1}^{\infty}\frac{f(n)}{n^s}=F(s)$.  
  • The other is the idea of an Euler product, which is what you have if you can write such a series as an infinite product over primes $\prod_{p} g(p)$, where usually $g$ somehow looks like an infinite sum itself.  

Our key example was the Riemann zeta function, where we saw that $$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}=\prod_p \left(\frac{1}{1-p^{-s}}\right)\, .$$

We also saw that $$\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s}=\prod_{p}\left(1-\frac{1}{p^s}\right)=\prod_p (1-p^{-s})$$ wherever these make sense. 

What was surprising about this is that the Euler products for the Riemann $\zeta$ function and this function are simply multiplicative inverses, e.g. $$\prod_p \frac{1}{1-p^{-s}}=1/\left(\prod_p 1-p^{-s}\right)\, .$$

sum([moebius(n)/n^2 for n in [1..1000]]).n() 

Recall that $\zeta(2)=\frac{\pi^2}{6}$ (though before we just used this as a sum, and didn't call it $\zeta(2)$.  

(Incidentally, though Euler calculated even values of $\zeta$, it was only in 1978 that $\zeta(3)$ was shown to be irrational, and then named after the man who proved this, Roger Apéry.  To this day, it is only known that at least one of the next four odd values is irrational.)


At least things agree to four digits when we approximate it, so this seems reasonable.

But last time, we said that 

  • Take $f(n)$ and $g(n)$ two arithmetic functions.
  • Let $h=f\star g$ be their Dirichlet product.  
  • Then let $F,G,H$ be the corresponding Dirichlet series (in $s$). 
  • If the series $F$ and $G$ converge absolutely for any $s$ you care about (not necessarily all $s$), then $$H=FG\; .$$

This is really a quite remarkable connection between the discrete/algebraic point of view and the analytic/calculus point of view.


  • Key fact you may or may not have seen in calculus:
    • When series converge absolutely, you can mess around with them a lot with impunity.
  • So we can mess around a lot with the product $$F(s)G(s)=\sum_{n=1}^\infty\frac{f(n)}{n^s}\sum_{m=1}^\infty\frac{g(m)}{m^s}$$ 
  • In particular, we can group the products $\frac{f(n)g(m)}{n^sm^s}$ the same way we did in proving things about $\star$ - we can group by when $n$ and $m$ are complementary divisors of the same number.   This gives $$\sum_{d=1}^\infty\sum_{nm=d}\frac{f(m)g(n)}{d^s}\; .$$
  • But the inner sum is precisely the $\star$ Dirichlet product (well, over $d^s$), so this is the same as $$\sum_{d=1}^\infty \frac{(f\star g)(d)}{d^s}\; .$$
  • The numerators are the definition of $h$, so this is just $H(s)$, as desired.

We can immediately apply this to calculate the Dirichlet series of $\phi$ in terms of the Riemann $\zeta$ function.  We have three facts:

  • $\phi\star u=N$
  • $\zeta$ is absolutely convergent for $s>1$
  • The Dirichlet series of $\phi$ is absolutely convergent as well, as $$0<\sum_{n=1}^\infty \frac{\phi(n)}{n^s}\leq \sum_{n=1}^\infty \frac{n}{n^s}=\sum_{n=1}^\infty\frac{1}{n^{s-1}}$$ which converges by the integral test if $s>2$ (it's also $\zeta(s-1)$).

So the series for $\phi$ (call it $P$) and $u$ multiply to the series for $N$.  But now we have three other facts.

  • The series for $u$ is $\zeta(s)$.
  • The series for $N$ (from last time, or above) is $\zeta(s-1)$.
  • So $P(s)\zeta(s)=\zeta(s-1)$ for $s>2$.

That means $$\sum_{n=1}^\infty \frac{\phi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}\; .$$

sum([euler_phi(n)/n^3 for n in [1..10000]]).n() 

It turns out that such Euler products (and hence nice computations like this) show up quite frequently.

Theorem: If $\sum_{n=1}^{\infty}\frac{f(n)}{n^s}$ converges absolutely and $f$ is multiplicative, then $$\sum_{n=1}^{\infty}\frac{f(n)}{n^s}=\prod_p\left(1+\frac{f(p)}{p^s}+\frac{f(p^2)}{p^{2s}}+\cdots\right)\, .$$  

The proof is essentially identical to what we proved with Moebius $\mu$'s Dirichlet series converging to its Euler product.


We can now announce four application facts which we can prove, using these tools.  We will prove as many as we have time for, and leave the rest.

  1. Fact: $$\qquad \sum_{n=1}^{\infty}\frac{1}{p_n}$$ diverges, with $p_n$ the $n$th prime.
  2. Fact: The probability that a random integer lattice point is visible from the origin is $\frac{6}{\pi^2}$.
    • This is the same thing as asking for the probability that two randomly chosen integers are relatively prime.
  3. Fact: The Dirichlet series for $f(n)=|\mu(n)|$ is $\zeta(s)/\zeta(2s)$.
  4. Fact: The average value of $\phi(n)$ is $\frac{3n}{\pi^2}$.


Let's prove these things.

Fact: $$\qquad \sum_{n=1}^{\infty}\frac{1}{p_n}$$ diverges, with $p_n$ the $n$th prime.

@interact def _(n=[10,100,1000,10000,100000,1000000]): out = sum([RealField(100)(1/p) for p in primes_first_n(n)]) html("The sum of the reciprocals of the first $%s$ primes is $\\approx %s$"%(n,out)) 

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

Proof (divergence of "prime harmonic series"):  

As with many other series, we will prove it by looking at the "tails" beyond a point that keeps getting further out.  In this case, we'll choose the 'tail' beyond the first $k$ primes.

  • So look at $$\sum_{n>k}\frac{1}{p_n}\, .$$  
  • Any number of the form $$p_1 p_2 p_3\cdots p_k r+1=p_k\#\cdot r+1$$ is not divisible by any of those first $k$ primes.
  • So $p_k\#\cdot r+1$ may be factored as $$p_{n_1}p_{n_2}\cdots p_{n_{\ell}}\; ,$$ where all $n_i>k$.  
  • That means that somewhere in the $\ell$th power of 'tail', $$\left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell}\; ,$$ we have the term $$\frac{1}{p_1 p_2 p_3\cdots p_k r+1}\; .$$ 

Now assume that in fact the "prime harmonic series" converges; we will derive a contradiction.  

  • For some $k$, the "tail" above is less than $\frac{1}{2}$, i.e. $\sum_{n>k}\frac{1}{p_n}<\frac{1}{2}$.
  • Then let's look at the sum of the $\ell$th power of the tail (this makes sense, since the series converges) $$\sum_{\ell=1}^{\infty}\left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell}\leq \sum_{\ell=1}^{\infty}\frac{1}{2^{\ell}}=2\, .$$  
  • Somewhere within this sum of the $\ell$th powers, every single term of the form $\frac{1}{p_1 p_2 p_3\cdots p_k r+1}$ will appear.
    • This is since all of these were are products of things like $\frac{1}{p_{n_i}}$ for $i>k$, though how many such primes (remember, we said $\ell$) are involved is heavily dependent upon $r$.
  • So the series of reciprocals of these terms $$0<\sum_{r=1}^{\infty}\frac{1}{p_1 p_2 p_3\cdots p_k r+1}\leq \sum_{\ell=1}^{\infty}\left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell}\, .$$ 
    • This makes sense since we have added up all of them, no matter how many primes - from the case where $p_1 p_2 p_3\cdots p_k r+1$ is itself prime to the case where it is a big product $p_{n_1}p_{n_2}\cdots p_{n_{\ell}}$.  
  • This series should still converge (by comparison, for instance), but $$\sum_{r=1}^{\infty}\frac{1}{p_1 p_2 p_3\cdots p_k r+1}>\sum_{r=1}^{\infty}\frac{1}{p_1 p_2 p_3\cdots p_k r+p_1 p_2 p_3\cdots p_k}=\frac{1}{p_1 p_2 p_3\cdots p_k}\sum_{r=1}^{\infty}\frac{1}{r+1}$$ which certainly diverges as a multiple of the tail of the harmonic series!  

This contradiction occurred because we assume that the tail of the original series was finite, so the series in fact diverges!


Fact: The chances that a random integer lattice point is visible from the origin is $\frac{6}{\pi^2}$.

@interact def _(viewsize=(5,[3..25])): var('x,y') P=Graphics() grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] P += points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (gcd(coords[0],coords[1])==1)] P += points(lattice_pts, rgbcolor = (0,0,1),pointsize=10) linesegs=[line([[0,0],[spot[0],spot[1]]],rgbcolor=(1,0,0),linestyle="--",thickness=.5) for spot in lattice_pts] for object in linesegs: P += object show(P, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) html("Probability in view is $\\approx %s$"%(Integer(len(lattice_pts))/Integer(len(grid_pts))).n()) html("Theoretical probability is $1/\zeta(2)\\approx %s$"%(1/zeta(2)).n()) 

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

Proof (probability of visibility):  

First off, it should be pretty clear from the picture that if $(x,y)$ has a gcd, then $\left(\frac{x}{d},\frac{y}{d}\right)$ is right on the line of sight from the origin to $(x,y)$ so that it is blocked off - hence we are really just asking for the probability that two integers are relatively prime.  So we will prove something about this instead.

  • We know that $gcd(x,y)=1$ is true precisely if $x$ and $y$ are never simultaneously congruent to zero modulo $p$, for any prime $p$.  
  • For any given prime $p$, the chances that two integers will both be congruent to zero is $$\left(\frac{1}{p}\right)\left(\frac{1}{p}\right)\, .$$  (This works because they really are independent, since $p$ is fixed.) 
  • Hence the probability that at least one won't be divisible by $p$ is $$1-\left(\frac{1}{p}\right)\left(\frac{1}{p}\right)=1-\frac{1}{p^2}=1-p^{-2}\, .$$ 
  • Now, a reasonable assumption: 
    • The probability than any given integer is divisible by $p$ has nothing to do with whether it is divisible by $q$ IF $p$ and $q$ are both prime.
    • This is not in general true for such properties; if $n$ is divisible by 4 it has a 100% likelihood of being divisible by 2, while if $n$ is prime, it has almost no chance of being even.
  • In this case it is legitimate to multiply the probabilities - we will sweep the fact that there are infinitely many under the rug as well under the rubric convergence - so $$\prod_p (1-p^{-2})=1/\prod_p \frac{1}{1-p^{-2}}=1/\zeta(2)=\frac{6}{\pi^2}\, .$$


Fact: The Dirichlet series for $|\mu(n)|$ is $\zeta(s)/\zeta(2s)$.


It's nearly completely symbolic at this point!

  • First, we have $$\sum_{n=1}^{\infty}\frac{|\mu(n)|}{n^s}=\prod_p\left(1+\frac{1}{p^s}\right)\, .$$ 
  • Since $(1+x)=\frac{1-x^2}{1-x}$, we can rewrite the right-hand side as $$\prod_p\left(1+\frac{1}{p^s}\right)=\frac{\prod_p\left(1-\frac{1}{p^{2s}}\right)}{\prod_p\left(1-\frac{1}{p^s}\right)}\; .$$
  • Now just make both parts reciprocals to get familiar friends: $$\frac{\prod_p\left(1-\frac{1}{p^{2s}}\right)}{\prod_p\left(1-\frac{1}{p^s}\right)}=\frac{\prod_p 1/(1-\frac{1}{p^s})}{\prod_p 1/(1-\frac{1}{p^{2s}})}\; ,$$ which means the sum is $\zeta(s)/\zeta(2s)$.



Fact: $$\lim_{n\to\infty}\frac{\frac{1}{n}\sum_{k=1}^n \phi(k)}{\frac{3}{\pi^2}n}=1$$


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

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

Proof (that the average of $\phi$ is linear with slope $3/\pi^2$):

We will crucially use these facts:

  • $$\sum_{n=1}^\infty\frac{\mu(n)}{n^2}=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$$
  • $$\phi=\mu\star N\Rightarrow \phi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}$$

Now we will look at the summation function for $\phi$.  We can once again think of it as summing things up in two different ways - along the hyperbola $xy=k$ and along each column.

  • $$\sum_{k=1}^n\phi(n)=\sum_{k=1}^n\sum_{d\mid k}\mu(d)\frac{k}{d}$$
@interact def _(n=(6,range(2,50))): viewsize=n+1 g(x)=1/x P=Graphics() P += plot(n*g,(x,0,n+1)) grid_pts = [[i,j] for i in [1..viewsize] for j in [1..viewsize]] P += points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[0]*coords[1]<=n)] for thing in lattice_pts: P += text(moebius(thing[1])*thing[0],thing,rgbcolor=(0,0,0)) show(P,ymax=viewsize,aspect_ratio=1) 

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

So $$\sum_{k=1}^n\sum_{d\mid k}\mu(d)\frac{k}{d}=\sum_{d=1}^n\mu(d)\left(\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}k\right)$$

  • The inner sum has previously been seen to be $$\frac{1}{2}\left(\frac{n}{d}\right)^2+O\left(\frac{n}{d}\right)\; .$$
  • If we plug that in, we get $$\sum_{k=1}^n\phi(n)=\frac{1}{2}n^2\sum_{d=1}^n\frac{\mu(d)}{d^2}+nO\left(\sum_{d=1}^n\frac{1}{d}\right)\; .$$
  • But we just saw that the first series goes to $\frac{6}{\pi^2}$ in the long run.   
    • Further, the error is $O(1/x)$, because $\mu(n)/n^2<1/n^2$ and $\int x^{-2}=-x^{-1}$.
  • Plugging that in, we get that $$\sum_{k=1}^n\phi(n) = \frac{1}{2}n^2\frac{6}{\pi^2}+O(\text{ stuff less than }x^2)$$

So dividing by $n$ and taking the limit, we get the asymptotic $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n\phi(n)=\lim_{n\to\infty}\frac{1}{2}\frac{n^2}{n}\frac{6}{\pi^2}=\lim_{n\to\infty}\frac{3}{\pi^2}n\; .$$

@interact def _(n=100): P = line(L(n)) show(P+plot(3/pi^2*x,(x,n-100,n),color='black',linestyle="--")+plot(3/pi^2*x+log(x),(x,n-100,n),color='red',linestyle='--'),xmin=n-100) 

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