Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

References [Enhancements On Off] (What's this?)

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

Similar Articles

Retrieve articles in Mathematics of Computation 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

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

American Mathematical Society