3
$\begingroup$

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 a kind of: $P_{n}(q) = \sum_{i=1...d} C_i(q^n,q) P_{n-i}(q) $,

but might be a bit more tricky - there can be a term in front of $P_{n}(q)$, i.e.: $C_0(q^n,q)P_{n}(q) = \sum_{i=1...d} C_i(q^n,q) P_{n-i}(q) $ . That small detail might complicate application of some methods, because basically what we are asking - solving some system of linear equations - which have trivial unwanted solution - all zeros. To avoid that we need to normalize the relation - that is trivial in the first case, and less trivial in the second - since we do not know what term is non-zero.

Question: Is there any algorithm (or (better) 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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Berlekamp-Massey. $\endgroup$ Commented Dec 12, 2024 at 7:15
  • $\begingroup$ @PeterTaylor thanks for comment ! Small question - we expect dependence on two things q and qˆn - at first glance BM is only on "q", without qˆn. Or I am not correct ? $\endgroup$ Commented Dec 12, 2024 at 9:20
  • $\begingroup$ Yes, BM is for fixed coefficients. I overlooked that you want something more complex. To be clear: is that $q^n$ and your keyboard is producing circumflex accents instead of carets, or is it something else? $\endgroup$ Commented Dec 12, 2024 at 10:28
  • $\begingroup$ @PeterTaylor Yes, it is q in power n. My french keyboard produces circumflex accents - sorry. For me they look like power sign in tex. $\endgroup$ Commented Dec 12, 2024 at 12:10

2 Answers 2

Reset to default
3
$\begingroup$

I have a Mathematica function that finds such recurrences, available here, on GitHub. The function is called FindPolynomialRecurrence.

The input is a list of polynomials in one variable. You can specify (maximal) length of recurrence. The coefficients are polynomials in $q$ and $n$, where $n$ is the index and $q$ the variable. You can specify maximal degree of these. It also allows for the recursion to involve derivatives (of specified order) of previous terms.

This algorithm allows for finding recursions for many of the classical sequences (Narayana polynomials, Eulerian polynomials, etc).

The code behind it is basically a big system of linear equations, nothing fancy. You of course need more data for reliably finding long recursions.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Thanks a lot for the answer ! May I ask some more details: first we do not have Mathematica - is there any way to launch your package via web-interface - like WolframAlfa ? Second: I a little modified the question - the relation might be a little bit more tricky - so not so clear how to normalize before rewriting as linear system - does your system support such cases ? Third - do not you know some analogous packages for Sage ? $\endgroup$ Commented Dec 12, 2024 at 8:43
  • 1
    $\begingroup$ My package also deals with a normalization factor (one supplies a Homogeneous->True flag). I think you need Mathematica unfortunately, one usually has to pay to run computations on other people's computers :). Not Sure if sage has it - I have not heard of this. But the logic is not that tricky to implement if you know Sage. I think it might take an hour or so of coding. $\endgroup$ Commented Dec 12, 2024 at 11:31
  • 1
    $\begingroup$ May I ask some question about package: I tried to run the following code in Wolfram Mathematica: FindPolynomialRecurrence[{1, t, 1 + t, 2 t + 1, 3 t + 2, 5 t + 3}, {t, n}, DifferentialDegree -> 0], and it doesn't work, it gives output "FindPolynomialRecurrence[{1, t, 1 + t, 1 + 2 t, 2 + 3 t, 3 + 5 t}, {t, n}, 0 -> 0]". Could you please show where there could be a possible mistake? $\endgroup$ Commented Jan 5 at 11:36
  • 1
    $\begingroup$ @MikhailEvseev You need to load the package first, either Get["PolynomialTools`"]; (assuming you put it in your package path) or, Get["/the/path/PolynomialTools.m"]; When I run your code, it returns None, so it does not satisfy a linear recurrence of default length (1). Increasing the length to 2, i.e, running FindPolynomialRecurrence[{1, t, 1 + t, 2 t + 1, 3 t + 2, 5 t + 3}, {t, n}, DifferentialDegree -> 0, RecurrenceLength -> 2] gives that each poly is the sum of prev two. $\endgroup$ Commented Jan 13 at 5:12
3
$\begingroup$

The guessing package in FriCAS has support for $q$-difference and $q$-differential equations. See https://arxiv.org/pdf/math/0702086 for some examples. Feel free to contact me by email for further help.

In principle, this package can also be used from within SageMath, but for larger examples I advise against it.

Hebisch, Waldemar; Rubey, Martin, Extended rate, more GFUN, J. Symb. Comput. 46, No. 8, 889-903 (2011). ZBL1218.68204.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.