4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I forgot to include that for the case $g(0)$, the oracle simply returns a random value - so your answer would still hold. $\endgroup$ – user2505282 May 9 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.