Number Theory Reading Group

Geometry of Numbers, Lecture 4: Lagrange’s Four Squares Theorem (Mike)

May 22, 2008 in Uncategorized | by mikepharvey | Leave a comment

We aim to give a proof of the following theorem, by using Minkowski’s First Theorem.

Theorem (Lagrange)

Every positive integer is the sum of four squares.

To establish this theorem, we shall require 3 lemmata.

Lemma 1

Let $m$ be an odd positive integer, then there exist $a,b \in \mathbb{Z}$ s.t.

$a^{2}+b^{2}+1 \equiv 0 \pmod{m}$ .

Proof
We split into 3 cases.
(i) $m = p$ , an odd prime.

Let

$A = \{a^{2}, a=0,1,\ldots,(p-1)/2\},$
$B = \{-b^{2}-1, b=0,1,\ldots,(p-1)/2\}.$

Clearly $|A| = |B| = (p+1)/2$ and the elements of $A$ (resp. $B$ ) are pairwise incogruent modulo $p$ . To see this,
assume $a, a' \in A$ satisfy $a^{2} \equiv a'^{2} \pmod{p}$ . Clearly $a' \equiv 0 \Rightarrow a \equiv 0$ . Assume
$a' \not\equiv 0 \pmod{p}$ . Then $(aa'^{-1})^{2} \equiv 1 \pmod{p}$ . By Lagrange’s theorem,

$x^{2} \equiv 1 \pmod{p}$

has only 2 solutions, and these are $-1$ and $1$ . If $aa'^{-1} \equiv -1 \pmod{p}$ , then $a \equiv -a' \pmod{p}$ , which is a contradiction to how $A$ was defined.

So $aa'^{-1} \equiv 1 \pmod{p}$ , and hence $a \equiv a' \pmod{p}$ . Similarly for $B$ .

So by the pigeonhole priniciple, the 2 sets can’t be distinct, and it follows that there exist integers $a,b$ such that $a^{2} + b^{2} + 1 \equiv 0 \pmod{p}$ .

(ii) $m = p^{k}, k\geq 1$ , $p$ odd prime.

We proceed by induction. We have the case $k=1$ from before. For some $k \geq 1$ , assume there exist integers $a,b$ such that

$a^{2} + b^{2} +1 \equiv 0 \pmod{p^{k}}$ .

Then there exists some integer $s$ such that

$a^{2} + b^{2} +1 = sp^{k}$ .

Clearly $p$ cant divide both $a$ and $b$ . Assume $a \not\equiv 0 \pmod{p}$ . Then we have $(2a,p)=1$ , and so there exists some integer $t$ such that $s+2at \equiv 0 \pmod{p}$ . This can be found by solving the equation.

Let $a_{1} = a + tp^{k}$ .

Then we have

$a_{1}^{2} = a^{2} + 2atp^{k} +t^{2}p^{2k}$
$=-b^{2} -1 +sp^{k}+2atp^{k} +t^{2}p^{2k}$
$\equiv -b^{2} -1 + (s+2at)p^{k} \pmod{p^{k+1}}$
$\equiv -b^{2} -1 \pmod{p^{k+1}}.$

Hence this case follows by induction.

(iii) $m$ is an odd positive integer

The case $m=1$ is trivial. So let

$m = \prod_{i=1}^{r}p_{i}^{k_{i}},$

where the $p_{i}$ are odd primes, and $k_{i} \geq 1$ are integers.

Then for each $i$ , we have integers $a_{i},b_{i}$ such that

$a_{i}^{2} + b_{i}^{2} +1 \equiv 0 \pmod{p_{i}^{k_{i}}}.$

We can then use the Chinese remainder theorem to find integers $a,b$ such that

$a \equiv a_{i} \pmod{p_{i}^{k_{i}}}, b \equiv b_{i} \pmod{p_{i}^{k_{i}}}$

for each $1 \leq i \leq r$ . It follows that

$a^{2} + b^{2} + 1 \equiv 0 \pmod{m}.$

Lemma 2
If every odd positive integer is the sum of four squares, then every positive integer is the sum of four squares.

Proof
If some integer $n$ is the sum of four squares, say

$n= a^{2} + b^{2} + c^{2} +d^{2}.$

Then we have

$2n = (a+b)^{2} + (a-b)^{2} + (c+d)^{2} + (c-d)^{2}.$

We can continue like this to show that $2^{k}n$ is the sum of four squares for any $k \geq 0$ .
As any positive integer is of the form $2^{k}n$ , for some $k \geq 0$ , and some odd integer $n$ , the lemma follows.

Lemma 3
Let $B_{r}(\textbf{0})$ be the ball of radius $r$ in $\mathbb{R}^{4}$ . Then

$\text{vol}(B_{r}(\textbf{0}))= \pi^{2}r^{4}/2.$

Proof
It is not hard to see that the volume of this ball is equal to

$\int_{-r}^{r}\frac{4}{3}\pi(r^{2}-z^{2})^{3/2}\text{d}z.$

Solve this by using the substitution $z = r\sin{\theta}$ .

We are now ready to prove the main theorem
Proof
By lemma 2, it suffices to prove for odd positive integers. Let $m$ be an odd positive integer. By lemma 1, there exist integers $a,b$ such that

$a^{2} + b^{2} + 1 \equiv 0 \pmod{m}.$

Let $\Gamma \subset \mathbb{Z}^{4}$ be the lattice with basis vectors

$\textbf{a}_{1} = (m,0,0,0)$
$\textbf{a}_{2} = (0,m,0,0)$
$\textbf{a}_{3} = (a,b,1,0)$
$\textbf{a}_{4} = (b,-a,0,1).$

We have $\text{det}(\Gamma) = m^{2}$ , and $u \in \Gamma$ can be written as

$\textbf{u} = u_{1}\textbf{a}_{1} +u_{2}\textbf{a}_{2} +u_{3}\textbf{a}_{3} +u_{4}\textbf{a}_{4}$
$(u_{1}m+u_{3}a+u_{4}b)\textbf{e}_{1}+(u_{2}m+u_{3}b-u_{4}a)\textbf{e}_{2}+u_{3}\textbf{e}_{3}+u_{4}\textbf{e}_{4},$

with $u_{1},\ldots,u_{4} \in \mathbb{Z}$ .
So

$|\textbf{u}|^{2} = (u_{1}m+u_{3}a+u_{4}b)^{2} + (u_{2}m+u_{3}b-u_{4}a)^{2} + u_{3}^{2} + u_{4}^{2}$
$\equiv u_{3}(a^{2} + b^{2} + 1) + u_{4}(a^{2} + b^{2} + 1) \pmod{m}$
$\equiv 0 \pmod{m},$

for all $\textbf{u} \in \Gamma$ .

Let $K = B_{\sqrt{2m}}(\textbf{0})$ be the ball of radius $2m$ in $\mathbb{R}^{4}$ . It is clear this is a symmetric convex body, amd has volume

$2\pi^{2}m^{2} > 16m^{2} = 2^{4}\text{det}(\Gamma)$ .

Hence we can apply Minkowski’s first theorem, and we have $K$ contains some non-trivial lattice point

$\textbf{u} = u_{1}\textbf{a}_{1} +u_{2}\textbf{a}_{2} +u_{3}\textbf{a}_{3} +u_{4}\textbf{a}_{4}$
$= v_{1}\textbf{e}_{1} + v_{2}\textbf{e}_{2} + v_{3}\textbf{e}_{3} + v_{4}\textbf{e}_{4},$

for integers $u_{1},\ldots,u_{4},v_{1},\ldots,v_{4}$ .
Now we have

$|\textbf{u}|^{2}\equiv 0 \pmod{m},$

and we have

$0 < |\textbf{u}|^{2} < 2m,$

since $\textbf{u} \in K.$ So it follows that $|\textbf{u}|^{2} = m,$ and therefore

$m = v_{1}^{2} + v_{2}^{2} + v_{3}^{2} + v_{4}^{2}.$

This proves the theorem.

Geometry of Numbers, Lecture 6: Some results from the Geometry of Numbers (Lee and Sean)

May 21, 2008 in Uncategorized | by Lee | Leave a comment

The Two Squares theorem

Let $p$ be prime. If $p\equiv1\pmod4$ then $p$ is the sum of two squares.

Proof We’ll show that if $m\in\mathbb{N}$ and there is $\ell\in\mathbb{Z}$ such that $\ell^2\equiv-1\pmod{m}$ then there exist $u,v\in\mathbb{Z}$ such that $m=u^2+v^2$ . In particular if $m=p\equiv1\pmod{4}$ then -1 is a quadratic residue mod p so p is the sum of two squares.

Let

$\Lambda=\{(x,y)\in\mathbb{Z}^2\mid x\equiv\ell y\pmod{m}\}\subseteq\mathbb{Z}^2.$

We can assume that $0<\ell<m$ . Since $\ell^2\equiv-1\pmod{m}$ there is a $k\in\mathbb{Z}$ such that $\ell^2=km-1$ . For a basis of $\Lambda$ we take

$v_0=(\ell,1)\qquad v_1=((k-1)m-1,\ell).$

That these form a basis is left as an exercise. The determinant of the lattice is then:

$\det(\Lambda)=\left|\left|\begin{array}{ c c }\ell & (k-1)m-1 \\ 1 & \ell \end{array}\right|\right|$
$=|\ell^2-(k-1)m+1|$
$=|km-1-km+m+1|$
$=m.$

Now let

$S=\{(x,y)\in\mathbb{R}^2\mid x^2+y^2\leq 2m\}.$

This is convex and symmetric and

$\textrm{vol}(S)=\pi\sqrt{2m}^2=2\pi m > 2^2m.$

So by Minkowski I, there exists $(u,v)\in S\cap\Lambda^\ast$ . Since $(u,v)\in\Lambda^\ast$ we know

$0<u^2+v^2<2m,$

and

$u\equiv \ell v\pmod m$

$u^2\equiv(\ell v)^2\pmod m$
$\equiv -v^2\pmod m.$

Thence

$u^2+v^2\equiv0\pmod m,$

and so

$u^2+v^2=m.$

The Local-Global Principle for Diagonal Ternary Quadratic Forms

Let $a_1,a_2,a_3\in\mathbb{Q}^\ast$ and set

$C:F(\boldsymbol{x})=a_1x_1^2+a_2x_2^2+a_3x_3^2=0.$

If $C(\mathbb{Q}_p)\neq0$ for all p then $C(\mathbb{Q})\neq0$ .

