9
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ Maybe we should have on On-Line Encylopedia of Polynomial Sequences? $\endgroup$
    – Bruce Westbury
    Commented Jul 22, 2010 at 11:45
  • $\begingroup$ 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. $\endgroup$
    – Noldorin
    Commented Jul 22, 2010 at 12:28
  • $\begingroup$ @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. $\endgroup$
    – Wadim Zudilin
    Commented Jul 22, 2010 at 13:01
  • $\begingroup$ 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/FindSequenceFunction.html" 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. $\endgroup$
    – Wadim Zudilin
    Commented Jul 22, 2010 at 13:07
  • $\begingroup$ @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! $\endgroup$
    – Noldorin
    Commented Jul 22, 2010 at 13:17

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Wadim Zudilin
    Commented Jul 22, 2010 at 12:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jacques Carette
    Commented Jul 22, 2010 at 21:33
  • $\begingroup$ I'll stay in touch with you on the news in this area. Thanks! $\endgroup$
    – Wadim Zudilin
    Commented Jul 22, 2010 at 23:36
  • $\begingroup$ same thing for FriCAS. I'm surprised: you know that FriCAS also does q-guessing, no? $\endgroup$
    – Martin Rubey
    Commented Aug 4, 2010 at 7:24
  • $\begingroup$ I'm not sure I knew that! Nice to know. What algorithms are used for that part? An Ore variant of Hermite-Pade? $\endgroup$
    – Jacques Carette
    Commented Aug 4, 2010 at 14:34
3
$\begingroup$

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...

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

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wadim Zudilin
    Commented Jul 22, 2010 at 23:32

You must log in to answer this question.

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