Mathematics of Computation

A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function

Author(s): P. G. Walsh.
Journal: Math. Comp. 69 (2000), 1167-1182.
MSC (1991): Primary 14H05, 11Y15
Posted: February 16, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

In this paper we present a refined version of the Newton polygon process to compute the Puiseux expansions of an algebraic function defined over the rational function field. We determine an upper bound for the bit-complexity of computing the singular part of a Puiseux expansion by this algorithm, and use a recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions to show that this computational complexity is polynomial in the degrees and the logarithm of the height of the polynomial defining the algebraic function.

1.: G. A. Bliss, Algebraic Functions, Amer. Math. Soc. Colloq. Publ. 16 (1933).
2.: W. S. Brown, On Euclid's algorithm and the computation of polynomial greatest common divisors, J. Assoc. Comput. Mach., 18 (1971), 478-504. MR 46:6570
3.: A. L. Chistov, Polynomial complexity of the Newton-Puiseux algorithm, Lecture Notes in Computer Sciences, 233 (1986), 247-255. CMP 19:07
4.: D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series I, J. Complexity, 2 (1986), 271-294. MR 90d:68031a
5.: -, On expansion of algebraic functions in power and Puiseux series II, J. Complexity, 3 (1987), 1-25. MR 90d:68031b
6.: J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105-123. MR 41:3477
7.: D. Duval, Rational Puiseux expansions, Compositio Math. 70 (1989), 119-154. MR 90c:14001
8.: B. M. Dwork and A. J. van der Poorten, The Eisenstein constant, Duke Math. J. 65, no. 1 (1992), 23-43. MR 93c:12010
9.: D. L. Hilliker and E. G. Straus, Determination of bounds for the solutions to those binary diophantine equations that satisfy the hypotheses of Runge's theorem, Trans. Amer. Math. Soc. 280 (1983), 637-657. MR 85c:11031
10.: D. Knuth, The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1969. MR 44:3531
11.: H. T. Kung and J. F. Traub, All algebraic functions can be computed fast, J. Assoc. Comput. Mach. 25 (1978), 246-260. MR 80a:68042
12.: S. Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14, no. 1 (1985), 184-195. MR 86d:11102
13.: L. Langemyr, An analysis of the subresultant algorithm over an algebraic number field, Proceedings of ISSAC `91, ACM Press, 1991, 167-172.
14.: A. K. Lenstra, Factoring polynomials over algebraic number fields, Proc. EuroCal. 1983, Lecture Notes in Computer Science, 162 (1983), 245-254. MR 86d:12001b
15.: A. K. Lenstra, H. W. Lenstra Jr., and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. MR 84a:12002
16.: R. Loos, Computing in algebraic extensions, in Computer Algebra, 2nd ed., edited by B. Buchberger et. al., Springer-Verlag, New York, 1982, 173-187. CMP 16:06
17.: V. Puiseux, Recherches sur les fonctions algébriques, J. Math. Pures Appl. 15 (1850), 365-480.
18.: W. M. Schmidt, Eisenstein's theorem on power series expansions of algebraic functions, Acta Arith. 56 (1990), 161-179. MR 91m:11021
19.: J. T. Schwartz and M. Sharir, On the piano mover's problem: III, in Planning, Geometry, and Complexity of Robot Motion, edited by J. T. Schwartz, M. Sharir, and J. Hopcroft, Ablex, New York, 1987. MR 86a:52016
20.: B. M. Trager, Algebraic factoring and rational function integration, Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, 219-226.
21.: B. L. van der Waerden, Modern Algebra, Frederick Ungar, 7th ed., New York, 1970. MR 10:587b
22.: R. J. Walker, Algebraic Curves, Princeton University Press, Princeton, New Jersey, 1950. MR 11:387e
23.: P. G. Walsh, The Computation of Puiseux Expansions and Runge's Theorem on Diophantine Equations, Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada, 1993.

P. G. Walsh
Affiliation: Department of Mathematics, University of Ottawa, 585 King Edward, Ottawa, Ontario, Canada KIN 6N5
Email: gwalsh@mathstat.uottawa.ca

DOI: 10.1090/S0025-5718-00-01246-1
PII: S 0025-5718(00)01246-1
Keywords: Algebraic function, Puiseux expansion, Newton polygon, complexity.
Received by editor(s): May 28, 1994
Received by editor(s) in revised form: March 21, 1995 and June 5, 1996
Posted: February 16, 2000
Additional Notes: This work constitutes part of the author's doctoral dissertation from the University of Waterloo.
Dedicated: Dedicated to Wolfgang Schmidt on the occasion of his sixtieth birthday.
Copyright of article: Copyright 2000, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS