Score:2

Duality Results for Some Module Lattices

cn flag

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?

Score:1
ng flag

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.

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.