# Separability Problems in Creative Telescoping ††thanks: S. Chen was
partially supported by the NSFC grants 11871067, 11688101, the Fund of the
Youth Innovation Promotion Association, CAS, and the National Key Research and
Development Project 2020YFA0712300. R. Feng was partially supported by the
NSFC grants 11771433, 11688101, and Beijing Natural Science Foundation under
Grant Z190004. P. Ma was partial supported by the NSFC grants 11871067. M.F.
Singer was partially supported by by a grant from the Simons Foundation (No.
349357, Michael Singer)

Shaoshi Chena,b, Ruyong Fenga,b,

Pingchuan Maa,b, and Michael F. Singerc
aKLMM, Academy of Mathematics and Systems Science,
Chinese Academy of Sciences,
Beijing, 100190, China
bSchool of Mathematical Sciences,
University of Chinese Academy of Sciences,
Beijing 100049, (China)
cDepartment of Mathematics,
North Carolina State University,
Raleigh, NC 27695, (USA)
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For given multivariate functions specified by algebraic, differential or
difference equations, the separability problem is to decide whether they
satisfy linear differential or difference equations in one variable. In this
paper, we will explain how separability problems arise naturally in creative
telescoping and present some criteria for testing the separability for several
classes of special functions, including rational functions, hyperexponential
functions, hypergeometric terms, and algebraic functions.

##  1 Introduction

The method of separation of variables has been used widely in solving
differential equations [21]. In order to solve the one-dimensional heat
equation

$\frac{\partial y}{\partial t}-c\frac{\partial^{2}y}{\partial
x^{2}}=0,\,\,\text{where $c\in{\mathbb{C}}$},$

together with the boundary conditions $y(t,0)=y(t,L)=0$. One can try to find a
nonzero solution of the form

$y=u(t)v(x),$

and then substitute this form into the equation to get

$\frac{\frac{\partial
u(t)}{{\partial}t}}{u}=c\frac{\frac{\partial^{2}v(x)}{{\partial}x^{2}}}{v}.$

Since both sides only depend on one variable, there exits some constant
$\lambda\in{\mathbb{C}}$ such that

$\frac{\partial u}{\partial t}-\lambda u=0\quad\text{and}\quad
c\frac{\partial^{2}v}{\partial x^{2}}-\lambda v=0.$

Note that the above two equations are also satisfied by $y=u(t)v(x)$, which
are linear differential equation in only one variable. After solving these
special equations with the boundary conditions into account, a special
solution of the heat equation can be given as

$y(t,x)=\sum_{n=1}^{\infty}d_{n}\sin\left(\frac{n\pi
x}{L}\right)\exp\left(-\frac{n^{2}\pi^{2}ct}{L^{2}}\right),$ (1.1)

where $d_{n}\in{\mathbb{C}}$ are coefficients determined by the initial
conditions. Motivated by this example, one would ask the following natural
question.

######  Problem 1.1 (Separability Problem).

Given a multivariate function specified by certain equations (e.g. algebraic,
differential or difference equations), decide whether this function satisfies
linear differential or difference equations in one variable.

To make the problem more tractable, we will consider some special classes of
functions, such as rational functions, algebraic functions, hyperexponential
functions and hypergeometric terms etc.. The main goal of this paper is to
show the close connection between the separability problem and Zeilberger’s
method of creative telescoping [27, 28].

The remainder of this paper is organized as follows. We specify the
separability problem and the existence problem of telescopers precisely in
Section 2 together with the definition of orders and (local) dispersions of
rational functions. After this, we explain how the separability problems arise
naturally in creative telescoping for rational functions in Section 3,
hyperexponential functions and hypergeometric terms in Section 4, and for
algebraic functions in Section 5. Separability criteria will be given for
these classes of special functions. We then conclude our paper with some
comments on the separability problem on D-finite functions and P-recursive
sequences.

##  2 Preliminaries

Let ${\mathbb{F}}$ be a field of characteristic zero and let
${{\mathbb{E}}={\mathbb{F}}(t,{\bf x})}$ be the field of rational functions in
$t$ and ${\bf x}=(x_{1},\ldots,x_{m})$ over ${\mathbb{F}}$. Let
$\delta_{t},\delta_{x_{i}}$ be the usual partial derivations
${\partial}/{\partial}_{t},{\partial}/{\partial}_{x_{i}}$ with
$x_{i}\in\\{x_{1},\ldots,x_{m}\\}$, respectively. The shift operators
$\sigma_{t}$ and $\sigma_{x_{i}}$ on ${\mathbb{E}}$ are defined as the
${\mathbb{F}}$-automorphisms such that for any $f\in{\mathbb{E}}$,
$\sigma_{t}(f(t,{\bf x}))=f(t+1,{\bf x})$ and

$\sigma_{x_{i}}(f(t,{\bf
x}))=f(t,x_{1},\ldots,x_{i-1},x_{i}+1,x_{i+1},\ldots,x_{m}).$

The ring of linear functional operators in $t$ and ${\bf x}$ over
${\mathbb{E}}$ is denoted by ${\mathbb{E}}\langle\partial_{t},\partial_{{\bf
x}}\rangle$, where $\partial_{{\bf
x}}=({\partial}_{x_{1}},\ldots,{\partial}_{x_{m}})$ and $\partial_{v}$ with
$v\in\\{t,{\bf x}\\}$ is either the derivation $D_{v}$ such that
$D_{v}f=fD_{v}+\delta_{v}(f)$ or the shift operator $S_{v}$ such that
$S_{v}f=\sigma_{v}(f)S_{v}$ for any $f\in{\mathbb{E}}$, and $\partial_{t}$ and
$\partial_{x_{i}}$ commute. For $v\in\\{t,{\bf x}\\}$, we let $\Delta_{v}$
denote the difference operator $S_{v}-{\bf 1}$, where ${\bf 1}$ stands for the
identity map on ${\mathbb{E}}$. Abusing notation, we let $\delta_{v}$ and
$\sigma_{v}$ denote arbitrary extensions of $\delta_{v}$ and $\sigma_{v}$ to
derivation and $\overline{\mathbb{F}}$-automorphism of
$\overline{{\mathbb{E}}}$, the algebraic closure of ${\mathbb{E}}$. The
functions we consider will be in certain differential or difference extension
of ${\mathbb{E}}$, which is also an
${\mathbb{E}}\langle\partial_{t},\partial_{{\bf x}}\rangle$-module via the
action defined by simply interpreting $D_{v},S_{v}$ by
$\delta_{v},\sigma_{v}$, respectively, for $v\in\\{t,{\bf x}\\}$. The ring
${\mathbb{F}}(t)\langle\partial_{t}\rangle$ is a subring of
${\mathbb{E}}\langle\partial_{t},\partial_{{\bf x}}\rangle$ that is also a
left Euclidean domain. Efficient algorithms for basic operations in
${\mathbb{F}}(t)\langle\partial_{t}\rangle$, such as computing the least
common left multiple (LCLM) of operators, have been developed in [10, 6].

######  Definition 2.1 (Separable functions).

Let $\mathfrak{M}$ be an ${\mathbb{E}}\langle\partial_{t},{\partial}_{{\bf
x}}\rangle$-module and $f\in\mathfrak{M}$. We say that $f(t,{\bf x})$ is
_$\partial_{t}$ -separable_ if there exists a nonzero
$L\in{\mathbb{F}}(t)\langle\partial_{t}\rangle$ such that $L(f)=0$.

As an example, the special solution (1.1) of the one-dimensional heat equation
is both $D_{t}$-separable and $D_{x}$-separable. Note that
$\partial_{t}$-separable functions are just the D-finite functions in the
differential case and the P-recursive sequences in the shift case, which are
both introduced in [26]. By the closure properties of D-finite functions and
P-recursive sequences, we have the same closure properties for
$\partial_{t}$-separable functions.

######  Proposition 2.2.

Let $\mathfrak{M}$ be an ${\mathbb{E}}\langle\partial_{t},{\partial}_{{\bf
x}}\rangle$-module. If $f,g\in\mathfrak{M}$ are $\partial_{t}$-separable, so
are $f+g,f\cdot g$, and $a\cdot f$ for all $a\in{\mathbb{F}}(t)$.

We will focus on the separability problem on function in an
${\mathbb{E}}\langle\partial_{t},{\partial}_{{\bf x}}\rangle$-module.

######  Definition 2.3 (Creative telescoping).

Let $\mathfrak{M}$ be an ${\mathbb{E}}\langle\partial_{t},{\partial}_{{\bf
x}}\rangle$-module and $f\in\mathfrak{M}$. A nonzero operator
$L\in{\mathbb{F}}(t)\langle\partial_{t}\rangle$ is called a _telescoper_ of
type $(\partial_{t},\partial_{{\bf x}})$ for $f$ if there exist
$Q_{1},\ldots,Q_{m}\in{\mathbb{E}}\langle\partial_{t},{\partial}_{{\bf
x}}\rangle$ such that

$L(t,{\partial}_{t})(f)=\partial_{x_{1}}(Q_{1}(f))+\cdots+\partial_{x_{m}}(Q_{m}(f)),$
(2.1)

where $\partial_{t}\in\\{D_{t},S_{t}\\}$ and
$\partial_{x_{i}}\in\\{D_{x_{i}},\Delta_{x_{i}}\\}$.

The central problem in the Wilf-Zeilberger theory of automatic proving of
special-function identities is related to the existence and the computation of
telescopers for special functions. In the next sections, we will show that
this central problem on creative telescoping is closely connected to the
separability problem on the corresponding class of special functions.

Let $V=(V_{1},\ldots,V_{s})$ be any set partition of the variables ${\bf
v}=\\{t,x_{1},\ldots,x_{m}\\}$. A rational function $f\in{\mathbb{F}}(t,{\bf
x})$ is said to be _split_ with respect to the partition $V$ if $f=f_{1}\cdots
f_{s}$ with $f_{i}\in{\mathbb{F}}(V_{i})$ and be _semi-split_ with respect to
$V$ if there are split functions $g_{j}\in{\mathbb{F}}(t,{\bf x})$ such that
$f=g_{1}+\cdots+g_{n}$. By definition, we have $f=p/q$ with
$p,q\in{\mathbb{F}}[t,{\bf x}]$ and $\gcd(p,q)=1$ is semi-split with respect
to the partition $V$ if and only if the denominator $q$ is a split polynomial
with respect to the partition $V$. Split rational functions will be used to
describe the separability of given functions.

Let ${\mathbb{K}}={\mathbb{F}}({\bf x})$ and $p\in{\mathbb{K}}[t]$ be an
irreducible polynomial in $t$. For any $f\in{\mathbb{K}}(t)$, we can write
$f=p^{m}a/b$, where $m\in{\mathbb{Z}},a,b\in{\mathbb{K}}[t]$ with
$\gcd(a,b)=1$ and $p\nmid ab$. Conventionally, we set $\nu_{p}(0)=+\infty$.
The integer $m$ is called the _order_ of $f$ at $p$, denoted by $\nu_{p}(f)$.
We collect some basic properties of valuations as follows and refer to [9,
Chapter 4] for their proofs.

######  Proposition 2.4.

Let $f,g\in{\mathbb{K}}(t)$ and $p\in{\mathbb{K}}[t]$ be an irreducible
polynomial. Then,

  * $(i)$

$\nu_{p}(fg)=\nu_{p}(f)+\nu_{p}(g)$.

  * $(ii)$

$\nu_{p}(f+g)\geq{\rm min}\\{\nu_{p}(f),\nu_{p}(g)\\}$ and equality holds if
$\nu_{p}(f)\neq\nu_{p}(g)$.

  * $(iii)$

If $\nu_{p}(f)\neq 0$, then $\nu_{p}(D_{t}(f))=\nu_{p}(f)-1$. In particular,
for any $i\in{\mathbb{N}}$, $\nu_{p}(D_{t}^{i}(f))=\nu_{p}(f)-i$ if
$\nu_{p}(f)<0$.

The dispersion introduced by Abramov in [1] can be viewed as a shift analogue
of the order. For any polynomial $u\in{\mathbb{K}}[t]$ with $\deg_{t}(u)\geq
1$, the _dispersion_ of $u$, denoted by $\text{dis}(u)$, is defined as
$\max\\{k\in{\mathbb{N}}\mid\gcd(u,\sigma_{t}^{k}(u))\neq 1\\}$, which is the
maximal integer root-distance $|\alpha-\beta|$ with $\alpha,\beta$ being roots
of $u$ in $\bar{K}$. Define $\text{dis}(u)=0$ if $u\in K\setminus\\{0\\}$ and
$\text{dis}(0)=+\infty$. For a rational function $f=a/b\in{\mathbb{K}}(t)$
with $a,b\in{\mathbb{K}}[t]$ and $\gcd(a,b)=1$, define
$\text{dis}(f)=\text{dis}(b)$. For later use, we introduce a local version of
Abramov’s dispersion. Let $p\in{\mathbb{K}}[t]$ be an irreducible polynomial.
If $\sigma_{t}^{i}(p)\mid u$ for some $i\in{\mathbb{Z}}$, the _local
dispersion_ of $u$ at $p$, denoted by $\text{dis}_{p}(u)$, is defined as the
maximal integer distance $|i-j|$ with $i,j\in{\mathbb{Z}}$ satisfying
$\sigma_{t}^{i}(p)\mid u$ and $\sigma_{t}^{j}(p)\mid u$; otherwise we define
$\text{dis}_{p}(u)=0$. Conventionally, we set $\text{dis}_{p}(0)=+\infty$. For
a rational function $f=a/b\in{\mathbb{K}}(t)$ with $a,b\in{\mathbb{K}}[t]$ and
$\gcd(a,b)=1$, we also define $\text{dis}_{p}(f)=\text{dis}_{p}(b)$. By
definition, we have

$\text{dis}(u)=\max\\{\text{dis}_{p}(u)\mid\text{$p$ is an irreducible factor
of $u$}\\}.$

The set $\\{\sigma_{t}^{i}(p)\mid i\in{\mathbb{Z}}\\}$ is called the
$\sigma_{t}$-orbit at $p$, denoted by $[p]_{\sigma_{t}}$. Note that
$\text{dis}_{p}(u)=\text{dis}_{q}(u)$ if $q\in[p]_{\sigma_{t}}$. So we can
define the local dispersion of a rational function $f$ at a $\sigma_{t}$-orbit
at $p$, denoted by $\text{dis}_{[p]_{\sigma_{t}}}(f)$.

######  Example 2.5.

Let $u=x(x+1)(x-5)(x^{2}+1)(x^{2}+4x+5)\in{\mathbb{Q}}[x]$. Then we have
$\text{dis}_{x}(u)=6$ and $\text{dis}_{x^{2}+1}(u)=2$. Abramov’s dispersion of
$u$ is then equal to $6$.

We now shows how the local dispersions change under the action of linear
recurrence operators, which was first proved for Abramov’s dispersions in [1,
2] and [23, Section 3.1].

######  Lemma 2.6.

Let $f=a/b\in{\mathbb{K}}(t)$ with $a,b\in{\mathbb{K}}[t]$ and $\gcd(a,b)=1$
and let $p\in{\mathbb{K}}[t]$ be an irreducible factor of $b$. Let
$L=\sum_{i=0}^{\rho}\ell_{i}S_{t}^{i}\in{\mathbb{K}}[t]\langle S_{t}\rangle$
be such that $\ell_{\rho}\ell_{0}\neq 0$ and $\sigma^{i}_{t}(p)$ does not
divide $\ell_{\rho}\ell_{0}$ for any $i\in{\mathbb{Z}}$. Then
$\text{dis}_{p}(L(f))=\text{dis}_{p}(f)+\rho$. In particular,
$\text{dis}_{p}(\Delta_{t}(f))=\text{dis}_{p}(f)+1$.

###### Proof.

Let $d=\text{dis}_{p}(b)$. Without loss of generality, we may assume that
$p\mid b$ but $\sigma_{t}^{i}(p)\nmid b$ for any $i<0$. Since $\gcd(a,b)=1$
and $\sigma_{t}$ is a ${\mathbb{K}}$-automorphism of ${\mathbb{K}}[t]$, we
have $\gcd(\sigma_{t}^{i}(a),\sigma_{t}^{i}(b))=1$ for any $i\in{\mathbb{Z}}$.
Applying $L$ to $f$ yields

$L(f)=\sum_{i=0}^{\rho}\ell_{i}\sigma_{t}^{i}\left(\frac{a}{b}\right)=\frac{\sum_{i=0}^{\rho}\ell_{i}\sigma_{t}^{i}(a)u_{i}}{u},$

where $u=b\sigma_{t}(b)\cdots\sigma_{t}^{\rho}(b)$ and
$u_{i}=u/\sigma_{t}^{i}(b)$. Write $L(f)=A/B$ with $A,B\in{\mathbb{K}}[t]$ and
$\gcd(A,B)=1$. Then $B\mid u$ and $\text{dis}_{p}(L(f))=\text{dis}_{p}(B)$ by
definition. Since $\sigma_{t}^{i}(p)\nmid\ell_{0}$ and
$\sigma_{t}^{i}(p)\nmid\ell_{\rho}$ for any $i\in{\mathbb{Z}}$, we have both
$p$ and $\sigma_{t}^{d+\rho}(p)$ do not divide the sum
$\sum_{i=0}^{\rho}\ell_{i}\sigma_{t}^{i}(a)u_{i}$, but they divide $u$. So
$p\mid B$ and $\sigma_{t}^{d+\rho}(p)\mid B$, which implies that
$\text{dis}_{p}(B)\geq d+\rho$. Since $B\mid u$, we have
$\text{dis}_{p}(B)\leq\text{dis}_{p}(u)=d+\rho$. Therefore,
$\text{dis}_{p}(L(f))=d+\rho$.

##  3 The rational case

We first explain how the existence problem of telescopers for rational
functions is naturally connected to the separability problem on this class of
functions. Let $f(t,x)$ be a bivariate rational function in
${\mathbb{F}}(t,x)$. By the Ostrogradsky-Hermite reduction [22, 18], we can
decompose $f$ into the form

$f=D_{x}(g)+\frac{a}{b},$

