In this post I want to prove a lemma which gives a closed-form expression for the summation $\sum_{n=1}^m\sin(nx)$.  The method of proof has come up before; it uses basic algebra, the complex exponential expression for sine, and the summation of a geometric series formula.

Continue reading →

We’ve discussed before the “trigonometric harmonic” series $\sum_{n=1}^\infty\cos n/n$. In particular, we showed that the series converges (conditionally). The argument involved the partial sums of the sequence $\{\cos n\}_{n=1}^\infty$, and we denoted these by $C(m)$. The closed-form expression we found for $C(m)$ involved the quantity $\cos m-\cos(m+1)$; in this post we show that this expression can also be written in the alternative form $2\sin(1/2)\sin(m+1/2)$. Continue reading →

Previously I discussed a variant on the harmonic series, $\sum_{n=1}^\infty\cos n/n$. Last time we showed that \[ \sum_{n=1}^\infty\frac{\cos n}{n} = \sum_{n=1}^\infty\sum_{m=1}^n\cos m\Bigl(\frac{1}{n}-\frac{1}{n+1}\Bigr) , \] and then showed that the series on the right converges absolutely, by comparison with the series $\sum_{n=1}^\infty3/n^2$. Since the series on the right converges and the two series have the same value, the series on the left also converges. However, this does not imply that the series on the left also converges absolutely. As a trivial counterexample, if a conditionally convergent series sums to $c$ then $c\sum_{n=1}^\infty \href{http://en.wikipedia.org/wiki/Kronecker_delta}{\delta_{n,1}}$ is an absolutely convergent series which sums to the same value. 🙂 In this post, we answer the question of whether $\sum_{n=1}^\infty\cos n/n$ converges absolutely or not. Continue reading →

Previously I derived the volume of a hypersphere in $n$ dimensions. A hypersphere with radius $R$ consists of the set of points $\newcommand{\x}{\mathbf{x}}\newcommand{\R}{\mathbb{R}}\x=(x_1,\dotsc,x_n)\in\R^n$ for which \[ \lVert\x\rVert \leq R , \] where $\lVert\x\rVert$ denotes the usual Euclidean norm (also known as the 2-norm), \[ \lVert\x\rVert := \sqrt{x_1^2+\dotsb+x_n^2} . \] Today, I’d like to consider the problem of computing the volume of an $n$-dimensional hyphersphere in the 1-norm (also known as the Manhattan distance or taxicab norm), which is defined by \[ \lVert\x\rVert_1 := \lvert x_1\rvert+\dotsb+\lvert x_n\rvert . \] The volume of the 1-norm hypersphere is given by the expression \[ V_n(R) := \frac{(2R)^n}{n!} , \] as we will show by induction on $n$. In the base case $n=1$ one has \[ \newcommand{\d}{\,\mathrm{d}} V_1(R) = \int_{-R}^R\d x_1 = 2R , \] as required. Now suppose that the formula holds in dimension $n-1$. Then we have \begin{align*}
V_n(R) &= \int\limits_{\lvert x_1\rvert\leq R}\;\int\limits_{\lvert x_1\rvert+\lvert x_2\rvert\leq R}\dotsi\int\limits_{\lvert x_1\rvert+\dotsb+\lvert x_n\rvert\leq R}\d x_n\dotsm\d x_1 \\
&= \int\limits_{\lvert x_1\rvert\leq R}\;\int\limits_{\lvert x_2\rvert\leq R-\lvert x_1\rvert}\dotsi\int\limits_{\lvert x_2\rvert\dotsb+\lvert x_n\rvert\leq R-\lvert x_1\rvert}\d x_n\dotsm\d x_1 \\
&= \int\limits_{\lvert x_1\rvert\leq R} V_{n-1}\bigl(R-\lvert x_1\rvert\bigr) \d x_1 \\
&= \int_{-R}^R \frac{2^{n-1}(R-\lvert x_1\rvert)^{n-1}}{(n-1)!} \d x_1 \\
&= 2\int_{0}^R \frac{2^{n-1}(R-x_1)^{n-1}}{(n-1)!} \d x_1 \\
&= \frac{2^n}{(n-1)!}\biggl[-\frac{1}{n}(R-x_1)^n\biggr]_0^R \\
&= \frac{(2R)^n}{n!}
\end{align*} By induction, the formula holds for all positive integers $n$.

Last year I asked if the series $\sum_{n=1}^\infty\cos n/n$ converges or diverges. Although the series looks rather simple, the standard convergence tests learned in Calculus 1 do not apply directly. However, there is a trick which allows one to rewrite the series into a form where the standard tests can be used. The trick is to use summation by parts, the discrete analog of integration by parts. Although less well-known, summation by parts does have its uses; for example, it was the method of proving Abel’s summation formula which has come up before. To simplify the exposition, it is convenient to define a function for the partial sums of the series’ numerators: \[ C(m) := \sum_{n=1}^m \cos n \] Now, using summation by parts the series may be rewritten so that \[ \sum_{n=1}^m\frac{\cos n}{n} = \frac{C(m)}{m} + \sum_{n=1}^{m-1} C(n)\Bigl(\frac{1}{n}-\frac{1}{n+1}\Bigr) . \tag{1} \] The key observation to make now is that $C(m)$ is bounded. This can be seen by using the complex exponential expression of the cosine, and summing a geometric series to find a closed-form expression for $C(m)$, as follows: \begin{align*}
C(m) &= \sum_{n=1}^m\frac{e^{in}+e^{-in}}{2} \\
&= \frac{e^i}{2}\Bigl(\frac{e^{im}-1}{e^i-1}\Bigr)+\frac{e^{-i}}{2}\Bigl(\frac{e^{-im}-1}{e^{-i}-1}\Bigr) \\
&= \frac{(e^{im}-1)(1-e^i)+(e^{-im}-1)(1-e^{-i})}{2(e^i-1)(e^{-i}-1)} \\
&= \frac{(e^{im}+e^{-im})-(e^{i(m+1)}+e^{-i(m+1)})}{2(2-(e^i+e^{-i}))}-\frac{1}{2} \\
&= \frac{\cos m-\cos(m+1)}{2(1-\cos1)}-\frac{1}{2}
\end{align*} By the triangle inequality, this has an absolute upper bound of \[ \lvert C(m)\rvert \leq \frac{1}{1-\cos1}+\frac{1}{2}<3 . \] From this it follows that $C(m)/m\to0$ as $m\to\infty$, and after taking the limit (1) becomes \[ \sum_{n=1}^\infty\frac{\cos n}{n} = \sum_{n=1}^\infty{}C(n)\Bigl(\frac{1}{n}-\frac{1}{n+1}\Bigr) , \tag{2} \] and we can use the absolute comparison test on the right sum. Using the fact that \[ \frac{1}{n}-\frac{1}{n+1} = \frac{1}{n^2+n} \leq \frac{1}{n^2} \] we have $\bigl\lvert C(n)(\frac{1}{n}-\frac{1}{n+1})\bigr\rvert<3/n^2$, and $\sum_{n=1}^\infty 3/n^2=3\zeta(2)$ is absolutely convergent, so by the comparison test the right sum in (2) is absolutely convergent as well. Thus the left side of (2) must converge, so $\sum_{n=1}^\infty\cos n/n$ converges.

Minkowski’s theorem says that if $S$ is a convex set in $\newcommand{\R}{\mathbb{R}}\R^n$ which is symmetric about the origin and has volume $V(S)>2^n$ (or if $S$ is compact and $V(S)\geq2^n$) then $S$ contains some nonzero point of $\newcommand{\x}{\mathbf{x}}\newcommand{\Z}{\mathbb{Z}}\Z^n$. Minkowski’s theorem can be seen as a simple consequence of Blichfeldt’s theorem. In particular, consider applying its statement to the set $S/2:=\{\,s/2:s\in S\,\}$. Since \[V(S/2)=V(S)/2^n>1\] (or if $S$ is compact, $V(S/2)\geq1$) the theorem says that there exist distinct $\x_1$, $\x_2\in S/2$ with $\x_1-\x_2\in\Z^n$. Say that these have the form $\newcommand{\s}{\mathbf{s}}\x_1=\s_1/2$ and $\x_2=\s_2/2$ where $\s_1$, $\s_2\in S$. Since $S$ is symmetric about the origin, it follows that $-\s_2\in S$. Additionally, since $S$ is convex, it follows that the midpoint of $\s_1$ and $-\s_2$ is also in $S$. But this midpoint $(\s_1-\s_2)/2=\x_1-\x_2$ is also in $\Z^n$. Since $\x_1\neq\x_2$ this point is nonzero, as required. Using the form of Blichfeldt’s theorem applied to general lattices $L$ of dimension $n$, one finds that if $S$ is a convex and symmetric set in $\R^n$ with volume $V(S)>2^n\det(L)$ (or if $S$ is compact and $V(S)\geq2^n\det(L)$) then $S$ contains a nonzero point of $L$.

The following theorem was proven by Blichfeldt¹ in 1914: Let $P$ be a set of points in $\newcommand{\R}{\mathbb{R}}\R^n$ which are invariant under translation by vectors in $\newcommand{\Z}{\mathbb{Z}}\Z^n$, and say that $[0,1)^n$ contains $N$ points of $P$. If $S$ is a set in $\R^n$ with volume $V(S)$ then there is some translation $\newcommand{\x}{\mathbf{x}}S+\x$ which contains at least $N\cdot V(S)$ points of $P$. Additionally, if $S$ is compact then there is some translation of $S$ which contains more than $N\cdot V(S)$ points of $P$. To show this, let $\newcommand{\p}{\mathbf{p}}\newcommand{\c}{{,}~}\p_1\c\dotsc\c\p_N$ be the points of $P$ contained in $[0,1)^n$. Since $P$ is invariant under translation by $\Z^n$, every $\p\in P$ is equivalent to some $\p_i$ modulo $\Z^n$. Let $\nu_i(S)$ denote the number of points in $P\cap S$ congruent to $\p_i$, so \[ \newcommand{\y}{\mathbf{y}}\nu_i(S) = \sum_{\y\in\Z^n}\chi_S(\p_i+\y) \] where $\chi_S$ is the characteristic function of $S$. Then \begin{align*}\newcommand{\d}{\,\mathrm{d}}
\int_{[0,1)^n}\nu_i(S+\x)\d\x &= \int_{[0,1)^n}\sum_{\y\in\Z^n}\chi_{S+\x}(\p_i+\y)\d\x \\
&= \int_{[0,1)^n}\sum_{\y\in\Z^n}\chi_S(\p_i+\y-\x)\d\x \\
&= \int_{(-1,0]^n}\sum_{\y\in\Z^n}\chi_S(\p_i+\y+\x)\d\x \\
&= \sum_{\y\in\Z^n}\int_{(-1,0]^n+\p_i+\y}\chi_S(\x)\d\x \\
&= \int_{\R^n}\chi_S(\x)\d\x \\
&= V(S)
\end{align*} where the penultimate step follows since taking the set $(-1,0]^n+\p_i+\y$ for each $\y\in\Z^n$ will produce a tiling of all of $\R^n$ with no overlap. Letting $\nu(S):=\lvert P\cap S\rvert=\sum_{i=1}^N\nu_i(S)$ and summing the above over $1\leq i\leq N$, we find that \[ \int_{[0,1)^n}\nu(S+\x)\d\x = N\cdot V(S) . \] By an averaging argument, there must be some $\x\in[0,1)^n$ such that $\nu(S+\x)/V([0,1)^n)\geq N\cdot V(S)$, i.e., the translation $S+\x$ contains at least $N\cdot V(S)$ points of $P$, as required. Next, we consider the case where $S$ is compact (i.e., closed and bounded). Since $\nu(S+\x)$ is an integer, if $N\cdot V(S)$ is not an integer then it immediately follows that $\nu(S+\x)>N\cdot V(S)$. So suppose that $h:=N\cdot V(S)$ is an integer. Let $S_k:=(1+\frac{1}{k})S$, so that applying the above result on $S_k$ for each $k\geq1$ we have that there exists some $\x_k\in[0,1)^n$ such that $\nu(S_k+\x_k)\geq N\cdot V(S_k)>h$. Since the $\x_k$ lie in $[0,1]^n$ which is compact, there must be some subsequence $\x_{k_j}$ which converges to a point $\x\in[0,1]^n$. By construction, each $S_{k_j}+\x_{k_j}$ contains at least $h+1$ points of $P$. Since $\bigcup_j S_{k_j}+\x_{k_j}$ is bounded, it contains a finite number of points of $P$. In particular, there are a finite number of ways of choosing $h+1$ points of $P$ from $\bigcup_j S_{k_j}+\x_{k_j}$. By the pigeonhole principle, there must be some choice $\p_1\c\dotsc\c\p_{h+1}\in P$ which appear infinitely often in the sets $S_{k_j}+\x_{k_j}$. Let $k’_j$ index a subsequence of these sets so that $\p_i\in S_{k’_j}+\x_{k’_j}$ for all $i$ and $j$. The points $\p_i$ must in fact appear in $S+\x$; otherwise there would be some $\p_i$ with positive distance to $S+\x$, but the distance of the farthest point of $S_{k’_j}+\x_{k’_j}$ to $S+\x$ goes to $0$ as $j\to\infty$, contradicting the supposed positive distance that $\p_i\in S_{k’_j}+\x_{k’_j}$ is away from $S+\x$. As required, we have found some translation $S+\x$ which contains more than $h=N\cdot V(S)$ points of $P$.

Alternate statement

Sometimes Blichfeldt’s theorem is stated in the following form: Let $S$ be a set in $\R^n$ with volume $V(S)>m$ for some $m\in\Z$ (if $S$ is compact we only require $V(S)\geq m$). Then $S$ contains $\x_1\c\dotsc\c\x_{m+1}$ distinct points whose differences $\x_i-\x_j$ all lie in $\Z^n$. This is a simple corollary of what we’ve already shown. Take $P:=\Z^n$, so that $N=1$. The theorem tells us there is some $\x$ such that $S+\x$ contains at least $V(S)\geq m+1$ (or if $S$ is compact, more than $V(S)\geq m$) points of $P$. Thus we have there exist $\p_i\in P$ and $\x_i\in S$ with $\p_i=\x_i+\x$ for $1\leq i\leq m+1$. Then \[ \x_i-\x_j = \p_i-\p_j \in \Z^n , \] as required.

Generalization

Finally, Blichfeldt’s theorem can be generalized to apply to arbitrary lattice points, instead of just $\Z^n$. One possible way of stating it would be: Let $L$ be a lattice in $\R^n$ with volume $\det(L)$, and $S$ be a set in $\R^n$ with volume $V(S)>m\det(L)$ for some $m\in\Z$ (if $S$ is compact we only require $V(S)\geq m\det(L)$). Then $S$ contains $\x_1\c\dotsc\c\x_{m+1}$ distinct points whose differences $\x_i-\x_j$ all lie in $L$. The same argumentation as above suffices to show this, except that we replace $[0,1)^n$ (a fundamental region for $\Z^n$) in the argument with a fundamental region for $L$.