More Web Proxy on the site http://driver.im/

research-article

Existence Problem of Telescopers: Beyond the Bivariate Case

Authors:

Rong-Hua WangAuthors Info & Claims

ISSAC '16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

Pages 167 - 174

https://doi.org/10.1145/2930889.2930895

Published: 20 July 2016 Publication History

Abstract

In this paper, we solve the existence problem of telescopers for rational functions in three discrete variables. We reduce the problem to that of deciding the summability of bivariate rational functions, a problem which has recently been solved. This existence criteria is used, for example, for detecting the termination of Zeilberger's algorithm to the function classes studied in this paper.

References

[1]

S. A. Abramov. The rational component of the solution of a first order linear recurrence relation with rational right hand side.v Z. Vy\v cisl. Mat. i Mat. Fiz., 15(4):1035--1039, 1090, 1975.

[2]

S. A. Abramov. Indefinite sums of rational functions. In Proc. of ISSAC '95, ACM Press, 303--308, 1995.

Digital Library

[3]

S. A. Abramov. When does Zeilberger's algorithm succeed? Adv. in Appl. Math., 30(3):424--441, 2003.

Digital Library

[4]

S. A. Abramov and Mark Van Hoeij. Integration of solutions of linear functional equations. Integral Transforms and Special Functions, 8(1--2):3--12, 1999.

[5]

S. A. Abramov and Ha Quang Le. A criterion for the applicability of Zeilberger's algorithm to rational functions. Discrete Math., 259(1--3):1--17, 2002.

Digital Library

[6]

S. A. Abramov, Ha Quang Le, and Ziming Li. Univariate Ore polynomial rings in computer algebra. Journal of Math. Sci., 131(5):5885--5903, 2005.

[7]

S. A. Abramov and Marko Petkovsek. On the structure of multivariate hypergeometric terms. Adv. Appl. Math., 29(3):386--411, 2002.

Digital Library

[8]

S. A. Abramov and Mark van Hoeij. A method for the integration of solutions of Ore equations. In Proceedings of ISSAC '97, ACM Press, 172--175, 1997.

Digital Library

[9]

G. E. Andrews and P. Paule. Some questions concerning computer-generated proofs of a binomial double-sum identity. J. Symbolic Comput., 16(2):147--151, August 1993.

Digital Library

[10]

B. Beckermann, H. Cheng and G. Labahn,Fraction-free Row Reduction of Matrices of Skew Polynomials, Proceedings of ISSAC'02, ACM Press, 8--15, 2002.

Digital Library

[11]

M. Bronstein and M. Petkov\vsek. An introduction to pseudo-linear algebra. Theoret. Comput. Sci., 157:3--33, 1996.

Digital Library

[12]

S. Chen, F. Chyzak, R. Feng, G. Fu, and Z. Li. On the existence of telescopers for mixed hypergeometric terms. J. Symbolic Comput., 68:1--26, 2015.

Digital Library

[13]

S. Chen and M. F. Singer. On the summability of bivariate rational functions. Journal of Algebra, 409:320 -- 343, 2014.

[14]

W. Y. C. Chen, Q. Hou, and Y. Mu. Applicability of the $q$-analogue of Zeilberger's algorithm. J. Symbolic Comput., 39(2):155--170, 2005.

Digital Library

[15]

W. Y. C. Chen, Q. Hou, and Y. Mu. A telescoping method for double summations. J. Comput. Appl. Math., 196(2):553--566, 2006.

Digital Library

[16]

F. Chyzak, M. Kauers, and B. Salvy. A non-holonomic systems approach to special function identities. In Proceedings of ISSAC'09, ACM Press, 111--118, 2009.

Digital Library

[17]

Z. Dvir, R. Mendes de Oliveira, and A. Shpilka. Testing equivalence of polynomials under shifts. In Automata, languages, and programming. Part I, volume 8572 of LNCS, pages 417--428. Springer, 2014.

[18]

R. W. Gosper, Jr. Decision procedure for indefinite hypergeometric summation. Proc. Nat. Acad. Sci. U.S.A., 75(1):40--42, 1978.

[19]

D. Grigoriev. Testing shift-equivalence of polynomials using quantum machines. In Proc. of ISSAC'96, ACM Press, 49--54, 1996.

Digital Library

[20]

D. Grigoriev. Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theoret. Comput. Sci., 180(1--2):217--228, 1997.

