TAOCP 7.2.1.4 Exercise 26

Let $f(x)=e^{-x^{2}/n}, \qquad n>0.$ The Poisson summation formula in the form used in TAOCP states that for sufficiently rapidly decreasing $f$, $\sum_{k=-\infty}^{\infty} f(k)=\sum_{m=-\infty}^{\inf...

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.2.1.4: Generating All Partitions

Exercise 26. [HM22] [HM22] In exercises 5.2.2–44 and 5.2.2–51 we studied two ways to prove that ∞  k=1 e−k2/n = 1 2(√πn −1) + O(n−M) for all M > 0. Show that Poisson’s summation formula gives a much stronger result.

Verified: no
Solve time: 20m22s

Solution

Let

$f(x)=e^{-x^{2}/n}, \qquad n>0.$

The Poisson summation formula in the form used in TAOCP states that for sufficiently rapidly decreasing $f$,

$\sum_{k=-\infty}^{\infty} f(k)=\sum_{m=-\infty}^{\infty} \widehat{f}(m),$

where

$\widehat{f}(m)=\int_{-\infty}^{\infty} f(x)e^{-2\pi i mx},dx.$

Compute the Fourier transform of $f$. Completing the square in the exponent,

$-x^{2}/n-2\pi i mx = -\frac{1}{n}\left(x+ i\pi m n\right)^{2}-\pi^{2} m^{2} n.$

Hence,

$\widehat{f}(m)=e^{-\pi^{2} m^{2} n}\int_{-\infty}^{\infty} e^{-(x+i\pi mn)^{2}/n},dx.$

Shifting the contour vertically does not change the Gaussian integral, so

$\widehat{f}(m)=e^{-\pi^{2} m^{2} n}\int_{-\infty}^{\infty} e^{-x^{2}/n},dx=\sqrt{\pi n},e^{-\pi^{2} m^{2} n}.$

Poisson summation yields

$\sum_{k=-\infty}^{\infty} e^{-k^{2}/n}=\sqrt{\pi n}\sum_{m=-\infty}^{\infty} e^{-\pi^{2} m^{2} n}.$

Split both sides into the $0$ term and symmetric pairs:

$1+2\sum_{k=1}^{\infty} e^{-k^{2}/n}=\sqrt{\pi n}\left(1+2\sum_{m=1}^{\infty} e^{-\pi^{2} m^{2} n}\right).$

Solving for the required sum gives

$\sum_{k=1}^{\infty} e^{-k^{2}/n}=\frac{1}{2}(\sqrt{\pi n}-1)+\sqrt{\pi n}\sum_{m=1}^{\infty} e^{-\pi^{2} m^{2} n}.$

The remainder term satisfies

$0<\sqrt{\pi n}\sum_{m=1}^{\infty} e^{-\pi^{2} m^{2} n}\le \sqrt{\pi n}\sum_{m=1}^{\infty} e^{-\pi^{2} n m}=\sqrt{\pi n},\frac{e^{-\pi^{2} n}}{1-e^{-\pi^{2} n}},$

which decays faster than $n^{-M}$ for every fixed $M>0$.

Therefore,

$\sum_{k=1}^{\infty} e^{-k^{2}/n}=\frac{1}{2}(\sqrt{\pi n}-1)+O!\left(\sqrt{n},e^{-\pi^{2} n}\right),$

and the error term is exponentially small in $n$, hence stronger than any power-law bound.

$\boxed{\sum_{k=1}^{\infty} e^{-k^{2}/n}=\frac{1}{2}(\sqrt{\pi n}-1)+\sqrt{\pi n}\sum_{m=1}^{\infty} e^{-\pi^{2} m^{2} n}}$