1
$\begingroup$

1- Can someone explain why we have the definition of dual of a lattice like $\Lambda^*=\{\vec{v}\in span(\textbf{B}): \langle \vec{v},\vec{x} \rangle \in \mathbb{Z}, \forall \vec{x} \in \Lambda\} $.

2- There is an explanation in the lecture note of Daniele Micciancio, (CSE206A) Spring 2007, here, but I cannot follow some parts of it.


enter image description here


$\endgroup$

2 Answers 2

3
$\begingroup$

For the highlighted lines, we first note that for any invertible matrix $M$ for the field of definition of the inner product we trivially have $$\langle \mathbf x,\mathbf y\rangle = \langle \mathbf x,M\cdot M^{-1}\mathbf y\rangle.$$ Using this with the matrix $M=\mathbf B^T\mathbf B$ and $\mathbf y=f(\mathbf x)$ we see that $$\langle x,f(\mathbf B)\rangle=\langle \mathbf x,\mathbf B^T\mathbf B(\mathbf B^T\mathbf B)^{-1}f(\mathbf B)\rangle.$$

We now note another property of the inner product that $$\langle M\mathbf x,\mathbf y\rangle=(M\mathbf x)^T\mathbf y=\mathbf x^TM^T\mathbf y=\langle \mathbf x,M^T\mathbf y\rangle.$$ It follows then that $$\langle \mathbf x,\mathbf B^T\mathbf B(\mathbf B^T\mathbf B)^{-1}f(\mathbf B)\rangle=\langle \mathbf B\cdot\mathbf x,\mathbf B(\mathbf B^T\mathbf B)^{-1}f(\mathbf B)\rangle.$$

$\endgroup$
0
1
$\begingroup$

Thanks to @Daniel S, for noting a property of inner product: looking an inner product as product of a row vector and a column vector.

I just write it for clarity in the case someone is not familiar with basic mathematical concepts.

We look at vectors as column vectors (so $\vec{v}^{T}$ is a row vector). $\mathbf{B}\in\mathbb{R}^{m\times n}$, where $m\geq n$, is the basis of the lattice.

... since every linear function $f:\mathcal{L}\rightarrow \mathbb{Z}$ can be written as $f_{\vec{v}}(\vec{y})=\langle\vec{v},\vec{y}\rangle$

For $\vec{y}_{m\times1}\in\mathcal{L(\mathbf{B}_{m\times n})}$, we can write it based on the basis of the lattice: $\exists\vec{x}\in\mathbb{Z}^{n}$: $\vec{y}=\mathbf{B}\vec{x}$.

$$f(\vec{y})=f(\mathbf{B}\vec{x})=f(\sum_{i=1}^{n}x_{i}\vec{b}_{i})$$

Because when multiplying a column vector to basis matrix from right, it's equivalent to linear combinations of column vectors of the basis matrix. All the time, the first (second, ...) element of $\vec{b}_{1}$ ($\vec{b}_{2},\ldots$) multiplied by first (second, ...) element of $\vec{x}$.

$$=\sum_{i=1}^{n}x_{i}f(\vec{b}_{i})$$

because $f$ is linear.

$$=\langle\vec{x},[f(\vec{b}_{1},\ldots,f(\vec{b}_{n}))]^{T}\rangle$$

by looking at this serie as an inner product of two vectors. Note $f:\mathcal{L}\rightarrow\mathbb{Z}$, so $f(\vec{b}_{i})\in\mathbb{Z}$ and $[f(\vec{b}_{1}),\ldots,f(\vec{b}_{n}))]\in\mathbb{Z}^{n}$ is a vector.

$$=\vec{x}^{T}_{n\times1}\cdot\overrightarrow{f(\mathbf{B}_{m\times n})}_{n\times1}$$

by looking at inner product as product of a row vector and a column vector.

$$=\vec{x}^{T}_{n\times1}\mathbf{B}^{T}_{m\times n}\cdot(?)\overrightarrow{f(\mathbf{B})}_{n\times1}$$

