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!

A curious hypersphere property

Last time when I derived the formula for the volume of a hypersphere in $n$ dimensions I forgot to point out a curious consequence of the formula, namely that the volume tends to zero as $n$ tends to infinity.

When I was an undergraduate I remember a professor of mine pointing this out and then declaring “That doesn’t make sense!”. At the time it didn’t seem too surprising to me, since I could see that the unit circle in $\newcommand{\R}{\mathbb{R}}\R^2$ took up more of the surrounding square $[-1,1]^2$ than the unit sphere in $\R^3$ took up of $[-1,1]^3$. Consquently, I thought it likely that the ratio of the volume of the unit sphere in $\R^n$ to the volume of $[-1,1]^n$ should go to zero as $n\to\infty$.

However, I misunderstood the claim being made: not only does the above ratio of hypersphere-to-hypercube volume go to zero, the volume of the hypersphere itself goes to zero. This was something I hadn’t even considered: since as $n\to\infty$ the hypersphere is “growing”, I presumably took for granted that its volume should go to infinity, not zero!

Of course, one can consider the unit sphere in $\R^{n-1}$ as a subset of the unit sphere in $\R^n$, since for example the unit sphere in $\R^3$ contains the unit circle as a “slice”. In this way as $n\to\infty$ the hypersphere is growing. However, though the “slice” has volume in $\R^{n-1}$, it has no volume in $\R^n$; as the dimension increases it becomes “harder” to make volume in a sense. This allows the hypersphere to “grow” as $n\to\infty$ while still shrink in volume.

Algebraically, as we’ve seen, the volume of the unit sphere in $\R^n$ is given by

\[ V_n = \frac{\pi^{n/2}}{(n/2)!} . \]

If one knows Stirling’s approximation

\[ n! \sim \sqrt{2\pi n}\Bigl(\frac{n}{e}\Bigr)^n \]

then it isn’t too hard to see that the denominator of $V_n$ grows asymptotically faster than the numerator, and therefore $V_n$ tends to $0$. Explicitly, we have

\[ \lim_{n\to\infty} V_n = \lim_{n\to\infty}\frac{\pi^{n/2}}{\sqrt{\pi n}(\frac{n}{2e})^{n/2}} = \lim_{n\to\infty}\frac{1}{\sqrt{\pi n}}\cdot\lim_{n\to\infty}\Bigl(\frac{2\pi e}{n}\Bigr)^{n/2} = 0 \]

since $\lim_{n\to\infty}1/\sqrt{\pi n}=0$ and

\[ \lim_{n\to\infty}\Bigl(\frac{2\pi e}{n}\Bigr)^{n/2} = \lim_{n\to\infty}\exp\Bigl(\frac{n}{2}\ln\Bigl(\frac{2\pi e}{n}\Bigr)\Bigr) = \lim_{m\to-\infty}\exp(m) = 0 . \]

Volume of a hypersphere

The volume of a hypersphere with radius $R$ in $n$ dimensions is given by the expression1

\[ V_n(R) = \frac{\pi^{n/2}}{(n/2)!} R^n . \]

We will show this by induction on $n$. The base cases can be checked directly, where we make use of polar coordinates in two dimensions:

V_1(R) = \int_{-R}^R\newcommand{\d}{\,\mathrm{d}}\d x = 2R = \frac{\pi^{1/2}}{(1/2)!} R \\
V_2(R) = \iint\limits_{x_1^2+x_2^2\leq R^2}\d x_2\d x_1 = \int_0^{2\pi}\int_0^R r\d r\d\theta = 2\pi\biggl[\frac{r^2}{2}\biggr]_0^R = \pi R^2

Suppose the formula holds in dimension $n-2$. Using this, we will show that the formula holds in dimension $n$:

