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.
Introduction
In the realm of mathematical physics and engineering, the "separation of variables" is a foundational technique used to solve partial differential equations. In symbolic computation, a parallel challenge exists within the framework of creative telescoping—an algorithmic paradigm used to prove mathematical identities and evaluate complex integrals or sums. The core of this challenge is the Separability Problem: determining whether a multivariate function satisfies a linear differential or difference equation in just one of its variables.
This paper establishes a rigorous algorithmic framework for identifying these functions. Identifying "separable" functions is not merely a theoretical exercise; it is a practical necessity in computer algebra. It dictates whether creative telescoping algorithms, such as Zeilberger’s algorithm, will terminate successfully or fail due to structural issues like division by zero.
The Role of Creative Telescoping
Creative telescoping aims to find a "telescoper"—a linear operator in one variable (say, $t$)—and a "certificate" (a function $g$) such that the original function $f$ satisfies a specific relation. The existence of such a telescoper is intrinsically tied to the separability of the function's remainder after reduction. If a function is $\partial_t$-separable, its behavior in variable $t$ can be completely described by a linear differential or difference equation that effectively ignores the other variables (e.g., $x$).
Algorithmic Criteria for Function Classes
The authors categorize the separability problem into distinct function classes, providing specific decision procedures for each:
1. Rational Functions
For rational functions, the authors utilize classical reduction techniques, specifically Ostrogradsky-Hermite and Abramov’s reduction. They establish Theorem 3.1, which provides a definitive "if and only if" condition: a rational function is separable if and only if it is "semi-split." A semi-split function is essentially a sum of terms where the variables are already algebraically separated.
2. Hyperexponential and Hypergeometric Terms
Moving to special functions, the paper leverages Gosper’s algorithm and its differential analogues. Theorem 4.1 characterizes separability based on the "multiplicative derivative" of the function. The authors prove that for these terms, separability depends on whether this derivative can be expressed in a specific form involving a rational function and its own derivative.
3. Algebraic Functions
The paper’s most significant technical contribution lies in its treatment of algebraic functions. The authors develop a "descent theorem" to reduce the complexity of the problem. They introduce Algorithm 5.10, a complete decision procedure that tests for separability by:
- Constructing an associated differential system.
- Searching for a specific type of invertible matrix transformation ($G$) that maps the system into a simpler field.
In Example 5.11, the authors demonstrate this algorithm on a non-trivial algebraic curve: $y^2 - 2(xt+1)y + (xt+1)^2 - t$. The algorithm successfully proves this function is $D_t$-separable, illustrating the power of the descent approach.
Key Theoretical Insights
Beyond the algorithms themselves, the paper introduces several vital mathematical tools:
- Local Dispersion: A "local version" of Abramov’s dispersion is introduced to track how the poles and roots of a function shift under difference operators. This serves as a key indicator of separability in discrete (shift) cases.
- Field Extension Descent: For algebraic functions, the authors demonstrate that separability is a property of the field extension in which the function resides. By finding a specific basis for the function that satisfies a differential system, the problem can be "descended" to a more manageable case.
Conclusion and Future Work
This work provides a comprehensive solution for the most common classes of functions used in automated identity proving. However, the authors identify several avenues for future research:
- Generalization: Extending these methods to the broader class of D-finite functions (functions satisfying linear differential equations with polynomial coefficients) and P-recursive sequences.
- Computational Efficiency: While the proposed algorithms are decidable, further optimization is required to handle large-scale multivariate inputs in symbolic software.
- Termination Problems: These criteria offer a potential path toward solving the "general termination problem" for Zeilberger-style algorithms, providing a theoretical boundary for when these algorithms should stop searching for a solution.
Summary updated