Proof
Wlog we may assume $a_1,a_2,a_3\in\mathbb{Z}^\ast$ , $\textrm{hcf}(a_1,a_2,a_3)=1$ , $a_1,a_2,a_3$ square-free, and $\textrm{hcf}(a_i,a_j)=1$ whenever $i\neq j$ .

Plan:

Define a lattice $\Lambda\subseteq\mathbb{Z}^3$ with $\det(\Lambda)\leq4|a_1a_2a_3|$ and such that $F(\boldsymbol{x})\equiv0\pmod{4|a_1a_2a_3|}$ for all $\boldsymbol{x}\in\Lambda$ .
Let $D=\{(x_1,x_2,x_3)\in\mathbb{R}^3 : |a_1|x_1^2+|a_2|x_2^2+|a_3|x_3^2<4|a_1a_2a_3| \}.$
D is convex and symmetric and $\textrm{vol}(D)=\pi\slash3 (2^3)(4|a_1a_2a_3|)>2^3\det(\Lambda)$ (exercise).
By Minkowski I there is $\boldsymbol{x}\in D\cap\Lambda^\ast$ , same reasoning as last theorem gives $F(\boldsymbol{x})=0$ .

So all we need to do is construct $\Lambda$ . Write $|a_1a_2a_3|=2^\lambda p_1p_2\cdots p_g$ , where the $p_i$ are distinct and $\lambda=0$ or $1$ . There are three parts.

(i) Let p be one of the $p_1,\ldots,p_g$ , so $p\mid a_1a_2a_3$ . Wlog say $p\mid a_1$ . So if

$a_1x_1^2+a_2x_2^2+a_3x_3^2=0$

then

$a_2x_2^2+a_3x_3^2\equiv 0\pmod p.$

By hypothesis there exists a p-adic solution to our equation, say $\alpha_1,\alpha_2,\alpha_3\in\mathbb{Q}_p$ such that

$a_1\alpha_1^2+a_2\alpha_2^2+a_3\alpha_3^2=0.$

We may assume that $\alpha_1,\alpha_2,\alpha_3\in\mathbb{Z}_p$ and that $p$ doesn’t divide all of them. Since

$a_2\alpha_2^2+a_3\alpha_3^2\equiv0\pmod p$

we must have $p\nmid \alpha_2\alpha_3$ , otherwise p will divide all three. Impose the condition on $\boldsymbol{x}\in\mathbb{Z}^3$ ,

$\alpha_3x_2\equiv-\alpha_2x_3\pmod p.$

If $\boldsymbol{x}\in\mathbb{Z}^3$ satisfies this condition then

$F(\boldsymbol{x})=a_1x_1^2+a_2x_2^2+a_3x_3^2$
$\equiv a_2x_2^2+a_3x_3^2\pmod p$
$\equiv a_2\left(-\frac{\alpha_2}{\alpha_3}x_3\right)^2+a_3x_3^2\pmod p$
$\equiv \frac{x_3^2}{\alpha_3^2}(a_2\alpha_2^2+a_3\alpha_3^2)\pmod p$
$\equiv 0\pmod p .$

(ii) Suppose $\lambda=0$ , so $a_1,a_2,a_3$ are all odd. We know there exist $\beta_1,\beta_2,\beta_3\in\mathbb{Z}_2$ such that

$a_1\beta_1^2+a_2\beta_2^2+a_3\beta_3^2=0.$

We also know $b^2\equiv\begin{cases}0\textrm{ if }b\textrm{ is even}\\1\textrm{ if }b\textrm{ is odd}\end{cases}\pmod4$ . Exactly one of $\beta_1,\beta_2,\beta_3$ must be even, wlog say $\beta_3$ . Then

$0\equiv a_1\beta_1^2+a_2\beta_2^2+a_3\beta_3^2\equiv a_1+a_2\pmod4.$

Impose the conditions

$\begin{cases}x_1\equiv x_2\pmod 2\\x_3\equiv0\pmod2\end{cases}.$

Then

$F(\boldsymbol{x})=a_1x_1^2+a_2x_2^2+a_3x_3^2$
$\equiv a_1x_1^2+a_2x_2^2\pmod4$
$\equiv(a_1+a_2)x_1^2\pmod4$
$\equiv0\pmod4.$

(iii) Suppose $\lambda=1$ , so one of $a_1,a_2,a_3$ is even, say $a_3$ . We know there exist $\gamma_1,\gamma_2,\gamma_3\in\mathbb{Z}_2$ such that

$a_1\gamma_1^2+a_2\gamma_2^2+a_3\gamma_3^2=0.$

In particular

$a_1\gamma_1^2+a_2\gamma_2^2+a_3\gamma_3^2\equiv0\pmod2$

so that $a_1\gamma_1^2+a_2\gamma_2^2\equiv0\pmod2$ . Thus either $\gamma_1,\gamma_2$ are both odd or both even. If they’re both even then

$a_3\gamma_3^2=-a_1\gamma_1^2-a_2\gamma_2^2$

is divisible by 4 so $\gamma_3$ will be even, a contradiction. So $\gamma_1,\gamma_2$ are both odd, hence

$0\equiv a_1\gamma_1^2+a_2\gamma_2^2+a_3\gamma_3^2\equiv a_1+a_2+a_3\gamma_3^2\pmod8$

