MAT 338 Day 40 2011

2392 days ago by kcrisman

We are almost at the very frontiers of serious number theory research now at the end of the semester.  In order to start to understand this, though, we will need to introduce two final concepts:

  • Euler products
  • Dirichlet series

To do so, let's step back a bit to two things you actually already knew.  If we let $p\mid n$ denote the set of primes which divide $n$, then $$\sigma(n)=\prod_{p\mid n}\left(\frac{p^{e+1}-1}{p-1}\right)=\prod_{p\mid n}\left(1+p+p^2+\cdots+p^e\right)$$ and $$\phi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)\, .$$  Indeed, we explicitly wrote out the product $$\frac{\sigma(n)}{n}=\frac{\prod_{p\mid n} \left(\frac{p^{e+1}-1}{p-1}\right)}{\prod_{p\mid n} p^{e}} = \prod_{p\mid n}\frac{p-1/p^{e}}{p-1}$$ in our work on perfect numbers and their friends, though perhaps at this point the product $$\frac{\sigma(n)}{n}=\frac{\prod_{p\mid n}\left(1+p+p^2+\cdots+p^e\right)}{\prod_{p\mid n}p^e}=\prod_{p\mid n}\left(1+p^{-1}+p^{-2}+\cdots p^{-e}\right)$$ might be more useful since it's not a nasty fraction.

But let's not forget that these products over primes are also sums over divisors - either by definition or by theorem.  It's clear with $\sigma$, since $$\sigma(n)=\sum_{d\mid n}d\, .$$  In fact, I can cleverly add up the divisors in the opposite order to get the slightly more felicitous $$\sigma(n)=\sum_{d\mid n}\frac{n}{d}=n\sum_{d\mid n}\frac{1}{d}\, .$$

With $\phi$ we have something to prove, but not much: recall that since $$\sum_{d\mid n}\phi(d)=n,\,$$ we have (via Möbius inversion) that $$\sum_{d\mid n}d\mu\left(\frac{n}{d}\right)=\phi(n)\, .$$  (We also wrote this as $\phi\star u=N\Rightarrow \phi=N\star \mu$.)  But what is interesting about this is that $\star$ is commutative, so it is also true that $$\phi(n)=\mu\star N=\sum_{d\mid n}\mu(d)\left(\frac{n}{d}\right)=n\sum_{d\mid n}\frac{\mu(d)}{d},\,$$ which after all does look a little cleaner of a sum over divisors.  Another way to write it is as $$\frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}$$ (which actually was an arithmetic function we discussed a little bit in February).

Now, in some sense we already knew all this; great, some arithmetic functions can be represented either as a sum over divisors or as a product over primes, depending on what you need from them.  

But the genius of Euler was to directly connect these ideas: $$\frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}=\prod_{p\mid n}\left(1-\frac{1}{p}\right)\quad\text{ and }\quad \frac{\sigma(n)}{n}=\prod_{p\mid n}\left(1+\frac{1}{p}+\frac{1}{p^{2}}+\cdots+ \frac{1}{p^{e}}\right)=\sum_{d\mid n}\frac{1}{d}\, .$$

Well, almost. His real genius was to take them to the limit!

Now, you can't really take these things to limits - you would get massive divergence.  So what do you do?  We will define new, related functions, such as  $$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}=1+\frac{1}{2^s}+\frac{1}{3^s}+\cdots$$  

zeta? 
       
plot(zeta,0,4,ymin=-1,ymax=10) 
       

This is known as the Riemann zeta function, and is probably one of the most studied, yet most mysterious functions in all of mathematics.  Riemann, by the way, died quite young (around 40), having made ground-breaking contributions to analysis (Riemann sums), geometry (Riemannian metrics - later used by Einstein), and one paper that changed the course of number theory.  He was a PK, and a quietly devout Lutheran throughout his life.

We'll motivate this function with the case $s=1$.  

  • Start with our last equation (for $\sigma$), $$\prod_{p\mid n}\left(1+\frac{1}{p}+\frac{1}{p^{2}}+\cdots +\frac{1}{p^{e}}\right)=\sum_{d\mid n}\frac{1}{d}\, ;$$ let's try computing both sides of this and seeing how they come together for a few fairly composite $n$, like 12, 16, 18, 20, or 30.
