10
$\begingroup$

Given a formal power series $f(x,y)=\sum_{n,m\ge 0}f(n,m)\: x^n y^m$ in two variables $x$ and $y$ over some field of characteristic zero, e.g. the field of complex numbers $\mathbb C$, we define a new formal power series in one variable $t$:

$\Delta(f)(t):=\sum_{i\ge 0} f(i,i) \:t^i$.

It is known that if $f(x,y)$ is rational $\Delta(f)(t)$ is in general not rational (I think it is algebraic though).

Example: $f(x,y)=\frac{1}{1-x-y}$ leads to $\Delta(f)(t)=(1-4t)^{-1/2}$.

The question is: Is there a constructive way (i.e. algorithm or explicit formula) to calculate $\Delta(f)(t)$ for rational (or algebraic) $f(x,y)$ ?

Improve this question
$\endgroup$
6
  • $\begingroup$ When you say "it is known that", do you have a reference? $\endgroup$
    – Igor Rivin
    Commented Aug 16, 2012 at 15:01
  • $\begingroup$ That is, you give an example (which works for me) but what book do you know which discusses these matters? $\endgroup$
    – Igor Rivin
    Commented Aug 16, 2012 at 15:02
  • 3
    $\begingroup$ What about $\Delta(f)(t)=\mathrm{Res}_{z=0} f(tz,1/z)/z$ $\endgroup$
    – Pietro Majer
    Commented Aug 16, 2012 at 15:03
  • 1
    $\begingroup$ @Pietro What you wrote is a really good mind-boggling exercise for the students: if your formula were correct, $\Delta f$ would be rational for rational $f$ (computing the residue of a rational function requires a few differentiations only and they cannot kill the rational dependence on the parameter $t$). It took me 3 full minutes to discover the error, so I do not want to deprive the others from the pleasure of figuring it out by themselves :). $\endgroup$
    – fedja
    Commented Aug 16, 2012 at 15:27
  • 1
    $\begingroup$ Also worth a look: van der Poorten and Lipshitz, Rational functions, diagonals, automata and arithmetic, in Number Theory (Banff, AB, 1988), 339–358, de Gruyter, Berlin, 1990, MR1106672 (93b:11095). $\endgroup$
    – Gerry Myerson
    Commented Aug 16, 2012 at 23:13

3 Answers 3

Reset to default
7
$\begingroup$

There is a discussion of taking diagonals of rational functions in Stanley's Enumerative Combinatorics Volume II (section 6.3). It contains a reasonably explicit description of how to take diagonals using Puiseux series as well as a description of how to do it using residues.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this hint. Actually I have the book on my shelf (Apparently I know volume I better than volume II ...). The example as well as the residue formula, that is mentioned in the comments, appear in section 6.3. It is not clear at the moment whether the proof Thm. 6.3.3. is constructive enough for my purposes. $\endgroup$
    – HCH
    Commented Aug 19, 2012 at 23:48
7
$\begingroup$

The reference to Stanley's book given by Qiaochu Yuan provides indeed an enlightening exposition on diagonals of bivariate rational functions. Note that the method using a residue mentioned at the end of example 6.3.4 is better suited for computations than the one using Puiseux series (Theorem 6.3.3).

This being said, it is hard (impossible?) to find a reference with a complete algorithm for the computation of algebraic equations for bivariate diagonals in characteristic 0. This is one of the motivations for a recent paper of Alin Bostan, Bruno Salvy and myself on that subject: Algebraic Diagonals and Walks: Algorithms, Bounds, Complexity. H.-C. Herbig's request is met there by Algorithm 3 and formula (4).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I was about to cite a "recent paper by Bostan, Salvy, and Dumont" but then I saw your answer :) $\endgroup$
    – Suvrit
    Commented Oct 18, 2015 at 3:13
5
$\begingroup$

Yes, there is a constructive way for both rational and algebraic $f.$ You should check out the very nice paper by Adamszewski and Bell, and references there in -- the formula for rational functions is given by Deligne (ref [13] in the cited paper), the result for algebraic functions appears very deep (see papers by Andre and Christol cited in the reference), but anyway, just read the introduction to the paper.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I was not aware of the literature mentioned above. I did know of a number of papers on the Hadamard product. The link to the diagonal is explained for example in: MR1617401 Abdelkader Necer, "Séries formelles et produit de Hadamard" I was not able yet to destille an "algorithm" from Deligne paper. Actually, his geometric proof of Furstenberg's theorem appears to be longer than the one in Stanley's book (see below). I have not yet looked into Christol's papers. Anyway - thanks for this helpful comment! $\endgroup$
    – HCH
    Commented Aug 20, 2012 at 0:05

You must log in to answer this question.

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