Number of *distinct* dot products of an integer vector by elements of a hyper-rectangle

Question

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.

Answer 1

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.

Answer 2

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