1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

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

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.