since $c^2\equiv1\pmod8$ for any odd c. Impose the conditions

$\begin{cases}x_1\equiv x_2\pmod8\\x_3\equiv\gamma_3 x_1\pmod8.\end{cases}$

Then

$F(\boldsymbol{x})=a_1x_1^2+a_2x_2^2+a_3x_3^2$
$\equiv a_1x_1^2+a_2x_1^2+a_3\gamma_3^2x_1^2\pmod8$
$\equiv(a_1+a_2+a_3\gamma_3^2)x_1^2\pmod8$
$\equiv0\pmod8.$

These conditions give us $F(x)\equiv0\pmod p$ for any $p\mid 4|a_1a_2a_3|$ as we wanted. Now we just have to check the determinant of $\Lambda$ .

We know that a lattice is a subgroup of $\mathbb{Z}^m$ , and in fact the determinant of the lattice is equal to the index of this subgroup:

$\det(\Lambda)=[\mathbb{Z}^m:\Lambda].$

We’ve defined our lattice in terms of a bunch of congruence conditions. It is a relatively straightforward lemma in group theory that if one has a subgroup I defined by congruences

$\sum_{j=1}^n a_{ij}x_j\equiv0\pmod{p_i}\qquad(1\leq i\leq m)$

then the index of I is at most $\prod_{i=1}^m p_i$ . In our case that means

$\det(\Lambda)\leq2^{2+\lambda}p_1\cdots p_g=4|a_1a_2a_3|.$

As required.

Geometry of Numbers, Lecture 5: Minkowski’s Second Theorem (Duc Khiem)

May 20, 2008 in Uncategorized | Tags: Geometry of Numbers | by Sean | Leave a comment

Recall the corollary to Minkowski’s first theorem (lecture 3).

Minkowski I’. Let K be a non-empty symmetric convex body in $\Bbb R^n$ , $\Gamma$ be a full rank lattice in $\Bbb R^n$ and define

$\lambda_1 := \lambda_1(K, \Gamma) = \inf\{ \lambda > 0 : \lambda\cdot K \cap \Gamma \setminus \{0\} \neq \emptyset \}.$

Then $\lambda_1^n vol(K) \leq 2^n \det (\Gamma).$

It can easily be shown that this corollary is actually equivalent to Minkowski’s first theorem; its advantage is that it is more amenable to generalisation.

Proof that Minkowski I’ implies Minkowski I. Let K be a symmetric convex volume whose volume exceeds $2^n \det(\Gamma).$ We want to show that K contains a point from $\Gamma^* = \Gamma \setminus \{ 0\}.$ By I’ and definition of $\lambda_1$ we must have $\lambda_1 <1.$ Since $\lambda_1$ is the infimum of the set

$\{ \lambda > 0 : (\lambda \cdot K) \cap \Gamma^* \neq \emptyset\},$

there must be some $\lambda \in [\lambda_1, 1)$ satisfying

$(\lambda \cdot K) \cap \Gamma^* \neq \emptyset.$

Since $\lambda \cdot K \subset K,$ it follows that K contains a non-zero point in $\Gamma.$

For a subset S of $\Bbb R^n$ we denote its linear span by $<S>.$

Definition. Let K and $\Gamma$ be as above. For $1 \leq k \leq n$ we set

$\lambda_k:= \lambda_k(K, \Gamma) = \inf \{ \lambda >0 :\ <\lambda\cdot K \cap \Gamma> \text{has dimension } \geq k \}.$

$\lambda_k$ is called the k-th successive minima of K with respect to $\Gamma.$

Notice that $<\lambda\cdot K \cap \Gamma>$ has dimension at least k if and only if $\lambda\cdot K$ contains k linearly independent lattice points of $\Gamma.$ Clearly $0 < \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$ and this new definition of $\lambda_1$ agrees with that given previously.

Minkowski’s Second Theorem. Let K and $\Gamma$ be as above. Then

(1) $\lambda_1 \lambda_2 \dotsm \lambda_n vol(K) \leq 2^n \det(\Gamma).$

This inequality is best possible.

Example. Consider $\Gamma = \Bbb Z^2$ (so $\det (\Gamma) =1$ ) and the rectangle centred at the origin $K = \{ (x_1, x_2) \in \Bbb R^2 : |x_i| < r_i \},$ where $0 < r_2 \leq r_1 \leq 1.$ Then $\lambda_1 = 1/r_1$ and $\lambda_2 = 1/r_2$ . We have $vol(K) = 2^2 r_1 r_2$ , so $\lambda_1 \lambda_2 vol(K) = 2^2 \det(\Gamma)$ .

