skip to main content
10.1145/2755996.2756648acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms

Published: 24 June 2015 Publication History

Abstract

The Abramov-Petkovsek reduction computes an additive decomposition of a hypergeometric term,which extends the functionality of the Gosper algorithm for indefinite hypergeometric summation. We modify the Abramov-Petkovsek reduction so as to decompose a hypergeometric term as the sum of a summable term and a non-summable one. The outputs of the Abramov-Petkovsek reduction and our modified version share the same required properties. The modified reduction does not solve any auxiliary linear difference equation explicitly. It is also more efficient than the original reduction according to computational experiments. Based on this reduction, we design a new algorithm to compute minimal telescopers for bivariate hypergeometric terms. The new algorithm can avoid the costly computation of certificates.

References

[1]
S. A. Abramov. The rational component of the solution of a first-order linear recurrence relation with a rational right side. USSR Comp. Math. Math. Phys., 15(4):216--221, 1975.
[2]
S. A. Abramov. When does Zeilberger's algorithm succeed? Adv. in Appl. Math., 30(3):424--441, 2003.
[3]
S. A. Abramov and M. PetkovekšMinimal decomposition of indefinite hypergeometric sums. In Proc. of ISSAC'01, pp. 7--14, 2001. ACM.
[4]
S. A. Abramov and M. Petkovšek. Rational normal forms and minimal decompositions of hypergeometric terms. J. Symbolic Comput., 33(5):521--543, 2002.
[5]
G. Almkvist and D. Zeilberger. The method of differentiating under the integral sign. J. Symbolic Comput., 10:571--591, 1990.
[6]
M. Apagodu and D. Zeilberger. Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory. Adv. in Appl. Math., 37(2):139--152, 2006.
[7]
A. Bostan, S. Chen, F. Chyzak, and Z. Li. Complexity of creative telescoping for bivariate rational functions. In Proc. of ISSAC '10, pp. 203--210, 2010. ACM.
[8]
A. Bostan, S. Chen, F. Chyzak, Z. Li, and G. Xin. Hermite reduction and creative telescoping for hyperexponential functions. In Proc. of ISSAC'13, pp. 77--84, 2013. ACM.
[9]
A. Bostan, P. Lairez, and B. Salvy. Creative telescoping for rational functions using the Griffith-Dwork method. In Proc. of ISSAC'13, pp. 93--100, 2013. ACM.
[10]
S. Chen. Some applications of differential-difference algebra to creative telescoping. PhD thesis, École Polytechnique, Palaiseau, 2011.
[11]
S. Chen and M. Kauers. Order-degree curves for hypergeometric creative telescoping. In Proc. of ISSAC'12, pp. 122--129, 2012. ACM.
[12]
S. Chen and M. Kauers. Trading order for degree in creative telescoping. J. Symbolic Comput., 47(8):968--995, 2012.
[13]
S. Chen, M. Kauers, and C. Koutschan. A generalized Apagodu-Zeilberger algorithm. In Proc. of ISSAC'14, pp. 107--114, 2014. ACM.
[14]
F. Chyzak and B. Salvy. Non-commutative elimination in Ore algebras proves multivariate identities. J. Symbolic Comput., 26:187--227, 1998.
[15]
M. C. Fasenmyer. Some generalized hypergeometric polynomials. Bull. Amer. Math. Soc., 53:806--812, 1947.
[16]
R. W. Gosper, Jr. Decision procedure for indefinite hypergeometric summation. Proc. Nat. Acad. Sci. U.S.A., 75(1):40--42, 1978.
[17]
M. Mohammed and D. Zeilberger. Sharp upper bounds for the orders of the recurrences output by the Zeilberger and q-Zeilberger algorithms. J. Symbolic Comput., 39(2):201--207, 2005.
[18]
O. Ore. Sur la forme des fonctions hyperg' eométriques de plusieurs variables. J. Math. Pures Appl. (9), 9(4):311--326, 1930.
[19]
M. Petkovšek, H. S. Wilf, and D. Zeilberger. A=B. A K Peters Ltd., Wellesley, MA, 1996.
[20]
M. Sato. Theory of prehomogeneous vector spaces (algebraic part). Nagoya Math. J., 120:1--34, 1990.
[21]
D. Zeilberger. A fast algorithm for proving terminating hypergeometric identities. Discrete Math., 80:207--211, 1990.
[22]
D. Zeilberger. A holonomic systems approach to special functions identities. J. Comput. Appl. Math., 32:321--368, 1990.
[23]
D. Zeilberger. The method of creative telescoping. J. Symbolic Comput., 11:195--204, 1991.

Cited By

View all
  • (2025)On the Existence of Telescopers for P-recursive SequencesJournal of Symbolic Computation10.1016/j.jsc.2025.102423(102423)Online publication date: Jan-2025
  • (2024)Power-partible reduction and congruences for Apéry numbersInternational Journal of Number Theory10.1142/S179304212550002221:01(23-34)Online publication date: 14-Aug-2024
  • (2023)Hermite Reduction for D-finite Functions via Integral BasesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597092(155-163)Online publication date: 24-Jul-2023
  • Show More Cited By

Index Terms

  1. A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation
    June 2015
    374 pages
    ISBN:9781450334358
    DOI:10.1145/2755996
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 24 June 2015

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. abramov-petkovsek reduction
    2. hypergeometric term
    3. summability
    4. telescoper

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    ISSAC'15
    Sponsor:

    Acceptance Rates

    ISSAC '15 Paper Acceptance Rate 43 of 71 submissions, 61%;
    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)6
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 10 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media