{'fraction_non_alphanumeric': 0.08514083446302154, 'fraction_numerical': 0.010732037957523723, 'mean_word_length': 3.398310698906923, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Separability Problems in Creative Telescoping

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.


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 ∂y ∂t − c ∂ 2 y ∂x 2 = 0, where c ∈ 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 Since both sides only depend on one variable, there exits some constant λ ∈ C such that ∂u ∂t − λu = 0 and c ∂ 2 v ∂x 2 − λ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 where d n ∈ 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.

Preliminaries
Let F be a field of characteristic zero and let E = F(t, x) be the field of rational functions in t and x = (x 1 , . . . , x m ) over F. Let δ t , δ xi be the usual partial derivations ∂/∂ t , ∂/∂ xi with x i ∈ {x 1 , . . . , x m }, respectively. The shift operators σ t and σ xi on E are defined as the F-automorphisms such that for any f ∈ E, σ t (f (t, x)) = f (t + 1, x) and σ xi (f (t, x)) = f (t, x 1 , . . . , x i−1 , x i + 1, x i+1 , . . . , x m ).
The ring of linear functional operators in t and x over E is denoted by E ∂ t , ∂ x , where ∂ x = (∂ x1 , . . . , ∂ xm ) and and ∂ t and ∂ xi commute. For v ∈ {t, x}, we let ∆ v denote the difference operator S v − 1, where 1 stands for the identity map on E. Abusing notation, we let δ v and σ v denote arbitrary extensions of δ v and σ v to derivation and F-automorphism of E, the algebraic closure of E. The functions we consider will be in certain differential or difference extension of E, which is also an E ∂ t , ∂ x -module via the action defined by simply interpreting D v , S v by δ v , σ v , respectively, for v ∈ {t, x}. The ring F(t) ∂ t is a subring of E ∂ t , ∂ x that is also a left Euclidean domain. Efficient algorithms for basic operations in F(t) ∂ t , such as computing the least common left multiple (LCLM) of operators, have been developed in [10,6].
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 ∂ 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 ∂ t -separable functions.
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 , . . . , V s ) be any set partition of the variables v = {t, x) such that f = g 1 + · · · + g n . By definition, we have f = p/q with p, q ∈ F[t, 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 K = F(x) and p ∈ K[t] be an irreducible polynomial in t. For any f ∈ K(t), we can write f = p m a/b, where m ∈ Z, a, b ∈ K[t] with gcd(a, b) = 1 and p ∤ ab. Conventionally, we set ν p (0) = +∞. The integer m is called the order of f at p, denoted by ν p (f ). We collect some basic properties of valuations as follows and refer to [9,Chapter 4] for their proofs.
(iii) If ν p (f ) = 0, then ν p (D t (f )) = ν p (f ) − 1. In particular, for any i ∈ N, The dispersion introduced by Abramov in [1] can be viewed as a shift analogue of the order. For any polynomial u ∈ K[t] with deg t (u) ≥ 1, the dispersion of u, denoted by dis(u), is defined as max{k ∈ N | gcd(u, σ k t (u)) = 1}, which is the maximal integer root-distance |α − β| with α, β being roots of u inK. Define dis(u) = 0 if u ∈ K \ {0} and dis(0) = +∞. For a rational function f = a/b ∈ K(t) with a, b ∈ K[t] and gcd(a, b) = 1, define dis(f ) = dis(b). For later use, we introduce a local version of Abramov's dispersion. Let p ∈ K[t] be an irreducible polynomial. If σ i t (p) | u for some i ∈ Z, the local dispersion of u at p, denoted by dis p (u), is defined as the maximal integer distance |i − j| with i, j ∈ Z satisfying σ i t (p) | u and σ j t (p) | u; otherwise we define dis p (u) = 0. Conventionally, we set dis p (0) = +∞. For a rational function f = a/b ∈ K(t) with a, b ∈ K[t] and gcd(a, b) = 1, we also define dis p (f ) = dis p (b). By definition, we have dis(u) = max{dis p (u) | p is an irreducible factor of u}.
The set {σ i t (p) | i ∈ Z} is called the σ t -orbit at p, denoted by [p] σt . Note that dis p (u) = dis q (u) if q ∈ [p] σt . So we can define the local dispersion of a rational function f at a σ t -orbit at p, denoted by dis [p]σ t (f ).
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].
Proof. Let d = dis p (b). Without loss of generality, we may assume that p | b but σ i t (p) ∤ b for any i < 0. Since gcd(a, b) = 1 and σ t is a K-automorphism of Applying L to f yields and gcd(A, B) = 1. Then B | u and dis p (L(f )) = dis p (B) by definition. Since σ i t (p) ∤ ℓ 0 and σ i t (p) ∤ ℓ ρ for any i ∈ Z, we have both p and σ d+ρ t (p) do not divide the sum ρ i=0 ℓ i σ i t (a)u i , but they divide u. So p | B and σ d+ρ t (p) | B, which implies that dis p (B) ≥ d + ρ. Since B | u, we have dis p (B) ≤ dis p (u) = d + ρ. Therefore, dis p (L(f )) = d + ρ.

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 F(t, x). By the Ostrogradsky-Hermite reduction [22,18], we can decompose f into the form x] with gcd(p, q) = 1. Since the shift operator S t is an F(x)automorphism and preserves the degrees in t and x, and q is also squarefree in x over F(t). This implies the operator L is a telescoper of type 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 ∈ F(t, x) into the form Note that any factor of a shift-free polynomial is still shift-free. So q is shift-free and deg 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.
Proof. Assume that f is semi-split in t and x. Then For the necessity we assume that f = a/b with a, b ∈ F[t, x] and gcd(a, b) = 1 is ∂ t -separable, i.e., there exists a nonzero operator L = ρ i=0 ℓ i ∂ i t ∈ F(t) ∂ t with ℓ ρ = 0 such that L(f ) = 0. It suffices to show that the denominator b is split with respect to t and 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 ∂ t . In the case which leads to an contradiction. In the case when ∂ t = S t , we may always assume that ℓ i ∈ F[t] and ℓ 0 = 0 since σ t is an F(x)-automorphism of F(t, x). Since ℓ 0 and ℓ ρ are free of x, we have σ i t (p) ∤ ℓ 0 ℓ ρ for any i ∈ Z. By Lemma 2.6, we get dis p (L(f )) = dis p (f ) + ρ < ∞, which contradicts with dis p (L(f )) = dis p (0) = +∞.
Remark 3.2. With the above theorem, we can detect easily the ∂ t -separability of rational functions by the computation of contents and derivatives of multivariate polynomials in t.

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 F(t, x), i.e., both σ t (H)/H and σ x (H)/H are in F(t, x). If telescopers of type (S t , S x ) exist for H, Zeilberger's algorithm starts from an ansatz: for x]. The second step of Zeilberger's algorithm is computing the Gosper form of L(H) that gives satisfying that gcd(q, σ i x (r)) = 1 for all i ∈ Z. The last step is finding ℓ 0 , . . . , ℓ ρ ∈ F(t), not all zero, such that the equation has a polynomial solution in F(t) [x]. If so, then L = ρ i=0 ℓ i S i t is a telescoper for H. It may happen that the final choice of the ℓ i 's satisfies that ρ i=0 ℓ 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 ∈ F(t) S t , 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]. and r ∈ F(t) such that Remark 4.2. The above form for ∂ t (H)/H can be detected by algorithms for computing the Gosper form and its differential analogue in [17,7].

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.
By applying the Ostrogradsky-Hermite reduction in y and Abramov's reduction in x to f ∈ F(t, x, y), we get where u, v, r ∈ F(t, x, y), α i , β i ∈ F(t, x) and β i 's are in distinct σ 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 ≤ i ≤ I, either α i is D t -separable in F(t, x) or β i ∈ F(t) and α i ∈ F(t, x)(β i ) has a telescoper of type (D t , S x ). The existence problem of telescopers of type (D t , S x ) in F(t, x)(β) with β ∈ F(t) has been solved in [15]. To completely solve Problem 5.1, it remains to solve the following separability problem.
We assume that F is an algebraically closed and computable subfield of C in the remaining part of this section.

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 ∈ 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 ⊂ R k(x, y) and for any x ∈ k(x, y), either x ∈ R or x −1 ∈ R. Any valuation ring R of k(x, y) is a local ring, whose unique maximal ideal p is called a place of k(x, y) and the quotient field R/p is called the residue field of the place p, denoted by Σ p . Lemma 5.3. Let k(x, y) and f ∈ k[X, Y ] be as above. Assume that (x,ȳ) ∈ k 2 satisfies that f (x,ȳ) = 0 and ∂f ∂Y (x,ȳ) = 0. Then there is a unique place p of k(x, y) containing x −x and y −ȳ. Furthermore, the residue field Σ p of 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 −x and y −ȳ, say p. Let a be the discrete valuation ring (DVR) with respect to p. It is easy to see that the ring k[x, y] is contained in a. Let m be the ideal in k[x, y] generated by x −x and y −ȳ. Then m is a maximal ideal. Denote by R the localization of k[x, y] at m and we still use m to denote the unique maximal ideal of R. Rewriting f (X, Y ) as a polynomial in X −x, Y −ȳ yields that Since ∂f ∂Y (x,ȳ) = 0, one has that ∂f ∂Y (x,ȳ) + (y −ȳ)A(x −x, y −ȳ) is invertible in R and so y −ȳ ∈ (x −x)R. It implies that R is a regular local ring, i.e., a DVR. Therefore R = a, since R ⊂ a. This concludes that p is unique.
We have that Σ p = R/m = k[x, y]/m ∼ = k. Since the field of constants of k(x, y) is a subfield of Σ p under the natural homomorphism, it coincides with k.
Remark 5.4. Let k(x, y) and (x,ȳ) 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− x)).
Theorem 5.5. Let F ⊆ k ⊆ C be fields with 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 ]/ f . Assume that 1. the places of k(t) that ramify in k(t, y) are defined over F, i.e., their uniformizing parameters can be chosen to be 1/t or t − c with c ∈ F.

