# Proving lower bound on number of queries to oracle?

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are integers. How do you determine what $p(x)$ is in the quickest way possible?

Question : How to prove the lower bound that you need at least $d$ many queries if the input polynomial has degree $d$?

$d$ queries at $a_1$, $\ldots$, $a_d$ cannot determine a polynomial $P$ of degree $d$ because all the polynomials $P + k(x-a_1)\cdots(x-a_d)$ give the same output for all those queries. So you need at least $d+1$. Clearly, $d+1$ are also sufficient.