V_n(R) &= \int\limits_{x_1^2\leq R^2}\;\int\limits_{x_1^2+x_2^2\leq R^2}\;\int\limits_{x_1^2+x_2^2+x_3^2\leq R^2}\dotsi\int\limits_{x_1^2+\dotsb+x_n^2\leq R^2}\d x_n\dotsm\d x_1 \\
&= \int\limits_{x_1^2\leq R^2}\;\int\limits_{x_1^2+x_2^2\leq R^2}\;\int\limits_{x_3^2\leq R^2-x_1^2-x_2^2}\dotsi\int\limits_{x_3^2+\dotsb+x_n^2\leq R^2-x_1^2-x_2^2}\d x_n\dotsm\d x_1 \\
&= \int\limits_{x_1^2\leq R^2}\;\int\limits_{x_1^2+x_2^2\leq R^2}V_{n-2}\Bigl(\sqrt{R^2-x_1^2-x_2^2}\Bigr)\d x_2\d x_1 \\
&= \frac{\pi^{n/2-1}}{(n/2-1)!}\iint\limits_{x_1^2+x_2^2\leq R^2}\sqrt{R^2-x_1^2-x_2^2}^{n-2}\d x_2\d x_1 \\
&= \frac{\pi^{n/2-1}}{(n/2-1)!}\int_0^{2\pi}\int_0^R\sqrt{R^2-r^2}^{n-2}r\d r\d\theta \\
&= \frac{2\pi^{n/2}}{(n/2-1)!}\biggl[-\frac{1}{n}\sqrt{R^2-r^2}^n\biggr]_0^R \\
&= \frac{\pi^{n/2}}{(n/2)!} R^n

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

  1. As one might expect, the factorial with a noninteger argument is simply notation for the gamma function, i.e., $n!:=\Gamma(n+1)$.

Double logarithm summation over primes

It is well known1 that

\[ \sum_{p\leq x}\ln p = x + O\biggl(\frac{x}{e^{c\sqrt{\ln x}}}\biggr) \]

where $c>0$ is a constant and the summation runs over the primes. In fact, under the Riemann hypothesis, one even has

\[ \sum_{p\leq x}\ln p = x + O(x^{1/2+\epsilon}) \]

for any $\epsilon>0$. Since $e^{c\sqrt{\ln x}}$ grows slower than any power of $x$, the second statement gives a better approximation.

A related question, but one I wasn’t familiar with, is to give a similar asymptotic result for the summation with $\ln p$ replaced by $\ln\ln p$. In other words, to estimate the quantity

\[ \sum_{p\leq x}\ln\ln p . \]

To do this, we may employ Abel’s summation formula with

\[ a_n := \begin{cases}
1 & \text{if $n$ is prime} \\
0 & \text{otherwise}
\end{cases} \]

and $\phi(n):=\ln\ln n$. Then we have

\[ \sum_{p\leq x}\ln\ln p = \pi(x)\ln\ln x-\int_2^x\frac{\pi(t)}{t\ln t}\mathrm{d}t . \]

By the prime number theorem we have $\pi(t)=t/\ln t+O(t/\ln(t)^2)$, so

\[ \int_2^x\frac{\pi(t)}{t\ln t}\mathrm{d}t = \int_2^x\frac{\mathrm{d}t}{\ln(t)^2}+O\biggl(\int_2^x\frac{\mathrm{d}t}{\ln(t)^3}\biggr) . \]

By Wolfram Alpha we have that

\[ \int_2^x\frac{\mathrm{d}t}{\ln(t)^2} = \DeclareMathOperator{\li}{li}\li(x)-\frac{x}{\ln x} + O(1) = \frac{x}{\ln(x)^2} + O\biggl(\frac{x}{\ln(x)^3}\biggr) , \]

with the latter equality following from the asymptotic expansion of the logarithmic integral.

It remains to estimate the integral $\int_2^x\ln(t)^{-3}\,\mathrm{d}t$. Actually, this is not entirely straightforward, but a trick is to split the integral into two (around $\sqrt{x}$) and then estimate each, as follows:

\[ \int_2^{\sqrt{x}}\frac{\mathrm{d}t}{\ln(t)^3} + \int_{\sqrt{x}}^x\frac{\mathrm{d}t}{\ln(t)^3} \leq \frac{\sqrt{x}-2}{\ln(2)^3} + \frac{x-\sqrt{x}}{\ln(\sqrt{x})^3} = O\biggl(\frac{x}{\ln(x)^3}\biggr) \]

Putting everything together, we find the result

\[ \sum_{p\leq x}\ln\ln p =\pi(x)\ln\ln x-\frac{x}{\ln(x)^2} +O\biggl(\frac{x}{\ln(x)^3}\biggr) . \]

  1. For example, see (2.29) in Approximate formulas for some functions of prime numbers by Rosser and Schoenfeld.