CryptoBook
Search…
Introduction
Lattices, also known as Minkowski's theory after Hermann Minkowski, or the geometry of numbers (deprecated!) allows the usage of geometrical tools (i.e. volumes) in number theory.
The intuitive notion of a lattice (perhaps surprisingly) matches its mathematical definition. For example, lattices are formed by
    points on an infinite checkerboard;
    centers of a hexagonal tessellation;
    integers on the real number line.
The last example should hint at how we generalize this concept to arbitrary dimensions. In general, lattices consist of discrete points which appear at "regular intervals."

Definitions

A lattice
LL
is a subgroup of
Rn\mathbb{R}^n
generated by
bib_i
, i.e.
L=i=1dZbi={i=1daibiaiZ}L=\sum_{i=1}^d\mathbb{Z} b_i = \left\{\left. \sum_{i=1}^d a_i b_i \right | a_i \in \mathbb{Z} \right\}
where
bib_i
are linearly independent vectors. Collectively,
{bi}i=1d\left\{b_i\right\}_{i=1}^d
form a basis of
LL
.
We say a set of vectors
viv_i
are linearly independent if the only solution to the equation
iaibi=0\sum_{i} a_i b_i = 0
is when all
aia_i
are zero.
Taking a step back, this definition should resemble that of a vector space, with one exception: scalars are integers! The discrete nature of lattices comes from this restriction.
Some more terminology from linear algebra will be useful. The dimension of a lattice, denoted
dimL\dim L
, is
dd
. A lattice is complete if
d=nd=n
. Note that we can always choose a subspace of
Rn\mathbb R^n
such that the lattice is complete, namely the subspace generated by
bib_i
.
The region
Φ={i=1dxibi0xi<1}\Phi=\left\{\left.\sum_{i=1}^dx_ib_i\right|0\leq x_i<1\right\}
is known as the fundamental mesh.
In the image above, we see the points of a lattice in
R2\mathbb R^2
. The red vectors are one set of basis vectors and the shaded region is the corresponding fundamental mesh. The green vectors also form another set of basis vectors with its corresponding fundamental mesh. We see here that the basis vectors and fundamental mesh is not unique to a lattice.
Although the fundamental mesh is not unique, it turns out that the (
mm
dimensional) volume of the fundamental mesh is constant for any given lattice. Hence we can define the volume of a lattice as the volume of a fundamental mesh. However this definition can be hard to handle hence we provide an equivalent definition via determinants:
Let
B\mathcal B
be a
d×nd\times n
matrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by
vol(L)=det(BBT)\text{vol}(L)=\sqrt{\left|\det\left(\mathcal B\mathcal B^T\right)\right|}
A subset
XX
of
Rn\mathbb R^n
is known as centrally symmetric if
xXx\in X
implies
xX-x\in X
. It is convex if for any
x,yXx,y\in X
, the line joining
x,yx,y
is contained in
XX
, i.e.
{tx+(1t)y0t1}X\left\{tx+(1-t)y|0\leq t\leq1\right\}\subset X
. Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:
Let
LL
be a complete lattice of dimension
nn
and
XX
be a centrally symmetric convex set. Suppose
vol(X)>2nvol(L)\text{vol}(X)>2^n\text{vol}(L)
Then
XX
contains at least one nonzero point of
LL
. This result is primarily used to prove the existence of lattice vectors.
Throughout this section,
v=ivi2\left\lVert v\right\rVert=\sqrt{\sum_iv_i^2}
denotes the
2\ell_2
norm and
a,b=iaibi\langle a,b\rangle=\sum_ia_ib_i
denotes the inner product.

Proof sketch of Minkowski's theorem

This proof is by some sort of a pigeonhole argument on volumes. Consider the set
12X={12xxX}\frac12X=\left\{\frac12x|x\in X\right\}
We have
vol(12X)>vol(L)\text{vol}\left(\frac12 X\right)>\text{vol}(L)
, hence the inclusion
12XRn/L\frac12X\to\mathbb R^n/L
cannot be injective, thus we can find some
x1=x2+x_1=x_2+\ell
,
x1,x212X,L,x1x2x_1,x_2\in\frac12 X,\ell\in L,x_1\neq x_2
. Hence
x1x2Lx_1-x_2\in L
is a nontrivial lattice point.

Exercises

1) Let
LL
be the lattice generated by
B=(198187)\mathcal B=\begin{pmatrix}-1&9&8\\1&-8&-7\end{pmatrix}
(take the rows as basis vectors).
    Compute the volume of this lattice
    Show that
    B=(101011)\mathcal B'=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}
    generates the same lattice
    Show that each row in
    C=(101022)\mathcal C=\begin{pmatrix}1&0&1\\0&2&2\end{pmatrix}
    is in the lattice but
    C\mathcal C
    does not generate the lattice. This is one key difference from the case of linear algebra (over fields).
2) Let
B,B\mathcal B,\mathcal B'
be
d×nd\times n
matrices whose row vectors are basis for lattices
L,LL,L'
. Both lattices are the same iff there exists some
UGLd(Z)U\in\text{GL}_d(\mathbb Z)
such that
B=UB\mathcal B'=U\mathcal B
. Find
UU
for problem 1. Note that
GLd(Z)\text{GL}_d(\mathbb Z)
is the group of invertible matrices with integer coefficients, meaning
UU
and
U1U^{-1}
have integer coefficients.
3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete lattice
LL
of dimension
nn
, we can find some centrally symmetric convex set
XX
with
vol(X)=2nvol(L)\text{vol}(X)=2^n\text{vol}(L)
but the only lattice point in
XX
is the origin.
4*) Let
vv
be the shortest nonzero vector for some lattice
LL
with dimension
nn
. Show that
v2πΓ(n2+1)1nvol(L)1n\left\lVert v\right\rVert\leq\frac2{\sqrt\pi}\Gamma\left(\frac n2+1\right)^{\frac1n}\text{vol}(L)^\frac1n
Last modified 3mo ago