We consider the additive decomposition problem in primitive towers and present an algorithm to decompose a function in a certain kind of primitive tower which we call S-primitive, as a sum of a derivative in the tower and a remainder which is minimal in some sense. Special instances of S-primitive towers include differential fields generated by finitely many logarithmic functions and logarithmic integrals. A function in an S-primitive tower is integrable in the tower if and only if the remainder is equal to zero. The additive decomposition is achieved by viewing our towers not as a traditional chain of extension fields, but rather as a direct sum of certain subrings. Furthermore, we can determine whether or not a function in an S-primitive tower has an elementary integral without the need to deal with differential equations explicitly. We also show that any logarithmic tower can be embedded into a particular extension where we can further decompose the given function. The extension is constructed using only differential field operations without introducing any new constants.
Hao Du, Austrian Academy of Sciences, RICAM, hao.du@ricam.oeaw.ac.at
Jing Guo, Chinese Academy of Sciences, KLMM, JingG@amss.ac.cn
Ziming Li, Chinese Academy of Sciences, KLMM, zmli@mmrc.iss.ac.cn
Elaine Wong, Austrian Academy of Sciences, RICAM, elaine.wong@ricam.oeaw.ac.at
Edit (July 2020):
This paper has been accepted to ISSAC 2020 with assigned DOI for the corresponding proceedings.
The preprint can be found at arXiv:2002.02355. Update: A more recent preprint can be found as a RICAM Report.
The appendix to our paper is here.
Edit (August 2020):
The Mathematica package AdditiveDecomposition.m (Version 0.2) is available for download.
The Mathematica notebook AdditiveDecomposition_Examples.nb contains some examples, including this collection, that illustrate the use of package (requires that the package and example file be stored in the same directory as the notebook).
For those without a Mathematica installation, we offer a pdf version of the example notebook for convenience.
S.A. Abramov. Indefinite sums of rational functions. Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 1995: 303-308.
A. Bostan, S. Chen, F. Chyzak and Z. Li. Complexity of creative telescoping for bivariate rational functions. Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2010: 203-210.
A. Bostan, S. Chen, F. Chyzak, Z. Li and G. Xin. Hermite reduction and creative telescoping for hyperexponential functions. Proceedings of the 2013 International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2013: 77-84.
A. Bostan, F. Chyzak, P. Lairez and B.Salvy. Generalized Hermite reduction, creative telescoping and definite integration of D-finite functions. Proceedings of the 2018 International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2018: 95-102.
M. Bronstein. Symbolic Integration I: transcendental functions. Berlin: Springer-Verlag, 2005.
S. Chen, H. Du and Z. Li. Additive decompositions in primitive extensions. Proceedings of the 2018 International Symposium on Symbolic and Algebraic Computation. New York, USA: ACM, 135-142.
S. Chen, M. van Hoeij, M. Kauers and C. Koutschan. Reduction-based creative telescoping for Fuchsian D-finite functions. Journal of Symbolic Computation, 2018, 85:108-127.
S. Chen, H. Huang, M. Kauers and Z. Li. A modified Abramov-Petkovšek reduction and creative telescoping for hypergeometric terms. Proceedings of the 2015 International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2015: 117-124.
S. Chen, M. Kauers and C. Koutschan. Reduction-based creative telescoping for algebraic functions. Proceedings of the 2016 International Symposium on Symbolic and Algebraic Computation. New York, NY, USA: ACM, 2016: 175-182.
D. Cox, J. Little, and D. O’Shea. Ideals, Varieties and Algorithms. Fourth Edition, Springer, 2015.
H. Du, H. Huang and Z. Li. A q-analogue of the modified Abramov-Petkovšek reduction. Advances in Computer Algebra. S. Schneider and C. Zima (eds.) Springer International Publishing, 2018: 105-129.
C. Hermite. Sur l’intégration des fractions rationnelles. Ann. Sci. École Norm. Sup.(2), 1872(1): 215-218.
M. V. Ostrogradsky. De l’intégration des fractions rationnelles. Bull. de la classe physico-mathématique de l’Acad. Impériale des Sciences de Saint-Pétersbourg, 1845, 4: 145-167, 286-300.
C. Raab. Definite Integration in Differential Fields. PhD thesis, RISC, Johannes Kepler University, Linz, Austria, 2012.
M. Singer, S. David and B. Caviness. An extension of Liouville’s theorem on integration in finite terms. SIAM J. Comput. 1985, 14: 966-990.
J. van der Hoeven. Constructing reductions for creative telescoping. AAECC. 2020.
O. Zariski and P. Samuel. Commutative Algebra I. Graduate Texts in Mathematics, Springer, 1975.