# Lattice Points (Lec. 12, Monday, March 01)

## Minkowski (Version 1)

:::{.remark}
Basic heuristic from last time: counting the lattice points in a region $R$ should be approximately $\vol(R)$.
We turned this into a theorem for certain regions:
:::

:::{.theorem title="Lattice points with volume after scaling"}
Let $R \subseteq \RR^n$ be a bounded region with a well-defined with respect to the Riemann integral.
Letting $L_{R}$ be the number of lattice points in $R$, we have
\[
{1\over t^n} L_{tR} \converges{t\to \infty}\to \vol(R)
.\]
:::

:::{.remark}
Most of today: Minkowski's theorem, which will guarantee a lattice point under some conditions.
:::

:::{.theorem title="Minkowski, Version 1"}
Let $R \subseteq \RR^n$ be a bounded region that is

1. Convex, so any line segment connecting two points in $R$ is entirely contained within $R$, and 

2. Symmetric about $\vector 0$, so $\vector x\in R\implies -\vector x\in R$.

If $\vol(R) > 2^n$, then $R$ contains a nonzero lattice point.
:::

:::{.remark}
Any circle/ball or ellipse will be an example.
Note that $2^n$ is sharp, i.e. this theorem does not hold for a smaller constant: take the square $(-1, 1) \cross (-1, 1) \subseteq \RR^2$, which has volume 4 but only contains the origin as a lattice point.
:::

:::{.proof title="of Minkowski Version 1"}
Note that any such region already contains $\vector 0$, since containing $\vector x$ and $-\vector x$ plus convexity implies containing the line between them, which passes through $\vector 0$.
By assumption $\vol(R) > 2^n$, and hence $(1/t^n)L_{tR} > 2^n$ for $t$ large enough.
So set $t=m$ for some $m>> 1\in \ZZ^{\geq 0}$, this yields $L_{mR} > (2m)^n$.
Consider $\ZZ^n$ and taking all coordinates $\mod 2m$.
This yields $(2m)^n$ equivalence classes of points, so by the pigeonhole principle there exist $\vector v_1 \neq \vector v_2 \in mR$ such that $(\vector v_1 - \vector v_2)/2m \in \ZZ^n$, and the claim is that this is the lattice point we want.

\

Note that this is nonzero, why is it in the region $R$?
By definition, $(1/m)\vector v_1 \in R$ and $(-1/m)\vector v_2 \in R$ using the symmetric assumption.
The midpoint between these is precisely the previous point, and this is in $R$ by convexity.
:::

## Minkowski (Version 2)

:::{.definition title="Lattice"}
A **lattice** in $\RR^n$ is the $\ZZ\dash$span of a collection of $\RR\dash$linearly independent vectors in $\RR^n$.
:::

:::{.example title="$n=2$"}
\envlist

- \( \Lambda \da \ZZ \tv{1, 0}^t + \ZZ\ts{0, 1}^t \).
  This tiles the plane by squares.
- \( \Lambda \da \ZZ \tv{1, 1}^t + \ZZ\ts{1, 3}^t \).
  Note that this now tiles the plane by parallelograms:

\begin{tikzpicture}
  \draw[thin,gray!40] (-1,-1) grid (4,4);
  \draw[<->] (-1,0)--(4,0) node[right]{$x$};
  \draw[<->] (0,-1)--(0,4) node[above]{$y$};
  \draw[line width=1pt,blue,-stealth](0,0)--(1,1) node[anchor=south west]{$\boldsymbol{u}$};
  \draw[line width=1pt,purple,-stealth](1,1)--(2,4) node[anchor=south west]{};
  \draw[line width=1pt,purple,-stealth](0,0)--(1,3) node[anchor=north east]{$\boldsymbol{v}$};
\draw[line width=1pt,blue,-stealth](1,3)--(2,4) node[anchor=south west]{};

\draw [draw=black, fill=purple, opacity=0.4]
       (0,0) -- (1,1) -- (2,4) -- (1,3) -- cycle;
