3
$\begingroup$

I have come across two supposedly identical definitions of lattices in the lattice crypto literature. There are mainly these two definitions of lattices, the first considers lattices as discrete additive subgroup and the second is the common vector space definition.

Definition 1: Discrete additive subgroup $$\forall x \neq y \in \mathcal{L}, ||x-y|| \geq \varepsilon, \quad \exists \varepsilon >0 \quad \text{(discrete)} $$ $$ \forall x,y \in \mathcal{L}, x - y \in \mathcal{L} \quad \text{(additive subgroup)} $$

Definition 2: Given $n$ linear independent vectors $b_1, ..., b_n \in \mathbf{R}^m$ the lattice generated by them is defined as $$\mathcal{L}(B) = \left\{ \sum_{i=1}^{n} x_i b_i : x_i \in \mathbf{Z} \right\}$$

I wonder to what extent the definitions are the same. Assuming a lattice is defined as in definition 2, it is not hard to see that this is also automatically a discrete additive subgroup. Here the vector space axioms take effect and in addition one can use that the successive minimum generates the "distance" (discrete property) which is necessary for an additive subgroup.

But. And this is the interesting point and at the same time my question. Is it possible to transfer/transform definition 2 into definition 1? How would that look like? So the question is, given definition 1, how does one show equivalence to definition 2?

Thanks for upcoming answers!


*My question may be more mathematical, but I think here are enough experts on the mathematical background of lattices.

$\endgroup$

1 Answer 1

1
$\begingroup$

It is a natural question you have, I refer you to the lectures of professor L.Ducas, which covers lattices in more mathematical manner, in the first lecture you'll proof the implication from definition 1 to definition 2 (Theorem 2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.