[math-fun] Kimberling's polynomial problem

9 Jun 2012

      (The GF of the elementwise product of two (constant coeff) linear recurrences.)

ClarkK>It appears that a denominator may be a polynomial whose roots
are the>reciprocal-products 1/(r(i)*s(j)), where r(i) ranges through
all the>roots of q(x) and s(j) ranges through all the roots of
v(x).>Clark Kimberling

WDS>--This polynomial A(x) is expressible in terms of the original polynomials
q(x) and v(x) by the use of "resultant" -- you can evaluate using
determinants without computing
any roots, just do rational operations.

Specifically, the polynomial B(x) whose roots are the products
r(i)*s(j) should be

B(x) = Resultant_y [q(y), y^degree(v) * v(x/y)]

and then A(x) is the "reverse" of B(x) to reciprocate its roots,

A(x) = B(1/x) * x^degree(B).

The "numerator" polynomial Kimberling also
wanted could then be obtained by simply solving for
it by given the known values of the first degree # of outputs,
i.e. series coefficients, of the generating function.
This is just a polynomial multiplication.
-------
Now suppose NONconstant coeffs, but we'll settle for the recurrence relation
of the elementwise product of two sequences, given their separate recurrences.
E.g., the
HolonomicFunctions package by Christoph Koutschan, RISC-Linz, Version
1.4.2 (08.02.2011)
gives the 2nd order recurrence for incomplete Gamma:

In[71]:= Annihilator[Gamma[a, z], S[a]]

Out[71]= {Subscript[S, a]^2 + (-1 - a - z)*Subscript[S, a] + a*z}

(S is the shift operator).  Now how the heck does it get
In[72]:= Annihilator[Gamma[a, z]^2, S[a]]

Out[72]= {(1 + a + z)*
   Subscript[S, a]^3 + (-4 - 8*a - 5*a^2 - a^3 - 6*z - 7*a*z -
     2*a^2*z - 4*z^2 - 2*a*z^2 - z^3)*Subscript[S, a]^2 +
     (2*z + 7*a*z + 9*a^2*z + 5*a^3*z + a^4*z + 4*z^2 + 10*a*z^2 +
     8*a^2*z^2 +
          2*a^3*z^2 + 3*z^3 + 5*a*z^3 + 2*a^2*z^3 + z^4 + a*z^4)*
   Subscript[S, a] +
     (-2*a^2*z^3 - 3*a^3*z^3 - a^4*z^3 - a^2*z^4 - a^3*z^4)}

?  Worse:
In[73]:= Annihilator[Gamma[a, z]*Gamma[a, y], S[a]]

Out[73]= {(2 + 3*a + a^2 - y*z)*Subscript[S, a]^4 +
     (-18 - 39*a - 29*a^2 - 9*a^3 - a^4 - 6*y - 11*a*y - 6*a^2*y -
     a^3*y - 6*z -
          11*a*z - 6*a^2*z - a^3*z + 3*y*z + a*y*z + 3*y^2*z +
     a*y^2*z + 3*y*z^2 +
          a*y*z^2 + y^2*z^2)*Subscript[S, a]^3 +
     (24*y + 68*a*y + 74*a^2*y + 39*a^3*y + 10*a^4*y + a^5*y + 24*z +
     68*a*z +
          74*a^2*z + 39*a^3*z + 10*a^4*z + a^5*z + 36*y*z +
     72*a*y*z + 53*a^2*y*z +
          17*a^3*y*z + 2*a^4*y*z - 10*y^2*z^2 - 9*a*y^2*z^2 -
     2*a^2*y^2*z^2 - 2*y^3*z^2 -
          a*y^3*z^2 - 2*y^2*z^3 - a*y^2*z^3)*Subscript[S, a]^2 +
     (-12*y*z - 52*a*y*z - 91*a^2*y*z - 82*a^3*y*z - 40*a^4*y*z -
     10*a^5*y*z - a^6*y*z -
          12*y^2*z - 40*a*y^2*z - 51*a^2*y^2*z - 31*a^3*y^2*z -
     9*a^4*y^2*z - a^5*y^2*z -
          12*y*z^2 - 40*a*y*z^2 - 51*a^2*y*z^2 - 31*a^3*y*z^2 -
     9*a^4*y*z^2 - a^5*y*z^2 -
          6*y^2*z^2 - 11*a*y^2*z^2 - 6*a^2*y^2*z^2 - a^3*y^2*z^2 +
     2*y^3*z^2 +
          5*a*y^3*z^2 + 4*a^2*y^3*z^2 + a^3*y^3*z^2 + 2*y^2*z^3 +
     5*a*y^2*z^3 +
          4*a^2*y^2*z^3 + a^3*y^2*z^3 + 2*y^3*z^3 + 3*a*y^3*z^3 +
     a^2*y^3*z^3)*
       Subscript[S, a] + (12*a^2*y^2*z^2 + 28*a^3*y^2*z^2 +
    23*a^4*y^2*z^2 +
        8*a^5*y^2*z^2 + a^6*y^2*z^2 - 2*a^2*y^3*z^3 - 3*a^3*y^3*z^3 -
    a^4*y^3*z^3)}

