# Distinguishing between a Polynomial and a Laurent Polynomial

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?

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$$
• Thanks, I forgot to include that for the case $g(0)$, the oracle simply returns a random value - so your answer would still hold. May 9, 2020 at 14:22