@interact def _(n=[30,20,18,24,12,16]): str = '$$'+'+'.join(['\\frac{1}{%s}'%d for d in divisors(n)])+'=%s$$'%sum([1/d for d in divisors(n)]) str2 = '$$'+''.join(['\left('+'+'.join(['\\frac{1}{%s^{%s}}'%(p,k) for k in [0..e]])+'\\right)' for (p,e) in factor(n)])+'=%s$$'%prod([sum([p^(-k) for k in [0..e]]) for (p,e) in factor(n)]) html(str) html("compare to "+str2) 
       

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

Notice how every integer $d$ formable by a product of the prime powers dividing $n$ shows up precisely once (as a reciprocal) in the sum.  In some sense, this is just the equivalence we already noted; in another sense, though, this gives us a way into introducing limits.

What would happen if we did, for instance, $$\left(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots\right)\left(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}+\cdots\right)\, ?$$ We should get a sum with exactly one copy of the reciprocal of each number divisible by only 2 and 3, e.g. $$\sum_{2\mid n\text{ or }3 \mid n}\frac{1}{n}\, .$$

@interact def _(e=(1,[0..6]),f=(2,[0..6])): n = 2^e*3^f html("You picked $%s=2^{%s}3^{%s}$"%(n,e,f)) str = '$$'+'+'.join(['\\frac{1}{%s}'%d for d in divisors(n)])+'=%s$$'%sum([1/d for d in divisors(n)]) str2 = '$$'+''.join(['\left('+'+'.join(['\\frac{1}{%s^{%s}}'%(p,k) for k in [0..e]])+'\\right)' for (p,e) in factor(n)])+'=%s$$'%prod([sum([p^(-k) for k in [0..e]]) for (p,e) in factor(n)]) html(str) html("compare to "+str2) 
       

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

There is no reason this wouldn't continue to work for many prime factors.

Because every integer is uniquely represented as a product of prime powers (FTA!), this implies that we might multiply out the left-hand side of the infinite product of infinite sums to get $$\prod_{p}\left(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\cdots\right)=\sum_{n=1}^{\infty}\frac{1}{n}\, .$$  Even better, since each of the multiplied terms on the left is a geometric series, we can write $$\prod_{p}\left(\frac{1}{1-1/p}\right)=\sum_{n=1}^{\infty}\frac{1}{n}\, .$$  

The only problem with all this is that both of these things clearly diverge!  So using $=$ is probably not the best idea.  Nonetheless, Euler's intuition is spot on, and we will be able to fix this quite satisfactorily.  For now, we can say that the harmonic series $$\zeta(1)=\sum_{n=1}^{\infty}\frac{1}{n}\text{ "equals" }\prod_{p}\left(\frac{1}{1-1/p}\right)=\prod_{p}\left(\frac{1}{1-p^{-1}}\right)\; .$$  

To make this rigorous, we start talking convergence.  

  • Recall the integral test for series!  This says that $\sum_{i=1}^n f(i)$ converges if and only if $\int_1^{\infty}f(x)dx$ converges.  (Well, if we assume a few other technical conditions, like that $f$ is decreasing and goes to zero.)
  • The improper integral in this case is $$\int_1^{\infty} x^{-s}\; dx$$ which evaluates to $$\frac{-x^{-s+1}}{1-s}\biggr|_1^{\infty}=\frac{1}{1-s}\left(1-\lim_{x\to\infty}\frac{1}{x^{s-1}}\right)\, .$$ 
  • For $s$ a real number, this converges precisely when $s>1$ (since that keeps $x$ in the denominator). 
  • So $\zeta(s)$ converges for all $s>1$.

But why is the product the same thing?  

  • One has to carefully set up the convergence here, too.  
  • It is NOT true in general that if a partial product equals a partial sum, then the 'full' sum is the 'full' product.
  • But if we can show that the product converges to the sum, then both will converge, and it will make sense to say that $$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}=\prod_p \left(\frac{1}{1-p^{-s}}\right)\; !$$

In order to see this, let's instead show that our other main example of a sum over divisors equalling a product over primes works.  