Proof of Minkowski II. [WORK IN PROGRESS!] By definition of the successive minima, for each $1 \leq i \leq n$ there exists $b_i \in \Gamma$ with $b_i \in \overline{\lambda_i \cdot K} = \lambda_i \cdot \overline{K}$ , $b_i \notin \lambda_i \cdot K$ and $b_1 , \dots, b_i$ linearly independent. We claim that $b_1, \dots, b_n$ form a basis for $\Gamma.$ Suppose otherwise, then it can easily be checked that there must exist $u \in \Gamma$ with $u = t_1 b_1 + \dots + t_n b_n$ where each $|t_i| \leq 1/2$ and at least one $t_i$ is non-zero (take a point of our lattice which is not an integer combination of $b_1, \dots, b_n$ ; this point must be a linear combination of the $b_i$ ; keep subtracting/adding the $b_i's$ until this linear combination has the required form).

Let $T: \Bbb R^n \rightarrow \Bbb R^n$ denote the invertible linear map which takes $b_i$ to the standard basis vector $e_i$ . Then $\Lambda = T(\Gamma)$ is a lattice in $\Bbb R^n$ of full rank and contains $\Bbb Z^n.$ Also $K' := T(K)$ is a symmetric convex body with successive minima $\lambda_1 , \dots , \lambda_n$ (with respect to the lattice $\Lambda).$ Moreover, for each $1 \leq i \leq n,$ we have $e_i \in (\lambda_i \cdot \overline{K'}) \setminus (\lambda_i \cdot K').$

Some notation:

$\displaystyle K_i := \frac{\lambda_i}{2} \cdot K.$
For $q \in \Bbb N$ let $M_q^n = \{ z \in \Bbb Z^n : |z_i| \leq q,\ 1 \leq i \leq n \},$ which is an n-dim box.

Geometry of Numbers, Lecture 3: Convex Bodies, Blichfeldt and Minkowski I (Sean)

April 30, 2008 in Uncategorized | Tags: Geometry of Numbers | by Sean | Leave a comment

Convexity, a reminder

Let V be a vector space over $\Bbb R$ or $\Bbb C$ . A subset $K \subset V$ is

convex if for any two points a, b in K the line segment between a and b $\{ (1- \lambda) a + \lambda b : 0 \leq \lambda \leq 1\}$ is contained in K.
symmetric if $a \in K$ implies $-a \in K$ .

We will be working in $V = \Bbb R^n.$ Here we can define a body in $\Bbb R^n$ to be a bounded open set. Clearly a body is Lebesgue measurable (it is open) and this measure, or ‘volume’, is finite (because the body is bounded). Minkowski’s Theorems concern symmetric convex bodies. Notice that a non-empty symmetric convex body contains some point $a \in K$ and so also contains the convex combination

$0 = \frac{1}{2} a + \frac{1}{2}(-a).$

As K is also open, we have $B_\epsilon (0) \subset K$ for some $\epsilon > 0$ (a fact we will use later).

Blichfeldt’s Lemma

Lemma (Blichfeldt). Let $\Gamma$ be a full rank lattice in $\Bbb R^n$ and let $K \subset \Bbb R^n$ be a body (not necessarily symmetric or convex) with $vol (K) > \det (\Gamma).$ Then there exists a shift of K, v+K, containing at least two points from $\Gamma.$

Define $\Gamma^* := \Gamma \setminus \{0\}.$ Then the usual conclusion of Blichfeldt (easily seen to be equivalent) is

There exists $a,b \in K$ with $a-b \in \Gamma^*.$

Equivalentlty

There exists b in K with $(K-b) \cap \Gamma^* \neq \emptyset.$

Proof of Blichfeldt: In lecture 1 we saw that every lattice is the image of $\Bbb Z^d$ under some map. In particular, $\Gamma$ is countable. We can therefore enumerate $\Gamma$ without repetitions: $g_1, g_2, g_3, \dots$

Let $FP( \Gamma)$ denote the fundamental parallelepiped of $\Gamma$ with respect to some fixed basis. For each i set $F_i := g_i + FP(\Gamma).$ Last week (lecture 2) Lee showed $\Bbb R^n = \bigsqcup_{i=1}^\infty F_i$ (a disjoint union). It follows that $K = \bigsqcup_{i=1}^\infty F_i\cap K$ , another disjoint union. Define $K_i = (F_i \cap K) - g_i.$ Then $K_i \subset FP(\Gamma)$ and each $K_i$ is measurable. Moreover, by translation invariance of Lebesgue measure, $vol(K_i) = vol(F_i \cap K).$ I claim that the $(K_i)_i$ are not disjoint. Suppose otherwise. Lee showed last week that $\det(\Gamma) = vol(FP(\Gamma)).$ By elementary properties of measures we therefore have

$\det(\Gamma) = vol( FP(\Gamma)) \geq vol \left( \bigsqcup_{i=1}^\infty K_i \right)$

$= \sum_i vol(K_i) = \sum_i vol(F_i \cap K) = vol(K),$

a contradiction. Thus $K_i \cap K_j \neq \emptyset$ for some $i \neq j.$ It follows that there exists $a \in F_i \cap K$ and $b \in F_j \cap K$ with $a- g_i = b - g_j.$ But then $a-b = g_i - g_j \in \Gamma^*,$ which completes the proof.

Although the proof doesn’t look very intuitive, the idea is simple: look at the body K ‘mod $\Gamma$ ‘; the resulting set is a subset of the fundamental parallelepiped and so must have volume smaller than $\det(\Gamma)$ ; but then not all residue classes ‘mod $\Gamma$ ‘ can contain 1 or less elements of K, because the volume of K exceeds $\det(\Gamma).$

Minkowski I

We’ve now all the tools in place to prove Minkowski’s first theorem.

Theorem (Minkowski I). Let $\Gamma$ be a full rank lattice in $\Bbb R^n$ and let $K \subset \Bbb R^n$ be a symmetric convex body of volume greater than $2^n\det( \Gamma)$ . Then K contains a non-zero element of $\Gamma.$

Proof. A symmetric convex body has a very convenient property. First, shrink it by a factor of 1/2 along each axis to obtain the dilation

$\frac{1}{2} \cdot K := \{ \frac{1}{2} a : a \in K \}.$

Then any shift of $\frac{1}{2} \cdot K$ by an element of $\frac{1}{2} \cdot K$ is also a subset of K. Re-phrasing this in a more convenient form, it can easily be checked (using convexity and symmetry) that for any $a \in K$ we have

$\frac{1}{2} \cdot K - \frac{1}{2} a \subset K.$

Hence, to prove Minkowski I, it suffices to show there exists $b \in \frac{1}{2} \cdot K$ with $\left(\frac{1}{2} \cdot K - b \right) \cap \Gamma^* \neq \emptyset.$ But this is the conclusion of Blichfeldt’s lemma applied to the body $1/2 \cdot K.$ It therfore suffices to show $vol(1/2 \cdot K) > \det(\Gamma).$ Since $vol(1/2 \cdot K) = 2^{-n} vol(K)$ , the proof is complete.

Minkowski’s first theorem yields the following corollary, which is a baby version of Minkowski’s second theorem.

Corollary. Let $\Gamma$ be a full rank lattice in $\Bbb R^n$ and K a non-empty symmetric convex body. Define the set

$M(K) := \{ \lambda >0 : \lambda \cdot K \cap \Gamma^* \neq \emptyset \}.$

[Notice that M(K) is non-empty, because $B_\varepsilon (0) \subset K$ for some $\varepsilon > 0.$ ]

If $\lambda_1 := \inf M(K)$ then

$\lambda_1^n vol(K) \leq 2^n \det(\Gamma).$ (1)

Proof. Suppose (1) doesn’t hold. Then by Minkowski I, $\lambda_1 \in M(K)$ and so $\lambda_1\cdot K$ contains some non-zero element $g \in \Gamma^*.$ Since K is open, so is the dilation of K by a non-zero factor $\lambda_1 \cdot K.$ It follows that we can find some $\delta>0$ with $(1+\delta)g \in \lambda_1 \cdot K.$ Therefore $g \in \frac{\lambda_1}{1+\delta} \cdot K.$ But then $\frac{\lambda_1}{1+\delta}$ is an element of M(K) smaller than the infimum of M(K), a contradiction. This completes the proof.

Geometry of Numbers, Lecture 2: Determinant of the Lattice and the Fundamental Parallelepiped (Lee)

April 24, 2008 in Uncategorized | Tags: Geometry of Numbers | by Lee | Leave a comment

Sean showed us last time that lattices are additive subgroups of $\mathbb{R}^d$ and that any lattice $\Gamma$ is of the form

$\Gamma=\{\alpha_1 e_1+\ldots +\alpha_k e_k \mid \alpha_i\in\mathbb{Z}, 1\leq i\leq k\}$

for $k$ linearly independent vectors $e_i$ in $\mathbb{R}^d$ . The number $k$ is called the rank of $\Gamma$ . If $k=d$ then we say that $\Gamma$ has full rank. The vectors $e_1,\ldots,e_k$ are called a basis for $\Gamma$ .

Example Take $e_1=(1,1)$ and $e_2=(1,0)$ . These are linearly independent in $\mathbb{R}^2$ so form a lattice $\Gamma$ of full rank in $\mathbb{R}^2$ .

This lattice looks like (and is) $\mathbb{Z}^2$ . We can also think of $e_1, e_2$ as vectors in $\mathbb{R}^3$ :

$e_1=(1,1,0)\qquad e_2=(1,0,0).$

They’re still linearly independent so form the basis of a lattice, but this lattice won’t have full rank.

In the above example we noticed that the lattice with basis $(1,1), (1,0)$ looked just like $\mathbb{Z}^2$ . And clearly any vector $(a,b)\in\mathbb{Z}^2$ can be written as

$(a-b)\binom{1}{0}+b\binom{1}{1},$

so $\Gamma=\mathbb{Z}^2$ . And in fact infinitely many pairs of basis vectors give the same lattice, so it would be helpful if these lattices had some kind of invariant which didn’t depend on the choice of basis, and indeed they do.

Given a set of $d$ vectors and a basis in $\mathbb{R}^d$ we can write the vectors in a matrix by making the columns the vectors with respect to the basis. For example the vectors $(1,3)$ and $(4,7)$ using the standard basis in $\mathbb{R}^2$ can be put in the matrix

$\left(\begin{array}{ c c }1 & 4 \\ 3 & 7\end{array}\right).$

Changing the order of our vectors or the order of our basis will change the matrix, but not the matrix’s determinant. Moreover this determinant is always nonzero provided our vectors are linearly independent. So perhaps the determinant of this matrix is the invariant we’re looking for, but first we need to show that different bases for our lattice give the same determinant.

Let’s let $\{a_1,\ldots,a_n\}$ and $\{a_1^\prime,\ldots,a_n^\prime\}$ be two bases for the same lattice $\Gamma$ . Since they proffer the same lattice any vector from one of the sets can be written in terms of the other set, that is to say for each $i,j=1,\ldots,n$ there exist integers $u_{ij}$ and $v_{ij}$ such that

$a_j^\prime=\sum_{i=1}^{n}u_{ij}a_i$

and

$a_j=\sum_{i=1}^n v_{ij}a_i^\prime.$

Then we can write the vectors in terms of themselves as follows

$a_j=\sum_{k=1}^n v_{kj}a_k^\prime$

$=\sum_{k=1}^n v_{kj}\sum_{i=1}^n u_{ik}a_i$

$=\sum_{i=1}^n\left(\sum_{k=1}^n u_{ik}v_{kj}\right)a_i .$

The vectors are linearly independent so the sum inside the brackets must be zero whenever $i\neq j$ , and one when $i=j$ . Similarly, using the other set of vectors, we have

$\sum_{k=1}^n v_{ik}u_{kj}=\delta_{ij}.$

If we let $U$ and $V$ be the matrices $(u_{ij})$ and $(v_{ij})$ respectively then the above tells us that $U=V^{-1}$ . And since they have integer entries the fact that $\det(U)\det(V)=1$ tells us that $\det(U)=\det(V)=\pm1$ . So these two bases are related by a unimodular matrix (a matrix with integer entries and determinant $\pm1$ ). Specifically we get the matrix for one basis by right-multiplying the matrix of the other basis by a certain unimodular matrix.

Conversely if we have a basis $\{a_1,\ldots,a_n\}$ for a lattice $\Gamma$ and take a unimodular matrix $U=(u_{ij})$ then the lattice with basis $\{a_1^\prime,\ldots,a_n^\prime\}$ where

$a_j^\prime=\sum_{i=1}^n u_{ij}a_i$

is again $\Gamma$ . To see this let $\Gamma^\prime$ be the lattice with basis $\{a_1^\prime,\ldots,a_n^\prime\}$ and note that each $a_j^\prime\in\Gamma$ , so $\Gamma^\prime\subseteq\Gamma$ . Let $U^{-1}=V=(v_{ij})$ , then this is also a unimodular matrix and we have

$\sum_{k=1}^n v_{ki}a_k^\prime=\sum_{k=1}^n v_{ki} \sum_{j=1}^n u_{jk}a_j$

$=\sum_{j=1}^n \left(\sum_{k=1}^n u_{jk}v_{ki}\right)a_j$

$=\sum_{j=1}^n\delta_{ji}a_j$

$=a_i\in\Gamma^\prime.$

So that $\Gamma\subseteq\Gamma^\prime$ , so the two lattices are in fact the same.

So we’ve shown that two bases give the same lattice if and only if their matrices are related by a unimodular matrix. In the simple example where we had $(1,1),(1,0)$ as a basis for $\mathbb{Z}^2$ we can now note that

$\left(\begin{array}{ c c }1 & 1 \\ 1 & 0\end{array}\right)\left(\begin{array}{ c c }0 & 1 \\ 1 & -1\end{array}\right)=\left(\begin{array}{ c c }1 & 0 \\ 0 & 1\end{array}\right).$

Recall we proposed that the determinant of the matrix given by the basis vectors might be an invariant of the lattice. Well the above shows this is the case. Given two bases of a lattice we’ve seen their matrices $A$ and $A^\prime$ are related by a unimodular matrix $U$ by $A=A^\prime U$ . And so

$\det(A)=\det(A^\prime U)=\det(A^\prime)\det(U)=\pm\det(A^\prime).$

So the determinant – up to sign – does not depend on the basis chosen. We call the absolute value of this the determinant of the lattice, denoted $\det(\Gamma)$ .

Another very important feature of a lattice $\Gamma$ is its fundamental parallelepiped. This depends on the basis chosen, and given a basis $\{a_1,\ldots,a_n\}$ it is the set:

$F(\Gamma)=F(\Gamma;a_1,\ldots,a_n)$

$=\left\{\sum_{i=1}^n x_i a_i \mid 0\leq x_i < 1\textrm{ for }i=1,\ldots,n \right\}\subseteq\mathbb{R}^n.$

In $\mathbb{R}^2$ this is the parallelogram cut out by the points $0, a_1, a_2,$ and $a_1+a_2$ , and in higher dimensions we get generalisations of this, hence the name. It clearly depends on the basis chosen.

The parallelepiped itself may not be unique, but its volume is. If $a_j=\sum_{i=1}^n\alpha_{ij}e_i$ then we have

$\textrm{vol}(F(\Gamma;a_1,\ldots,a_n))=\int\cdots\int_{F(\Gamma;a_1,\ldots,a_n)}dV$

$=\int_0^1\cdots\int_0^1 |\det(\alpha_{ij})|dx_1\cdots dx_n$

$=|\det(a_{ij})|$

$=\det(\Gamma).$

And so the volume is independent of the basis used.

The fundamental parallelepiped is extra useful as every point in $\mathbb{R}^n$ can be written uniquely as the sum of a point on the lattice and a point in the fundamental parallelepiped. That is,

$\mathbb{R}^n=\Gamma+F(\Gamma;a_1,\ldots,a_n).$

This is intuitively clear and is an extension of the idea of writing any real number as its integer part plus its fractional part, except now we have the lattice replacing integers and the parallelepiped replacing the fractional part. The proof uses this basic principle and simply applies it to $n$ dimensions.

Geometry of Numbers, Lecture 1: Lattices (Sean)

March 19, 2008 in Uncategorized | Tags: Geometry of Numbers | by Sean | Leave a comment

Notation.

Let $Z$ be an abelian group whose operation we will denote additively. Given a d-tuple $v = (v_1, \dots, v_d)$ of elements in $Z$ and a d-tuple of integers $n = (n_1, \dots, n_d)$ we define their dot product by the usual formula

$n\cdot v := n_1v_1 + \dots + n_d v_d.$

The map $n \mapsto n\cdot v$ is then a homomorphism ${\Bbb Z}^d \rightarrow Z$ and its image ${\Bbb Z}^d \cdot v$ is precisely the subgroup of $Z$ generated by $v_1,\dots, v_d$ .

Lattices.

We will study a special type of abelian group, namely the lattices in $\Bbb R^d$ . To define these groups we need the notion of an isolated point in a topological space: given a subset $Y$ of a topological space $X$ , we say $y \in Y$ is isolated in $Y$ if there exists a neighbourhood $N$ of $y$ with $N\cap Y = \{ y \}$ . $Y$ is said to be discrete if all its points are isolated.

Definition. A lattice $\Gamma$ in $\Bbb R^d$ is any additive subgroup of $\Bbb R^d$ which is discrete. The rank $k$ of $\Gamma$ is the dimension of the linear subspace of $\Bbb R^d$ generated by $\Gamma$ . Clearly $0 \leq k \leq d$ . If $k = d$ then we say $\Gamma$ has full rank. If $v_1 , \dots, v_k$ are linearly independent and generate $\Gamma$ as a group, then we call $v_1, \dots, v_k$ a basis for $\Gamma$ .

The integer lattice $\Bbb Z^d$ is our archetypal example of a lattice (clearly this is a discrete additive subgroup of $\Bbb R^d$ ). The definition excludes subgroups such as $\Bbb Q^d$ . Generalising $\Bbb Z^d$ , a wealth of examples of lattices of rank k can be obtained by choosing a set of k linearly independent vectors $\{ v_1 , \dots , v_k \} \subset \Bbb R^d$ , then forming the dot product

$\Gamma := \Bbb Z^k \cdot (v_1, \dots, v_k).$

Proposition 1. $\Gamma$ is a lattice in $\Bbb R^d$ .

Proof. Clearly $\Gamma$ is an additive subgroup of $\Bbb R^d$ . It remains to show $\Gamma$ is discrete. Nathanson does this by noting that by the linear independence of $v_1, \dots, v_k$ , the function

$T : \displaystyle \sum_{i=1}^k \lambda_i v_i \mapsto (\lambda_1, \dots, \lambda_k)$

is a well-defined linear map from the subspace of $\Bbb R^d$ generated by $v_1, \dots, v_k$ to $\Bbb R^k$ . It can be shown that this map is continuous and maps $\Gamma$ to $\Bbb Z^k$ . Because of this continuity and the discreteness of $\Bbb Z^k$ , $\Gamma$ must also be discrete. I find the continuity of $T$ intuitive, but not obvious (it is an obvious consequence of the continuity of linear maps between finite dimensional normed spaces, but this fact doesn’t seem concrete enough in this setting for my taste). I will therefore present an argument which shows a little more directly why $\Gamma$ is discrete. We’ll start by showing that there exists a constant $C > 0$ such that for any $\underline{\lambda} \in \Bbb R^k$

$|\underline{\lambda}| \leq C \left| \sum_{i=1}^k \lambda_i v_i \right|, (1)$

where the above absolute values represent Euclidean norms in $\Bbb R^k$ and $\Bbb R^n$ , respectively. Let

$y = (y_1, \dots , y_n) = \sum_{i=1}^k \lambda_i v_i$ , (2)

and for each i let $v_i = (v_{i1}, \dots, v_{in}).$ By the linear independence of the $v_i$ , there exists $u_{ij} \in \Bbb R$ (at least one of which is non-zero) such that if $y$ and $\underline{\lambda}$ satisfy (2), then

$\lambda_i = \sum_{j= 1}^n y_j u_{ij}.$

Applying Cauchy-Schwarz we have

$\left(\sum_{i=1}^k \lambda_i^2 \right)^{1/2} = \left(\sum_{i=1}^k \left(\sum_{j= 1}^n y_j u_{ij}\right)^2 \right)^{1/2}$

$\leq \left( \left(\sum_{j= 1}^n y_j^2\right)\left( \sum_{i=1}^k\sum_{j=1}^n u_{ij}^2\right)\right)^{1/2}.$

Taking $C = \left( \sum_{i=1}^k\sum_{j=1}^n u_{ij}^2\right)^{1/2} > 0$ we obtain (1). Since two distinct points of $\Bbb Z^k$ are at a distance of at least 1, it follows from (1) that two distinct point of $\Gamma$ are at a distance of at least $1/C$ . Hence $\Gamma$ is discrete. This completes the proof.

In fact lattices of the form $\Bbb Z^k \cdot (v_1, \dots, v_k)$ are the only type of lattices, which follows from the next theorem whose proof can be found in Nathanson (Theorem 6.1):

Theorem 1. $\Gamma$ is a lattice in $\Bbb R^d$ of rank k if and only if there exists a set of k linearly independent vectors $\{ v_1, \dots, v_k\} \subset \Bbb R^d$ with $\Gamma = \Bbb Z^k \cdot (v_1, \dots, v_k).$