4
$\begingroup$

I have faced a problem in my work and I will appreciate any hint/reference as I am not much into the lattice problems.

Assume an n-dimensional lattice $\Lambda_n$ with generator matrix $G$. Note that lattice points are not necessarily integer, i.e., $x\in \mathbb{R}$ where $x$ is a lattice point. Is there a way to count/estimate/bound the number of lattice points inside and on an n-ball?

any hint or reference to appropriate literature is appreciated

$\endgroup$
  • $\begingroup$ You mean to say that the lattice points are the images of some integer lattice under a linear transformation, and therefore $x\in\mathbb R^n$? So you might as well ask for integer lattice points in some $n$-dimensional paraboloid. Not that I think that formulation is any easier, mind, just thinking out loud. What kind of performance are you looking for? Would a scan conversion which gives an exact answer $m$ (i.e. there are $m$ points inside the ball) in time $O\left(m^{(n-1)/n}\right)$ be preferable to one which uses the bounding box for a very loose bound in $O(1)$? $\endgroup$ – MvG May 2 '14 at 13:05
  • $\begingroup$ I was googling about the lattice points in an n-ball and found some papers about integer lattices (Gauss' circle problem) but in my problem the lattice is not integer. With $x\in \mathbb{R}$ I mean that the entries of the lattice point (vector $x$) are real numbers. I am not sure if the exact number of the lattice points inside an n-ball is solved but even a bound can be enough to proceed with my problem. $\endgroup$ – M.X May 2 '14 at 13:38
  • $\begingroup$ What do you mean by “solved”? Sure you can compute that number, a brute force enumeration will yield the count eventually. On the other hand, a closed formula might be unrealistic. $\endgroup$ – MvG May 2 '14 at 14:08
4
$\begingroup$

The $n$-volume of the fundamental parallelotope is the absolute value of the determinant of $G.$

The $n$-volume of the ball of radius $1$ is, in shorthand, $\pi^{n/2}/ (n/2)!,$ or $$ \omega_n = \frac{\pi^{n/2}}{\Gamma \left( 1 + \frac{ n}{2} \right)}. $$ The volume of the ball of radius $R$ is $\omega_n R^n. $

So, there is your estimate of the count, $\omega_n R^n / |G|.$

$\endgroup$
  • $\begingroup$ Are you aware of a reference for this fact? $\endgroup$ – jvnv Sep 25 '17 at 12:12
  • $\begingroup$ @jvnv looked at your posts, not sure what part of this could be a problem for you. The volume of the ball should be in any mathematical statistics book; the easiest method is induction by 2, even/odd dimension, using polar coordinates for the integral. Note that I am assuming $G$ expresses a basis of the lattice as its rows, so the Gram matrix is actually $G G^T.$ For anything in that area, try SPLAG by Conway and Sloane. Sphere Packing Lattices and Groups $\endgroup$ – Will Jagy Sep 25 '17 at 17:35
  • $\begingroup$ None of the parts is a problem for me, but I was just curious whether you had a reference for this fact. I expect this reasoning to be packed as a result somewhere. I will have a look into the book by Conway and Sloane; thanks for pointing this out. $\endgroup$ – jvnv Sep 25 '17 at 20:17

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.