Worse:
In[74]:= Annihilator[Gamma[a, z]*Gamma[a + b, z], S[a]]

Out[74]= {(1 + 2*a + a^2 + b + a*b - z - z^2)*Subscript[S, a]^4 +
     (-9 - 24*a - 22*a^2 - 8*a^3 - a^4 - 12*b - 22*a*b - 12*a^2*b -
     2*a^3*b - 3*b^2 -
          4*a*b^2 - a^2*b^2 + 4*z - 6*a*z - 8*a^2*z - 2*a^3*z -
     3*b*z - 8*a*b*z -
          3*a^2*b*z - b^2*z - a*b^2*z + 10*z^2 + 4*a*z^2 + 2*b*z^2 +
     6*z^3 + 2*a*z^3 +
          b*z^3 + z^4)*
   Subscript[S, a]^3 + (20*z + 68*a*z + 89*a^2*z + 56*a^3*z +
          17*a^4*z + 2*a^5*z + 34*b*z + 89*a*b*z + 84*a^2*b*z +
     34*a^3*b*z + 5*a^4*b*z +
          16*b^2*z + 32*a*b^2*z + 20*a^2*b^2*z + 4*a^3*b^2*z +
     2*b^3*z + 3*a*b^3*z +
          a^2*b^3*z + 16*a*z^2 + 24*a^2*z^2 + 12*a^3*z^2 +
     2*a^4*z^2 + 8*b*z^2 +
          24*a*b*z^2 + 18*a^2*b*z^2 + 4*a^3*b*z^2 + 4*b^2*z^2 +
     6*a*b^2*z^2 +
          2*a^2*b^2*z^2 - 16*z^3 - 16*a*z^3 - 4*a^2*z^3 - 8*b*z^3 -
     4*a*b*z^3 - 11*z^4 -
          10*a*z^4 - 2*a^2*z^4 - 5*b*z^4 - 2*a*b*z^4 - 3*z^5 -
     2*a*z^5 - b*z^5)*
       Subscript[S, a]^2 + (-4*z^2 - 20*a*z^2 - 41*a^2*z^2 -
     44*a^3*z^2 - 26*a^4*z^2 -
          8*a^5*z^2 - a^6*z^2 - 10*b*z^2 - 41*a*b*z^2 -
     66*a^2*b*z^2 - 52*a^3*b*z^2 -
          20*a^4*b*z^2 - 3*a^5*b*z^2 - 8*b^2*z^2 - 26*a*b^2*z^2 -
     31*a^2*b^2*z^2 -
          16*a^3*b^2*z^2 - 3*a^4*b^2*z^2 - 2*b^3*z^2 - 5*a*b^3*z^2 -
     4*a^2*b^3*z^2 -
          a^3*b^3*z^2 - 8*z^3 - 32*a*z^3 - 50*a^2*z^3 - 38*a^3*z^3 -
     14*a^4*z^3 -
          2*a^5*z^3 - 16*b*z^3 - 50*a*b*z^3 - 57*a^2*b*z^3 -
     28*a^3*b*z^3 - 5*a^4*b*z^3 -
          10*b^2*z^3 - 23*a*b^2*z^3 - 17*a^2*b^2*z^3 -
     4*a^3*b^2*z^3 - 2*b^3*z^3 -
          3*a*b^3*z^3 - a^2*b^3*z^3 + 3*z^4 + 8*a*z^4 + 7*a^2*z^4 +
     2*a^3*z^4 + 4*b*z^4 +
          7*a*b*z^4 + 3*a^2*b*z^4 + b^2*z^4 + a*b^2*z^4 + 4*z^5 +
     10*a*z^5 + 8*a^2*z^5 +
          2*a^3*z^5 + 5*b*z^5 + 8*a*b*z^5 + 3*a^2*b*z^5 + b^2*z^5 +
     a*b^2*z^5 + z^6 +
          2*a*z^6 + a^2*z^6 + b*z^6 + a*b*z^6)*Subscript[S, a] +
     (4*a^2*z^4 + 12*a^3*z^4 + 13*a^4*z^4 + 6*a^5*z^4 + a^6*z^4 +
    4*a*b*z^4 +
        18*a^2*b*z^4 + 26*a^3*b*z^4 + 15*a^4*b*z^4 + 3*a^5*b*z^4 +
    6*a*b^2*z^4 +
        15*a^2*b^2*z^4 + 12*a^3*b^2*z^4 + 3*a^4*b^2*z^4 +
    2*a*b^3*z^4 + 3*a^2*b^3*z^4 +
        a^3*b^3*z^4 - a^2*z^5 - 2*a^3*z^5 - a^4*z^5 - a*b*z^5 -
    3*a^2*b*z^5 -
        2*a^3*b*z^5 - a*b^2*z^5 - a^2*b^2*z^5 - a^2*z^6 - 2*a^3*z^6 -
    a^4*z^6 - a*b*z^6 -
        3*a^2*b*z^6 - 2*a^3*b*z^6 - a*b^2*z^6 - a^2*b^2*z^6)}

In[75]:= Annihilator[Gamma[a, z]*Gamma[a + b, y], S[a]]
You don't want to know!
--rwg

[math-fun] Kimberling's polynomial problem

Bill Gosper