where $g\in{\mathbb{F}}(t,x)$ and $a,b\in{\mathbb{F}}(t)[x]$ with
$\gcd(a,b)=1$, $\deg_{x}(a)<\deg_{x}(b)$ and $b$ being squarefree in $x$ over
${\mathbb{F}}(t)$. Moreover, $f=D_{x}(h)$ for some $h\in{\mathbb{F}}(t,x)$ if
and only if $a=0$. Then $f$ has a telescoper of type $(S_{t},D_{x})$ if and
only if $a/b$ does. Applying a nonzero operator
$L=\sum_{i=0}^{\rho}\ell_{i}S_{t}^{i}\in{\mathbb{F}}(t)\langle S_{t}\rangle$
to $a/b$ yields

$L\left(\frac{a}{b}\right)=\sum_{i=0}^{\rho}\ell_{i}(t)\sigma_{t}^{i}\left(\frac{a}{b}\right)=\sum_{i=0}^{\rho}\frac{\ell_{i}(t)a(t+i,x)}{b(t+i,x)}=\frac{p}{q},$

where $p,q\in{\mathbb{F}}[t,x]$ with $\gcd(p,q)=1$. Since the shift operator
$S_{t}$ is an ${\mathbb{F}}(x)$-automorphism and preserves the degrees in $t$
and $x$, we have $b(t+i,x)$ is squarefree in $x$ over ${\mathbb{F}}(t)$ for
any $i\in{\mathbb{N}}$ and $\deg_{x}(a(t+i,x))<\deg_{x}(b(t+i,x))$. So
$\deg_{x}(p)<\deg_{x}(q)$ and $q$ is also squarefree in $x$ over
${\mathbb{F}}(t)$. This implies the operator $L$ is a telescoper of type
$(S_{t},D_{x})$ for $a/b$, i.e., $L(a/b)=D_{x}(g)$ for some
$g\in{\mathbb{F}}(t,x)$ if and only if $p=0$, i.e., $L(a/b)=0$. Therefore, we
conclude that $f$ has a telescoper of type $(S_{t},D_{x})$ if and only $a/b$
is $S_{t}$-separable.

We can also consider telescopers of type $(D_{t},S_{x})$. By Abramov’s
reduction [3, 4], we can decompose $f\in{\mathbb{F}}(t,x)$ into the form

$f=\Delta_{x}(g)+\frac{a}{b},$

where $g\in{\mathbb{F}}(t,x)$ and $a,b\in{\mathbb{F}}(t)[x]$ with
$\gcd(a,b)=1$, $\deg_{x}(a)<\deg_{x}(b)$ and $b$ being shift-free in $x$ over
${\mathbb{F}}(t)$, i.e., $\gcd(b,\sigma_{x}^{i}(b))=1$ for all nonzero
$i\in{\mathbb{Z}}$. Applying a nonzero operator
$L=\sum_{i=0}^{\rho}\ell_{i}(t)D_{t}^{i}\in{\mathbb{F}}(t)\langle
D_{t}\rangle$ to $a/b$ yields

$L\left(\frac{a}{b}\right)=\sum_{i=0}^{\rho}\ell_{i}\delta_{t}^{i}\left(\frac{a}{b}\right)=\sum_{i=0}^{\rho}\frac{\ell_{i}(t)a_{i}}{b^{i+1}}=\frac{p}{q},$

where $a_{i},p,q\in{\mathbb{F}}[t,x]$ with $\deg_{x}(a_{i})<(i+1)\deg_{x}(b)$
and $\gcd(p,q)=1$. Since $b$ is shift-free in $x$, so is $b^{i}$ for any
$i\in{\mathbb{N}}$. Note that any factor of a shift-free polynomial is still
shift-free. So $q$ is shift-free and $\deg_{x}(p)<\deg_{x}(q)$. This implies
the operator $L$ is a telescoper of type $(D_{t},S_{x})$ for $a/b$, i.e.,
$L(a/b)=\Delta_{x}(g)$ for some $g\in{\mathbb{F}}(t,x)$ if and only if $p=0$,
i.e., $L(a/b)=0$. Then we also have that $f$ has a telescoper of type
$(D_{t},S_{x})$ if and only $a/b$ is $D_{t}$-separable.

The next theorem characterizes all possible separable rational functions in
terms of semi-split rational functions.

######  Theorem 3.1.

A rational function $f\in{\mathbb{F}}(t,{\bf x})$ is $\partial_{t}$-separable
if and only if $f$ is semi-split in $t$ and ${\bf x}$.

###### Proof.

Assume that $f$ is semi-split in $t$ and ${\bf x}$. Then
$f=a_{1}b_{1}+\cdots+a_{n}b_{n}$, where $a_{i}\in{\mathbb{F}}(t)$ and
$b_{i}\in{\mathbb{F}}({\bf x})$ for all $i$ with $1\leq i\leq n$. Since each
$a_{i}b_{i}$ is annihilated by the operator
$L_{i}:=\partial_{t}-\partial_{t}(a_{i})/a_{i}\in{\mathbb{F}}(t)\langle{\partial}_{t}\rangle$,
the rational function $f$ is annihilated by $\text{LCLM}(L_{1},\ldots,L_{n})$.
So $f$ is $\partial_{t}$-separable.

For the necessity we assume that $f=a/b$ with $a,b\in{\mathbb{F}}[t,{\bf x}]$
and $\gcd(a,b)=1$ is $\partial_{t}$-separable, i.e., there exists a nonzero
operator
$L=\sum_{i=0}^{\rho}\ell_{i}{\partial}_{t}^{i}\in{\mathbb{F}}(t)\langle{\partial}_{t}\rangle$
with $\ell_{\rho}\neq 0$ such that $L(f)=0$. It suffices to show that the
denominator $b$ is split with respect to $t$ and ${\bf x}$. Suppose for the
sake of contradiction that $b$ is not split. Then $b$ has at least one
irreducible factor $p$ such that $p$ is not split. Now we proceed by a case
distinction according to the type of $\partial_{t}$. In the case when
${\partial}_{t}=D_{t}$, we have $\nu_{p}(\ell_{i}D_{t}^{i}(f))=\nu_{p}(f)-i$
for each $i$ with $\ell_{i}\neq 0$, since $\nu_{p}(f)<0$ and
$\nu_{p}(\ell_{i})=0$, which implies further that
$\nu_{p}(L(f))=\nu_{p}(f)-\rho$ by Proposition 2.4. But
$\nu_{p}(L(f))=\nu_{p}(0)=+\infty$, which leads to an contradiction. In the
case when ${\partial}_{t}=S_{t}$, we may always assume that
$\ell_{i}\in{\mathbb{F}}[t]$ and $\ell_{0}\neq 0$ since $\sigma_{t}$ is an
${\mathbb{F}}({\bf x})$-automorphism of ${\mathbb{F}}(t,{\bf x})$. Since
$\ell_{0}$ and $\ell_{\rho}$ are free of $x$, we have
$\sigma_{t}^{i}(p)\nmid\ell_{0}\ell_{\rho}$ for any $i\in{\mathbb{Z}}$. By
Lemma 2.6, we get $\text{dis}_{p}(L(f))=\text{dis}_{p}(f)+\rho<\infty$, which
contradicts with $\text{dis}_{p}(L(f))=\text{dis}_{p}(0)=+\infty$.

######  Remark 3.2.

With the above theorem, we can detect easily the $\partial_{t}$-separability
of rational functions by the computation of contents and derivatives of
multivariate polynomials in $t$.

##  4 The Hyperexponential and Hypergeometric
Cases

The separability problem on hyperexponential functions and hypergeometric
terms was first studied in [19], which was later connected to the existence of
parallel telescopers for hyperexponential functions [13]. We motivate this
problem by revisiting Zeilberger’s algorithm which computes telescopers for
hypergeometric terms (see [24, Chapter 6]).

Let $H(t,x)$ be a nonzero hypergeometric term over the rational-function field
${\mathbb{F}}(t,x)$, i.e., both $\sigma_{t}(H)/H$ and $\sigma_{x}(H)/H$ are in
${\mathbb{F}}(t,x)$. If telescopers of type $(S_{t},S_{x})$ exist for $H$,
Zeilberger’s algorithm starts from an ansatz: for fixed $\rho\in{\mathbb{N}}$,
set $L=\sum_{i=0}^{\rho}\ell_{i}S_{t}^{i}\in{\mathbb{F}}(t)\langle
S_{t}\rangle$ with the $\ell_{i}$’s being undetermined coefficients. Applying
$L$ to $H$ yields

$T:=L(H)=\sum_{i=0}^{\rho}\ell_{i}\sigma_{t}^{i}(H)=\sum_{i=0}^{\rho}\ell_{i}a_{i}H=\frac{\sum_{i=0}^{\rho}\ell_{i}P_{i}}{Q}H,$

where $a_{i}=\sigma_{t}^{i}(H)/H=P_{i}/Q\in{\mathbb{F}}(t,x)$ with
$P_{i},Q\in{\mathbb{F}}[t,x]$. The second step of Zeilberger’s algorithm is
computing the Gosper form of $L(H)$ that gives

$\frac{\sigma_{x}(L(H))}{L(H)}=\frac{\sigma_{x}\left(\sum_{i=0}^{\rho}\ell_{i}P_{i}\right)}{\sum_{i=0}^{\rho}\ell_{i}P_{i}}\frac{\sigma_{x}(p)}{p}\frac{q}{r},$

where $(p,q,r)\in{\mathbb{F}}(t)[x]^{3}$ is a Gosper form of the rational
function

$\frac{Q\sigma_{x}(H)}{(\sigma_{x}(Q)H)}$