\end{tikzpicture}

- \( \Lambda \da \ZZ \tv{1, 0}^t \), which recovers \( \ZZ \subseteq \RR \).
  This is not a full lattice, since it lies in a proper subspace of $\RR^2$.

Note that this will always result in a free abelian group on $n$ generators.
Why not define a lattice this way?
Here's a non-example:

- \( \Lambda \da \ZZ \tv{\sqrt{2} , 0}^t + \ZZ\ts{1, 0}^t \), which are not linearly independent over $\RR$.
  This yields a dense set of points on the real axis in $\RR^2$, and is still a free abelian group of rank 2.
  We'll see later that no lattice can be dense, and in fact they must always be discrete.

:::

:::{.remark}
It may not be obvious that a lattice has a uniquely determined number of generating elements.
This turns out to be true: if \( \Lambda = \sum_{i=1}^d  \ZZ \vector v_i \) with \( \ts{ \vector{v}_i }_{i=1}^d \) linearly independent over $\RR$, then 
\[
\Lambda\tensor_\ZZ \RR \cong \sum_{i=1}^d \RR \vector v_i \cong \RR^d 
,\] 
which is now an $\RR\dash$vector vector space of real dimension $d$.
Noting that $\dim_\RR(\Lambda\tensor_\ZZ \RR)$ doesn't depend on the choice of basis, any different choice of generating set for \( \Lambda \) must have the same number of generators.
:::

:::{.definition title="Full Lattices"}
If $d=n$, we'll call \( \Lambda \) a **full lattice**.
:::

:::{.definition title="Fundamental Parallelepiped"}
Note that if \( \Lambda \) is full, then \( \Lambda= \sum_{i=1}^n \ZZ \vector{v}_i \) with the $\vector v_i$ linearly independent over $\RR$.
We define the **fundamental parallelepiped** as the set
\[
\ts{ \sum_{i=1}^n c_n \vector v_n \st 0 \leq c_i \leq 1} 
.\]
Note that this depends on the choice of generating set.
:::

:::{.example title="of a fundamental parallelepiped"}
For $\vector v_1 = \tv{1, 1}^t$ and $\vector v_2 = \tv{1, 3}$, we get the parallelogram shown in the earlier figure.
Note that \( \Lambda \) is also generated by \( \vector v_1 = \ts{1, 1}, \vector w_2 = \tv{0, 2} \), but this generates a different parallelepiped:

\begin{tikzpicture}
  \draw[thin,gray!40] (-1,-1) grid (4,4);
  \draw[<->] (-1,0)--(4,0) node[right]{$x$};
  \draw[<->] (0,-1)--(0,4) node[above]{$y$};
  \draw[line width=1pt,blue,-stealth](0,0)--(1,1) node[anchor=south west]{$\vector v_1$};
  \draw[line width=1pt,purple,-stealth](1,1)--(2,4) node[anchor=south west]{};
  \draw[line width=1pt,purple,-stealth](0,0)--(1,3) node[anchor=south east]{$\vector v_2$};
\draw[line width=1pt,blue,-stealth](1,3)--(2,4) node[anchor=south west]{};

\draw[line width=1pt,green,-stealth](0,0)--(0,2) node[anchor=south east]{$\vector w_2$};

\draw [draw=black, fill=purple, opacity=0.4]
       (0,0) -- (1,1) -- (2,4) -- (1,3) -- cycle;

\draw [draw=black, fill=green, opacity=0.2]
       (0,0) -- (1,1) -- (1,3) -- (0,2) -- cycle;
\end{tikzpicture}

:::

:::{.proposition title="The volume of the fundamental parallelotope is a lattice invariant"}
In general, one gets a parallelotope whose volume is an invariant of the lattice itself.
:::

