5
$\begingroup$

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.

Setup: Let $e_{i}$ be an orthogonal (but not orthonormal) basis for $\mathbb{R}^{N}$. Define $\Lambda=\big\{\sum_{j=1}^{N}x_{j}e_{j}\mid x_{j}\in\mathbb{N}\big\}$ (where here I assume $0\in\mathbb{N}$). Now order the points in $\Lambda$ first by their $L^{1}$-norm, breaking ties lexicographically.

Question: Is there an efficient algorithm for producing the points in $\Lambda$ in order (up to some pre-defined bound)? Note that I want to walk this set in order, not produce it and then sort it.

Observations: This is easy to do if the $e_{i}$ are orthonormal. For instance, the problem is solved here. To make something like this work here, one would need to be able to efficiently answer the following. given positive real numbers $x_{1},x_{2},\ldots, x_{N}$, is there an efficient way to the numbers $\sum_{j=1}^{N}n_{j}x_{j}$ in increasing order, where $n_{j}\in\mathbb{N}$.

$\endgroup$
10
  • $\begingroup$ math.ucdavis.edu/~latte $\endgroup$ Apr 23, 2015 at 18:27
  • 1
    $\begingroup$ It feels like this is very close to the subset-sum problem: en.wikipedia.org/wiki/Subset_sum_problem $\endgroup$ Apr 23, 2015 at 18:36
  • $\begingroup$ @SteveHuntsman - LattE will only count the points $\endgroup$ Apr 23, 2015 at 19:31
  • $\begingroup$ @Per Alexandersson It does seem related, but I suspect that the problem I am considering is simpler as negative numbers are explicitly forbidden. Nonetheless, I'll be sure to look closely at subset sum to see if any of the techniques can be adapted. $\endgroup$
    – Paul
    Apr 23, 2015 at 19:52
  • $\begingroup$ @Paul: But you don't need negative numbers, only two subsets with same sum. This seems to be very similar to determining if two elements in $\Lambda$ has the same $L_1$-norm... $\endgroup$ Apr 23, 2015 at 19:58

2 Answers 2

1
$\begingroup$

I am going to try to answer the version of the Observation which seems to imply that the original "orthogonal" basis condition really is meant to mean "positive multiples of the standard basis vectors". So the problem is, given positive real numbers $x_1$, $x_2$, ..., $x_j$, produce the first $M$ elements of the set $x_1 \mathbb{N} + x_2 \mathbb{N} + \cdots + x_j \mathbb{N}$ in order. For simplicity I'm going to ignore the possibility of ties (this is easily dealt with). The basic idea is just to think of this as a shortest paths problem in the graph $\mathbb{N}^j$ (where the edges are given by the standard basis vectors $e_i$ and the weight of the edge $e_i$ is $n_i$.) Now Dijkstra's algorithm does this efficiently (we can just stop when the $M$ nearest neighbours are found). For this particular set up there are even some extra gains to be made -- since we know that the distance to a vertex is independent of the path used to get to it, we can choose a standard path to every vertex (e.g., go along the first dimension, then the second, ...) and only add those neighbours that extend such standard paths.

$\endgroup$
0
$\begingroup$

This question seems related to the case $N=2.$ I gave an answer suggesting that the continued fraction expansion of ${|e_2|}/{|e_1|}$ was the key. I haven't rechecked it. I'd venture that already the case $N=3$ would be much more difficult.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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