4

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.

Keerthana S
  • 49
  • 3
  • If there are no negative coefficients, then you can't know this without sampling $d+1$ values. But if there are negative coefficients, you could know this earlier, and it might be possible to plan the queries such as to find out early. So I think you need to be more specific about what kind of analysis you want -- worst case, best case, average? And if average, for which distribution? – joriki Jul 25 '18 at 01:04
  • 1
    What do you mean by "Given a polynomial"? How is it "given" to you? That determines what you are allowed to do with it. – Somos Jul 25 '18 at 02:25
  • @Somos the polynomial and its derivatives can be evaluated at any value. – Keerthana S Jul 25 '18 at 04:17
  • So you are given a polynomial function. Are you given its degree as well? Are you given any bound on the coefficients? – Somos Jul 25 '18 at 04:30
  • The coefficients are integers, no bound. – Keerthana S Jul 25 '18 at 04:32

5 Answers5

3

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 $$

John Hughes
  • 93,729
  • As I mentioned in the question, the queries can be chosen cleverly to have an elegant approach to guess if the polynomial has negative coefficients. – Keerthana S Jul 25 '18 at 01:07
  • When you only get to choose one point, for linear polynomials, it's pretty tough to be clever (except as in Marcus M.'s nice answer). [I confess that I didn't notice the critical 'integer coefficients" part of your question, though.] – John Hughes Jul 25 '18 at 01:12
2

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.

Marcus M
  • 11,229
  • Nice! (Although there's some proving to do to establish "completely determines...") :) – John Hughes Jul 25 '18 at 01:10
  • I don't understand this whatsoever. Suppose you find $f(\pi) = 7.8843$. What does this tell you about the signs of any terms (except that there must be at least one positive term)? – David G. Stork Jul 25 '18 at 01:12
  • @DavidG.Stork the point is, for each $f_1$ and $f_2$ with integer coefficients, $f_1(\pi) = f_2(\pi)$ if and only if the two polynomials are equal; to see why this is true, note that $\pi$ is killed by the polynomial $f_1 - f_2$, but since $\pi$ is transcendental, that means that $f_1 - f_2 = 0$. This means that the value of $f(\pi)$ in fact is enough information to deduce $f$, and therefore find the signs of its coefficients. – Marcus M Jul 25 '18 at 01:15
  • So what should be your $f_2$? And if you find $f_1(\pi) \neq f_2(\pi)$ (for whatever $f_2$ you happen to choose) what will that tell you about the signs of the $f_1$ polynomial (our target)? Just that at least one of them is different. So what? – David G. Stork Jul 25 '18 at 01:21
  • @DavidG.Stork, I think you're misunderstanding quite a bit about what I'm arguing; I edited in an explanation in more detail in the post. The point is that if you know that $f$ has integer coefficients, then $f(\pi)$ tells you exactly what $f$ is. – Marcus M Jul 25 '18 at 01:28
  • 1
    Of course one might ask what does it mean to "know" the value $f(\pi)$. If you know it as an explicit symbolic expression (a linear combination of powers of $\pi$), you can just scan the coefficients. If you know it in the sense that you have a black box to produce arbitrarily accurate rational approximations (e.g. perhaps decimal expansions to arbitrary precision), you can never be sure that the answer is "no". – Robert Israel Jul 25 '18 at 01:57
  • 2
    @DavidG.Stork: If you find that $f(\pi) = 7.8843$, then by multiplying $f$ by $10,000$, you find that $10000 f(\pi) - 78843 = 0$, i.e., you've shows that $\pi$ is the solution to a polynomial with integer coefficients, hence it's not transcendental. So your hypothetical situation just isn't going to happen. – John Hughes Jul 25 '18 at 02:15
1

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.

Theo Bendit
  • 50,900
  • This is really the same as my answer, and you appear to have not used the important clue that the coefficients are integers (just as I did). – John Hughes Jul 25 '18 at 02:12
0
  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

Rhys Hughes
  • 12,842
  • I don't see why this should work and should require the minimal number of samples, as the OP requests. Please explain. – David G. Stork Jul 25 '18 at 01:02
  • We Hugheses seem to disagree; what result does your test give on the example I provide below? (BTW, you can replace the numbers $1, \ldots, n$ with any other set of numbers, including ones that are negative.) – John Hughes Jul 25 '18 at 01:03
  • Useful fact: You can tell the sign of the highest-order term in the polynomial by querying (finding $y$) for an extremely large $x$ (ideally $x \to \infty$), which immediately gives the sign of that term. – David G. Stork Jul 25 '18 at 01:05
  • 1
    It's tough to know what "extremely large" is, as it needs to be larger than the largest root (assuming the polynomial's factorable into linear terms). For any $x_0$ you pick, I can find a polynomial (like $(x - (|x_0| + 1))^n$) where your test will fail. – John Hughes Jul 25 '18 at 01:07
0

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.

vvg
  • 3,311