Consider the definition of the dual lattice for a lattice $\mathcal{L}(\mathbf{B}_{m\times n})\in\mathbb{R}^{m}$ where $\mathbf{B}\in\mathbb{R}^{m\times n}$ and $n\leq m$ [sp2 Seminar, Luxembourg 2019, DualitySlides, page 5]:

$$ \mathcal{L}^{\vee}=\{\vec{v}\in span_{\mathbb{R}}(\mathcal{L}(\mathbf{B})): \langle\vec{v},\vec{w}\rangle\in\mathbb{Z}, \text{for all} \ \vec{w}\in\mathcal{L}(\mathbf{B})\} $$

The question is: 1- Why don't we write $\vec{v}\in\mathbb{R}^{m}$ instead of $span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}_{m\times n}))$ ? (Consider a full-rank case too, not just when $n<m$)

  • In [Daniel Dadush, Leo Ducas, "Intro to lattice algorithms and lattice cryptography", lecture 1, 2018] Dadush and Ducas want to introduce lattices. There is some explanation for duality representation of a lattice for defining the lattice concepts in their first lecture. I don't know whether this explanation is related to the above question or not.

enter image description here

2- Can someone explain the relation between above picture with the definition of dual lattice?


1 Answer 1


Consider the trivial example of $L = \mathbb{Z}\times \{0\}\subseteq\mathbb{R}^2$, e.g. a 1D lattice in 2 dimensions. One can compute with the first definition that

\begin{align*} L^\vee &= \{\vec v \in \mathbb{R}\times \{0\}\mid \forall \vec w\in L, \langle \vec v, \vec w\rangle\in\mathbb{Z}\}\\ &= \{\vec v\in\mathbb{R}\times\{0\}\mid \forall c\in\mathbb{Z}, cv_1\in\mathbb{Z}\}\\ &= \mathbb{Z}\times\{0\}. \end{align*}

If we do not require $\vec v\in\mathsf{span}_{\mathbb{R}}(\mathbb{Z}\times\{0\})$, we instead get

$$L^\vee = \{\vec v\in\mathbb{R}^2\mid \forall c\in\mathbb{Z}, cv_1\in\mathbb{Z}\} = \mathbb{Z}\times\mathbb{R}$$

As you mention, this isn't a lattice, and results regarding duality start failling apart.

  • $\begingroup$ For non full-rank lattices, the answer is a little clear but as it was mentioned, what about a full-rank case? $\endgroup$ Jan 17 at 21:38
  • 1
    $\begingroup$ I'm confused what you mean. The rank of a lattice is the number of linearly independent basis vectors of it. Consequentially, if you have $B\in\mathbb{R}^{k\times n}$ a lattice basis, and $L = B\mathbb{Z}^n$ a lattice, then $\mathsf{span}_\mathbb{R}(L)$ is the $k$-dimensional vector space $B\mathbb{R}^n$. When $k = n$ is full-rank, this is precisely $\mathbb{R}^n$, so the non-full-rank case is the only place where the distinction between $\mathsf{span}_\mathbb{R}(L)$ and $\mathbb{R}^n$ matters. $\endgroup$
    – Mark Schultz-Wu
    Jan 17 at 21:46
  • $\begingroup$ thanks. You're right. I think it's the answer to the first question. Do you have any idea about the second question? $\endgroup$ Jan 17 at 23:20
  • $\begingroup$ @user1035648 $\Lambda_p^\perp(A)$ is simply a scaled form of the dual lattice. To see this, note that $\equiv 0\bmod p$ is equivalent to $\in p\mathbb{Z}$, so scaling by $\frac{1}{p}$ you get the traditional definition of the dual lattice. $\endgroup$
    – Mark Schultz-Wu
    Feb 8 at 3:31
  • $\begingroup$ This is a true fact. The question is about justifying why, in the definition of dual lattice, vectors must come from the span of the lattice rather than the space in which the lattice exists. In the first question, we've examined it in a way; In the second question, we found some explanations (indicated with red rectangles) in a lecture note that appear to be related to our question. The note states if vectors in the definition of dual lattice don't come from the span of the lattice, it would contradict with the characteristic of the lattice, which is discreteness. This is my perception. $\endgroup$ Feb 8 at 12:59

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.