Reconstructing a polynomial from resultants I am trying to compute a monic polynomial $f(x)$ with integer coefficients and known degree $d$.  I am given $n$ pairwise coprime polynomials $g_1(x),\ldots,g_n(x)$, also with integer coefficients, each monic of degree at most $e < d$.  I am also given the values of the $n$ resultants $\mathrm{Res}_x(f(x),g_i(x))$ for $i = 1,\ldots,n$.

The question is: find an algorithm that recovers $f(x)$ from these inputs, for some value of $n$ (depending on $d$ and $e$).

If I take $n = (d+1)$ choose $e$, then an algorithm is as follows: write the coefficients of $f$ as indeterminates, and write out each resultant in terms of these variables.  Then I get $n$ polynomial equations in $d$ variables of degree at most $e$.  I linearize the system, and if $n$ is as above then I have enough equations to find a solution.
I suspect there is some algorithm involving Gröbner bases, but I doubt it is any faster than the above.
Ideally I would like an algorithm that is polynomial-time in $d$ and $e$.  (In my application I have $e = O(\sqrt{d})$.)  I have no idea if such an algorithm is reasonable to expect.  Even something better than $O(d^e)$ would be nice.

[EDIT] What gives me hope are these two papers:
C. Hillar, Cyclic Resultants, Journal of Symbolic Computation, 39 (2005), 653-669.
C. Hillar and L. Levine, Polynomial recurrences and cyclic resultants, Proceedings of the American Mathematical Society, 135 (2007), 1607-1618.
They show that if $g_i(x) = x^i - 1$ then there is an algorithm.  The algorithm requires exponentially many resultants, but they conjecture that it is possible with polynomially many.  I was hoping that if we allow a larger set of $g_i$ but strongly constrain the degrees than we can still recover something.

 A: I really like this question, but unfortunately I think that it doesn't have any algorithm in the general case, as I'll explain below.  Thus, to reconstruct your desired $f$, either you need to use $g_m$'s that are special, or assume that $f$ has some special structure (or both).
My claim goes against your stated algorithm (which is a shame, as it is a nice idea), so I'll first describe why I don't think that the algorithm works.  I thought I had a formal proof that the algorithm was faulty (aside from the below counter-example), but it didn't go through.  The problems I see are two fold:


*

*Even if one solves the system, I feel like it may not always be possible to get back to the actual coefficients of $f$ (I wouldn't be surprised if it was possible, though).

*You claim that once we have enough equations then we should be able to solve the system of equations, but I don't currently see a proof that these equations are linearly independent (I feel like this is really where the algorithm breaks down).
So now I'll give my counter-example: in a nutshell I'll construct an infinity family of monic, integer, coprime polynomials $g_m$ such that there are (at least) two monic integer polynomials $f_{-1}$ and $f_1$ such that $Res_x(f_1(x),g_m(x))=Res_x(f_{-1}(x),g_m(x))$ for all $m$. Thus, the resultants do not contain enough information to reconstruct $f$, no matter how long the algorithm takes.
Now for the details.  First I'll assume that both $d$ and $e$ are even (I don't feel like this is a big restriction, but who knows?) [but I don't actually need $d>e$].  Define $g_m(x):=x^e-m^e$, for $m\in\{2,3,\ldots\}$. Clearly they are monic, integer, and coprime. Define $f_1=(x-1)^d$ and $f_{-1}=(x+1)^d$.  Recall the formula for the resultant of monic polynomials (over the closure of whatever field we are working over):

$Res_x(P,Q)=\Pi_{(a,b):P(a)=Q(b)=0}(a-b)$

where the product is over roots, taken with multiplicity.  So then

$Res_x(f_1,g_m)=\Pi_{j=1}^e (1-m\omega^j)^d$

where $\omega$ is a primitive $e$-root of unity (again, over the closure of the field).  But as $d$ is even, this means that $-1$ is a $d$-root of unity so,

$=\Pi_{j=1}^e (1-m\omega^j)^d=\Pi_{j=1}^e (-(1-m\omega^j))^d=\Pi_{j=1}^e (-1+m\omega^j)^d$

and using $e$ is even, and thus that $-\omega$ is an $e$-th root iff $\omega$ is, we see that via reindexing

$=\Pi_{j=1}^e (-1-m\omega^j)^d=Res_x(f_{-1},g_m)$

so I've established the equality of the resultants, for any $m$.  So clearly any algorithm that attempts reconstruction will fail, as it cannot distinguish between $f_{-1}$ and $f_{1}$.
Clearly, this result relies crucially on the fact that both $e$ and $d$ are even, but otherwise has no restriction.  I feel like something could be done for cases when a small prime divides both $d$ and $e$, but at the moment this result seems sufficient for your purposes.
I suppose in a sense this counter-example "shows" that the "linearized" system you proposed cannot be invertible in general.  It could be an interesting to ask for conditions for when the $g_m$ do form such an invertible system. However, as you say above, your $g_m$ are given you, so I'm not sure of a quick way to avoid this counter-example. 
I hope that something is still recoverable for your application.
