RISC Report number 23-01

# Refined telescoping algorithms in $\mathrm{R}\mathrm{\Pi\Sigma}$-extensions
to reduce the degrees of the denominators

Carsten Schneider  Johannes Kepler University Linz
Research Institute for Symbolic Computation
A-4040 Linz, Austria<EMAIL_ADDRESS>
###### Abstract.

We present a general framework in the setting of difference ring extensions
that enables one to find improved representations of indefinite nested sums
such that the arising denominators within the summands have reduced degrees.
The underlying (parameterized) telescoping algorithms can be executed in
$\mathrm{R}\mathrm{\Pi\Sigma}$-ring extensions that are built over general
$\Pi\Sigma$-fields. An important application of this toolbox is the
simplification of d’Alembertian and Liouvillian solutions coming from
recurrence relations where the denominators of the arising sums do not factor
nicely.

###### Key words and phrases:

telescoping, difference rings, reduced denominators, nested sums

Supported by the Austrian Science Foundation (FWF) grant P33530.

##  1\. Introduction

Parameterized telescoping, a central paradigm of symbolic summation, can be
introduced in a a _difference ring_ (or _field_) $(\mathbb{A},\sigma)$ as
follows. $\mathbb{A}$ is a ring (or field) in which the summation objects are
modeled, $\sigma:\mathbb{A}\to\mathbb{A}$ is a ring (or field) automorphism
that scopes the shift operator, and
$\mathbb{K}=\text{const}_{\sigma}\mathbb{A}=\\{c\in\mathbb{A}\mid\sigma(c)=c\\}$
is the set of constants which forms a subring (or subfield) of $\mathbb{A}$;
here $\mathbb{K}$ is always a field also called _constant field_. Then we are
interested in the following problem.

Problem PT in $(\mathbb{A},\sigma)$ (with constant field
$\mathbb{K}=\text{const}_{\sigma}\mathbb{A}$). Given
$f_{1},\dots,f_{m}\in\mathbb{A}\setminus\\{0\\}$. Find $h\in\mathbb{A}$ and
$(c_{1},\dots,c_{m})\in\mathbb{K}^{m}\setminus\\{\mathbf{0}\\}$ with

$\sigma(h)-h=c_{1}\,f_{1}+\dots+c_{d}\,f_{m}.$ (1)

For the special case $m=1$ this reduces to the telescoping problem.

Problem T in $(\mathbb{A},\sigma)$. Given $f\in\mathbb{A}\setminus\\{0\\}$.
Find $h\in\mathbb{A}$ with

$\sigma(h)-h=f.$ (2)

If $\sigma$ encodes the shift in $k$, equation (2) turns to
$h(k+1)-h(k)=f(k)$. Summing this equation over $k$ from $a$ to $b$ gives
$\sum_{k=a}^{b}f(k)=h(b+1)-h(a)$. Similarly, Zeilberger’s creative telescoping
paradigm [57] for finding recurrences of definite sums is covered in Problem
PT by setting $f_{i}=F(n+i-1,k)\in\mathbb{A}$ for $1\leq i\leq m$.

The breakthrough of these summation techniques was Gosper’s telescoping
algorithm for hypergeometric products [25] and Zeilberger’s extension to
creative telescoping [57]. They have been optimized and extended further to
other input classes, such as ($q$–)hypergeometric products [36, 37, 10, 21,
20, 19] or holonomic sequences [56, 23, 33]. Another milestone was Karr’s
summation algorithm [28, 29] that solves Problems T and PT in
$\Pi\Sigma$-fields.

######  Definition 1.

A difference field extension $(\mathbb{F},\sigma)$ of a difference field
$(\mathbb{G},\sigma)$ is called a _$\Pi\Sigma$ -field extension_ if
$\mathbb{G}=\mathbb{G}_{0}\leq\mathbb{G}_{1}\leq\dots\leq\mathbb{G}_{e}=\mathbb{F}$
is a tower of rational function field extensions with
$\mathbb{G}_{i}=\mathbb{G}_{i-1}(t_{i})$ for $1\leq i\leq e$ and we have
$\text{const}_{\sigma}\mathbb{F}=\text{const}_{\sigma}\mathbb{G}$ where for
all $1\leq i\leq e$ one of the following holds:

  * •

$\frac{\sigma(t_{i})}{t_{i}}\in(\mathbb{G}_{i-1})^{*}$ ($t_{i}$ is called a
_$\Pi$ -field monomial_);

  * •

$\sigma(t_{i})-t_{i}\in\mathbb{G}_{i-1}$ ($t_{i}$ is called a _$\Sigma$ -field
monomial_).

Such an $(\mathbb{F},\sigma)$ is called a _$\Pi\Sigma$ -field over
$\mathbb{K}$_ if $\text{const}_{\sigma}\mathbb{G}=\mathbb{G}=\mathbb{K}$.

Together with $\mathrm{R}\mathrm{\Pi\Sigma}$-extensions [51, 52] (see
Definition 2) one can rephrase indefinite nested sums defined over nested
products fully automatically [42, 9, 49, 34, 35, 53]; see also [9, 18]. In
particular, improved algorithms for (parameterized) telescoping [45, 47, 48,
9, 50] are implemented within the summation package Sigma[44, 54] to find
representations with minimal nesting depth. Further important simplifications
have been introduced in [5, 36] for the rational case $\mathbb{K}(x)$ with
$\sigma(x)=x+1$ that finds for a given $f\in\mathbb{K}(x)$ an $h$ in
$\mathbb{K}(x)$ or in a $\Pi\Sigma$-field $\mathbb{K}(x)(t)$ with
$\sigma(t)-t=f^{\prime}\in\mathbb{K}(x)$ such that (2) holds and the
denominator of $f^{\prime}$ has minimal degree; for the generalization in a
$\Pi\Sigma$-field $(\mathbb{F}(x),\sigma)$ we refer to [43].

In this article we aim at enhancing this telescoping approach [5, 36, 43]
(also related, e.g., to [6, 22, 17]) such that the generator $x$ may arise
also within an extension tower. E.g., consider the sum in

$\text{$\sum_{k=1}^{n}$}\Big{(}\frac{-2+k}{10(1+k^{2})}+\frac{(1-4k-2k^{2})}{10(1+k^{2})(2+2k+k^{2})}S_{1}(k)+\frac{(1-4k-2k^{2})}{5(1+k^{2})(2+2k+k^{2})}S_{3}(k)\Big{)}\\\\[-5.69046pt]
=\frac{(n^{2}+4n+5)}{10(n^{2}+2n+2)}S_{1}(n)-\frac{(n-1)(n+1)}{5(n^{2}+2n+2)}S_{3}(n)-\frac{2}{5}S_{2}(n).$
(3)

where the denominators in $k$ do not factorize nicely over $\mathbb{Q}$; here
$S_{o}(n)=\sum_{i=1}^{k}1/i^{o}$ denotes the harmonic numbers. Then with our
new algorithms one can compute the right-hand side of (3) in terms of sums
whose denominators factor linearly. In general, we assume that the sums and
products within $\mathbb{A}$ have nice denominators in $x$ (here in $k$),
i.e., have irreducible factors whose degrees are at most $d$ for some given
$d\in\mathbb{N}_{\geq 0}$. Then we can decide algorithmically if Problems T
and PT are solvable in $\mathbb{A}$ or in an extension of it of where the
additional sums have again nice denominators.

These algorithms play a crucial role to simplify d’Alembertian and Liouvillian
solutions [38, 40, 8, 27, 39] for hypergeometric products, and their
generalizations in $\Pi\Sigma$-fields [7]. E.g., during calculations coming
from particle physics [12, 14, 15] we have obtained sum solutions up to
nesting depth $40$ where the denominators of the sums are built by irreducible
polynomials with degrees up to 1000. Using our new toolbox we have obtained
optimal sum representations with only linear factors in the denominators.
These simplifications are essential to get solutions in terms of harmonic sums
and their generalizations [13, 55, 2, 3, 1]. In particular, these tools can be
combined efficiently with quasi-shuffle algebras [11, 4].

The article proceeds as follows. In Sec. 2 we present refined
$\mathrm{R}\mathrm{\Pi\Sigma}$-extensions and their main properties. In Sec. 3
we elaborate on denominator reduced representations. This insight yields new
telescoping algorithms in Sec. 4. A conclusion is given in Sec. 5.

##  2\. Basic notions and properties

All fields and rings have characteristic $0$. $(\mathbb{E},\sigma)$ is a
_difference ring (or field) extension_ of $(\mathbb{A},\sigma^{\prime})$ if
$\mathbb{A}$ is a subring (or subfield) of $\mathbb{E}$ and
$\sigma|_{\mathbb{A}}=\sigma^{\prime}$; from now on we do not distinguish
between $\sigma$ and $\sigma^{\prime}$.

We call a difference field or ring $(\mathbb{A},\sigma)$ with constant field
$\mathbb{K}$ _computable_ if $\sigma$ is computable, one can carry out the
standard operations in $\mathbb{A}$ and can decide if an element is $0$. It is
called _LA-computable_ if, in addition, one can compute for
$f_{1},\dots,f_{m}\in\mathbb{A}$ a basis of the $\mathbb{K}$-vector space

$\text{Ann}_{\mathbb{K}}(f_{1},\dots,f_{m})=\\{(c_{1},\dots,c_{m})\in\mathbb{K}^{m}\mid
c_{1}\,f_{1}+\dots+c_{m}\,f_{m}=0\\}.$

In a $\Pi\Sigma$-field extension $(\mathbb{F}(x),\sigma)$ of
$(\mathbb{F},\sigma)$ we define the _period_ of $h\in\mathbb{F}^{*}$ by
$\text{per}(h)=0$ if there is no $n\in\mathbb{N}_{\geq 1}$ with
$\sigma^{n}(h)/h\in\mathbb{F}$; otherwise, $\text{per}(h)$ is the smallest
$n\in\mathbb{N}_{\geq 1}$ with this property. We rely on the following
properties proved for a $\Pi\Sigma$-field in [28] and for a $\Pi\Sigma$-field
extension in [16, 41].

######  Lemma 1.

Let $f,g\in\mathbb{F}[x]\setminus\\{0\\}$ in a $\Pi\Sigma$-extension
$(\mathbb{F}(x),\sigma)$ of $(\mathbb{F},\sigma)$.

  1. 1.

If $\text{per}(f)>0$, then $\frac{\sigma(x)}{x}\in\mathbb{F}$ and $f=c\,x^{m}$
with $c\in\mathbb{F}^{*}$, $m\in\mathbb{Z}$.

  2. 2.

Suppose that $\frac{\sigma(x)}{x}\notin\mathbb{F}$ or not both $f,g$ have the
form $c\,x^{m}$ with $c\in\mathbb{F}^{*}$, $m\in\mathbb{Z}$. Then there is at
most one $k\in\mathbb{Z}$ with $\sigma^{k}(f)/g\in\mathbb{F}$.

Thus any element in $\mathbb{F}(x)$ has period $0$ or $1$. Furthermore, the
only monic and irreducible polynomial with period $1$ is the $\Pi$-monomial
$x$ itself. Write $f=f_{1}^{n_{1}}\dots f_{u}^{n_{u}}\in\mathbb{F}(x)$ where
the irreducible polynomials $f_{i}$ are pairwise coprime and
$n_{i}\in\mathbb{Z}$. We say that _$f$ has $x$-degree$\leq d$_ with
$d\in\mathbb{N}_{\geq 0}$ if for any period $0$ factor $f_{i}$ with $1\leq
i\leq u$ we have $\deg_{x}(f_{i})\leq d$; note: $f$ may contain a period $1$
factor. Irreducible polynomials $f,g\in\mathbb{F}[x]$ are called _$\sigma$
-equivalent_ if there is a $k\in\mathbb{Z}$ with
$\sigma^{k}(f)/g\in\mathbb{F}$. Otherwise, they are called _$\sigma$
-coprime_.

We introduce $\mathrm{R}\mathrm{\Pi\Sigma}$-extensions [51, 52] to model,
e.g., $(-1)^{n}$.

######  Definition 2.

A difference ring extension $(\mathbb{E},\sigma)$ of a difference ring
$(\mathbb{A},\sigma)$ is called an _$\mathrm{R}\mathrm{\Pi\Sigma}$ -extension_
if
$\mathbb{A}=\mathbb{A}_{0}\leq\mathbb{A}_{1}\leq\dots\leq\mathbb{A}_{e}=\mathbb{E}$
is a tower of ring extensions with
$\text{const}_{\sigma}\mathbb{E}=\text{const}_{\sigma}\mathbb{A}$ where for
all $1\leq i\leq e$ one of the following holds:

  * •

$\mathbb{A}_{i}=\mathbb{A}_{i-1}[t_{i}]$ is a ring extension subject to the
relation $t_{i}^{\nu}=1$ for some $\nu>1$ where
$\frac{\sigma(t_{i})}{t_{i}}\in(\mathbb{A}_{i-1})^{*}$ is a primitive $\nu$th
root of unity ($t_{i}$ is called an _$R$ -monomial_, and and we define
$\nu=\operatorname{ord}(t_{i})$);

  * •

$\mathbb{A}_{i}=\mathbb{A}_{i-1}[t_{i},t_{i}^{-1}]$ is a Laurent polynomial
ring extension with $\frac{\sigma(t_{i})}{t_{i}}\in(\mathbb{A}_{i-1})^{*}$
($t_{i}$ is called a _$\Pi$ -monomial_);

  * •

$\mathbb{A}_{i}=\mathbb{A}_{i-1}[t_{i}]$ is a polynomial ring extension with
$\sigma(t_{i})-t_{i}\in\mathbb{A}_{i-1}$ ($t_{i}$ is called an _$\Sigma$
-monomial_).

Depending on the occurrences of the $\mathrm{R}\mathrm{\Pi\Sigma}$-monomials
such an extension is also called a _$R$
-/$\Pi$-/$\Sigma$-/$R\Pi$-/$R\Sigma$-/$\Pi\Sigma$-extension_.
$(\mathbb{E},\sigma)$ is called a _simple $\mathrm{R}\mathrm{\Pi\Sigma}$-ring
extension_ of $(\mathbb{A},\sigma)$ if for all $R\Pi$-monomials $t_{i}$ we
have $\frac{\sigma(t_{i})}{t_{i}}=u\,t_{1}^{m_{1}}\dots t_{i-1}^{m_{i-1}}$
with $u\in\mathbb{A}^{*}$ and $m_{j}=0$ if $t_{j}$ is a $\Sigma$-monomial. If
$t_{i}$ is an $R$-monomial, we require in addition that $u$ is a root of unity
and $m_{j}=0$ if $t_{j}$ is an $\Pi\Sigma$-monomial.

######  Example 1.

Take the difference field $(\mathbb{Q}(x),\sigma)$ with $\sigma(x)=x+1$. Since
$\text{const}_{\sigma}\mathbb{Q}(x)=\mathbb{Q}$, it is a $\Pi\Sigma$-field
over $\mathbb{Q}$. We introduce the following
$\mathrm{R}\mathrm{\Pi\Sigma}$-extensions $(\mathbb{E},\sigma)$ over
$(\mathbb{Q}(x),\sigma)$, i.e., $\text{const}_{\sigma}\mathbb{E}=\mathbb{Q}$;
for algorithmic techniques that verify this property we refer to [28, 51].

  1. 1.

$(\mathbb{E},\sigma)$ with the polynomial ring
$\mathbb{E}=\mathbb{Q}(x)[h_{1}][h_{2}]$, $\sigma(h_{1})=h_{1}+\frac{1}{1+x}$
and $\sigma(h_{3})=h_{3}+\frac{1}{(1+x)^{3}}$ is a simple $\Sigma$-extention
of $(\mathbb{K}(x),\sigma)$.

  2. 2.

Take the ring $\mathbb{E}_{0}=\mathbb{K}(x)[z]$ subject to the relation
$z^{2}=1$ and define on top the Laurent polynomial ring
$\mathbb{E}=\mathbb{E}_{0}[\tau_{1},\tau_{1}^{-1}][\tau_{2},\tau_{2}^{-1}]$.
Then $(\mathbb{E},\sigma)$ with $\sigma(z)=-z$,
$\sigma(\tau_{1})=(x+1)\tau_{1}$ and $\sigma(\tau_{2})=(x+1)\tau_{1}$ is a
simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{Q}(x),\sigma)$.

  3. 3.

Take the polynomial ring $\mathbb{E}=\mathbb{E}_{0}[h_{1}]$. Then
$(\mathbb{E},\sigma)$ with $\sigma(z)=-z$ and
$\sigma(h_{1})=h_{1}+\frac{-z}{1+x}$ is a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{Q}(x),\sigma)$.

For convenience we use $\mathbb{A}\langle t\rangle$ with three different
meanings: it is the ring $\mathbb{A}[t]$ subject to the relation $t^{\nu}=1$
if $t$ is an $R$-monomial of order $\nu$, it is the polynomial ring
$\mathbb{A}[t]$ if $t$ is a $\Sigma$-monomial, or it is the Laurent polynomial
ring $\mathbb{A}[t,t^{-1}]$ if $t$ is a $\Pi$-monomial.
Let $(\mathbb{E},\sigma)$ be a simple $\mathrm{R}\mathrm{\Pi\Sigma}$-ring
extension of $(\mathbb{A},\sigma)$ with $\mathbb{E}=\mathbb{A}\langle
t_{1}\rangle\dots\langle t_{e}\rangle$. The elements in $\mathbb{E}$ are
spanned over the power products $\mathbf{t}^{\mathbf{n}}=t_{1}^{n_{1}}\dots
t_{e}^{n_{e}}\in\mathbb{E}$ with
$\mathbf{n}=(n_{1},\dots,n_{e})\in\mathbb{Z}^{e}$ where $n_{i}\geq 0$ if
$t_{i}$ is a $\Sigma$-monomial. If _$\mathbf{n}$ is reduced_, i.e., if $0\leq
i<\operatorname{ord}(t_{i})$ in case that $t_{i}$ is an $R$-monomial, the
power products are uniquely given. In particular,
$\mathbf{t}^{\mathbf{n}}\in\mathbb{A}$ implies $\mathbf{n}=\mathbf{0}$.
Furthermore, one can reorder the generators in $\mathbb{E}$ such that first
$R$-monomials, then $\Pi$-monomials and finally $\Sigma$-monomials are
adjoined.

Subsequently, let $\mathbb{A}=\mathbb{F}(x)$ where $(\mathbb{F}(x),\sigma)$ is
a $\Pi\Sigma$-field extension of $(\mathbb{F},\sigma)$. Let
$f=\sum_{\mathbf{i}\in\mathbb{Z}^{e}}f_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}}\in\mathbb{E}$
with $f_{\mathbf{i}}=\frac{p_{\mathbf{i}}}{q_{\mathbf{i}}}$ where the
polynomials $p_{\mathbf{i}},q_{\mathbf{i}}\in\mathbb{F}[x]$ are coprime.
Define $q=\operatorname{lcm}_{\mathbf{i}}(q_{\mathbf{i}})\in\mathbb{F}[x]$
being monic. Then we say that $f=\frac{h}{q}$ with
$h=\sum_{\mathbf{i}\in\mathbb{Z}^{e}}f^{\prime}_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}}\in\mathbb{F}[x]\langle
t_{1}\rangle\dots\langle t_{e}\rangle$ and
$f^{\prime}_{\mathbf{i}}=f_{\mathbf{i}}\,q/q_{i}\in\mathbb{F}[x]$ is in
_reduced representation_ , and we denote $q$ by $\operatorname{den}(f)$.
Subsequently, we will use the following properties: if
$\operatorname{den}(h)$, $\operatorname{den}(g)$ with $h,g\in\mathbb{E}$ have
$x$-degrees$\leq d$, then $\operatorname{den}(h\smash{{}^{+}_{\bullet}}g)$
have $x$-degrees$\leq d$. Further, if $\operatorname{den}(h)$ has
$x$-degree$\leq d$ but not $\operatorname{den}(g)$, then
$\operatorname{den}(h\smash{{}^{+}_{\bullet}}g)$ do not have $x$-degrees$\leq
d$.

Finally, we refine simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extensions further as
follows.

######  Definition 3.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and let $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$. Then
this _extension has $x$-degree$\leq d$_ with $d\in\mathbb{N}_{\geq 0}$ if for
all $\Pi\Sigma$-monomials $t_{i}$ one of the following properties hold:

  * •

If $t_{i}$ is a $\Pi$-monomial, then
$\frac{\sigma(t_{i})}{t_{i}}=u\,t^{n_{1}}\dots t^{n_{i-1}}$ where
$n_{j}\in\mathbb{Z}$ and $u\in\mathbb{F}(x)^{*}$ has $x$-degree$\leq d$.

  * •

If $t_{i}$ is a $\Sigma$-monomial, $\sigma(t_{i})-t_{i}=f$ where
$\operatorname{den}(f)$ has $x$-degree$\leq d$.

With $\mathbb{F}=\mathbb{Q}$ all the difference rings in Example 1 have
$x$-degree$\leq 1$.

######  Lemma 2.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and let $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$x$-degree$\leq d\in\mathbb{N}_{\geq 0}$.

  1. 1.

Let $f\in\mathbb{E}$ such that $\operatorname{den}(f)$ has $x$-degree$\leq d$.
Then $\operatorname{den}(\sigma^{k}(f))$ has $x$-degree$\leq d$ for any
$k\in\mathbb{Z}$.

  2. 2.

Let $f\in\mathbb{E}$ with $\operatorname{den}(f)=b\,c$ where
$c\in\mathbb{F}[x]$ contains precisely the irreducible period $0$ factors with
$x$-degrees larger than $d$ and $b$ has $x$-degree$\leq d$. Then for any
$k\in\mathbb{Z}$ we have $\operatorname{den}(\sigma^{k}(f))=\sigma^{k}(c)B$
for some $B\in\mathbb{F}[x]$ which has $x$-degree$\leq d$.

  3. 3.

For $g\in\mathbb{E}$ and a period $0$ irreducible $q\in\mathbb{F}[x]$ with
$\deg_{x}(q)>d$ the following holds:
(i) If $q\mid\operatorname{den}(g)$ and $\sigma(q)\nmid\operatorname{den}(g)$,
then $\sigma(q)\mid\operatorname{den}(\sigma(g)-g)$.
(ii) If $\sigma^{k}(q)\nmid\operatorname{den}(g)$ for any $k\in\mathbb{Z}$,
then $\sigma^{k}(q)\nmid\operatorname{den}(\sigma(g)-g)$ for any
$k\in\mathbb{Z}$.

###### Proof.

(1) We show statement 1 by induction on $e$. The base case $e=0$ obviously
holds. Now suppose that the lemma holds for $e-1$ extensions and consider the
next $\mathrm{R}\mathrm{\Pi\Sigma}$-monomial $t_{e}$ with
$\sigma(t_{e})=\alpha\,t_{e}+\beta$. If $t_{e}$ is an $R\Pi$-monomial, then
$\beta=0$ and $\alpha=u\,m$ with $u\in\mathbb{F}(x)^{*}$,
$m=t_{1}^{z_{1}}\dots t_{e-1}^{z_{e-1}}$ with $z_{i}\in\mathbb{Z}$; here
$z_{i}=0$ for all $1\leq i<e$ if $t_{i}$ is a $\Sigma$-monomial. Note that
$\sigma^{k}(t_{e})=\alpha_{k}t_{e}+\beta_{k}$ with $\beta_{k}=0$ and
$\alpha_{k}=\prod_{i=0}^{k-1}\sigma^{i}(u\,m)$ if $k\geq 0$ and
$\alpha_{k}=\prod_{i=1}^{-k}\sigma^{-i}(u^{-1}\,m^{-1})$ if $k<0$. Since $u$
has $x$-degree$\leq d$ (it $t_{e}$ is an $R$-monomial, $u\in\mathbb{F}^{*}$ is
a root of unity), the induction assumption can be applied and it follows that
$\operatorname{den}(\alpha_{k})$ has $x$-degree$\leq d$ for any
$k\in\mathbb{Z}$. Otherwise, suppose that $t_{e}$ is a $\Sigma$-monomial with
$\alpha=1$ and $\beta=\sigma(t_{e})-t_{e}\in\mathbb{F}(x)\langle
t_{1}\rangle\dots\langle t_{e-1}\rangle$. Then
$\sigma^{k}(t_{e})=\alpha_{k}\,t_{e}+\beta_{k}$ with $\alpha_{k}=1$ and
$\beta_{k}=\sum_{i=0}^{k-1}\sigma^{i}(\beta)$ if $k\geq 0$ and
$\beta_{k}=-\sum_{i=1}^{k}\sigma^{-i}(\beta)$ if $k<0$. Since
$\operatorname{den}(\beta)$ has $x$-degree$\leq d$, we can apply again the
induction assumption and $\operatorname{den}(\beta_{k})$ has $x$-degree$<d$
for any $k\in\mathbb{Z}$. Now consider
$f=\sum_{i}f_{i}\,t_{e}^{i}\in\mathbb{E}$ with $f_{i}\in\mathbb{F}(x)\langle
t_{1}\rangle\dots\langle t_{e-1}\rangle$. Then
$\sigma^{k}(f)=\sum_{i}\sigma^{k}(f_{i})(\alpha_{k}\,t_{e}+\beta_{k})^{i}$
where all components have $x$-degrees$\leq d$. Thus $\sigma^{k}(f)$ has
$x$-degree$\leq d$.
(2) Let $f=\frac{a}{b\,c}$ with $a\in\mathbb{F}[x]\langle
t_{1}\rangle\dots\langle t_{e}\rangle$ and $\operatorname{den}(f)=b\,c$ as
claimed in statement 2. Let $k\in\mathbb{Z}$ and consider
$\sigma^{k}(f)=\frac{A}{B\,C}$ with $\operatorname{den}(\sigma^{k}(f))=B\,C$
where $C$ contains precisely the period $0$ irreducible factors having
$x$-degrees larger than $d$ and $B$ has $x$-degree$\leq d$. By statement 1 it
follows that $\sigma^{k}(a)=\frac{a^{\prime}}{b^{\prime}}$ with
$a^{\prime}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$b^{\prime}=\operatorname{den}(\sigma^{k}(a))\in\mathbb{F}[x]$ has
$x$-degree$\leq d$. Thus
$\sigma^{k}(f)=\frac{\sigma^{k}(a)}{\sigma^{k}(b)\,\sigma^{k}(c)}=\frac{a^{\prime}}{b^{\prime}\sigma^{k}(b)\sigma^{k}(c)}$
where $\sigma^{k}(c)$ contains all irreducible period $0$ factors of
$\operatorname{den}(f)$ whose degree is larger than $d$ and
$b^{\prime}\sigma^{k}(b)$ has $x$-degree$\leq d$. Note that cancellation might
happen. However, $C\mid\sigma^{k}(c)$. Now consider
$f=\frac{\sigma^{-k}(A)}{\sigma^{-k}(B)\sigma^{-k}(C)}$. Similarly, we get
$f=\frac{A^{\prime}}{B^{\prime}\sigma^{-k}(C)}$ with
$A^{\prime}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$B^{\prime}\in\mathbb{F}[x]$ has $x$-degree$\leq d$. This implies that
$c\mid\sigma^{-k}(C)$ and thus $\sigma(c)\mid C$. Consequently $c=C\,u$ for
some $u\in\mathbb{F}^{*}$ and the statement is proven.
(3) Write $g=\frac{a}{b\,c}$ with $a\in\mathbb{F}[x]\langle
t_{1}\rangle\dots\langle t_{e}\rangle$ and $\operatorname{den}(g)=b\,c$ with
$b,c\in\mathbb{F}[x]$ were $b$ has $x$-degree$\leq d$ and $c$ contains all
period $0$ irreducible factors whose $x$-degrees are larger than $d$. Then
$\sigma(g)=\frac{A}{B\,\sigma(c)}$ with
$\operatorname{den}(\sigma(g))=B\,\sigma(c)$ where $B\in\mathbb{F}[x]$ has
$x$-degree$\leq d$ by statement 2. (i) Suppose $q\mid\operatorname{den}(g)$.
Thus $q\mid c$, hence $\sigma(q)\mid\sigma(c)$ and therefore
$\sigma(q)\mid\operatorname{den}(\sigma(g))$. By the second assumption
$\sigma(q)\nmid\operatorname{den}(g)$ it follows that
$\sigma(q)\mid\operatorname{den}(\sigma(g)-g)$.
(ii) If $\sigma^{k}(q)$ is no factor of $\operatorname{den}(g)$ for any
$k\in\mathbb{Z}$, then it is no factor of $c$ and thus of $\sigma(c)$.
Consequently it is not a factor in $\operatorname{den}(\sigma(g))$. In
particular, it cannot be a factor in $\operatorname{den}(\sigma(g)-g)$. ∎

##  3\. Refined representations

We start with the following definition and lemmas to get a normalized
representation of the denominator of a given input summand.

######  Definition 4.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and $d\in\mathbb{N}_{\geq 0}$. We call a finite set
$Q\subseteq\mathbb{F}[x]$ of monic irreducible polynomials a _$(d,x)$ -set_ if
the degrees are larger than $d$, they have period $0$ and are pairwise
$\sigma$-coprime. Let $f\in\mathbb{F}[x]\setminus\\{0\\}$. Then a $(d,x)$-set
$Q$ is called _$(d,f)$ -complete_ if for any irreducible factor $h$ of $f$
with $\deg_{x}(h)>d$ there are $q\in Q$ and $k\in\mathbb{Z}$ with
$\sigma^{k}(q)/h\in\mathbb{F}$.

In the following we require that one can solve Problem SE; for algorithmic
details see Thm. 3 below.

Problem SE in $(\mathbb{F}(x),\sigma)$ (Shift Equivalence) Given a
$\Pi\Sigma$-field extension $(\mathbb{F}(x),\sigma)$ of $(\mathbb{F},\sigma)$
and irreducible $f,g\in\mathbb{F}[x]$. Decide constructively if there is a
$k\in\mathbb{Z}$ with $\sigma^{k}(f)/g\in\mathbb{F}$.

######  Lemma 3.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ in which one can solve Problem SE and can factorize
polynomials. Let $f\in\mathbb{F}[x]\setminus\\{0\\}$, $d\in\mathbb{N}_{\geq
0}$ and $Q\subseteq\mathbb{F}[x]$ be an $(d,x)$-set. Then one can compute a
set $Q^{\prime}\supseteq Q$ which is $(d,f)$-complete.

###### Proof.

Compute all irreducible, pairwise coprime, period $0$ factors
$f_{1},\dots,f_{m}\in\mathbb{F}[x]$ of $f$ with $\deg_{x}(f_{i})>d$. If $m=0$,
$Q$ is the desired result. Otherwise, set $Q^{\prime}:=Q$ and proceed for each
$i=1\dots m$ and check if there is a $q\in Q^{\prime}$ and $k\in\mathbb{Z}$
with $\sigma^{k}(f_{i})/q$; if there is none, set
$Q^{\prime}:=Q^{\prime}\cup\\{f_{i}\\}$. The obtained $Q^{\prime}$ is
$(d,f)$-complete. ∎

