On the length of integers in telescopers for proper hypergeometric terms. (January 2015)

• Record Type: Journal Article
• Authors: Kauers, Manuel; Yen, Lily
• Is Part Of: Journal of symbolic computation. Volume 66(2015)
• Page Start: 21
• Page End: 33
• Publication Date: 2015-01
• Subjects: Symbolic summation -- Hypergeometric identities -- Zeilberger's algorithm; 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.2014.02.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We show that the number of digits in the integers of a creative telescoping relation of expected minimal order for a bivariate proper hypergeometric term has essentially cubic growth with the problem size. For telescopers of higher order but lower degree we obtain a quintic bound. Experiments suggest that these bounds are tight. As applications of our results, we give an improved bound on the maximal possible integer root of the leading coefficient of a telescoper, and the first discussion of the bit complexity of creative telescoping.