Determine a polynomial with nonnegative integer coefficients with minimum queries.

Question

A friend of us makes up a polynomial with nonnegative integer coefficients. Our task is to find it out with a minimum number of queries. For each query we give him a nonnegative integer L and he computes P(L) and returns the result to us.

I know the beautiful trick to solve this - first ask P(1) to determine the sum of the coefficients that is at least as great as the greatest coefficent of the polynomial. Let T be the result of P(1). Then we ask P(T + 1). The value we get we covert to T + 1-base positional system and this way we figure the coefficients of the polynomial in 2 queries. I was wondering if it is possible to find it with a single querie or 2 queries is the lower bound of the worst case?

Answer 1

I would say that for a n-th degree polynomial, you'd need at most n+1 queries to solve it. This is because every polynomial of degree n has n+1 variables and this is solvable if you have n+1 equations (that are linearly independent).

Answer 2

You give your friend the number $\pi$. A polynomial with integer coefficients is completely determined by its value at $\pi$. Of course, any transcendental would do, in place of $\pi$.