Digital Library

[21]

Q. Hou and R. Wang. An algorithm for deciding the summability of bivariate rational functions. Adv. in Appl. Math., 64:31 -- 49, 2015.

Digital Library

[22]

M. Karr. Summation in finite terms. J. Assoc. Comput. Mach., 28(2):305--350, 1981.

Digital Library

[23]

M. Karr. Theory of summation in finite terms. J. Symbolic Comput., 1(3):303--315, 1985.

Digital Library

[24]

P. Paule. Greatest factorial factorization and symbolic summation. J. Symbolic Comput., 20(3):235--268, 1995.

Digital Library

[25]

R. Pirastu. Algorithms for indefinite summation of rational functions in Maple. In MapleTech, pages 29--38, 1995.

[26]

C. Schneider. Symbolic Summation in Difference Fields. PhD thesis, J. Kepler University Linz, 2001.

[27]

H. S. Wilf and D. Zeilberger. An algorithmic proof theory for hypergeometric (ordinary and "q") multisum/integral identities. Invent. Math., 108(3):575--633, 1992.

[28]

D. Zeilberger. A fast algorithm for proving terminating hypergeometric identities. Discrete Math., 80(2):207--211, 1990.

Digital Library

[29]

D. Zeilberger. A holonomic systems approach to special functions identities. J. Comput. Appl. Math., 32:321--368, 1990.

Digital Library

Cited By

Chen SFeng RLi ZSinger MWatt S(2024)Telescopers for differential forms with one parameterSelecta Mathematica10.1007/s00029-024-00926-630:3Online publication date: 9-Mar-2024
https://doi.org/10.1007/s00029-024-00926-6
Arreche CZhang YMaza MZhi L(2022)Mahler Discrete Residues and Summability for Rational FunctionsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536186(525-533)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3536186
Chen SDavenport JWang DKauers MBradford R(2019)A Reduction Approach to Creative TelescopingProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326277(11-14)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326277
Show More Cited By

Index Terms

Existence Problem of Telescopers: Beyond the Bivariate Case
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Generating functions

Recommendations

Existence Problem of Telescopers for Rational Functions in Three Variables: the Mixed Cases
ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

We present criteria on the existence of telescopers for trivariate rational functions in four mixed cases, in which discrete and continuous variables appear simultaneously. We reduce the existence problem in the trivariate case to the exactness testing ...
Hermite reduction and creative telescoping for hyperexponential functions
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

We present a new reduction algorithm that simultaneously extends Hermite's reduction for rational functions and the Hermite-like reduction for hyperexponential functions. It yields a unique additive decomposition that allows to decide hyperexponential ...
A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms
ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

July 2016

434 pages

ISBN:9781450343800

DOI:10.1145/2930889

General Chairs:
Sergei Abramov
Russian Academy of Sciences, Russia
,
Eugene Zima
Wilfrid Laurier University, Canada
,
Program Chair:
Xiao-Shan Gao
Chinese Academy of Sciences, China

Copyright © 2016 ACM.

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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISSAC '16

Sponsor:

SIGSAM

ISSAC '16: International Symposium on Symbolic and Algebraic Computation

July 20 - 22, 2016

ON, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)2

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen SFeng RLi ZSinger MWatt S(2024)Telescopers for differential forms with one parameterSelecta Mathematica10.1007/s00029-024-00926-630:3Online publication date: 9-Mar-2024
https://doi.org/10.1007/s00029-024-00926-6
Arreche CZhang YMaza MZhi L(2022)Mahler Discrete Residues and Summability for Rational FunctionsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536186(525-533)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3536186
Chen SDavenport JWang DKauers MBradford R(2019)A Reduction Approach to Creative TelescopingProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326277(11-14)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326277
Giesbrecht MHuang HLabahn GZIma EDavenport JWang DKauers MBradford R(2019)Efficient Integer-Linear Decomposition of Multivariate PolynomialsProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326261(171-178)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326261
Chen SDu LZhu CDavenport JWang DKauers MBradford R(2019)Existence Problem of Telescopers for Rational Functions in Three VariablesProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326231(82-89)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326231
Chen S(2018)Bivariate Extensions of Abramov’s Algorithm for Rational SummationAdvances in Computer Algebra10.1007/978-3-319-73232-9_4(93-104)Online publication date: 26-Feb-2018
https://doi.org/10.1007/978-3-319-73232-9_4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten