MAT 338 Day 41

962 days ago by pub

We start with Z's presentation on computers in conjectures in number theory - the last one!

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)\, ,
which for n=1 one can interpret as the somewhat nonsensical but still fun 
\sum_{n=1}^{\infty}\frac{1}{n}=\prod_p \left(\frac{1}{1-1/p}\right)\, .
 And of course the most famous thing, as we've mentioned several times, is the solution to the Basel problem, when s=2:
zeta(RealField(100)(2));RealField(100)(pi^2/6);sum([RealField(100)(1/n^2) for n in [1..10000]]);prod([RealField(100)(1/(1-1/p^2)) for p in prime_range(10000)]) 
        
1.6449340668482264364724151666
1.6449340668482264364724151666
1.6448340718480597698060818333
1.6449179207462864179339592276
1.6449340668482264364724151666
1.6449340668482264364724151666
1.6448340718480597698060818333
1.6449179207462864179339592276
def Zeta(x): return RR(zeta(x)) plot(Zeta,2,20) 
       

Clearly there must be more efficient ways of calculating it than by hand!  But the product seems to converge faster.

Let's see this process one more time, for another function.  After all, convergence for just the sum of \frac{1}{n^s} is a little familiar.  Theorem 9.7 shows that such series will converge and have Euler product representations, but let's do it specifically for the Dirichlet series we get from \mu(n) - namely, we want to prove 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.  We start with the identity we already know:
\sum_{d\mid n}\frac{\mu(d)}{d}=\prod_{p\mid n}(1-p^{-1})\, .
 Assuming we multiply these products out through the kth prime, we get
\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)=1-\frac{1}{p_1}-\frac{1}{p_2}-\cdots +\frac{1}{p_1 p_2}+\frac{1}{p_1 p_3}+\cdots -\frac{1}{p_1 p_2 p_3}-\frac{1}{p_1 p_2 p_4}-\cdots = \sum_{n\text{ squarefree and only }p_i\mid n,1\leq i\leq k}\frac{\mu(n)}{n}\, .
 This might take a little bit to assimilate, so let's stare at it for a while.

Next, let's once again let A_k=\{n | n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},e_i\geq 0\} i.e. all integers built out of the first k primes.  Then since \mu(n)=0 unless it has no higher prime powers, and since we can replace the p_i with p_i^s with no harm, the right hand side above is equal to \sum_{n\in A_k}\frac{\mu(n)}{n^s}.  That means I can write

\prod_{i=1}^k (1-p_i^{-s})=\sum_{n\in A_k}\frac{\mu(n)}{n^s}\, .
 But once again, every n\notin A_k must be n>p_k since it cannot have any of the first k primes as factors, so at the very least we know that
\left| \prod_{i=1}^k (1-p_i^s)-\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s}\right|=\left|\sum_{n\notin A_k}\frac{\mu(n)}{n^s}\right|\leq \sum_{n\notin A_k}\left|\frac{\mu(n)}{n^s}\right|\leq \sum_{n>p_k}\left|\frac{\mu(n)}{n^s}\right|\leq \sum_{n>p_k}\frac{1}{n^s}\, .
 There are a few things to explain here.  First, the infinite sum converges for the same s as \zeta(s) does, since \zeta converged absolutely.  Second, we can put the absolute value inside the summation by an extended triangle inequality, which shows up practically everywhere in the guise of the so-called Cauchy-Schwarz inequality.  Finally, this error is bounded by something which we know must go to zero as k\to \infty, so the error goes to zero.  That means that it all converges and we have our Euler product for this Dirichlet series!  

What is particularly cool about this is that now we see 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)\, ,
which for instance implies that \sum \frac{\mu(n)}{n^2}=\frac{6}{\pi^2}.
L = Dokchitser(conductor=1, gammaV=[0], weight=1, eps=1) L.init_coeffs('moebius(k)') 
       

But this is true in general!  Take f(n) and g(n) two arithmetic functions, and let h=f\star g be their Dirichlet product.  Then let F,G,H be the corresponding series (in s). Then you can follow your nose, assuming these things converge absolutely for the s you care about; see the proof on page 180 in your book.  Note that we have not proved that you can multiply and rearrange these series with abandon!  It is a very important theoretical result that absolute convergence allows us to do that.  Examples 9.4 and 9.5, and Exercises 9.10-9.12, are very fun in that regard.  Finally, Corollary 9.8 give us one last result from the hard work developing all these things earlier, showing it has paid off: 

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)\, .
 In the case of \mu, all the f(p^e) disappeared except e=1, so the form becomes simpler; in the Riemann zeta function case they in fact became a geometric series, because u(n)=1 for all n, which is why it has a simple form.  In general, though, such things are not so easy.  Notice that we can do some things quite simply now.  For instance
