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 coefficient of the polynomial. Let $T$ be the result of $P(1)$. Then we ask $P(T + 1)$. The value we get we convert to a $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 query or 2 queries is the lower bound of the worst case?

Answer 1

It's not possible to find it with a single query.

Suppose you had one, e.g. asking for a single number $n$. Then you can't distinguish between the cases where your friend's secret polynomial is $P(x) = 2x$ and $P(x) = x + n$; in both cases, they will reply with $2n$. (I know it's unlikely that he chose the second option, especially if $n$ is a non-obvious number like 372, but you can't rule it out.)

Answer 2

If this is allowed you could ask him to evaluate the polynomial at $\pi$ or another transcendental number.

The response will be something like $a_0 + a_1 \pi + a_2 \pi^2 + ...$, which is unique for all combinations of $\{a_i\}$, even for negative integers (by the definiton of transcendental numbers). The drawback of this method is just that depending on the format of the returned number it might be hard to decompose it.