1
$\begingroup$

I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell_2$-norm).

The brute force approach is to generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points and remove those with norm strictly greater than $1$. I was wondering if there is a more elegant approach to solving this problem. My initial thoughts are to attempt to cover the $d-1$ dimensional sphere with $n$ points and try and use those points to find out the "limits" that I can then use to generate the lattice coordinate vectors. Then I would define the lattice over the intervals defined by these limits $[a_1,b_1] \times [a_2,b_2] \times … \times [a_d,b_d]$. However, in my mind it is non-trivial to decide how many points to put on the sphere and the algorithm for actually determining the aforementioned limits.

Another approach would be to think of what are the coordinates of the maximum volume polyhedron that can be inscribed in the ball and then somehow constrain them to be on the lattice...Again, this seems to be non trivial. A similar line of thought would be to find the minimum volume polyhedron in which we can include the unit ball by enforcing the constraint that its vertices are lattice points. Then we can just subtract the distance between two lattice points and end up inside the sphere...

Are any of these problems with known solutions/non-trivial to solve?

Thank you in advance.

$\endgroup$
  • $\begingroup$ It's non-trivial to "generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points." If you're given a bad enough basis, you may have to consider arbitrarily large integer combinations of basis vectors before finding the shortest one. $\endgroup$ – Huck Bennett Jun 8 '18 at 19:51
  • $\begingroup$ @Huck Bennett: Thank you for your reply. I am not sure how my question relates to the SVP (pardon my ignorance, I come from a different field)? I am looking to list all the points on the lattice inside the unit ball. To simplify the problem, I have decided to choose a discretisation of the $[−1,1]$ interval (with say k=4 points in total) and construct all the $k^d$ possible coordinate points. Then one can remove those points that have norm greater than $1$. Any pointers to relevant work in the field would be appreciated! $\endgroup$ – Deathcrush Jun 8 '18 at 22:36
  • 2
    $\begingroup$ @Deathcrush what do you mean by "the lattice"? What lattice? How is it specified? I feel like you mean some scaling of the integer lattice, i.e. $t \mathbb{Z}^n$ for some $t \in \mathbb{R}$. Is that the case? Or do you mean an arbitrary lattice specified by a basis en.wikipedia.org/wiki/Lattice_(group)? $\endgroup$ – Sasho Nikolov Jun 9 '18 at 4:27
1
$\begingroup$

In general, even telling whether any such point exists is hard; it is equivalent to the Shortest Vector Problem (SVP), and it is conjectured that there is no polynomial-time algorithm for this problem.

$\endgroup$
  • $\begingroup$ Thank you for your reply @D.W. I am afraid I do not immediately see the connection between the SVP and intersecting the unit ball with the lattice defined over the $\ell_\infty$ unit ball? I am only interested in listing the points that lie inside the sphere, not finding the shortest vector in my lattice. $\endgroup$ – Deathcrush Jun 8 '18 at 22:16
  • $\begingroup$ @Deathcrush, You asked about intersecting a lattice with the $\ell_2$ unit ball. That's what my question addresses: it's hard to tell whether there exists a point in that intersection (as hard as the SVP). The $\ell_\infty$ unit ball is irrelevant so I'm not sure why you're bringing that up in your comment. $\endgroup$ – D.W. Jun 8 '18 at 23:19
  • $\begingroup$ Sorry @D.W, I am new to this area and my statements might be imprecise. In my simple case, I am not defining an arbitrary lattice. I am just discretising the $[-1,1]$ interval and using that to create a $d$ dimensional discrete structure (so I generate all possible $d$-vectors with coordinates from the aforementioned interval). In my simple mind this is like define a "discrete structure" (which I call lattice) over the $d$ dimensional cube of side $2$. Then the question was how to generate the points that lie inside the sphere without explicitly generating all those in the cube... $\endgroup$ – Deathcrush Jun 9 '18 at 10:14
  • $\begingroup$ @Deathcrush, please edit the question to clarify what you mean, then. $\endgroup$ – D.W. Jun 9 '18 at 15:04
  • 2
    $\begingroup$ @Deathcrush why not consider your lattice as a graph in the natural way and run BFS on it? $\endgroup$ – Sasho Nikolov Jun 9 '18 at 17:13

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.