trying to construct $\mathbf{B}\vec{x}$, the argument of $f$ at the first line.

$$=\vec{x}^{T}_{n\times1}\mathbf{B}^{T}\mathbf{B}_{m\times n}\cdot(\mathbf{B}^{T}\mathbf{B})^{-1}\overrightarrow{f(\mathbf{B})}_{n\times1}$$

$\mathbf{B}\in\mathbb{R}^{m\times n}$, where $m\geq n$ is a rectangular matrix; it doesn't have inverse. $\mathbf{B}$'s columns are basis vectors of the lattice, so are linearly independent. $\Rightarrow$ $(\mathbf{B}^{T}\mathbf{B})_{n\times n}$ has inverse (Note: $(\mathbf{B}\mathbf{B}^{T})_{m\times m}$ is not invertible).

$$=(\mathbf{B}\vec{x})^{T}_{m\times1}\cdot\underbrace{\left(\mathbf{B}_{m\times n}(\mathbf{B}^{T}\mathbf{B})^{-1}_{n\times n}\cdot\overrightarrow{f(\mathbf{B})}_{n\times 1}\right)}_{\vec{v}}$$

$\vec{v}=\left(\mathbf{B}_{m\times n}(\mathbf{B}^{T}\mathbf{B})^{-1}_{n\times n}\cdot\overrightarrow{f(\mathbf{B})}_{n\times 1}\right)$ is in the linear span of the lattice. Because $f:\mathcal{L}\rightarrow\mathbb{Z}$ and $\mathbf{B}\in\mathbb{R}^{m\times n}$, so $\overrightarrow{f(\mathbf{B}_{m\times n})}\in\mathbb{Z}^{n}$ $\Rightarrow\vec{v}'=(\mathbf{B}^{T}\mathbf{B})^{-1}_{n\times n}\cdot\overrightarrow{f(\mathbf{B}_{m\times n})}_{n\times1}\in\mathbb{R}^{n}$ $\Rightarrow\vec{v}=\mathbf{B}_{m\times n}\cdot(\mathbf{B}^{T}\mathbf{B})^{-1}f(\mathbf{B})=\mathbf{B}_{m\times n}\cdot\vec{v}'_{n\times1}\in span_{\mathbb{R}}(\mathbf{B}_{m\times n})=\{\mathbf{B}_{m\times n}\vec{w}:\vec{w}\in\mathbb{R}^{n}\}$.

$$=\langle\vec{y},\vec{v}\rangle$$

again by looking inner product as product of a row vector and a column vecror.


Finally, we've reached to the equality $f(\vec{y})=\langle\vec{y},\vec{v}\rangle$ for all $\forall\vec{y}\in\mathcal{L}(\mathbf{B})$ and some vector $\vec{v}\in span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}))=span_{\mathbb{R}}(\mathbf{B})$ (because $\mathbf{B}$ is the basis of the lattice $\mathcal{L}(\mathbf{B})$, so $span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}))=span_{\mathbb{R}}(\mathbf{B})$).

In other words, we can write a linear function $f:\mathcal{L}\rightarrow\mathbb{Z}$ as $f(\vec{y})=f_{\vec{v}}(\vec{y})=\langle\vec{v},\vec{y}\rangle$ for some $\vec{v}\in span_{\mathbb{R}}(\mathbf{B})$, i.e., represent it with a vector.

Now we substitute this representation in the natural definition of duality for lattices:

$$\left(\mathcal{L}(\mathbf{B})\right)^{*}=\{f:\mathcal{L}(\mathbf{B})\rightarrow\mathbb{Z} \ | \ f \ \text{is linear}\}=\{\vec{v}\in span_{\mathbb{R}}(\mathbf{B}): \langle\vec{v},\vec{y}\rangle\in\mathbb{Z},\forall\vec{y}\in\mathcal{L}(\mathbf{B})\}$$


As it was noted in Wikipedia, It should be emphasized that a lattice and its dual are fundamentally different kinds of objects; one consists of vectors in Euclidean space, and the other consists of a set of linear functionals on that space.

$\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.