Assume we have sequence of polynomials : $P_i(q)$ - each term is polynomial in $q$. (With integer coefficients, but hopefully it is not important).
We expect that there exists recurrence relation: $P_{n}(q) = \sum_{i=1...d} C_i(qˆn,q) P_{n-i}(q) $
Question: Is there any algorithm (or ready to use package) to find these $C_i$ for given input sequence of polynomials?
Trivial example can be : $$P_0(q) = 1 , P_1(q) = q , P_2(q) = qˆ2, ... $$ then recurrence $$P_n(q) = q P_{n-1}(q)$$
Non-trivial example can be found here: https://mathoverflow.net/a/469903/10446
Some more potential applications:
Count Manin matrices: Number of $F_p$-matrices ac=ca, bd = db , ad - da = cb - bc is polynomial in p ? ("Manin matrix variety" - normal ? Cohen–Macaulay ? )
Count polynomial nilpotent matrices: Nilpotent polynomial matrices over $F_q$ - polynomial count variety ? ( Nilpotent cone for Hitchin-Gaudin like integrable system)
Count commuting matrices with block structures: Count N-tuples of commuting matrices over $F_q$ is given by polynomials with pattern $\sum q^{A_i(N)} P_{i}(q) $, where $P_i$ - do not depend on $N$?
