Distinguishing between a Polynomial and a Laurent Polynomial

Question

Let $f(x) \in \mathbb{Z}_p[x]$ (for a prime $p \gg d$) be a polynomial of degree $d$, and let $g(x)$ be a Laurent polynomial with the same degree and only the first negative exponent term ($g(x) = \frac{a_{-1}}{x} + a_0 + a_1 x + \dots a_dx^d$) over the same field.

Now, say we are given oracle access to both these functions with the additional condition that we can only $< d$ queries (Else we can just ask $d+1$ queries and interpolate the points to check if the function is a polynomial or not - this was the only way I could think of.)

Is this possible - if the test doesn't have to be perfect and can have some false positives or negatives?

Answer 1

Is this possible

Unless querying $g(0)$ gives you a distinguishable error for a Laurent polynomial, and assuming that the values $a_0, …, a_d$ are equidistributed (for both the Laurent and normal polynomial cases), it's not possible if you are limited to $d$ queries.

The question is equivalent to asking "you're given Oracle access to a Laurent polynomial $g(x) = \frac{a_{-1}}{x} + a_0 + a_1 x + \dots a_dx^d$, can you determine whether $a_{-1} = 0$?" [1]

Well, for any fixed value of $a_{-1}$, the $d$ queries can result in any of the $p^d$ possible sets of responses with equal probability (because there exists a unique polynomial $a_0 + a_1 x + \dots a_dx^d$ that results in the $d$ required $g(x) - \frac{a_{-1}}{x}$ values). Because this is true for any value of $a_{-1}$, we cannot gain any information on its value (including whether or not it is 0).

---

[1]: Along with the convention that $\frac{0}{0} = 0$