satisfying that $\gcd(q,\sigma_{x}^{i}(r))=1$ for all $i\in{\mathbb{Z}}$. The
last step is finding $\ell_{0},\ldots,\ell_{\rho}\in{\mathbb{F}}(t)$, not all
zero, such that the equation

$\left(\sum_{i=0}^{\rho}\ell_{i}P_{i}\right)p=q\sigma_{x}(z)-\sigma_{x}^{-1}(r)z.$

has a polynomial solution in ${\mathbb{F}}(t)[x]$. If so, then
$L=\sum_{i=0}^{\rho}\ell_{i}S_{t}^{i}$ is a telescoper for $H$. It may happen
that the final choice of the $\ell_{i}$’s satisfies that
$\sum_{i=0}^{\rho}\ell_{i}P_{i}=0$. This means division by zero may happen in
the second step. To avoid this, we should first detect whether $L(H)=0$ for
some $L\in{\mathbb{F}}(t)\langle S_{t}\rangle$, i.e., the separability problem
on hypergeometric terms.

The following theorem characterizes all possible separable hyperexponential
functions and hypergeometric terms, whose proof was given in [19, Lemma 4] or
in [13, Proposition 10].

######  Theorem 4.1.

Let $\mathfrak{M}$ be an ${\mathbb{E}}\langle\partial_{t},{\partial}_{{\bf
x}}\rangle$-module and let $H\in\mathfrak{M}$ be such that

$\partial_{t}(H)=aH\,\,\text{and}\,\,{\partial}_{x_{i}}(H)=b_{i}H\,\,\text{with
$a,b_{i}\in{\mathbb{F}}(t,{\bf x})$}.$

Then we have,

  * $(i)$

Hyperexponential case: $H$ is $D_{t}$-separable if and only if there exist
$p\in{\mathbb{F}}({\bf x})[t]$ and $r\in{\mathbb{F}}(t)$ such that

$a=\frac{\delta_{t}(p)}{p}+r.$

  * $(ii)$

Hypergeometric case: $H$ is $S_{t}$-separable if and only if there exist
$p\in{\mathbb{F}}({\bf x})[t]$ and $r\in{\mathbb{F}}(t)$ such that

$a=\frac{\sigma_{t}(p)}{p}\cdot r.$

######  Remark 4.2.

The above form for $\partial_{t}(H)/H$ can be detected by algorithms for
computing the Gosper form and its differential analogue in [17, 7].

##  5 The Algebraic case

In this section, we solve the separability problem on algebraic functions. We
first explain the connection between this problem and the following existence
problem of telescopers for rational functions in three variables.

######  Problem 5.1.

Given $f\in{\mathbb{F}}(t,x,y)$, decide whether there exists a nonzero
operator $L\in{\mathbb{F}}(t)\langle D_{t}\rangle$ such that
$L(f)=\Delta_{x}(g)+D_{y}(h)$ for some $g,h\in{\mathbb{F}}(t,x,y)$.

By applying the Ostrogradsky-Hermite reduction in $y$ and Abramov’s reduction
in $x$ to $f\in{\mathbb{F}}(t,x,y)$, we get

$f=\Delta_{x}(u)+D_{y}(v)+r\,\,\text{with
$r=\sum_{i=1}^{I}\frac{\alpha_{i}}{y-\beta_{i}}$}$

where $u,v,r\in{\mathbb{F}}(t,x,y)$,
$\alpha_{i},\beta_{i}\in\overline{{\mathbb{F}}(t,x)}$ and $\beta_{i}$’s are in
distinct $\sigma_{x}$-orbits. Then $f$ has a telescoper of type
$(D_{t},S_{x},D_{y})$ if and only if $r$ does. By Theorem 4.21 in [12] or
Theorem 4.43 in [11], we have $r$ has a telescoper of type
$(D_{t},S_{x},D_{y})$ if and only if for each $i$ with $1\leq i\leq I$, either
$\alpha_{i}$ is $D_{t}$-separable in $\overline{{\mathbb{F}}(t,x)}$ or
$\beta_{i}\in\overline{{\mathbb{F}}(t)}$ and
$\alpha_{i}\in{\mathbb{F}}(t,x)(\beta_{i})$ has a telescoper of type
$(D_{t},S_{x})$. The existence problem of telescopers of type $(D_{t},S_{x})$
in ${\mathbb{F}}(t,x)(\beta)$ with $\beta\in\overline{{\mathbb{F}}(t)}$ has
been solved in [15]. To completely solve Problem 5.1, it remains to solve the
following separability problem.

######  Problem 5.2.

Given an algebraic function $f(t,{\bf x})$ over ${\mathbb{F}}(t,{\bf x})$,
decide whether $f(t,{\bf x})$ is $D_{t}$-separable.

We assume that ${\mathbb{F}}$ is an algebraically closed and computable
subfield of ${\mathbb{C}}$ in the remaining part of this section.

###  5.1 A descent theorem

We first recall some basic notions and results from the theory of algebraic
functions of one variable [16]. Let $k$ be a field of characteristic zero and
$k(x,y)$ be an algebraic function field of one variable over $k$, i.e., the
transcendence degree of $k(x,y)$ over $k$ is one. This means there exists a
polynomial $f\in k[X,Y]$ such that $f(x,y)=0$. The field of constants of
$k(x,y)$ is defined as the set of elements of $k(x,y)$ which are algebraic
over $k$. A subring $R$ of $k(x,y)$ is called a _valuation ring_ if $k\subset
R\subsetneqq k(x,y)$ and for any $x\in k(x,y)$, either $x\in R$ or $x^{-1}\in
R$. Any valuation ring $R$ of $k(x,y)$ is a local ring, whose unique maximal
ideal ${\mathfrak{p}}$ is called a _place_ of $k(x,y)$ and the quotient field
$R/{\mathfrak{p}}$ is called the _residue field_ of the place
${\mathfrak{p}}$, denoted by $\Sigma_{{\mathfrak{p}}}$.

######  Lemma 5.3.

Let $k(x,y)$ and $f\in k[X,Y]$ be as above. Assume that $(\bar{x},\bar{y})\in
k^{2}$ satisfies that $f(\bar{x},\bar{y})=0$ and $\frac{\partial f}{\partial
Y}(\bar{x},\bar{y})\neq 0$. Then there is a unique place ${\mathfrak{p}}$ of
$k(x,y)$ containing $x-\bar{x}$ and $y-\bar{y}$. Furthermore, the residue
field $\Sigma_{{\mathfrak{p}}}$ of ${\mathfrak{p}}$ is isomorphic to $k$ and
$k$ is the field of constants of $k(x,y)$.

###### Proof.

By Corollary 2 of [16, page 8], there is a place of $k(x,y)$ containing
$x-\bar{x}$ and $y-\bar{y}$, say ${\mathfrak{p}}$. Let ${\mathfrak{a}}$ be the
discrete valuation ring (DVR) with respect to ${\mathfrak{p}}$. It is easy to
see that the ring $k[x,y]$ is contained in ${\mathfrak{a}}$. Let
${\mathfrak{m}}$ be the ideal in $k[x,y]$ generated by $x-\bar{x}$ and
$y-\bar{y}$. Then ${\mathfrak{m}}$ is a maximal ideal. Denote by $R$ the
localization of $k[x,y]$ at ${\mathfrak{m}}$ and we still use ${\mathfrak{m}}$
to denote the unique maximal ideal of $R$. Rewriting $f(X,Y)$ as a polynomial
in $X-\bar{x},Y-\bar{y}$ yields that

$\left(\frac{\partial f}{\partial
Y}(\bar{x},\bar{y})+(Y-\bar{y})A\right)(Y-\bar{y})+(X-\bar{x})B$

for some $A,B\in k[X-\bar{x},Y-\bar{y}]$. Since $\frac{\partial f}{\partial
Y}(\bar{x},\bar{y})\neq 0$, one has that $\frac{\partial f}{\partial
Y}(\bar{x},\bar{y})+(y-\bar{y})A(x-\bar{x},y-\bar{y})$ is invertible in $R$
and so $y-\bar{y}\in(x-\bar{x})R$. It implies that $R$ is a regular local
ring, i.e., a DVR. Therefore $R={\mathfrak{a}}$, since
$R\subset{\mathfrak{a}}$. This concludes that ${\mathfrak{p}}$ is unique.

We have that
$\Sigma_{{\mathfrak{p}}}=R/{\mathfrak{m}}=k[x,y]/{\mathfrak{m}}\cong k$. Since
the field of constants of $k(x,y)$ is a subfield of $\Sigma_{{\mathfrak{p}}}$
under the natural homomorphism, it coincides with $k$.

######  Remark 5.4.

Let $k(x,y)$ and $(\bar{x},\bar{y})$ be as in Lemma 5.3. The above proof
implies that $k(x,y)$ can be embedded into the field of formal Laurent series
$k((x-\bar{x}))$.

######  Theorem 5.5.

Let ${\mathbb{F}}\subseteq k\subseteq{\mathbb{C}}$ be fields with
${\mathbb{F}}$ being algebraically closed. Let $f(t,Y)$ be an irreducible
polynomial in $k[t,Y]$. Let $k(t,y)$ be the quotient field of $k[t,Y]/\langle
f\rangle$. Assume that

  1. 1.

