That harmonic series variant absolutely

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{}{\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

The infinite hat problem

The infinite hat problem is a great puzzle. If you have a strong math background, you should try solving it before reading my solution below!

Here’s my strategy for the wizards: first, they agree on an ordering of themselves. Each wizard can be indexed by a natural number, since there are countably many of them. They then consider the set of all possible hat configurations $S$ with respect to that ordering. By the¬†well-ordering theorem¬†(which is equivalent to the axiom of choice) a well-ordering of $S$¬†exists; the wizards also agree on a specific well-ordering.

Note that this step is non-constructive because it relies on the axiom of choice. That is, such a well-ordering exists but there may not be a way to explicitly construct it. The point of the note about assuming the axiom of choice was a tip-off that the wizards need to make their decision based off of a set whose existence is only ensured by the axiom of choice.

Once the well-ordering has been chosen the wizards are ready to receive their hats. Once they are able to see everyone else’s hat, they each construct a¬†subset $T$ of $S$ which contains the hat configurations which differ from the configuration they can see in only finitely many hats. The lack of knowledge about a wizard’s own hat is irrelevant to this construction, since¬†that lack of knowledge only¬†changes the configuration they see in finitely many hats. In particular, for every wizard their subset¬†$T$¬†will consist of the true configuration along with all configurations which differ from the true configuration in finitely many hats, and therefore be the same for all wizards.

Now that all the wizards have constructed the same $T\subset S$, they use the well-ordering of $S$ to find the least element of $T$, and everyone guesses the hat colour which they have in the least element. Since every element of $T$ differs from the true configuration in finitely many hats, the configuration that the wizards guess will also differ in finitely many hats. Thus almost all wizards will choose correctly.

I¬†heard about the problem on a list of good logic puzzles compiled by Philip Thomas. I purposely haven’t read his solution yet,¬†since I didn’t want that to influence me while writing down¬†my solution.

An extended hat puzzle

Shortly after hearing about the hat puzzle I wrote about last month I came across an interesting extension of the problem, which replaces the 100 wizards with an infinite number of wizards:

A countably infinite number of wizards are each given a red or blue hat with 50% probability. Each wizard can see everyone’s hat except their own. The wizards have to guess the colour of their hat without communicating in any way, but will be allowed to devise a strategy to coordinate their guesses beforehand. How can they ensure that only a finite number of them guess incorrectly? You may assume the axiom of choice.

This seems paradoxical since somehow knowing about other wizard’s hats—which are chosen independently from a wizard’s own hat—allows each wizard to conclude that they will almost surely guess their hat colour correctly.

A hat puzzle

I heard about an interesting puzzle recently:

100 wizards are each given either a red or blue hat with 50% probability. Each wizard can see everyone’s hat except their own. The wizards have to guess the colour of their hat without communicating in any way, but will be allowed to devise a strategy to coordinate their guesses beforehand. How can they maximize the probability that all 100 of them guess correctly?

I like this puzzle because at first it seems impossible to do much better than guessing randomly—how could knowing the colour of other people’s hats help you guess the colour of your own, since the colours were chosen independently? However, there is a very simple strategy which allows them to do much better than guessing randomly.

Continue reading

Volume of a hypersphere in the 1-norm

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

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!}

By induction, the formula holds for all positive integers $n$.

Harmonic series variant solution

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:

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}

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

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$.

Blichfeldt’s Theorem

The following theorem was proven by Blichfeldt1 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

\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)

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.


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$.

Two characterizations of a lattice

A lattice¬†is a discrete additive subgroup of $\newcommand{\R}{\mathbb{R}}\R^n$; for the purposes of this post we’ll restrict ourselves to¬†full rank¬†lattices, i.e., those which span the entire vector space $\R^n$. An alternate way of defining a lattice is to consider it as the¬†integer span of a collection of linearly independent vectors $\newcommand{\b}{\mathbf{b}}\newcommand{\c}{{,}~}\b_1\c\dotsc\c\b_n\in\R^n$, known as a basis of $L$. That is, $L$ consists of the collection of points

