Abstract.
An important application of solving parameterized linear difference equations in ΠΣ-fields, a very general class of difference fields, is simplifying and proving of nested multisum expressions and identities. Together with other reduction techniques described elsewhere, the algorithms considered in this article can be used to search for all solutions of such difference equations. More precisely, within a typical reduction step one often is faced with subproblems to find all solutions of linear difference equations where the solutions live in a polynomial ring. The algorithms under consideration deliver degree bounds for these polynomial solutions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abramov, S.A.: Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations. Moscow Univ. Comput. Math. Cybernet. 3, 63–68 (1989)
Abramov, S.A.: Rational solutions of linear differential and difference equations with polynomial coefficients. U.S.S.R. Comput. Math. Math. Phys. 29(6), 7–12 (1989)
Abramov, S.A.: Rational solutions of linear difference and q-difference equations with polynomial coefficients. In: T. Levelt, (ed.), Proc. ISSAC’95, ACM Press, New York, 1995, pp. 285–289
Abramov, S.A., Bronstein, M., Petkovšek, M.: On polynomial solutions of linear operator equations. In: T. Levelt, (ed.), Proc. ISSAC’95, ACM Press, New York, 1995, pp. 290–296
Andrews, G.E., Paule, P., Schneider, C.: Plane partitions VI: Stembridge’s TSPP Theorem. To appear in the Dave Robbins memorial issue of Advances in Applied Math., 2005
Bronstein, M.: On solutions of linear ordinary difference equations in their coefficient field. J. Symbolic Comput. 29(6), 841–877 June 2000
Chyzak, F.: An extension of Zeilberger’s fast algorithm to general holonomic functions. Discrete Math. 217, 115–134 (2000)
Cohn, R.M.: Difference Algebra. Interscience Publishers, John Wiley & Sons, 1965
Driver, K., Prodinger, H., Schneider, C., Weideman, A.: Padé approximations to the logarithm II: Identities, recurrences, and symbolic computation. To appear in Ramanujan Journal, 2005
Driver, K., Prodinger, H., Schneider, C., Weideman, A.: Padé approximations to the logarithm III: Alternative methods and additional results. To appear in Ramanujan Journal, 2005
Karr, M.: Summation in finite terms. J. ACM 28, 305–350 (1981)
Karr, M.: Theory of summation in finite terms. J. Symbolic Comput. 1, 303–315 (1985)
Paule, P., Schneider, C.: Computer proofs of a new family of harmonic number identities. Adv. in Appl. Math. 31(2), 359–378 (2003)
Petkovšek, M.: Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symbolic Comput. 14(2–3), 243–264 (1992)
Petkovšek, M., Weixlbaumer, C.: A comparison of degree polynomials. http://www.fmf.uni-lj.si/~petkovsek/, 2000, Note
Petkovšek, M., Wilf, H.S., Zeilberger, D.: A=B. A. K. Peters, Wellesley, MA, 1996
Schneider, C.: An implementation of Karr’s summation algorithm in Mathematica. Sém. Lothar. Combin. S43b, 1–10 (2000)
Schneider, C.: Symbolic summation in difference fields. Technical Report 01-17, RISC-Linz, J. Kepler University, 2001, PhD Thesis
Schneider, C.: Solving parameterized linear difference equations in ΠΣ-fields. SFB-Report 02-19, J. Kepler University, Linz, November 2002, Submitted
Schneider, C.: A collection of denominator bounds to solve parameterized linear difference equations in ΠΣ-extensions. In: D. Petcu, V. Negru, D. Zaharie, T. Jebelean, (eds.), Proc. SYNASC04, 6th Internat. Symposium on Symbolic and Numeric Algorithms for Scientific Computation, Timisoara (Romania), September 2004. Mirton Publishing. ISBN 973-661-441-7, pp. 269–282
Schneider, C.: A new Sigma approach to multi-summation. To appear in the Dave Robbins memorial issue of Advances in Applied Math. 2005
C. Schneider. Product representations in ΠΣ-fields. Annals of Combinatorics, 9(1), 75–99 (2005)
C. Schneider. The summation package Sigma: Underlying principles and a rhombus tiling application. Discrete Math. Theor. Comput. Sci., 6(2), 365–386 (2004)
Schneider, C.: Symbolic summation with single-nested sum extensions. In: J. Gutierrez, (ed.) Proc. ISSAC’04, ACM Press, 2004, pp. 282–289
van Hoeij, M.: Rational solutions of linear difference equations. In: O. Gloor, (ed.), Proc. ISSAC’98, ACM Press, 1998, pp. 120–123
Zeilberger, D.: A fast algorithm for proving terminating hypergeometric identities. Discrete Math. 80(2), 207–211 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the SFB-grant F1305 and the grant P16613-N12 of the Austrian FWF.
Rights and permissions
About this article
Cite this article
Schneider, C. Degree Bounds to Find Polynomial Solutions of Parameterized Linear Difference Equations in ΠΣ-Fields. AAECC 16, 1–32 (2005). https://doi.org/10.1007/s00200-004-0167-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-004-0167-3