# Counting points on the intersection of a box and a lattice

Let $$A:\mathbb{Z}^n\to \mathbb{Z}^n$$ be non-singular. Consider a box $$B=[0,N_1]\times [0,N_2] \times \dotsc \times [0,N_n]$$. Let $$p_1,\dotsc,p_n$$ be primes (distinct, if you wish) and let $$L = p_1\mathbb{Z} \times \dotsb \times p_n \mathbb{Z}$$. Can one give a good bound on $$A^{-1} L \cap B$$? For instance, might $$|A^{-1} L \cap B| \ll \det(A) \prod_{i\leq n} (N_i/p_{\pi(i)} + 1)$$ hold for some permutation $$\pi$$ of $$\{1,2,\dotsc,n\}$$?

Assume all $$p_i$$ considerably larger than $$n$$ if needed. Also assume the matrix entries of $$A$$ to be bounded, if needed.

Note: I am not looking for an estimate with error term of size $$\prod_{j\leq n-1} N_j$$, say. That would be easy.

• what are $\mathbb{Z}_i$ for different $i$? – Fedor Petrov Jul 17 '19 at 18:28
• Sorry, meant $\mathbb{Z}$ – H A Helfgott Jul 17 '19 at 18:39
• If all $N_i$ are the same ($=N$) and the entries of $A$ are of absolute value $\leq c$, then it's easy to get a fairly good upper bound ($\leq \prod_i (c n N/p_i+1)$. The interesting case is that of $N_i$ not all of the same size. – H A Helfgott Jul 17 '19 at 18:58
• (Of course one can always chop a box into cubes, but I am hoping for something better ) – H A Helfgott Jul 17 '19 at 20:01

## 1 Answer

Probably not an answer, but too much for a comment:

Actually you can represent $$L$$ as a transformation of $$\mathbb Z^n$$ via $$L=\Lambda \mathbb Z^n$$, where $$\Lambda=(\lambda_{ij})$$ is the diagonal matrix such that $$\lambda_{ii}=pi$$. In the same way you can represent $$N$$ as $$ME_n$$ where $$M=(m)_{ij}$$ is the diagonal matrix with $$m_{ii}=(N_i)$$ and the unit cube $$E_n=[0,1]^n \subset \mathbb R^n$$ in the real vector space $$\mathbb R^n$$. Then we get: $$$$|A^{-1}L\cap N|=|\mathbb Z^n \cap (\Lambda^{-1}AM)E_n|$$$$ This suggests that $$\det(\Lambda^{-1}AM)$$ is useful, here. But this would be true only, if we would consider semi-open complete intervals in $$\mathbb R^n$$. So we must add another $$1$$ to each dimension on the $$\mathbb Z^n$$. This leads to the formula: $$$$|\mathbb Z^n \cap (\Lambda^{-1}AM)E_n| \leq \det (\Lambda^{-1}AM +I)$$$$

Maybe, some improvement can be achieved using the singular value decomposition $$$$\Lambda^{-1}AM = U \Sigma V^T.$$$$ This would give you the intersection of a rotated orthogonal grid $$U^T\mathbb Z^n$$ with some rotated parallelepiped $$\Sigma V^TE_n$$: $$$$|\mathbb Z^n \cap (\Lambda^{-1}AM)E_n|= |\mathbb Z^n \cap U\Sigma V^TE_n| = |U^T\mathbb Z^n \cap \Sigma V^TE_n|$$$$

• so $det(A)∏_{i≤n}(N_i/p_{π(i)}+1)$ iff $1 ≪ \det A$ for some permutation $π$. – Tobias Schlemmer Jul 18 '19 at 14:41