# Creative Telescoping for Parametrised Integration and Summation

Frédéric Chyzak

► To cite this version:

Frédéric Chyzak. Creative Telescoping for Parametrised Integration and Summation. École thématique. France. 2011, pp.1-37. hal-04194004

HAL Id: hal-04194004

https://inria.hal.science/hal-04194004v1

Submitted on 1 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Creative Telescoping for Parametrised Integration and Summation

Frédéric Chyzak

<figure><img src="image_2.png" /></figure>

Journées nationales de Calcul formel (Nov. 14–18, 2011)
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
# A Nice Story: Apéry's Proof of Irrationality of $\zeta(3)$

## Proof, as explained in (van der Poorten, 1979)

Define:

$$ 
\begin{aligned}
b_{n,k} &= \binom{n}{k}^2 \binom{n+k}{k}^2, \quad c_{n,k} = \sum_{m=1}^{n} \frac{1}{m^3} + \sum_{m=1}^{k} \frac{(-1)^{m-1}}{2m^3 \binom{n}{m} \binom{n+m}{m}}, \\
a_{n,k} &= b_{n,k} c_{n,k}, \quad a_n = \sum_{k=0}^{n} a_{n,k}, \quad b_n = \sum_{k=0}^{n} b_{n,k}, \\
g_n &= \gcd(1, \dots, n), \quad p_n = 2g_n^3 n, \quad q_n = 2g_n^3 b_n.
\end{aligned}
$$

Then, $(a_n)$ and $(b_n)$ satisfy the same 2nd-order recurrence, and:

$$ \zeta(3) - \frac{a_n}{b_n} = \mathcal{O}(b_n^{-2}), \quad p_n \in \mathbb{Z}, \quad q_n \in \mathbb{N}, \quad \zeta(3) - \frac{p_n}{q_n} = \mathcal{O}(q_n^{-1.08}). $$

Classical irrationality criterion for $\alpha \in \mathbb{R}$:

$$ \left( \forall \epsilon > 0, \exists \frac{p}{q}, \left| \alpha - \frac{p}{q} \right| < \frac{\epsilon}{q} \right) \Rightarrow \alpha \notin \mathbb{Q}. $$
# Apéry's Recurrence for $(a_n)$ and $(b_n)$

Second-order recurrence (Apéry, 1979)

$$ (n + 1)^3 u_{n+1} - (34n^3 + 3n^2 + 27n + 5) u_n + n^3 u_{n-1} = 0 $$

Cohen and Zagier's "Creative Telescoping" (van der Poorten, 1979)

"[They] cleverly construct

$$ B_{n,k} = 4(2n+1)(k(2k+1) - (2n+1)^2) b_{n,k} $$

with the motive that

$$ B_{n,k} - B_{n,k-1} = (n+1)^3 b_{n+1,k} - (34n^3 + 51n^2 + 27n + 5)b_{n,k} + n^3 b_{n-1,k}. $$

After summation over $k$ from 0 to $n+1$:

$$ \underbrace{B_{n,n+1} - B_{n,n-1}}_{0-0=0} = (n+1)^3 b_{n+1} - (34n^3 + 3n^2 + 27n + 5) b_n + n^3 b_{n-1}. $$
# Differentiating under the Integral Sign

Zeilberger's derivation (1982) of a classical integral

$$f(b) = \int_{-\infty}^{+\infty} e^{-x^2} \cos 2bx \, dx = ?$$

$$f'(b) = \int_{-\infty}^{+\infty} -2xe^{-x^2} \sin 2bx \, dx = \\ \left[ e^{-x^2} \sin 2bx \right]_{x=-\infty}^{x=+\infty} + \int_{-\infty}^{+\infty} -2be^{-x^2} \cos 2bx \, dx = -2bf(b)$$

Continuous analogue of creative telescoping:

$$\frac{dF}{dx}(b,x) = \frac{df}{db}(b,x) + 2bf(b,x) \quad \text{for} \quad F(b,x) = -\frac{1}{2x} \frac{df}{db}(b,x)$$

After integration over $x$ from $-\infty$ to $+\infty$:

$$\underbrace{\left[ \frac{dF}{dx}(b,x) \right]_{x=-\infty}^{x=+\infty}}_{0-0=0} = f'(b) + 2bf(b)$$
# Sums and Integrals (1/5)

## Binomial sums

$$ \sum_{k=0}^{n} \binom{n}{k}^2 \binom{n+k}{k}^2 = \sum_{k=0}^{n} \binom{n}{k} \binom{n+k}{k} \sum_{j=0}^{k} \binom{k}{j}^3 \quad (\text{Strehl, 1994}) $$

$$ \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{i+j}{i}^2 \binom{4n-2i-2j}{2n-2i} = (2n+1) \binom{2n}{n}^2 \quad (\text{Blodgelt, 1990}) $$

## Integrals of the theory of special functions

Four types of Bessel functions (Glasser & Montaldi, 1994):

$$ \int_{0}^{+\infty} x J_{1}(ax) I_{1}(ax) Y_{0}(x) K_{0}(x) dx = - \frac{\ln(1-a^4)}{2\pi a^2} $$

No explicit form, but a 2nd-order linear ODE:

$$ \int_{0}^{\infty} \int_{0}^{\infty} J_{1}(x) J_{1}(y) J_{2}(c\sqrt{xy}) \frac{dx dy}{e^{x+y}} $$
# Sums and Integrals (2/5)

## Extractions of coefficients

Theory of orthogonal polynomials, here, Hermite (Doetsch, 1930):

$$ \frac{1}{2\pi i} \oint \frac{(1 + 2xy + 4y^2) \exp\left(\frac{4x^2y^2}{1 + 4y^2}\right)}{y^{n+1}(1 + 4y^2)^{\frac{3}{2}}} dy = \frac{H_n(x)}{[n/2]!} $$

## Scalar products involving orthogonal/parametrised families

Chebyshev polynomials, Bessel functions, modified Bessel functions:

$$ \int_{-1}^{+1} \frac{e^{-px} T_n(x)}{\sqrt{1-x^2}} dx = (-1)^n \pi I_n(p) \\ \int_{0}^{+\infty} xe^{-px^2} J_n(bx) I_n(cx) dx = \frac{1}{2p} \exp\left(\frac{c^2 - b^2}{4p}\right) J_n\left(\frac{bc}{2p}\right) $$
# Sums and Integrals (3/5)

## q-Sums, e.g., from the theory of combinatorial partitions

Finite forms of the Rogers–Ramanujan identities and a generalisation: setting $(q; q)_n = (1-q)\cdots(1-q^n)$,

$$ \sum_{k=0}^{n} \frac{q^{k^2}}{(q;q)_k (q;q)_{n-k}} = \sum_{k=-n}^{n} \frac{(-1)^k q^{(5k^2-k)/2}}{(q;q)_{n-k} (q;q)_{n+k}} \quad (\text{Andrews, 1974}) $$

$$ \sum_{j=0}^{n} \sum_{i=0}^{n-j} \frac{q^{(i+j)^2+j^2}}{(q;q)_{n-i-j} (q;q)_i (q;q)_j} = \sum_{k=-n}^{n} \frac{(-1)^k q^{7/2k^2+1/2k}}{(q;q)_{n+k} (q;q)_{n-k}} \quad (\text{Paule, 1985}) $$

## Scalar products in algebraic combinatorics

For $p_1 = x_1 + x_2 + \cdots$ and $p_2 = x_1^2 + x_2^2 + \cdots$:

$$ \left\langle \exp\left(\frac{(p_1^2 - p_2)}{2} - \frac{p_2^2}{4}\right) \middle| \exp\left(t\left(p_1^2 + p_2\right)/2\right) \right\rangle = \frac{e^{-\frac{1}{4}t(t+2)}}{\sqrt{1-t}} $$
# Sums and Integrals (4/5)

## Combinatorial identities

In the graph-counting sequence $k^{k-1}$:

$$ \sum_{k=0}^{n} \binom{n}{k} i (k+i)^{k-1} (n-k+j)^{n-k} = (n+i+j)^n \quad (\text{Abel}) $$

In Stirling numbers of the second kind (partitions) and Eulerian numbers (ascents in permutations):

$$ \sum_{k=0}^{n} (-1)^{m-k} k! \binom{n-k}{m-k} \binom{n+1}{k+1} = \left\langle \frac{n}{m} \right\rangle \quad (\text{Frobenius}) $$

In Bernoulli numbers (Taylor expansion of $\tan(x)$):

$$ \sum_{k=0}^{m} \binom{m}{k} B_{n+k} = (-1)^{m+n} \sum_{k=0}^{n} \binom{n}{k} B_{m+k} \quad (\text{Gessel, 2003}) $$
# Sums and Integrals (5/5)

Identities in more special functions (related, e.g., to number theory)

In Hurwitz's zeta function and the beta function:

$$ \int_{0}^{\infty} x^{k-1} \zeta(n, \alpha + \beta x) dx = \beta^{-k} B(k, n-k) \zeta(n-k, \alpha) $$

In the polylogarithm functions:

$$ \int_{0}^{\infty} x^{\alpha-1} \mathrm{Li}_{n}(-xy) dx = \frac{\pi (-\alpha)^{n} y^{-\alpha}}{\sin(\alpha \pi)} $$

In the (upper) incomplete Gamma function:

$$ \int_{0}^{\infty} x^{s-1} \exp(xy) \Gamma(a, xy) dx = \frac{\pi y^{-s}}{\sin((a+s)\pi)} \frac{\Gamma(s)}{\Gamma(1-a)} $$

+ a lot more in:

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

or in web sites, like Victor Moll's web site on GR
$$U_n = \sum_{k=a}^{b} u_{n,k} = ?$$

Given a relation $a_r(n)u_{n+r,k} + \cdots + a_0(n)u_{n,k} = v_{n,k+1} - v_{n,k}$, summation leads by "telescoping" to

$$a_r(n)U_{n+r} + \cdots + a_0(n)U_n = v_{n,b+1} - v_{n,a} \stackrel{\text{often}}{=} 0.$$

$$U(x) = \int_{a}^{b} u(x, y) dy = ?$$

Given a relation $a_r(x) \frac{\partial^r u}{\partial x^r} + \cdots + a_0(x)u = \frac{\partial}{\partial y} v(x, y)$, integrating leads by "telescoping" to