\[ \newcommand{\norm}[1]{\lVert#1\rVert}\newcommand{\x}{\mathbf{x}}\newcommand{\Z}{\mathbb{Z}} \biggl\{\,\sum_{i=1}^n x_i\b_i : x_i\in\Z \,\biggr\} . \]

The goal of this post is to show that these two ways of defining a lattice are equivalent. It is more or less immediate that a lattice $L$ in the second sense is an additive subgroup which spans $\R^n$; it is also discrete since one can show that1

\[ \newcommand{\0}{\mathbf{0}} \norm{\x} \geq \min_{1\leq i\leq n}\norm{\b_i^*} \]

for all $\x\in L$ and $\x\neq\0$, where $\b_i^*$ is the Gram–Schmidt orthogonalization¬†of $\b_i$. Thus $\0$ is an isolated point of $L$, and it follows that every point of $L$ must be isolated;¬†a nonisolated point would imply (using a suitable translation) that $\0$ is nonisolated.

The harder direction is to show that a lattice in the first sense is also a lattice in the second sense; the remainder of the post is devoted to this. Let $L$ be a discrete additive subgroup of $\R^n$ containing $n$ linearly independent vectors.

In the case $n:=1$, since $L$ spans $\R$ it must contain $\pm a\neq0$. Since it also contains $0$ and is discrete, there must be a minimal $b>0$ with $b\in L$. Then as required we have $L= \{\, xb : x\in\Z \,\}$; if there was any point $c=xb\in L$ for $x\notin\Z$ then $c-\lfloor x\rfloor b$ would lie in $L$ and $(0,b)$, a contradiction to the minimality of $b$.

Now suppose the result holds for all lattices in $\R^{n-1}$; we will show the result holds for $L$ and appeal to induction. We know that $L$ contains $n$ linearly independent vectors; select any $n-1$ of them and let $S$ be the subspace they generate. Let $S’$ be the rotation of $S$ such that every vector in $S’$ has a $0$ in its final coordinate. Crucially, applying the rotation on $L$ to form $L’$ preserves the discrete additive subgroup structure, so we can apply the induction hypothesis to the discrete additive subgroup¬†formed by only considering the first $n-1$ coordinates of $S’\cap L’$. Let $\b_1\c\dotsc\c\b_{n-1}$ be a basis of this lattice (which exists by hypothesis), except extended with an extra $0$ coordinate so as to live in $\R^n$ instead of $\R^{n-1}$.

Since $L’$ generates $\R^n$, it must contain a vector not in $S’$, i.e., with nonzero final coordinate. Furthermore, it must contain a vector with minimal positive final coordinate; otherwise there would exist a sequence $\newcommand{\N}{\mathbb{N}}\{\x_i\in L’\}_{i\in\N}$ with $(x_i)_n\to0$ as $i\to\infty$. By translating the $\x_i$ by suitable multiples of $\b_1\c\dotsc\c\b_{n-1}$ we can ensure that they lie in the compact set

\[ \biggl\{\, \sum_{i=1}^{n-1} \alpha_i \b_i + (0,\dotsc,0,\alpha) : \alpha_i\in[0,1]\c\lvert \alpha\rvert\leq\max_{i\in\N}\lvert(x_i)_n\rvert \,\biggr\} , \]

and therefore some subsequence of the $\x_i$ converges to some point in the set. Taking successive differences of this subsequence we get a sequence of points in $L’$ which converge to $\0\in L’$, a contradiction to the discreteness of $L’$.

Let $\b_n\in L’$ be a vector with minimal nonzero final coordinate. We claim that $\b_1\c\dotsc\c\b_n$ is a basis for $L’$. Let $\x\in L’$ be arbitrary, and consider

\[ \x’ := \x – \biggl\lfloor \frac{x_n}{(b_n)_n} \biggr\rfloor \b_n \in L’ . \]

Its final coordinate is $x_n-\lfloor x_n/(b_n)_n\rfloor(b_n)_n\in[0,(b_n)_n)$ and therefore by minimality of $(b_n)_n$ it must be $0$, so $\x’\in S’\cap L’$ and therefore can be written as an integer combination of $\b_1\c\dotsc\c\b_{n-1}$. Thus $\x=\x’+\lfloor x_n/(b_n)_n\rfloor\b_n$ can be written as an integer linear combination of $\b_1\c\dotsc\c\b_n$, and so these vectors form a basis of $L’$. Applying the reverse rotation of $L\mapsto L’$ to the basis¬†$\b_1\c\dotsc\c\b_n$ gives us a basis of $L$, as required.

  1. To see this, write $\x = \sum_{i=1}^n x_i \b_i = \sum_{i=1}^n x_i^* \b_i^*$. Let $k$ be the largest $i$ such that $x_i\neq0$, so $\DeclareMathOperator{\sp}{span} \x \in x_k \b_k^* + \sp(\b_1,\dotsc,\b_{k-1})$ which shows that $x_k^*=x_k\in\Z$. Then

    \begin{equation}\norm{\x}^2 = \sum_{i=1}^k (x_i^*)^2 \norm{\b_i^*}^2 \geq (x_k^*)^2 \norm{\b_k^*}^2 \geq \min_{1\leq i\leq n} \norm{\b_i^*}^2 , \end{equation}

    as required.

A year of Simple Go

A year ago today I made the first commit to the Git repository of Simple Go. Coincidentally, I finished the new release I’ve been working on almost exactly one year after the first commit. The major new features in the latest version are a simplified status bar, a settings dialog window, and the use of a configuration file to store settings.

Additionally, with the new settings dialog comes the ability to control more settings, including the player names (to be stored in SGF files), setting GNU Go to control either Black or White (or both), controlling the number of seconds GNU Go can use to make a move or score the game, and specifying the komi value.

At this point, Simple Go does more or less everything I’d envisioned when I first started the project. Of course, I will continue to fix bugs and add new features when inspiration strikes, but at this point I’m happy with how Simple Go turned out, and will use it to record my games. So there you have it — from idea to realization in one year!