Consider the following set-up:
A person has a vector of with integer entries, which is not known to you. The person refuses to reveal the vector to you; however, you may supply another vector with integer entries, and they will tell you the result of taking the dot product with the hidden vector.
A straightforward way to extract the value at the $i$-th index is to supply the vector $(0, 0, \ldots, 1, \ldots, 0)$ - where the number $1$ occurs at the $i$-th position. Doing this for all values of $i$ lets you recover the hidden vector in number of steps equal to the length of the vector.
Is there a shorter way to just extract the absolute value of the largest entry (or an upper bound for the same) in this set-up? For example, if it is known that all the entries happen to be positive integers, one can supply the vector $(1, 1, \ldots, 1)$ and obtain an upper bound for the largest entry in a single step.
Also, if it happens that it is not possible to do this in fewer than $n$ steps (where $n$ is the length of the vector), could you please refer me to a proof for why this is the case?
Another variant of the question - is it possible to determine the positions of the negative numbers in the vector in fewer than $n$ steps?
Edit: I came across a variant of this question a while ago. The set-up was almost identical, except the vector had positive integer entries instead of just integer entries. The solution involved finding an upper bound $M$ for the largest term (exactly as I have outlined above, and then taking the dot product with the vector $(1, M, M^2, \ldots, M^{n-1})$ to get a number whose base-$M$ expansion was the entries of the vector.
I found this really interesting, and I was wondering if this could be generalized to either the full set of integers or the rationals. Since it seems unlikely that one will be able to determine the full vector in fewer than $n$ steps, I am interested in knowing whether it will be possible to determine a simpler property - such as the positions of the negative entries - in fewer than $n$ steps.
Without any assumption on the vector, you cannot do this in fewer than $n$ attempts. Let the true secret vector be $\mathbf{a}$. It's enough to show that for any $\mathbf{u}_1, \ldots, \mathbf{u}_{n-1} \in \mathbb{Z}^n$ there exists another vector $\mathbf{b}$ in $\mathbb{Z}^n$ with different maximum entry and such that $\mathbf{a} \cdot \mathbf{u}_i = \mathbf{b}\cdot \mathbf{u}_i$ for all $i$. That way, no matter what your $n-1$ "questions" were, you can never tell if the answer was $\mathbf{a}$ or $\mathbf{b}$.
The span of $\mathbf{u}_1, \ldots, \mathbf{u}_{n-1}$ in $\mathbb{Q}^n$ has dimension at most $n-1$, so its orthogonal complement has dimension at least 1. The orthogonal complement has a nonzero integer vector $\mathbf{v}$, because if you pick any nonzero element you can multiply it by the lcm of the denominators of its entries to get an integer vector. Add a large enough multiple of $\mathbf{v}$ to $\mathbf{a}$ so that you get a vector with a different maximum entry - call this $\mathbf{b}$. Now $\mathbf{a} \cdot \mathbf{u}_i$ and $\mathbf{b}\cdot \mathbf{u}_i$ are equal for all $i$, because they differ by something orthogonal to the $u_i$, but $\mathbf{a}$ and $\mathbf{b}$ have different maximum entries.
The same argument applies to locating the negative entries: by adding or subtracting a large enough multiple of an integer vector in the orthogonal complement to $\mathbf{a}$ you can obtain a vector with negative entries in different places with the same dot products with the $\mathbf{u}_i$s.
This is closely related to the "guess the polynomial" game which has appeared on this site before: your enemy has a secret polynomial $p(x) \in \mathbb{Z}[x]$ which you have to guess and will only answer questions of the form "What is $p(r)$?" for $r \in \mathbb{Q}$. If the coefficients are nonnegative then you can do it in two steps: ask for $p(1)$ to get a bound on the coefficients then for $p(M)$ where $M$ is sufficiently large that the trick in the OP works. The only difference is that you are not given the degree of the polynomial whereas in this question you know $n$.