Symbolische Summation von Differenzenkörpern

Das algorithmische Problem der symbolischen Summation kann als das diskrete Analogon der symbolischen Integration angesehen werden. Mit anderen Worten versuchen Summationsalgorithmen anstelle des Vereinfachens von Integralen, einfache Darstellungen von kompliziert aufgebauten Summenausdrücken zu finden. In Anwendungen aus der Chemie, Informatik, Mathematik oder Physik treten solche Summen häufig im Zusammenhang mit Abzählproblemen auf. Historisch gesehen begann die moderne symbolische Summation erst kürzlich, nämlich mit Gospers Algorithmus (1978), der ein Entscheidungsverfahren für indefinite hypergeometrische Summation darstellt. Die nächsten wichtigen Durchbrüche wurden von Karr (1981) und Zeilberger (1990) erreicht. Erst vor kurzem entwickelte Schneider in seiner Doktorarbeit Karrs Summationstheorie entscheidend weiter. Insbesondere konnte er Zeilbergers "creative telescoping" für definite hypergeometrische Summen auf Summen erweitern, die in einem sehr allgemeinen algebraischen Bereich, nämlich sogenannten Differenzenkörpern, ausdrückbar sind. Die vorgeschlagene wissenschaftliche Arbeit beschäftigt sich mit offenen Problemen, die im Zusammenhang mit Schneiders Differenzenkörper Methode stehen. Das allgemeine Ziel ist, eine allgemeine Theorie analog zum Integrieren zu erhalten. Besondere Betonung wird auf Computeralgebra Implementierungen gelegt, die Wissenschaftler in praktischer Problemlösung unterstützen.

Verschiedene Aspekte verschiedener Zugaenge zum Symbolischen Summieren wurden waehrend dieses Projekts in verschiedene Richtungen erweitert. Symbolisches Summieren befasst sich mit dem Problem, einen mathematischen Ausdruck mit Summationszeichen systematisch in einen aequivalenten aber einfacheren Ausdruck zu ueberfuehren, wobei "einfacher" bedeuten kann, dass der neue Ausdruck keine Summationszeichen mehr enthaelt, oder weniger als der urspruengliche Ausdruck, oder dass die Summationszeichen in einer guenstigeren Anordnung auftreten. Im Idealfall kann eine systematische Prozedur (d.h. ein Algorithmus) zur Umwandlung eines Summenausdrucks in diesem Sinne von einem Computer durchgefuehrt warden. Forschung in Symbolischen Summieren verbindet sowohl theoretische Aspekte (z.B. das Auffinden von Strukturaussagen, die die Form potentieller geschlossener Darstellungen einschraenken) als auch praktische Aspekte (z.B. konkrete Summationsalgorithmen zu entwickeln und sie in auf einem Computer zu implementieren). Mehrere Algorithmen zum Symbolischen Summieren wurden in der Vergangenheit vorgeschlagen, und mehrere Software-Pakete stehen zur Verfuegung. In diesem Projekt haben wir uns hauptsaechlich mit der Erweiterung eines Summationsalgorithmus befasst, der 1981 von Karr angegeben wurde. Aussderdem haben wir neue Summationsalgorithmen und Algorithmen zur Behandlung von Rekurrenzen entwickelt, die eng mit dem Summationsproblem verwandt sind. Die wichtigsten Ergebnisse des Projekts, dokumentiert durch mehr als 30 referierte wissenschaftliche Artikel, betreffen: Algorithmen zur Behandlung verschachtelter Summen (z.B. zum automatischen Minimieren der Schachtelungstiefe einer Summe) Algorithmen zur Behandlung linearer Rekurrenzen (z.B. zum automatischen Auffinden sogenannter verallgemeinerter d`Alembert Loesungen solcher Gleichungen) Algorithmen zur Behandlung nichtlinearer Rekurrenzen (z.B. zum automatischen Auffinden von algebraischen Abhaengigkeiten zwischen Loesungen solcher Gleichungen) Algorithmen zur Behandlung von Ungleichungen fuer Spezielle Funktionen (z.B., zum automatischen Beweisen der Positivitaet gewisser kombinatorischer Folgen) Die Bedeutung unserer Beitraege wird dadurch unterstrichen, dass viele unserer Algorithmen Probleme loesen, die von keiner anderen derzeit bekannten Methode geloest werden koennen. Die Ergebnisse des Projekts haben unmittelbare Auswirkungen auf klassische Zweige der Mathematik wie die Kombinatorik oder die Theorie der speziellen Funktionen. Ausserdem gibt es Anwendungen in finiten Elementen (Numerik), in der Quantenfeldtheorie (Teilchenphysik) und anderen Disziplinen, die auf den ersten Blick nicht verwandt zu sein scheinen. Mit Hilfe der Software, die in diesem Projekt entwickelt wurde, ist es bereits gelungen, Loesungen zu mehreren offenen Problemen anzugeben, die in in diesen Bereichen aufgetreten sind.