8
$\begingroup$

This is a crosspost of https://math.stackexchange.com/questions/446470/combinatorics-of-resultants which received no answer. [EDIT: I deleted the initial copy of the question on MathSE].

Let $f(z)=\sum_{i=0}^{D_f}x_iz^i$ and $g(z)=\sum_{i=0}^{D_g}y_iz^i$ be two polynomials. I would like to know the number of monomials (in the variables $x_i$ and $y_i$) in the resultant in $z$ of $f$ and $g$. Equivalently, this is the number of monomials in the determinant of the Sylvester matrix: $$ \left( \begin{array}{ccccccccc} x_0 & x_1 & x_2 & \cdots & x_{D_f} & 0 & 0 & \cdots & 0\\ 0 & x_0 & x_1 & \cdots & x_{D_f-1} & x_{D_f}& 0 & \cdots & 0 \\ \vdots & \ddots & \ddots &\cdots &\ddots &\ddots & \ddots &\cdots &\vdots\\ y_0 & y_1 & y_2 & \cdots & y_{D_g} & 0 & 0 & \cdots & 0\\ 0 & y_0 & y_1 & \cdots & y_{D_g-1} & y_{D_g}& 0 & \cdots & 0 \\ \vdots & \ddots & \ddots &\cdots &\ddots &\ddots & \ddots &\cdots &\vdots\\ \end{array} \right). $$

I think there is a classical answer to this problem (I even seem to recall having seen it once) but I can't find a pointer to it. Can anyone point me either to a closed form or even better a tight and simple upper bound on this number of monomials ?

$\endgroup$
4
  • 1
    $\begingroup$ I played around a little in Sloane's encyclopedia. For $\deg f=1$, the answer is $\deg g+1$. For $\deg f =2$, the answer appears to be oeis.org/A002623. No luck for the general question. Some sequences which look good at first but then fail are A227125, A202560 and A156353; the latter two were attempts at the variant problem of counting the nonzero terms in the determinant, before combining equal terms. $\endgroup$ Jul 22, 2013 at 16:57
  • $\begingroup$ @DavidSpeyer: Thanks for your suggestion. Seeing your attempts, do you think it would be easier to count the nonzero terms of the determinant or maybe the $L_1$ norm of the vector of coefficients ? $\endgroup$
    – minar
    Jul 22, 2013 at 18:53
  • $\begingroup$ Counting nonzero terms sounds easier to me, not that I was able to do either. $\endgroup$ Jul 22, 2013 at 18:54
  • 2
    $\begingroup$ The infinity norm of the vector of coefficients, otherwise known as the height of the polynomial, is discussed in Carlos D'Andrea and Kevin G. Hare, On the height of the Sylvester resultant, Experimental Mathematics, 13:3 (2004) 331-341. $\endgroup$ Jul 23, 2013 at 1:11

1 Answer 1

5
$\begingroup$

Yes, this (like everything else under the Sun) was studied, but not a lot. The reference is: M. Kalkbrener, An upper bound on the number of monomials in the Sylvester resultant.

$\endgroup$
2
  • $\begingroup$ Seems a little off target: This answers the question for $f$ and $g$ sparse (with $r$ and $s$ nonzero terms respectively). The closest I can do for the question where all coefficients are nonzero is Gelfand, Kapranov, Zelevinsky "Newton polytopes of the classical resultant and discrimant", but they don't really answer the question either. $\endgroup$ Jul 22, 2013 at 18:06
  • $\begingroup$ Thanks for the pointer. As @David Speyer noted, it addresses the sparse case and it is not clear whether the bound will be tight for the dense case ($r=m+1$ and $s=n+1$). At least, it gives a starting point. $\endgroup$
    – minar
    Jul 22, 2013 at 18:51

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.