Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Irreducibility testing over local fields

Author: P. G. Walsh
Journal: Math. Comp. 69 (2000), 1183-1191
MSC (1991): Primary 12Y05, 12E05
Published electronically: March 2, 2000
MathSciNet review: 1710699
Full-text PDF

Abstract | References | Similar Articles | Additional Information


The purpose of this paper is to describe a method to determine whether a bivariate polynomial with rational coefficients is irreducible when regarded as an element in $\mathbf{Q}((x))[y]$, the ring of polynomials with coefficients from the field of Laurent series in $x$ with rational coefficients. This is achieved by computing certain associated Puiseux expansions, and as a result, a polynomial-time complexity bound for the number of bit operations required to perform this irreducibility test is computed.

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

  • 1. S. S. Abhyankar, Irreducibility criterion for germs of analytic functions of two complex variables, Adv. Math. 74 (1989), 190-257. MR 90h:32018
  • 2. G. A. Bliss, Algebraic functions, Amer. Math. Soc. Colloq. Publ. 16 (1933).
  • 3. A. L. Chistov, Polynomial complexity of the Newton-Puiseux algorithm, Lecture Notes in Computer Science 233 (1986), 247-255. CMP 19:07
  • 4. -, Efficient factoring polynomials over local fields and its applications, Proc. ICM 1990, (1991), 1509-1519. MR 93e:11152
  • 5. J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105-123. MR 41:3477
  • 6. D. L. Hilliker, An algorithm for computing the values of the ramification index in the Puiseux series expansions of an algebraic function, Pacific J. Math. 118, no. 2 (1985), 427-435. MR 86i:11068
  • 7. 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
  • 8. E. Kaltofen, ``Polynomial Factorization 1982-1986'', in Computers and Mathematics, Lecture Notes in Pure and Applied Mathematics 125 (1990), 285-309. MR 92f:12001
  • 9. -, ``Polynomial Factorization 1987-1991'', In Proceedings of Latin '92, Lecture Notes in Computer Science 583 (1992), 294-313.
  • 10. D. Knuth, The Art of Computer Programming, Vol. 2: 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. A. K. Lenstra, Factoring polynomials over algebraic number fields, Proc. EuroCal. 1983, Lecture Notes in Computer Science 162 (1983), 245-254. MR 86g:12001b
  • 14. -, Factoring multivariate integral polynomials, Theoret. Comp. Sci. 34 (1984), 207-213. MR 86g:12001a
  • 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. V. Puiseux, Recherches sur les fonctions algébriques, J. Math. Pures Appl. 15 (1850), 365-480.
  • 17. B. M. Trager, Algebraic factoring and rational function integration, Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, 219-226.
  • 18. R. J. Walker, Algebraic Curves, Princeton University Press, Princeton, New Jersey, 1950. MR 11:387e
  • 19. P. G. Walsh, A quantitative version of Runge's theorem on diophantine equations, Acta Arith. 62 (1992), 157-172. MR 94a:11037
  • 20. -, The Computation of Puiseux Expansions and Runge's Theorem on Diophantine Equations, Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada, 1994.
  • 21. -, A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function, Math. Comp., Posted on February 16, 2000, PII S0025-5718(00)01246-1

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 12Y05, 12E05

Retrieve articles in all journals with MSC (1991): 12Y05, 12E05

Additional Information

P. G. Walsh
Affiliation: Department of Mathematics, University of Ottawa, Ontario, Canada

Keywords: Algebraic function, Puiseux expansion, irreducibility testing, computational complexity, local field
Received by editor(s): September 5, 1994
Received by editor(s) in revised form: June 12, 1995
Published electronically: March 2, 2000
Additional Notes: This work constitutes part of the author’s doctoral dissertation at the University of Waterloo
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society