9
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ What do you mean by "I linearize the system"? $\endgroup$ Jul 29, 2010 at 21:51
  • 1
    $\begingroup$ Given a polynomial system of equations, I define a linear system where each distinct monomial in the polynomial system corresponds to a unique variable in the linear system. $\endgroup$ Jul 29, 2010 at 22:19
  • $\begingroup$ The resultant of $f$ and $g$ is the product of $g(a)$ as $a$ runs through the roots of $f$, so it's a polynomial with known integer coefficients in the $d$ roots of $f$. It seems to me that, in principle, if $n=d$ then you have enough equations to find the roots (and therefore the coefficients) of $f$. How this works out in practice, I don't know. $\endgroup$ Jul 29, 2010 at 23:53
  • $\begingroup$ Here's another idea that probably doesn't work. If $p$ is a prime dividing the resultant of $f$ and $g$ then the two polynomials have a common factor over the integers modulo $p$. There are good algorithms for factoring the given $g$ modulo $p$, so you get some information about the factorization of $f$ modulo $p$. If you have enough pieces of information about the factorization of $f$ modulo various primes, maybe the Chinese Remainder Theorem recovers the form of $f$. One weakness of this method (aside from all the handwaving) is it seems to go nowhere if all the resultants are 1. $\endgroup$ Jul 29, 2010 at 23:59
  • $\begingroup$ Do you get to pick the $g_i$ or must they be arbitrary (but coprime)? $\endgroup$
    – miforbes
    Jul 30, 2010 at 18:08

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Perhaps what one can recover is an algorithm for reducing to a finite number of possibilities for $f$, a number bounded by some simple function of $n$ and the degrees. $\endgroup$ Aug 1, 2010 at 0:13
  • $\begingroup$ That it is an interesting possibility, but I feel like the above counter-example should be generalizable to a situation where the number of finite possibilities is rather large. But even in this case, I'm not sure how one would find the finite number of possibilities, as clearly any linear system as either a unique solution or an infinite number (over an infinite field). Also, I'm not sure if this would be sufficient for the application at hand. $\endgroup$
    – miforbes
    Aug 1, 2010 at 10:38
  • 1
    $\begingroup$ @miforbes, I think your construction is very powerful. Let $f$ be any polynomial, let $g(x)=x^2-m$ for any non-zero integer $m$, then the resultant of $f(x)$ and $g$ is $f(\sqrt m)f(-\sqrt m)$, which is also the resultant of $f(-x)$ and $g$, so here we have an infinity of $g$ of degree 2 that can't distinguish any $f(x)$ from $f(-x)$ (which are different, provided $f$ is not even). $\endgroup$ Aug 1, 2010 at 12:57
  • $\begingroup$ @Gerry: Indeed; I'll have to admit I was somewhat surprised by the result. That is, I was expecting successful recovery (albeit with a strong lower bound on the number of resultants needed) upon first reading the question. $\endgroup$
    – miforbes
    Aug 1, 2010 at 17:59
  • $\begingroup$ That result is discouraging. I've edited the question to include a family of $g_i$ for which it is possible. $\endgroup$ Aug 3, 2010 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.