:::{.proof title="of proposition"}
How do we compute this?
Let $M_v = \tv{ \vector v_1^t, \cdots, \vector v_n^t}$ be the linear transformation obtained by placing all of the generating vectors into the columns of a matrix, and consider scaling the unit cube $C = [0, 1]^n$.
Then letting $P$ be the fundamental parallelepiped, we have $P = M_v C$ and so
\[
\vol(P) = \vol(M_v C) = \abs{ \det(M_v) } \vol(C) = \det(M_v)
,\]
using that the volume of the standard cube is 1.
So it suffices to check that if $\vector v_i$ and $\vector w_j$ generate the same lattice \( \Lambda \), then $\det M_v = \det M_w$.
Why is this true?
If they generate the same lattice, every $\vector v_i$ is a $\ZZ\dash$linear combination of the $\vector w_j$, and similarly every $\vector w_j$ can be written as a linear combination of the $\vector v_i$.
So we get 
\[
M_v = M_w A
\qquad 
M_w = M_v A'
\]
for some matrices $A, A'$.
We can thus write 
\[
M_v = M_vA' A
.\].
Since the $\vector v_i$ are linearly independent, $M_v$ is invertible, so right-multiplying yields $AA' = I$ and taking determinants yields 
\[
1 = \det(A')\det(A)
.\]
Noting that $A, A' \in \Mat(n\times n, \ZZ)$, their determinants must be integers, which forces $\det(A) = \det(A') = \pm 1$.
Taking determinants in the original equation yields
\[
\det(M_v) = \det(A) \det(M_w) = \pm \det(M_w)
,\]
and taking absolute values yields the result.
:::

:::{.definition title="Covolume of a Lattice"}
We'll call the common value $\abs{\det M_v}$ for any choice of generating set \( \ts{ \vector v_i } \) the **covolume** of \( \Lambda \):
\[
\covol( \Lambda) \da \abs{ \det M_v }
.\]
:::

:::{.theorem title="Minkowski (Version 2)"}
Let \( \Lambda \) be a full lattice in $\RR^n$, and let $R \subseteq \RR^n$ be a region that is convex and symmetric about zero.
Assume that 
\[
\vol(R) > 2^n \covol( \Lambda)
.\]
Then $R$ contains a nonzero $\vector v \in \Lambda$.
:::

:::{.remark}
Taking \( \Lambda\da \ZZ^n \) recovers the first version.
Idea of proof: any full lattice is the image of the standard lattice under some linear transformation.
:::

:::{.proof title="of Minkowski Version 2"}
Let $\vector v_1, \cdots, \vector v_n$ be $n$ generators for \( \Lambda \), then define a linear transformation
\[
T: \RR^n &\to \RR^n \\
\vector v_i &\mapsto \vector e_i
,\]
which takes each generator to the corresponding standard basis vector.
The $T \Lambda = \ZZ^n$ is the standard lattice, and 
\[
\vol (T(R)) = \abs{ \det(T) } \vol(R) = {\vol(R) \over \covol( \Lambda) } > 2^n
,\]
noting that $T\inv = \tv{\vector v_1^t, \cdots, \vector v_n^t}$.
Now applying the original Minkowski theorem we get a nonzero point 
\[
\vector x\in \ZZ^n \intersect T(R)
\implies T\inv \vector x \in \Lambda \intersect R
.\]
:::

### Application: The 4 Square Theorem

:::{.theorem title="4 Square Theorem (Lagrange)"}
Every positive integer is a sum of 4 squares of integers.
:::

:::{.lemma title="Finding sums of squares in $\ZZ/m$"}
Let $m \in \ZZ^{>0}$  be squarefree, then there are $A, B \in \ZZ$ such that
\[
A^2 + B^2 + 1 \equiv 0 \mod m
,\]
i.e. $-1$ is always the sum of two squares in the ring $\ZZ/m$.
:::