$$a_r(x) \frac{\partial^r U}{\partial x^r} + \cdots + a_0(x) U = v(x, b) - v(x, a) \stackrel{\text{often}}{=} 0.$$

Adapts easily to $U(x) = \sum_{k=a}^{b} u_k(x)$ and $U_n = \int_{a}^{b} u_n(y) dy$.
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
# History for Algorithms Based on Fasenmyer's Ansatz

* (Fasenmyer, 1945, 1947, 1949) "Some generalized hypergeometric polynomials", "A note on pure recurrence relations"

* (Rainville, 1960) "Special functions"

* (Verbaeten, 1974, 1976) "The automatic construction of pure recurrence relations", "Rekursietrekkingen voor lineaire hypergeometrische funkties"

* (Zeilberger, 1982) "Sister Celine's technique and its generalizations"

* (Lipshitz, 1988) "The diagonal of a D-finite power series is D-finite"

* (Zeilberger, 1990) "A holonomic systems approach to special functions identities"

* (Wilf and Zeilberger, 1992) "An algorithmic proof theory for hypergeometric (ordinary and 'q') multisum/integral identities"

* (Hornegger, 1992) "Hypergeometrische Summation und polynomiale Rekursion"

* (Wegschaider, 1997) "Computer generated proofs of binomial multi-sum identities"

* (Tefera, 2000, 2002) "Improved algorithms and implementations in the multi-WZ theory", "MultInt, a MAPLE package for multiple integration by the WZ method"

* (Riese, 2003) "qMultiSum: a package for proving q-hypergeometric multiple summation identities"
## Definition (hypergeometric terms)

An element $h$ of a $\mathbb{K}(n,k)$-vector space closed under shifts is hypergeometric if the quotients

$$ \frac{h_{n+1,k}}{h_{n,k}} \quad \text{and} \quad \frac{h_{n,k+1}}{h_{n,k}} $$

exist and are rational functions.

Basic observation: for all $(i,j) \in \mathbb{Z}^2$,

$$ \frac{h_{n+i,k+j}}{h_{n,k}} \in \mathbb{K}(n,k). $$

Generalises to more indices.

An **idealisation** of sequences like: $n!$, $\binom{n}{k}$, falling factorials
$$ n^k = n(n-1)\cdots(n-k+1), \text{ etc.} $$
Fasenmyer's ansatz: For a given hypergeometric $h_{n,k}$, solve

$$ \sum_{i=0}^{r} \sum_{j=0}^{s} c_{i,j}(n) h_{n+i,k+j} = 0 \quad \text{where the } c\text{'s don't involve } k. $$

Motivation:

$$ \sum_{i=0}^{r} \left( \sum_{j=0}^{s} c_{i,j}(n) \right) h_{n+i,k} = g_{n,k+1} - g_{n,k} \quad \text{where} \quad g_{n,k} = \sum_{i=0}^{r} \sum_{j=0}^{s-1} \tilde{c}_{i,j}(n) h_{n+i,k+j}. $$

Idea: Use the rational functions $h_{n+i,k+j}/h_{n,k}$, then clear denominators

$$ \sum_{i=0}^{r} \sum_{j=0}^{s} c_{i,j}(n) p_{i,j}(n,k) = 0 \quad \text{for } p_{i,j} \in \mathbb{K}(n)[k], $$

then solve a linear system over $\mathbb{K}(n)$. If no solution, increase $(r,s)$.

Question: possibility to enforce max $\deg_k p_{i,j} < (r+1)(s+1)$?
Two Motivating Examples

Common denominator $C_r$ of $h_{n+i,k+j}/h_{n,k}$ when $r = s$ increases?

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

$$ C_r = (k+1) \cdots (k+r) (n+1-k) \cdots (n+r-k) $$

has **linearly many terms**. The method **succeeds** easily (by finding Pascal's triangle rule).

$$ \frac{1}{n^2 + k^2} $$

$$ C_r = \prod_{i,j \in \mathbb{N}, i+j \le r} ((n+i)^2 + (k+j)^2) $$

has **quadratically many terms**. The method seems to **fail** (out of memory).
Definition (proper hypergeometric term)

A hypergeometric term $h$ is *proper* if it can be written, for $\epsilon_\ell = \pm 1$,

$$h_{n,k} = \underbrace{P(n,k)}_{P \in \mathbb{K}[n,k]} \underbrace{\zeta^n \bar{\zeta}^k}_{\bar{\zeta}, \bar{\xi} \in \mathbb{K}} \prod_{\ell=1}^{L} \Gamma(\underbrace{a_\ell n + b_\ell k + c_\ell}_{a_\ell, b_\ell \in \mathbb{Z}}, c_\ell \in \mathbb{K})^{\epsilon_\ell}.$$

$$\Gamma(s+1) = s \Gamma(s) \implies \Gamma(s+u)/\Gamma(s) = \text{poly. of degree } u \text{ in } s$$

Key observation

$$h_{n+i,k+j} \rightarrow \Gamma(a_\ell n + b_\ell k + c_\ell + u) \quad \text{where} \quad |u| \le |a_\ell|r + |b_\ell|s =: \sigma_\ell,$$

$$h_{n+i,k+j} = \zeta^n \bar{\zeta}^k \prod_{\ell=1}^{L} \Gamma(a_\ell n + b_\ell k + c_\ell - \epsilon_\ell \sigma_\ell)^{\epsilon_\ell} \times \underbrace{p_{i,j}(n,k)}_{\in \mathbb{K}(n)[k]}.$$

Examples: $\binom{n}{k}$, $\frac{1}{n-k}$, $n^{\underline{k}}$. Counter-example: $\frac{1}{n^2+k^2}$.
# Wilf and Zeilberger's Algorithm

## Theorem

Fasenmyer's ansatz can be solved for the setting:

$$r = B \quad \text{and} \quad s = (A - 1)B + \text{deg}_k(P) + 1,$$

where

$$A = \sum_{\ell} |a_{\ell}| \quad \text{and} \quad B = \sum_{\ell} |b_{\ell}|.$$

**Proof:** Observe $\text{deg}_k p_{i,j} \le \text{deg}_k P + Ar + Bs$, set $r = B$, and enforce

$$\text{deg}_k P + Ar + Bs + 1 < (r + 1)(s + 1).$$

## Generalisations:

* to more than 2 indices, with non-explicit bounds;

* to proper q-hypergeometric terms, with similar bounds:

$$h_{n,k} = P(q^n, q^k) \zeta^n \zeta^k q^{\alpha n^2 + \beta nk + \gamma k^2 + \lambda(\frac{n}{2}) + \mu(\frac{k}{2})} \prod_{\ell=1}^{L} ((q; c_\ell)_{a_\ell n + b_\ell k})^{\epsilon_\ell}.$$
Sequences:

$$u : (n,k) \mapsto u_{n,k}.$$

Shift operators:

$$S_n u : (n,k) \mapsto u_{n+1,k} \quad \text{and} \quad S_k u : (n,k) \mapsto u_{n,k+1}.$$

Multiplication operators:

$$nu : (n,k) \mapsto nu_{n,k} \quad \text{and} \quad ku : (n,k) \mapsto ku_{n,k}.$$

Operator algebras, e.g., $\mathbb{K}(n)[k]\langle S_n, S_k \rangle$, in which:

$$S_n n = (n+1) S_n \quad \text{and} \quad S_k k = (k+1) S_k.$$
# Wegschaider's Fix

Given $L = \sum_{i=0}^{r} \sum_{j=0}^{s} c_{i,j}(n) S_n^i S_k^j \in \mathbb{K}(n)\langle S_n, S_k \rangle$ such that $Lh = 0$, find a nonzero $P \in \mathbb{K}(n)\langle S_n \rangle$ such that $Ph = (S_k - 1)(\cdots)$, in the bad case $L = (S_k - 1)^m \tilde{L}$.

Observe the commutation:

$$ (k-a)^\ell (S_k - 1) = (S_k - 1)(k-a-1)^\ell - \ell(k-a-1)^\ell - 1, $$
so that, after iterating,

$$ k^m (S_k - 1)^m = (-1)^m m! + (S_k - 1) \cdots. $$

As $(-1)^m m!^{-1} k^m \tilde{L}h = 0$, write $\tilde{L} = P + (S_k - 1)Q$ to get:

$$ 0 = P(n, S_n) h + (S_k - 1) \underbrace{\hat{Q}(n, k, S_n, S_k) h}_{\substack{\text{dependency in } k \\ \text{still sums right!}}} \neq 0 $$
Verbaeten's Completion (1/2)

<figure><img src="image_7.png" /></figure>

$$ \text{Ex: } \sum_{k=0}^{2n} \underbrace{(-1)^k \binom{2n}{k}^3}_{:=h_{n,k}} = (-1)^n \frac{(3n)!}{n!^3} \quad (\text{Dixon, 1891}). $$

$$ r_{i,j} := \frac{h_{n-i,k-j}}{h_{n,k}} = (\cdots) \left( \frac{k!}{(k-j)!} \frac{(2n-k)!}{(2n-k-(2i-j))!} \right)^3 $$

Denom. of $r_{i,j}$ constant on a parallel to $\Delta$.

Common denom. of $r_{i,j}$ over the 's =
$(k-2n-4)^3 \cdots (k-2n-1)^3 =: C$.

$\deg_k Cr_{i,j} = 3(2i+4) \le 30$ over 's and 's.

\# of unknowns = \# of 's and 's = 36 \Rightarrow \text{success after}

\# equations = 1 + maximal degree in k = 31 \Rightarrow \text{completion!}
* Verbaeten could already solve Fasenmyer's ansatz for a class of special proper hypergeometric terms;

* Elegant geometric interpretation by Hornegger (volumes of polytopes);

* Nicely put to practice, also in the multisum case, by Wegschaider for sums, resp. Riese for *q*-sums.
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
Definition (D-finite term; hyperexponential term)

An element $f$ of a finite-dimensional $\mathbb{K}(x,y)$-vector space closed under derivations is called *differentiably finite*, in short *D-finite*.

$$ \dim \operatorname{span} \sum_{i,j \ge 0} \mathbb{K}(x,y) D_x^i D_y^j f < \infty. $$

The 1-dimensional case is called *hyperexponential*.

Vast closure properties, under: derivation, addition, product, and ...
# Lipshitz's Closure under Diagonals

Series $f = \sum_{n,m \in \mathbb{N}} c_{n,m} x^n y^m \in \mathbb{Q}[[x,y]] \to \textcolor{red}{\text{diagonal}} \Delta f = \sum_{n \in \mathbb{N}} c_{n,n} x^n \in \mathbb{Q}[[x]]$.

**Theorem (Lipshitz, 1989)**

The diagonal of a D-finite series is D-finite.

To prepare for the proof, introduce

$$g = \frac{1}{s} f \left( s, \frac{x}{s} \right) \in \bigcup_{m \in \mathbb{Z}} \left\{ \sum_{(p,q) \in \mathbb{Z}^2, p+q \ge m} \phi_{p,q} s^p x^q \right\},$$

so that $\Delta f = \text{res}_s g$, where

$$\text{res}_s \sum_{(p,q) \in \mathbb{Z}^2, p+q \ge m} \phi_{p,q} s^p x^q = \sum_{q=m+1}^{\infty} \phi_{-1,q} x^q.$$
# Differential Operators

Functions:
$$u : (x, y) \mapsto u(x, y).$$

Derivation operators:
$$D_x u : (x, y) \mapsto \frac{\partial u}{\partial x}(x, y) \quad \text{and} \quad D_y u : (x, y) \mapsto \frac{\partial u}{\partial y}(x, y).$$

Multiplication operators:
$$xu : (x, y) \mapsto xu(x, y) \quad \text{and} \quad yu : (x, y) \mapsto yu(x, y).$$

Operator algebras, e.g., $\mathbb{K}(x)[y]\langle D_x, D_y \rangle$, in which:
$$D_x x = x D_x + 1 \quad \text{and} \quad D_y y = y D_y + 1.$$

Remark: if $p \in \mathbb{K}[x, y]$,
$$D_x^a D_y^b p = p D_x^a D_y^b + \text{[terms of total order less than } a+b\text{)].}$$
By D-finiteness, $g$ annihilated by:

