Discrete Sums to Continuous Integrals with Abel's Partial Summation Formula

It is often easier to understand how a discrete function behaves if it can be expressed as a continuous function. Abel's partial summation formula allows us to write a discrete sum as continuous integral.

In this blog post we'll derive the partial summation formula, and show a simple example of its power.

The video for this post is at [youtube], and the slides are here [pdf].

A Useful Object

The following is a sum over an arithmetic function $a(n)$ weighted by a smooth function $f(x)$. 

$$\sum_{x_{1}<n\leq x_{2}}a(n)f(n)$$

This is a useful general object to find an integral form for, because it gives us flexibility in choosing the arithmetic and smooth functions. 

To be more precise about the functions, $a(n)$ takes only positive integers $n\geq1$, and $f(x)$ has a continuous derivative over the domain $[x_{1},x_{2}]$. Both $a(n)$ and $f(x)$ can be complex.

Deriving An Integral Form

If you look ahead, the derivation of an integral form for the sum might look overwhelming, but it is just lots of simple algebra.

Because $a(n)$ is only defined over integers $n\geq1$, we can clarify the sum by setting $m_{1}=\left\lfloor x_{1}\right\rfloor$  and $m_{2}=\left\lfloor x_{2}\right\rfloor$. Remember that $\left\lfloor x\right\rfloor$  is the largest integer up to, and including, $x$.

$$\sum_{x_{1}<n\leq x_{2}}a(n)f(n)=\sum_{n=m_{1}+1}^{m_{2}}a(n)f(n)$$

Let's define $A(x)=\sum_{n\leq x}a(n)$. By definition $a(n)=A(n)-A(n-1)$ so we can replace $a(n)$.

$$\begin{align}\sum_{m_{1}+1}^{m_{2}}a(n)f(n)&=\sum_{m_{1}+1}^{m_{2}}\left[A(n)-A(n-1)\right]f(n)\\ \\ &=\sum_{m_{1}+1}^{m_{2}}A(n)f(n)-\sum_{m_{1}}^{m_{2}-1}A(n)f(n+1)\end{align}$$

The two sums have different limits for n, but both cover $[m_{1}+1,m_{2}-1]$.

$$\begin{align}\sum_{m_{1}+1}^{m_{2}}a(n)f(n) &=\sum_{m_{1}+1}^{m_{2}-1}A(n)\left[f(n)-f(n+1)\right] \\ \\ &+A(m_{2})f(m_{2})-A(m_{1})f(m_{1}+1)\end{align}$$

Noticing that $\int_{n}^{n+1}f'(t)dt=f(n+1)-f(n)$ allows us to introduce the integral.

$$\begin{align}\sum_{m_{1}+1}^{m_{2}}a(n)f(n) &=-\sum_{m_{1}+1}^{m_{2}-1}A(n)\int_{n}^{n+1}f'(t)dt \\ \\ &+A(m_{2})f(m_{2})-A(m_{1})f(m_{1}+1)\end{align}$$

Now, because $A(t)=A(n)$ over the interval $[n,n+1)$, we can move $A(n)$ it inside the integral as $A(t)$.

$$\begin{align}\sum_{m_{1}+1}^{m_{2}}a(n)f(n) &=-\sum_{m_{1}+1}^{m_{2}-1}\int_{n}^{n+1}A(t)f'(t)dt\\ \\ &+A(m_{2})f(m_{2})-A(m_{1})f(m_{1}+1)\end{align}$$

That sum of integrals over consecutive intervals can be simplified to a single integral. 

$$\begin{align}\sum_{x_{1}<n\leq x_{2}}a(n)f(n) &=-\int_{m_{1}+1}^{m_{2}}A(t)f'(t)dt\\ \\ &+A(m_{2})f(m_{2})-A(m_{1})f(m_{1}+1)\end{align}$$

We now need to adjust the integration limits back to $x_{1}$ and $x_{2}$, not forgetting the intervals to $m_{1}$ and $m_{2}$. Writing out the integrals that split the interval $[x_{1},x_{2}]$ is helpful.

$$\int_{x_{1}}^{x_{2}}Xdt=\int_{m_{1}+1}^{m_{2}}Xdt+\int_{x_{1}}^{m_{1}+1}Xdt+\int_{m_{2}}^{x_{2}}Xdt$$

Rearranging, and noticing that $A(t)=A(x_{1})$ over the interval $[x_{1},m_{1}+1)$, and $A(t)=A(x_{2})$ over the interval $[m_{2},x_{2}]$, gives us the following.

$$\begin{align}-\int_{m_{1}+1}^{m_{2}}A(t)f'(t)dt&=\int_{x_{1}}^{m_{1}+1}A(t)f'(t)dt+\int_{m_{2}}^{x_{2}}A(t)f'(t)dt\\ \\ &-\int_{x_{1}}^{x_{2}}A(t)f'(t)dt\\ \\ &=A(x_{1})\left[f(m_{1}+1)-f(x_{1})\right]+A(x_{2})\left[f(x_{2})-f(m_{2})\right]\\ \\ &-\int_{x_{1}}^{x_{2}}A(t)f'(t)dt\end{align}$$

We plug this integral back into our object, then use $A(m_{1})=A(x_{1})$ and $A(m_{2})=A(x_{2})$.

$$\begin{align}\sum_{x_{1}<n\leq x_{2}}a(n)f(n)&=A(x_{2})f(m_{2})-A(x_{1})f(m_{1}+1)\\ \\ &+A(x_{1})\left[f(m_{1}+1)-f(x_{1})\right]+A(x_{2})\left[f(x_{2})-f(m_{2})\right]\\ \\ &-\int_{x_{1}}^{x_{2}}A(t)f'(t)dt\end{align}$$

Many of these terms cancel out, leaving us with the much neater Abel Identity, as it is also called.

