Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 1, mathematical background.

In this note, I write down proofs missing from his lecture note as well as my questions. Due to the nature of personal notes, I will not formally put references.

**Definition 2.1.** An $n$dimensional lattice $L$ is a discrete additive subgroup of $R_{n}$

**Proposition.** Let $L$ be a subgroup of $R_{n}$ then TFAE:

- For all $x∈L$ there exists $ε>0$ s.t. $L∩B(x,ε)={x}$
- There exists $ε>0$ s.t. $L∩B(0,ε)={0}$
- There exists $ε>0$ s.t. for all $x∈L$ it holds that $L∩B(x,ε)={x}$

**Proof.** We prove this by cycling around.

**3 ⟹ 1 ⟹ 2.**Trivial.**2 ⟹ 3.**Take the $ε$ guaranteed by (2) as that for (3). For all $x,v∈L$ s.t. $v∈B(x,ε)$ we have $v−x∈L$ since $L$ is a subgroup and $v−x∈B(0,ε)$ By the choice of $ε$ and (2), it follows that $v−x=0$

**Definition 2.3.** The rank of lattice $L$ is $r=dimspanL$

**Proposition.** If $L⊆Q_{n}$ there exists $d∈N_{∗}$ s.t. $d⋅L⊆Z_{n}$

**Proof.** This will be trivial once we show that a lattice always has a basis.

**Definition 2.4.** A basis $B={b_{1},…,b_{r}}$ of lattice $L$ is a linearly independent subset of it such that it generates $L$ (as an abelian group).

**Proposition.** Any (finite-dimensional) lattice has a basis.

**Proof.** Clearly $L$ is torsion-free, so by the fundamental theorem of finitely generated abelian groups, we only need to show that $L$ is finitely generated. Since $L⊆R_{n}$ it has a maximal linearly independent subset $S={s_{1},…,s_{r}}$ For all $x∈L$ there exists *real coefficients* $y_{1},…,y_{r}$ s.t.
$x=i=1∑r y_{i}s_{i}.$
Let
$v==defx−∑_{i=1}⌊y_{i}⌋s_{i}$
then $v∈L$ and
$∣v∣≤i=1∑r ∣s_{i}∣==defR.$
This means the set
$S∪(L∩B(0,R))$
generates $L$ We’re done because this is a finite set — in particular, it contains at most
$r+R_{n}/ε_{n}$
points, where $ε$ is the positive number guaranteed by (3) of a previous proposition.

**Corollary 2.7.** (Checking equivalence of lattices generated by two bases, generalized to rank-deficient case.) To check whether $B_{1},B_{2}∈R_{n×r}$ generate the same lattice:

- Check whether $r=rank(B_{1},B_{2})$ This ensures $colspanB_{1}=colspanB_{2}$
- Find an isometry (isomorphism between Euclidean spaces) $ρ:colspanB_{1}→R_{r}$ and compute $C_{1}=ρ(B_{1}),C_{2}=ρ(B_{2}),C_{1},C_{2}∈R_{r×r}$ Note that the $ρ$ can be found using Gram–Schmidt orthonormalisation (QR decomposition).
- Check whether $C_{1}C_{2}$ is unimodular.

**Definition 2.8.** (Fundamental region, generalized to rank-deficient case.) A fundamental region $F⊆R_{n}$ of lattice $L$ is one such that it has exactly one representative for each coset in $(spanL)/L$

**Definition 2.9.** The fundamental parallelepiped of a lattice basis $B∈R_{n×r}$ is $B⋅[2−1 ,21 )_{r}$
Sometimes, one might opt for an alternative definition $B⋅[0,1)_{r}$

**Example.** Voronoi cell of $L$ is the set
$V(L)==def{x∈spanL:∀v∈L∖{0},∣x∣<∣x−v∣}.$
It is not a fundamental region, but its closure is the closure of a fundamental region.

**Definition 2.11.** The volume (determinant) of lattice $L$ is the volume of any of its fundamental region.

**Claim 2.12.** (Determinant from basis, generalized to rank-deficient case.) If $L$ has basis $B$ it has determinant $det(B_{_{T}}B) $

**Question.** There need to be some extra conditions posed on the fundamental region to make the volume well-defined. Consider the lattice $Z$ which has a fundamental region
$V∪(1+[0,1)∖V).$
Here, $V$ is a Vitali set containing 0. This fundamental region is not measurable, so it makes no sense to talk about its volume.
Another interesting question: is there a Banach–Tarski paradox for lattice fundamental regions?

The simplest way to fix this is to consider a region that contains at most one representative of each coset and whose closure contains at least one representative of each coset. This ensures the volume is well-defined (though I don’t know how to prove this).

**Definition 2.13.** The minimum distance of lattice $L$ is
$λ_{1}(L)==deff_{x∈L∖{0}}∣x∣$

I haven’t carefully investigated Minkowski’s results — I will update if I find a question or comment.

Please enable JavaScript to view the comments powered by Disqus.