Irreducibility testing over local fields

Walsh, P.

doi:10.1090/S0025-5718-00-01247-3

Irreducibility testing over local fields
HTML articles powered by AMS MathViewer

by P. G. Walsh PDF

Math. Comp. 69 (2000), 1183-1191 Request permission

Abstract:

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

Shreeram S. Abhyankar, Irreducibility criterion for germs of analytic functions of two complex variables, Adv. Math. 74 (1989), no. 2, 190–257. MR 997097, DOI 10.1016/0001-8708(89)90009-1
G. A. Bliss, Algebraic functions, Amer. Math. Soc. Colloq. Publ. 16 (1933).
A. L. Chistov, Polynomial complexity of the Newton-Puiseux algorithm, Lecture Notes in Computer Science 233 (1986), 247–255.
Alexandre L. Chistov, Efficient factoring polynomials over local fields and its applications, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990) Math. Soc. Japan, Tokyo, 1991, pp. 1509–1519. MR 1159333
J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105–123. MR 258831, DOI 10.1017/s0305004100001110
David Lee Hilliker, An algorithm for computing the values of the ramification index in the Puiseux series expansions of an algebraic function, Pacific J. Math. 118 (1985), no. 2, 427–435. MR 789182
David Lee 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), no. 2, 637–657. MR 716842, DOI 10.1090/S0002-9947-1983-0716842-3
Erich Kaltofen, Polynomial factorization 1982–1986, Computers in mathematics (Stanford, CA, 1986) Lecture Notes in Pure and Appl. Math., vol. 125, Dekker, New York, 1990, pp. 285–309. MR 1068540
—, “Polynomial Factorization 1987–1991”, In Proceedings of Latin ’92, Lecture Notes in Computer Science 583 (1992), 294–313.
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
H. T. Kung and J. F. Traub, All algebraic functions can be computed fast, J. Assoc. Comput. Mach. 25 (1978), no. 2, 245–260. MR 488306, DOI 10.1145/322063.322068
Susan Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), no. 1, 184–195. MR 774938, DOI 10.1137/0214015
A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-8
A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-8
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
V. Puiseux, Recherches sur les fonctions algébriques, J. Math. Pures Appl. 15 (1850), 365–480.
B. M. Trager, Algebraic factoring and rational function integration, Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, 219–226.
Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
P. G. Walsh, A quantitative version of Runge’s theorem on Diophantine equations, Acta Arith. 62 (1992), no. 2, 157–172. MR 1183987, DOI 10.4064/aa-62-2-157-172
—, The Computation of Puiseux Expansions and Runge’s Theorem on Diophantine Equations, Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada, 1994.
—, 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 S 0025-5718(00)01246-1