# Given an integer lattice, how to count the number of points whose norm is smaller than some bound $M$?

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.

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).

• 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. – Hilder Vítor Lima Pereira Nov 21 '18 at 8:03

(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:

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.)