:::{.proof title="of lemma"}
We're trying to solve an equation $\mod m$, and by the CRT it suffices to solve it for every prime power dividing $m$, and since $m$ is squarefree, all prime powers occur with exponent 1.
So it suffices to consider $m=p$ a prime.
We can further assume $p$ is odd, since if $p=2$ we can take $A=1, B=2$.
Consider the following two subsets of $\ZZ/p$:
\[
S_1 &\da \ts{ A^2 \mod p } \\
S_2 &\da \ts{ -1-B^2 \mod p } 
.\]
Note that $\# S_1 = {p+1 \over 2}$, since the number of nonzero squares is half the number of elements, so \({p-1\over 2}\), and we add in zero.
Similarly $\# S_2 = \# S_1$ since it can be obtained from $S_1$ by sending $x\mapsto -1-x$.
Note that \( {p+1\over 2} > {p\over 2} \), but $\abs{\ZZ/p} = p$, so these two sets can't be disjoint.
So there is some $A^1 = -1-B^2 \mod p$.
:::

:::{.proof title="of the 4 Square Theorem"}
Suppose $m$ is squarefree.
Choose $A, B$ as in the lemma, so $A^2 + B^2 \equiv -1 \mod m$, and define 
\( \gamma \da A+ Bi \in \ZZ[i] \).
Let \[ \Lambda \da \ts{ (\alpha, \beta) \in \ZZ[i] \st \alpha\equiv \beta \gamma \mod m } .\]
Taking one such ordered pair in \( \Lambda \), we can apply complex conjugation to obtain 
\[
\alpha\equiv \beta \gamma\mod m \implies \conj{ \alpha} \conj{ \beta} \conj{ \gamma} \mod \conj {m} = m
,\]
where we can immediately note that $\conj{m} = m$ since $m\in \ZZ$.
Multiplying these two congruences yields
\[
\alpha\conj{\alpha} 
= N( \alpha) 
\equiv N( \beta) N( \gamma) \mod m
\equiv - N( \beta) \mod m
,\]
and so we have \( N( \alpha) + N( \beta) \equiv 0 \mod m \).
But these are Gaussian integers, so writing \( \alpha = a + bi, \beta = c + di \) we obtain 
\[
a^2 + b^2 + c^2 + d^2 = \equiv 0 \mod m
.\]
Being congruent to $0\mod m$ in $\ZZ[i]$ means that both the real and imaginary parts are divisible by $m$, but since the left-hand side above is an ordinary integer, it has no imaginary part.
So $m \divides a^2 + b^2 + c^2 + d^2$ for every element of \( \Lambda \).
Noting that \( \Lambda \subseteq \ZZ[i] \) we can identify \( \Lambda \subseteq \ZZ^4 \subseteq \RR^4 \) by pairing $( \alpha, \beta) \mapstofrom (a,b,c,d)$.


:::{.claim}
\( \Lambda\subseteq \RR^4 \) is a full lattice, and after writing a set of generators and computing the determinant, one finds that $\covol( \Lambda) = m^2$.
:::

> See the book for a proof of this claim!

Now let 
\[
R \da \ts{ \tv{x,y,z,w} \in \RR^4 \st x^2 + y^2 + z^2 + w ^2 < 2m  }
,\]
which is a convex and centrally symmetric region.
A multivariable Calculus exercise shows $\vol(R) = 2\pi^2 m^2$, and $2\pi^2 > 2^4 \covol( \Lambda)$.
Applying Minkowski version 2, there exists a nonzero point $\vector x \in R \intersect\Lambda$,
and thus its coordinates satisfy
\[
0 < x^2 + y^2 + z^2 + w^2 < 2m
.\]
The middle term is then an integer that is a multiple of $m$, forcing it to be equal to $m$.
:::

:::{.remark}
We made the assumption that $m$ was squarefree, but we can write any $m\in \ZZ^{>0}$ as $m = k^2 m'$ where $m'$ is squarefree.
Then writing $m' = x^2 + y^2 + z^2 + w^2$, we have 
\[ 
m = (kx)^2 + (ky)^2 + (kz)^2 + (kw)^2 
.\]
There are other applications of Minkowski's theorem that tell you when certain types of numbers are represented by special quadratic forms (such as the above sum of squares).
See Pete Clark's papers!
:::