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

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.

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.

• Thanks that helps a lot! Not sure if I got the worry you brought up, but the rest makes sense. Oct 1, 2021 at 8:16
• 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.
– Mark
Oct 1, 2021 at 8:46