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

Author:
P. G. Walsh

Journal:
Math. Comp. **69** (2000), 1167-1182

MSC (1991):
Primary 14H05, 11Y15

DOI:
https://doi.org/10.1090/S0025-5718-00-01246-1

Published electronically:
February 16, 2000

MathSciNet review:
1710624

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
14H05,
11Y15

Retrieve articles in all journals with MSC (1991): 14H05, 11Y15

Additional Information

**P. G. Walsh**

Affiliation:
Department of Mathematics, University of Ottawa, 585 King Edward, Ottawa, Ontario, Canada KIN 6N5

Email:
gwalsh@mathstat.uottawa.ca

DOI:
https://doi.org/10.1090/S0025-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

Published electronically:
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.

Article copyright:
© Copyright 2000
American Mathematical Society