Given these notions, we obtain the following representation; it can be
considered as a variant of partial fraction decomposition and is connected to
constructions given [5, 36, 6, 22, 43, 17].

######  Lemma 4.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and let $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$x$-degree$\leq d$ with $d\in\mathbb{N}_{\geq 0}$ and
$\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$. Let
$f\in\mathbb{E}$ and let $Q=\\{q_{1},\dots,q_{r}\\}$ be
$(d,\operatorname{den}(f))$-complete. Then there are
$f^{\prime},g\in\mathbb{E}$ s.t.

$\sigma(g)-g+f^{\prime}=f$ (4)

where $f^{\prime}$ can be written in the _$\sigma$ -reduced form_

$f^{\prime}=\frac{p_{1}}{q_{1}^{n_{1}}}+\frac{p_{r}}{q_{r}^{n_{r}}}+\frac{p}{q}$
(5)

with the following ingredients:

  1. 1.

$n_{1},\dots,n_{r}\in\mathbb{N}_{\geq 1}$,

  2. 2.

$q\in\mathbb{F}[x]\setminus\\{0\\}$ with $x$-degree $\leq d$,

  3. 3.

$p\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle t_{e}\rangle$,

  4. 4.

and $p_{1},\dots,p_{r}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle
t_{e}\rangle$ with $\deg_{x}(p_{i})<\deg_{x}(q_{i})\,n_{i}$.

If one can factorize polynomials in $\mathbb{F}[x]$ and can solve Problem SE
in a computable $(\mathbb{F}(x),\sigma)$, then $g$ and $f^{\prime}$ with (5)
can be computed.

###### Proof.

Write $f=\frac{a}{b}$ with $a\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle
t_{e}\rangle$ and $b\in\mathbb{F}[x]\setminus\\{0\\}$ monic in reduced
representation. If $\mathbb{F}$ is computable, this can be accomplished with
the Euclidean algorithm. In particular, write $b=q^{\prime}\,b^{\prime}$ where
$q^{\prime}\in\mathbb{F}[x]\setminus\\{0\\}$ has $x$-degree$\leq d$ and where
$b^{\prime}=v_{1}^{n_{1}}\dots v_{r}^{n_{r}}\in\mathbb{F}[x]$ with
$v_{i}\in\mathbb{F}[x]\setminus\\{0\\}$ are the monic irreducible and period
$0$ factors with $\deg_{x}(v_{i})>d$. Note that $Q$ is
$(d,b^{\prime})$-complete. If $b^{\prime}=1$, we can take $p=a$, $q=b$, $r=0$
and $g=0$, and we are done. Otherwise, take $s,t\in\mathbb{F}[x]$ such that
$1=s\,b^{\prime}+t\,q^{\prime}$; since $\gcd(b^{\prime},q^{\prime})=1$, such
$s$ and $t$ exist and can be calculated by the extended Euclidean algorithm if
$\mathbb{F}$ is computable. Hence
$\frac{a}{b}=\frac{s\,a}{q^{\prime}}+\frac{t\,a}{b^{\prime}}$. Now we repeat
this tactic to $\frac{s\,a}{b^{\prime}}$ iteratively to separate the coprime
factors $v_{i}^{n_{i}}$ in the denominator of $b^{\prime}$ and get

$\frac{a}{b}=\frac{s\,a}{q^{\prime}}+\frac{u_{1}}{v_{1}^{n_{1}}}+\dots+\frac{u_{r}}{v_{r}^{n_{r}}}$
(6)

with $u_{i}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle t_{e}\rangle$.
W.l.o.g. suppose that $v_{1},\dots,v_{k}$ are all those factors that are
$\sigma$-equivalent to $q_{1}\in Q$. Hence for all $1\leq i\leq k$,
$c_{i}:=\frac{\sigma^{s_{i}}(q_{1})}{v_{i}}\in\mathbb{F}$ for some uniquely
determined $s_{i}\in\mathbb{Z}$; see Lemma 1.2. Define
$f^{\prime}_{i},\gamma_{i}\in\mathbb{E}$ with
$f^{\prime}_{i}=\frac{\sigma^{-s_{i}}(u_{i}\,c_{i}^{n_{i}})}{q_{1}^{n_{i}}}$
and
$\gamma_{i}=\sum_{j=0}^{s_{i}-1}\sigma^{j}(\frac{\sigma^{-s_{i}}(u_{i}\,c_{i}^{n_{i}})}{q_{1}^{n_{i}}})$
if $s_{i}\geq 0$ and
$\gamma_{i}=-\sum_{j=1}^{-s_{i}}\sigma^{-j}(\frac{\sigma^{-s_{i}}(u_{i}\,c_{i}^{n_{i}})}{q_{1}^{n_{i}}})$
if $s_{i}<0$. Then by telescoping and $\sigma^{s_{i}}(q_{1})=c_{i}\,v_{i}$ we
get

$\sigma(\gamma_{i})-\gamma_{i}+f^{\prime}_{i}=\sigma^{s_{i}}\big{(}\sigma^{-s_{i}}(u_{i}\,c_{i}^{n_{i}})/q_{1}^{n_{i}}\big{)}=\frac{u_{i}\,c_{i}^{n_{i}}}{\sigma^{s_{i}}(q_{1})^{n_{i}}}=\frac{u_{i}}{v_{i}^{n_{i}}}.$

Since $u_{i}\,c_{i}^{n_{i}}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle
t_{e}\rangle$, it follows that
$\operatorname{den}(\sigma^{-s_{i}}(u_{i}\,c_{i}^{n_{i}}))$ has no irreducible
factors with $x$-degrees larger than $d$ by Lemma 2.1. Thus we can write
$f^{\prime}_{i}=\frac{\alpha_{i}}{\beta_{i}\,q_{1}^{n_{1}}}$ with
$\alpha_{i}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$\beta_{i}\in\mathbb{F}[x]\setminus\\{0\\}$ whose irreducible factors have
$x$-degrees$\leq d$. Since $\gcd(q_{1}^{n_{1}},\beta_{i})=1$, we can write
$s^{\prime}_{i}\,\beta_{i}+t^{\prime}_{i}\,q_{1}^{n_{1}}=1$ with
$s^{\prime}_{i},t^{\prime}_{i}\in\mathbb{F}[x]$ (and can again compute it if
$\mathbb{F}$ is computable). Hence $f^{\prime}_{i}=\phi_{i}+h_{i}$ with
$\phi_{i}=\frac{\alpha_{i}\,s^{\prime}_{i}}{q_{1}^{n_{1}}}$ and
$h_{i}=\frac{\alpha_{i}\,t^{\prime}_{i}}{\beta_{i}}$. Now take
$g^{\prime}:=\gamma_{1}+\dots+\gamma_{k}\in\mathbb{E}$. Further let
$\frac{H_{1}}{H_{2}}=h_{1}+\dots+h_{k}$ where $H_{1}\in\mathbb{F}[x]\langle
t_{1},\dots,t_{e}\rangle$ and $H_{2}\in\mathbb{F}[x]\setminus\\{0\\}$ which
has $x$-degree$\leq d$. In addition, define $w_{1}\in\mathbb{F}[x]\langle
t_{1},\dots,t_{e}\rangle$ with
$\frac{w_{1}}{q_{1}^{n_{1}}}=\phi_{1}+\dots+\phi_{k}$. Then
$\sigma(g^{\prime})-g^{\prime}+\frac{w_{1}}{q_{1}^{n_{1}}}+\frac{H_{1}}{H_{2}}=\frac{u_{1}}{v_{1}^{n_{1}}}+\dots+\frac{u_{k}}{v_{k}^{n_{k}}}.$
Since $q_{1}^{n_{1}}\in\mathbb{F}[x]\setminus\\{0\\}$, the leading coefficient
of $q_{1}^{n_{1}}$ is a unit. Thus we can compute
$w_{1}=\tilde{q}_{1}\,q_{1}^{n_{1}}+p_{1}$ with
$p_{1},\tilde{q}_{1}\in\mathbb{F}[x]\langle t_{1},\dots,t_{e}\rangle$ with
$\deg_{x}(p_{1})<\deg_{x}(q_{1}^{n})$ by polynomial division (and considering
$x$ as the top variable). This gives
$\frac{w_{1}}{q_{1}^{n_{1}}}=\frac{p_{1}}{q_{1}^{n_{1}}}+\tilde{q}_{1}$.
Define $p^{\prime\prime}\in\mathbb{F}[x]\langle t_{1},\dots,t_{e}\rangle$ and
$q^{\prime\prime}\in\mathbb{F}[x]\setminus\\{0\\}$ with
$\frac{p^{\prime\prime}}{q^{\prime\prime}}=\frac{a\,a}{q^{\prime}}+\tilde{q}_{1}+\frac{H_{1}}{H_{2}}$;
note: $q^{\prime\prime}$ has only factors with $x$-degree$\leq d$. Thus
plugging the ingredients into (6) gives

$\frac{a}{b}=\sigma(g^{\prime})-g^{\prime}+\frac{p^{\prime\prime}}{q^{\prime\prime}}+\frac{p_{1}}{q_{1}^{n}}+\overbrace{\frac{u_{k+1}}{v_{k+1}^{m_{k+1}}}+\dots+\frac{u_{r}}{v_{r}^{m_{r}}}}^{R}.$

Repeating this transformation to $R$ produces the desired representation (5).
If one can factorize polynomials in $\mathbb{F}[x]$ and one can solve Problem
SE in $(\mathbb{F}(x),\sigma)$, this representation can be calculated. ∎

######  Example 2.

1\. Take the difference ring $(\mathbb{E},\sigma)$ from Example 1.1. Here we
can rephrase the summand on the left-hand side of (3) with

$f=\frac{-2+x}{10(1+x^{2})}+\frac{h_{1}(1-4x-2x^{2})}{10(1+x^{2})(2+2x+x^{2})}+\frac{h_{3}(1-4x-2x^{2})}{5(1+x^{2})(2+2x+x^{2})}\in\mathbb{E}.$
(7)

$Q=\\{q_{1}\\}$ with $q_{1}=1+x^{2}$ is $(1,f)$-complete. We can compute

$g=\frac{h_{3}(1+2x)}{10(1+x^{2})}+\frac{h_{3}(1+2x)}{5(1+x^{2})}-\frac{(1+2x)(2+x^{2})}{10x^{3}(1+x^{2})}$
(8)

and $f^{\prime}=\frac{p_{1}}{q_{1}}+\frac{p}{q}$ with $p_{1}=0$ and
$\frac{p}{q}=\frac{-2-4x+x^{2}}{10x^{3}}$ such that (4) holds.
2\. Take the difference ring $(\mathbb{E},\sigma)$ from Example 1.3 and
consider

$\mathbf{f}=(f_{1},f_{2},f_{3})=\Big{(}\frac{h_{1}(x+z+x^{2}z)}{x(1+x^{2})},\frac{h_{1}}{2+2x+x^{2}},\frac{xz}{1+x^{2}}\Big{)}\in\mathbb{E}^{3}.$
(9)

$Q=\\{q_{1}\\}$ with $q_{1}=1+x^{2}$ is $(1,f_{i})$-complete for $1\leq i\leq
3$. For $\sigma(g_{i})-g_{i}+f^{\prime}_{i}=f_{i}$ we get $g_{i}\in\mathbb{E}$
and the $\sigma$-reduced form $f^{\prime}_{i}=\frac{p_{i,1}}{q_{1}}+\rho_{i}$
with $\rho_{i}=p^{\prime}_{i}/q^{\prime}_{i}$. Namely, $p_{1,1}=h_{1}$,
$\rho_{1}=\frac{h_{1}z}{x}$, $g_{1}=0$, and $p_{2,1}=h_{1}+xz$,
$\rho_{2}=-\frac{z}{x}$, $g_{2}=\frac{h_{1}x-z}{x(1+x^{2})}$, and
$p_{3,1}=xz$, $\rho_{3}=0$, $g_{3}=0$.

######  Lemma 5.

Let $(\mathbb{E},\sigma)$ be a simple $R\Pi$-extension of
$(\mathbb{H},\sigma)$ with $\mathbb{E}=\mathbb{H}\langle
t_{1}\rangle\dots\langle t_{e}\rangle$. Let
$f=\sum_{\mathbf{i}\in\mathbb{Z}^{e}}f_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}}\in\mathbb{E}$
and
$g=\sum_{\mathbf{i}\in\mathbb{Z}^{e}}g_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}}\in\mathbb{E}$
with $\sigma(g)-g=f$. Then for each reduced $\mathbf{i}\in\mathbb{Z}^{e}$
there is a unique reduced $\mathbf{j}\in\mathbb{Z}^{e}$ with
$u=\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}\in\mathbb{H}^{*}$.
Conversely, for each reduced $\mathbf{j}\in\mathbb{Z}^{e}$ there is a unique
reduced $\mathbf{i}\in\mathbb{Z}^{e}$ with
$u=\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}\in\mathbb{H}^{*}$.
For such a tuple $(\mathbf{i},\mathbf{j})$ with
$u=\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}\in\mathbb{H}^{*}$
we have $u\,\sigma(g_{\mathbf{i}})-g_{\mathbf{j}}=f_{\mathbf{j}}$.

###### Proof.

Let $\mathbf{i}\in\mathbb{Z}^{e}$ be reduced and take
$h=\sigma(\mathbf{t}^{\mathbf{i}})$. By definition we have
$h=u\,\mathbf{t}^{\mathbf{j}}$ with $u\in\mathbb{H}^{*}$ and a reduced
$\mathbf{j}\in\mathbb{Z}^{e}$, i.e.,
$\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}=u\in\mathbb{H}^{*}$.
Suppose that
$\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{k}}}=u^{\prime}\in\mathbb{H}^{*}$
with another reduced $\mathbf{k}\in\mathbb{Z}^{e}$. Then
$\mathbf{t}^{\mathbf{j}-\mathbf{k}}=u^{\prime}/u\in\mathbb{H}^{*}$ which
implies that $\mathbf{j}=\mathbf{k}$, i.e., $\mathbf{j}$ is uniquely
determined. Similarly, let $\mathbf{j}\in\mathbb{Z}^{e}$ be reduced and take
$h=\sigma^{-1}(\mathbf{t}^{\mathbf{j}})$. By definition we have
$h=u^{\prime}\,\mathbf{t}^{\mathbf{i}}$ with $u^{\prime}\in\mathbb{H}^{*}$ and
$\mathbf{i}\in\mathbb{Z}^{e}$ reduced, i.e.,
$\mathbf{t}^{\mathbf{i}}/\sigma^{-1}(\mathbf{t}^{\mathbf{j}})=1/u^{\prime}\in\mathbb{H}^{*}$
and thus $\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}=u$
with $u=\sigma(1/u^{\prime})\in\mathbb{H}^{*}$. Further, suppose that
$\frac{\sigma(\mathbf{t}^{\mathbf{k}})}{\mathbf{t}^{\mathbf{j}}}=u^{\prime}\in\mathbb{H}^{*}$
with another reduced $\mathbf{k}\in\mathbb{Z}^{e}$. Then
$\sigma(\mathbf{t}^{\mathbf{i}-\mathbf{k}})=u/u^{\prime}$ and thus
$\mathbf{t}^{\mathbf{i}-\mathbf{k}}=\sigma^{-1}(u/u^{\prime})\in\mathbb{H}^{*}$.
This implies $\mathbf{i}=\mathbf{k}$ and proves the uniqueness of
$\mathbf{i}$. Now take such a tuple $(\mathbf{i},\mathbf{j})$ of reduced
elements with
$u=\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}\in\mathbb{H}^{*}$.
By coefficient comparison in $\sigma(g)-g=f$ w.r.t. $\mathbf{t}^{\mathbf{j}}$
we get
$\sigma(g_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}})-g_{\mathbf{j}}\,\mathbf{t}^{\mathbf{j}}=f_{\mathbf{j}}\,\mathbf{t}^{\mathbf{j}}$.
With
$\sigma(g_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}})=\sigma(g_{\mathbf{i}})\,u\,\mathbf{t}^{\mathbf{j}}$
and dividing through $\mathbf{t}^{\mathbf{j}}$ we get
$u\,\sigma(g_{\mathbf{i}})-g_{\mathbf{j}}=f_{\mathbf{j}}$. ∎

######  Lemma 6.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and $(\mathbb{E},\sigma)$ be a simple $R\Pi$-extension
of $(\mathbb{F}(x),\sigma)$ with $x$-degree$\leq d$. Let $f\in\mathbb{E}$ with
$\operatorname{den}(f)=v\,q^{n}$ where $n\in\mathbb{N}_{\geq 1}$,
$q\in\mathbb{F}[x]$ is an irreducible period $0$ factor with $\deg_{x}(v)>d$
and $v\in\mathbb{F}[x]$ does not contain any factor which is
$\sigma$-equivalent to $q$. Then there is no $g\in\mathbb{E}$ with
$\sigma(g)-g=f.$

###### Proof.

Suppose that there is such a
$g=\sum_{\mathbf{i}\in\mathbb{Z}^{e}}g_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}}\in\mathbb{E}$
with $g_{\mathbf{i}}=\frac{\gamma_{\mathbf{i}}}{\delta_{\mathbf{i}}}$ where
$\gamma_{\mathbf{i}}\in\mathbb{F}[x],\delta_{\mathbf{i}}\in\mathbb{F}[x]\setminus\\{0\\}$
with $\gcd(\gamma_{\mathbf{i}},\delta_{\mathbf{i}})=1$. Write
$f=\sum_{\mathbf{i}\in\mathbb{Z}^{e}}f_{\mathbf{i}}\,\mathbf{t}^{\mathbf{i}}\in\mathbb{E}$
with $f_{\mathbf{i}}=\frac{a_{\mathbf{i}}}{b_{\mathbf{i}}}$ with
$a_{\mathbf{i}},b_{\mathbf{i}}\in\mathbb{F}[x]$ and
$\gcd(a_{\mathbf{i}},b_{\mathbf{i}})=1$ where $b_{\mathbf{i}}$ may contain $q$
as factor but not $\sigma^{k}(q)$ with $k\neq 0$. There must be a denominator
$\delta_{\mathbf{i}}$ that contains $\sigma^{\lambda}(q)$ for some
$\lambda\in\mathbb{Z}$. Otherwise, we conclude with Lemma 2.3.(ii) that
$q\nmid\operatorname{den}(\sigma(g)-g)$, a contradiction. Among all
$g_{\mathbf{j}}\neq 0$ take $\mathbf{j}\in\mathbb{Z}^{e}$ such that
$\sigma^{\lambda}(q)\mid\delta_{\mathbf{j}}$ with $\lambda\in\mathbb{Z}$
maximal. By Lemma 5 we can take $\mathbf{i}\in\mathbb{Z}^{e}$ with
$u=\frac{\sigma(\mathbf{t}^{\mathbf{j}})}{\mathbf{t}^{\mathbf{i}}}\in\mathbb{H}^{*}$
and $u\,\sigma(g_{\mathbf{j}})-g_{\mathbf{i}}=f_{\mathbf{i}}$. Note that
$u=v\,t_{1}^{z_{1}}\dots t_{e}^{z_{e}}$ with $z_{i}\in\mathbb{Z}$ where
$v\in\mathbb{F}[x]$ has $x$-degree$\leq d$. Then
$\sigma^{\lambda+1}(q)\mid\sigma(\delta_{\mathbf{j}})$ but
$\sigma^{\lambda+1}(q)\nmid\delta_{\mathbf{i}}$. Thus
$\sigma^{\lambda+1}(q)\mid\operatorname{den}(f_{\mathbf{i}})=b_{\mathbf{i}}$.
Hence $\lambda=-1$ for the maximal choice $\lambda$. Among all
$g_{\mathbf{j}}\neq 0$ take $\mathbf{j}\in\mathbb{Z}^{e}$ such that
$\sigma^{\lambda}(q)\mid\delta_{\mathbf{j}}$ with $\lambda$ minimal. Note that
$\lambda<0$ (since the maximal choice is $-1$). By Lemma 5 we can take
$\mathbf{j}\in\mathbb{Z}^{e}$ with
$u=\frac{\sigma(\mathbf{t}^{\mathbf{i}})}{\mathbf{t}^{\mathbf{j}}}\in\mathbb{H}^{*}$
and $u\,\sigma(g_{\mathbf{i}})-g_{\mathbf{j}}=f_{\mathbf{j}}$. Similarly, one
gets $\sigma^{\lambda}(q)\nmid\operatorname{den}(u\,\sigma(g_{\mathbf{i}}))$
and we conclude that
$\sigma^{\lambda}(q)\mid\operatorname{den}(f_{\mathbf{j}})=b_{\mathbf{j}}$
with $\lambda<0$, a contradiction. Thus $g\in\mathbb{E}$ with $\sigma(g)-g=f$
cannot exist. ∎

Now we can present the main property for
$\mathrm{R}\mathrm{\Pi\Sigma}$-extensions which can be considered as a
generalization appearing in [5, 36, 6, 22, 43, 17]; there the denominators are
split by $\sigma$-equivalent factors.

######  Proposition 1.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$x$-degree$\leq d$. Let $p\in\mathbb{E}$ and
$q\in\mathbb{F}[x]\setminus\\{0\\}$ with $x$-degree$\leq d$. Let
$\\{q_{1},\dots,q_{r}\\}\subseteq\mathbb{F}[x]$ be a $(d,x)$-set,
$n_{1},\dots,n_{r}\in\mathbb{N}_{\geq 1}$ and
$p_{1},\dots,p_{r}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle
t_{e}\rangle$ with $\deg_{x}(p_{i})\leq\deg_{x}(q_{i})\,n_{i}$. If there is a
$g\in\mathbb{E}$ with

$\hskip
42.67912pt\sigma(g)-g=\frac{p_{1}}{q_{1}^{n_{1}}}+\frac{p_{r}}{q_{r}^{n_{r}}}+\frac{p}{q}$
(10)

then $p_{1}=\dots=p_{r}=0$ and $\operatorname{den}(g)$ has $x$-degree$\leq d$.

###### Proof.

Write $\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$.
W.l.o.g. we may assume that all $R$-monomials are adjoined first,
$\Pi$-monomials come next and $\Sigma$-monomials are adjoint at the end;
otherwise we reorder them accordingly. We prove the proposition by induction
of the number of $\Sigma$-extensions in $\mathbb{E}$. In the base case, we
assume that $\mathbb{E}$ is built only by simple $R\Pi$-extensions and there
is a $g\in\mathbb{E}$ with (10). In addition assume that there is $i$ such
that $p_{i}$ is nonzero. Write
$\frac{p_{i}}{q_{1}^{n_{i}}}=\frac{p^{\prime}_{i}}{q_{1}^{\mu}}$ in reduced
representation with $\mu\leq n_{i}$. Since
$\deg_{x}(p_{i})<\deg_{x}(q_{i}^{n_{i}})$, it follows $\mu\geq 1$. In
particular we can write the right-hand side of (10) in reduced representation
with $f=\frac{p^{\prime}}{v\,q_{i}^{\mu}}$ where
$p^{\prime}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$v\in\mathbb{F}[x]$ whose irreducible factors are $\sigma$-coprime with
$q_{i}$. By Lemma 6 a solution $g\in\mathbb{E}$ with (10) is not possible, a
contradiction. Hence $p_{i}=0$ for all $i$, and we get
$\sigma(g)-g=\frac{p}{q}$ with $g\in\mathbb{E}$. Suppose there is an
irreducible period $0$ factor $v$ in $\operatorname{den}(g)$ with
$\deg_{x}(v)>d$. By Lemma 1.1 we can take among the $\sigma$-equivalent
factors of $v$ in $\operatorname{den}(g)$ that one which maps to the other
factors only by negative $\sigma$-shifts. By Lemma 2.3.(i),
$\sigma(v)\mid\operatorname{den}(\sigma(g)-g)$, a contradiction. Thus
$\operatorname{den}(g)$ has $x$-degree$\leq d$.

Now consider the simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension
$(\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle,\sigma)$ of
$(\mathbb{F}(x),\sigma)$ with $x$-degree $\leq d$ with
$\sigma(t_{e})=t_{e}+\beta$ and suppose that the proposition holds for
$(\mathbb{H},\sigma)$ with $\mathbb{H}=\mathbb{F}(x)\langle
t_{1}\rangle\dots\langle t_{e-1}\rangle$. Let $g\in\mathbb{F}(x)\langle
t_{1}\rangle\dots\langle t_{e}\rangle$ such that (10) holds. By [51, Lemma
7.2] it follows that for $b=\deg_{t_{e}}(f)+1$ we have that
$\deg_{t_{e}}(g)\leq b$. We show the proposition by a second induction on $b$.
If $b=0$, it follows that $f$ is free of $t_{e}$ and the main induction
assumption implies the correctness. Now suppose that the proposition holds for
a solution where the degree is smaller than $b$. Define
$\phi:=\operatorname{coeff}(f,t_{e},b)\in\mathbb{H}$ and
$\gamma:=\operatorname{coeff}(g,t_{e},b)\in\mathbb{H}$ being the coefficients
of $t_{e}^{b}$ in $f$ and $g$. Then $g=\gamma\,t_{e}^{b}+w$ with
$w\in\mathbb{F}(x)\langle t_{1},\dots,t_{e-1}\rangle[t_{e}]$ where
$\deg_{t_{e}}(w)<b$. By coefficient comparison it follows that
$\sigma(\gamma)-\gamma=\phi$. Define
$h_{i}:=\operatorname{coeff}(p_{i},t_{e},b)\in\mathbb{H}$ and
$u:=\operatorname{coeff}(p,t_{e},b)\in\mathbb{H}$. Then
$\phi=\frac{h_{1}}{q_{1}^{n_{1}}}+\dots+\frac{h_{r}}{q_{r}^{n_{r}}}+\frac{u}{q}$
holds in $\mathbb{H}$. Hence by the induction assumption on $\mathbb{H}$ we
conclude that $h_{1}=\dots=h_{r}=0$ and $\operatorname{den}(\gamma)$ has
$x$-degree$\leq d$. Now define
$U=\frac{p}{q}-(\sigma(\gamma\,t^{b})-\gamma\,t^{b})\in\mathbb{H}[t_{e}]$.
Then by construction
$\sigma(w)-w=\frac{p_{1}}{q_{1}^{n_{1}}}+\dots+\frac{p_{r}}{q_{r}^{n_{r}}}+U$
and $\deg_{t_{e}}(U)<b$. Moreover, $\operatorname{den}(\sigma(\gamma\,t^{b}))$
has $x$-degrees$\leq d$ by Lemma 2.1. Since also $q$ and
$\operatorname{den}(\gamma)$ have $x$-degrees$\leq d$, we conclude that
$\operatorname{den}(U)$ has $x$-degree$\leq d$. With the second induction
hypothesis (induction on $b$) it follows that $p_{1}=\dots=p_{r}=0$ and
$\operatorname{den}(w)$ has $x$-degree$\leq d$. Hence
$\operatorname{den}(\gamma\,t^{b}+w)$ has $x$-degree$\leq d$. This completes
the proof. ∎

In the following we rely on Theorem 1 shown in [52, Theorem 7.10]; for the
field version with $m=1$ see [28] and for the general case
$m\in\mathbb{N}_{\geq 0}$ see [46]; this result is also related to [26].

######  Theorem 1 ([52]).

Let $(\mathbb{A},\sigma)$ be a difference ring with constant field
$\mathbb{K}=\text{const}_{\sigma}\mathbb{A}$ and let
$f_{1},\dots,f_{m}\in\mathbb{A}$. Then there is a $\Sigma$-extension
$(\mathbb{A}[s_{1}]\dots[s_{m}],\sigma)$ of $(\mathbb{A},\sigma)$ with
$\sigma(s_{i})=s_{i}+f_{i}$ for $1\leq i\leq m$ iff there are no
$(c_{1},\dots,c_{m})\in\mathbb{K}^{m}\setminus\\{\mathbf{0}\\}$ and
$h\in\mathbb{A}$ with (1).

Using this result we obtain the following characterization of certain classes
of simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension. They will be introduced in
Def. 5 below and will be the basis of our telescoping algorithms.

######  Theorem 2.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ with $\mathbb{K}=\text{const}_{\sigma}\mathbb{F}$ and
let $(\mathbb{E},\sigma)$ be a simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension
of $(\mathbb{F}(x),\sigma)$ with $x$-degree$\leq d$ and
$\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$. Let
$\\{q_{1},\dots,q_{r}\\}\subseteq\mathbb{F}[x]$ be a $(d,x)$-set,
$n_{1},\dots,n_{r}\in\mathbb{N}_{\geq 1}$, and for $1\leq i\leq r$ and $1\leq
j\leq e_{i}$ with $e_{i}\geq 1$ let $p_{i,j}\in\mathbb{F}[x]\langle
t_{1}\rangle\dots\langle t_{e}\rangle\setminus\\{0\\}$ with
$\deg_{x}(p_{i,j})<\deg_{x}(q_{i})n_{i}$. Then the following statements are
equivalent.

  1. 1.

$\text{Ann}_{\mathbb{K}}(p_{i,1},\dots,p_{i,e_{i}})=\\{\mathbf{0}\\}$ for all
$1\leq i\leq r$;

  2. 2.

there are no $g\in\mathbb{E}$ and $c_{i,j}\in\mathbb{K}$ (not all zero) such
that

$\sigma(g)-g=\sum_{i,j}c_{i,j}\frac{p_{i,j}}{q_{i}^{n_{i}}};$ (11)

  3. 3.

the difference ring extension $(\mathbb{S},\sigma)$ of $(\mathbb{E},\sigma)$
with the polynomial ring

$\mathbb{S}=\mathbb{E}[s_{1,1},\dots,s_{1,e_{1}},\dots,s_{r,1},\dots,s_{r,e_{r}}]$

and $\sigma(s_{i,j})=s_{i,j}+\frac{p_{i,j}}{q_{i}^{n_{i}}}$ is a
$\Sigma$-extension, i.e.,
$\text{const}_{\sigma}\mathbb{S}=\text{const}_{\sigma}\mathbb{F}$.

###### Proof.

$(1)\Rightarrow(2)$ Let $c_{i,j}\in\mathbb{K}$, not all zero, and
$g\in\mathbb{E}$ such that
$\sigma(g)-g=\sum_{i,j}c_{i,j}\frac{p_{i,j}}{q_{i}^{n_{i}}}=\sum_{1\leq i\leq
r}\frac{p_{i}}{q_{i}^{n_{i}}}$ with
$p_{i}=\sum_{j=1}^{e_{i}}c_{i,j}p_{i,j}\in\mathbb{F}[x]\langle
t_{1}\rangle\dots\langle t_{e}\rangle$ for $1\leq i\leq r$. Since
$\deg_{x}(p_{i,j})<\deg_{x}(q_{i})n_{i}$, we have
$\deg_{x}(p_{i})<\deg_{x}(q_{i})n_{i}$. Hence we can apply Proposition 1 and
it follows that $p_{i}=0$ for all $i$. By assumption we can take $i,j$ with
$c_{i,j}\neq 0$. Thus
$\mathbf{0}\neq(c_{i,1},\dots,c_{i,e_{i}})\in\text{Ann}_{\mathbb{K}}(p_{i,1},\dots,p_{i,e_{i}})$.
$(2)\Rightarrow(1)$ Suppose that there is $i$ with
$V_{i}=\text{Ann}_{\mathbb{K}}(p_{i,1},\dots,p_{i,e_{i}})\neq\\{\mathbf{0}\\}$.
Then we can take $g=0\in\mathbb{E}$ and $(c_{i,1},\dots,c_{i,e_{i}})\in
V_{i}\setminus\\{\mathbf{0}\\}$ where all other $c_{k,j}0$ are set to zero.
This gives (11).
$(2)\Leftrightarrow(3)$ follows by Theorem 1. ∎

##  4\. Refined telescoping algorithms

We will assume that certain algorithmic properties are satisfied in the ground
field $(\mathbb{F}(x),\sigma)$. Here we can exploit the following result.

######  Theorem 3 ([28, 52]).

Let $\mathbb{K}=A(y_{1},\dots,y_{\lambda})$ be a rational function field over
an algebraic number field $A$, $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field
over $\mathbb{K}$ and $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F},\sigma)$. Then:

  1. 1.

One can solve Problem SE in $(\mathbb{F}(x),\sigma)$.

  2. 2.

$(\mathbb{E},\sigma)$ is LA-computable and Problems T and PT are solvable in
$\mathbb{E}$.

Statement 1 of Theorem 3 follows by [28, 24, 42] and statement 2 by [28, 52].
More general difference fields $(\mathbb{F},\sigma)$ can be constructed
provided that certain algorithmic properties hold in $\mathbb{F}$; compare
[51, Sec. 2.3.3]. E.g., one can take $\Pi\Sigma$-field extensions and radical
field extensions [32] over free difference fields [31, 30].

In the following we will obtain an enhanced telescoping algorithm that works
for the following subclass of simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extensions; note that these extensions are
precisely those which are characterized in Thm. 2.

######  Definition 5.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$, $d\in\mathbb{N}_{\geq 0}$ and $Q\subseteq\mathbb{F}[x]$
be $(d,x)$-set $Q$. We call $(\mathbb{S},\sigma)$ an
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F},\sigma)$ also
_$(d,x,Q)$ -reduced_ if the extension is simple and it can be rewritten (after
reordering of the generators) to the form $\mathbb{S}=\mathbb{E}\langle
s_{1}\rangle\dots\langle s_{u}\rangle$ with $\mathbb{E}=\mathbb{F}(x)\langle
t_{1}\rangle\dots\langle t_{e}\rangle$ such that

  * •

$(\mathbb{E},\sigma)$ is an $\mathrm{R}\mathrm{\Pi\Sigma}$-extension of
$(\mathbb{F}(x),\sigma)$ with $x$-degree$\leq d$;

  * •

$(\mathbb{S},\sigma)$ is a $\Sigma$-extension of $(\mathbb{E},\sigma)$ with
$\sigma(s_{i})-s_{i}=p_{i}/q_{i}^{m_{i}}$ where $m_{i}\geq 1$,
$p_{i}\in\mathbb{F}[x]\langle t_{1}\rangle\dots\langle
t_{e}\rangle\setminus\\{0\\}$ and $q_{i}\in Q$ with
$\deg_{x}(p_{i})<m_{i}\deg_{x}(q_{i})$. The $s_{1},\dots,s_{u}$ are also
called the _$Q$ -contributions_.

Given such a $(d,x,Q)$-reduced $\mathrm{R}\mathrm{\Pi\Sigma}$-extension
$(\mathbb{S},\sigma)$ of $(\mathbb{F}(x),\sigma)$ with $f\in\mathbb{E}$ (by
iterative application of the algorithm below), one can construct a
$\Sigma$-extension that is again a $(d,x,Q^{\prime})$ reduced extension (with
$Q\subseteq Q^{\prime}$) and in which one finds $h\in\mathbb{S}^{\prime}$ with
(2).

######  Algorithm 1.

(Finding degree-reduced representations)

Input:

A $\Pi\Sigma$-field extension $(\mathbb{F}(x),\sigma)$ of
$(\mathbb{F},\sigma)$ in which Problem SE is solvable, $d\in\mathbb{N}_{\geq
0}$, a simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension $(\mathbb{E},\sigma)$
of $(\mathbb{F}(x),\sigma)$ with $x$-degree$\leq d$ which is LA-computable and
in which one can solve Problem T, and a $(d,x)$-set
$Q=\\{q_{1},\dots,q_{\lambda}\\}\subseteq\mathbb{F}[x]$ such that the
$\Sigma$-extension $(\mathbb{S},\sigma)$ of $(\mathbb{E},\sigma)$ is
$(d,x,Q)$-reduced $\mathrm{R}\mathrm{\Pi\Sigma}$-extension of
$(\mathbb{F}(x),\sigma)$; $f\in\mathbb{E}$.

Output:

A $(d,x)$ set $Q^{\prime}\supseteq Q$; a $\Sigma$-extension
$(\mathbb{S}^{\prime},\sigma)$ of $(\mathbb{S},\sigma)$ which is a a
$(d,x,Q^{\prime})$-reduced $\mathrm{R}\mathrm{\Pi\Sigma}$-extension
$(\mathbb{S}^{\prime},\sigma)$ of $(\mathbb{F}(x),\sigma)$ together with a
solution $h\in\mathbb{S}^{\prime}$ for (2).

  1. Write $\mathbb{S}=\mathbb{E}[s_{1,1},\dots,s_{1,e_{1}},\dots,s_{\lambda,1},\dots,s_{r,e_{\lambda}}]$ with $e_{i}\in\mathbb{N}_{\geq 0}$, $\sigma(s_{i,j})=s_{i,j}+\frac{p_{i,j}}{q_{i}^{n_{i}}}$, $n_{i,j}\in\mathbb{N}_{\geq 1}$ and $p_{i,j}\in\mathbb{E}$ with $\deg_{x}(p_{i,j})<n_{i,j}\deg_{x}(q_{i})$.

  2. 1

Compute $Q\subseteq\tilde{Q}=\\{q_{1},\dots,q_{r}\\}\subseteq\mathbb{F}[x]$
which is $(d,\operatorname{den}(f))$-complete; see Lemma 3. Set $e_{i}=0$ for
$\lambda<i\leq r$ (i.e., for the elements $\tilde{Q}\setminus Q$).

  3. 2

Compute $f^{\prime},g\in\mathbb{E}$ such that (4) where $f^{\prime}$ is
written in the form (5) with the properties (1)–(4) as given in Lemma 4.

  4. 3

Set $Q^{\prime}=\tilde{Q}$, $\mathbb{S}_{0}=\mathbb{S}$, $u=0$ and $w=0$.

  5. 4

For $i=1$ to $r$ do

  6. 5

If $p_{i}\neq 0$ then

  7. 6

If $e_{i}=0$ then set $B=\\{\\}$

  8. else set $\mu_{i}=\max(n_{i},n_{i,1},\dots,n_{i,e_{i}})$ and compute a basis $B$ of

$\hskip
28.45274ptV_{i}=\text{Ann}_{\mathbb{K}}(q_{i}^{\mu_{i}-n_{i,1}}p_{i,1},\dots,q_{i}^{\mu_{i}-n_{i,{e_{i}}}}p_{i,e_{i}},q_{i}^{\mu_{i}-n_{i}}p_{i})$
(12)

  9. 7

If $B=\\{\\}$ then

  10. 8

Set $u=u+1$ and $Q^{\prime}=Q^{\prime}\cup\\{q_{i}\\}$.

  11. 9

Take a new variable $s_{u}$ being transcendental over $\mathbb{S}_{u-1}$ and
construct the difference ring extension $(\mathbb{S}_{u},\sigma)$ of
$(\mathbb{S}_{u-1},\sigma)$ with $\mathbb{S}_{u}=\mathbb{S}_{u-1}[s_{u}]$ and
$\sigma(s_{u})=s_{u}+\frac{p_{i}}{q_{i}^{n_{i}}}$.

  12. 10

Set $w=w+s_{u}\in\mathbb{S}_{u}$.

  13. else

  14. 11

Set $w=w+c_{1}\,s_{i,1}+\dots+c_{e_{i}}\,s_{i,e_{i}}$ where
$B=\\{(c_{1},\dots,c_{e_{i}},-1)\\}$.

  15. fi

  16. fi

  17. od

  18. 12

Compute, if possible, a $\gamma\in\mathbb{E}$ with
$\sigma(\gamma)-\gamma=\frac{p}{q}$.
If such a $\gamma$ exists, set $g^{\prime}=\gamma$ and
$\mathbb{S}^{\prime}=\mathbb{S}_{u}$. Otherwise, define the ring extension
$(\mathbb{S}^{\prime},\sigma)$ of $(\mathbb{S}_{u},\sigma)$ with the
polynomial ring $\mathbb{S}^{\prime}=\mathbb{S}_{u}[t]$ and
$\sigma(t)=t+\frac{p}{q}$, and set $g^{\prime}=s$.

  19. 13

Return $(h,(\mathbb{S}^{\prime},\sigma),Q^{\prime})$ with
$h=g+g^{\prime}+w\in\mathbb{S}^{\prime}$.

######  Proposition 2.

Algorithm 1 is correct and can be executed in a $\Pi\Sigma$-field
$(\mathbb{F}(x),\sigma)$ as specified in Theorem 3.

###### Proof.

Consider the $i$th loop with $1\leq i\leq r$. For the special case $e_{i}=0$
in step 6 it follows with $p_{i}\neq 0$ that we have $V_{i}=\\{\mathbf{0}\\}$
with the basis $B=\\{\\}$. Otherwise, we compute a basis $B$ of $V_{i}$ and we
proceed. If $B=\\{\\}$ in step 7 then we adjoin a new variable $s_{u}$ which,
for later arguments, we also denote by $s_{i,e^{\prime}_{i}}$ with
$e^{\prime}_{i}=e_{i}+1$. In particular, we set $p_{i,e^{\prime}_{i}}=p_{i}$
and $n_{i,e^{\prime}_{i}}=n_{i}$ and get
$\sigma(s_{e^{\prime}_{i}})-s_{e^{\prime}_{i}}=p_{i,e^{\prime}_{i}}/{q_{i}}^{n_{i,e^{\prime}_{i}}}$.
Otherwise, if $B\neq\\{\\}$, the ring will remain unchanged and we define
$e^{\prime}_{i}=e_{i}$. Note that $|B|=1$. Namely, suppose that we can take
two elements
$\mathbf{c}=(c_{1},\dots,c_{e_{i}+1}),\mathbf{d}=(d_{1},\dots,d_{e_{i}+1})\in
B$ with $\mathbf{c}\neq\mathbf{d}$. If the last component of both vectors is
nonzero, we can assume that it is $1$ by multiplying the vectors with an
appropriate element of $\mathbb{K}$. These normalized vectors must be still
different (since $B$ is a basis). Thus
$\mathbf{e}=\mathbf{c}-\mathbf{d}\neq\mathbf{0}$ where the last entry is $0$.
Removing this last entry gives a vector in
$\text{Ann}_{\mathbb{K}}(q_{i}^{\mu_{i}-n_{i,1}}p_{i,1},\dots,q_{i}^{\mu_{i}-n_{i,{e_{i}}}}p_{i,e_{i}})$
with $\deg_{x}(q_{i}^{\mu_{i}-n_{i,1}}p_{i,1})<\mu_{i}\,\deg_{x}(q_{i})$. Thus
we can apply Theorem 2: $(\mathbb{S},\sigma)$ is not a $\Sigma$-extension of
$(\mathbb{E},\sigma)$, a contradiction. Hence we can suppose that
$B=\\{(c_{1},\dots,c_{e_{i}},-1)\\}$ as stated in step 11.
Now consider the difference ring extension $(\mathbb{S}^{\prime},\sigma)$ of
$(\mathbb{E},\sigma)$ of the output. After reordering and using the renaming
from above we get
$\mathbb{S}^{\prime}=\mathbb{E}^{\prime}[s_{1,1},\dots,s_{1,e^{\prime}_{1}},\dots,s_{r,1},\dots,s_{r,e^{\prime}_{\lambda}}]$
as follows:

  1. (1)

$\mathbb{E}^{\prime}=\mathbb{E}$ in case that one finds a
$\gamma\in\mathbb{E}$ with $\sigma(\gamma)-\gamma=\frac{p}{q}$, or
$\mathbb{E}^{\prime}=\mathbb{E}[t]$ if there is no such $\gamma$. In this case
$(\mathbb{E}^{\prime},\sigma)$ with $\mathbb{E}^{\prime}=\mathbb{E}[t]$ is a
$\Sigma$-extension of $(\mathbb{E},\sigma)$ with $x$-degree$\leq d$ by Theorem
1;

  2. (2)

we have $\sigma(s_{i,j})=s_{i,j}+p_{i,j}/q_{i}^{n_{i}}$ where $q_{i}\in
Q^{\prime}$, $\deg_{x}(p_{i,j})<n_{i}\,\deg_{x}(q_{i})$ and
$V_{i}=\\{\mathbf{0}\\}$ with (12) and with
$\deg_{x}(q_{i}^{\mu_{i}-n_{i,1}}p_{i})<\mu_{i}\deg_{x}(q_{i})$. By Theorem 2,
$(\mathbb{S}^{\prime},\sigma)$ is a $\Sigma$-extension of
$(\mathbb{E}^{\prime},\sigma)$.

In summary, $(\mathbb{S}^{\prime},\sigma)$ is a $(d,x,Q^{\prime})$-reduced
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$. Finally,
we observe that in the steps 9 or 11 we have
$\sigma(s_{u})-s_{u}=p_{i}/q_{i}^{n_{i}}$ with $q_{i}\in Q^{\prime}$ or
$\sigma(b)-b=p_{i}/q_{i}^{n_{i}}$ with
$b=c_{1}s_{i,1}+\dots+c_{e_{i}}s_{i,e_{i}}$. Thus after quitting the for loop
we get $\sigma(w)-w=\sum_{i=1}^{r}p_{i}/q_{i}^{n_{i}}$. With step 12 and (5),
$\sigma(g^{\prime}+w)-(g^{\prime}+f)=f^{\prime}$. Hence with
$h=g+g^{\prime}+w$,

$\sigma(h)-h=(\sigma(g)-g)+(\sigma(g^{\prime}+w)-(g^{\prime}+w))\stackrel{{\scriptstyle\eqref{Equ:RefinedTele}}}{{=}}(f-f^{\prime})+f^{\prime}=f.$
(13)

All steps are executable in $(\mathbb{F}(x),\sigma)$ as given in Thm. 3. ∎

######  Example 3.

