Cool riddle involving integer vectors

Question

Let $V$ be a $k$-dimensional vector ($k$ is given) of the form $$V=[n_1, n_2, ..., n_k],$$

where $n_1, n_2, ..., n_k$ are positive integers.

Your objective is to determine $V$ by choosing $T$ vectors of your choice, and receiving their dot products with $V$ respectively.

for example, if my vector is $[1, 2]$, and your vectors are $[1, 1], [5, 3/2]$, you will get their dot poducts: $([1,1]*[1,2] =3, [5,3/2]*[1,2] = 8)$

What is the minimum number of vectors $T$ that you need to choose to determine $V$? (bonus: add the requirement that your vectors must consist of positive integers as well)

(p.s. there exists a solution $T<k$, it's not that obvious)

The solution to this riddle(s) is amazing, and i'll post it in a couple of days.

Answer 1

If any real numbers are allowed then $ T=1 $: choose the vector $(e, e^2,\ldots , e^n) $ and use the fact that $ e $ is transcendental. It is not constructive but you know that different vectors will output different dot products.

Edit: if $(a_1,\ldots, a_n) $ and $(b_1,\ldots, b_n) $ are two vectors that output the same number, then $ e $ is a root of the polynomial with integer coefficients $$\sum (a_i -b_i) X^i$$ therefore all its coefficients are zero.

Answer 2

I would choose $T = k$ vectors $a_1, a_2, \ldots, a_k$, which are linearly independent.

Then, I would create a matrix $A$ which rows corresponds to each vector $a_i$. For construction, $A$ is invertible.

Moreover, given $q_i$ as the dot product of $V$ with $a_i$, I create the column vector $q = [q_1 ~ q_2 ~ \ldots ~ q_k]^\top.$

Finally, I can calculate $V$ as follows:

$$V = A^{-1}q.$$

Additionally, I can avoid the inversion of matrix $A$ if I choose $a_i$ as versors, i.e. $a_i$ has only $0$ components, and the $i$-th entry is $1$. In this case, $A$ is the identity matrix, and I obtain that:

$$q_i = n_i.$$

Answer 3

If $V$ were limited to entries at most $b$, then the solution would be easy: query $$ V \cdot [b^0, b^1, \dots, b^{k-1}]$$ The result, when read in base-$b$, would be the vector $V$. However, this would be foiled for any constant choice of $b$ because the entries of $V$ could be arbitrarily large. (Any scheme to "guess" such a $b$, for example, by repeatedly doubling, could be similarly fooled).

However, it's easy to get a $b$ large enough: $V \cdot [1, 1, \dots, 1]$ is the sum of the entries in $V$. Since all of the entries in $V$ are strictly positive, this dot product is strictly bigger than any entry in $V$ (as it's the sum of the largest element and the rest of the elements, which are at least 1).

Thus, the first query is $b = V \cdot [1, 1, 1, \dots, 1]$.

The second query is $v = V \cdot [b^0, b^1, b^2, \cdots, b^{k-1}]$.

Then $V$ is the result from reading the digits of $v$ in base-$b$, so $t \leq 2$.

(Since any number of vectors have the same dot product, $t \geq 2$ so this does give $t = 2$ exactly)

---

This relies heavily on the positiveness of the entries of $V$. Can the problem be solved in fewer than $k$ queries when the entries of $V$ are allowed to be negative?

---

I remember a very similar problem, that tasks you with determining the coefficients of a polynomial $q$ with only non-negative integer as coefficients with as few integer queries as possible. (The method looks about the same as this problem).

A link to a blog post concerning this problem is here.

Answer 4

Here is my answer:

Let $I = [ln(2),ln(3),...,ln(p_k)]$ where $p_k$ is the $k^{th}$ prime.

$V*I=n_1ln(2)+n_2ln(3)+...+n_kln(p_k) = ln(2^{n_1}*3^{n_2}*...*p_k^{n_k})$

Therefore, by taking the prime factorizations of $e^{V*I}$, and looking at the exponents, we can deduce what $V$ is.

So by choosing $I$ and only $I$ to be our vector, we can fully deduce $V$ (and $minT=1$).