# Find a polynomial in two or three queries

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

• Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.

• Output: The $d$ coefficients of polynomial $f(x)$.

My algorithm: let

$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$

Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.

However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?

• You keep changing the question. Perhaps you should first decide on your question and only then ask it. Otherwise it can be somewhat frustrating for the answerer. Oct 13, 2017 at 12:40
• What does $\mathbb{Z}^+$ means?
– md5
Oct 13, 2017 at 12:44
• set of positive integers Oct 13, 2017 at 12:45
• BTW for your algorithm, the coefficients can be computed in $O(n^2)$ instead of $O(n^3)$ with Lagrange's closed formula.
– md5
Oct 13, 2017 at 12:49
• Exact same question, worded differently: math.stackexchange.com/questions/446130/… Oct 14, 2017 at 0:38

You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your choice and read off the coefficients from the base $x$ expansion.
Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.
• Sorry I did not get this part " I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero " Oct 13, 2017 at 13:09
• This is an adversary argument. Your algorithm asks the black box for the value of $f$ at $d-1$ places, and it always answers zero. I show that this is not enough for you to deduce the value of $f$. Oct 13, 2017 at 13:10