A difference ring theory for symbolic summation. (January 2016)

• Record Type: Journal Article
• Authors: Schneider, Carsten
• Is Part Of: Journal of symbolic computation. Volume 72(2016)
• Page Start: 82
• Page End: 127
• Publication Date: 2016-01
• Subjects: Difference ring extensions -- Roots of unity -- Indefinite nested sums and products -- Parameterized telescoping (telescoping creative telescoping) -- Semi-constants -- Semi-invariants; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.02.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: A summation framework is developed that enhances Karr's difference field approach. It covers not only indefinite nested sums and products in terms of transcendental extensions, but it can treat, e.g., nested products defined over roots of unity. The theory of the so-called R Π Σ ⁎ -extensions is supplemented by algorithms that support the construction of such difference rings automatically and that assist in the task to tackle symbolic summation problems. Algorithms are presented that solve parameterized telescoping equations, and more generally parameterized first-order difference equations, in the given difference ring. As a consequence, one obtains algorithms for the summation paradigms of telescoping and Zeilberger's creative telescoping. With this difference ring theory one gets a rigorous summation machinery that has been applied to numerous challenging problems coming, e.g., from combinatorics and particle physics.