Degree bounds to find polynomial solutions of parameterized linear difference equations in \(\Pi\Sigma\)-fields. (English) Zbl 1101.39001
Summary: An important application of solving parameterized linear difference equations in \(\Pi \Sigma\)-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.
MSC:
| 39A10 | Additive difference equations |
| 12H10 | Difference algebra |
| 39B52 | Functional equations for functions with more general domains and/or ranges |
References:
| [1] | 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) · Zbl 0723.65048 |
| [2] | 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) · Zbl 0719.65063 · doi:10.1016/S0041-5553(89)80002-3 |
| [3] | 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 · Zbl 0914.65131 |
| [4] | 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 · Zbl 0914.65132 |
| [5] | 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 · Zbl 1066.05019 |
| [6] | Bronstein, M.: On solutions of linear ordinary difference equations in their coefficient field. J. Symbolic Comput. 29(6), 841–877 June 2000 · Zbl 0961.12004 · doi:10.1006/jsco.2000.0368 |
| [7] | Chyzak, F.: An extension of Zeilberger’s fast algorithm to general holonomic functions. Discrete Math. 217, 115–134 (2000) · Zbl 0968.33011 · doi:10.1016/S0012-365X(99)00259-9 |
| [8] | Cohn, R.M.: Difference Algebra. Interscience Publishers, John Wiley & Sons, 1965 |
| [9] | 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 · Zbl 1102.41015 |
| [10] | 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 · Zbl 1108.41011 |
| [11] | Karr, M.: Summation in finite terms. J. ACM 28, 305–350 (1981) · Zbl 0494.68044 · doi:10.1145/322248.322255 |
| [12] | Karr, M.: Theory of summation in finite terms. J. Symbolic Comput. 1, 303–315 (1985) · Zbl 0585.68052 · doi:10.1016/S0747-7171(85)80038-9 |
| [13] | Paule, P., Schneider, C.: Computer proofs of a new family of harmonic number identities. Adv. in Appl. Math. 31(2), 359–378 (2003) · Zbl 1039.11007 · doi:10.1016/S0196-8858(03)00016-2 |
| [14] | Petkovšek, M.: Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symbolic Comput. 14(2–3), 243–264 (1992) · Zbl 0761.11008 |
| [15] | Petkovšek, M., Weixlbaumer, C.: A comparison of degree polynomials. http://www.fmf.uni-lj.si/\(\sim\)petkovsek/, 2000, Note |
| [16] | Petkovšek, M., Wilf, H.S., Zeilberger, D.: A=B. A. K. Peters, Wellesley, MA, 1996 |
| [17] | Schneider, C.: An implementation of Karr’s summation algorithm in Mathematica. Sém. Lothar. Combin. S43b, 1–10 (2000) |
| [18] | Schneider, C.: Symbolic summation in difference fields. Technical Report 01-17, RISC-Linz, J. Kepler University, 2001, PhD Thesis |
| [19] | Schneider, C.: Solving parameterized linear difference equations in {\(\Pi\)}{\(\Sigma\)}-fields. SFB-Report 02-19, J. Kepler University, Linz, November 2002, Submitted |
| [20] | Schneider, C.: A collection of denominator bounds to solve parameterized linear difference equations in {\(\Pi\)}{\(\Sigma\)}-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 |
| [21] | Schneider, C.: A new Sigma approach to multi-summation. To appear in the Dave Robbins memorial issue of Advances in Applied Math. 2005 |
| [22] | C. Schneider. Product representations in {\(\Pi\)}{\(\Sigma\)}-fields. Annals of Combinatorics, 9(1), 75–99 (2005) |
| [23] | C. Schneider. The summation package Sigma: Underlying principles and a rhombus tiling application. Discrete Math. Theor. Comput. Sci., 6(2), 365–386 (2004) · Zbl 1066.68164 |
| [24] | Schneider, C.: Symbolic summation with single-nested sum extensions. In: J. Gutierrez, (ed.) Proc. ISSAC’04, ACM Press, 2004, pp. 282–289 · Zbl 1134.33329 |
| [25] | van Hoeij, M.: Rational solutions of linear difference equations. In: O. Gloor, (ed.), Proc. ISSAC’98, ACM Press, 1998, pp. 120–123 · Zbl 0919.65088 |
| [26] | Zeilberger, D.: A fast algorithm for proving terminating hypergeometric identities. Discrete Math. 80(2), 207–211 (1990) · Zbl 0701.05001 · doi:10.1016/0012-365X(90)90120-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
