6
$\begingroup$

This question concerns various important classes of formal power series. For concreteness and convenience, let us work with power series $F(x) = \sum_{n\geq 0}c_n x^n \in \mathbb{C}[[x]]$, i.e., with complex coefficients. Then we have the following inclusions: $$ \textrm{rational power series} \subseteq \textrm{algebraic power series} \subseteq \textrm{differentially finite power series}$$ See for instance the classic paper Differentially Finite Power Series by Stanley, which defines all these classes and explains the inclusions. These classes are especially important when thought of as generating functions of discrete structures according to size, e.g., words in some formal language according to their length.

When I conceptualize these classes of power series, I think of the following table:

Power series class Example $F(x)$ Recurrence satisfied by $c_n$ G.f. for formal language class
rational $\sum_{n\geq 0} 2^nx^n$ linear recurrence with constant coefficients regular language
algebraic $\sum_{n\geq 0}\binom{2n}{n}x^n$ ??? unambiguous context-free grammar
$D$-finite $\sum_{n\geq 0}\binom{2n}{n}^2x^n$ linear recurrence with polynomial coefficients ???

Question: Are there reasonable things to fill in the missing "???" squares in the table above?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ For the second "???" mathoverflow.net/questions/8262/… $\endgroup$
    – Gjergji Zaimi
    Commented Jan 15 at 20:28
  • 2
    $\begingroup$ I think this table is slightly misleading. Not everything in the first is in the third column (what do you do with -1 e.g.?) And if you are constraining yourself to a smaller class in the third column, you need to talk about N-rational GF and N-algebraic GFs of Banderier-Dromota. For D-finite there is no good notion of "N-D-finite", but by Christol's conjecture if your seq grows at most exponentially these are binomial sums and do have combin. interpretation (see Garrabrant-Pak). For more on this see my recent talk video tinyurl.com/3m8btt7y and slides tinyurl.com/5n773b6w $\endgroup$
    – Igor Pak
    Commented Jan 15 at 21:34
  • $\begingroup$ @IgorPak: of course you are right, these are just meant to be roughly equivalent categories. E.g., I believe the exact statement is that $c_n$ satisfies a linear recurrence with constant coefficients iff $F(x) = P(x)/Q(x)$ for polynomials with $\mathrm{deg}(P) < \mathrm{deg}(Q)$. So, in general, we can take a sequence of coefficients satisfying a constant coefficient recurrence and change finitely many initial terms to get a rational power series. But here I am just interested in a "big picture" perspective, ignoring these technical details. $\endgroup$
    – Sam Hopkins
    Commented Jan 16 at 0:27
  • $\begingroup$ I think it would be good to add another row for differentially algebraic series, and yet another one for recurrences that are polynomials in $f_n, f_{n+1},\dots, f_{n+k}$ for fixed $k$. $\endgroup$
    – Martin Rubey
    Commented Jan 16 at 17:10
  • 1
    $\begingroup$ @SamHopkins Technical details matter. These issues are complicated and somewhat confusing, but it is what it is. For example, number of accepting paths in a FSA have indeed N-rational GFs. But not all rational nonnegative GFs are N-rational. For Algebraic, the same story with PDA. You might think it's a quibble, but it's actually crucial for the "big picture". For example, given an algebraic GF (say, Tutte's GF for #plane triangulations), what type of class does it really belong to since it's not N-algebraic but is obviously "combinatorial"? $\endgroup$
    – Igor Pak
    Commented Jan 16 at 21:09

0

Reset to default

You must log in to answer this question.