1
$\begingroup$

Let $\mathbf{b}_1, \mathbf{b}_2, ..., \mathbf{b}_n$ be linearly independent $m$-dimensional vectors whose entries belong to $[0, M] \cap \mathbb{Z}$, for some $M \in \mathbb{N}^*$. Of course, $n \le m$ and I am mainly interested in the case $n < m$.

Let $L$ be the integer lattice whose basis is formed by these vectors. Hence, any $\mathbf{u} \in L$ can be written as $\sum_{i=1}^n c_i\mathbf{b}_i$ for $c_i \in \mathbb{Z}$.

Is there some method to derive upper-bounds to the number of points of $L$ that have norm smaller than or equal to $M$?

That is, an upper-bound to the cardinality of the following set:

$$\left\{ \mathbf{u} \in L : ||\mathbf{u}|| \le M \right\}$$

Here, $||\mathbf{u}|| := \sqrt{\sum_{i=1}^n u_i^2}$, that is, the Euclidean norm.

$\endgroup$
2
$\begingroup$

Let $b_1,\dots,b_n$ in $[-M,M]^m$ be linearly independent, and let $L = \sum_i \mathbb{Z}b_i$ be the lattice they generate. For $i = 1, \dots,n$, let $r_i$ be the smallest positive real number such that $L$ contains $i$ linearly independent vectors of $\ell^\infty$-norm $\leq r_i$. We have $$ 0 < r_1 \leq r_2 \leq \dots \leq r_n \leq M . $$ By a result of Henk (th 2.1 in this note by Boucksom), we have for any $c \geq 1$ the inequality $$ | \{ b \in L \ | \ ||b||_{\infty} \leq cM \ \}| \leq 2^n \prod_{i=1}^n \left( \frac{2cM}{r_i} + 1\right) \leq (2(2c+1)M)^n \prod_{i=1}^n r_i^{-1}. $$ On the other hand, a theorem of Minkowski (th 4.1 in Boucksom's note) yields $$ \prod_{i=1}^n r_i^{-1} \leq \frac{n!}{2^n} V, $$ where $V$ is the euclidean volume of $$ \{ (x_1,\dots,x_n) \in \mathbb{R}^n \ | \ ||\sum_{i=1}^n x_i b_i||_{\ell^\infty} \leq 1 \}. $$ Thus we get

$$ | \{ b \in L \ | \ ||b||_{\infty} \leq cM \ \}| \leq n!(2(2c+1)M)^n V, $$ for $c \geq 1$, and in particular an upper bound for your question is given by $n! (6M)^n V$. If the $b_i$'s are small, then $V$ is large (and so is the LHS).

$\endgroup$
  • $\begingroup$ Thank you for the answer. It is surely an upper-bound, but this factorial term makes it too big... It would be great if I could find a tighter bound. Do you think it is possible? Thank you again. $\endgroup$ – Hilder Vítor Lima Pereira Nov 21 '18 at 8:03
1
$\begingroup$

(I'm operating under the assumption that you want an upper bound that holds for all such lattices. If you have a specific lattice that interests you, then there are potentially other methods to try.)

For an easy bound, you can just use basic packing arguments to see that no rank $n$ lattice can have more than, say, $(2M+1)^n$ points of length at most $M \cdot \lambda_1(L)$, where $\lambda_1(L)$ is the length of the shortest lattice vector, which for you is at least $1$. In particular, assume without loss of generality that the lattice lies in $\mathbb{R}^n$ (by viewing the lattice as embedded in its span), and place an $n$-dimensional ball of radius $\lambda_1(L)/2$ around each lattice vector. Notice that these balls are disjoint and that they all lie in a ball of radius $M+1/2$. Therefore, the total volume of the small balls must be at most the volume of the larger ball, which immediately yields the bound.

For stronger bounds with a much more difficult proof, first notice that the densest such lattice should'' simply be $\mathbb{Z}^n$. This is morally true because $\mathbb{Z}^n$ has the minimal determinant amongst all such lattices. Since atypical'' set of volume $V$ in the subspace spanned by your lattice has $V/\det(L)$ points, the lattice with smallest determinant tends to have more points inside of it. E.g., this provably holds as $M \to \infty$.

I'm not sure if $\mathbb{Z}^n$ is exactly the densest such lattice for all $n,m, M$ (some related conjectures are false). But, we know that something close to this is true. In particular, in work with Regev, we showed that no lattice $L \subseteq \mathbb{R}^n$ whose sublattices $L' \subseteq L$ all satisfy $\det(L') \geq 1$ has ``significantly'' more points than $\mathbb{Z}^n$. Your lattices clearly satisfy this constraint, so the bound applies. Here's the precise statement, and there are of course more details in the paper:

Reverse Minkowski

I hope that the notation is clear. We write $rB_2^n$ for an $n$-dimensional ball of radius $n$, and you should think of our $\mathcal{L}$ as your lattice embedded in the subspace that it spans.

(You can almost certainly get tighter bounds for the specific class of rank $n$ lattices that are sublattices of $\mathbb{Z}^m$ (the restriction on the coordinates of the basis seems unlikely to matter much), but this might be sufficient for you.)

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.