Hypergeometric dispersion and the orbit problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Hypergeometric dispersion and the orbit problem

Full text

Pdf (177 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 2000 international symposium on Symbolic and algebraic computation table of contents

St. Andrews, Scotland

Pages: 8 - 13

Year of Publication: 2000

ISBN:1-58113-218-2

Authors

Sergei A. Abramov	Computer Center of the Russian Academy of Science, Vavilova 40, Moscow 117967, Russia
Manuel Bronstein	INRIA - Projet Cafe, 2004, Route des Lucioles, B.P. 93, F-06902 Sophia Antipolis Cedex, France

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 5, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/345542.345561 What is a DOI?

ABSTRACT

We describe an algorithm for finding the positive integer solutions n of orbit problems of the form &agr;n = &bgr; where &agr; and &bgr; are given elements of a field K. Our algorithm corrects the bounds given in [7], and shows that the problem is not polynomial in the Euclidean norms of the polynomials involved. Combined with a simplified version of the algorithm of [8] for the “specification of equivalence”, this yields a complete algorithm for computing the dispersion of polynomials in nested hypergeometric extensions of rational function fields. This is a necessary step in computing symbolic sums, or solving difference equations, with coefficients in such fields. We also solve the related equations p(&agr;n) = 0 and p(n, &agr;n) = 0 where p is a given polynomial and &agr; is given.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. A. Abramov. On the summation of rational functions. USSR Computational Mathematics and Mathematical Physics, 11:324-330, 1971.
	2	S. A. Abramov. Complexity of the solution of exponential equation and the orbit problem for second-order matrices. Moscow University Computational Mathematics and Cybernetics, 4:55-63, 1987.
	3	S. A. Abramov. Rational solutions of linear difference and q-difference equations with polynomial coefficients. Programming and Computer Software, 21:273-278, 1995.
	4	P. Blanksby and H. Montgomery. Algebraic integers near the unit circle. Acta Arithmetica, 18:355-369, 971.
	5	Manuel Bronstein, On solutions of linear ordinary difference equations in their coefficient field, Journal of Symbolic Computation, v.29 n.6, p.841-877, June 2000 [doi>10.1006/jsco.2000.0368 ]
	6	Michael A. Harrison, Lectures on Linear Sequential Machines, Academic Press, Inc., Orlando, FL, 1969
	7	R. Kannan , R. J. Lipton, Polynomial-time algorithm for the orbit problem, Journal of the ACM (JACM), v.33 n.4, p.808-821, Oct. 1986 [doi>10.1145/6490.6496]
	8	Michael Karr, Summation in Finite Terms, Journal of the ACM (JACM), v.28 n.2, p.305-350, April 1981 [doi>10.1145/322248.322255]
	9	M Karr, Theory of summation in finite terms, Journal of Symbolic Computation, v.1 n.3, p.303-315, September 1985 [doi>10.1016/S0747-7171(85)80038-9]
	10	N. Osipov. On the simplification of nested real radicals. Programming and Computer Software, 23:142-146, 1997.
	11	H. Shank. The rational case of a matrix problem of Harrison. Discrete Mathematics, 28:207-212, 1979.

CITED BY 4

	S. A. Abramov , H. Q. Le , M. Petkovšek, Rational canonical forms and efficient representations of hypergeometric terms, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.7-14, August 03-06, 2003, Philadelphia, PA, USA
	Sergei A. Abramov , Manuel Bronstein, On solutions of linear functional systems, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.1-6, July 2001, London, Ontario, Canada
	S. A. Abramov, A direct algorithm to compute rational solutions of first order linear q-difference systems, Discrete Mathematics, v.246 n.1-3, p.3-12, 6 March 2002
	S. P. Tsarev, On the rational summation problem, Programming and Computing Software, v.31 n.2, p.56-59, March 2005