3
$\begingroup$

Imagine a vector $\boldsymbol{v}$ composed of integers, and the set $S$ of all integer vectors within a hyper-rectange, with one corner at the origin and other at $\boldsymbol{m}$. In other words: $S = \{\boldsymbol{u} : m_i \gt u_i \ge 0 \} $. Alternately, you may think of $S$ as the Cartesian product of a multiple integer ranges $[0, m_i)$. At any rate, imagine the set of all dot products $P = \{\boldsymbol{v} \cdot \boldsymbol{u} : u \in S\}$. Given a specific $\boldsymbol{v}$ and $\boldsymbol{m}$, what can be said of the cardinality of $P$?

For example: if $\boldsymbol{v} = \{1, 1, 10\}$, and $\boldsymbol{m} = \{3,3,3\}$, $P = 6 * 3 = 18$. This is because the first two dimensions of $\boldsymbol{m}$ both project to overlapping regions, while the final dimension does not.

In general, I'm curious if there is a faster way to compute $|P|$ than brute force, particularly for low dimensions (say < 10), but potentially large values of $m$ such that the total number of elements in $S$ is very large. Also, any literature references would be great. I feel like this belongs to some subproblem of integer latices, but I can't seem to get the right keywords.

$\endgroup$
3
$\begingroup$

This feels awfully related to the Subset-sum problem

If $m=2(1,1,\dots,1)$, all the dot products will be the sum of subsets of components of $v$. If two such scalar product coincide, then you have solved an instance of subset-sum problem. So, your problem is at least NP-complete, in the number of dimensions.

$\endgroup$
  • 1
    $\begingroup$ You want the m's to be 2 to be consistent with the usage in the post. $\endgroup$ – The Masked Avenger Dec 3 '14 at 15:09
  • $\begingroup$ Ah, yes, it was a bit confusing, not the convention I would take as natural. $\endgroup$ – Per Alexandersson Dec 3 '14 at 19:23
1
$\begingroup$

Just as with the Subset-sum problem, there are decent methods for calculating your set $P$ that will be much better than brute force. If $S_k=\{\mathbf{u}\in S:u_i=0\text{ for all } i>k\}$ and $P_k=\{\mathbf{v}\cdot\mathbf{u}:\mathbf{u}\in S_k\}$, then $P_{k+1}=\{p+u_{k+1}v_{k+1} : p\in P_k,0\le u_{k+1}<m_{k+1}\}$. Starting with $P_0=\{0\}$, calculate subsequent $P_k$ iteratively to recover $P=P_n$.

$\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.