4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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'|<n} \frac{\prod_{i\in I'} N_i}{\prod_{i\in I} r_i}\\ \lesssim \frac{(2 C n)^{n-1}}{\sqrt{2 \pi}} \cdot \max_{|I|=|I'|<n} \frac{\prod_{i\in I'} N_i}{\prod_{i\in I} r_i}. \end{aligned} $$

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'|<n} \frac{\prod_{i\in I'} N_i}{\prod_{i\in I} r_i}\right).$$ 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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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