Finding unknown integer-valued polynomials using inequalities

Question

I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here.

Suppose you are given the degree of an unknown polynomial, and are told that all the coefficients are integers and are all within $min \le a\_k \le max$. Also, you have access to an oracle who will evaluate p(q), the unknown polynomial, and compare it to your guess $g\_q$, where q is the number of previous guesses you have made, and determine if your guess was less, greater than, or exactly equal to the unknown polynomial.

What is the optimal method of choosing guesses, given previous results, in order to make a correct guess as soon as possible in the worst case?

If the degree is d and the coefficients are bounded by [min, max] then it would seem the best possible method would require slightly less than $ \frac {d \log (max - min + 1)}{\log 2}$ by binary search. Its slightly less because with an answer of > from the oracle, you exclude both the values less than and those equal to the guess, which could be more than 50% of possibilities.

If the median of the evaluated values at q of all of the remaining possible polynomials can be found, than guessing that value would be guaranteed to eliminate at least half of the possibilities. But is there any efficient way to find the median of a function of a set of polynomials that are only identified by inequalities?

For the first guess, q is zero and therefore all but the constant term of the polynomial are irrelevant. It makes sense then to make g(0) to be $\frac {min + max}{2}$. But after that, the best way of finding the median quickly seems elusive.

As an example, make min = -100, max = 100 and d = 1. $\frac {-100 + 100}{2}$ = 0, so g(0) should be 0. If the oracle returns > then we know $0 < a\_0 \le 100$ or $1 \le a\_0 \le 100$ since we are dealing with integer coefficients.

An ideal method would include an efficient way to find the median and characterize the set of possibilities given the previous answers from the oracle. But medians can be hard to calculate so an efficient method to calculate the mean of p(q) for the set of possibilities would be close enough if an efficient method doesn't exist for medians.

Answer 1

Just determine the coefficient at the highest power first by plugging in huge numbers and doing binary search (comparing to what you'd get for the half-integer coefficients). Once you know it, you can easily figure out the coefficient at the next power in the same way and so on.

Now, if you also have a bound on $q$ you can plug in, it becomes interesting.

Oops, sorry for misunderstanding.

OK, you can easily do $Cd^M\log N$ then. The trick is that no matter how you split the d-dimensional simplex of volume 1 by a hyperplane through its center and no matter which piece you'll take, you'll be able to find a simplex of volume $1-d^{-m}$ conatining this piece where $m$ is some fixed number, which I will need some time to compute precisely (my educated guess would be m=4). Now just use this fact to obtain a simplex of either volume less than $N^{-2d}$ or with one vertex outside the ball of radius $N^{3d}$ containing the set of remaining polynomials after just $O(d^M\log N)$ steps. In both cases, you'll be able to find a linear dependence between the coefficients that is precise up to $N^{-2}$, which means that you can eliminate one coefficient from the polynomial entirely (the $d$-th power of the variable is still well below $N$, so the precision is enough to distinguish the integer values and each exactly attained equality which will not allow you to tell for sure which half you are in gives you food for interpolation).

Sorry if it is too sketchy. I'll try to edit it into something more reasonable later unless somebody gives a better solution.