the places of $k(t)$ that ramify in $k(t,y)$ are defined over ${\mathbb{F}}$,
i.e., their uniformizing parameters can be chosen to be $1/t$ or $t-c$ with
$c\in{\mathbb{F}}$.

  2. 2.

there exists a solution $(a,\alpha)$ of the system

$\displaystyle f(a,\alpha)$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle\frac{{\partial}f}{{\partial}Y}(a,\alpha)$ $\displaystyle\neq$
$\displaystyle 0,$

where $a\in{\mathbb{F}}$ and $\alpha\in k$.

Then there exists $\beta\in\overline{{\mathbb{F}}(t)}$ such that
$k(t,y)=k(t,\beta)$.

###### Proof.

Since $(a,\alpha)$ is a simple point of $f(t,Y)=0$ in $k^{2}$, by [25],
$f(t,Y)$ is absolutely irreducible over $k$. This implies that $f$ is
irreducible over ${\mathbb{C}}$, i.e., ${\mathbb{C}}[t,Y]/\langle f\rangle$ is
an integral domain. Let ${\mathbb{C}}(t,y)$ be the quotient field of
${\mathbb{C}}[t,Y]/\langle f\rangle$. Then $k(t,y)$ can be considered as a
subfield of ${\mathbb{C}}(t,y)$ under the natural homomorphism. From Theorem 3
in [16, page 92], none of places of ${\mathbb{C}}(t,y)$ is ramified with
respect to $k(t,y)$. Therefore the condition 1 holds for ${\mathbb{C}}(t,y)$.
Proposition 2.1 in [20, page 10] states that there is
$\beta\in\overline{{\mathbb{F}}(t)}$ such that
${\mathbb{C}}(t,y)={\mathbb{C}}(t,\beta)$. Now there are
$g_{0}(t),\cdots,g_{n-1}(t)\in{\mathbb{C}}(t)$ such that

$\beta=\sum_{i=0}^{n-1}g_{i}(t)y^{i},$ (5.1)

where $n=[{\mathbb{C}}(t,y):{\mathbb{C}}(t)]$. For each $i$, let
$g_{i}={q_{i}}/{q}$ with $q_{i},q\in{\mathbb{C}}[t]$ and let
$s=\max_{i}\\{\deg_{t}q_{i},\deg_{t}q\\}$. Equation (2) implies that
$q\beta=\sum_{i=0}^{n-1}q_{i}y^{i}$ and therefore the set

$\left\\{t^{j}\beta,\,\,t^{j}y^{i}\right\\}_{j=0,\ldots s,i=0,\ldots n-1}$

is linearly dependent over ${\mathbb{C}}$. This set lies in $k(t,y,\beta)$
and, since it is linearly dependent over $D_{t}$-constants in a larger
differential field, it is linearly dependent over $D_{t}$-constants in
$k(t,y,\beta)$. Denote by $\tilde{k}$ the set of $D_{t}$-constants of
$k(t,y,\beta)$. If $\tilde{k}=k$, then $\beta\in k(t,y)$, which will conclude
the proposition. Therefore it suffices to prove that $\tilde{k}=k$. It is easy
to verify that $\tilde{k}$ coincides with the field of constants of
$k(t,y,\beta)$. In the following, we will show that the field of constants of
$k(t,y,\beta)$ is equal to $k$.

From Remark 5.4, $k(t,y)$ and ${\mathbb{C}}(t,y)$ can be embedded into
$k((t-a))$ and ${\mathbb{C}}((t-a))$ respectively. We will consider them as
the subfields of $k((t-a))$ and ${\mathbb{C}}((t-a))$ respectively. Since
$\beta\in{\mathbb{C}}(t,y)\cap\overline{{\mathbb{F}}(t)}$, ${\mathbb{F}}$ is
algebraically closed and $a\in{\mathbb{F}}$, $\beta\in{\mathbb{F}}((t-a))$.
Therefore, $k(t,y,\beta)\subseteq k((t-a))$. Since $k$ is algebraically closed
in $k((t-a))$, the field of constants of $k(t,y,\beta)$ is equal to $k$. This
completes the proof.

###  5.2 Separability criteria

Let $P=\sum_{i=0}^{n}A_{i}Y^{i}\in{\mathbb{F}}(t,{\bf x})[Y]$ be the minimal
polynomial of $y\in\overline{{\mathbb{F}}(t,{\bf x})}$. We can always pick
$(a,\alpha)\in{\mathbb{F}}\times\overline{{\mathbb{F}}({\bf x})}$ such that

$A_{n}({\bf x},a)\neq 0,\,\,P({\bf
x},a,\alpha)=0\,\,\mbox{and}\,\,\frac{\partial P}{\partial Y}({\bf
x},a,\alpha)\neq 0.$ (5.2)

Let $K={\mathbb{F}}({\bf x},\alpha)$ and $\ell=[K(t,y):K(t)]$. Asume that
$z\in\overline{{\mathbb{F}}(t,{\bf x})}$ also satisfies the equation $P(z)=0$.
Then $z$ and $y$ are conjugated over ${\mathbb{F}}(t,{\bf x})$. By Theorem
3.2.4 in [9], any field automorphism of the splitting field of $P$ commutes
with the derivation $D_{t}$. So for any $L\in{\mathbb{F}}(t)\langle
D_{t}\rangle$, $L(z)=0$ if and only if $L(y)=0$. Thus to detect if there is a
nonzero $L\in{\mathbb{F}}(t)\langle D_{t}\rangle$ such that $L(y)=0$, it
suffices to detect if there exists such operator for $z$. In the following, we
will characterize all possible $D_{t}$-separable algebraic functions.

Assume that $y$ is $D_{t}$-separable, i.e., there exists a nonzero
$L\in{\mathbb{F}}(t)\langle D_{t}\rangle$ such that $L(y)=0$. Let
${\mathfrak{p}}$ be a place of $K(t)$ and ${\mathfrak{q}}$ a place of $K(t,y)$
that is ramified with respect to ${\mathfrak{p}}$. Suppose that $p$ and $q$
are uniformizing parameters of ${\mathfrak{p}}$ and ${\mathfrak{q}}$
respectively, and $e$ is the corresponding ramification index. Then $p=aq^{e}$
for some invertible $a$ in the DVR with respect to ${\mathfrak{q}}$.
Furthermore assume that $p$ is an irreducible polynomial in $K[t]$. Let $\wp$
be a place of ${\mathbb{C}}(t,y)$ lying above ${\mathfrak{q}}$. Then by
Theorem 3 in [16, page 92]), $\wp$ is not ramified with respect to
${\mathfrak{q}}$ and so $q$ is a uniformizing parameter of $\wp$. Since
$p\in\wp$, the uniformizing parameter of $\wp\cap{\mathbb{C}}(t)$ can be
selected as a factor of $p$, say $t-c$ for some $c\in{\mathbb{C}}$. It is easy
to see that $p/(t-c)$ is an invertible element in the DVR with respect to
$\wp$. It implies that $t-c=\bar{a}q^{e}$ for some invertible element
$\bar{a}$ and thus $K(t,y)$ can be embedded into ${\mathbb{C}}((t-c)^{1/e})$.
Therefore $y\in{\mathbb{C}}((t-c)^{1/e}))$ and $c$ is a singular point of $L$.
Note that the singular points of $L$ lie in the algebraically closed field
${\mathbb{F}}$. So $c\in{\mathbb{F}}$ and then $p=b(t-c)$ for some $b\in K$.
In other words, $t-c$ is a uniformizing parameter of ${\mathfrak{p}}$. Hence
$K(t,y)$ satisfies the condition 1 of Theorem 5.5. By Theorem 5.5, there is
$\beta\in\overline{{\mathbb{F}}(t)}$ such that $K(t,y)=K(t,\beta)$. We now
characterize separable algebraic functions as follows.

######  Proposition 5.6.

Let $P=\sum_{i=0}^{n}A_{i}Y^{i}\in{\mathbb{F}}[t,{\bf x}][Y]$ with $A_{n}\neq
0$ be the minimal polynomial of $y\in\overline{{\mathbb{F}}(t,{\bf x})}$. Let
$K={\mathbb{F}}({\bf x})(\alpha)$ with $\alpha\in\overline{{\mathbb{F}}({\bf
x})}$ be as in (5.2) and $\beta\in\overline{k(t)}$ be such that
$K(t,y)=K(t,\beta)$. If $y$ is $D_{t}$-separable, then

  1. $(1)$

$A_{n}(\mathbf{x},t)$ is split, i.e., $A_{n}(\mathbf{x},t)=a(\mathbf{x})b(t)$,
where $a(\mathbf{x})\in{\mathbb{F}}[\mathbf{x}],b(t)\in{\mathbb{F}}[t]$, and

  2. $(2)$

$y=\frac{1}{b(t)q(t)}\sum_{i=0}^{\ell-1}a_{i}(t)\beta^{i},$ (5.3)

where $\ell=[K(t,y):K(t)],a_{i}(t)\in K[t]$ and $q(t)$ is the discriminant of
the base $\\{1,\beta,\cdots,\beta^{\ell-1}\\}$.

###### Proof.

