3
$\begingroup$

Is every univariate P-recurrence the diagonal of a constant coefficient multivariate recurrence?

For example, the Delannoy numbers satisfy $n d(n) = 3(2n-1) d(n-1)-(n-1) d(n-2)$, and it is the diagonal of $D(m,n)$, i.e. $d(n)=D(n,n)$, where $D(m,n) = 1$ if $m=0$ or $n=0$, and $D(m,n) = D(m-1,n) + D(m-1,n-1) + D(m,n-1)$ otherwise.

Any pointer or reference will be appreciated.

[Background information: It is well-known that the diagonal of a multivariate D-finite series is D-finite. (see "The Diagonal of a D-Finite Power Series is D-Finite" by L. Lipschitz, Journal of Algebra 1988.) And there is a well-known connection between D-finite series and P-recursive sequences, both in the univariate (R. Stanley 1980) and multivariate settings (L. Lipschitz 1989).]

Improve this question
$\endgroup$
5
  • $\begingroup$ What about setting $D (a,b) = d ((a+b)/2) $ if $a+b $ is even and $0$ otherwise? $\endgroup$
    – darij grinberg
    Commented Oct 7, 2017 at 21:58
  • $\begingroup$ Thanks. But I think the resulted D(a,b) does not follow a recurrence, at least not of the desired type. $\endgroup$
    – Thomas
    Commented Oct 8, 2017 at 15:44
  • 2
    $\begingroup$ No, the factorials grow too quickly to be diagonal coefficients of rational functions. $\endgroup$
    – Ira Gessel
    Commented Oct 10, 2017 at 3:36
  • 1
    $\begingroup$ Here is a good set of slides about your question pierre.lairez.fr/files/slides/diapos-2015-03-27.pdf by Pierre Lairez. There is a conjecture: "integer coeff + convergent + d-finite" => diagonal? The statement seems to be known as Christol's conjecture (1990) and it seems that it hasn't been proven yet. $\endgroup$
    – Sergey Dovgal
    Commented Oct 11, 2017 at 6:35
  • $\begingroup$ I do not whether it's intentional, but the question is about the diagonal of a constant coefficient multivariate recurrence, not a system of them. Then you can have recurrences like the knight walk recurrence of Bousquet-Mélou and Petkovsek that do not correspond to a D-finite sequence. That the diagonal of such a sequence grows like a factorial is not ruled out by the usual results. $\endgroup$
    – Bruno Salvy
    Commented Oct 16, 2017 at 5:26

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .