10
$\begingroup$

I have a formal power series in one variable that I think might be algebraic (or perhaps just D-finite). Is there software that could help me explore this?

By way of comparison, there’s a very simple way to see if a formal power series appears to be rational: for small values of $n$, compute the determinant of the $(n+1)$-by-$(n+1)$ Hankel matrix whose entries are the first $2n+1$ coefficients of the formal power series. If the determinant is 0, then nontrivial elements of the nullspace correspond to possible $n$th order recurrence relations.

(I’m including the combinatorics tag since this sort of pattern-finding is sometimes an important early step in a combinatorial research project.)

$\endgroup$
9
  • 2
    $\begingroup$ I have written a Maple library that takes a sequence and tries to conjecture an algebraic, D-finite, or D-algebraic expression for it. It's not quite polished enough for a public release yet, but I would be happy to run it on your series for you. $\endgroup$ May 19 at 21:20
  • $\begingroup$ Thanks for the offer, Jay! The sequences I’m curious about are 18, 142, 1266, 12030, 118650, 1198230, 12296202, 127633590, 1336133730, 14079114270, 149124688482, 1586159072814, 16929780310218, 181227223899942, 1944808008842490, 20915277691567206, ... and 84, 724, 6516, 60900, 586404, 5777916, 57952212, 589381020, 6060195316, 62863155972, 656765033268, 6902094928308, 72892778268996, 773013952508268, 8226672021670804,... $\endgroup$ May 19 at 23:58
  • $\begingroup$ I wasn't able to make any guesses, but that is not uncommon with this few terms. Any chance you have more? $\endgroup$ May 20 at 1:17
  • 2
    $\begingroup$ The listtorec function in the gfun package in Maple tries to find a P-recursion for a sequence and listtodiffeq tries to find a differential equation. They do not succeed in your examples. See de.maplesoft.com/support/help/Maple/view.aspx?path=gfun. $\endgroup$
    – Ira Gessel
    May 20 at 2:26
  • 1
    $\begingroup$ Could you include the algorithm that generated the sequences? It might be relevant $\endgroup$ May 22 at 17:17
9
$\begingroup$

Fricas is good at that. It can be accessed via sage, once installed.

sage: L=[catalan_number(i) for i in range(20)]                                  
sage: fricas.guessHolo(L)                                                       
[
     n           2      ,
  [[x ]f(x): (4 x  - x)f (x) + (2 x - 1)f(x) + 1 = 0,

                     2      3      4
   f(x) = 1 + x + 2 x  + 5 x  + O(x )]
  ]
sage:  

and also

sage: fricas.guessAlg(L)                                                        
    n             2                                   2      3      4
[[[x ]f(x): x f(x)  - f(x) + 1 = 0, f(x) = 1 + x + 2 x  + 5 x  + O(x )]]
$\endgroup$
6
  • $\begingroup$ If I'm doing it right, doesn't know that. $\endgroup$
    – LSpice
    May 22 at 14:33
  • $\begingroup$ (The previous comment was very terse because the links were very long. 😁) $\endgroup$
    – LSpice
    May 22 at 14:36
  • 1
    $\begingroup$ Sagecell does not have fricas. You need to do "sage -i fricas" in your own installation of sagemath. $\endgroup$
    – F. C.
    May 22 at 16:59
  • $\begingroup$ There is a sandbox for fricas, but it seems it cannot handle these sequences. $\endgroup$ May 22 at 17:15
  • 1
    $\begingroup$ Once you have sage installed, sage -i fricas installs fricas. $\endgroup$ May 23 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.