Die Allgegenwart der Klasse der D-finiten Funktionen und der P-rekursiven Folgen im Gebiet des Symbolischen Rechnens ist allgemein bekannt. Diese Klasse ist definiert durch lineare Differential- und Differenzengleichungen mit polynomiellen Koeffizienten. Die Ergebnisse dieser Arbeit bestehen aus Teilen, die mit dieser Klasse zu tun haben. Im ersten Teil verallgemeinern wir die reduktions-basierten Algorithmen für creative telescoping auf den hypergeometrischen Fall. Diese Verallgemeinerung erlaubt eine effizientere Behandlung von definiten Summen hypergeometrischer Terme. Die Abramov-Petkovsek-Reduktion berechnet eine additive Zerlegung eines gegebenen hypergeometrischen Terms, durch die die Funktionalität des Gosper- Algorithmus für indefinite hypergeometrische Summen erweitert. Wir adaptieren diese Reduktion so, dass sie einen hypergeometrischen Term in einen summierbaren und einen nichtsummierbaren Term zerlegt. Eigenschaften des Outputs der ursprünglichen Zerlegung bleiben für unsere modifizierte Version erhalten. Darüber hinaus braucht man bei der modifizierten Reduktion keine lineare Hilfsrekurrenz explizit zu lösen. Ausgehend von der modifizierten Reduktion entwickeln wir einen neuen Algorithmus zur Berechnung minimaler Telescoper für bivariate hypergeometrische Terme. Dieser neue Algorithmus can die teure Berechnung von Zertifikaten vermeiden, und gemäß unserer Experimente läuft er schneller als der klassische Zeilberger-Algorithmus, egal ob man Zertifikate mitberechnet oder nicht. Wir verwenden außerdem ein neues Argument für die Terminierung der genannten neuen Algorithmen, das es uns erlaubt, Schranken für die Ordnung des minimalen Telescopers herzuleiten. Verglichen mit den bekannten Schranken in der Literatur sind unsere Schranken manchmal besser und nie schlechter als die bekannten. Im zweiten Teil der Arbeit untersuchen wir die Klasse der D-finiten Zahlen, die eng verwandt mit D-finiten Funktionen und P-rekursiven Folgen ist. Sie besteht aus den Grenzwerten der konvergenten P-rekursiven Folgen. Typischerweise enthält diese Klasse neben den algebraischen Zahlen viele weitere bekannte mathematische Konstanten. Unsere Definition der Klasse der D-finiten Zahlen hängt von zwei Unterringen des Körpers der komplexen Zahlen ab. Wir untersuchen, wie die Klasse von der Wahl dieser zwei Unterringe abhängt. Außerdem zeigen wir, dass die D-finiten Zahlen über dem Körper der Gaußschen rationalen Zahlen im wesentlichen dieselben Zahlen sind, die auch als Werte von D-finiten Funktionen an nicht-singulären algebraischen Argumenten auftreten (die sogenannten regulären holonomen Konstanten). Dieses Resultat erleichtert es, gewisse Zahlen als Elemente der Klasse zu erkennen.
Abstract
The ubiquity of the class of D-finite functions and P-recursive sequences in symbolic computation is widely recognized. This class is defined in terms of linear differential and difference equations with polynomial coefficients. In this thesis, the presented work consists of two parts related to this class. In the first part, we generalize the reduction-based creative telescoping algorithms to the hypergeometric setting. This generalization allows to deal with definite sums of hypergeometric terms more quickly. The Abramov-Petkovsek reduction computes an additive decomposition of a given hypergeometric term, which extends the functionality of Gosper's algorithm for indefinite hypergeometric summation. We modify this reduction so as to decompose a hypergeometric term as the sum of a summable term and a nonsummable one. Properties satisfied by the output of the original reduction carry over to our modified version. Moreover, the modified reduction does not solve any auxiliary linear difference equation explicitly. Based on the modified reduction, we design a new algorithm to compute minimal telescopers for bivariate hypergeometric terms. This new algorithm can avoid the costly computation of certificates, and outperforms the classical Zeilberger algorithm no matter whether certificates are computed or not according to the computational experiments. We further employ a new argument for the termination of the above new algorithm, which enables us to derive order bounds for minimal telescopers. Compared to the known bounds in the literature, our bounds are sometimes better, and never worse than the known ones. In the second part of the thesis, we study the class of D-finite numbers, which is closely related to D-finite functions and P-recursive sequences. It consists of the limits of convergent P-recursive sequences. Typically, this class contains many well-known mathematical constants in addition to the algebraic numbers. Our definition of the class of D-finite numbers depends on two subrings of the field of complex numbers.We investigate how different choices of these two subrings affect the class. Moreover, we show that D-finite numbers over the Gaussian rational field are essentially the same as the values of D-finite functions at non-singular algebraic number arguments (so-called the regular holonomic constants). This result makes it easier to recognize certain numbers as belonging to this class.
