Louis Dumont

HomeResearch | Publications | Thesis defense My PGP key


Diagonals of rational functions

Let $$f(x_1,x_2,\dots,x_n)=\sum_{i_1,i_2,\dots,i_r\ge 0}{u_{i_1,i_2,\dots,i_r}x_1^{i_1}x_2^{i_2}\dots x_r^{i_r}}$$ be a rational function. The diagonal of $f$ is defined as
$$\mathrm{Diag}(f) = \sum_{i\ge 0}{u_{i,i,\dots,i}x^i}.$$
Diagonals of rational functions form a very rich class that is studied actively.
When $f(x,y)$ is a bivariate rational function, $\mathrm{Diag}(f)$ is an algebraic function. This result goes back all the way to Pólya in the 1920's.
This theorem is effective, and its algorithmic aspects are studied in [1]. A long version of this paper can be found at [2].

Creative Telescoping

The method of creative telescoping has become a standard approach for the symbolic computation of integrals. Suppose for instance that you wish to compute an integral
$$u_n=\oint{F_n(x)\mathrm{d} x}$$ on a small contour around $0$. Since the integral depends on a parameter $n$, the result is a sequence. The aim of creative telescoping is to discover a relation of the form
$$\sum_{i=0}^r{c_i(n)F_{n+i}(x)}=G_n'(x)\qquad (1)$$
for a certain function $G_n$. Provided that the functions involved are regular enough and that the contour doesn't meet their poles, this equation can be integrated, yielding
that is, a recurrence for the sequence $(u_n)$.

This approach has been used in many more situations : with a continuous parameter, with more variables, for sum computations, …

In [3], an algorithm that belongs to the new generation of reduction-based creative telescoping algorithm is designed to discover equation of type $(1)$ when $F_n(x)$ is a mixed hypergeometric and hyperexponential term, that is when
$$\frac{F_{n+1}(x)}{F_n(x)}\quad \text{and}\quad \frac{F_n'(x)}{F_n(x)}$$
are rational functions.

A preliminary implementation of the algorithms described in this paper is available online.