Score:3

Equivalence of lattice definitions

mq flag

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.

Score:1
sz flag

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).

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.