\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)}=\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), a quick but deep computation (see Exercise 9.14).  (And if one was very astute, one could use this argument to figure out whether there was a Dirichlet product hanging around this example.)

We can do some fun things with these ideas as well.

Fact:\qquad \sum_{n=1}^{\infty}\frac{1}{p_n} diverges, with p_n the nth prime.
[sum([RealField(100)(1/p) for p in primes_first_n(n)]) for n in [10,100,1000,10000]] 
        
[1.5334387718720320221427253051, 2.1063421214726210940060270059,
2.4574112767113577477383628425, 2.7092582487972945768171320614]
[1.5334387718720320221427253051, 2.1063421214726210940060270059, 2.4574112767113577477383628425, 2.7092582487972945768171320614]

Fact: The chances that a random integer lattice point is visible from the origin is \frac{6}{\pi^2}.
var('x,y') viewsize=10 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) 
       

Proof (divergence of "prime harmonic series"):  As with many other series like this, we will prove it by looking at the "tails" beyond the first k primes; here, we will 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
is not divisible by any of those first k primes, so p_1 p_2 p_3\cdots p_k r+1=p_{n_1}p_{n_2}\cdots p_{n_{\ell}}, where all n_i>k.  Okay, that means that somewhere in the "FOILing" of the product
\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.  Then for some k, the "tail" above is less than \frac{1}{2}, i.e.

\sum_{n>k}\frac{1}{p_n}<\frac{1}{2}\text{, so }\sum_{\ell=1}^{\infty}\left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell}\leq \sum_{\ell=1}^{\infty}\frac{1}{2^{\ell}}=2\, .
 Now notice that although this is a crazy sum of powers of sums, in particular it will include somewhere within it every single term of the form \frac{1}{p_1 p_2 p_3\cdots p_k r+1}, since all of these were just shown to be products of \frac{1}{p_{n_i}} for i>k, though how many such primes (remember, we said \ell) are involved is heavily dependent upon r.

But that means that the series

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}}.  Yet then this series should 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!

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.

But 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 (very naively speaking, but it works out) that two integers will both be congruent to zero is

\left(\frac{1}{p}\right)\left(\frac{1}{p}\right)\, ,
so that the probability that at least one won't be is
1-\left(\frac{1}{p}\right)\left(\frac{1}{p}\right)=1-\frac{1}{p^2}=1-p^{-2}\, .
 Again, we won't justify this, but 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.  (Note that 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.  This is a little sketchy still since there are infinitely many conditions, but we will ignore that and come up with the result that the chances are

\prod_p (1-p^{-2})=1/\prod_p \frac{1}{1-p^{-2}}=1/\zeta(2)=\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);print "Probability in view is about",(Integer(len(lattice_pts))/Integer(len(grid_pts))).n();print "while theoretical probability is",1/zeta(2) 
       

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

Don't forget to attend the poster session Wednesday in Ken Olson!  As soon as I know something, or W does, we will also let you know about the Thursday morning gig.

Finally, a preview of next time.  Recall (or don't recall) that it makes sense to ask for a radius of convergence for a Taylor series, which is visible:
P=plot(ln,0,2.5) Q=plot(taylor(ln(x),x,1,20),0,2.5) show(P+Q,ymin=-2) 
       

But it's also possible to ask for complex input values!  And that makes the plot much, much more obvious for why it fails:
def f(x,y): if x^2==y^2: return -1e5 else: return abs(ln(x^2-y^2)) P=plot3d(f,(x,0,2.5),(y,0,2.5),color='red') var('z') T(z)=taylor(ln(z),z,1,20) S(x,y)=abs(T(x^2-y^2)) Q=plot3d(S(x,y),(x,0,2.5),(y,0,2.5)) show(P+Q) 
       

The upshot is that convergence and other questions make a lot more sense over the complex numbers.  So why shouldn't this also be the case for Dirichlet series?  And indeed, this is exactly what we will do next time in order to finish the course with the greatest unsolved question in mathematics - the Riemann Hypothesis!