$$\boxed{\sum_{x_{1}<n\leq x_{2}}a(n)f(n)=A(x_{2})f(x_{2})-A(x_{1})f(x_{1})-\int_{x_{1}}^{x_{2}}A(t)f'(t)dt}$$

In many cases $n$ starts at 1, and so the formula reduces further. 

$$\boxed{\sum_{1\leq n\leq x_{2}}a(n)f(n)=A(x_{2})f(x_{2})-\int_{1}^{x_{2}}A(t)f'(t)dt}$$

The lower limit of the integral is 1 because $A(t)=0$ in the range $[0,1)$.

Example: Growth of $\sum1/n$

Abel's identity is particularly useful for clarifying the asymptotic behaviour of discrete functions. Let's illustrate its use to show the how the harmonic series $\sum_{1}^{N}1/n$ grows.

We can choose $a(n)=1$ and $f(x)=1/x$, which means $A(x)=\left\lfloor x\right\rfloor$  and $f'(x)=-1/x^{2}$. 

$$\begin{align}\sum_{n\leq N}\frac{1}{n}&=A(N)f(N)-\int_{1}^{N}A(t)f't)\\ \\ &=\frac{N-\{N\}}{N}+\int_{1}^{N}\frac{t-\{t\}}{t^{2}}dt\end{align}$$

We've used $\left\lfloor x\right\rfloor =x-\{x\}$, where $\{x\}$ is the fractional part of $x$. This also lets us split the integral into manageable parts.

$$\sum_{0<n\leq N}\frac{1}{n}=1+\mathcal{O}\left(\frac{1}{N}\right)+\int_{1}^{N}\frac{1}{t}dt-\int_{1}^{N}\frac{\{t\}}{t^{2}}dt$$

Because $\{t\}$ is only ever in the range $[0,1)$, the last integral is always less than $\int_{1}^{N}1/t^{2}dt$, that is, $\mathcal{O}\left(\left[-1/t\right]_{1}^{N}\right)$.

$$\begin{align}\sum_{0<n\leq N}\frac{1}{n}&=1+\mathcal{O}\left(\frac{1}{N}\right)+\ln(N)+\mathcal{O}\left(1-\frac{1}{N}\right)\\ \\ &=\ln(N)+\mathcal{O}\left(1\right)\end{align}$$

This tells us the harmonic series grows like $\ln(N)$, a powerful result derived easily using the Abel identity. It also tells us the difference is bounded by 1. In fact, the difference tends to the Euler–Mascheroni constant $\gamma\approx0.5772$ which pops up in several areas of number theory and analysis.

Convergence Of Dirichlet Series

The Riemann Zeta series is an example of a Dirichlet series.

$$\zeta(s)=\sum\frac{1}{n^{s}}=\frac{1}{1^{s}}+\frac{1}{2^{s}}+\frac{1}{3^{s}}+\frac{1}{4^{s}}+\ldots$$

Dirichlet series have the general form $\sum a_{n}/n^{s}$, in contrast to the more familiar power series $\sum a_{n}z^{n}$.

In this blog post we'll explore when these series converge, first looking at absolute convergence, and then more general convergence.

The video for this post is at [youtube], and the slides are here [pdf].

Abscissa Of Absolute Convergence

A series converges absolutely even when all its terms are replaced by their magnitudes, sometimes called absolute values. This is quite a strong condition, and not all series that converge do so absolutely.

Let's assume a Dirichlet series converges absolutely at $s_{1}=\sigma_{1}+it_{1}$, and consider another point $s_{2}=\sigma_{2}+it_{2}$ where $\sigma_{2}\geq\sigma_{1}$. On the complex plane, $s_{2}$ is to the right of $s_{1}$.

Now let's compare the magnitudes of the terms in this series at $s_{1}$ and $s_{2}$. Remember $n^{\sigma+it}=n^{\sigma}e^{it\ln n}$, and because the magnitude of any $e^{i\theta}$ is 1, we can simplify $\left|n^{\sigma+it}\right|=n^{\sigma}$.

$$\sum\left|\frac{a_{n}}{n^{s_{1}}}\right|=\sum\frac{\left|a_{n}\right|}{n^{\sigma_{1}}}\geq\sum\frac{\left|a_{n}\right|}{n^{\sigma_{2}}}=\sum\left|\frac{a_{n}}{n^{s_{2}}}\right|$$

This is simply telling us that the magnitude of each term in the series at $s_{2}$ is less than or equal to the magnitude of the same term at $s_{1}$. So if the series converges at $s_{1}$, it must also converge at $s_{2}$. More generally, the series converges at any $s=\sigma+it$ where $\sigma\geq\sigma_{1}$. 

If our series doesn't converge everywhere, the $s$ for which it diverges must therefore have $\sigma<\sigma_{1}$. We can see there must be a minimum $\sigma_{a}$, called the abscissa of absolute convergence, such that the series converges for all $\sigma>\sigma_{a}$. 

Notice how absolute convergence depends only on the real part of $s$. Working out the domain of convergence along the real line automatically gives us the domain of convergence in the complex plane.

For example, in we previously showed the series $\sum1/n^{\sigma}$ converges for real $\sigma>1$. We also know the series diverges at $\sigma=1$. These two facts allow us to say $\sigma_{a}=1$, and so the series converges for all complex $s=\sigma+it$ where $\sigma>1$.

It's interesting that the region of convergence for a Dirichlet series is a half-plane, whereas the region for the more familiar power series $\sum a_{n}z^{n}$ is a circle.

Abscissa Of Convergence

Absolute convergence is easier to explore as we don't need to consider the effect of complex terms which contribute a negative amount to the overall magnitude of the series. For example, a term $e^{i\pi}=-1$ can partially cancel the effect of a term $2e^{i2\pi}=+2$. This cancelling effect can mean some series do converge, even if not absolutely.

Our strategy, inspired by Apostol, will be to show that if a Dirichlet series is bounded at $s_{0}=\sigma_{0}+it_{0}$ then it is also bounded at $s=\sigma+it$, where $\sigma>\sigma_{0}$, and then push a little further to show it actually converges at that $s$. 

Let's start with a Dirichlet series $\sum a_{n}/n^{s}$ that we know has bounded partial sums at a point $s_{0}=\sigma_{0}+it_{0}$ for all $x\geq1$. 

$$\left|\sum_{n\leq x}\frac{a_{n}}{n^{s_{0}}}\right|\leq M$$

Being bounded is not as strong a requirement as convergence, the partial sums could oscillate for example.

We'll use Abel's partial summation formula, explained in a later blog, which relates a discrete sum to a continuous integral.

$$\sum_{x_{1}<n\leq x_{2}}b_{n}f(n)=B(x_{2})f(x_{2})-B(x_{1})f(x_{1})-\int_{x_{1}}^{x_{2}}B(t)f'(t)dt$$

Because we're comparing to $s_{0}$, we'll define $f(x)=x^{s_{0}-s}$ and $b_{n}=a_{n}/n^{s_{0}}$. Here $B(x)$ is defined as $\sum_{n\leq x}b_{n}$, and so $\left|B(x)\right|\leq M$.

$$\begin{align}\sum_{x_{1}<n\leq x_{2}}\frac{a_{n}}{n^{s}}&=\sum_{x_{1}<n\leq x_{2}}b_{n}f(n)\\ \\ &=\frac{B(x_{2})}{x_{2}^{s-s_{0}}}-\frac{B(x_{1})}{x_{1}^{s-s_{0}}}+(s-s_{0})\int_{x_{1}}^{x_{2}}\frac{B(t)}{t^{s-s_{0}+1}}dt\end{align}$$

We now consider the magnitude of the series, which is never more than the sum of the magnitudes of its parts, and make use of $\left|B(x)\right|\leq M$. 

$$\begin{align}\left|\sum_{x_{1}<n\leq x_{2}}\frac{a_{n}}{n^{s}}\right|&\leq\left|\frac{B(x_{2})}{x_{2}^{s-s_{0}}}\right|+\left|\frac{B(x_{1})}{x_{1}^{s-s_{0}}}\right|+\left|(s-s_{0})\int_{x_{1}}^{x_{2}}\frac{B(t)}{t^{s-s_{0}+1}}dt\right|\\ \\ &\leq Mx_{2}^{\sigma_{0}-\sigma}+Mx_{1}^{\sigma_{0}-\sigma}+\left|s-s_{0}\right|M\int_{x_{1}}^{x_{2}}t^{\sigma_{0}-\sigma-1}dt\end{align}$$

Because $x_{1}<x_{2}$, we can say $Mx_{2}^{\sigma_{0}-\sigma}+Mx_{1}^{\sigma_{0}-\sigma}<2Mx_{1}^{\sigma_{0}-\sigma} for \sigma>\sigma_{0}$. Despite appearances, evaluating the integral is easy.

$$\begin{align}\left|\sum_{x_{1}<n\leq x_{2}}\frac{a_{n}}{n^{s}}\right| &\leq 2Mx_{1}^{\sigma_{0}-\sigma}+\left|s-s_{0}\right|M\left(\frac{x_{2}^{\sigma_{0}-\sigma}-x_{1}^{\sigma_{0}-\sigma}}{\sigma_{0}-\sigma}\right)\\ \\ &\le2Mx_{1}^{\sigma_{0}-\sigma}\left(1+\frac{\left|s-s_{0}\right|}{\sigma-\sigma_{0}}\right)\end{align}$$

The last step uses $\left|x_{2}^{\sigma_{0}-\sigma}-x_{1}^{\sigma_{0}-\sigma}\right|=x_{1}^{\sigma_{0}-\sigma}-x_{2}^{\sigma_{0}-\sigma}<x_{1}^{\sigma_{0}-\sigma}<2x_{1}^{\sigma_{0}-\sigma}$. 

The key point is that $\sum_{x_{1}<n\leq x_{2}}a_{n}/n^{s}$ is bounded if $\sum_{n\leq x}a_{n}/n^{s_{0}}$ is bounded, where $\sigma>\sigma_{0}$.

Let's see if we can push this result about boundedness to convergence. 

$$\left|\sum_{x_{1}<n\leq x_{2}}\frac{a_{n}}{n^{s}}\right|\le2Mx_{1}^{\sigma_{0}-\sigma}\left(1+\frac{\left|s-s_{0}\right|}{\sigma-\sigma_{0}}\right)=Kx_{1}^{\sigma_{0}-\sigma}$$

Here $K$ doesn't depend on $x_{1}$. If we let $x_{1}\rightarrow\infty$ then $Kx_{1}^{\sigma_{0}-\sigma}\rightarrow0$, which means the magnitude of the tail of the infinite sum $\sum a_{n}/n^{s}$ diminishes to zero, and so the series is not just bounded, it also converges. 

Let's summarise our results so far:

• If $\sum_{n\leq x}a_{n}/n^{s_{0}}$ is bounded, the infinite sum $\sum a_{n}/n^{s}$ converges for $\sigma>\sigma_{0}$.

• With the special case of $s_{0}=0$, if $\sum_{n\leq x}a_{n}$ is bounded, the infinite sum $\sum a_{n}/n^{s}$ converges for $\sigma>0$.

The special case is particularly useful as we can sometimes say whether a series converges for $\sigma>0$ just by looking at the coefficients $a_{n}$.

Following the same logic as for $\sigma_{a}$, it is clear there is an abscissa of convergence $\sigma_{c}$ where a Dirichlet series converges for $\sigma>\sigma_{c}$, and diverges for $\sigma<\sigma_{c}$.

Maximum Difference Between $\sigma_{c}$ And $\sigma_{a}$

We know that not all convergent series are absolutely convergent, so we can say $\sigma_{a}\geq\sigma_{c}$. We shouldn't have to increase $\sigma$ by too much before a conditionally convergent series converges absolutely.

If a series converges at $s_{0}$, the magnitude of terms is bounded. We can call this bound $C$.

$$\sum\left|\frac{a_{n}}{n^{s}}\right|=\sum\left|\frac{a_{n}}{n^{s_{0}}}\cdot\frac{1}{n^{s-s_{0}}}\right|\leq C\sum\frac{1}{n^{\sigma-\sigma_{0}}}$$

We know series of the form $\sum n^{\sigma_{0}-\sigma}$ only converge for $\sigma_{0}-\sigma>1$, so we can say if $\sigma$ is larger than $\sigma_{c}$ by at least 1, the series converges absolutely.

$$\boxed{0\leq\sigma_{a}-\sigma_{c}\leq1}$$

Example: Alternating Zeta Function

Let's apply our results to the alternating zeta function, also called the eta function.

$$\eta(s)=\sum\frac{(-1)^{n+1}}{n^{s}}=\frac{1}{1^{s}}-\frac{1}{2^{s}}+\frac{1}{3^{s}}-\frac{1}{4^{s}}+\ldots$$

At $s_{0}=0$ the partial sum $\sum_{n\leq x}(-1)^{n+1}$ oscillates but is always bounded $\leq1$, and so $\sum(-1)^{n+1}/n^{s}$ converges for $\sigma>0$. 

Into The Complex Domain

The Riemann Zeta function encodes information about the primes. We've already seen how we can use it to easily prove there are infinite primes, and that the prime harmonic series diverges, telling us the primes aren't so sparse.

$$\zeta(s)=\sum_{n}\frac{1}{n^{s}}=\prod_{p}(1-\frac{1}{p^{s}})^{-1}$$

We've thought about the zeta function with s as an integer, for example the harmonic series with $s=1$, and the Basel problem with $s=2$. We've also considered $s$ as a real number, and asked whether the zeta function converges for values of $s$ between 1 and 2. We proved the zeta function converges for $s>1$.

Riemann was the first to consider s as a complex number. If we think the zeta function over the complex domain might reveal new insights into the primes, we need to understand how it behaves. Exploring where it converges is a good start.

The video for this blog is at [youtube]. Slides are online [pdf].

Convergence For $\sigma>1$

It has become tradition to write complex $s$ as $s=\sigma+it$, where $\sigma$ is the real part of $s$.

$$\sum\frac{1}{n^{s}}=\sum\frac{1}{n^{\sigma+it}}=\sum\frac{1}{n^{\sigma}}\frac{1}{n^{it}}$$

Let's look at the series with each term replaced by its magnitude. 

$$\sum\left|\frac{1}{n^{s}}\right|=\sum\left|\frac{1}{n^{\sigma}}\frac{1}{n^{it}}\right|$$

Rewriting $n^{it}$ as $e^{it\ln(n)}$ makes clear it has a magnitude of 1.

$$\sum\left|\frac{1}{n^{s}}\right|=\sum\frac{1}{n^{\sigma}}$$

We've already shown $\sum1/n^{\sigma}$ converges for $\sigma>1$ where $\sigma$ is real. This tells us $\sum1/n^{s}$ converges absolutely for for $\sigma>1$. Since absolute convergence implies convergence, we can say $\sum1/n^{s}$ converges whenever the real part of $s$ is more than 1, that is $\sigma>1$.

Divergence For $\sigma\leq0$

Let's look again at the terms in the sum.

$$\left|\frac{1}{n^{s}}\right|=\left|\frac{1}{n^{\sigma}}\frac{1}{n^{it}}\right|=\frac{1}{n^{\sigma}}$$

If $\sigma<0$, the magnitude of the terms grows larger than 1. If $\sigma=0$, the magnitude of each term is exactly 1. For any series to converge, a necessary requirement is that the terms get smaller towards zero. This means $\sum1/n^{s}$ diverges for $\sigma\leq0$.

Divergence For $\sigma<1$

Having found the Riemann Zeta function converges for $\sigma>1$, and diverges for $\sigma\leq0$, we are left with a gap $0<\sigma\leq 1$. To fill this gap we need to understand more generally when series of the form $\sum a_{n}/n^{s}$, called Dirichlet series, converge or diverge. 

A later blog post will explain how Dirichlet series converge in half-planes to the right of an abscissa of convergence $\sigma_{c}$. That is, they converge at an $s=\sigma+it$ where $\sigma>\sigma_{c}$.

Because $\zeta(s)$ converges for $\sigma>1$, and we know it diverges at $s=1+0i$, the abscissa of absolute convergence is at $\sigma_{c}=1$. We can now say $\zeta(s)$ diverges for $\sigma<1$.

Visualising The Zeta Function For $s>1$

Visualising a function helps us understand it. The plot below shows a surface plot of $\ln\left|\zeta(s)\right|$ for $\sigma>1$. Because the values of $\zeta(s)$ are complex, it is easier to plot the magnitude of $\zeta(s)$. Taking the logarithm scales down very large values to better show the function's features. 

The spike around $s=1+0i$ corresponds to the divergent harmonic series $\zeta(1)$.

The surface seems to smooth out to the right as $\sigma$ grows larger. Again, it is natural to ask what value it approaches. Let's look again at the terms of the sum $\zeta(s)$.

$$\zeta(s)=\frac{1}{1^{s}}+\frac{1}{2^{s}}+\frac{1}{3^{s}}+\frac{1}{4^{s}}+\ldots$$

As $s\rightarrow\infty$ all the terms $1/n^{s}\rightarrow0$, except the first term which remains 1. To be more precise, the magnitude of each term $|n^{-s}|=n^{-\sigma}$ tends to zero as $\sigma\rightarrow\infty$ for all $n>1$. That means the magnitude of the function $\zeta(s)\rightarrow1$ as $\sigma\rightarrow\infty$.

Hints The Function Extends Into $\sigma\leq1$

Looking again at the plot above, we can see that aside from $s=1+0i$, the function doesn't seem to diverge along the line $s=1+it$. It looks like the surface has been prematurely cut off, and would continue smoothly into $\sigma\leq1$ if allowed.

The plot below shows a contour plot of $\ln\left|\zeta(s)\right|$. The contours do indeed appear artificially cut off, as if they should continue smoothly to the left of $\sigma=1$.

The intuition that a function should continue smoothly without abrupt changes corresponds to a powerful property of many functions we come across. If we can show $\zeta(s)$ is one of these well-behaved functions, we are then justified in trying to extend it to the left of $\sigma=1$.