Take the 2-minute tour ×
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|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
2  
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
    
Nice! Actually I wasn't thinking to a particular context, that in any case has to be fixed (even though I'd had bet rational functions were ok!) –  Pietro Majer Aug 16 '12 at 16:38

2 Answers 2

up vote 3 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|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

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

 
discard

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.