We apply Algorithm 1 to $(\mathbb{S},\sigma)$ with $\mathbb{S}=\mathbb{E}$
given in Ex. 1.1, $Q=\\{q_{1}\\}=\\{1+x^{2}\\}$ and $f$ as given in (7). For
step 4 see Ex. 2.1. Since $\mathbb{S}=\mathbb{E}$ and $|Q|=1$, we have $r=1$
and $e_{1}=0$. Furthermore, $p_{1}=0$. Thus we enter step 12 with
$\frac{p}{q}=\frac{-2-4x+x^{2}}{10x^{3}}$. Since there is no
$\gamma\in\mathbb{E}$ with $\sigma(\gamma)-\gamma=\frac{p}{q}$, we can adjoin
the $\Sigma$-monomial $t$ to $\mathbb{E}$ with $\sigma(t)=t+\frac{p}{q}$ and
get the solution $h=g+t$ with $g$ given in (8). We reinterpret $t$ as
$\sum_{i=2}^{k}\frac{3-6i+i^{2}}{10(-1+i)^{3}}=\frac{2+4k-k^{2}}{10k^{3}}-\frac{1}{5}S_{3}(k)-\frac{2}{5}S_{2}(k)+\frac{1}{10}S_{1}(k)$.
Rephrasing $h$ back to the given summation objects and summing (2) over $k$
from $1$ to $n$ yield the right-hand side of (3);

######  Example 4.

Denote the summand on the the left-hand side

$\text{$\sum_{k=1}^{n}$}\frac{(1+k+((1+k)^{2}+k!)k!)(1+k!)-k(1+k)(k!)^{4}}{(1+k)(1+(1+k)k!)(k!)^{3}(1+k!)}\text{$\sum_{i=1}^{k}$}\frac{1}{i!}\\\\[-8.5359pt]
=-\frac{1}{2}+\frac{1}{n!+nn!}-\frac{1}{1+n!+nn!}+\text{$\sum_{i=1}^{n}$}\frac{1}{(i!)^{3}}+\frac{1}{1+n!+nn!}\text{$\sum_{i=1}^{n}$}\frac{1}{i!}$
(14)

by $F(k)$. Take the $\Pi\Sigma$-field $(\mathbb{Q}(x)(\tau),\sigma)$ over
$\mathbb{Q}$ with $\sigma(x)=x+1$, $\sigma(\tau)=(x+1)\tau$ and consider the
simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension $(\mathbb{E},\sigma)$ of
$(\mathbb{Q}(x)(\tau),\sigma)$ with $\sigma(s)=s+\frac{1}{(x+1)\tau}$. Then we
can rephrase $F(k+1)$ by
$f=\frac{(-\tau^{4}sx(1+x)+(1+\tau)(1+x+\tau(\tau+(1+x)^{2})))}{\tau^{3}(1+\tau)(1+x)(1+\tau(1+x))}\in\mathbb{E}$.
Here we set $\mathbb{F}=\mathbb{Q}(x)$ and the $\Pi$-monomial $\tau$ will play
the role of $x$. Note that $\tau^{3}$ is a period $1$ factor. Hence the
extension $(\mathbb{E},\sigma)$ of $(\mathbb{Q}(x)(\tau),\sigma)$ has
$\tau$-degree$\leq 0=d$. Further, $Q=\\{q_{1}\\}$ with $q_{1}=\tau+1$ is
$(0,f)$-complete. We apply Algorithm 1 with $\mathbb{S}=\mathbb{E}$ and get
$g\in\mathbb{E}$ and $f^{\prime}\in\mathbb{E}$ with
$f^{\prime}=\frac{p_{1}}{q_{1}}+\frac{p}{q}$. Namely, $p_{1}=0$,
$\frac{p}{q}=\frac{1+x-\tau^{2}x}{\tau^{3}(1+x)}$ and
$g=-\frac{1}{\tau}+\frac{s}{1+\tau}$. Since there is no
$\gamma\in\mathbb{E}^{\prime}$ with $\sigma(\gamma)-\gamma=\frac{p}{q}$, we
can construct the $\Sigma$-extension $(\mathbb{E}[t],\sigma)$ of
$(\mathbb{E},\sigma)$ with $\sigma(t)=t+\frac{p}{q}$. In particular, $h=g+t$
is a solution of (2). Finally, we rephrase $h$ back to summation objects. Here
$t$ can be interpreted as
$\sum_{i=1}^{k}\frac{i^{3}+(i!)^{2}-i(i!)^{2}}{(i!)^{3}}=-\frac{1}{(k!)^{3}}+\frac{1}{k!}+\sum_{i=1}^{k}\frac{1}{(i!)^{3}}$.
Finally, summing (2) over $k$ one gets the right-hand side of (14).

######  Example 5.

We want to model the sums $T_{1}(n)=\sum_{k=1}^{n}F_{1}(k)$ and
$T_{2}(n)=\sum_{k=2}^{n}F_{2}(k)$ with
$F_{1}(k)=\frac{(1-(-1)^{j})j}{(3-3j+j^{2})(j!)^{2}}\prod_{i=1}^{j}i!$ and

$\displaystyle F_{2}(k)=\Big{(}(-1)^{k-1}$
$\displaystyle(3+(-3+k)k)(1+(-1+k)k)(k!)^{2}+(k-1)\Big{(}\prod_{i=1}^{k}i!\Big{)}\times$
$\displaystyle\Big{(}(-1+(-1)^{k})k(1+n)(1+(-1+k)k)+(1+(-1)^{k})(3+(-3+k)k)k!\Big{)}\Big{/}$
$\displaystyle\hskip
96.73918pt\Big{(}(-1+k)(3-3k+k^{2})(1-k+k^{2})(k!)^{2}\Big{)}$

in a difference ring. Here we start with $(\mathbb{E},\sigma)$ given in Ex.
1.2. First we rephrase $F_{1}(k+1)$ in $\mathbb{E}$ by replacing the objects
$k,(-1)^{k},k!,\prod_{i=1}^{k}i!$ with $x,z,\tau_{1},\tau_{2}$ yielding
$f_{1}\in\mathbb{E}$. Note that $Q=\\{q_{1}\\}$ with $q_{1}=x^{2}-x+1$ is
$(1,f_{1})$-complete. Next, activating Algorithm 1 we get as output the
$(1,x,Q)$-reduced $\mathrm{R}\mathrm{\Pi\Sigma}$-extension
$(\mathbb{S},\sigma)$ of $(\mathbb{E},\sigma)$ with
$\mathbb{S}=\mathbb{E}[s_{1,1}]$ and
$\sigma(s_{1,1})-s_{1,1}=\frac{p_{1,1}}{q_{1}}(=f_{1})$ where
$p_{1,1}=\tau_{2}/\tau_{1}(1+z)$. Now we turn to $T_{2}$. As above we rephrase
$F_{2}(k+1)$ in $\mathbb{S}$ yielding $f:=f_{2}$. Note that $Q$ is again
$(1,f)$-complete. Since there is no $h\in\mathbb{E}$ with (2), we could
activate Theorem 1 (with $m=1$) to get the $\Sigma$-monomial $t$ over
$\mathbb{S}$ with $\sigma(t)=t+f$. But we can do better. Activating again
Algorithm 1 we compute
$g=\frac{\tau_{2}(1+z)}{\tau_{1}(1-x+x^{2})}\in\mathbb{E}$ and
$f^{\prime}\in\mathbb{E}$ such that (4) holds where $f^{\prime}$ has the
$\sigma$-reduced form (5) with $r=1$. Namely, we get
$p_{1}=\tau_{2}/\tau_{1}(-n-nz)$ and $\frac{p}{q}=\frac{z}{x}$. Note that this
time we have $p_{1}\neq 0$ and $e_{1}=1$. Hence we compute for $i=1$ in step 6
the value $\mu_{1}=0$ and the basis $B=\\{(-n,-1)\\}$ of
$\text{Ann}_{\mathbb{Q}}(p_{1,1},p_{1})$ which gives $w=-n\,s(=-n\,s_{1,1})$.
Since there is no $\gamma\in\mathbb{E}$ with
$\sigma(\gamma)-\gamma=\frac{p}{q}$, we can adjoin the $\Sigma$-monomial $t$
to $\mathbb{S}$ with $\sigma(t)-t=\frac{p}{q}=\frac{z}{x}$ and we get the
solution
$h=w+t+g=\frac{\tau_{2}(1+z)}{\tau_{1}(1-x+x^{2})}-n\,s_{1}+t\in\mathbb{S}[t]$
of (2) as output. $t$ can be reinterpreted as
$\sum_{i=2}^{n}(-1)^{i-1}/(i-1)$. Rephrasing $h$ with the given summation
objects and summing (2) over $k$ yield

$T_{2}(n)=2n-n\,T_{1}(n)+\frac{1+(-1)^{n}}{(1-n+n^{2})n!}\text{$\prod_{i=1}^{n}$}i!+\text{$\sum_{i=2}^{n}$}\frac{(-1)^{i-1}}{i-1}.$

Algorithm 1 gives a strategy to find telescoping solutions such that the
denominators have $x$-degrees$\leq d$. In the following we show that this is
the only possible tactic and that it will always lead to a nice solution
whenever it exists in some appropriate extension.

######  Theorem 4.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and let
$Q=\\{q_{1},\dots,q_{r}\\}\subseteq\mathbb{F}[x]$ be a $(d,x)$-set. Let
$(\mathbb{S},\sigma)$ with
$\mathbb{S}=\mathbb{E}[s_{1,1},\dots,s_{1,e_{1}},\dots,s_{r,1},\dots,s_{r,e_{r}}]$
be a $(d,x,Q)$-reduced $\mathrm{R}\mathrm{\Pi\Sigma}$-extension of
$(\mathbb{F}(x),\sigma)$ with $e_{i}\in\mathbb{N}_{\geq 0}$ and where
$s_{i,j}$ are the $Q$-contributions with
$\sigma(s_{i,j})=s_{i,j}+\frac{p_{i,j}}{q_{i}^{n_{i,j}}}$ where
$n_{i,j}\in\mathbb{N}_{\geq 1}$ and $p_{i,j}\in\mathbb{E}$. For
$f\in\mathbb{E}$, take $f^{\prime},g\in\mathbb{E}$ such that (4) where
$f^{\prime}$ is written in the form (5) with the properties (1)–(4) as given
in Lemma 4. Then there is an $h\in\mathbb{S}$ with (2) iff for all $1\leq
i\leq r$ there are $c_{i,j}\in\mathbb{K}=\text{const}_{\sigma}\mathbb{F}$ with

$q_{i}^{\mu_{i}-n_{i}}p_{i}=c_{i,1}q_{i}^{\mu_{i}-n_{i,1}}p_{i,1}+\dots+c_{i,e_{i}}q_{i}^{\mu_{i}-n_{i,{e_{i}}}}p_{i,e_{i}}$
(15)

for $\mu_{i}=\max(n_{i},n_{i,1},\dots,n_{i,e_{i}})$ and there is a
$g^{\prime}\in\mathbb{E}$ with

$\sigma(g^{\prime})-g^{\prime}=\frac{p}{q};$ (16)

if this is the case, $\operatorname{den}(g^{\prime})$ has $x$-degrees$\leq d$
and we get the solution

$h=g+g^{\prime}+\sum_{i=1}^{r}\sum_{j=1}^{e_{i}}c_{i,j}s_{i,j}\in\mathbb{S}.$
(17)

###### Proof.

Suppose there is an $h\in\mathbb{S}$ with (2). Then with (4) we get
$\sigma(\gamma)-\gamma=f^{\prime}$ with $\gamma=h-g\in\mathbb{S}$. In
particular, by [4, Prop. 6.4] it follows that
$\gamma=\sum_{i=1}^{r}\sum_{j=1}^{e_{i}}c_{i,j}s_{i,j}+g^{\prime}$ with
$c_{i,j}\in\mathbb{K}$ and $g^{\prime}\in\mathbb{E}$. Consequently,
$\sigma(g^{\prime})-g^{\prime}=\frac{p^{\prime}_{1}}{q_{1}^{\mu_{1}}}+\dots+\frac{p^{\prime}_{r}}{q_{r}^{\mu_{r}}}$
with
$p^{\prime}_{i}=q_{i}^{\mu_{i}-n_{i}}p_{i}-(c_{i,1}q_{i}^{\mu_{i}-n_{i,1}}p_{i,1}+\dots+c_{i,e_{i}}q_{i}^{\mu_{i}-n_{i,e_{i}}}p_{i,e_{i}})$.
Since $\deg_{x}(p^{\prime}_{i})<\deg_{x}(q_{i})\mu_{i}$, we can apply Prop. 1
and we get $p^{\prime}_{1}=\dots=p^{\prime}_{r}=0$. Thus (15) and (16) hold.
Furthermore, $\operatorname{den}(g^{\prime})$ has $x$-degree $\leq d$ by Prop.
1. Conversely, if (15) holds and there is a $g^{\prime}\in\mathbb{E}$ with
(16), then for $w=\sum_{i=1}^{r}\sum_{j=1}^{e_{i}}c_{i,j}s_{i,j}$ we obtain

$\displaystyle\sigma(g^{\prime}$
$\displaystyle+w)-(g^{\prime}+w)=\frac{p}{q}+\text{$\sum_{i=1}^{r}$}\text{$\sum_{j=1}^{e_{i}}$}c_{i,j}\frac{p_{i,j}}{q_{i}^{n_{i,j}}}$
$\displaystyle=\frac{p}{q}+\text{$\sum_{i=1}^{r}$}\frac{1}{q_{i}^{\mu_{i}}}\text{$\sum_{j=1}^{e_{i}}$}c_{i,j}q_{i}^{\mu_{i}-n_{i,j}}p_{i,j}=\frac{p}{q}+\text{$\sum_{i=1}^{r}$}\frac{q_{i}^{\mu_{i}-n_{i}}\,p_{i}}{q_{i}^{\mu_{i}}}=f^{\prime}.$

Hence with (17) it follows that (13) which completes the proof. ∎

With $\mathbb{S}=\mathbb{E}$ Theorem 4 reduces to Corollary 1.

######  Corollary 1.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and let $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$x$-degree$\leq d$. For $f\in\mathbb{E}$, take $f^{\prime},g\in\mathbb{E}$
such that (4) where $f^{\prime}$ is written in the form (5) with the
properties (1)–(4) as given in Lemma 4. Then there is an $h\in\mathbb{E}$ with
(2) if and only if $p_{1}=\dots=p_{r}=0$ and there is a
$g^{\prime}\in\mathbb{E}$ with (16); if this is the case,
$\operatorname{den}(g^{\prime})$ has $x$-degree$\leq d$ and
$h=g+g^{\prime}\in\mathbb{E}$ is a solution.

The following ”optimal” behavior of Algorithm 1 holds.

######  Corollary 2.

Let $(\mathbb{S},\sigma)$ be $(d,x,Q)$-reduced
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$f\in\mathbb{E}$ as assumed in Algorithm 1 and let $Q^{\prime}$,
$(\mathbb{S}^{\prime},\sigma)$ and $h\in\mathbb{S}^{\prime}$ with (2) be the
output of Algorithm 1. If there is a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension $(\mathbb{H},\sigma)$ of
$(\mathbb{S},\sigma)$ with $x$-degree$\leq d$ with $h^{\prime}\in\mathbb{H}$
where $\sigma(h^{\prime})-h^{\prime}=f$ then the following holds.

  1. 1.

$Q^{\prime}=Q$ and $(\mathbb{S}^{\prime},\sigma)$ is a $\Sigma$-extension of
$(\mathbb{S},\sigma)$ with $x$-degree$\leq d$.

  2. 2.

If $\mathbb{H}=\mathbb{S}$, then $\mathbb{S}^{\prime}=\mathbb{S}$.

  3. 3.

If $h^{\prime}$ in the extension $\mathbb{H}$ is free of the $Q$-contributions
(i.e., free of the $s_{i,j}$) then $h$ is also free of the $Q$-contributions.

###### Proof.

Suppose that there is such an $(\mathbb{H},\sigma)$ with
$h^{\prime}\in\mathbb{H}$ where $\sigma(h^{\prime})-h^{\prime}=f$. Then
$\mathbb{H}=\mathbb{E}^{\prime}[s_{1,1},\dots,s_{1,e^{\prime}_{1}},\dots,s_{r,1},\dots,s_{r,e^{\prime}_{\lambda}}]$
where $(\mathbb{E}^{\prime},\sigma)$ is a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{G}(x),\sigma)$ with
$x$-degree$\leq d$. Now we apply Thm. 4 (with $\mathbb{S}$ and $\mathbb{E}$
replaced by $\mathbb{H}$ and $\mathbb{E}^{\prime}$) and conclude that there
are $c_{i,j}\in\mathbb{K}$ with (15) for $1\leq i\leq r$. If $e_{i}=0$, then
$p_{i}=0$. Otherwise, we have $V_{i}\neq\\{\mathbf{0}\\}$ with the basis
$B=\\{(c_{1},\dots,c_{e_{i}},-1)\\}$. Thus we do not enter in steps 8–10 and
hence $Q=Q^{\prime}$ and $\mathbb{S}_{u}=\mathbb{S}$. If
$\mathbb{H}=\mathbb{S}$, it follows by Thm 4 that there is a
$g^{\prime}\in\mathbb{S}$ with (16). Thus the result is returned in
$\mathbb{S}^{\prime}=\mathbb{S}$. Otherwise, we get
$\mathbb{S}^{\prime}=\mathbb{S}_{u}[t]=\mathbb{S}[t]$ where $t$ is a
$\Sigma$-monomial with $x$-degree$\leq d$. This proves statements 1 and 2 of
the proposition. Furthermore, if $h^{\prime}$ is free of the $s_{i,j}$ then it
follows that $c_{i,j}=0$ in (15). In particular, $p_{i}=0$ for all $1\leq
i\leq r$. Hence we never enter in steps 6–11 and thus $w=0$. Therefore $h$ is
free of the $s_{i,j}$ and statement 3 is proven. ∎

The above results can be turned to parameterized versions. Here we extend only
Corollary 1 yielding Algorithm 1 below.

######  Corollary 3.

Let $(\mathbb{F}(x),\sigma)$ be a $\Pi\Sigma$-field extension of
$(\mathbb{F},\sigma)$ and let $(\mathbb{E},\sigma)$ be a simple
$\mathrm{R}\mathrm{\Pi\Sigma}$-extension of $(\mathbb{F}(x),\sigma)$ with
$\mathbb{E}=\mathbb{F}(x)\langle t_{1}\rangle\dots\langle t_{e}\rangle$ and
$x$-degree$\leq d$. For $f_{1},\dots,f_{m}\in\mathbb{E}^{*}$ let
$Q=\\{q_{1},\dots,q_{r}\\}\subseteq\mathbb{F}[x]$ be $(d,f_{i})$-complete with
$1\leq i\leq m$. Take $f^{\prime}_{i},g_{i}\in\mathbb{E}$ with
$\sigma(g_{i})-g_{i}+f^{\prime}_{i}=f_{i}$ where $f^{\prime}_{i}$ is given by

$f^{\prime}_{i}=\frac{p_{i,1}}{q_{1}^{n_{i,1}}}+\frac{p_{i,r}}{q_{r}^{n_{i,1}}}+\frac{p^{\prime}_{i}}{q^{\prime}_{i}}$
(18)

with the properties (1)–(4) ($p_{j},n_{j}$ replaced by $p_{i,j},n_{i,j}$, and
$p,q$ replaced by $p^{\prime}_{i},q^{\prime}_{i}$) as given in Lemma 4. Let
$\mu_{i}=\max(n_{1,i},\dots,n_{m,i})$ and

$V_{i}=\text{Ann}_{\mathbb{K}}(q_{1}^{\mu_{1}-n_{1,j}}p_{1,j},\dots,q_{1}^{\mu_{m}-n_{m,j}}p_{m,j}).$
(19)

Then with $\mathbf{c}=(c_{1},\dots,c_{m})\in\mathbb{K}^{m}$ the following
holds.

  1. 1.

There is an $h\in\mathbb{E}$ with (1) iff there is a $g^{\prime}\in\mathbb{E}$
with

$\sigma(g^{\prime})-g^{\prime}=c_{1}\,\frac{p^{\prime}_{1}}{q^{\prime}_{1}}+\dots+c_{m}\,\frac{p^{\prime}_{m}}{q^{\prime}_{m}}$
(20)

and $\mathbf{c}\in V_{i}$ holds for all $1\leq j\leq r$; if this is the case,
$\operatorname{den}(g^{\prime})$ has $x$-degree$\leq d$ and
$h=g^{\prime}+\sum_{i=1}^{m}c_{i}\,g_{i}\in\mathbb{E}$ is a solution of (1).

  2. 2.

If $\mathbf{c}\in V_{i}$ for all $1\leq j\leq r$ but there is no
$g^{\prime}\in\mathbb{E}$ with (20), then there is the $\Sigma$-extension
$(\mathbb{E}[t],\sigma)$ of $(\mathbb{E},\sigma)$ with $x$-degree$\leq d$
where
$\sigma(t)-t=c_{1}\,\frac{p^{\prime}_{1}}{q^{\prime}_{1}}+\dots+c_{m}\,\frac{p^{\prime}_{m}}{q^{\prime}_{m}}$,
and $h=t+\sum_{i=1}^{m}c_{i}\,g_{i}$ satisfies (1).

###### Proof.

(1) Define $f:=\sum_{i=1}^{m}c_{i}\,f_{i}$, $g:=\sum_{i=1}^{m}c_{i}\,g_{i}$,
$f^{\prime}=\sum_{i=1}^{m}c_{i}\,f^{\prime}_{i}$,
$p_{j}=\sum_{i=1}^{m}c_{i}\,p_{i,j}$, and $p\in\mathbb{F}[x]\langle
t_{1}\rangle\dots\langle t_{e}\rangle$, $q\in\mathbb{G}[x]$ such that
$\frac{p}{q}:=\sum_{i=1}^{m}c_{i}\frac{p^{\prime}_{i}}{q^{\prime}_{i}}$. With
$f_{i}=\sigma(g_{i})-g_{i}+f^{\prime}_{i}$ for $1\leq i\leq m$ it follows

$f=\text{$\sum_{i=1}^{m}$}c_{i}f_{i}=\sigma\Big{(}\text{$\sum_{i=1}^{m}$}c_{i}g_{i}\Big{)}-\text{$\sum_{i=1}^{m}$}c_{i}g_{i}+\text{$\sum_{i=1}^{m}$}c_{i}f^{\prime}_{i}=\sigma(g)-g-f^{\prime}.$
(21)

One can verify that for $f^{\prime}$ the representation (5) with the
properties (1)–(4) hold. Thus by Corollary 1 if follows that there is an
$h\in\mathbb{E}$ with (2) (i.e., (1) holds) if and only if $p_{j}=0$ for all
$1\leq j\leq r$ (i.e., $\mathbf{c}\in V_{j}$ for all $j$) and there is a
$g^{\prime}\in\mathbb{E}$ with (16) (i.e. (20) holds). Finally, the
irreducible factors in the denominator of $g^{\prime}$ have $x$-degrees$\leq
d$ and $h=g^{\prime}+g\in\mathbb{E}$ is a solution of (1).
(2) Suppose that $\mathbf{c}\in V_{i}$ for all $1\leq j\leq r$. Since there is
no $g^{\prime}\in\mathbb{E}$ with (20), we can apply Theorem 1 with $m=1$, and
it follows that $t$ as given in statement 2 is a $\Sigma$-monomial over
$\mathbb{E}$ where $\operatorname{den}(\sigma(t)-t)$ has $x$-degree$\leq d$.
Furthermore, $g^{\prime}=t$ is a solution of (1). Hence we can apply statement
1 by replacing $\mathbb{E}$ with $\mathbb{E}[t]$ and it follows that
$h=g^{\prime}+g=t+g$ with $c_{1},\dots,c_{m}$ is a solution of (1). ∎

######  Algorithm 2.

(Refined parameterized telescoping)

Input::

A $\Pi\Sigma$-field extension $(\mathbb{F}(x),\sigma)$ of
$(\mathbb{F},\sigma)$ in which Problem SE is solvable; $d\in\mathbb{N}_{\geq
0}$ and an LU-computable simple $\mathrm{R}\mathrm{\Pi\Sigma}$-extension
$(\mathbb{E},\sigma)$ of $(\mathbb{F}(x),\sigma)$ with $x$-degree$\leq d$ in
which Problem PT is solvable;
$\mathbf{f}=(f_{1},\dots,f_{m})\in\mathbb{E}^{m}$.

Output::

A solution
$\mathbf{c}=(c_{1},\dots,c_{m})\in\mathbb{K}^{m}\setminus\\{\mathbf{0}\\}$ and
$h\in\mathbb{E}$ of (1) if it exists. Otherwise a constructive decision if
there is a $\Sigma$-extension $(\mathbb{S},\sigma)$ of $(\mathbb{E},\sigma)$
with $x$-degree$\leq d$ with a solution of
$\mathbf{c}\in\mathbb{K}^{m}\setminus\\{\mathbf{0}\\}$ and $h\in\mathbb{S}$ of
(1).

  1. 1

For $f_{1},\dots,f_{m}\in\mathbb{E}$, compute
$Q=\\{q_{1},\dots,q_{r}\\}\subseteq\mathbb{F}[x]$ which is
$(d,f_{i})$-complete; here one may use a variant of Lemma 3. Further, compute
$f^{\prime}_{i},g_{i}\in\mathbb{E}$ such that
$\sigma(g_{i})-g_{i}+f^{\prime}_{i}=f_{i}$ where $f^{\prime}_{i}$ is written
in the form (18) with the properties (1)–(4) ($p_{j},n_{j}$ replaced by
$p_{i,j},n_{i,j}$, and $p,q$ replaced by $p^{\prime}_{i},q^{\prime}_{i}$) as
given in Lemma 4.

  2. 2

Compute for $1\leq i\leq r$ the bases $B_{i}$ of $V_{i}$ given in (19) with
$\mu_{i}=\max(n_{1,i},\dots,n_{m,i})$. If $B_{i}=\\{\\}$, then stop and output
“no solution”.

  3. 3

Compute a basis $B=\\{(d_{i,1},\dots,c_{i,m})\\}_{1\leq i\leq u}$ of
$V=V_{1}\cap\dots\cap V_{m}$.
If $B=\\{\\}$, i.e., $V=\\{\mathbf{0}\\}$ then stop with the output “no
solution”.

  4. 4

Compute
$(\tilde{f}_{1},\dots,\tilde{f}_{u})^{t}=D\,\Big{(}\frac{p^{\prime}_{1}}{q^{\prime}_{1}},\dots,\frac{p^{\prime}_{m}}{q^{\prime}_{m}}\Big{)}^{t}$
with $D=(d_{i,j})\in\mathbb{K}^{u\times m}$.

  5. 5

Compute, if possible,
$\mathbf{\kappa}=(\kappa_{1},\dots,\kappa_{u})\in\mathbb{K}^{u}\setminus\\{\mathbf{0}\\}$
and $\tilde{g}\in\mathbb{E}$ with

$\sigma(\tilde{g})-\tilde{g}=\kappa_{1}\,\tilde{f}_{1}+\dots+\kappa_{u}\,\tilde{f}_{u}.$
(22)

  6. 6

If there is not such a solution, then take the difference ring extension
$(\mathbb{S},\sigma)$ of $(\mathbb{E},\sigma)$ with the polynomial ring
extension $\mathbb{S}=\mathbb{E}[t]$ and $\sigma(t)=t+\tilde{f}_{1}$. Set
$\tilde{g}=t$, $\mathbf{\kappa}=(1,0,\dots,0)\in\mathbb{K}^{u}$.

  7. 7

Return $(\mathbf{c},h,(\mathbb{S},\sigma))$ with
$\mathbf{c}=\mathbf{\kappa}D\in\mathbb{K}^{m}$,
$h=\tilde{g}+\sum_{i=1}^{m}c_{i}\,g_{i}\in\mathbb{S}$.

######  Proposition 3.

Algorithm 2 is correct and can be executed in a $\Pi\Sigma$-field
$(\mathbb{F}(x),\sigma)$ as specified in Theorem 3.

###### Proof.

Suppose that $V=V_{1}\cap\dots\cap V_{m}=\\{\mathbf{0}\\}$. By Cor. 3.1 there
are no
$\mathbf{c}=(c_{1},\dots,c_{m})\in\mathbb{K}^{m}\setminus\\{\mathbf{0}\\}$ and
$h$ in $(\mathbb{E},\sigma)$ or in a $\Sigma$-extension $(\mathbb{S},\sigma)$
of $(\mathbb{E},\sigma)$ with $x$-degree$\leq d$ which satisfy (1). Thus the
stops in steps 2 and 3 with the output ”no solution” are correct. Now suppose
that there is such a solution $h\in\mathbb{E}$ with
$\mathbf{c}\neq\mathbf{0}$. We conclude with Corollary 3.1 that $\mathbf{c}\in
V$ holds and that there is a $g^{\prime}\in\mathbb{E}$ with (20). Since $B$ is
a basis of $V$, there is a
$\mathbf{b}=(b_{1},\dots,b_{u})\in\mathbb{K}^{u}\setminus\\{\mathbf{0}\\}$
with $\mathbf{b}\,D=\mathbf{c}\neq\mathbf{0}$. Consequently

$b_{1}\,\tilde{f}_{1}+\dots+b_{u}\,\tilde{f}_{u}=\mathbf{b}(\tilde{f}_{1},\dots,\tilde{f}_{u})^{t}=\overbrace{\mathbf{b}\,D}^{\mathbf{c}}(\frac{p^{\prime}_{1}}{q^{\prime}_{1}},\dots,\frac{p^{\prime}_{m}}{q^{\prime}_{m}})^{t}=\sigma(g^{\prime})-g^{\prime}.$

Thus we also find
$\mathbf{\kappa}=(\kappa_{1},\dots,\kappa_{u})\in\mathbb{K}^{u}\setminus\\{\mathbf{0}\\}$
and $\tilde{g}\in\mathbb{E}$ with (22) in step 5. Now consider the output
given in step 7. Then

$\displaystyle c_{1}\,f^{\prime}_{1}$
$\displaystyle+\dots+c_{m}\,f^{\prime}_{m}=\mathbf{c}(f^{\prime}_{1},\dots,f^{\prime}_{m})^{t}=\mathbf{\kappa}D(f^{\prime}_{1},\dots,f^{\prime}_{m})^{t}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}$
$\displaystyle\mathbf{\kappa}D(\frac{p^{\prime}_{1}}{q^{\prime}_{1}},\dots,\frac{p^{\prime}_{m}}{q^{\prime}_{m}})^{t}=\mathbf{\kappa}(\tilde{f}_{1},\dots,\tilde{f}_{u})^{t}=\sigma(\tilde{g}))-\tilde{g};$

here (*) holds since $D$ kills the contributions with denominator factors
having $x$-degrees larger than $d$. With
$\sigma(g_{i})-g_{i}+f^{\prime}_{i}=f_{i}$ and (21) we obtain
$\sum_{i=1}^{m}c_{i}\,f_{i}=\sigma(h)-h$ with
$h=g^{\prime}+\sum_{i=1}^{m}c_{i}g_{i}$. Summarizing, if once can solve
Problem PT in $\mathbb{E}$, the algorithm finds such a solution. Otherwise, we
fail to find $\kappa_{i}\in\mathbb{K}$ and $\tilde{g}\in\mathbb{E}$ with (22).
By Thm. 1, $(\mathbb{S},\sigma)$ given in step 6 is a $\Sigma$-extension of
$(\mathbb{E},\sigma)$ with $x$-degree$\leq d$; Further, for the $\kappa_{i}$
and $g^{\prime}=t$ we have (22). Also for this case the output
$h\in\mathbb{S}$ produces the desired solution. Clearly, the algorithm is
applicable as specified in Theorem 3. ∎

######  Example 6.

Given $(\mathbb{E},\sigma)$ from Ex. 1.3 and $\mathbf{f}\in\mathbb{E}$ as
given in (9) we start Algorithm 2. Step 1 has been carried out in Ex. 2.2.
Next, we compute a basis of
$\text{Ann}_{\mathbb{Q}}(p_{1,1},p_{2,1},p_{3,1})$. Namely,
$B=\\{\mathbf{d}\\}$ with $\mathbf{d}=(d_{1},d_{2},d_{3})=(1,-1,1)$. Finally,
we get
$\tilde{f}_{1}=\sum_{i=1}^{3}d_{i}\rho_{i}=\frac{h_{1}z}{x}+\frac{z}{x}$ with
$u=1$. Since there is no $\kappa_{1}\neq 0$ and $\tilde{g}\in\mathbb{E}$ with
(22), we can adjoin the $\Sigma$-monomial $t$ with
$\sigma(t)-t=\tilde{f}_{1}=\frac{h_{1}z}{x}+\frac{z}{x}$ and set
$\mathbf{\kappa}=(1)$ and $\tilde{g}=t$. Thus
$\mathbf{c}=\mathbf{\kappa}(d_{1},d_{2},d_{3})=(1,-1,1)$ and
$h=\tilde{g}+g_{1}-g_{2}+g_{3}=t-\frac{\text{h1}x-z}{x(1+x^{2})}$ is a
solution of (1) with $m=3$.

Remark. If one is interested in solving Problem PT only in $\mathbb{E}$ (and
not in an extension $\mathbb{S}$), one could also use the algorithms from [51,
52]; compare Thm. 3. However, similarly to the observation in [19], we have
the benefit that Algorithm 2 (in comparison to the ones in [51, 52]) leads to
speedups when complicated denominators arise.

##  5\. Conclusion

We presented telescoping algorithms that enable one to decide algorithmically
if irreducible factors can be eliminated in the input summand $f$. The
algorithms require that the nested sums arising in $f$ have already
representations with nice denominators. In order to be more flexible, we
considered sum extensions in Def. 5 where the outermost sum can have bad
denominators. It would be interesting to see if this can be pushed further to
more complex sums. Here ideas from [5, 36, 6, 22, 43, 17] might be useful to
eliminate denominator factors within unwanted shift-equivalence classes.

Further, one could try to deal with several $\Pi\Sigma$-field monomials (and
not only $x$). This would lead to algorithms that can handle not only the
($q$–)rational but also the multibasic and mixed case [10].

The above algorithm have been implemented in the package Sigma and are
combined with algorithms given in [45, 47, 48, 9, 50] when one has to solve
Problems T and PT in step 12 of Alg. 1 and step 5 of Alg. 2. Thus one can
search in addition for sum representations with optimal nesting depth. This
highly flexible toolbox is crucial to simplify complicated sum expressions
coming, e.g., from particle physics [12, 14, 15].

## References

  * [1] J. Ablinger, J. Blümlein, C. G. Raab, and C. Schneider.  Iterated binomial sums and their associated iterated integrals.  J. Math. Phys., 55(112301):1–57, 2014.  arXiv:1407.1822.
  * [2] J. Ablinger, J. Blümlein, and C. Schneider.  Harmonic sums and polylogarithms generated by cyclotomic polynomials.  J. Math. Phys., 52(10):1–52, 2011.  arXiv:1007.0375.
  * [3] J. Ablinger, J. Blümlein, and C. Schneider.  Analytic and algorithmic aspects of generalized harmonic sums and polylogarithms.  J. Math. Phys., 54(8):1–74, 2013.  arXiv:1302.0378.
  * [4] J. Ablinger and C. Schneider.  Algebraic independence of sequences generated by (cyclotomic) harmonic sums.  Annals of Combinatorics, 22(2):213–244, 2018.  arXiv:1510.03692.
  * [5] S. A. Abramov.  The rational component of the solution of a first-order linear recurrence relation with a rational right-hand side.  U.S.S.R. Comput. Maths. Math. Phys., 15:216–221, 1975.  Transl. from Zh. vychisl. mat. mat. fiz. 15, pp. 1035–1039, 1975.
  * [6] S. A. Abramov.  When does Zeilberger’s algorithm succeed?  Adv. Appl. Math., 30(3):424–441, 2003.
  * [7] S. A. Abramov, M. Bronstein, M. Petkovšek, and C. Schneider.  On rational and hypergeometric solutions of linear ordinary difference equations in $\Pi\Sigma^{*}$-field extensions.  J. Symb. Comput., 107:23–66, 2021.  arXiv:2005.04944 [cs.SC].
  * [8] S. A. Abramov, P. Paule, and M. Petkovšek.  $q$-Hypergeometric solutions of $q$-difference equations.  Discrete Math., 180(1-3):3–22, 1998.
  * [9] S. A. Abramov and M. Petkovšek.  Polynomial ring automorphisms, rational $(w,\sigma)$-canonical forms, and the assignment problem.  J. Symbolic Comput., 45(6):684–708, 2010.
  * [10] A. Bauer and M. Petkovšek.  Multibasic and mixed hypergeometric Gosper-type algorithms.  J. Symbolic Comput., 28(4–5):711–736, 1999.
  * [11] J. Blümlein.  Algebraic relations between harmonic sums and associated quantities.  Comput. Phys. Commun., 159(1):19–54, 2004.  arXiv:hep-ph/0311046.
  * [12] J. Blümlein, M. Kauers, S. Klein, and C. Schneider.  Determining the closed forms of the $O(a_{s}^{3})$ anomalous dimensions and Wilson coefficients from Mellin moments by means of computer algebra.  Comput. Phys. Commun., 180:2143–2165, 2009.  arXiv:0902.4091.
  * [13] J. Blümlein and S. Kurth.  Harmonic sums and Mellin transforms up to two-loop order.  Phys. Rev., D60, 1999.
  * [14] J. Blümlein, P. Marquard, C. Schneider, and K. Schönwald.  The massless three-loop Wilson coefficients for the deep-inelastic structure functions $F_{2},F_{L},xF_{3}$ and $g_{1}$.  Journal of High Energy Physics, (Paper No. 156):1–83, 2022.  arXiv:2208.14325 [hep-ph].
  * [15] J. Blümlein, P. Marquard, C. Schneider, and K. Schönwald.  The three-loop polarized singlet anomalous dimensions from off-shell operator matrix elements.  Journal of High Energy Physics, 2022(193):0–32, 2022.  arXiv:2111.12401 [hep-ph].
  * [16] M. Bronstein.  On solutions of linear ordinary difference equations in their coefficient field.  J. Symbolic Comput., 29(6):841–877, 2000.
  * [17] S. Chen, F. Chyzak, R. Feng, G. Fu, and Z. Li.  On the existence of telescopers for mixed hypergeometric terms.  J. Symbolic Comput., 68(part 1):1–26, 2015.
  * [18] S. Chen, R. Feng, G. Fu, and Z. Li.  On the structure of compatible rational functions.  In Proceedings of ISSAC 2011, pages 91–98, 2011.
  * [19] S. Chen, H. Huang, M. Kauers, and Z. Li.  A modified Abramov-Petkovsek reduction and creative telescoping for hypergeometric terms.  In K. Yokoyama, S. Linton, and D. Robertz, editors, Proc. ISSAC 2015, pages 117–124. ACM, 2015.
  * [20] S. Chen, M. Jaroschek, M. Kauers, and M. F. Singer.  Desingularization explains order-degree curves for Ore operators.  In M. Kauers, editor, Proc. of ISSAC 2013, pages 157–164, 2013\.
  * [21] S. Chen and M. Kauers.  Order-degree curves for hypergeometric creative telescoping.  In J. van der Hoeven and M. van Hoeij, editors, Proceedings of ISSAC 2012, pages 122–129, 2012.
  * [22] W. Y. C. Chen, Q. Hou, and Y. Mu.  Applicability of the q-analogue of Zeilberger’s algorithm.  J. Symb. Comput., 39(2):155–170, 2005.
  * [23] F. Chyzak.  An extension of Zeilberger’s fast algorithm to general holonomic functions.  Discrete Math., 217:115–134, 2000.
  * [24] G. Ge.  Algorithms related to the multiplicative representation of algebraic numbers.  PhD thesis, Univeristy of California at Berkeley, 1993.
  * [25] R. W. Gosper.  Decision procedures for indefinite hypergeometric summation.  Proc. Nat. Acad. Sci. U.S. A., 75:40–42, 1978.
  * [26] C. Hardouin and M. F. Singer.  Differential Galois theory of linear difference equations.  Math. Ann., 342(2):333–377, 2008.
  * [27] P. A. Hendriks and M. F. Singer.  Solving difference equations in finite terms.  J. Symbolic Comput., 27(3):239–259, 1999.
  * [28] M. Karr.  Summation in finite terms.  J. ACM, 28:305–350, 1981.
  * [29] M. Karr.  Theory of summation in finite terms.  J. Symbolic Comput., 1:303–315, 1985.
  * [30] M. Kauers and C. Schneider.  Application of unspecified sequences in symbolic summation.  In J. Dumas, editor, Proc. ISSAC’06., pages 177–183. ACM Press, 2006.
  * [31] M. Kauers and C. Schneider.  Indefinite summation with unspecified summands.  Discrete Math., 306(17):2021–2140, 2006.
  * [32] M. Kauers and C. Schneider.  Symbolic summation with radical expressions.  In C. Brown, editor, Proc. ISSAC’07, pages 219–226, 2007.
  * [33] C. Koutschan.  Creative telescoping for holonomic functions.  In C. Schneider and J. Blümlein, editors, Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts and Monographs in Symbolic Computation, pages 171–194. Springer, 2013.  arXiv:1307.4554.
  * [34] E. D. Ocansey and C. Schneider.  Representing (q-)hypergeometric products and mixed versions in difference rings.  In C. Schneider and E. Zima, editors,  Advances in Computer Algebra. WWCA 2016., volume 226 of Springer Proceedings in Mathematics & Statistics, pages 175–213. Springer, 2018.  arXiv:1705.01368.
  * [35] E. D. Ocansey and C. Schneider.  Representation of hypergeometric products of higher nesting depths in difference rings.  RISC Report Series 20-19, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria, 2020.  arXiv:2011.08775.
  * [36] P. Paule.  Greatest factorial factorization and symbolic summation.  J. Symbolic Comput., 20(3):235–268, 1995.
  * [37] P. Paule and A. Riese.  A Mathematica $q$-analogue of Zeilberger’s algorithm based on an algebraically motivated approach to $q$-hypergeometric telescoping.  In M. Ismail and M. Rahman, editors, Special Functions, q-Series and Related Topics, volume 14, pages 179–210. AMS, 1997.
  * [38] M. Petkovšek.  Hypergeometric solutions of linear recurrences with polynomial coefficients.  J. Symbolic Comput., 14(2-3):243–264, 1992.
  * [39] M. Petkovšek and H. Zakrajšek.  Solving linear recurrence equations with polynomial coefficients.  In C. Schneider and J. Blümlein, editors, Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts and Monographs in Symbolic Computation, pages 259–284. Springer, 2013.
  * [40] M. van Hoeij.  Finite singularities and hypergeometric solutions of linear recurrence equations.  J. Pure Appl. Algebra, 139(1-3):109–131, 1999.
  * [41] C. Schneider.  Symbolic summation in difference fields.  Technical Report 01-17, RISC-Linz, J. Kepler University, November 2001\.  PhD Thesis.
  * [42] C. Schneider.  Product representations in ${\Pi}{\Sigma}$-fields.  Ann. Comb., 9(1):75–99, 2005.
  * [43] C. Schneider.  Simplifying sums in $\Pi\Sigma$-extensions.  J. Algebra Appl., 6(3):415–441, 2007.
  * [44] C. Schneider.  Symbolic summation assists combinatorics.  Sém. Lothar. Combin., 56:1–36, 2007.  Article B56b.
  * [45] C. Schneider.  A refined difference field theory for symbolic summation.  J. Symbolic Comput., 43(9):611–644, 2008.  arXiv:0808.2543v1.
  * [46] C. Schneider.  Parameterized telescoping proves algebraic independence of sums.  Ann. Comb., 14:533–552, 2010.  arXiv:0808.2596; for a preliminary version see FPSAC 2007.
  * [47] C. Schneider.  Structural theorems for symbolic summation.  Appl. Algebra Engrg. Comm. Comput., 21(1):1–32, 2010.
  * [48] C. Schneider.  A symbolic summation approach to find optimal nested sum representations.  In A. Carey, D. Ellwood, S. Paycha, and S. Rosenberg, editors, Motives, Quantum Field Theory, and Pseudodifferential Operators, volume 12 of Clay Mathematics Proceedings, pages 285–308. Amer. Math. Soc, 2010.  arXiv:0808.2543.
  * [49] C. Schneider.  A streamlined difference ring theory: Indefinite nested sums, the alternating sign and the parameterized telescoping problem.  In F. Winkler, V. Negru, T. Ida, T. Jebelean, D. Petcu, S. Watt, and D. Zaharie, editors, Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 15th International Symposium, pages 26–33. IEEE Computer Society, 2014.  arXiv:1412.2782.
  * [50] C. Schneider.  Fast algorithms for refined parameterized telescoping in difference fields.  In M. W. J. Guitierrez, J. Schicho, editor, Computer Algebra and Polynomials, number 8942 in Lecture Notes in Computer Science (LNCS), pages 157–191. Springer, 2015.  arXiv:1307.7887.
  * [51] C. Schneider.  A difference ring theory for symbolic summation.  J. Symb. Comput., 72:82–127, 2016.  arXiv:1408.2776.
  * [52] C. Schneider.  Summation Theory II: Characterizations of $R\Pi\Sigma$-extensions and algorithmic aspects.  J. Symb. Comput., 80(3):616–664, 2017.  arXiv:1603.04285.
  * [53] C. Schneider.  Minimal representations and algebraic relations for single nested products.  Programming and Computer Software, 46(2):133–161, 2020.  arXiv:1911.04837.
  * [54] C. Schneider.  Term algebras, canonical representations and difference ring theory for symbolic summation.  In J. Blümlein and C. Schneider, editors, Anti-Differentiation and the Calculation of Feynman Amplitudes, Texts and Monographs in Symbolic Computuation, pages 423–485. Springer, 2021.  arXiv:2102.01471 [cs.SC], RISC-Linz Report Series No. 21-03.
  * [55] J. A. M. Vermaseren.  Harmonic sums, Mellin transforms and integrals.  Int. J. Mod. Phys., A14:2037–2976, 1999.
  * [56] D. Zeilberger.  A holonomic systems approach to special functions identities.  J. Comput. Appl. Math., 32:321–368, 1990.
  * [57] D. Zeilberger.  The method of creative telescoping.  J. Symbolic Comput., 11:195–204, 1991.