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 ?

Improve this question
$\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$
    – David E Speyer
    Commented 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
    Commented Jul 22, 2013 at 18:53
  • $\begingroup$ Counting nonzero terms sounds easier to me, not that I was able to do either. $\endgroup$
    – David E Speyer
    Commented 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$
    – Gerry Myerson
    Commented Jul 23, 2013 at 1:11

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – David E Speyer
    Commented 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
    Commented Jul 22, 2013 at 18:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .