# How to find/guess a polynomial sequence?

My question is motivated by the recent question and more recent appearance of its author Bruce Westbury. Most of you know that the best way to find a sequence of integers is looking for it on The On-Line Encyclopedia of Integer Sequences. (My personal success of using this powerful database is however less than 10%.) Another strategy (especially, when you suspect that your sequence is holonomic) would be trying a guessing package in a computer algebra system, like $\operatorname{gfun}$ in Maple.

What can we do if we need to identify a sequence of polynomials? (for simplicity with integer coefficients)

One recipe (which was used by my colleague for solving the problem in this question) is again to use the OEIS, since the latter contains many 2D examples as well (like the whole Pascal triangle of binomial coefficients and several subcollections from it). The chances are miserable (as Bruce's sequence shows). Even having some additional information (like knowing that the polynomials are $q$-analogues of a known integer sequence), there seems to be no general machinery or database to assist in identification. Are there algorithms (better implemented) for polynomials analogous to $\operatorname{gfun}$?

Thanks!

P.S. The tag "soft-question" here means that the question is indeed soft but also on software.

-
Maybe we should have on On-Line Encylopedia of Polynomial Sequences? –  Bruce Westbury Jul 22 '10 at 11:45
Interesting question. Algorithmically, this strikes me as a problem that would belong to the PSPACE class or even higher, i.e. not terribly tractable computationally. –  Noldorin Jul 22 '10 at 12:28
@Bruce: A good point. And I am still wondering on how the magic "FRICAS team" can be of help here... ;-) @Noldorin: I am trying to understand whether "not terribly tractable computationally" means tractable or not. –  Wadim Zudilin Jul 22 '10 at 13:01
In my profile I see that there was one more answer "There are sophisticated algorithms that do exactly that. There is a very powerful function in Mathematica: reference.wolfram.com/mathematica/ref/…; from user mathoverflow.net/users/1047/vonjd. I wonder why it's not here any more but indeed in the rubric "Generalizations & Extensions" there is an example of non-numerical guess. –  Wadim Zudilin Jul 22 '10 at 13:07
@Wadim: I haven't really investigated it so I wouldn't now for sure. :) Intuition says it would possible, but may well scale expontentially with time - whether you call that tractable or not is up to you! –  Noldorin Jul 22 '10 at 13:17

You do realize that gfun works for polynomials as well as for integer sequences? The version that ships with Maple is not always the most up-to-date however, for that you should get it from the source. I know the authors very well, and the implementation of the guessing algorithms in gfun are state-of-the-art. [That doesn't mean that they can't be improved!] I know that they like to receive feedback and bug reports.

For those who are curious: the core algorithm behind gfun's guessing capabilities is simultaneous Hermite-Pade approximation, using a variant of the Beckermann-Labahn algorithm.

-
Great, Jacques! Thanks a lot for the link (and I hope it should be in Maple 15). So, the differential equations for generating functions of polynomial sequences can be now guessed as well. I wonder whether the techniques is $q$-applicable but nevertheless it's already more than something. –  Wadim Zudilin Jul 22 '10 at 12:56
The DEs for generating function guessing of polynomial sequences has been available for over 15 years in gfun. The question about q-guessing is another matter though: that would require a q-Pade. Now, I do believe that Beckermann-Labahn have some more recent work which works over Ore algebras, so maybe. I would have to ask George (but I won't see him until mid-August). And Bruno (Salvy, main author of gfun) is on vacation until mid-August as well. –  Jacques Carette Jul 22 '10 at 21:33
I'll stay in touch with you on the news in this area. Thanks! –  Wadim Zudilin Jul 22 '10 at 23:36
same thing for FriCAS. I'm surprised: you know that FriCAS also does q-guessing, no? –  Martin Rubey Aug 4 '10 at 7:24
I'm not sure I knew that! Nice to know. What algorithms are used for that part? An Ore variant of Hermite-Pade? –  Jacques Carette Aug 4 '10 at 14:34

An obvious way to convert a sequence of polynomials to a sequence of numbers is to plug in a number. Small integers, ..., -1, 0, 1, ... often give illuminating sequences, and I have many times guessed a sequence of polynomials by this method, either by recognizing that the resulting sequence was holonomic or by finding it in Sloane. For sequences of $q$-series, amazing things sometimes happen when you plug in a root of unity. For example, in Bruce Westbury's sequence that inspired the question, plugging in $e^{2\pi i/6}$ produces only the integers -1, 0, 1 for the terms listed in his question. Plugging in $e^{2\pi i/5}$ doesn't always give integers, but does give 0 for the last three terms. I don't know how to use this to guess the sequence, but it is curious. I wonder if it continues...

-
That's an excellent point, Will! Have you posted your hint to Bruce's problem? Thank you! –  Wadim Zudilin Jul 22 '10 at 23:34
I did add a comment over there. –  Will Orrick Jul 23 '10 at 1:40
I see. You are not brave to put it as answer. :-) (On MO we are not necessarily supposed to provide final answers!) –  Wadim Zudilin Jul 23 '10 at 2:29
Thanks Will. I have put this information in the question. I would expect any features you observe to persist. Does this help? –  Bruce Westbury Jul 23 '10 at 7:30

Sounds like a problem you'd find in the book A=B.

-
John, as you can read from my initials, WZ, I am pretty familiar with Wilf-Zeilberger. As well as continuation of the story for the $q$-series. The methods are not efficient to determine a polynomial seqeunce, unless you can give an example. –  Wadim Zudilin Jul 22 '10 at 23:32