Determine if a polynomial has negative coefficients?

Question

Given a polynomial with integer coefficients, is there an elegant way to determine if the polynomial has negative coefficients with minimum number of queries about the value of the polynomial at certain values. The value of the derivative of the polynomial at certain values can also be queried.

The number of queries should at least be less than degree of the polynomial + 1 which can determine the complete polynomial.

Answer 1

1. Query if for any $x>0$ that $f(x)\le0$ and $f(x+\alpha)<f(x)$ for any $\alpha>0$
2. Query if for any $x<0$ that $f(x)\ge0$ and $f(x+\alpha)>f(x)$ for any $\alpha>0$

A few rare cases may slip through but in general this seems pretty adequate

Answer 2

NB: This is not a solution to the problem as posed; I didn't notice the word "integer" when I wrote it. I'm leaving it just for posterity.]

Nice question. You haven't said whether the the query-$x$-values are chosen a priori, or whether the resulting $y$-value from one $x$-query can be used to decide which $x$ to use next.

[The following is a "solution" to the less-interesting problem when the coefficients are real, rather than being constrained to integers; for the integer problem, Marcus M.'s solution gives a nice answer.]

Assuming the "pick all $x$ values a priori," the answer for the basic question is "no." Why?

Suppose our $x$-values are $1, \ldots, n$. Let $$ p(x) = C (x-1) (x-2) \cdots (x-n) $$ Then the corresponding $y$-values are all zero. But you can't tell anything about the coefficients, for if $C$ is positive, then the coefficient of $x^n$ is positive, while if $C$ is negative, that coefficient is negative. So the $y$-values alone don't give the information you need in this case.

Let me be even more explicit. Let's look at the case where the degree $n$ is $1$. So $p(x) = Ax + B$. You get to evaluate $p$ at exactly one $x$-value. Let's say you pick $x = 1$, and you get the result $A + B$, and let's suppose that it's $3$. Then the following are all possibilities: $$ A = 3, B = 0 \\ A = 0, B = 3 \\ A = -10, B = 13 \\ \ldots $$

Answer 3

This is perhaps a bad but technically correct answer: Since $\pi$ is transcendental, the value $f(\pi)$ completely determines the polynomial $f$ provided $f$ has integer coefficients. In particular, this tells you if there are any negative coefficients. For the case of choosing $x$ values before-hand and where your coefficients are real numbers---not integers, like you state---John Hughes' answer explains why that's impossible.

---

EDIT: A more detailed explanation, to help explain it. Here's an underlying fact

The function $F:\mathbb{Z}[x] \to \mathbb{R}$ defined via $f \mapsto f(\pi)$ is injective. Therefore, if you know $f(\pi)$ then you can recover the coefficients of $f$ by applying $F^{-1}$.

To see that $F$ is injective, suppose that $F(f_1) = F(f_2)$. Then $f_1(\pi) = f_2(\pi)$, i.e. $(f_1 - f_2)(\pi) = 0$. However, since $(f_1 - f_2) \in \mathbb{Z}[x]$, we must have that $f_1 - f_2 = 0$ since $\pi$ is transcendental over $\mathbb{Z}$. This proves that $F$ is injective.

Since every injective function is invertible on its image, this means that given the value $f(\pi)$, the coefficients of $f$ can be recovered by inverting $F^{-1}$. Of course, coming up with an algorithm to actually compute $F^{-1}$ is probably impossible in practice.

Answer 4

There is no necessary and sufficient test, unfortunately. If you're lucky with your inputs, and the polynomial indeed has negative coefficients, then you can determine this with fewer inputs (obvious example: if you plug in even one positive input and the result is negative).

Let's see why no such test exists. Each input provides us with a linear equation. If we're looking for our polynomial $$f(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n,$$ then knowing, say $f(2) = 4$ tells us that $$4 = a_0 + 2a_1 + 4a_2 + \ldots + 2^n a_n.$$ If we get $n+1$ of these equations, we get a system of $n + 1$ linear equations in $n + 1$ variables, which (as it turns out) has a unique solution, telling us the polynomial.

Each equation, geometrically, represents a "hyperplane": an $n$-dimensional space of solutions, in $\mathbb{R}^{n+1}$. As we collect more equations, we intersect these hyperplanes, stripping away dimensions (in $3$ dimensions, say, two of these planes will intersect in a line, and a third will intersect at a unique point). If we take $n + 1$ equations, this yields a point, the coordinates of which are our polynomial.

So, if we take fewer equations, we're left with a non-trivial affine space of solutions, by which I mean a line, a plane, or a higher-dimensional equivalent.

Now, if we want to guarantee a negative solution, what we're aiming for is a solution set that misses the positive orthant of the $\mathbb{R}^{n+1}$, by which I mean, the convex cone of points which have only positive coordinates. We may get lucky, and our solution set misses this set completely.

But, we may never get the situation where our non-trivial affine solution set lies entirely within this orthant! We can never contain even a line in there, as going off in one direction will always yield a solution with a negative coefficient. That is, as I said, we may be able to prove the existence of a negative coefficient if we are lucky enough, but we may never prove that the coefficients are all positive unless we have $n + 1$ equations.

Answer 5

If we know the height $h(f)$ of the polynomial $$f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$$ i.e., $$-b \le a_i \le b$$ where $b = h(f)$, then a single evaluation of $f(2b + 1)$ is sufficient to determine the coefficients $a_i$ uniquely.

See

Bettina Richmond (2010) On a Perplexing Polynomial Puzzle, The College Mathematics Journal, 41:5, 400-403, DOI: 10.4169/074683410X522017

A preprepint is also available here.