Finding zeros of an integer polynomial

[Roy Smith]

Given a set of coefficients, Ci, I want to find a set of Ni, such that

sum from i = 0 to Imax ( Ci * Ni ) = 0

where all the Ci's are integers and all the Ni's are non-negative
integers. Imax may be as large as 50, which kind of implies that
solutions which are O(Imax ^ 2), or even O(Imax ^ 3) are fine, but
probably not anything bigger than that.

A possible variation on this is that the Ni's may only be chosen from
the set {0, 1}, but that's a different problem.

Yeah, I know this sounds like a homework problem (and, in a sense, it
is), but I'm not looking for people to solve it for me. I suspect this
kind of problem is well-known, and if you could give me some hints about
what it's called and where I could go to read about solutions, that
would be cool.

It's obvious that some sets of Ci's won't allow any solutions. As a
trivial case, it's clear that if all the Ci's are the same sign, no
solutions are possible. For the particular case I'm interested in,
however, it can be taken as a given that there are both positive and
negative Ci's.

For the variation where Ni is chosen from {0, 1}, it's equally trivial
to come up with sets of Ci that have opposite signs but no solution:
{10, -5}, for example.

For the more general case (Ni are non-negative integers), it seems like
there must be some solution. Find two Ci's with opposite signs and set
Ni1 = Ci2 and Ni2 = Ci1.

But, that's as far as I can get. How do I go about finding a more
general solution?

[James Waldby]

On Sun, 17 Jun 2012 10:59:06 -0400, Roy Smith wrote:

> Given a set of coefficients, Ci, I want to find a set of Ni, such that
>
> sum from i = 0 to Imax ( Ci * Ni ) = 0
>
> where all the Ci's are integers and all the Ni's are non-negative
> integers. Imax may be as large as 50, which kind of implies that
> solutions which are O(Imax ^ 2), or even O(Imax ^ 3) are fine, but
> probably not anything bigger than that.
>
> A possible variation on this is that the Ni's may only be chosen from
> the set {0, 1}, but that's a different problem.
>

[snip re "some sets of Ci's won't allow any solutions"

> however, it can be taken as a given that there are both positive and
> negative Ci's.

[snip re Ni in {0,1} case]

> For the more general case (Ni are non-negative integers), it seems like
> there must be some solution. Find two Ci's with opposite signs and set
> Ni1 = Ci2 and Ni2 = Ci1.
>
> But, that's as far as I can get. How do I go about finding a more
> general solution?

The simplest general solution is Ni = 0 for all i. For a less-trivial
solution, suppose Cj > 0 > Ck and let Nj = -Ck, Nk = Cj, and other Ni=0.
The problem might be more interesting if you require two things:
(1) all Ni>0, (2) minimize sum(Ni) [or some other measure].
With only requirement (1) added, there are several trivial ways of
extending the previously-mentioned solution, but depending on the
measure, requirement (2) probably can arbitrarily increase difficulty
of solution.

--
jiw