Top

Programming and Computer Software

Published in:

01-03-2020

Minimal Representations and Algebraic Relations for Single Nested Products

Author: Carsten Schneider

Published in: Programming and Computer Software | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recently, it has been shown constructively how a finite set of hypergeometric products, multibasic hypergeometric products or their mixed versions can be modeled properly in the setting of formal difference rings. Here special emphasis is put on robust constructions: whenever further products have to be considered, one can reuse –up to some mild modifications – the already existing difference ring. In this article we relax this robustness criteria and seek for another form of optimality. We will elaborate a general framework to represent a finite set of products in a formal difference ring where the number of transcendental product generators is minimal. As a bonus we are able to describe explicitly all relations among the given input products.

previous article Differential Geometry and Mechanics: A Source for Computer Algebra Problems

next article Computation of Involutive and Gröbner Bases Using the Tableau Representation of Polynomials

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

For \(1 \leqslant i \leqslant r\) we assume that \({{f}_{i}}(k) \ne 0\) for all \(k \in \mathbb{N} = {\text{\{ }}0,1,2, \ldots {\text{\} }}\) with \(k \geqslant {{l}_{i}}\).

We assume that \(\mathbb{F}\) can be embedded into the ring of sequences.

In this example the evaluation of an element from \(\mathbb{Q}(i)(x)\) is carried out by replacing x with concrete values \(n \in \mathbb{N}\). Later we will generalize this simplest case to formal difference rings equipped with an evaluation function acting on the ring elements.

More generally, if R is a commutative ring with 1, we define the ideal I generated by \({{a}_{1}}, \ldots ,{{a}_{r}} \in R\) with I = \({{\langle {{a}_{1}}, \ldots ,{{a}_{r}}\rangle }_{R}}\) = \({\text{\{ }}{{f}_{1}}{{a}_{1}} + \ldots + {{f}_{r}}{{a}_{r}}|{{f}_{1}}, \ldots ,{{f}_{r}} \in R{\text{\} }}\).

Throughout this article, all rings and fields have characteristic 0 and with \(\mathbb{A}{\text{*}}\) we denote the group of units. Furthermore, all rings are commutative. The order of \(a \in \mathbb{A}{\text{*}}\), denoted by \({\text{ord}}(a)\), is the smallest positive integer k with a^k = 1. If such a k does not exist, we set \({\text{ord}}(a) = 0\).

Note that \(\widehat {{\text{ev}}}({{\hat {x}}_{i}},n) \ne 0\) for all \(n \geqslant {{l}_{i}}\) by part (1) of Lemma 6.

To fulfill the property \({{f}_{i}} \in \mathbb{F}{\text{*}}\), the variables \({{q}_{1}} \ldots ,{{q}_{{v}}}\) and \({{y}_{1}}, \ldots ,{{y}_{{v}}}\) and the field below \(\mathbb{K}'\) have to be set up accordingly.

Note that generators \({{\hat {x}}_{i}}\) in \(\mathbb{E}\) represent products with no extra properties: in particular, all algebraic relations induced by their sequence evaluations are ignored.

Note that by Proposition 43 given below a difference ring generated by a finite set of R-monomials \(z_{1}^{'}, \ldots ,z_{l}^{'}\) is isomorphic to a difference ring generated by only one R-monomial z with ord(z) = \({\text{lcm}}({\text{ord}}(z_{1}^{'}), \ldots ,{\text{ord}}(z_{l}^{'})) = {\text{ord}}(z_{1}^{'}) \ldots {\text{ord}}(z_{l}^{'})\). Hence claiming that the order \(d = {\text{ord}}(z)\) is optimal means that among all solutions of Problem DR (\(\lambda \) need not to be surjective) in a difference ring with the A-monomials \(z_{1}^{'}, \ldots ,z_{l}^{'}\) the order d of z is smaller or equal to \({\text{ord}}(z_{1}^{'}) \ldots {\text{ord}}(z_{l}^{'})\).

In order to fit the specification in Problem DR, we set \({{t}_{1}}: = {{x}_{3}}\) and \({{t}_{2}}: = {{x}_{4}}\) and \({{z}_{1}}: = z\).

If the set R = {λ ∈ (const_σ\(\mathbb{F}\))* | λ^m = 1)} is contained in an algebraic number field, it is finite. In particular, if there is a primitive mth root of unity λ ∈ R, then R = {λⁱ | 0 ≤ i < m}.

Note that the quotient field of E is H. In particular, \((\mathbb{H},\sigma )\) is a sub-difference ring of \((\mathbb{E},\sigma )\).

If m is minimal with a^m ∈ \({{H}_{{(\mathbb{F},\sigma )}}}\), ρ is a primitive mth root of unity. In particular, if R is contained in an algebraic number field, we can choose any primitive mth root of unity λ ∈ \(\mathbb{K}{\text{*}}\) and can set λ_i = λⁱ and u = m to get R. Furthermore, one only has to loop through all i with ord(λⁱ) = m (i.e., with gcd(i, m) = 1) to discover ρ = λⁱ for some i.

In [18] this representation is also called σ-representation. Its existence can be derived from the statements (1) and (2) of Lemma 31.

The proof is based on Karr’s summation algorithm [18] and Ge’s algorithm [15]. For the rational and q-rational case we refer also to [5].

Note that F〈x〉 is a p.i.d. which implies this statement. For completeness we carry out the proof explicitly.

Since ord(\({{z}^{{{{d}_{u}} - {{\nu }_{i}}}}}\)) = d_i, it follows that \({{z}^{{{{d}_{u}} - {{\nu }_{i}}}}}\) = \({{z}^{{{{n}_{i}}\frac{{{{d}_{u}}}}{{{{d}_{i}}}}}}}\) for some n_i ∈ \(\mathbb{N}\) with 1 ≤ n_i < d and gcd(n_i, d_i) = 1.

Note that all the requirements of Assumption 28 except item (5) are needed.

For (63) we will require that m_i ≠ 0. Thus we allow m_i = ord(z_i) instead of m_i = 0.

So far it was sufficient in our applications to use the standard algorithm (see, e.g. [12]) based on column and row reductions to calculate the Smith Normal form for integer matrices. For faster algorithms we refer to [30,45]. For an excellent survey on the available strategies see also [14].

