Summation theory. II: Characterizations of \(R {\Pi}{\Sigma}^{\ast}\)-extensions and algorithmic aspects. (English) Zbl 1403.12002
Summary: Recently, \(R \Pi \Sigma^\ast\)-extensions have been introduced which extend M. Karr’s \(\Pi \Sigma^\ast\)-fields substantially [J. ACM 28, 305–350 (1981; Zbl 0494.68044); J. Symb. Comput. 1, 303–315 (1985; Zbl 0585.68052)]: one can represent expressions not only in terms of transcendental sums and products, but one can work also with products over primitive roots of unity. Since one can solve the parameterized telescoping problem in such rings, covering as special cases the summation paradigms of telescoping and creative telescoping, one obtains a rather flexible toolbox for symbolic summation. This article is the continuation of this work. Inspired by Singer’s Galois theory of difference equations we will work out several alternative characterizations of \(R\Pi \Sigma^\ast\)-extensions: adjoining naively sums and products leads to an \(R\Pi \Sigma^\ast\)-extension iff the obtained difference ring is simple iff the ring can be embedded into the ring of sequences iff the ring can be given by the interlacing of \(\Pi \Sigma^\ast\)-extensions. From the viewpoint of applications this leads to a fully automatic machinery to represent indefinite nested sums and products in such \(R \Pi \Sigma^\ast\)-rings. In addition, we work out how the parameterized telescoping paradigm can be used to prove algebraic independence of indefinite nested sums. Furthermore, one obtains an alternative reduction tactic to solve the parameterized telescoping problem in basic \(R\Pi \Sigma^\ast\)-extensions exploiting the interlacing property.
Keywords:
difference ring extensions; roots of unity; indefinite nested sums and products; simple difference rings; difference ideals; constants; interlacing of difference rings; embedding into the difference ring of sequences; Galois theoryReferences:
| [1] | Ablinger, J.; Behring, A.; Blümlein, J.; De Freitas, A.; von Manteuffel, A.; Schneider, C., Calculating three loop ladder and V-topologies for massive operator matrix elements by computer algebra, Comput. Phys. Commun., 202, 33-112 (2016) · Zbl 1348.81034 |
| [2] | Ablinger, J.; Blümlein, J.; Raab, C. G.; Schneider, C., Iterated binomial sums and their associated iterated integrals, J. Math. Phys., 55, 112301, 1-57 (2014) · Zbl 1306.81141 |
| [3] | Ablinger, J.; Blümlein, J.; Schneider, C., Harmonic sums and polylogarithms generated by cyclotomic polynomials, J. Math. Phys., 52, 10, 1-52 (2011) · Zbl 1272.81127 |
| [4] | Ablinger, J.; Blümlein, J.; Schneider, C., Analytic and algorithmic aspects of generalized harmonic sums and polylogarithms, J. Math. Phys., 54, 8, 1-74 (2013) · Zbl 1295.81071 |
| [5] | Ablinger, J.; Schneider, C., Algebraic independence of (cyclotomic) harmonic sums (2015) |
| [6] | Abramov, S. A., The rational component of the solution of a first-order linear recurrence relation with a rational right-hand side, USSR Comput. Math. Math. Phys.. USSR Comput. Math. Math. Phys., Ž. Vyčisl. Mat. Mat. Fiz., 15, 1035-1039 (1975), Transl. from · Zbl 0326.65069 |
| [7] | Abramov, S. A., Rational solutions of linear differential and difference equations with polynomial coefficients, USSR Comput. Math. Math. Phys., 29, 6, 7-12 (1989) · Zbl 0719.65063 |
| [8] | Abramov, S. A.; Petkovšek, M., D’Alembertian solutions of linear differential and difference equations, (von zur Gathen, J., Proc. ISSAC’94 (1994), ACM Press), 169-174 · Zbl 0919.34013 |
| [9] | Abramov, S. A.; Petkovšek, M., Polynomial ring automorphisms, rational \((w, \sigma)\)-canonical forms, and the assignment problem, J. Symb. Comput., 45, 6, 684-708 (2010) · Zbl 1189.33038 |
| [10] | Abramov, S. A.; Zima, E. V., D’Alembertian solutions of inhomogeneous linear equations (differential, difference, and some other), (Proc. ISSAC’96 (1996), ACM Press), 232-240 · Zbl 0966.34005 |
| [11] | Apagodu, M.; Zeilberger, D., Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Adv. Appl. Math., 37, 139-152 (2006) · Zbl 1108.05010 |
| [12] | Bauer, A.; Petkovšek, M., Multibasic and mixed hypergeometric Gosper-type algorithms, J. Symb. Comput., 28, 4-5, 711-736 (1999) · Zbl 0973.33010 |
| [13] | Blümlein, J., Algebraic relations between harmonic sums and associated quantities, Comput. Phys. Commun., 159, 1, 19-54 (2004) · Zbl 1097.11063 |
| [14] | Blümlein, J.; Kurth, S., Harmonic sums and Mellin transforms up to two-loop order, Phys. Rev. D, 60 (1999) |
| [15] | Bronstein, M., On solutions of linear ordinary difference equations in their coefficient field, J. Symb. Comput., 29, 6, 841-877 (2000) · Zbl 0961.12004 |
| [16] | Chen, S.; Chyzak, F.; Feng, R.; Fu, G.; Li, Z., On the existence of telescopers for mixed hypergeometric terms, J. Symb. Comput., 68, part 1, 1-26 (2015) · Zbl 1303.33024 |
| [17] | Chen, S.; Kauers, M., Order-degree curves for hypergeometric creative telescoping, (van der Hoeven, Joris; van Hoeij, Mark, Proceedings of ISSAC 2012 (2012)), 122-129 · Zbl 1323.68591 |
| [18] | Chyzak, F., An extension of Zeilberger’s fast algorithm to general holonomic functions, Discrete Math., 217, 115-134 (2000) · Zbl 0968.33011 |
| [19] | Cohn, R. M., Difference Algebra (1965), Interscience Publishers, John Wiley & Sons · Zbl 0127.26402 |
| [20] | Eröcal, B., Algebraic extensions for summation in finite terms (February 2011), RISC, Johannes Kepler University: RISC, Johannes Kepler University Linz, PhD thesis |
| [21] | Hardouin, C.; Singer, M. F., Differential Galois theory of linear difference equations, Math. Ann., 342, 2, 333-377 (2008) · Zbl 1163.12002 |
| [22] | Hendriks, P. A.; Singer, M. F., Solving difference equations in finite terms, J. Symb. Comput., 27, 3, 239-259 (1999) · Zbl 0930.39004 |
| [23] | Karpilovsky, G., On finite generation of unit groups of commutative group rings, Arch. Math. (Basel), 40, 6, 503-508 (1983) · Zbl 0498.16004 |
| [24] | Karr, M., Summation in finite terms, J. ACM, 28, 305-350 (1981) · Zbl 0494.68044 |
| [25] | Karr, M., Theory of summation in finite terms, J. Symb. Comput., 1, 303-315 (1985) · Zbl 0585.68052 |
| [26] | Kauers, M.; Schneider, C., Indefinite summation with unspecified summands, Discrete Math., 306, 17, 2021-2140 (2006) · Zbl 1157.05006 |
| [27] | Kauers, M.; Schneider, C., Symbolic summation with radical expressions, (Brown, C. W., Proc. ISSAC’07 (2007)), 219-226 · Zbl 1190.68091 |
| [28] | Kauers, M.; Zimmermann, B., Computing the algebraic relations of c-finite sequences and multisequences, J. Symb. Comput., 43, 11, 787-803 (2008) · Zbl 1163.11084 |
| [29] | Koutschan, C., Creative telescoping for holonomic functions, (Schneider, C.; Blümlein, J., Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions. Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts Monogr. Symbol. Comput. (2013), Springer), 171-194 · Zbl 1308.81102 |
| [30] | Levin, A., Difference Algebra, Algebra Appl., vol. 8 (2008), Springer: Springer New York · Zbl 1209.12003 |
| [31] | Moch, S. O.; Uwer, P.; Weinzierl, S., Nested sums, expansion of transcendental functions, and multiscale multiloop integrals, J. Math. Phys., 6, 3363-3386 (2002) · Zbl 1060.33007 |
| [32] | Neher, E., Invertible and nilpotent elements in the group algebra of a unique product group, Acta Appl. Math., 108, 1, 135-139 (2009) · Zbl 1189.16023 |
| [33] | Ocansey, E.D., Schneider, C., 2016. Representing \((q\); Ocansey, E.D., Schneider, C., 2016. Representing \((q\) · Zbl 1365.12004 |
| [34] | Pauer, F.; Unterkircher, A., Gröbner bases for ideals in Laurent polynomial rings and their application to systems of difference equations, Appl. Algebra Eng. Commun. Comput., 9, 4, 271-291 (1999) · Zbl 0978.13017 |
| [35] | Paule, P., Greatest factorial factorization and symbolic summation, J. Symb. Comput., 20, 3, 235-268 (1995) · Zbl 0854.68047 |
| [36] | Paule, P.; Riese, A., A Mathematica q-analogue of Zeilberger’s algorithm based on an algebraically motivated approach to \(q\)-hypergeometric telescoping, (Ismail, M.; Rahman, M., Special Functions, q-Series and Related Topics, vol. 14 (1997), AMS), 179-210 · Zbl 0869.33010 |
| [37] | Paule, P.; Schorn, M., A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, J. Symb. Comput., 20, 5-6, 673-698 (1995) · Zbl 0851.68052 |
| [38] | Petkovšek, M., Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symb. Comput., 14, 2-3, 243-264 (1992) · Zbl 0761.11008 |
| [39] | Petkovšek, M.; Wilf, H. S.; Zeilberger, D., \(A = B (1996)\), AK Peters: AK Peters Wellesley, MA · Zbl 0848.05002 |
| [40] | Petkovšek, M.; Zakrajšek, H., Solving linear recurrence equations with polynomial coefficients, (Schneider, C.; Blümlein, J., Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions. Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts Monogr. Symbol. Comput. (2013), Springer), 259-284 · Zbl 1312.65212 |
| [41] | van der Put, M.; Singer, M. F., Galois Theory of Difference Equations, Lect. Notes Math., vol. 1666 (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0930.12006 |
| [42] | Reutenauer, C., On a matrix representation for polynomially recursive sequences, Electron. J. Comb., 19, 3, 26 (2012), Paper 36 · Zbl 1298.05039 |
| [43] | Schneider, C., An implementation of Karr’s summation algorithm in mathematica, Sémin. Lothar. Comb., S43b, 1-10 (2000) · Zbl 0941.68162 |
| [44] | Schneider, C., Symbolic summation in difference fields (November 2001), J. Kepler University, PhD Thesis |
| [45] | Schneider, C., Symbolic summation with single-nested sum extensions, (Gutierrez, J., Proc. ISSAC’04 (2004), ACM Press), 282-289 · Zbl 1134.33329 |
| [46] | Schneider, C., Finding telescopers with minimal depth for indefinite nested sum and product expressions, (Kauers, M., Proc. ISSAC’05 (2005), ACM), 285-292 · Zbl 1360.68953 |
| [47] | Schneider, C., Product representations in ΠΣ-fields, Ann. Comb., 9, 1, 75-99 (2005) · Zbl 1123.33021 |
| [48] | Schneider, C., Solving parameterized linear difference equations in terms of indefinite nested sums and products, J. Differ. Equ. Appl., 11, 9, 799-821 (2005) · Zbl 1087.33011 |
| [49] | Schneider, C., Simplifying sums in ΠΣ-extensions, J. Algebra Appl., 6, 3, 415-441 (2007) · Zbl 1120.33023 |
| [50] | Schneider, C., Symbolic summation assists combinatorics, Sémin. Lothar. Comb., 56, 1-36 (2007), Article B56b · Zbl 1188.05001 |
| [51] | Schneider, C., A refined difference field theory for symbolic summation, J. Symb. Comput., 43, 9, 611-644 (2008) · Zbl 1147.33006 |
| [52] | Schneider, C., Parameterized telescoping proves algebraic independence of sums, Ann. Comb., 14, 533-552 (2010), for a preliminary version see FPSAC 2007 · Zbl 1232.33034 |
| [53] | Schneider, C., Structural theorems for symbolic summation, Appl. Algebra Eng. Commun. Comput., 21, 1, 1-32 (2010) · Zbl 1191.68891 |
| [54] | Schneider, C., A symbolic summation approach to find optimal nested sum representations, (Carey, A.; Ellwood, D.; Paycha, S.; Rosenberg, S., Motives, Quantum Field Theory, and Pseudodifferential Operators. Motives, Quantum Field Theory, and Pseudodifferential Operators, Clay Math. Proc., vol. 12 (2010), Amer. Math. Soc), 285-308 · Zbl 1225.33031 |
| [55] | Schneider, C., Simplifying multiple sums in difference fields, (Schneider, C.; Blümlein, J., Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions. Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts Monogr. Symbol. Comput. (2013), Springer), 325-360 · Zbl 1315.68294 |
| [56] | Schneider, C., A streamlined difference ring theory: indefinite nested sums, the alternating sign and the parameterized telescoping problem, (Winkler, Franz; Negru, Viorel; Ida, Tetsuo; Jebelean, Tudor; Petcu, Dana; Watt, Stephen; Zaharie, Daniela, Symbolic and Numeric Algorithms for Scientific Computing. Symbolic and Numeric Algorithms for Scientific Computing, SYNASC, 2014, 15th International Symposium (2014), IEEE Computer Society), 26-33 |
| [57] | Schneider, C., Fast algorithms for refined parameterized telescoping in difference fields, (Weimann, M.; Guitierrez, J.; Schicho, J., Computer Algebra and Polynomials. Computer Algebra and Polynomials, Lect. Notes Comput. Sci., vol. number 8942 (2015), Springer), 157-191 · Zbl 1434.39004 |
| [58] | Schneider, C., A difference ring theory for symbolic summation, J. Symb. Comput., 72, 82-127 (2016) · Zbl 1328.12015 |
| [59] | Singer, M. F., Algebraic and algorithmic aspects of linear difference equations, Galois theories of linear difference equations: an introduction, (Math. Surv. Monogr., vol. 211 (2016), AMS), chapter Algebraic and algorithmic aspects of linear difference equations · Zbl 1347.39002 |
| [60] | Vermaseren, J. A.M., Harmonic sums, Mellin transforms and integrals, Int. J. Mod. Phys. A, 14, 2037-2976 (1999) · Zbl 0939.65032 |
| [61] | Wegschaider, K., Computer generated proofs of binomial multi-sum identities (May 1997), RISC, J. Kepler University, Master’s thesis |
| [62] | Wilf, H.; Zeilberger, D., An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math., 108, 575-633 (1992) · Zbl 0739.05007 |
| [63] | Zeilberger, D., A holonomic systems approach to special functions identities, J. Comput. Appl. Math., 32, 321-368 (1990) · Zbl 0738.33001 |
| [64] | Zeilberger, D., The method of creative telescoping, J. Symb. Comput., 11, 195-204 (1991) · Zbl 0738.33002 |
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.
