# A diagonal operation on power series

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)$ ?

• When you say "it is known that", do you have a reference? – Igor Rivin Aug 16 '12 at 15:01
• That is, you give an example (which works for me) but what book do you know which discusses these matters? – Igor Rivin Aug 16 '12 at 15:02
• What about $\Delta(f)(t)=\mathrm{Res}_{z=0} f(tz,1/z)/z$ – Pietro Majer Aug 16 '12 at 15:03
• @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 :). – fedja Aug 16 '12 at 15:27
• 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). – Gerry Myerson Aug 16 '12 at 23:13

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.

• 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. – HCH Aug 19 '12 at 23:48

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

• I was about to cite a "recent paper by Bostan, Salvy, and Dumont" but then I saw your answer :) – Suvrit Oct 18 '15 at 3:13

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

• 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! – HCH Aug 20 '12 at 0:05