Recreational Mathematics Club

Discussion #2
  
All about lattices
  

Speakers: Mahek Shamsukha, Dhairya Baxi

Indian Institute of Science

1 Lattices

Lattices are regular, discrete arrangements of points in Euclidean space. They arise naturally in crystallography, sphere packings, integer programming, cryptography, and coding theory. Two equivalent definitions are in common use.

Definition 1.1 (Algebraic definition). A lattice Λ ⊆ ℝn is a discrete additive subgroup of ℝn:

Definition 1.2 (Constructive / basis definition). Let B = [b1,…,bk] ∈ ℝn×k have linearly independent columns. The lattice generated by B is

{ k } L(B ) = ∑ x b : x ∈ ℤ = {Bx : x ∈ ℤk }. i=1 i i i

The matrix B is called a basis; n and k are the dimension and rank. When n = k the lattice is full rank.

Key contrast with vector spaces. span(B) = {Bx : x ∈ ℝk} allows real coefficients and produces a continuous set. L(B) = {Bx : x ∈ ℤk} restricts to integer coefficients, producing a discrete set. Since the columns b1,…,bk are linearly independent, any y ∈ span(B) has a unique representation y = ∑ xibi, and y ∈ L(B) if and only if all xi ∈ ℤ.

Example 1.3. The standard integer lattice ℤn = {(x1,…,xn) : xi ∈ ℤ} is generated by the standard basis vectors of ℝn.

Example 1.4 (ℚn is not a lattice). The set ℚn is a subgroup of ℝn (it is closed under addition and subtraction), but it fails the discreteness condition. For any 𝜀 > 0, one can always find two distinct points x,y ∈ ℚn with ∥x − y∥ < 𝜀 (e.g. take x = 0 and y = (𝜀∕2,0,…,0)), so no uniform lower bound on pairwise distances exists. Hence ℚn is not a lattice.

2 Lattice Bases and Unimodular Transformations

A lattice can be represented by many different bases. Two bases B and C generate the same lattice if and only if B = CU for some unimodular matrix U.

Theorem 2.1. L(B) = L(C) if and only if there exists a unimodular matrix U (a square integer matrix with det(U) = ±1) such that B = CU.

Proof. (⇐) Suppose B = CU for some unimodular U. Since det(U) = ±1 and U has integer entries, U−1 is also an integer matrix, and

−1 C = BU .

Hence every column of B is an integer combination of columns of C, giving L(B) ⊆ L(C), and symmetrically L(C) ⊆ L(B). Thus L(B) = L(C).

(⇒) Suppose L(B) = L(C). Since the columns of B lie in L(C), and vice versa, there exist integer matrices V,W such that

B = CW and C = BV.

Substituting the second into the first,

B = BV W = ⇒ B (I − V W ) = 0.

Since the columns of B are linearly independent, we conclude V W = I. Taking determinants on both sides,

det(V) ⋅det(W ) = det(I) = 1.

Since V,W have integer entries, det(V ),det(W) ∈ ℤ, so the only possibility is

det(V ) = det(W ) = ±1.

Hence W is unimodular, and B = CW is the required relation with U = W. □

3 Gram–Schmidt Orthogonalization

Given a lattice basis B = [b1,…,bn], it is often useful to transform it into an orthogonal system.

Definition 3.1. The Gram–Schmidt orthogonalization produces vectors B∗ = [b1∗,…,bn∗] defined iteratively by

∑ ∗ b∗= bi − μi,j b∗, μi,j = ⟨bi, bj⟩. i j<i j ⟨b∗j, b∗j⟩

In matrix notation, B = B∗M where M is upper triangular with 1s on the diagonal.

The vectors b1∗,…,bn∗ are mutually orthogonal and span the same vector space as B. However, the orthogonal vectors are usually not lattice vectors.

Example 3.2. Consider the basis B = {b1 = (2,0), b2 = (1,2)}. The two diagrams below show Gram–Schmidt applied in different orders.

∗∗ xybbbbO1221r = = = =de(((br2101:,,, b0)2)2)1 first, then b2     ∗∗ (8 4) xybbbbO1212r = = = =de((br2152:,,, b02−2))5first, then b1

4 Fundamental Parallelepiped and Determinant

Given a lattice basis B = [b1,…,bn], we define the fundamental parallelepiped

{ ∑n } 𝒫(B ) = xi bi : 0 ≤ xi < 1 . i=1

The translates 𝒫(B) + v for v ∈ L(B) partition all of ℝn; each coset of the lattice has exactly one representative in 𝒫(B).

Definition 4.1. The determinant of a lattice is the volume of the fundamental parallelepiped:

n ∏ ∗ det(L(B)) = vol(𝒫 (B)) = ∥bi∥. i=1

Geometrically, det(L) measures the inverse density of lattice points: a large region of volume V contains roughly V∕det(L) lattice points. The determinant does not depend on the choice of basis.

