×

A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function. (English) Zbl 1042.14039

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

MSC:

14Q05 Computational aspects of algebraic curves
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. A. Bliss, Algebraic Functions, Amer. Math. Soc. Colloq. Publ. 16 (1933). · Zbl 0008.21004
[2] W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. Assoc. Comput. Mach. 18 (1971), 478 – 504. · Zbl 0226.65040 · doi:10.1145/321662.321664
[3] A. L. Chistov, Polynomial complexity of the Newton-Puiseux algorithm, Lecture Notes in Computer Sciences, 233 (1986), 247-255. CMP 19:07 · Zbl 0636.65043
[4] D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series. I, J. Complexity 2 (1986), no. 4, 271 – 294. , https://doi.org/10.1016/0885-064X(86)90006-3 D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series. II, J. Complexity 3 (1987), no. 1, 1 – 25. · Zbl 0656.34003 · doi:10.1016/0885-064X(87)90002-1
[5] D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series. I, J. Complexity 2 (1986), no. 4, 271 – 294. , https://doi.org/10.1016/0885-064X(86)90006-3 D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series. II, J. Complexity 3 (1987), no. 1, 1 – 25. · Zbl 0656.34003 · doi:10.1016/0885-064X(87)90002-1
[6] J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105 – 123. · Zbl 0215.37302
[7] Dominique Duval, Rational Puiseux expansions, Compositio Math. 70 (1989), no. 2, 119 – 154. · Zbl 0699.14034
[8] Bernard M. Dwork and Alfred J. van der Poorten, The Eisenstein constant, Duke Math. J. 65 (1992), no. 1, 23 – 43. · Zbl 0770.11051 · doi:10.1215/S0012-7094-92-06502-1
[9] 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. · Zbl 0528.10011
[10] Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. · Zbl 0191.18001
[11] H. T. Kung and J. F. Traub, All algebraic functions can be computed fast, J. Assoc. Comput. Mach. 25 (1978), no. 2, 245 – 260. · Zbl 0371.68019 · doi:10.1145/322063.322068
[12] Susan Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), no. 1, 184 – 195. · Zbl 0565.12002 · doi:10.1137/0214015
[13] L. Langemyr, An analysis of the subresultant algorithm over an algebraic number field, Proceedings of ISSAC ‘91, ACM Press, 1991, 167-172. · Zbl 1019.11507
[14] A. K. Lenstra, Factoring polynomials over algebraic number fields, Proc. EuroCal. 1983, Lecture Notes in Computer Science, 162 (1983), 245-254. · Zbl 0539.68030
[15] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515 – 534. · Zbl 0488.12001 · doi:10.1007/BF01457454
[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] Wolfgang M. Schmidt, Eisenstein’s theorem on power series expansions of algebraic functions, Acta Arith. 56 (1990), no. 2, 161 – 179. · Zbl 0659.12003
[19] Jacob T. Schwartz and Micha Sharir, On the piano movers’ problem. III. Coordinating the motion of several independent bodies: the special case of circular bodies moving amidst polygonal barriers, Internat. J. Robotics Res. 2 (1983), no. 3, 46 – 75. · Zbl 0592.51011 · doi:10.1177/027836498300200304
[20] B. M. Trager, Algebraic factoring and rational function integration, Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, 219-226. · Zbl 0498.12005
[21] B. L. van der Waerden, Modern Algebra, Frederick Ungar, 7th ed., New York, 1970.
[22] R. J. Walker, Algebraic Curves, Princeton University Press, Princeton, New Jersey, 1950. · Zbl 0039.37701
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.