$$A(s, x, D_s) = \lambda(s, x) D_s^m + \text{(lower order terms in } D_s \text{ only)},$$

$$B(s, x, D_x) = \lambda(s, x) D_x^{m'} + \text{(lower order terms in } D_x \text{ only)},$$

for $\lambda \in \mathbb{K}[s, x]$ and all degrees $\le h$.

By induction using $\lambda D_s^a D_x^b g = \sum_{0 \le i+j \le a+b-1} (\deg \le h) D_s^i D_x^j g,$

$$\lambda^{a+b} x^c D_s^a D_x^b g = \sum_{0 \le i < m, 0 \le j < m'} (\deg \le (a+b)h+c) D_s^i D_x^j g.$$

Dimension analysis: for $a+b+c \le N$,

$$\dim. \binom{N+3}{3} \approx \Theta(N^3) \rightarrow \dim. \binom{(h+1)N+2}{2} \approx \Theta(N^2).$$

$g$ killed by $L(x, D_x, D_s) = P(x, D_x) D_s^v + \text{(higher-order deriv. w.r.t. } s\text{)},$ so that $P(\ne 0!)$ kills $\text{res}_s g = \Delta f$.
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
# History for Zeilberger's Fast Algorithm(s)

* (Gosper, 1978) "Decision procedure for indefinite hypergeometric summation"

* (Almkvist and Zeilberger, 1990) "The method of differentiating under the integral sign"

* (Zeilberger, 1991) "The method of creative telescoping"

* (Chyzak, 2000) "An extension of Zeilberger's fast algorithm to general holonomic functions"

* (Koutschan, 2010) "A fast approach to creative telescoping"
# Gosper's Algorithm (1/2)

## Specifications

**INPUT:** a hypergeometric term $f_k$.

**OUTPUT:** a rational function $R(k)$ such that $Rf$ is an indefinite sum w.r.t. $k$ of $f$, or $\nexists$ ("a proof that no such $R$ exists").

## Simplified variant (basing on Abramov's algorithm)

1. Rewrite the equation

$$f_k = R(k+1)f_{k+1} - R(k)f_k$$

in a rational function $R$ into

$$1 = R(k+1)\rho(k) - R(k).$$

2. Solve by **Abramov's decision algorithm**: finding no $R$ is a **proof** that none exists.
# Gosper's Algorithm (2/2)

## Original variant

1. Write the ratio $\rho(k) = f_{k+1}/f_k$ in the (unique) form

$$ \rho(k) = \frac{p(k+1)}{p(k)} \frac{q(k)}{r(k+1)} $$

so that $\gcd(p, q) = \gcd(p, r) = \gcd(q(k), r(k+h)) = 1$ for all integer $h > 0$.

2. The change of variables $R = \frac{rS}{p}$ yields an equation in a polynomial $S$:

$$ p(k) = q(k) S(k+1) - r(k) S(k). $$

3. Solve (using **explicit bounds**). If an $S$ is found, return $R = rS/p$, else, this is a proof that no $R$ exists.

Both variants reduce to linear-system solving.
Example of Use of Gosper's Algorithm

$$ \sum_{k=0}^{n-1} \frac{(-1)^k (4k+1) \binom{2k+1}{k}}{4^k (4k^2-1)} = -\frac{2(n+1)}{4n+1} \frac{(-1)^n (4n+1) \binom{2n+1}{n}}{4^n (4n^2-1)} - 2. $$

The hypergeometric summand is given by:

$$ \rho = -\frac{1}{2} \frac{(4k+5)(2k-1)}{(4k+1)(k+2)}, $$

$$ p(k) = 4k+1, \quad q(k) = \frac{1}{2}-k, \quad r(k) = k+2. $$
# Parametrised Gosper Algorithm

## Specifications

INPUT: a hypergeometric $f_k$ and rational functions $s_0(k), \dots, s_m(k)$.
OUTPUT: a rational function $R(k)$ and constants $\eta_0, \dots, \eta_m$ such that
$Rf$ is an indefinite sum w.r.t. $k$ of

$$ (\eta_0 s_0(k) + \dots + \eta_m s_m(k)) f_k, $$

or $\nexists$ ("a proof that no such $R$ exists for any family $\{\eta_i\}$").

## Sketch of algorithm

$\eta_i$ involved only **linearly** and **in inhomogeneous side** of equation $\rightarrow$
simply linear solving for $S(k)$ with additional unknowns $\eta_0, \dots, \eta_m$.
# Zeilberger's ("Fast") Algorithm

## Specifications

INPUT: hypergeometric term $f_{n,k}$.

OUTPUT: rational functions $\eta_0(n), \dots, \eta_r(n), \phi(n,k)$ for minimal $r \in \mathbb{N}$ such that

$$ \eta_r(n)f_{n+r,k} + \dots + \eta_0(n)f_{n,k} = \phi(n, k+1)f_{n,k+1} - \phi(n, k)f_{n,k}. $$

Termination not guaranteed in general, but it is in "holonomic" case. Explicit criterion due to Abramov.

## Sketch

For increasing values $r = 0, 1, \dots$:

* Compute the rational functions $s_i(n,k) = f_{n+i,k}/f_{n,k}$.

* Appeal to the parametrised Gosper algorithm.

* If $(\phi, \{\eta_i\})$ is found, return it (else loop).

A $q$-analogue exists for $q$-hypergeometric terms.
Example of Use of Zeilberger's Algorithm (1/5)

Jacobi's orthogonal polynomials $P_n^{(\alpha,\beta)}(x)$ can be expressed in terms of Gauss's hypergeometric function ${}_2F_1\left(\begin{array}{c} a, b \\ c \end{array}\middle|z\right)$:

$$P_n^{(\alpha,\beta)}(x) = \frac{(\alpha + 1)_n}{n!} {}_2F_1\left(-n, n + \alpha + \beta + 1 \middle| \frac{1-x}{2}\right),$$

$$\text{for} \quad {}_2F_1\left(\begin{array}{c} a, b \\ c \end{array}\middle|z\right) = \sum_{k=0}^{\infty} \frac{(a)_k (b)_k}{(c)_k k!} z^k.$$

Zeilberger's algorithm provides *recurrences* in $n, \alpha, \text{or } \beta$, like:

$$\begin{aligned} 0 = {}& 2(n+2)(n+\alpha+\beta+2)(2n+\alpha+\beta+2)P_{n+2}^{(\alpha,\beta)}(x) \\ & - ((2n+\alpha+\beta+2)_{3}x + (2n+\alpha+\beta+3)(\alpha-\beta)(\alpha+\beta))P_{n+1}^{(\alpha,\beta)}(x) \\ & + 2(n+\alpha+1)(n+\beta+1)(2n+\alpha+\beta+4)P_{n}^{(\alpha,\beta)}(x). \end{aligned}$$

Slight extension: mixed recurrences, contiguity relations.
Example of Use of Zeilberger's Algorithm (2/5)

The summand is

$$f_k = \frac{(\alpha + 1)_n (-n)_k (n + \alpha + \beta + 1)_k (1-x)^k}{n! (\alpha + 1)_k k! 2^k}.$$

The ratio $f_{k+1}/f_k$ is

$$\rho = \frac{1}{2} \frac{(n-k)(n+k+\alpha+\beta+1)(x-1)}{(k+1)(k+\alpha+1)}.$$
Example of Use of Zeilberger's Algorithm (3/5)

The parametrised recurrence to solve for rational solutions is

$$
\begin{align*}
& (n+2-k)(n+1-k)(n-k)(n+\alpha+\beta+2) \\
& \quad (n+\alpha+\beta+1)(n+k+\alpha+\beta+1)(x-1)R(k+1) \\
& -2(k+1)(k+\alpha+1)(n+\alpha+\beta+1) \\
& \quad (n+2-k)(n+1-k)(n+\alpha+\beta+2)R(k) \\
& = 2\eta_0(k+1)(k+\alpha+1)(n+\alpha+\beta+1) \\
& \quad (n+1-k)(n+2-k)(n+\alpha+\beta+2) \\
& \quad + 2\eta_1(n+k+\alpha+\beta+1)(n+\alpha+1)(k+1) \\
& \quad (k+\alpha+1)(n+2-k)(n+\alpha+\beta+2) \\
& \quad + 2\eta_2(n+\alpha+2)(n+\alpha+1)(n+\alpha+\beta+2+k) \\
& \quad (n+k+\alpha+\beta+1)(k+1)(k+\alpha+1).
\end{align*}
$$
Example of Use of Zeilberger's Algorithm (4/5)

A multiple of the denominators of all solutions is

$$ (n + 2 - k)(n + 1 - k). $$

The recurrence rewrites

$$ \begin{aligned} & \left( -(n + \alpha + \beta + 2) (n + \alpha + \beta + 1) (x - 1) k^2 + \cdots \right) S(k+1) \\ & \qquad + \left( -2(n + \alpha + \beta + 2) (n + \alpha + \beta + 1) k^2 + \cdots \right) S(k) \\ & = (c_0 k^4 + \cdots) \eta_0 + (c_1 k^4 + \cdots) \eta_1 + (c_2 k^4 + \cdots) \eta_2. \end{aligned} $$

Therefore, any solution $S(k)$ has degree at most 2 in $k$.
Example of Use of Zeilberger's Algorithm (5/5)

Solving yields $P(n,k) = Q(n,k+1) - Q(n,k)$ where

$$P(n,k) = 2(n + \beta + 1)(n + \alpha + 1)(2n + \alpha + \beta + 4) u(n,k) \\ -(2n + \alpha + \beta + 3)(\alpha^2 + \alpha^2 x + 4\alpha nx + 2\alpha\beta x + 6\alpha x + 12nx \\ + \beta^2 x + 4nx\beta + 4n^2 x + 6\beta x + 8x - \beta^2) u(n+1,k) \\ + 2(n + 2)(n + \alpha + \beta + 2)(2n + \alpha + \beta + 2) u(n+2,k),$$

$$Q(n,k) = \frac{N(n,k)}{D(n,k)} u(n,k) \quad \text{for}$$

$$N(n,k) = -2(2n + \alpha + \beta + 4)(2n + \alpha + \beta + 3)(2n + \alpha + \beta + 2) \\ \times (n + \alpha + 1)(\alpha + k)k \\ D(n,k) = (n + \alpha + \beta + 1)(n + 1 - k)(n + 2 - k).$$

The announced recurrence is obtained after summation.
Strict analogue for bivariate hyperexponential functions:

$$ \frac{D_x f(x, y)}{f(x, y)} = R(x, y) \in \mathbb{K}(x, y) \quad \text{and} \quad \frac{D_y f(x, y)}{f(x, y)} = S(x, y) \in \mathbb{K}(x, y). $$

Example:

$$ \begin{align*} F(x) &= \int_{-\infty}^{+\infty} f(x, y) dy \quad \text{for} \quad f(x, y) = \exp \left( -\frac{x^2}{y^2} - y^2 \right), \\ (xD_x^3 + 3D_x^2 - 4xD_x - 12) f &= D_y \left( \frac{2(3y^2 - 2x^2)}{y^3} f \right), \\ (xD_x^3 + 3D_x^2 - 4xD_x - 12) F &= 0, \\ F(x) &= \sqrt{\pi} \exp(-2x). \end{align*} $$

Termination always guaranteed by “holonomy”!
# Functions versus Equations versus Vector Space

Special function or combinatorial sequence $f$:

$$f(n, z) = J_n(z) \quad (\text{Bessel function}).$$

[Also: algebraic, trigonometric, elementary, transcendental, hypergeometric functions; binomial coefficients, harmonic numbers, hypergeometric sequences; orthogonal polynomials; q-analogues.]

Linear functional system (+ initial conditions):

$$z^2 J_n''(z) + z J_n'(z) + (z^2 - n^2) J_n(z) = 0, \quad z J_n'(z) + z J_{n+1}(z) - n J_n(z) = 0, \\ z J_{n+2}(z) - 2(n+1) J_{n+1}(z) + z J_n(z) = 0.$$

Vector space closed under $D_z$ and $S_n$, here **finite-dimensional**:

$$V = C(n, z) J_n(z) \oplus C(n, z) J_{n+1}(z) = C(n, z) J_n(z) \oplus C(n, z) J'_n(z).$$
$\partial_i = D_i$ or $S_i$

$t$ is $\partial$-finite w.r.t. the operator algebra
$$ \mathbb{K}(x_1, \dots, x_m)\langle\partial_1, \dots, \partial_m\rangle $$

$\Uparrow$

the $\partial_1^{\alpha_1} \dots \partial_m^{\alpha_m} t$'s span a
finite-dimensional $\mathbb{K}(x_1, \dots, x_m)$-vector space:

$$ \dim_{\mathbb{K}(x_1, \dots, x_m)} \left( \mathbb{K}(x_1, \dots, x_m) \langle \partial_1, \dots, \partial_m \rangle t \right) < +\infty $$

$t$ is described by
higher-order linear functional equations.

Algorithmic closures under $+$, $\times$, the $\partial_i$'s, integration, summation
$\Rightarrow$ **simplification** and **zero test** of $\partial$-finite expressions.
Extended Gosper Decision Algorithm

ALGORITHM: $T = \textbf{Indefinite}(t, (b_i)_{i=1,...,d}, A)$.
INPUT: 
    &nbsp;&nbsp;a $\partial$-finite term $t \in V = \bigoplus_{i=1}^d \mathbb{K}(x) b_i$, 
    &nbsp;&nbsp;an operator algebra $A = \mathbb{K}(x)\langle\partial\rangle$, 
    &nbsp;&nbsp;the action of $A$ on $V$.
OUTPUT: $T \in V$ such that $\partial T = t$; or $\nparallel$.

① let $T = \phi_1 b_1 + \dots + \phi_d b_d$ for **undetermined coefficients** $\phi_i \in \mathbb{K}(x)$;

② extract the coefficients of $\partial T - t$ in the $b_i$'s to obtain a **first-order functional system** in the $\phi_i$'s;

③ solve for **rational solutions** (uncoupling + Abramov's decision algorithms);

④ if solvable return $T$; otherwise return $\nparallel$.
Example of Indefinite $\partial$-Finite Summation

$$ \text{Input:} \quad \left\{ \begin{array}{l} \displaystyle \sum_{j=1}^{k} t_j \quad \text{for } t_k = \binom{k}{p} H_k, \quad H_k = 1 + \frac{1}{2} + \cdots + \frac{1}{k}, \\ \phantom{\text{Input:}} \quad (\cdots) t_{k+2} + (\cdots) t_{k+1} + (\cdots) t_k = 0. \end{array} \right. $$

$$ \text{Algorithmic reformulation:} \quad A = Q(p,k)\langle S_k \rangle, \quad T = \phi_0 t_k + \phi_1 t_{k+1}. $$
$$ \begin{array}{l} (k+2-p) \phi_0(k+1) + (2k+3) \phi_1(k+1) - (k+2-p) \phi_1(k) = 0, \\ (k+2-p)(k+1-p) \phi_0(k) + (k+1)^2 \phi_1(k+1) = \\ \quad - (k+2-p)(k+1-p). \end{array} $$
$$ \longrightarrow \quad (\cdots) \phi_1(k+2) + (\cdots) \phi_1(k+1) + (\cdots) \phi_1(k) = (\cdots). $$

$$ \text{Output:} \quad \left\{ \begin{array}{l} \phi_0(k) = \frac{(k-p)(k+p+2)}{(p+1)^2}, \quad \phi_1(k) = -\frac{(k-p)(k-p+1)}{(p+1)^2}, \\ T = \sum_k t_k \delta k = \binom{k}{p} \frac{k-p}{(p+1)^2} ((p+1)H_k - 1). \end{array} \right. $$
Example of Indefinite $\partial$-Finite Integration

Input: $$ \begin{cases} \int \mathrm{Ci}(z) \, dz & \text{for } t(z) = \mathrm{Ci}(z) = \int_0^z \frac{\cos(t) - 1}{t} \, dt, \\ (\cdots) \quad t'''(z) + (\cdots) \quad t''(z) + (\cdots) \quad t'(z) = 0. \end{cases} $$

Algorithmic reformulation: $A = Q(z)\langle D_z\rangle$, $T = \phi_0 t + \phi_1 t' + \phi_2 t''$.

z$\phi_1 + z\phi'_2 - 2\phi_2 = 0,
z^2\phi_0 + z^2\phi'_1 - z\phi_1 - z\phi'_2 + (2-z^2)\phi_2 = 0,
\phi'_0 = 0.
\rightarrow z^3\phi'''_2 - 2z^2\phi''_2 + (z^3+4z)\phi'_2 - 4\phi_2 = 0.

Output: $$ \begin{cases} \phi_0(z) = z, & \phi_1(z) = 1, & \phi_2(z) = z, \\ T = \int \mathrm{Ci}(z) \, dz = z \mathrm{Ci}(z) - \sin(z). \end{cases} $$
Extended Zeilberger (a.k.a. Chyzak's) Algorithm

ALGORITHM: (P, Q) = **Definite**($u$, ($b_i$)$_{i=1,...,d}$, A).

INPUT: 
    { a $\partial$-finite term $u$ w.r.t. $A = \mathbb{K}(x,y)\langle\partial_{x}, \partial_{y}\rangle$, 
    a finite $\mathbb{K}(x,y)$-basis ($b_i$)$_{i=1,...,d}$ of $Au$.
OUTPUT: 
    { $P \in \mathbb{K}(x,y)\langle\partial_{x}\rangle$, 
    $Q \in A$ such that $Pu = \partial_{y}Qu$, resp. $Pu = (\partial_{y} - 1)Qu$.

For increasing values of $r$:

① let $P = \sum_{i=0}^{r} \eta_i \partial_x^i$ and $t = Pu$ for **undetermined coefficients** $\eta_i(x)$;

② let $(T, (\eta_i)) = \textbf{ParamIndefinite}(t, (b_i), A, \{\eta_0, \dots, \eta_r\})$.

③ if $T \neq \emptyset$ return $(P, Q)$ for $Qu = T$.
A $\partial$-Finite Integral: $\frac{2}{\pi} \int_{0}^{1} \frac{\cos(zt)}{\sqrt{1-t^2}} dt = J_0(z)$

$$A = Q(z,t)\langle D_z, D_t \rangle, f = \frac{\cos(zt)}{\sqrt{1-t^2}} \leftrightarrow \text{basis} = (f, D_z f = -t \frac{\sin(zt)}{\sqrt{1-t^2}}) \\ \left\langle D_z^2 + t^2, \quad t(1-t^2)D_t - (1-t^2)zD_z - t^2 \right\rangle$$

$$P = zD_z^2 + D_z + z, \quad Q = \frac{1-t^2}{t}D_z, \quad P \int_0^1 \frac{\cos(zt)}{\sqrt{1-t^2}} + \left[Q \frac{\cos(zt)}{\sqrt{1-t^2}}\right]_0^1 = 0: \\ (zD_z^2 + D_z + z) \frac{2}{\pi} \int_0^1 \frac{\cos(zt)}{\sqrt{1-t^2}} dt = 0 \quad + \text{ 2 initial conditions.}$$
# A Neumann Addition Theorem $J_0(z)^2 + 2 \sum_{k=1}^{\infty} J_k(z)^2 = 1$

① $A = Q(z, k)\langle D_z, S_k \rangle$, $J_k(z) \leftrightarrow \text{basis} = (J_k(z), D_z J_k(z))$: $$z^2 D_z^2 + z D_z + z^2 - k^2, \quad z S_k + z D_z - k.$$

② By closure, $J_k(z)^2 \leftrightarrow \text{basis} = (J_k(z)^2, S_k J_k(z)^2, D_z J_k(z)^2)$: $$z D_z^2 + (-2k+1) D_z - 2z S_k + 2z, \\ z D_z S_k + z D_z + (2k+2) S_k - 2k, \\ z^2 S_k^2 - 4(k+1)^2 S_k - 2z(k+1) D_z + 4k(k+1) - z^2.$$

③ $P = D_z$, $Q = \frac{k}{z} + \frac{1}{2} D_z$, $P \sum_{k=0}^{\infty} J_k(z)^2 + [Q J_k(z)^2]_{k=0}^{\infty} = 0$:

$$D_z \left( 2 \sum_{k=1}^{\infty} J_k(z)^2 + J_0(z)^2 - 1 \right) = 0 \quad + \text{initial condition at } 0.$$
Chyzak's fast algorithm can be **slow**:

① **uncouple** the system for the $\phi$'s (non-commutative Gauss elim.)

② **algorithmically** bound denominators (Abramov's bound)

③ **algorithmically** bound numerator degrees (indicial equation)

Handles multiple sums/integrals iteratively.

**Always** finds a solution (at least theoretically).

Koutschan's **fast** heuristics

① **don't uncouple!**

② **heuristically** set denominator exponents (in accordance to *Pu*)

③ **heuristically** set numerator degrees (prop. to the denom. degs)

Simultaneous multiple sums/integrals possible, at times faster.

**May fail** to find a solution.
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
# History of Gröbner Bases for Creative Telescoping

* (Galligo, 1985) "Some algorithmic questions on ideals of differential operators"

* (Takayama, 1989) "Gröbner basis and the problem of contiguous relations"

* (Kandri-Rody and Weispfenning, 1990) "Noncommutative Gröbner bases in algebras of solvable type"

* (Takayama, 1990) "Gröbner basis, integration and transcendental functions", "An algorithm of constructing the integral of a module: an infinite dimensional analog of Gröbner basis"

* (Kredel, 1993) "Solvable polynomial rings"

* (Chyzak and Salvy, 1998) "Non-commutative elimination in Ore algebras proves multivariate identities"

* (Oaku and Takayama, 1998) "Algorithms for $D$-modules: restriction, tensor product, localization, and local cohomology groups"

* (Saito, Sturmfels, and Takayama, 2000) "Gröbner deformations of hypergeometric differential equations"
# Crash Course on Gröbner Bases

Generalize Euclidean division and the Euclidean (gcd) algorithm to ideals in polynomial rings $K[x_1, \dots, x_m]$.

1. **Monomial order(ing):** total order $<$ on the monomials, compatible with the product, with minimal element 1

2. **Gröbner basis of an ideal I** w.r.t. $<$: generators matching the stairs of I

$$GB(f_1, f_2, f_3) = (g_1, \dots, g_5)$$

3. **Quotient:** vector basis below the stairs; a ring in the commutative case

4. **Reduction of P modulo I:** unique remainder written on this basis

5. **Elimination:** procedure for computing $I \cap K[x_1, \dots, x_s], s < m$

<figure><img src="image_8.png" /></figure>
# Annihilating Ideals

For an operator algebra $A = \mathbb{K}(x_1, \dots, n_1, \dots)\langle D_1, \dots, S_1, \dots \rangle$:

* left ideal: $annf = \{P \in A | Pf = 0\} \leftrightarrow \text{"all equations on } f$

* left module: $A/annf \simeq Af \leftrightarrow \text{"space of shifted derivatives of } f$

## Calculations modulo annf.

Example of Bessel functions, $J_n(z)$:

$$ \mathrm{ann} J = A (z^2 D_z^2 + z D_z + (z^2 - n^2), z D_z + z S_n - n, z S_n^2 - 2(n+1)S_n + z). $$

$$ V = AJ \simeq A/\mathrm{ann}J $$

$$ (J_n(z), J_{n+1}(z), J'_n(z)) \leftrightarrow (1 + \mathrm{ann}J, S_n + \mathrm{ann}J, D_z + \mathrm{ann}J) $$

Also for $\mathbb{K}[x_1, \dots, n_1, \dots]\langle D_1, \dots, S_1, \dots \rangle$ and intermediate cases.
Buchberger's algorithm extends to left ideals.

Gröbner bases are still finite (noetherianity).

(Galligo, 1985; Takayama, 1989; Kandry-Rody and Weispfenning, 2000; Kredel, 1993)

Direct extensions to Gröbner bases for left modules.

Technical restriction on commutations:

$$ \partial_i x_j = (a_{i,j}x_j + b_{i,j})\partial_i + c_{i,j}(x_1, \dots, x_m) \quad \text{with } a_{i,j} \neq 0. $$

Restriction on orders allowed: $c_{i,j}(x_1, \dots, x_m) < x_j \partial_i$.

Both OK for $\partial = D$ and $\partial = S$, as $Dx = xD + 1$ and $Sx = xS + S$.
# Closures of $\partial$-Finite Functions under $+, \times, \partial$

Finite dimensions make algorithms terminate.

Example: the product $h = T_n(x) \times \frac{e^{-ux}}{\sqrt{1-x^2}}$.

$A = \mathbb{Q}(x, n, u)\langle D_x, S_n, D_u \rangle$, Total degree in $D_x > S_n > D_u$.

A Gröbner basis for $\text{ann}\,f$, $f = T_n(x)$, provides normal forms in $\mathcal{A}f$:

$$D_u, \quad (x^2 - 1)D_x - nS_n + nx, \quad S_n^2 - 2xS_n + 1.$$

A Gröbner basis for $\text{ann}\,f$, $g = \frac{e^{-ux}}{\sqrt{1-x^2}}$, provides normal forms in $\mathcal{A}g$:

$$D_u + x, \quad S_n - 1, \quad (x^2 - 1)D_x + ux^2 + x - u.$$
<figure><img src="image_9.png" /></figure>

$$1 < [D_u] < S_n < [D_x] < D_u^2 < D_u S_n < D_u D_x < [S_n^2] < S_n D_x < D_x^2 < \dots$$

Normal forms in $Af \otimes_{\mathbb{Q}(x,n,u)} Ag$:

$$1 (f \otimes g) = f \otimes g,$$

$$D_u (f \otimes g) = D_u f \otimes g + f \otimes D_u g = -x (f \otimes g),$$

$$S_n (f \otimes g) = S_n f \otimes S_n g = S_n f \otimes g,$$

$$D_x (f \otimes g) = D_x f \otimes g + f \otimes D_x g$$

$$= (x^2 - 1)^{-1} (n S_n f \otimes g - (ux^2 + (n+1)x - u) (f \otimes g)),$$

$$S_n^2 (f \otimes g) = S_n^2 f \otimes S_n^2 g = 2x S_n f \otimes g - f \otimes g.$$

Gröbner basis computed for $f \otimes g$:

$$[D_u] + x, \quad (x^2 - 1)[D_x] - nS_n + ux^2 + (n+1)x - u, \quad [S_n^2] - 2xS_n + 1.$$
An Integral: $$ \int_{-1}^{+1} T_n(x) \frac{e^{-ux}}{\sqrt{1-x^2}} dx = \pi (-1)^n I_n(u) $$

Now, in $Q[n, u, x] \langle D_x, S_n, D_u \rangle$, heuristically eliminating $x$ by the order
$$ x \gg D_x > S_n > D_u > n > u $$

yields another Gröbner basis:

$$ \underbrace{S_n^2 + 2S_n D_u + 1, \quad D_x (D_u^2 - 1) - nS_n + uD_u^2 - (n-1)D_u - u, \quad x + D_u}_{\text{non-trivial by chance!}} $$

The integral $H = \int_{-1}^{+1} h \, dx$ satisfies

$$ (S_n^2 + 2S_n D_u + 1) H = 0, $$

$$ (nS_n - uD_u^2 + (n-1)D_u + u) H = [(D_u^2 - 1)h]_{x=-1}^{x=+1} = 0. $$
# Takayama's Approach

(Chyzak and Salvy's variant)

Optimisation dedicated to integrals/sums over natural boundaries

Compute the *P*'s such that, for some *Q*,

$$P(n, u, D_x, S_n, D_u) - D_x Q(x, n, u, D_x, S_n, D_u) \in \text{ann} h$$

without computing the *Q*'s.

Idea: View ideal $\text{ann} h$ as a module

$$\sum_{i=1}^{\ell} Q[n, u, x] \langle D_x, S_n, D_u \rangle g_i = \lim_{N \to \infty} \sum_{i=1}^{\ell} \sum_{j=0}^{N} Q[n, u] \langle D_x, S_n, D_u \rangle x^j g_i.$$

Adapts to mixed simultaneous integrations/summations.
## Example: Same Integral

• For $N = 3$:

$$ \begin{aligned} & 1D_u + x, \quad xD_u + x^2, \quad x^2D_u + x^3, \\ & 1(-D_x - nS_n - u) + x(n+1) + x^2(u + D_x), \quad x(-D_x - nS_n - u) + x^2(n+1) + x^3(u + D_x), \\ & 1(S_n^2 + 1) - x2S_n, \quad x(S_n^2 + 1) - x^22S_n, \quad x^2(S_n^2 + 1) - x^32S_n. \end{aligned} $$

• Moding out $D_x$ on the left, by $p(x)D_x = D_x p(x) - p'(x)$, yields

$$ \begin{aligned} & D_u 1 + x, \quad D_u x + x^2, \quad D_u x^2 + x^3, \\ & (-nS_n - u)1 + (n-1)x + ux^2, \quad 1 + (-nS_n - u)x + (n-2)x^2 + ux^3, \\ & (S_n^2 + 1)1 - 2S_n x, \quad (S_n^2 + 1)x - 2S_n x^2, \quad (S_n^2 + 1)x^2 - 2S_n x^3. \end{aligned} $$

• Gröbner basis for $x \gg S_n > D_u$:

$$ \begin{aligned} & \boxed{(-u - nS_n - (n-1)D_u + uD_u^2)1}, \quad \boxed{(S_n^2 + 1 + 2D_uS_n)1}, \\ & D_u 1 + x, \quad \boxed{(-u - nS_n - (n-1)D_u)1 + ux^2}, \\ & (unS_nD_u + n(n-2)S_n - u + (u^2 + n^2 - 3n + 2)D_u + nu)1 + u^2x^3. \end{aligned} $$
$M_k(I) := \langle m : m \text{ is below the stairs and of total degree } \leqslant s \rangle$

**Theorem (Hilbert)**

For any $I$, there is an integer $\delta(I)$ such that $\#M_k(I) = \Theta(s^{\delta(I)})$.

* $\delta(I)$ is the (Hilbert) dimension of $I$.

* Finite measure of infinite-dimensional vector-spaces.

* Also measures capacity for elimination.

* Can be obtained by a Gröbner-basis calculation.

* $I \subset J \Rightarrow \delta(I) \geq \delta(J)$

Caution!
dimension in $\mathbb{K}(\underline{x})\langle\underline{\mathcal{D}}\rangle \neq$ dimension in $\mathbb{K}[\underline{x}]\langle\underline{\mathcal{D}}\rangle$
Examples of Dimensions in $\mathbb{K}(\underline{x})\langle\partial\rangle$

Binomial coefficients $\binom{n}{k}$ w.r.t. $S_n, S_k$;
Hypergeometric sequences:

<figure><img src="image_10.png" /></figure>

Stirling nbs w.r.t. $S_n, S_k$:

<figure><img src="image_11.png" /></figure>

Bessel $J_v(x)$ w.r.t. $S_v, D_x$;
Orthogonal polys w.r.t. $S_n, D_x$:

<figure><img src="image_12.png" /></figure>

Abel-type w.r.t. $S_m, S_k, S_r, S_s$, $h(m, k) (k+r)^k (m-k+s)^{m-k} \frac{r}{k+r}$:

<figure><img src="image_13.png" /></figure>
Sample Dimensions in $K(\underline{x})\langle\underline{\partial}\rangle$ vs in $K[\underline{x}]\langle\underline{\partial}\rangle$

Experimentation “shows”:

Differential case

<table><thead><tr><th>algebra \ function</th><th>1</th><th>exp(x + y)</th><th>Γ(x + y)</th><th>Γ(x) Γ(y)</th></tr></thead><tbody><tr><td>C(x, y)⟨D<sub>x</sub>, D<sub>y</sub>⟩</td><td>0</td><td>0</td><td>1</td><td>2</td></tr><tr><td>C[x, y]⟨D<sub>x</sub>, D<sub>y</sub>⟩</td><td>2</td><td>2</td><td>3</td><td>4</td></tr></tbody></table>

Recurrence case

<table><thead><tr><th>algebra \ function</th><th>1</th><th>1/nk</th><th>1/(1 + nk)</th><th>(n/k)</th><th>{n/k}</th></tr></thead><tbody><tr><td>C(n, k)⟨S<sub>n</sub>, S<sub>k</sub>⟩</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><td>C[n, k]⟨S<sub>n</sub>, S<sub>k</sub>⟩</td><td>2</td><td>2</td><td>3</td><td>2</td><td>3</td></tr></tbody></table>
# Elimination for Holonomic Functions

In the differential setting: $D_i x_j = x_j D_i + \delta_{i,j}$.

## Holonomic function

a function of $x_1, \dots, x_m$ is **holonomic**

<figure><img src="image_14.png" /></figure>

the $x_1^{\alpha_1} \dots x_m^{\alpha_m} D_1^{\beta_1} \dots D_m^{\beta_m} f$ for $\alpha_1 + \dots + \alpha_m + \beta_1 + \dots + \beta_m \le N$
span a **K-vector** space of dimension $\mathcal{O}(N^m)$.

## Elimination lemma

For a holonomic function $f$ and **any choice**

$$ \{u_1, \dots, u_{m+1}\} \subset \{x_1, \dots, x_m, D_1, \dots, D_m\}, $$

there is a **non-zero** $P(u_1, \dots, u_{m+1})$ such that $Pf = 0$.

**Corollary 1:** A holonomic function is D-finite.

**Corollary 2:** Creative telescoping succeeds for holonomic functions.
# D-Finite Functions are Holonomic

Finite-dimensional confinement of derivatives:

$$f \in V = \bigoplus_{j=1}^{d} \mathbb{K}(x_1, \dots, x_m) b_j, \quad D_s b_i = \sum_{j=1}^{d} \frac{a_{s,i,j}}{w} b_j, \quad a_{s,i,j}, w \in \mathbb{K}[x_1, \dots, x_m]$$

Action of $x$'s and $D$'s on degrees: for $\mu = 1 + \max \{ \deg w, \deg a_{s,i,j} \}$,

$$D_s \left( \frac{p}{w^N} b_i \right) = \frac{D_s p}{w^N} b_i - N \frac{p}{w^{N+1}} D_s w b_i + \sum_{j=1}^{d} \frac{a_{s,i,j} p}{w^{N+1}} b_j, \quad x_s \left( \frac{p}{w^N} b_i \right) = \frac{x_s w p}{w^{N+1}} \\ \frac{(\deg \le \alpha)}{w^N} \rightarrow \frac{(\deg \le \alpha + \mu)}{w^{N+1}}$$

Dimension analysis: for $\alpha_1 + \dots + \alpha_m + \beta_1 + \dots + \beta_m \le N$,

$$x_1^{\alpha_1} \dots x_m^{\alpha_m} D_1^{\beta_1} \dots D_m^{\beta_m} f = \frac{(\deg \le \mu N)}{w^N} \rightarrow \dim \left( \frac{\mu N + m}{m} \right) \approx \Theta(N^m).$$
# Other Techniques by Homogenisation

For $F(x) = \int_a^b f(x, y) dy$. Common themes:

* reduce by weights $-1$ for $y$, $+1$ for $\partial_y$;

* “homogenise” to recover termination.

## Saito, Surmfels, Takayama

* Homogenise the algebra by $\partial_y y = y \partial_y + h^2$.

* Compute Gröbner basis for homogenised generators of $annf$, then dehomogenise the output.

## Oaku's "homogenisation" for the V-filtration

* Add a variable $v$ to the algebra.

* Mark monomials in generators by $v$ raised to the V-degree.

* Compute Gröbner basis that eliminates $v$, then set $v = 1$.
# Weyl Closure

A problem: $f = p^{-1}$ for $p = y^2 - y + x$ (Chyzak and Salvy, 1998)

$$g_1 = pD_x + 1 \quad \text{and} \quad g_2 = pD_y + 2y - 1$$

In $A = Q(x, y)\langle D_x, D_y \rangle$: $\text{ann}_A f = Ag_1 + Ag_2$.

In $W = Q[x, y]\langle D_x, D_y \rangle$: $Wg_1 + Wg_2$ has Hilbert dimension 3 (!) $\rightarrow$ elimination of $y$ from $\{g_1, g_2\}$ fails

$$g_3 = pD_xD_y + 2D_y \in W \cap \text{ann}_A f$$

$Wg_1 + Wg_2 + Wg_3$ has Hilbert dimension 2 $\rightarrow$ elimination of $y$ from $\{g_1, g_2, g_3\}$ finds $(1 - 4x) D_x^2 - 6D_x - D_y^2$

Problem: GB, Takayama, etc., require $\text{ann}_W f$ as inputs, not $\text{ann}_A f$.

Completion of $\text{ann}_A f$ to $\text{ann}_W f$ by Tsai's Weyl-closure algorithms (2000, 2002)

(Differential case only.)
# Contents

1. Introduction: Early Days and Examples

2. Fasenmyer's (a.k.a. "k-Free") Ansatz

3. Lipshitz's Diagonals

4. Zeilberger's Ansatz

5. Gröbner Bases: Closures and Elimination

6. **Beyond Holonomy**

7. Termination, Bounds, Complexity

8. Conclusions
# Examples of Non-∂-Finite Terms

* Stirling numbers of the second kind, $\binom{n}{k}$ = numbers of partitions of a set of $n$ objects into $k$ non-empty subsets:

$$ \binom{n+1}{k} = k \binom{n}{k} + \binom{n}{k-1} \quad (k > 0) $$

with initial conditions $\binom{0}{0} = 1$ and $\binom{n}{0} = \binom{n}{n} = 0$, $(n > 0)$.

* Hurwitz' zeta function, $\zeta(s, x) = \sum_{n=0}^{\infty} \frac{1}{(x+n)^s}$:

$$ \frac{\partial \zeta}{\partial x} = -s \zeta(s+1, x) $$

with initial conditions $\zeta(0, x) = 1/2 - x$ and $\zeta(s, 1) = \zeta(s)$ (Riemann's zeta function).

$$ \operatorname{ann} \binom{n}{k} = A_{n,k} (S_n S_k - (k+1)S_k - 1), \quad \operatorname{ann} \zeta = A_{x,s} (D_x + sS_s). $$
# History for Algorithms in Positive Dimension

* (Majewicz, 1996) "WZ-style certification and Sister Celine's technique for Abel-type sums"

* (Kauers, 2007) "Summation algorithms for Stirling number identities"

* (Chen, Sun, 2009) "Extended Zeilberger's algorithm for identities on Bernoulli and Euler polynomials"

* (Chyzak, Kauers, Salvy, 2009) "A non-holonomic systems approach to special function identities"
Algebraic Closure Properties in Positive Dimension

<figure><img src="image_15.png" /></figure>

Proposition

$\delta$ of sum $\le$ max. of $\delta$'s, $\delta$ of product $\le$ sum of $\delta$'s, $\delta$ of der. $\le \delta$.

Algorithm (for a product $fg$): for a graded ordering,

For $s = 0, 1, 2, \dots$, until $\delta(I) \le \text{bound}$:

for each $|\alpha| \le s$, reduce $\partial^\alpha(fg)$ to a sum $\sum u_{\alpha, \beta, \gamma}(x) \partial^\beta f \partial^\gamma g$

over $\beta \in M_s(\text{ann } f)$, $\gamma \in M_s(\text{ann } g)$ (M_s: "monomials under the stairs")

search for $Q(x)$-linear relations, set $I$ to the ideal they generate
  return $I$, a subideal of $\text{ann } fg$

Example (Stirling numbers of the second kind): $\binom{n}{k}$, $\delta(I) = 1$,

$$
\text{1st-order rec. } \xrightarrow{s=3} \binom{n}{k} \binom{m}{k}, \delta(I) = 2, \text{ 2nd-order rec.}
$$
# A Slightly Different View of Fasenmyer's Technique

## Rediscovering Pascal's Triangle Rule

Reduce all monomials of degree $\le s = 2$:

<figure><img src="image_16.png" /></figure>

$$ 
\begin{gathered}
1 \to 1, \quad S_n \to \frac{n+1}{n+1-k} 1, \quad S_k \to \frac{n-k}{k+1} 1 \\
S_n^2 \to \frac{(n+2)(n+1)}{(n+2-k)(n+1-k)} 1, \quad S_k^2 \to \frac{(n-k-1)(n-k)}{(k+2)(k+1)} 1, \quad S_n S_k \to \frac{n+1}{k+1} 1.
\end{gathered}
$$

Common denominator: $C_2 = (k+1)(k+2)(n+1-k)(n+2-k)$.

$$ C_2, C_2S_n, C_2S_k, C_2S_n^2, C_2S_k^2, C_2S_nS_k \text{ confined in} \\ \langle 1, k, k^2, k^3, k^4 \rangle \text{ over } \mathbb{K}(n) \\ \to C_2(S_nS_k - S_k - 1) \in \text{ann}\left(\begin{pmatrix} n \\ k \end{pmatrix}\right). $$

$\deg C_s = O(s) \Rightarrow$ this had to happen for some s.
More Examples from this Perspective

Proper hypergeometric terms: essentially the same situation.

$\frac{1}{n^2 + k^2}$: confinement in a space of dimension $O(s^2)$, no elimination of $k$ succeeds.

$f = \frac{a(x, y_1, \dots, y_r)}{b(x, y_1, \dots, y_r)}$: $C_s = b^s$, confinement in a space of dimension $O(s^r)$ over $\mathbb{K}(x)$, elimination of $y_1, \dots, y_r$ has to succeed. Base case of proof that D-finite functions are holonomic.
# Adding a Left Part and a Right Part

## Specification of a Creative-Telescoping Algorithm

Input: generators of (a subideal of) $\text{ann}f$

Output: all $(A, B)$ such that:

* $A + \partial_y B \in \text{ann}f$, resp. $A + (\partial_y - 1)B \in \text{ann}f$,

* $A$ is free of $y$ and $\partial_y$.

## Definition (telescoping ideal of $I$ w.r.t. $y$)

$$T_y(I) := (I + \partial_y S_{x,y}) \cap S_x \quad \text{where}$$

$$S_{x,y} := \mathbb{K}(x,y)\langle\partial_x, \partial_y\rangle \text{ and } S_x := \mathbb{K}(x)\langle\partial_x\rangle.$$

When $I = S_{x,y}G_1 + \dots + S_{x,y}G_\ell$, this involves

$$(S_{x,y}G_1 + \dots + S_{x,y}G_\ell) + \partial_y S_{x,y}.$$
Polynomial Growth and Creative Telescoping when
$\delta > 0$

Definition (polynomial growth *p*)

An ideal has polynomial growth *p* if there exists a sequence of
polynomials P_s(x, y), s.t. if |a| + b ≤ s,

$P_s \tilde{\partial}_{x_1}^{a_1} \dots \tilde{\partial}_{x_k}^{a_k} \tilde{\partial}_y^b$ reduces to polys of degree $O(s^p)$ in $y$.

Theorem (Chyzak, Kauers & Salvy, 2009)

$$
\delta(T_y(I)) \leq \max(\delta(I) + p - 1, 0).
$$

Proof: $P_s \tilde{\partial}_x^a \tilde{\partial}_y^b - \sum_{\beta \in M_s(I)} (\text{deg. in } y \le O(s^p)) \partial^\beta \in I$
⇒ any choice of $(\delta(I) + p - 1) + 1$ generators among $\{\partial_{x_1}, \dots, \partial_{x_k}, \partial_y\}$
is algebraically dependent modulo $I$.

Corollary (sufficient condition for creative telescoping)

$$
\delta(I) + p - 1 < k \Rightarrow \text{identities exist for the sum/int. w.r.t. y.}
$$
# Examples with Polynomial Growth $p = 1$

* Proper hypergeometric (Wilf & Zeilberger, 1992):

$$Q(n,k)\zeta^k \frac{\prod_{i=1}^{u} (a_i n + b_i k + c_i)!}{\prod_{i=1}^{v} (u_i n + v_i k + w_i)!}$$

Q polynomial, $a_i, b_i, u_i, v_i$ integers.

* Differential D-finite (special case of holonomy).

* Stirling: $\delta = 1 \to$ for $\ge 3$ vars, e.g., Frobenius' id.:

$$\sum_{k=0}^{n} (-1)^{m-k} k! \binom{n-k}{m-k} \binom{n+1}{k+1} = \binom{n}{m}.$$

* Abel type: $\delta = 2 \to$ for $\ge 4$ vars, e.g., Abel's id.:

$$\sum_{k=0}^{n} \binom{n}{k} i(k+i)^{k-1} (n-k+j)^{n-k} = (n+i+j)^n.$$

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>
# Algorithm I: Fasenmyer's Style

Polynomial growth + linear algebra $\rightarrow J := I \cap S_x[\partial_y]$.

## Algorithm

For increasing values of $s$, until $\delta(J) \le$ bound:

① Reduce all $\partial_x^a \partial_y^b$ with $a + b \le s$;

② Normalize to a common denominator;

③ Set up a linear system to cancel the positive powers of $y$;

④ If a non-zero solution is found, it has the form $A(x, \partial_x) + \partial_y B(y, \partial_x, \partial_y)$; return it.

This computes $A$ in

$$ (J + \partial_y S_x[\partial_y]) \cap S_x, \quad \text{not in} \quad T_t(I) := (I + \partial_y S_{x,y}) \cap S_x. $$

$$ S_x = \mathbb{K}(x)\langle\partial_x\rangle \subset S_x[\partial_y] \subset S_{x,y} := \mathbb{K}(x,y)\langle\partial_x, \partial_y\rangle. $$
Algorithm II. Zeilberger's Style Extended to Dim > 0

Compute A in $T_t(I) := (I + \partial_y S_{x,y}) \cap S_x \leftrightarrow$ faster, more precise.

For $s = 0, 1, 2, \dots$, until $\delta(J) \le \text{bound}$:

set $A := \sum_{|\alpha| \le s} \eta_\alpha \partial^\alpha$

for undetermined coefficients $\eta_\alpha(y) \in \mathbb{K}(x)$

set $B := \sum_{\beta \in M_s(I)} \phi_\beta(y) \partial^\beta$

for undetermined coefficients $\phi_\beta(y) \in \mathbb{K}(x, y)$

reduce $A - \partial_y B$

onto the basis $M_{s+1}(I)$

extract coefficients to form a linear system of first order w.r.t. $\partial_y$

solve and set $J$ to the ideal of the $A$'s return the pairs $(A, B)$

<figure><img src="image_20.png" /></figure>
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
# History for Termination, Bounds, and Complexity

* (Wilf and Zeilberger, 1992) "An algorithmic proof theory for hypergeometric (ordinary and 'q') multisum/integral identities"

* (Yen, 1996, 1997) "A two-line algorithm for proving terminating hypergeometric identities", "A two-line algorithm for proving q-hypergeometric identities"

* (Abramov, 2002, 2003) "Applicability of Zeilberger's algorithm to hypergeometric terms", "When does Zeilberger's algorithm succeed?"

* (Zhang, 2003) "A new elementary algorithm for proving q-hypergeometric identities"

* (Apagodu and Zeilberger, 2005, 2006) "Sharp upper bounds for the orders of the recurrences output by the Zeilberger and q-Zeilberger algorithms", "Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory"

* (Bostan, Cluzeau, and Salvy, 2005) "Fast algorithms for polynomial solutions of linear differential equations"

* (Bostan, Chyzak, Salvy, and Cluzeau, 2006) "Low complexity algorithms for linear recurrences"

* (Guo, Hou, Sun, 2008) "Proving hypergeometric identities by numerical verifications"

* (Bostan, Chen, Chyzak, and Li, 2010) "Complexity of creative telescoping for bivariate rational functions"

* (Chen, 2011) "Some applications of differential-difference algebra to creative telescoping"

* (Chen, Chyzak, Feng, and Li) "On the existence of telescopers for hyperexponential-hypergeometric sequences" (in preparation)
For proper hypergeometric terms $P(n, k) \zeta^n \bar{\zeta}^k \prod_{\ell=1}^{L} \Gamma(a_\ell n + b_\ell k + c_\ell)^{\epsilon_\ell}$:

$$r \le \sum_{\ell=1}^{L} |b_\ell| \qquad (\text{Wilf and Zeilberger, 1992})$$

$$r \le \sum_{\ell=1, \epsilon=+1}^{L} b_{\ell}^{+} + \sum_{\ell=1, \epsilon=-1}^{L} (-b_{\ell})^{+} + \left( - \sum_{\ell=1, \epsilon=\pm 1}^{L} \epsilon b_{\ell} \right)^{+} \quad (\text{Yen, 1993})$$

For hyperexponential terms $p(x, y) \exp \left( \frac{a(x, y)}{b(x, y)} \right) \prod_{s \in S} s(x, y)^{\alpha_s}$:

(Apagodu and Zeilberger, 2006), if $a \ne 0$, $\alpha_s \notin \bar{\mathbb{Q}}$:

$$r \le \deg_y(b) + \max(\deg_y(a), \deg_y(b)) + \left( \sum_{s \in S} \deg_y(s) \right) - 1.$$
# Proving Summation Identities by Evaluations

**Linear-algebraic**
system to encode
output recurrence

**Bounds on orders,**
**degrees, and heights**
(Cramer's rules)

**Bound on maximal**
**integer singularity**
of recurrence

(Yen, 1996)

To prove $\sum_{k=\infty}^{\infty} P(n,k) \zeta^n \bar{\zeta}^k \prod_{\ell=1}^{L} \Gamma(a_\ell n + b_\ell k + c_\ell)^{\epsilon_\ell} = 1$ for all $n$, it is sufficient to verify it at $n = 0, \dots, N$, where $N = ((3\sigma)^{3\beta} \delta^5 h)^\beta + 1$.

$$ 
\begin{align*}
\lambda_+ &= \#\{ \ell \mid \epsilon_\ell = +1 \}, & \lambda_- &= \#\{ \ell \mid \epsilon_\ell = -1 \}, \\
\sigma &= \max(\lambda_+, \lambda_-) \max \{ |a_\ell|, |b_\ell|, |c_\ell| \}, \\
\delta &= 1 + \max(\deg_n P, \deg_k P), & \beta &= (\delta + 1) (2\sigma)^3, \\
h &= \text{height}(P) = \text{maximal absolute value of coeff.}
\end{align*}
$$

**Proof:** For the linear-algebra formulation, bound Fasenmyer's ansatz by Wilf and Zeilberger, and translate it to Zeilberger's ansatz.
# Proving Summation Identities by Fewer Evaluations

(Guo, Hou, and Sun, 2008)

To reduce $N$:

* directly use Zeilberger's ansatz with tighter order bound and explicit denominator bound;

* perform explicit majorisations on the concrete matrix, rather than use a generic bound;

* simplify the matrix by algorithmic manipulations.

→ *new* $N$ given by a procedure, not a formula.

Examples:

<table><thead><tr><th></th><th>Σ<sub>k</sub> (n/k) = 2<sup>n</sup></th><th>Σ<sub>k</sub> (n/k)<sup>2</sup> = (2n/n)</th></tr></thead><tbody><tr><td>Yen</td><td>10<sup>11</sup></td><td>10<sup>115</sup></td></tr><tr><td>Guo, Hou, Sun</td><td>4</td><td>12091</td></tr></tbody></table>
# Definite Integration of Bivariate Rational Functions

First step toward complexity analysis of creative telescoping

$$f \in \mathbb{K}(x, y) \text{ with } \deg_x = \deg_y = \delta \longrightarrow L(x, D_x)f = D_y g \text{ for } g \in \mathbb{K}(x, y)$$

(Bostan, Chen, Chyzak, Li, 2010): Complexity is polynomial!

New algorithm based on Hermite reduction + Analyses:

<table><thead><tr><th></th><th>Method</th><th>deg<sub>D</sub>, L</th><th>deg<sub>x</sub>, L</th><th>deg<sub>x</sub>, g</th><th>deg<sub>y</sub>, g</th><th>Complexity</th></tr></thead><tbody><tr><td>Minimal</td><td>Hermite</td><td>&le; &delta;</td><td>O(&delta;<sup>3</sup>)</td><td>O(&delta;<sup>3</sup>)</td><td>O(&delta;<sup>2</sup>)</td><td>O(&delta;<sup>&omega;+4</sup>) L.V.</td></tr><tr><td>Telescoper</td><td>A. &amp; Z.</td><td>&le; &delta;</td><td>O(&delta;<sup>3</sup>)</td><td>O(&delta;<sup>3</sup>)</td><td>O(&delta;<sup>2</sup>)</td><td>O(&delta;<sup>2&omega;+3</sup>) L.V.</td></tr><tr><td>Nonminimal</td><td>Lipshitz</td><td>&le; 6(&delta; + 1)<sup>2</sup></td><td>O(&delta;<sup>2</sup>)</td><td>O(&delta;<sup>3</sup>)</td><td>O(&delta;<sup>3</sup>)</td><td>O(&delta;<sup>6&omega;</sup>) det.</td></tr><tr><td>Telescoper</td><td>Cubic</td><td>&le; 6&delta;</td><td>O(&delta;<sup>2</sup>)</td><td>O(&delta;<sup>2</sup>)</td><td>O(&delta;<sup>2</sup>)</td><td>O(&delta;<sup>4&omega;</sup>) det.</td></tr></tbody></table>

Hermite-based: matrix size = $\delta$, entries of degree $\delta^3$.

A. & Z.: matrix size = $\delta^2$, entries of degree $\delta^2$.

Lipshitz: total-degree filtration at degree = $\delta \rightarrow$ matrix size = $\delta^6$.

Cubic: bi-filtration at (degree, order) = ($\delta^2$, $\delta$) $\rightarrow$ matrix size = $\delta^4$.
# Hermite Reduction for Indefinite Integration in $K(y)$

One step, given a Bézout relation $1 = sq' + tq$ for irreducible $q$:

$$ \int \frac{p}{q^i} = \int \frac{-sp}{j-1} \cdot \frac{-(j-1)q'}{q^i} + \int \frac{tp}{q^{i-1}} = \frac{-sp}{(j-1)q^{i-1}} + \int \frac{tp + (sp)'/(j-1)}{q^{i-1}} $$

By iterating:

$$ \int \sum_{j=1}^{\nu} \frac{p_j}{q^j} = \sum_{j=1}^{\nu-1} \frac{a_j}{q^j} + \int \frac{u}{q} \quad \text{where } \deg u < \deg q. $$

Viewed differently:

$$ \sum_{j=1}^{\nu} \frac{p_j}{q^j} = \left( \sum_{j=1}^{\nu-1} \frac{a_j}{q^j} \right)' + \frac{u}{q} \quad \text{where } \deg u < \deg q. $$

Complexity for general $\frac{p}{q}$: $\tilde{O}(\max(\deg p, \deg q))$.
# An Algorithm for Definite Integration in $K(x, y)$

Given $f = \frac{p}{q} \in K(x)(y)$, to compute $\int_a^b f(x, y) dy$:

$$f(x,y) = D_y \left( \dots \right) + \frac{u_0}{q^*}, \quad \dots, \quad D_x^r f(x,y) = D_y \left( \dots \right) + \frac{u_r}{q^*}$$

1. $q^* = q_1 \cdots q_m$ is the squarefree part of $q = q_1 q_2 \cdots q_m$;

where:

2. $\deg_y u_i < \deg_y q^*$ for $0 \le i \le r$.

Linear algebra over $K(x)$: for some $r \le \deg_y q^*$,

$$\sum_{i=0}^{r} \eta_i(x) D_x^i f(x, y) = D_y \left( \dots \right) + \frac{0}{q^*}.$$

Matrix size ruled by $\deg_y u$, not by $\deg_y g$!

Complexity:

* bivariate Hermite by evaluation/interpolation;

* linear algebra over $K[x]$ by Storjohann-Villard.
# Contents

① Introduction: Early Days and Examples

② Fasenmyer's (a.k.a. "k-Free") Ansatz

③ Lipshitz's Diagonals

④ Zeilberger's Ansatz

⑤ Gröbner Bases: Closures and Elimination

⑥ Beyond Holonomy

⑦ Termination, Bounds, Complexity

⑧ Conclusions
$$ \sum_{k=0}^{n} (-1)^k \binom{n}{k} \binom{pk}{n} = (-p)^n \quad \text{(order } p-1 \text{ instead of 1)}, $$

$$ \sum_{k=0}^{n} \frac{1}{pk+1} \binom{pk+1}{k} \binom{p(n-k)}{n-k} = \binom{pn+1}{n} $$

(order 2 instead of 1 for $p = 3$).

This non-minimality is not understood well.

$$ \eta_r(n) u_{n+r,k} + \dots + \eta_0(n) u_{n,k} = v_{n,k+1} - v_{n,k} $$

The existence of $v$ constrains $d$!

This relation does not take the summation range into account!
# An Integral Not Amenable to Creative Telescoping?

Borrowed from (Borwein, Straub, Wan, Zudilin, 2011).

$$F(x) = \int_{0}^{\infty} \underbrace{xt J_{0}(xt) J_{0}(t)^{4}}_{=f(x,t)} dt \quad \rightarrow \quad Pf = D_{t}g \quad \text{for } g = Qf.$$

$$P = (x-4)(x-2)(x+2)(x+4)x^3 D_x^3 + 6(x^2-10)x^4 D_x^4 + (7x^4 - 32x^2 + 64)x D_x + (x^2-8)(x^2+8)$$

$$Q = 5x^3t^2 D_x D_t^3 - x^2t^3 D_t^4 - t^{-1}x^2(5x^4t^4 - 60x^2t^4 + 64t^4 - 28t^2 - 4) - 7x^2t^2 D_t^3 \\ + x^2t(10x^2t^2 - 20t^2 - 1)D_t^2 - 5x^3(2x^2t^2 - 12t^2 - 1)D_x D_t \\ + 4x^2(5x^2t^2 - 15t^2 - 1)D_t + 5t^{-1}x^3(2x^2t^2 - 12t^2 - 1)D_x$$

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

$$D_x^i f|_{x=3/2} = \Theta(\cos(3\pi/2 + \pi/4) \sin(t + \pi/4) t^{i-3/2})! \quad \text{No limit of } g \text{ at } \infty!$$

$$\text{For } i > 0, \text{ no limit of } \int_{0}^{T} D_{x}^{i} f|_{x=3/2} dt \text{ at } \infty!$$
# Successful Applications of Creative Telescoping

* *Descendants in heap-ordered trees* (Prodinger, 1996): Zeilberger's algorithm ($2 \times$)

* *Totally symmetric plane partition* (Kauers, Koutschan & Zeilberger, 2011): q-Koutschan ($n \times$)

* Lattice walks confined in a quadrant, in particular *Gessel's conjecture for $\leftarrow, \rightarrow, \downarrow, \uparrow$* (Kauers, Koutschan & Zeilberger, 2009): variant of Takayama for specialisation ($n \leftrightarrow S_n$)

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

All were first proofs!