# Duality Results for Some Module Lattices

Let $$R$$ be the ring of integers of a cyclotomic field $$\mathbb{Q}(\zeta_n)$$, where $$n$$ is a power of two, and $$\boldsymbol{a} \in R_{q}^{m}$$, for $$m\in\mathbb{Z}^+$$, $$q\in\mathbb{Z}_{\geq2}$$ prime. Define the following $$R$$-modules, where $$I$$ is an ideal of $$R_{q} = R/qR$$: $$\begin{gathered} \boldsymbol{a}^{\perp}(I):=\left\{\left(t_{1}, \ldots, t_{m}\right) \in R^{m}: \forall i,\left(t_{i} \bmod q\right) \in I \text { and } \sum_{i} t_{i} a_{i}=0 \bmod q\right\}, \\ L(\boldsymbol{a}, I):=\left\{\left(t_{1}, \ldots, t_{m}\right) \in R^{m}: \exists s \in R_{q}, \forall i,\left(t_{i} \bmod q\right)=a_{i} \cdot s \bmod I\right\}. \end{gathered}$$ Ideals of $$R_{q}$$ can be written in the form $$I_{S}:=\prod_{i \in S}\left(x-\zeta_n^{i}\right) \cdot R_{q}=\left\{a \in R_{q}: \forall i \in S, a\left(\zeta_n^{i}\right)=0\right\}$$, where $$S$$ is any subset of $$\{1, \ldots, n\}$$ (the $$\zeta_n^{i}$$'s are the roots of $$\Phi_n$$ modulo $$q$$ ). Define $$I_{S}^{\times}=\prod_{i \in S}\left(x-{\zeta_n^{i}}^{-1}\right) \cdot R_{q}$$.

The authors of this paper then prove (Lemma 7): let $$S \subseteq\{1, \ldots, n\}$$ and $$\boldsymbol{a} \in R_{q}^{m}$$. Let $$\bar{S}=\{1, \ldots, n\} \backslash S$$ and $$\boldsymbol{a}^{\times} \in$$ $$R_{q}^{m}$$ be defined by $$a_{i}^{\times}=a_{i}\left(x^{-1}\right)$$. Then, with $$\widehat{\cdot}$$ denoting the dual of a lattice: $$\widehat{\boldsymbol{a}^{\perp}\left(I_{S}\right)}=\frac{1}{q} L\left(\boldsymbol{a}^{\times}, I_{\bar{S}}^{\times}\right).$$ My question is: while the containment $$\frac{1}{q} L\left(\boldsymbol{a}^{\times}, I_{\bar{S}}^{\times}\right)\subset \widehat{\boldsymbol{a}^{\perp}\left(I_{S}\right)}$$ is clear to me, I cannot prove the reverse direction $$\widehat{\boldsymbol{a}^{\perp}\left(I_{S}\right)}\subset\frac{1}{q} L\left(\boldsymbol{a}^{\times}, I_{\bar{S}}^{\times}\right)$$. How is the result obtained?

Their paper contains a proof of this, they "just" first appeal to lattice duality. In short, to prove that lattices

$$A = B,$$

it suffices (as you say) to prove that $$A\subseteq B$$ and $$B\subseteq A$$. What they do is use that

$$B\subseteq A\iff A^*\subseteq B^*,$$

and instead prove that $$A\subseteq B$$ and $$A^*\subseteq B^*$$. You can verify that their proof does precisely this, but with $$A = L(\cdot)$$, and $$B = \widehat{\alpha^\perp(\cdot)}$$ your lattices. Concretely, the containment you are missing is $$\widehat{L(\cdot)}\subseteq \frac{1}{q}\alpha^\perp(\cdot)$$. Regarding this, they state

This can be seen by considering elements of $$L(\cdot)$$ that correspond to $$s = 1$$.

I haven't checked, this but I imagine they mean that $$\widehat{L(\cdot)} = \{\vec t\in R^m :\forall \ell \in L(\cdot): \langle \ell, t\rangle\equiv 0\bmod q\}$$. If we replace $$L(\cdot)$$ in this with some subset $$S\subseteq L(\cdot)$$, we get a superset of $$\widehat{L(\cdot)}$$. It seems they in particular state you should replace $$L(\cdot)$$ with the subset corresponding to the choice of $$s = 1$$. Concretely, this gives us the containment.

$$\widehat{L(I_{\alpha^\times, \overline{S}}^\times)} \subseteq \{\vec t\in R^m : \forall i : (t_i\bmod q) = \alpha_i^\times\bmod I_{\overline{S}}^\times\}.$$

I don't know if this is precisely $$\frac{1}{q}\alpha^\perp(\cdot)$$, but their hint makes it sound like the right thing to look at.