@interact def _(e=(1,[0..3]),f=(2,[0..3]),g=(0,[0..3])): n = 2^e*3^f*5^g html("You picked $%s=2^{%s}3^{%s}5^{%s}$"%(n,e,f,g)) str = '$$'+'+'.join(['\\frac{%s}{%s}'%(moebius(d),d) for d in divisors(n)])+'=%s$$'%sum([moebius(d)/d for d in divisors(n)]) str2 = '$$'+''.join(['\left(1-\\frac{1}{%s}\\right)'%p for (p,e) in factor(n)])+'=%s$$'%prod([1-1/p for (p,e) in factor(n)]) html(str) html("compare to "+str2) 
       

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

This is the same setup, but for the sum/product combination $$\sum_{d\mid n}\frac{\mu(d)}{d}=\prod_{p\mid n}\left(1-\frac{1}{p}\right)\, .$$    This would lead to the series $$\sum_{n=1}^\infty \frac{\mu(n)}{n^s}\; .$$

We call a series like this a Dirichlet series. 

Definition:  

In general, for an arithmetic function $f(n)$, its Dirichlet series is $$F(s)=\sum_{n=1}^{\infty}\frac{f(n)}{n^s}\, .$$  

 

Three questions to see if we understand this:

  • For what arithmetic function is the Riemann zeta function the Dirichlet series?
  • What would the Dirichlet series of $N$ be?   
  • What about the Dirichlet series of $I$?

Note that this already indicates some level of connection between arithmetic functions - connections which may not have been evident otherwise.

The very important thing to note about such series is that they often can indeed be expanded as infinite products as well.  Something like  $$\sum_{n=1}^{\infty}\frac{f(n)}{n^s}=\prod_p (\text{ something involving }f(p)\text{ and }p^s)$$  If this is possible, then we say that the series has an Euler product form.  

A potential Euler product, then, is one for the Dirichlet series of the Moebius function - $$\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'll prove this works.

  • 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 $k$th 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 it's okay to stare at it for a while.
  • Next, let's introduce the set (cf. Jones and Jones) $$A_k=\{n | n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},e_i\geq 0\}$$  This is the set of all integers built out of the first $k$ primes.  
  • Then since $\mu(n)=0$ unless it has no higher prime powers, the big right hand side sum is equal to $$\sum_{n\in A_k}\frac{\mu(n)}{n}\; .$$  
  • I can replace $p_i$ with $p_i^s$ with no harm (the FTA gives the same relations), so I can now write $$\prod_{i=1}^k (1-p_i^{-s})=\sum_{n\in A_k}\frac{\mu(n)}{n^s}\, .$$  
  • In order to get a bound on the difference between the infinite product and infinite series, let's take a closer look at $n\notin A_k$.
    • All $n\notin A_k$ must be $n>p_k$ since $n$ 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|\; .$$
    • What this means is we have a specific formula for an error up through the $k$th prime.
    • Note that this only makes sense because the infinite sum involving $\mu$ converges for the same $s$ as $\zeta(s)$ does.  This is because it's bounded by $\pm\zeta$, and $\zeta$ converged absolutely for $s>1$ (recalling our calculus tests).
  • Next I can do a few extra things to bound this error even better.  $$\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.  
    • We can put the absolute value inside the summation by an extended triangle inequality; this is only legitimate if the final thing converges, but we are about to show that.
    • The second inequality is again due to the fact that any $n\notin A_k$ must be bigger than $p_k$, so the set of all integers above $p_k$ would just yield a bigger sum.
    • The last one is using the boundedness by $\zeta$ we used a second ago.
  • Finally, this error $\sum_{n>p_k}\frac{1}{n^s}$ must go to zero as $k\to \infty$, since this is the tail of a convergent infinite series.  
  • 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:

  • $$\prod_p \frac{1}{1-p^{-s}}=1/\left(\prod_p 1-p^{-s}\right)\, .$$
  • So $$\sum_{n=1}^\infty\frac{\mu(n)}{n^s}=1/\zeta(s)\; .$$

That is, we have that 

  • The arithmetic functions $u\star \mu=I$ - they are inverses.
  • The Dirichlet series of these functions are also inverses.

This is not a coincidence.

L = Dokchitser(conductor=1, gammaV=[0], weight=1, eps=1) L.init_coeffs('moebius(k)') 
       
L(2); (1/(pi^2/6)).n() 
       
0.0741344280534404
0.607927101854027
0.0741344280534404
0.607927101854027
  • 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\; .$$

These are deep and amazing results, which we will exploit with many applications next time.