there exists a solution (a, α) of the system
where a ∈ F and α ∈ k.
Proof. Since (a, α) 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 C, i.e., C[t, Y ]/ f is an integral domain. Let C(t, y) be the quotient field of C[t, Y ]/ f . Then k(t, y) can be considered as a subfield of C(t, y) under the natural homomorphism. From Theorem 3 in [16, page 92], none of places of C(t, y) is ramified with respect to k(t, y). Therefore the condition 1 holds for C(t, y). Proposition 2.1 in [20, page 10] states that there is β ∈ F(t) such that C(t, y) = C(t, β). Now there are g 0 (t), · · · , g n−1 (t) ∈ C(t) such that i=0 q i y i and therefore the set t j β, t j y i j=0,...s,i=0,...n−1 is linearly dependent over C. This set lies in k(t, y, β) 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, β). Denote byk the set of D t -constants of k(t, y, β). Ifk = k, then β ∈ k(t, y), which will conclude the proposition. Therefore it suffices to prove thatk = k. It is easy to verify thatk coincides with the field of constants of k(t, y, β). In the following, we will show that the field of constants of k(t, y, β) is equal to k. From Remark 5.4, k(t, y) and C(t, y) can be embedded into k((t − a)) and C((t − a)) respectively. We will consider them as the subfields of k((t − a)) and C((t − a)) respectively. Since β ∈ C(t, y) ∩ F(t), F is algebraically closed and a ∈ F, β ∈ F((t − a)). Therefore, k(t, y, β) ⊆ k ((t − a)). Since k is algebraically closed in k((t−a)), the field of constants of k(t, y, β) is equal to k. This completes the proof.

