Reconstructing a polynomial from resultants

Question

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.

Answer 1

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.