This means that the RΠ-extension \((\mathbb{H}',\sigma )\) of the difference field \((\mathbb{F},\sigma )\) has the form \(\mathbb{H}'\)=\(\mathbb{F}\langle {{y}_{1}}\rangle \ldots \langle {{y}_{e}}\rangle [{{z}_{1}}] \ldots [{{z}_{l}}]\) with \(\frac{{\sigma ({{y}_{i}})}}{{{{y}_{i}}}} \in \mathbb{F}\langle {{y}_{i}}\rangle \ldots \langle {{y}_{{i - 1}}}\rangle {\text{*}}\) for 1 ≤ i ≤ e and \(\frac{{\sigma ({{z}_{i}})}}{{{{z}_{i}}}} \in \mathbb{K}{\text{*}}\) for 1 ≤ i ≤ l.

Ablinger, J., Behring, A., Blümlein, J., Freitas, A.D., von Manteuffel, A., and Schneider, C., Calculating three loop ladder and V-topologies for massive operator matrix elements by computer algebra, Comput. Phys. Comm., 2016, vol. 202, pp. 33–112. arXiv:1509.08324 [hep-ph].

Ablinger, J., Blümlein, J., Freitas, A.D., Goedicke, A., Schneider, C., and Schönwald, K., The two-mass contribution to the three-loop gluonic operator matrix element \(A_{{gg,Q}}^{{(3)}}\), Nucl. Phys. B, 2018, vol. 932, pp. 129–240. arXiv:1804.02226 [hep-ph].

Abramov, S.A., On the summation of rational functions, Zh. Vychisl. Mat. Fiz., 1971, vol. 11, pp. 1071–1074.MathSciNetMATH

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., 1975, vol. 15, pp. 216–221.MathSciNetCrossRef

Abramov, S.A., Rational solutions of linear differential and difference equations with polynomial coefficients, USSR Comput. Math. Math. Phys., 1989, vol. 29, no. 6, pp. 7–12.MathSciNetCrossRef

Abramov, S.A. and Petkovšek, M., Polynomial ring automorphisms, rational \((w,\sigma )\)-canonical forms, and the assignment problem, J. Symb. Comput., 2010, vol. 45, no. 6, pp. 684–708.CrossRef

Apagodu M. and Zeilberger, D., Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Adv. Appl. Math., 2006, vol. 37, pp. 139–152.MathSciNetCrossRef

Bauer A. and Petkovšek, M., Multibasic and mixed hypergeometric Gosper-type algorithms, J. Symb. Comput., 1999, vol. 28, no. 4–5, pp. 711–736.MathSciNetCrossRef

Bronstein, M., On solutions of linear ordinary difference equations in their coefficient field, J. Symb. Comput., 2000, vol. 29, no. 6, pp. 841–877.MathSciNetCrossRef

10.

Chen, S. and Kauers, M., Order-degree curves for hypergeometric creative telescoping, in Proc. ISSAC 2012, van der Hoeven, J. and van Hoeij, M., Eds., 2012, pp. 122–129.

11.

Chyzak, F., An extension of Zeilberger’s fast algorithm to general holonomic functions, Discrete Math., 2000, vol. 217, pp. 115–134.MathSciNetCrossRef

12.

Cohn, P.M., Algebra, 2nd ed., John Wiley & Sons, 1989, vol. 2.MATH

13.

Cohn, R.M., Difference Algebra, John Wiley & Sons, 1965.MATH

14.

Elsheikh, M., Giesbrecht, M., Novocin, A., and Saunders, B.D., Fast computation of Smith forms of sparse matrices over local rings, in Proc. ISSAC 2012, New York: ACM, 2012, pp. 146–153.

15.

Ge, G., Algorithms related to the multiplicative representation of algebraic numbers, PhD Thesis, Univ. of California at Berkeley, 1993.

16.

Gosper, R.W., Decision procedures for indefinite hypergeometric summation, Proc. Nat. Acad. Sci. USA, 1978, vol. 75, pp. 40–42.MathSciNetCrossRef

17.

Hardouin, C. and Singer, M., Differential Galois theory of linear difference equations, Math. Ann., 2008, vol. 342, no. 2, pp. 333–377.MathSciNetCrossRef

18.

Karr, M., Summation in finite terms, J. ACM, 1981, vol. 28, pp. 305–350.MathSciNetCrossRef

19.

Karr, M., Theory of summation in finite terms, J. Symb. Comput., 1985, vol. 1, pp. 303–315.MathSciNetCrossRef

20.

Kauers, M. and Zimmermann, B., Computing the algebraic relations of c-finite sequences and multisequences, J. Symb. Comput., 2008, vol. 43, no. 11, pp. 787–803.MathSciNetCrossRef

21.

Koutschan, C., Creative telescoping for holonomic functions, in Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Schneider, C. and Blümlein, J., Eds., Springer, 2013, pp. 171–194. arXiv:1307.4554 [cs.SC].

22.

Nemes, I. and Paule, P., A canonical form guide to symbolic summation, in Advances in the Design of Symbolic Computation Systems, Miola, A. and Temperini, M., Eds., Wien-New York: Springer, 1997, pp. 84–110.MATH

23.

Ocansey, E.D. and Schneider, C. Representing (q-)hypergeometric products and mixed versions in difference rings, in Springer Proceedings in Mathematics and Statistics, vol 226: Advances in Computer Algebra. WWCA 2016, Schneider, C. and Zima, E., Eds., Springer, 2018, pp. 175–213.

24.

Ocansey, E.D., Difference ring algorithms for nested products, PhD Thesis, RISC, J. Kepler Univ., 2019.

25.

Paule, P., Greatest factorial factorization and symbolic summation, J. Symb. Comput., 1995, vol. 20, no. 3, pp. 235–268.MathSciNetCrossRef

26.

Paule, P. and Riese, A., A Mathematica q-analogue of Zeilberger’s algorithm based on an algebraically motivated approach to q-hypergeometric telescoping, in Special Functions, q-Series and Related Topics, Ismail, M. and Rahman, M., Eds., AMS, 1997, vol. 14, pp. 179–210.MATH

27.

Paule, P. and Schorn, M., A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, J. Symb. Comput., 1995, vol. 20, no. 5-6, pp. 673–698.MathSciNetCrossRef

28.

Petkovšek, M., Wilf, H.S., and Zeilberger, D., \(A = B\), Peters, A.K., Eds., Wellesley, MA, 1996.

29.

Chen, G.F.S., Feng, R., and Li, Z., On the structure of compatible rational functions, in Proc. ISSAC 2011, San Jose, 2011, pp. 91–98.

30.

Saunders, B.D. and Wan, Z., Smith normal form of dense integer matrices fast algorithms into practice, in Proc. ISSAC’04, Gutierrez, J., Ed., ACM Press, 2004, pp. 274–281.

31.

Schneider, C., Symbolic summation in difference fields, Technical Report 01-17, PhD Thesis, Linz: J. Kepler Univ., Nov. 2001.

32.

Schneider, C., Product representations in \(\Pi \Sigma \)-fields, Ann. Comb., 2005, vol. 9, no. 1, pp. 75–99.MathSciNetCrossRef

33.

Schneider, C., Simplifying sums in \(\Pi \Sigma \)-extensions, J. Algebra Appl., 2007, vol. 6, no. 3, pp. 415–441.MathSciNetCrossRef

34.

Schneider, C., Symbolic summation assists combinatorics, Sém. Lothar. Combin., 2007, vol. 56, pp. 1–36, Article B56b.

35.

Schneider, C., A refined difference field theory for symbolic summation, J. Symb. Comput., 2008, vol. 43, no. 9, pp. 611–644. arXiv:0808.2543v1.MathSciNetCrossRef

36.

Schneider, C., Parameterized telescoping proves algebraic independence of sums, Ann. Comb., 2010, vol. 14, pp. 533–552. arXiv:0808.2596.

37.

Schneider, C., Structural theorems for symbolic summation, Appl. Algebra Eng. Comm. Comput., 2010, vol. 21, no. 1, pp. 1–32.MathSciNetCrossRef

38.

Schneider, C., A symbolic summation approach to find optimal nested sum representations, in Clay Mathematics Proceedings, vol. 12: Motives, Quantum Field Theory, and Pseudodifferential Operators, Carey, A., Ellwood, D., Paycha, S., and Rosenberg, S., Eds., Am. Math. Soc., 2010, pp. 285–308. arXiv:0808.2543.

39.

Schneider, C., A streamlined difference ring theory: indefinite nested sums, the alternating sign and the parameterized telescoping problem, in Proc. 15th Int. Symp. on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Winkler, F., Negru, V., Ida, T., Jebelean, T., Petcu, D., Watt, S., and Zaharie, D., Eds., IEEE Computer Soc., 2014, pp. 26–33. arXiv:1412.2782v1 [cs.SC].

40.

Schneider, C., Fast algorithms for refined parameterized telescoping in difference fields, in Computer Algebra and Polynomials, Guitierrez, M.W.J. and Schicho, J., Eds., Springer, 2015, pp. 157–191. arXiv:1307.7887 [cs.SC].

41.

Schneider, C., A difference ring theory for symbolic summation, J. Symb. Comput., 2016, vol. 72, pp. 82–127. arXiv:1408.2776 [cs.SC].MathSciNetCrossRef

42.

Schneider, C., Summation theory II: characterizations of \(R\Pi \Sigma \)-extensions and algorithmic aspects, J. Symb. Comput., 2017, vol. 80, no. 3, pp. 616–664. arXiv:1603.04285 [cs.SC].

43.

Singer, M., Algebraic and algorithmic aspects of linear difference equations, in Mathematical Surveys and Monographs, vol. 211: Galois Theories of Linear Difference Equations: an Introduction, Hardouin, M.S.C. and Sauloy, J., Eds., AMS, 2016.

44.

van der Put, M. and Singer, M., Galois Theory of Difference Equations, Berlin: Springer-Verlag, 1997.CrossRef

45.

Eberly, P.G.A.S.W., Giesbrecht, M., and Villard, G., Faster inversion and other black box matrix computations using efficient block projections, in Proc. ISSAC’07, Brown, C., Ed., ACM Press, 2007, pp. 143–150.

46.

Wegschaider, K., Computer generated proofs of binomial multi-sum identities, Master’s Thesis, RISC, J. Kepler Univ., May 1997.

47.

Wilf, H. and Zeilberger, D., An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math., 1992, vol. 108, pp. 575–633.MathSciNetCrossRef

48.

Zeilberger, D., A holonomic systems approach to special functions identities, J. Comput. Appl. Math., 1990, vol. 32, pp. 321–368.MathSciNetCrossRef

49.

Zeilberger, D., The method of creative telescoping, J. Symb. Comput., 1991, vol. 11, pp. 195–204.MathSciNetCrossRef

Title: Minimal Representations and Algebraic Relations for Single Nested Products
Author: Carsten Schneider
Publication date: 01-03-2020
Publisher: Pleiades Publishing
Published in: Programming and Computer Software / Issue 2/2020
Print ISSN: 0361-7688
Electronic ISSN: 1608-3261
DOI: https://doi.org/10.1134/S0361768820020103

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2020

Normalization of a Periodic Hamiltonian System

Differential Geometry and Mechanics: A Source for Computer Algebra Problems

Computation of Involutive and Gröbner Bases Using the Tableau Representation of Polynomials

Procedures for Searching Laurent and Regular Solutions of Linear Differential Equations with the Coefficients in the Form of Truncated Power Series

On a Machine-Checked Proof for Fraction Arithmetic over a GCD Domain

A Modular Extension for a Computer Algebra System

Premium Partner