Separability criteria
be the minimal polynomial of y ∈ F(t, x). We can always pick (a, α) ∈ F × F(x) such that . Asume that z ∈ F(t, x) also satisfies the equation P (z) = 0. Then z and y are conjugated over F(t, 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 ∈ F(t) D t , L(z) = 0 if and only if L(y) = 0. Thus to detect if there is a nonzero L ∈ F(t) D t 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 ∈ F(t) D t such that L(y) = 0. Let p be a place of K(t) and q a place of K(t, y) that is ramified with respect to p. Suppose that p and q are uniformizing parameters of p and q respectively, and e is the corresponding ramification index. Then p = aq e for some invertible a in the DVR with respect to q. Furthermore assume that p is an irreducible polynomial in K[t]. Let ℘ be a place of C(t, y) lying above q. Then by Theorem 3 in [16, page 92]), ℘ is not ramified with respect to q and so q is a uniformizing parameter of ℘. Since p ∈ ℘, the uniformizing parameter of ℘ ∩ C(t) can be selected as a factor of p, say t − c for some c ∈ C. It is easy to see that p/(t − c) is an invertible element in the DVR with respect to ℘. It implies that t − c =āq e for some invertible elementā and thus K(t, y) can be embedded into C((t − c) 1/e ). Therefore y ∈ 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 F. So c ∈ F and then p = b(t − c) for some b ∈ K. In other words, t − c is a uniformizing parameter of p. Hence K(t, y) satisfies the condition 1 of Theorem 5.5. By Theorem 5.5, there is β ∈ F(t) such that K(t, y) = K(t, β). We now characterize separable algebraic functions as follows.
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 ≤ i ≤ n. Since A n is the LCM of the q i 's, we have A n (x, t) is also split.
Let S be the integral closure of K[t] in K(t, y). Then β, A n (x, t)y ∈ S. Since {1, β, · · · , β ℓ−1 } is a base of K(t, y) over K(t), one has that Setting a i (t) = g i (t)/a(x), we obtain the required expression for y.
Recall that K = F(x, α) and ℓ = [K(t, y) : K(t)]. Since the i-th derivative of y is also in K(t, y) for any i ∈ N, we have that Y = (1, y, y 2 , · · · , y ℓ−1 ) t satisfies a linear differential system of the form 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 Proof. Assume that there exists a nonzero L ∈ F(t) D t 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, β) over K(t). Let β 1 = β, β 2 , · · · , β ℓ be the conjugates of β and σ i ∈ Gal(E/K(t)) such that σ i (β) = β i . Then σ 1 (y), · · · , σ ℓ (y) are all zeroes of P (x, t, y). We will denote the Vandermonde matrix generated by σ 1 (y), · · · , σ ℓ (y) by U (y) and the one generated by β 1 , · · · , β ℓ by U (β). Then U (y) is a fundamental matrix of the system (5.4) and U (β) is a fundamental matrix of a system Y ′ = BY with B ∈ Mat ℓ (F(t)). Using the argument similar to that in the proof of Proposition 5.7, we have that for all j with 1 ≤ j ≤ ℓ − 1, where a i,j (t) ∈ K[t] and b(t), q(t) are as in Proposition 5.6. Applying σ l to both sides of the equalities (5.5) implies that where j = 1, · · · , ℓ − 1, l = 1, · · · , ℓ. Letã i,j = a i,j b ℓ−1−j and that is an element in Mat ℓ (K[t]). Then the equations (5.6) can be rewritten as U (y) = (GU (β))/(b(t) ℓ−1 q(t)). Hence G is invertible and an easy calculation yields that This implies that Now we prove the converse. Assume that there is an invertible matrix G ∈ Mat ℓ (K[t]) such thatB Then U (y) = GF , where F is a fundamental matrix of Y ′ =BY with entries in some differential extension field of K(t). Obviously, the entries of both G and F are annihilated by nonzero operators in F(t) D t and thus so are the sum of products of entries of G and F , in particular, so is y.
Remark 5.8. Once β is computed, one can obtain the linear differential equations Y ′ = BY satisfied by U (β).

