# Number of points in a lattice and an oblong box

I have a very simple question in geometry of numbers. (It is a slight modification of Counting points on the intersection of a box and a lattice .) There's a bound I can easily prove, and it's good enough for my purposes, but it may be embarrassingly suboptimal.

Let $$S = (N_1,2 N_1] \times \dotsb \times (N_n,2 N_n]$$, where $$N_i\geq M\geq 1$$. Define the lattice $$L$$ as the preimage of $$r_1 \mathbb{Z} \times \dotsb r_n \mathbb{Z}$$ under an affine linear map $$\vec{v} \mapsto A \vec{v} + \vec{b}$$, where $$r_i\geq M$$ are integers and $$A=\{a_{i,j}\}$$ is a non-singular $$n$$-by-$$n$$ matrix such that $$a_{i,j}\in \mathbb{Z}$$, $$|a_{i,j}|\leq C$$. How do you bound the number of points $$|S\cap L|$$ in $$S\cap L$$?

It is simple to show (chopping $$A S$$ into hypercubes of side $$M$$) that $$|S\cap L| \leq (4 C n)^n \prod_{i=1}^n \frac{N_i}{M}.$$ How much better can one do? Can one replace $$(4 n)^n$$ by $$2^n n!$$, say? Or (much more ambitiously) $$\prod_{i=1}^n N_i/M$$ by $$\prod_{i=1}^n N_i/r_i$$?

(It would be interesting, for starters, to combine the argument above with Davenport's Lemma (as in Counting number of points on a lattice in a hypercube), but doing so in such a way as to obtain a real improvement doesn't seem obvious.)

## 1 Answer

It does seem to me that one can do better in some circumstances by using Davenport's Lemma after all. We recall (see Davenport's On a principle of Lipschitz): for $$B$$ convex, $$\bigl(|B\cap\mathbb{Z}^n|-\mathrm{vol}(B)\bigr) \leq \sum_{m=0}^{n-1} V_m,$$ where $$V_m$$ is the sum of the $$\mathrm{vol}(\pi(B))$$ under all projections $$\pi$$ obtained by setting $$n-m$$ coordinates to $$0$$.

Let $$B = R (A S + \vec{b})$$, where $$R(x_1,\dotsc,x_n) = (x_1/r_1,\dotsc,x_n/r_n)$$. Then $$|S\cap L| = |B\cap \mathbb{Z}^n|$$, and $$\mathrm{vol}(B) = \frac{\det(A)\cdot \mathrm{vol}(S)}{\prod_{i=1}^n r_i}\leq C^n n! \prod_{i=1}^n \frac{N_i}{r_i}.$$

Now, the ($$m$$-dimensional) volume of $$\pi(B)$$ for $$\pi$$ a projection obtained by setting $$n-m$$ coordinates to $$0$$ is at most $$2^{m-n}$$ times the sum of the $$\mathrm{vol}(\pi(R P))$$ over all $$m$$-dimensional sides $$P$$ of the parallelepiped $$AS$$. It is clear that $$\mathrm{vol}(\pi(R P)) =\mathrm{vol}(\pi(P))/\prod_{i\in I} r_i$$, where $$I$$ is the set of coordinates that $$\pi$$ does not set equal to $$0$$. We know that $$\mathrm{vol}(\pi(P)) \leq \mathrm{vol}(P)$$ because, in general, (orthogonal) projections do not increase volumes. We also know that $$\mathrm{vol}(P) \leq \prod_{i\in I'} C n N_i$$, where $$I'$$ is the set of indices that vary as we traverse the side $$P$$. (Here $$C n N_i$$ is an upper bound on the length of the image under $$A$$ of the side $$(N_i,2 N_i]$$.) Hence $$\textrm{vol}(\pi(R P)) \leq (C n)^m \frac{\prod_{i\in I'} N_i}{\prod_{i\in I} r_i}.$$ We are summing over $$\binom{n}{m}$$ projections and $$\binom{n}{m}$$ sides. Thus, the contribution of a given $$m$$ to the right side of Davenport's Lemma is at most $$2^{-n} (2 C n)^m \binom{n}{m}^2 \cdot \frac{\prod_{i=1}^m N_i}{\prod_{i\in I} r_i},$$ where we assume that $$N_1,N_2,\dotsc$$ are sorted in decreasing order, and $$I$$ is the set of $$m$$ indices corresponding to the $$m$$ smallest values of $$r_i$$. We sum over all $$m\leq n$$, and, obtain a total of \begin{aligned} 2^{-n} \sum_{m=0}^{n-1} (2 C n)^m \binom{n}{m}^2 \cdot \max_{|I|=|I'|=m} \frac{\prod_{i\in I'} N_i}{\prod_{i\in I} r_i}&\leq \frac{(C n)^{n-1}}{2} \binom{2n}{n} \cdot \max_{|I|=|I'|

We conclude that $$|S\cap L| \leq C^n n! \prod_{i=1}^n \frac{N_i}{r_i} + O\left( (2 C n)^{n-1} \max_{|I|=|I'| That doesn't improve on the original bound in full generality, however (except in so far as it replaces $$(4 C n)^n$$ by $$C^n n! + O((2 C n)^{n-1})$$.