Proposition 4.2. For any lattice basis B,

---------- ∘ ⊤ det(L (B)) = det(B B).

In particular, if B ∈ ℝn×n is square, then det(L(B)) = |det(B)|.

Proof. From the Gram–Schmidt factorisation B = B∗M, where M is upper triangular with 1s on the diagonal, we compute

det(B ⊤B ) = det(M ⊤B ∗⊤B ∗M ) = det(M ⊤ ) det(B ∗⊤B ∗) det(M ).

Since M is upper triangular with 1s on the diagonal, det(M) = det(M⊤) = 1. Since the columns of B∗ are orthogonal, B∗⊤B∗ is diagonal with entries ∥bi∗∥2, so

∏ det(B∗⊤B ∗) = ∥b∗i∥2 = det(L (B ))2. i

Taking the square root,

∘ ---------- -| det(B ⊤B ) = det(L (B)). --

Theorem 4.3. Let B ∈ ℤn×n be nonsingular and let d = |det(B)|. Then d ℤn ⊆ L(B).

Proof. Let v ∈ d ℤn be arbitrary, so v = dy for some y ∈ ℤn. We wish to find x ∈ ℤn such that

Bx = v = dy.

Recall the adjugate (classical adjoint) adj(B), whose (i,j) entry is the signed (j,i) cofactor of B. Since B ∈ ℤn×n, every cofactor is an integer determinant, so

n×n adj(B ) ∈ ℤ .

The key identity relating the adjugate to the inverse is

B ⋅adj(B) = det(B)I = d I.

Set x = adj(B)y. Since adj(B) and y are both integer, x ∈ ℤn. Moreover,

Bx = B adj(B )y = dI y = dy = v.

Hence v = Bx ∈ L(B), and since v was arbitrary, d ℤn ⊆ L(B). □

This shows that every integer lattice contains a scaled copy of the standard lattice as a sublattice.

5 Minimum Distance and Shortest Vectors

Definition 5.1. The minimum distance of a lattice Λ is

λ1(Λ ) = min ∥x∥. x∈Λ∖{0}

This corresponds to the length of the shortest nonzero lattice vector. More generally, the successive minima λ1 ≤ λ2 ≤⋅⋅⋅≤ λn are defined so that λk(Λ) is the smallest r such that Λ contains k linearly independent vectors of length at most r.

Theorem 5.2. For a lattice basis B with Gram–Schmidt vectors bi∗,

∗ λ1(L (B )) ≥ miin ∥bi∥.

6 Blichfeldt’s Theorem

Blichfeldt’s theorem is essentially the pigeonhole principle for volumes: if a set S is too large to fit inside a single fundamental parallelepiped, then when we tile space with translates of 𝒫(B), at least two pieces of S must land in the same cell — and shifting them back reveals two points of S that differ by a lattice vector.

Theorem 6.1 (Blichfeldt). Let Λ = L(B) be a lattice and S ⊂ ℝn a measurable set. If vol(S) > det(Λ), then there exist two distinct points z1,z2 ∈ S such that z1 − z2 ∈ Λ.

Proof. Decompose S into the pieces that lie in each lattice-translate of 𝒫(B):

Sx = S ∩ (x+ 𝒫(B )), x ∈ Λ.

These sets are pairwise disjoint and cover S, so

∑ vol(S) = vol(Sx). x∈Λ

Now translate each piece back into 𝒫(B) by defining Tx = Sx − x ⊆𝒫(B). Since translation preserves volume,

∑ ∑ vol(Tx) = vol(Sx) = vol(S ) > det(Λ ) = vol(𝒫(B )). x∈Λ x∈Λ

Since all Tx live inside 𝒫(B) and their total volume exceeds vol(𝒫(B)), they cannot all be disjoint. Hence there exist distinct x≠y ∈ Λ such that Tx∩Ty≠∅. Pick any point p in this intersection. Then

z1 = p + x ∈ Sx ⊆ S, z2 = p+ y ∈ Sy ⊆ S,

and

z1 − z2 = x − y ∈ Λ. -|

The diagram below illustrates the idea in ℝ2: a blob S is cut by the lattice tiling, each piece is translated into 𝒫(B), and two pieces overlap.

pieces overlap 𝒫S(Bi)n 𝒫 (B )

7 Minkowski’s Convex Body Theorem

Theorem 7.1 (Minkowski). Let Λ be a lattice in ℝn and let S be a convex, centrally symmetric body. If

n vol(S ) > 2 det(Λ),

then S contains a nonzero lattice point.

Proof. Apply Blichfeldt to S∕2 = {x : 2x ∈ S}, which satisfies vol(S∕2) = 2−n vol(S) > det(Λ). Blichfeldt gives distinct z1,z2 ∈ S∕2 with z1 − z2 ∈ Λ ∖{0}. Then 2z1,2z2 ∈ S, so by symmetry −2z2 ∈ S, and by convexity

-| z1 − z2 = 12(2z1) + 12(− 2z2) ∈ S. --

This theorem gives an upper bound on the shortest lattice vector:

√-- λ1(Λ ) ≤ n det(Λ )1∕n.

8 Application: Primes of the Form a2 + b2

Theorem 8.1. If p is a prime with p ≡ 1 (mod 4), then p = a2 + b2 for some integers a,b.

Idea of the proof. Since p ≡ 1 (mod 4), there exists i such that i2 ≡−1 (mod p).

Consider the lattice generated by

( ) 1 0 B = i p .

By Minkowski’s theorem, there exists a nonzero lattice vector (a,b)⊤ satisfying 0 < a2+b2 < 2p. Using i2 ≡−1 (mod p), one checks that p∣a2 + b2. Since the value lies strictly between 0 and 2p, we must have a2 + b2 = p. □

9 Hermite Normal Form

The Hermite Normal Form (HNF) provides a canonical, unique representation for a lattice. We say a matrix B = [b1,…,bn] of full row rank is in HNF if it has the form B = [H∣0], where:

Definition 9.1. A square matrix H = [hij] is in Hermite Normal Form if:

In particular, H is nonsingular. The HNF is computed by applying elementary column operations, which are special unimodular transformations:

1.
Swap two columns: bi ↔ bj.
2.
Multiply a column by −1: bi ←−bi.
3.
Add an integer multiple of one column to another: bi ← bi + αbj, α ∈ ℤ.

Since these are unimodular, they preserve the lattice generated by the columns of B.

Theorem 9.2 (Existence of HNF). Every rational matrix of full row rank can be brought into Hermite normal form by a sequence of elementary column operations. Equivalently, for every such matrix B there is a unimodular matrix U such that BU is in HNF.

Proof. Without loss of generality assume B is integral (otherwise clear denominators). We build a sequence of matrices

( ) Hk 0 Bk = Ck Dk ,

where Hk is a k×k matrix already in HNF. At each step, let d1,…,dn−k be the first-row entries of Dk. By permuting columns and negating, assume all di ≥ 0 with at least one nonzero. If two nonzero entries di > dj appear, add −⌊di∕dj⌋ times column j to column i, strictly reducing the total sum of first-row entries. Repeating (this executes the Euclidean algorithm on pairs of entries) terminates with a single nonzero entry d in the first row of Dk, which is placed in the first column by a swap. Finally, for each i = 1,…,k, subtract ⌊ci∕d⌋ times the new column from column i to reduce all entries in the first row of Ck to the range [0,d). This yields Bk+1 with Hk+1 of size (k + 1) × (k + 1) in HNF. □

Remark 9.3. The naive algorithm above may be non-polynomial due to intermediate entry growth. A polynomial-time variant exists by performing all arithmetic modulo the determinant of the relevant submatrix, keeping entries bounded throughout.

Sublattices and the Index

Let Λ′ = L(B′) be a sublattice of Λ = L(B), both full-dimensional. Then B′ = BV for some integral matrix V , and the index of Λ′ in Λ is

′ det(Λ-′) D (Λ,Λ ) := |det(V )| = det(Λ ) ∈ ℤ>0.

Lemma 9.4. If Λ′ is a sublattice of Λ with index D, then

′ D Λ ⊆ Λ ⊆ Λ.

Proof. Let B,B′ be bases of Λ,Λ′ with B′ = BV and D = |det(V )|. Then B = B′V −1 and DV −1 is an integral matrix (since the entries of V −1 = adj(V )∕det(V ) become integral upon multiplication by D). Hence

DB = B′(DV − 1) ∈ L(B ′) = Λ′,

so DΛ ⊆ Λ′. □

Theorem 9.5 (Bases in HNF). Let Λ′ be a sublattice of Λ.

(a)
For every basis B of Λ, there is a unique basis B′ of Λ′ such that B′ = BH with H in HNF.
(b)
For every basis B′ of Λ′, there is a unique basis B of Λ such that B′ = BH with H in HNF.

10 Easy and Hard Lattice Problems

Using HNF and the dual lattice, the following problems are all solvable in polynomial time: computing a basis for L(B), deciding whether L(B) = L(C), membership testing (v ∈ L(B)?), union, and containment.

In contrast, the following are believed to be computationally hard.

Definition 10.1. The Shortest Vector Problem (SVP): given a lattice basis B, find a nonzero lattice vector of length at most γ ⋅ λ1(L(B)).

Definition 10.2. The Shortest Independent Vectors Problem (SIVP): given a rank-n basis B, find n linearly independent lattice vectors of length at most γ ⋅ λn(L(B)).

Definition 10.3. The Closest Vector Problem (CVP): given a basis B and a target vector t, find a lattice vector within distance γ ⋅ dist(t,L(B)).

Acknowledgements

These notes follow the exposition in: