Score:0

Volume $q^n$ of a dual q-ary lattice in MR09

za flag

Given a matrix $\mathbf{A} \in \mathbb{Z}^{n \times m}$, $m$ sufficiently large with respect to $n$ and prime $q$. The rows of $\mathbf{A}$ are linearly independent with high probability. In MR09 the authors state that the number of vectors in $\mathbb{Z}_q^m$ belonging to the $q$-ary lattice $\Lambda_q^\intercal(\mathbf{A})$ is $q^{m-n}$ and therefore it follows that $\text{det}(\Lambda_q^\intercal(\mathbf{A})) = q^n$.

I understand that the dimension of the kernel of $\mathbf{A}$ (which is equivalent to the the dimension of the dual lattice) is $m-n$. However, I don't understand how the volume immediatley follows and would be thankful for an explanation.

Score:0
ng flag

Note that for a lattice $L\subseteq\mathbb{R}^n$, $\det(L)$ is the volume of a fundamental domain. There are often many of these objects, but there are two that are typically of primary interest:

  1. The Voronoi Cell $\mathcal{V}(L) = \{x\in\mathbb{R}^n\mid \forall \ell\in L\setminus\{0\}, \lVert x\rVert_2\leq \lVert x-\ell\rVert_2\}$, e.g. it is the points in $\mathbb{R}^n$ that are closer to 0 than any other lattice point.
  2. The Fundamental Parallelpiped --- for a basis $\mathbf{B}$ of the lattice, this is the set $\mathbf{B}[0,1)^n$ (or sometimes $\mathbf{B}[-1/2,1/2)^n$.

Up to some issues on the boundary, a fundamental domain "tiles space", meaning that the sum

$$L + D = \mathbb{R}^n$$

is a partition. If we assume the lattice is $q$-ary, we can reduce everything mod $q$ to get that $(L\bmod q) + (D\bmod q) = \mathbb{R}/q\mathbb{R}^n$ is a partition as well [1]. Taking volumes, we get that $$|L\bmod q||D\bmod q| = q^n\implies |L\bmod q| = \frac{q^n}{|D|} = \frac{q^n}{\det L}.$$ What you want then follows from using that the lattice is $m$-dimensional, and has $|L\bmod q| = q^{m-n}$ points, so the determinant must be $q^n$.


[1] There may be some issues with particularly irregular fundamental domains $D$ here (in particular fundamental domains that are not contained in $[-q/2, q/2)^n$, but if you let $D$ be the Voronoi cell everything seems fine, and I am not even sure if this worry I mention is for a particular reason.

za flag
Thanks that helps a lot! Not sure if I got the worry you brought up, but the rest makes sense.
Mark avatar
ng flag
You need that the modular reduction preserves being a partition. This is clear to me provided that $D\subseteq [-q/2, q/2)^n$, as then modular reduction "just" squishes all of these regions together (and is the identity on the copy of $D$ at the origin). The voronoi cell of a $q$-ary lattice always satisfies this, which is why I mentioned it in particular. It is plausible that modular reduction preserves being a partition even for more general $D$, but then modular reduction is no longer the identity on the copy of $D$ at the origin, and I haven't thought through what happens then.
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.