Let $r_{i}=A_{i}/A_{n}=p_{i}/q_{i}\in{\mathbb{F}}(t,{\bf x})$ with $0\leq
i\leq n$, $p_{i},q_{i}\in{\mathbb{F}}[t,{\bf x}]$ and $\gcd(p_{i},q_{i})=1$.
Since $y$ is $D_{t}$-separable, so are all of the conjugate roots of $P(Y)=0$.
By Vieta’s formulas, the $r_{i}$’s are polynomials of these roots, which
therefore are also $D_{t}$-separable by Proposition 2.2. By Theorem 3.1,
$q_{i}$ is split for all $i$ with $0\leq i\leq n$. Since $A_{n}$ is the LCM of
the $q_{i}$’s, we have $A_{n}(\mathbf{x},t)$ is also split.

Let $S$ be the integral closure of $K[t]$ in $K(t,y)$. Then
$\beta,A_{n}(\mathbf{x},t)y\in S$. Since $\\{1,\beta,\cdots,\beta^{\ell-1}\\}$
is a base of $K(t,y)$ over $K(t)$, one has that

$A_{n}(\mathbf{x},t)y=\frac{1}{q(t)}\sum_{i=0}^{\ell-1}g_{i}(t)\beta^{i},$

where $g_{i}(t)\in K[t]$. Setting $a_{i}(t)=g_{i}(t)/a(\mathbf{x})$, we obtain
the required expression for $y$.

Recall that $K={\mathbb{F}}({\bf x},\alpha)$ and $\ell=[K(t,y):K(t)]$. Since
the $i$-th derivative of $y$ is also in $K(t,y)$ for any $i\in{\mathbb{N}}$,
we have that $Y=(1,y,y^{2},\cdots,y^{\ell-1})^{t}$ satisfies a linear
differential system of the form

$Y^{\prime}=AY,\quad\text{where $A\in\text{Mat}_{\ell}(K(t))$}.$ (5.4)

We will call (5.4) the associated differential equation of $y$ over $K(t)$.
The following proposition will allow us to design an algorithm for testing the
separability of algebraic functions.

######  Proposition 5.7.

Let $y$ and $K$ be as above. Assume that (5.4) is the associated differential
equation of $y$ over $K(t)$. Then $y$ is $D_{t}$-separable if and only if
there is an invertible matrix $G$ with entries in $K[t]$ such that

$G^{-1}G^{\prime}-G^{-1}AG\in{\rm Mat}_{\ell}({\mathbb{F}}(t)).$

###### Proof.

Assume that there exists a nonzero $L\in{\mathbb{F}}(t)\langle D_{t}\rangle$
such that $L(y)=0$. Then by Proposition 5.6, $y$ has the form (5.3). Let $E$
be the Galois closure of $K(t,\beta)$ over $K(t)$. Let
$\beta_{1}=\beta,\beta_{2},\cdots,\beta_{\ell}$ be the conjugates of $\beta$
and $\sigma_{i}\in{\rm Gal}(E/K(t))$ such that $\sigma_{i}(\beta)=\beta_{i}$.
Then $\sigma_{1}(y),\cdots,\sigma_{\ell}(y)$ are all zeroes of
$P(\mathbf{x},t,y)$. We will denote the Vandermonde matrix generated by
$\sigma_{1}(y),\cdots,\sigma_{\ell}(y)$ by $U(y)$ and the one generated by
$\beta_{1},\cdots,\beta_{\ell}$ by $U(\beta)$. Then $U(y)$ is a fundamental
matrix of the system (5.4) and $U(\beta)$ is a fundamental matrix of a system
$Y^{\prime}=BY$ with $B\in{\rm Mat}_{\ell}({\mathbb{F}}(t))$. Using the
argument similar to that in the proof of Proposition 5.7, we have that for all
$j$ with $1\leq j\leq\ell-1$,

$y^{j}=\frac{1}{b(t)^{j}q(t)}\sum_{i=0}^{\ell-1}a_{i,j}(t)\beta^{i},$ (5.5)

where $a_{i,j}(t)\in K[t]$ and $b(t),q(t)$ are as in Proposition 5.6. Applying
$\sigma_{l}$ to both sides of the equalities (5.5) implies that

$\sigma_{l}(y)^{j}=\frac{1}{b(t)^{j}q(t)}\sum_{i=0}^{\ell-1}a_{i,j}(t)\beta^{i}_{l},$
(5.6)

where $j=1,\cdots,\ell-1,l=1,\cdots,\ell$. Let
$\tilde{a}_{i,j}=a_{i,j}b^{\ell-1-j}$ and

$G=\begin{pmatrix}b(t)^{\ell-1}q(t)&0&\cdots&0\\\
\tilde{a}_{0,1}(t)&\tilde{a}_{1,1}(t)&\cdots&\tilde{a}_{\ell-1,1}(t)\\\
\vdots&\vdots&\vdots&\vdots\\\
\tilde{a}_{0,\ell-1}(t)&\tilde{a}_{1,\ell-1}(t)&\cdots&\tilde{a}_{\ell-1,\ell-1}(t)\end{pmatrix}$

that is an element in ${\rm Mat}_{\ell}(K[t])$. Then the equations (5.6) can
be rewritten as $U(y)=({G}U(\beta))/({b(t)^{\ell-1}q(t)})$. Hence $G$ is
invertible and an easy calculation yields that

$\displaystyle U(\beta)^{\prime}$
$\displaystyle=(b^{\ell-1}qG^{-1}U(y))^{\prime}$
$\displaystyle=\left((b^{\ell-1}q)^{\prime}-b^{\ell-1}qG^{-1}G^{\prime}+b^{\ell-1}qG^{-1}AG\right)G^{-1}U(y)$
$\displaystyle=BU(\beta)=b^{\ell-1}qBG^{-1}U(y).$

This implies that

$G^{-1}AG-G^{-1}G^{\prime}=B-\frac{(b^{\ell-1}q)^{\prime}}{b^{\ell-1}q}\in{\rm
Mat}_{\ell}({\mathbb{F}}(t)).$

Now we prove the converse. Assume that there is an invertible matrix $G\in{\rm
Mat}_{\ell}(K[t])$ such that

$\tilde{B}=G^{-1}AG-G^{-1}G^{\prime}\in{\rm Mat}_{\ell}({\mathbb{F}}(t)).$

Then $U(y)=GF$, where $F$ is a fundamental matrix of $Y^{\prime}=\tilde{B}Y$
with entries in some differential extension field of $K(t)$. Obviously, the
entries of both $G$ and $F$ are annihilated by nonzero operators in
${\mathbb{F}}(t)\langle D_{t}\rangle$ and thus so are the sum of products of
entries of $G$ and $F$, in particular, so is $y$.

######  Remark 5.8.

Once $\beta$ is computed, one can obtain the linear differential equations
$Y^{\prime}=BY$ satisfied by $U(\beta)$.

###  5.3 An algorithm for testing separability

We now present an algorithm to decide whether a given algebraic function
$y\in\overline{{\mathbb{F}}(t,{\bf x})}$ is $D_{t}$-separable or not. For the
sake of simplicity, we may take ${\mathbb{F}}=\bar{\mathbb{Q}}$, the field of
all algebraic numbers over ${\mathbb{Q}}$. Let
$P=\sum_{i=0}^{n}A_{i}Y^{i}\in{\mathbb{F}}[t,{\bf x}][Y]$ be the minimal
polynomial of $y$. Furthermore, assume that $A_{n}$ is split. Under this
assumption, $y$ is $D_{t}$-separable if and only if $A_{n}y$ is
$D_{t}$-separable. Therefore without loss of generality, we may assume that

$P(\mathbf{x},t,Y)=Y^{n}+A_{n-1}(\mathbf{x},t)Y^{n-1}+\cdots+A_{0}(\mathbf{x},t),$
(5.7)

where $A_{i}\in{\mathbb{F}}[\mathbf{x},t]$. Let
$(a,\alpha)\in{\mathbb{F}}\times\overline{{\mathbb{F}}({\bf x})}$ satisfy

$P(\mathbf{x},a,\alpha)=0,\,\,\frac{\partial P}{\partial
Y}(\mathbf{x},a,\alpha)\neq 0,$ (5.8)

and let $K={\mathbb{F}}({\bf x},\alpha)$. Then $P({\bf x},t,Y)$ may be
factorized into a product of irreducible polynomials in $K[t,Y]$. There is a
unique factor of $P({\bf x},t,Y)$ in $K[t,Y]$ vanishing at $(a,\alpha)$,
denoted by $\bar{P}({\bf x},\alpha,t,Y)$. Let $K(t,y)$ be the quotient field
of $K[t,Y]/\langle\bar{P}({\bf x},\alpha,t,Y)\rangle$. Furthermore suppose
that $K(t,y)$ satisfies the condition 1 of Theorem 5.5. Then Theorem 5.5
implies that there is $\beta\in\overline{{\mathbb{F}}(t)}$ such that
$K(t,y)=K(t,\beta)$. We shall show how to find such $\beta$.

Let $R={\mathbb{F}}(t)[{\bf x}]$ and $S$ the integral closure of $R$ in
$K(t,y)$. Then $\alpha,y\in S$. Suppose that

$\bar{P}({\bf
x},\alpha,t,Y)=B_{\ell}Y^{\ell}+B_{\ell-1}Y^{\ell-1}+\cdots+B_{0},$ (5.9)

where $B_{\ell}\in{\mathbb{F}}[\mathbf{x}],B_{i}\in k[\mathbf{x},\alpha,t]$
with $i=0,\cdots,\ell-1$. Note that

$\displaystyle[K(t,y):{\mathbb{F}}({\bf x},t)]$
$\displaystyle=[K(t,y):K(t)][K(t):{\mathbb{F}}({\bf x},t)]$
$\displaystyle=[K(t,y):K(t)][K:{\mathbb{F}}({\bf x})]=\ell[K:{\mathbb{F}}({\bf
x})].$

The set

$\left\\{\alpha^{i}y^{j}\left|i=0,\cdots,[K:{\mathbb{F}}({\bf
x})]-1,j=0,\cdots,\ell-1\right.\right\\}$

is a base of $K(t,y)$ over ${\mathbb{F}}({\bf x},t)$. Let $D({\bf x},t)$ be
the discriminant of the above base and let $F({\bf x},Y)$ be an irreducible
polynomial in ${\mathbb{F}}[{\bf x},Y]$ such that $F({\bf x},\alpha)=0$. Then
we have

######  Lemma 5.9.

Let $(\mathbf{c},b)\in{\mathbb{F}}^{m+1}$ satisfy $F(\mathbf{c},b)=0$ and
$D(\mathbf{c},t)B_{\ell}(\mathbf{c})\neq 0$. Then $\bar{P}(\mathbf{c},b,t,Y)$
is irreducible in ${\mathbb{F}}[t,Y]$ and for any root $Y=\gamma$ of
$\bar{P}(\mathbf{c},b,t,Y)=0$, we have that $K(t,y)$ is isomorphic to
$K(t,\gamma)$.

###### Proof.

Let $\beta\in K(t,y)$ be as above. Since $\beta$ is algebraic over
${\mathbb{F}}(t)$ we have that $\beta$ is integral over
$R={\mathbb{F}}(t)[\mathbf{x}]$. Therefore we may write

$\beta=\frac{1}{D({\bf x},t)}\sum b_{i,j}\alpha^{i}y^{j},$

where the $b_{i,j}\in R$. Let $(\mathbf{c},b)$ satisfy the hypothesis of the
lemma and consider the ideal

${\mathfrak{p}}=\langle x_{1}-c_{1},\ldots,x_{m}-c_{m},\alpha-b\rangle\lhd
R[\alpha].$

Note that ${\mathfrak{p}}$ is a maximal ideal. The Going Up Theorem implies
that there is a maximal ideal ${\mathfrak{q}}\lhd S$ such that
${\mathfrak{q}}\cap R[\alpha]={\mathfrak{p}}$. In particular, $D({\bf
x},t)\notin{\mathfrak{q}}$. There is a natural map $\phi:S\rightarrow
S/{\mathfrak{q}}$. We will let $M$ denote the field $S/{\mathfrak{q}}$. The
element $\gamma=\phi(y)$ is a root of $\bar{P}(\mathbf{c},b,t,\gamma)=0$.
Since the minimal polynomial $Q(t,Y)$ of $\beta$ lies in ${\mathbb{F}}[t,Y]$,
it remains unchanged when we apply $\phi$ to its coefficients. Therefore
$\phi(\beta)$ satisfies $Q(t,\phi(\beta))=0$. In particular, the degree of
$\phi(\beta)$ over ${\mathbb{F}}(t)$ is equal to $\ell$, the degree of
$K(t,\beta)$ over $K(t)$. Since

$\phi(\beta)=\frac{1}{D(\mathbf{c},t)}\sum\phi(b_{i,j})\phi(\alpha)^{i}\gamma^{j}$

we have that $\phi(\beta)\in{\mathbb{F}}(t)(\gamma)$. Note that
$\bar{P}(\mathbf{c},b,t,Y)\neq 0$. The element $\gamma$ satisfies
$\bar{P}(\mathbf{c},b,t,\gamma)=0$ and so it has degree at most $\ell$ over
${\mathbb{F}}(t)$. Since $\phi(\beta)\in{\mathbb{F}}(t,\gamma)$, we have that

$\displaystyle\ell\geq[{\mathbb{F}}(t,\gamma):{\mathbb{F}}(t)]\geq[{\mathbb{F}}(t,\phi(\beta)):{\mathbb{F}}(t)]$
$\displaystyle=[K(t,\beta):K(t)]$ $\displaystyle=[K(t,y):K(t)]=\ell$

and so $[{\mathbb{F}}(t,\gamma):{\mathbb{F}}(t)]=\ell$ . Therefore
$\bar{P}(\mathbf{c},b,t,Y)$ is irreducible. Furthermore
${\mathbb{F}}(t,\beta)$ is isomorphic to
${\mathbb{F}}(t,\phi(\beta))={\mathbb{F}}(t,\gamma)$. This implies that
$K(t,y)$ is isomorphic to $K(t,\gamma)$.

Let $\bar{P}(\mathbf{x},\alpha,t,Y)$ be as above. Lemma 5.9 implies that if
$y$ is $D_{t}$-separable then one can compute
$(\mathbf{c},b)\in{\mathbb{F}}^{m+1}$ such that $\bar{P}(\mathbf{c},b,t,Y)$ is
irreducible over ${\mathbb{F}}(t)$ and $\beta$ can be taken to be a zero of
$\bar{P}(\mathbf{c},b,t,Y)$. From $\bar{P}(\mathbf{c},b,t,Y)$, we can
construct the associated differential equation of $\beta$ over
${\mathbb{F}}(t)$. Denote this associated differential equation by
$Y^{\prime}=BY$ with $B\in{\rm Mat}_{\ell}({\mathbb{F}}(t))$. The proof of
Proposition 5.7 implies that if $y$ is $D_{t}$-separable then there is an
invertible matrix $G$ with entries in $K[t]$ such that

$G^{\prime}=AG-G\left(B-\frac{q^{\prime}(t)}{q(t)}\right),$

where $q(t)$ is the discriminant of $\\{1,\beta,\cdots,\beta^{\ell-1}\\}$ and
$Y^{\prime}=AY$ is the associated differential equation of $y$ over $K(t)$.
Here the polynomial $b(t)$ in (5.5) disappears because we assume that $P$ is
monic in $Y$. Note that $G$ is a polynomial solution of the linear
differential equation $Y^{\prime}=AY-Y(B-q(t)^{\prime}/q(t))$, which can be
computed by algorithms developed in [5, 8].

We summarize the above results as the following algorithm.

######  Algorithm 5.10.

Input: An irreducible polynomial

$P(t,{\bf x},Y)=A_{n}Y^{n}+A_{n-1}Y^{n-1}+\cdots+A_{0}\in{\mathbb{F}}[t,{\bf
x},Y].$

Output: “Yes” if $y$ is $D_{t}$-separable, otherwise “No”, where
$y\in\overline{k(\mathbf{x},t)}$ is a root of $P(Y)=0$.

  * $(1)$

If $A_{n}$ is not split, then $y$ is not $D_{t}$-separable and return “No”.

  * $(2)$

Transform $P(\mathbf{x},t,Y)$ into a monic polynomial by replacing $Y$ by
$Y/A_{n}$ and clear the denominators.

  * $(3)$

Compute $\beta$:

    * $(3.a)$

Find $(a,\alpha)\in{\mathbb{F}}\times\overline{{\mathbb{F}}({\bf x})}$
satisfying the conditions (5.8).

    * $(3.b)$

Decompose $P$ into a product of irreducible polynomials over
${\mathbb{F}}(\mathbf{x},\alpha)$. Let $\bar{P}(\mathbf{x},\alpha,t,Y)$ be the
irreducible factor satisfying that

$\bar{P}(\mathbf{x},\alpha,a,\alpha)=0.$

    * $(3.c)$

Compute $D(\mathbf{x},t)$, the discriminant of the base
$\\{\alpha^{i}\bar{y}^{j}\\}$, where $\bar{y}$ is a zero of
$\bar{P}(\mathbf{x},\alpha,t,Y)$ in $\overline{{\mathbb{F}}(t,{\bf x})}$.

    * $(3.d)$

Compute a point $(\mathbf{c},b)\in{\mathbb{F}}^{m+1}$ such that

$D(\mathbf{c},t)B_{\ell}(\mathbf{c})\neq 0$ and $F(\mathbf{c},b)=0$,

where $F$ is the minimal polynomial of $\alpha$ over
${\mathbb{F}}(\mathbf{x})$ and $B_{\ell}(\mathbf{x})$ is the leading
coefficient of $\bar{P}(\mathbf{x},\alpha,t,Y)$.

    * $(3.e)$

Let $\beta$ be a zero of $\bar{P}(\mathbf{c},b,t,Y)=0$ in
$\overline{{\mathbb{F}}(t)}$.

  * $(4)$

Compute $G$:

    * $(4.a)$

Compute $q(t)$, the discriminant of the base
$\\{\beta^{j}|j=0,\cdots,\ell-1\\}$ and compute the associated differential
equations of $y$ and $\beta$, which are denoted by $Y^{\prime}=AY$ and
$Y^{\prime}=BY$ respectively.

    * $(4.b)$

By algorithms developed in [5, 8], compute a base of polynomial solutions of
$Z^{\prime}=AZ-Z(B-q(t)^{\prime}/q(t))$, where $Z=(z_{ij})$ with indeterminate
entries, say $\\{Q_{1},\cdots,Q_{s}\\}$.

    * $(4.c)$

Compute $C=\det(z_{1}Q_{1}+\cdots+z_{s}Q_{s})$ with $z_{1},\cdots,z_{s}$ being
indeterminates. If $C=0$ then return “No”, otherwise return “Yes”.

We now show an example to illustrate the main steps of the above algorithm.

######  Example 5.11.

Let ${\mathbb{E}}=\bar{{\mathbb{Q}}}(t,x)$ and $y$ be the algebraic function
over ${\mathbb{E}}$ defined by

$P(x,t,Y):=Y^{2}-2(xt+1)Y+(xt+1)^{2}-t.$

We are going to decide whether $y$ is $D_{t}$-separable or not. We will follow
the above algorithm step by step. Since $P(x,t,Y)$ is monic in $Y$. We begin
with the third step, i.e., computing $\beta$.

  1. (3)

Compute $\beta=\sqrt{t}+1$:

    1. (3.a)

Set $(a,\alpha)=(1,x)$. One sees that $P(x,1,x)=0$ and

$\frac{\partial P}{\partial Y}(x,1,x)=-2\neq 0.$

So $\bar{{\mathbb{Q}}}(x,\alpha)=\bar{{\mathbb{Q}}}(x)$.

    2. (3.b)

Since $P(x,t,Y)$ is irreducible over $\bar{{\mathbb{Q}}}(x)$, we take
$\bar{P}(x,\alpha,t,Y)$ to be $P(x,t,Y).$

    3. (3.c)

Set $D(x,t)=4t$, which is the discriminant of the base $\\{1,\bar{y}\\}$ with
$P(x,t,\bar{y})=0$.

    4. (3.d)

One sees that $B_{2}(x)=1$ and $F=z-x$. So the point $(0,0)$ satisfies
$D(0,t)B_{2}(0)\neq 0$ and $F(0,0)=0$.

    5. (3.e)

Set $\beta=\sqrt{t}+1$ which is a zero of $P(0,t,Y)=Y^{2}-2Y+1-t$.

  2. (4)

Compute $G$:

    1. (4.a)

Set $q(t)=4t$, which is the discriminant of the base $\\{1,\beta\\}$, and set

$A=\begin{pmatrix}0&0\\\
\frac{x}{2}-\frac{1}{2t}&\frac{1}{2t}\end{pmatrix},\,\,B=\begin{pmatrix}0&0\\\
-\frac{1}{2t}&\frac{1}{2t}\end{pmatrix}.$

Then $Y^{\prime}=AY$ and $Y^{\prime}=BY$ are the associated differential
equations of $y$ and $\beta$ respectively.

    2. (4.b)

Set $Z=(z_{ij})_{1\leq i,j\leq 2}$, and compute a base of the polynomial
solutions of the system $Z^{\prime}=AZ-Z(B-1/t)$. One has that

$\left\\{Q_{1}:=\begin{pmatrix}t&0\\\
xt^{2}+t&0\end{pmatrix},\,\,Q_{2}:=\begin{pmatrix}0&0\\\
-t&t\end{pmatrix}\right\\}$

is a required base.

    3. (4.c)

One has that ${\rm det}(z_{1}Q_{1}+z_{2}Q_{2})=z_{1}z_{2}t^{2}\neq 0$. So $y$
is $D_{t}$-separable.

##  6 Conclusion and future work

We present a connection between the separability problems and the existence
problems in creative telescoping. Separability criteria are given for rational
functions, hyperexponential functions, hypergeometric terms and algebraic
functions. Some results in the algebraic case have been generalized to the
case of $D$-finite functions whose annihilating operators of minimal order are
completely reducible in [14]. The existence problems of telescopers for
rational functions in three variables are now completely settled by combining
the results in [11] with the separability criteria in this paper.

In terms of future research, the first natural direction is to solve the
separability problem for P-recursive sequences, which may have applications in
solving the general termination problem of Zeilberger’s algorithms beyond the
hypergeometric case. Another direction is to develop more symbolic
computational tools for the method of separation of variables for partial
differential equations as in [21].

## References

  * [1] S. A. Abramov.  The summation of rational functions.  Ž. Vyčisl. Mat i Mat. Fiz., 11:1071–1075, 1971.
  * [2] S.A. Abramov.  Solution of linear finite-difference equations with constant coefficients in the field of rational functions.  USSR Computational Mathematics and Mathematical Physics, 14(4):247 – 251, 1974.
  * [3] Sergei A. Abramov.  The rational component of the solution of a first order linear recurrence relation with rational right hand side.  Ž. Vyčisl. Mat. i Mat. Fiz., 15(4):1035–1039, 1090, 1975\.
  * [4] Sergei A. Abramov.  Indefinite sums of rational functions.  In ISSAC ’95: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, pages 303–308, New York, NY, USA, 1995. ACM.
  * [5] Sergei A. Abramov and Manuel Bronstein.  On solutions of linear functional systems.  In ISSAC’01: Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, pages 1–6, New York, NY, USA, 2001\. ACM.
  * [6] Sergei A. Abramov, Ha Quang Le, and Ziming Li.  Univariate Ore polynomial rings in computer algebra.  J. of Mathematical Sci., 131(5):5885–5903, 2005.
  * [7] Gert Almkvist and Doron Zeilberger.  The method of differentiating under the integral sign.  J. Symbolic Comput., 10:571–591, 1990.
  * [8] Moulay A. Barkatou.  On rational solutions of systems of linear differential equations.  J. Symbolic Comput., 28(4-5):547–567, 1999.  Differential algebra and differential equations.
  * [9] Manuel Bronstein.  Symbolic Integration I: Transcendental Functions, volume 1 of Algorithms and Computation in Mathematics.  Springer-Verlag, Berlin, second edition, 2005.
  * [10] Manuel Bronstein and Marko Petkovšek.  An introduction to pseudo-linear algebra.  Theoret. Comput. Sci., 157:3–33, 1996.
  * [11] Shaoshi Chen, Lixin Du, Rong-Hua Wang, and Chaochao Zhu.  On the existence of telescopers for rational functions in three variables.  J. Symbolic Comput., 104:494 – 522, 2021.
  * [12] Shaoshi Chen, Lixin Du, and Chaochao Zhu.  Existence problem of telescopers for rational functions in three variables: The mixed cases.  In ISSAC’19: Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, pages 82–89, New York, NY, USA, 2019. ACM.
  * [13] Shaoshi Chen, Ruyong Feng, Ziming Li, and Michael F. Singer.  Parallel telescoping and parameterized Picard–Vessiot theory.  In ISSAC ’14: Proceedings of the 2014 International Symposium on Symbolic and Algebraic Computation, pages 99–106, New York, NY, USA, 2014. ACM.
  * [14] Shaoshi Chen, Ruyong Feng, Ziming Li, Michael F. Singer, and Stephen Watt.  Telescopers for differential forms with one parameter, 2021.  arXiv: 2101.06576.
  * [15] Shaoshi Chen and Michael F. Singer.  Residues and telescopers for bivariate rational functions.  Adv. Appl. Math., 49(2):111–133, August 2012.
  * [16] Claude Chevalley.  Introduction to the Theory of Algebraic Functions of One Variable.  Mathematical Surveys, No. VI. American Mathematical Society, New York, NY, 1951.
  * [17] Ralph William Gosper, Jr.  Decision procedure for indefinite hypergeometric summation.  Proc. Nat. Acad. Sci. U.S.A., 75(1):40–42, 1978.
  * [18] Charles Hermite.  Sur l’intégration des fractions rationnelles.  Ann. Sci. École Norm. Sup. (2), 1:215–218, 1872.
  * [19] Ha Quang Le and Ziming Li.  On a class of hyperexponential elements and the fast versions of Zeilberger’s algorithm, 2004.  MM-Res. Preprints (2004) No. 23, 136-150.
  * [20] Gunter Malle and B. Heinrich Matzat.  Inverse Galois theory.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 1999.
  * [21] Willard Miller, Jr.  Symmetry and Separation of Variables.  Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1977.  With a foreword by Richard Askey, Encyclopedia of Mathematics and its Applications, Vol. 4.
  * [22] Mikhail Vasil’evich Ostrogradskiĭ.  De l’intégration des fractions rationnelles.  Bull. de la classe physico-mathématique de l’Acad. Impériale des Sciences de Saint-Pétersbourg, 4:145–167, 286–300, 1845\.
  * [23] Peter Paule and Markus Schorn.  A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities.  J. Symbolic Comput., 20(5-6):673–698, 1995.  Symbolic computation in combinatorics $\Delta{{}_{1}}$ (Ithaca, NY, 1993).
  * [24] Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger.  $A=B$.  A. K. Peters Ltd., Wellesley, MA, 1996.  With a foreword by Donald E. Knuth.
  * [25] Jean-François Ragot.  Probabilistic absolute irreducibility test for polynomials.  J. Pure Appl. Algebra, 172(1):87–107, 2002.
  * [26] Richard P. Stanley.  Differentiably finite power series.  European J. Combin., 1(2):175–188, 1980.
  * [27] Herbert S. Wilf and Doron Zeilberger.  An algorithmic proof theory for hypergeometric (ordinary and “$q$”) multisum/integral identities.  Invent. Math., 108(3):575–633, 1992.
  * [28] Doron Zeilberger.  The method of creative telescoping.  J. Symbolic Comput., 11(3):195–204, 1991.