Let $Q$ an unknown quadratic form in an $n$-dimensional space. You can ask questions "What is $Q(v)$?"
What is the least number of questions you need to ask to check if $Q$ is positive definite?
Attempt Consider a quadratic form $$Q(x)=x_1^2+x_2^2+...+x_s^2-x_{s+1}^2-...-x_r^2$$ You need to ask at least $r$ questions to make a definite conclusion about $Q$. But how can I prove that $r$ is enough for any form? True that any quadratic form can be transformed into the form above, but we cannot make transformations
Makes all the difference whether the answer for a vector is just (positive/negative) or if we are told a numeric value; looking at the wording again, apparently we get a numeric value.
My first guess is the triangular number $n(n+1)/2.$ ADDED: yes, that is correct. Take a standard basis. First check $Q$ at all points with just a single $1,$ other entries $0.$ This gives the diagonal of the Gram matrix. Then check $Q$ on all vectors with exactly two entries equal to $1$ and otherwise $0.$ Those give all the off diagonal entries of the Gram matrix.
in dimension 2. Suppose the actual form is $x^2 + 200 xy + 9999 y^2.$ I ask for the form at $(1,0)$ and am told $1.$ Good start. I ask for the form at $(0,1)$ and am told $9999.$ In order to find out the $200$ I can ask at $(1,1).$ I am told $10200.$ One version of the parallelogram law is $$ 2 \langle v,w \rangle = Q(v+w) - Q(v) - Q(w) $$ so i have, in this basis, Gram matrix $$ \left( \begin{array}{cc} 1 & 100 \\ 100 & 9999 \end{array} \right) $$
which is indefinite.