Louis Dumont
Home
| Research | Publications
| Thesis defense |
My
PGP key
Research
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
$$\sum_{i=0}^r{c_i(n)u_{n+i}}=0,$$
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.