3
$\begingroup$

I have a black-box polynomial function, with $n$ inputs. The only things I know for sure about this polynomial are that (a) it has no constant term, and (b) all coefficients and exponents are integers with magnitude below some $k$. (Exponents are positive, of course.) And I strongly suspect that some of the inputs aren't used at all.

Let's say I get to evaluate this polynomial once, with any set of real number inputs I choose. Is there a clever way of choosing those inputs, such that the answer allows me to unambiguously and straightforwardly recover the polynomial?

One way, of course, would be to make all the inputs unrelated irrational numbers, and then brute-force polynomials until I got a matching answer. If $n$ were $2$, I could feed in (say) $e$ and $\pi$ and see whether the answer matched $5e\pi^4+2e$, $7e^2\pi^2+4\pi$, etc. Obviously that would take some time.

Anything better?

Improve this question
$\endgroup$
  • $\begingroup$ You can't just take $n$ unrelated irrational numbers, as in your solution for $n=2$? $\endgroup$ – MonadBoy Dec 3 '15 at 10:56
  • $\begingroup$ @A.Sh I could, but I'd like something more efficient, where the recovery process was better than brute force enumeration of all polynomials. $\endgroup$ – Sneftel Dec 3 '15 at 10:57
3
$\begingroup$

Let $k < 10^m$, then using inputs $x_\imath=10^{-p_\imath*m}$ where $p_\imath$ are different primes greater than $k$ gives you your polynomial on a silver plate (coefficients can be seen in decimal record "as is" while positions they're in tell you exponents).

Improve this answer
$\endgroup$
  • $\begingroup$ That is an extremely straightforward recovery process. :) Beautiful! $\endgroup$ – Sneftel Dec 3 '15 at 11:05
  • $\begingroup$ That's just lovely. $\endgroup$ – MonadBoy Dec 3 '15 at 11:42

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.