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?


1 Answer 1


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.


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.