Mathematics of Computation

Author(s): P. G. Walsh.
Journal: Math. Comp. 69 (2000), 1183-1191.
MSC (1991): Primary 12Y05, 12E05
Posted: March 2, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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

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.

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

P. G. Walsh
Affiliation: Department of Mathematics, University of Ottawa, Ontario, Canada
Email: gwalsh@mathstat.uottawa.ca

DOI: 10.1090/S0025-5718-00-01247-3
PII: S 0025-5718(00)01247-3
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
Posted: March 2, 2000
Additional Notes: This work constitutes part of the author's doctoral dissertation at the University of Waterloo
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