Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|cite|improve this question
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

3 Answers 3

up vote 5 down vote accepted

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.

share|cite|improve this answer
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. – H.-C. Herbig 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).

share|cite|improve this answer
I was about to cite a "recent paper by Bostan, Salvy, and Dumont" but then I saw your answer :) – Suvrit Oct 18 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 [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.

share|cite|improve this answer
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! – H.-C. Herbig Aug 20 '12 at 0:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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