An algorithm for testing separability
We now present an algorithm to decide whether a given algebraic function y ∈ F(t, x) is D t -separable or not. For the sake of simplicity, we may take F =Q, the field of all algebraic numbers over Q.
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 where and let K = F(x, α). Then P (x, t, Y ) may be factorized into a product of irreducible polynomials in K[t, Y ]. There is a unique factor of P (x, t, Y ) in K[t, Y ] vanishing at (a, α), denoted byP (x, α, t, Y ). Let K(t, y) be the quotient field of K[t, Y ]/ P (x, α, t, Y ) . Furthermore suppose that K(t, y) satisfies the condition 1 of Theorem 5.5. Then Theorem 5.5 implies that there is β ∈ F(t) such that K(t, y) = K(t, β). We shall show how to find such β.
and S the integral closure of R in K(t, y). Then α, y ∈ S. Suppose thatP The set α i y j |i = 0, · · · , [K : F(x)] − 1, j = 0, · · · , ℓ − 1 is a base of K(t, y) over F(x, t). Let D(x, t) be the discriminant of the above base and let F (x, Y ) be an irreducible polynomial in F[x, Y ] such that F (x, α) = 0. Then we have and for any root Y = γ ofP (c, b, t, Y ) = 0, we have that K(t, y) is isomorphic to K(t, γ).
Proof. Let β ∈ K(t, y) be as above. Since β is algebraic over . Therefore we may write where the b i,j ∈ R. Let (c, b) satisfy the hypothesis of the lemma and consider the ideal Note that p is a maximal ideal. The Going Up Theorem implies that there is a maximal ideal q ⊳ S such that q ∩ R[α] = p. In particular, D(x, t) / ∈ q. There is a natural map φ : S → S/q. We will let M denote the field S/q. The element γ = φ(y) is a root ofP (c, b, t, γ) = 0. Since the minimal polynomial Q(t, Y ) of β lies in F[t, Y ], it remains unchanged when we apply φ to its coefficients. Therefore φ(β) satisfies Q(t, φ(β)) = 0. In particular, the degree of φ(β) over F(t) is equal to ℓ, the degree of K(t, β) over K(t). Since . Note thatP (c, b, t, Y ) = 0. The element γ satisfies P (c, b, t, γ) = 0 and so it has degree at most ℓ over F(t). Since φ(β) ∈ F(t, γ), we have that γ). This implies that K(t, y) is isomorphic to K(t, γ).
LetP (x, α, t, Y ) be as above. Lemma 5.9 implies that if y is D t -separable then one can compute (c, b) ∈ F m+1 such thatP (c, b, t, Y ) is irreducible over F(t) and β can be taken to be a zero ofP (c, b, t, Y ). FromP (c, b, t, Y ), we can construct the associated differential equation of β over F(t). Denote this associated differential equation by Y ′ = BY with B ∈ Mat ℓ (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 where q(t) is the discriminant of {1, β, · · · , β ℓ−1 } and Y ′ = 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 , 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 Output: "Yes" if y is D t -separable, otherwise "No", where y ∈ k(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 (x, t, Y ) into a monic polynomial by replacing Y by Y /A n and clear the denominators.
(3.b) Decompose P into a product of irreducible polynomials over F(x, α).
where F is the minimal polynomial of α over F(x) and B ℓ (x) is the leading coefficient ofP (x, α, t, Y ).
We now show an example to illustrate the main steps of the above algorithm.
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 β.

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].