| Popis: |
In the past few decades, numerous tools for automatically discovering and proving identities involving sequences and special functions were developed. These tools are often based on algorithms which manipulate sequences satisfying linear recurrences. If the recurrences have constant coefficients, these sequences are called $C$-finite and in the case of polynomial coefficients they are called $D$-finite. We study sequences satisfying recurrences with coefficients which are $C$-finite themselves and call them $C^2$-finite. We investigate which properties and algorithms carry over from the classical $C$-finite and $D$-finite cases to this new setting. In particular, we show that most so-called closure-properties, which are known for the classical cases, also hold for $C^2$-finite sequences, i.e., they are closed under termwise addition, termwise multiplication, interlacing and taking subsequences at arithmetic progressions. In many cases these operations are effective and we present algorithms for performing them. In general, however, these algorithms are closely related to and limited by certain decision procedures of $C$-finite sequences. Deciding whether every term of a sequence is positive or nonzero is not known to be decidable in theory. Nevertheless, we show that it is often easy to decide these properties in practice. Restricting the ring of $C^2$-finite sequence to sequences which satisfy a monic (i.e., having constant leading coefficient) linear recurrence with $C$-finite coefficients, we obtain a subring where all closure properties can be performed effectively. On the other hand, we can allow more general sequences as coefficients. This way we obtain increasingly larger rings where the operations are more difficult to perform. Most of the theoretical results are also implemented in a package for the computer algebra system SageMath. The thesis contains a tutorial for this package. The tutorial shows how the examples given throughout the thesis can be performed automatically on the computer. In den letzten Jahrzehnten wurden zahlreiche Werkzeuge für das automatische Entdecken und Beweisen von Identitäten von Folgen und speziellen Funktionen entwickelt. Diese Werkzeuge basieren oft auf Algorithmen, die Folgen, die lineare Rekursionen erfüllen, manipulieren. Falls die Rekursionen konstante Koeffizienten haben, nennt man die Folgen $C$-finit und im Falle von polynomiellen Koeffizienten nennt man sie $D$-finit. Wir untersuchen Folgen, die Rekursionen mit Koeffizienten erfüllen, die selbst $C$-finit sind und nennen sie $C^2$-finit. Wir untersuchen, welche Eigenschaften und Algorithmen wir vom klassischen $C$-finiten und $D$-finiten Fall auf diese neue Klasse übertragen können. Insbesondere zeigen wir, dass die meisten sogenannten closure properties, die für die klassischen Fälle bekannt sind, auch für $C^2$-finite Folgen gelten. D.h., sie sind abgeschlossen bezüglich termweiser Addition, termweiser Multiplikation und Verflechtung. Außerdem ist die Teilfolge von $C^2$-finiten Folgen wieder $C^2$-finit. Diese Operationen sind häufig effektiv und wir stellen Algorithmen vor, die diese Berechnungen durchführen. Im Allgemeinen sind diese Algorithmen jedoch durch bestimmte schwierige Entscheidungsprobleme für $C$-finite Folgen eingeschränkt. Es ist zum Beispiel nicht bekannt, ob die Probleme, dass jeder Term einer Folge positiv oder ungleich null ist, entscheidbar sind. Wir zeigen jedoch, dass diese Probleme in der Praxis oft einfach zu entscheiden sind. Schränkt man den Ring der $C^2$-finiten Folgen auf Folgen ein, die eine normierte (d.h. mit konstantem Leitkoeffizienten) lineare Rekursion mit $C$-finiten Koeffizienten erfüllen, so erhält man einen Unterring, in dem alle closure properties effektiv durchgeführt werden können. Andererseits können wir auch allgemeinere Folgen als Koeffizienten zulassen. Auf diese Weise erhält man größere Ringe, in denen die Operationen schwieriger durchzuführen sind. Die meisten der theoretischen Ergebnisse sind auch in einem Softwarepaket für das Computeralgebrasystem SageMath implementiert. Die Dissertation enthält ein Tutorial für dieses Paket. Das Tutorial zeigt, wie die in der Dissertation gegebenen Beispiele automatisch auf dem Computer ausgeführt werden können. Author Philipp Nuspl Dissertation Universität Linz 2023 |
