Top

Applicable Algebra in Engineering, Communication and Computing

30-11-2024 | Original Paper

Plane curve germs and contact factorization

Authors: Joris van der Hoeven, Grégoire Lecerf

Published in: Applicable Algebra in Engineering, Communication and Computing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Given an algebraic germ of a plane curve at the origin, in terms of a bivariate polynomial, we analyze the complexity of computing an irreducible decomposition up to any given truncation order. With a suitable representation of the irreducible components, and whenever the characteristic of the ground field is zero or larger than the degree of the germ, we design a new algorithm that involves a nearly linear number of arithmetic operations in the ground field plus a small amount of irreducible univariate polynomial factorizations.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Abelard, S., Berardini, E., Couvreur, A., Lecerf, G.: Computing Riemann–Roch spaces via Puiseux expansions. J. Complex. 73, 101666 (2022)MathSciNetCrossRef

Abhyankar, S.S.: Irreducibility criterion for germs of analytic functions of two complex variables. Adv. Math. 74(2), 190–257 (1989)MathSciNetCrossRef

Abhyankar, S.S., Moh, T.: Newton-Puiseux expansion and generalized Tschirnhausen transformation. I. J. Reine Angew. Math. 260, 47–83 (1973)MathSciNet

Abhyankar, S.S., Moh, T.: Newton-Puiseux expansion and generalized Tschrinhausen transformation. II. J. Reine Angew. Math. 261, 29–54 (1973)

Alberich-Carramiñana, M., Guàrdia, J., Nart, E., Poteaux, A., Roé, J., Weimann, M.: Polynomial factorization over henselian fields. Found. Comput. Math. (2024). https://doi.org/10.1007/s10208-024-09646-xCrossRef

Alonso, M.E., Castro-Jiménez, F.J., Hauser, H.: Encoding algebraic power series. J. Found. Comput. Math. 18(3), 789–833 (2018)MathSciNetCrossRef

Aschenbrenner, M., van den Dries, L., van der Hoeven, J.: Asymptotic Differential Algebra and Model Theory of Transseries Number 195 in Annals of Mathematics studies. Princeton University Press, New Jersey (2017)

Bauch, J.-D., Nart, E., Stainsby, H.D.: Complexity of OM factorizations of polynomials over local fields. LMS J. Comput. Math. 16, 139–171 (2013)MathSciNetCrossRef

Berthomieu, J., Lecerf, G., Quintin, G.: Polynomial root finding over local rings and application to error correcting codes. Appl. Algebra Engrg. Comm. Comput. 24(6), 413–443 (2013)MathSciNetCrossRef

10.

Bostan, A., Christol, G., Dumas, Ph.: Fast computation of the Nth term of an algebraic series over a finite prime field. In: Rosenkranz, M. (ed.), Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pp. 119–126. ACM, New York, NY, USA, (2016)

11.

Bostan, A., Chyzak, F., Lecerf, G., Salvy, B., Schost, É.: Differential equations for algebraic functions. In: Brown, C.W. (ed.) Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, ISSAC ’07. ACM, New York, NY, USA, (2007)

12.

Bostan, A., Lecerf, G., Salvy, B., Schost, É., Wiebelt, B.: Complexity issues in bivariate polynomial factorization. In: Schicho, J. (ed.) Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC ’04, pp. 42–49, ACM Press. New York, NY, USA, (2004)

13.

Campillo, A., Farrán, J.I.: Symbolic Hamburger–Noether expressions of plane curves and applications to AG codes. Math. Comp. 71(240), 1759–1780 (2002)MathSciNetCrossRef

14.

Cantor, D.G., Gordon, D.M.: Factoring polynomials over \(p\)-adic fields. In: Bosma, W. (ed.) Algorithmic Number Theory. 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000. Proceedings, volume 1838 of Lecture Notes in Comput. Sci., pp. 185–208. Springer-Verlag, (2000)

15.

Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inf. 28, 693–701 (1991)MathSciNetCrossRef

16.

Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587–592 (1981)MathSciNetCrossRef

17.

Chistov, A.L.: Polynomial complexity of the Newton–Puiseux algorithm. In: Mathematical Foundations of Computer Science 1986. Proceedings of the 12th Symposium Bratislava, Czechoslovakia August 25–29, 1986, volume 233 of Lecture Notes in Comput. Sci., pp. 247–255. Springer-Verlag, (1986)

18.

Chistov, A.L.: Efficient factoring polynomials over local fields and its applications. In: Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990, vol. 1, pp. 1509–1519. Springer-Verlag, (1991)

19.

Chudnovsky, D.V., Chudnovsky, G.V.: On expansion of algebraic functions in power and Puiseux series. I. J. Complex. 2(4), 271–294 (1986)MathSciNetCrossRef

20.

Chudnovsky, D.V., Chudnovsky, G.V.: On expansion of algebraic functions in power and Puiseux series. II. J. Complex. 3(1), 1–25 (1987)MathSciNetCrossRef

21.

Cohen, H.: A course in computational algebraic number theory. Graduate Texts in Mathematics. Springer, Berlin, Heidelberg (1993)CrossRef

22.

Cossart, V., Moreno-Socías, G.: Racines approchées, suites génératrices, suffisance des jets. Annales de la Faculté des sciences de Toulouse \(6_{e}\) série, 14(3):353–394, (2005)

23.

Duval, D.: Rational Puiseux expansions. Compos. Math. 70(2), 119–154 (1989)MathSciNet

24.

Dwivedi, A., Saxena, N.: Computing Igusa’s local zeta function of univariates in deterministic polynomial-time. In: Galbraith, S.D. (ed.) ANTS XIV. Proceedings of the Fourteenth Algorithmic Number Theory Symposium, volume 4 of The Open Book Series, pp. 197–214. MSP, Berkeley, CA, USA (2020)

25.

Fernández, J., Guàrdia, J., Montes, J., Nart, E.: Residual ideals of MacLane valuations. J. Algebra 427, 30–75 (2015)MathSciNetCrossRef

26.

Ford, D., Letard, P.: Implementing the Round Four maximal order algorithm. J. Théor. Nombres Bordeaux 6(1), 39–80 (1994)MathSciNetCrossRef

27.

Ford, D., Pauli, S., Roblot, X.-F.: A fast algorithm for polynomial factorization over \({\mathbb{Q} }_p\). J. Théor. Nombres Bordeaux 14(1), 151–169 (2002)MathSciNetCrossRef

28.

Ford, D., Veres, O.: On the complexity of the Montes ideal factorization algorithm. In: Hanrot, G., Morain, F., Thomé, E. (eds.), Algorithmic Number Theory. 9th International Symposium, ANTS-IX, Nancy, France, July 19-23, 2010. Proceedings, volume 6197 of Lecture Notes in Comput. Sci., pp. 174–185. Springer-Verlag, (2010)

29.

Fröhlich, A., Shepherdson, J.C.: On the factorisation of polynomials in a finite number of steps. Math. Z. 62, 331–334 (1955)MathSciNetCrossRef

30.

Fröhlich, A., Shepherdson, J.C.: Effective procedures in field theory. Philos. Trans. R. Soc. Lond. Ser. A. 248, 407–432 (1956)MathSciNetCrossRef

31.

von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. 3rd edn., Cambridge University Press, New York (2013)

32.

von Gathen, J., Shoup, V.: Computing Frobenius maps and factoring polynomials. Comput. Complex. 2(3), 187–224 (1992)MathSciNetCrossRef

33.

Greuel, G.-M., Pfister, G.: A Singular Introduction to Commutative Algebra. Springer-Verlag, Berlin Heidelberg (2002)CrossRef

34.

Guàrdia, J., Montes, J., Nart, E.: Okutsu invariants and Newton polygons. Acta Arith. 145(1), 83–108 (2010)MathSciNetCrossRef

35.

Guàrdia, J., Montes, J., Nart, E.: Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. J. Théor. Nombres Bordeaux 23(3), 667–696 (2011)MathSciNetCrossRef

36.

Guàrdia, J., Montes, J., Nart, E.: Newton polygons of higher order in algebraic number theory. Trans. Am. Math. Soc. 364(1), 361–416 (2012)MathSciNetCrossRef

37.

Guàrdia, J., Montes, J., Nart, E.: A new computational approach to ideal theory in number fields. Found. Comput. Math. 13(5), 729–762 (2013)MathSciNetCrossRef

38.

Guàrdia, J., Montes, J., Nart, E.: Higher Newton polygons and integral bases. J. Number Theory 147, 549–589 (2015)MathSciNetCrossRef

39.

Guàrdia, J., Nart, E., Pauli, S.: Single-factor lifting and factorization of polynomials over local fields. J. Symb. Comput. 47(11), 1318–1346 (2012)MathSciNetCrossRef

40.

Harvey, D., van der Hoeven, J.: Polynomial multiplication over finite fields in time \(O (n \log n)\). J. ACM 69(2), 1–40 (2022)CrossRef

41.

Henry, J.P.G., Merle, M.: Complexity of computation of embedded resolution of algebraic curves. In: Davenport, J.H. (ed.), Eurocal ’87. European Conference on Computer Algebra. Leipzig, GDR, June 2–5, (1987). Proceedings, volume 378 of Lect. Notes Comput. Sci., pp. 381–390. Springer Berlin Heidelberg, 1989

42.

Hironaka, H.: Resolution of singularities of an algebraic variety over a field of characteristic zero. Ann. Math. 79, 109–326 (1964)MathSciNetCrossRef

43.

van der Hoeven, J.: Automatic asymptotics. PhD thesis, École polytechnique, Palaiseau, France, (1997)

44.

van der Hoeven, J.: Relax, but don’t be too lazy. J. Symbol. Comput. 34, 479–542 (2002)MathSciNetCrossRef

45.

van der Hoeven, J.: Newton’s method and FFT trading. J. Symbol. Comput. 45(8), 857–878 (2010)MathSciNetCrossRef

46.

van der Hoeven, J.: Faster Chinese remaindering. Technical Report, HAL, (2016). https://hal.archives-ouvertes.fr/hal-01403810

47.

van der Hoeven, J.: Computing with D-algebraic power series. Appl. Algebra Eng. Comm. Comput. 30(1), 17–49 (2019)MathSciNetCrossRef

48.

van der Hoeven, J.: Effective power series computations. Found. Comput. Math. 19(3), 623–651 (2019)MathSciNetCrossRef

49.

van der Hoeven, J.: The Jolly Writer. Scypress, Your Guide to GNU TeXmacs (2020)

50.

van der Hoeven, J., Lecerf, G.: Modular composition via factorization. J. Complex. 48, 36–68 (2018)MathSciNetCrossRef

51.

van der Hoeven, J., Lecerf, G.: Accelerated tower arithmetic. J. Complex. 55, 101402 (2019)MathSciNetCrossRef

52.

van der Hoeven, J., Lecerf, G.: Directed evaluation. J. Complex. 60, 101498 (2020)MathSciNetCrossRef

53.

van der Hoeven, J., Lecerf, G.: Univariate polynomial factorization over finite fields with large extension degree. Appl. Algebra Eng. Commun. Comput. 35, 121–149 (2024)MathSciNetCrossRef

54.

Kaltofen, E., Shoup, V.: Fast polynomial factorization over high algebraic extensions of finite fields. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, pp. 184–188. New York, NY, USA, ACM (1997)

55.

Kaltofen, E., Shoup, V.: Subquadratic-time factoring of polynomials over finite fields. Math. Comput. 67(223), 1179–1197 (1998)MathSciNetCrossRef

56.

Kedlaya, K.S.: On the algebraicity of generalized power series. Beitr. Algebra Geom. 58, 499–527 (2017)MathSciNetCrossRef

57.

Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767–1802 (2011)MathSciNetCrossRef

58.

Kung, H.T., Traub, J.F.: All algebraic functions can be computed fast. J. ACM 25(2), 245–260 (1979)MathSciNetCrossRef

59.

Lang, S.: Algebra. Graduate Texts in Mathematics, vol. 211, 3rd edn. Springer-Verlag, New York (2002)

60.

Lecerf, G.: Fast separable factorization and applications. Appl. Algebra Eng. Comm. Comput. 19(2), 135–160 (2008)MathSciNetCrossRef

61.

Lecerf, G.: New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. Appl. Algebra Eng. Comm. Comput. 21(2), 151–176 (2010)MathSciNetCrossRef

62.

MacLane, S.: A construction for absolute values in polynomial rings. Trans. Am. Math. Soc. 40(3), 363–395 (1936)MathSciNetCrossRef

63.

MacLane, S.: A construction for prime ideals as absolute values of an algebraic field. Duke Math. J. 2(3), 492–510 (1936)MathSciNet

64.

Montes, J.: Polígonos de Newton de orden superior y aplicaciones aritméticas. PhD thesis, Universitat de Barcelona, Spain, (1999)

65.

Mora, F.: An algorithm to compute the equations of tangent cones. In: Calmet, J. (ed.), Computer Algebra. EUROCAM ’82, European Computer Algebra Conference, Marseilles, France, April 5-7, 1982, volume 144 of Lect. Notes in Computer Sc., pp. 158–165. Springer-Verlag Berlin Heidelberg, (1982)

66.

Moroz, G.: New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1090–1099. Los Alamitos, CA, USA. IEEE (2022)

67.

Moroz, G., Schost, É.: A fast algorithm for computing the truncated resultant. In: Rosenkranz, M. (ed.), Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pp. 341–348. New York, NY, USA, (2016). ACM

68.

Nart, E.: Okutsu-Montes representations of prime ideals of one-dimensional integral closures. Publicacions Matemàtiques 55(2), 261–294 (2011)MathSciNetCrossRef

69.

Neiger, V., Rosenkilde, J., Schost, É.: Fast computation of the roots of polynomials over the ring of power series. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’17, pp. 349–356. ACM Press, New York, NY, USA, (2017)

70.

Newton, I.: De methodis serierum et Fluxionum. Manuscript, (1671)

71.

Okutsu, K.: Construction of integral basis. I. Proc. Jpn. Acad. Ser. A Math. Sci. 58(1), 47–49 (1982)MathSciNetCrossRef

72.

Okutsu, K.: Construction of integral basis. II. Proc. Jpn. Acad. Ser. A Math. Sci. 58(2), 87–89 (1982)MathSciNetCrossRef

73.

Okutsu, K.: Construction of integral basis. III. Proc. Jpn. Acad. Ser. A Math. Sci. 58(3), 117–119 (1982)MathSciNetCrossRef

74.

Okutsu, K.: Construction of integral basis. IV. Proc. Jpn. Acad. Ser. A Math. Sci. 58(4), 167–169 (1982)MathSciNetCrossRef

75.

Ore, Ö.: Zur Theorie der Algebraischen Körper. Acta Math. 44, 219–314 (1923)MathSciNetCrossRef

76.

Ore, Ö.: Bestimmung der Diskriminanten algebraischer Körper. Acta Math. 45, 303–344 (1925)MathSciNetCrossRef

77.

Ore, Ö.: Newtonsche Polygone in der Theorie der algebraischen Körper. Math. Ann. 99, 84–117 (1928)MathSciNetCrossRef

78.

Ostrowski, A.M.: Über die Bedeutung der Theorie der konvexen Polyeder für die formale Algebra. Jahresber. Deutsch. Math.-Verein. 30(2), 98–99 (1921). (Talk given at Der Deutsche Mathematikertag vom 18–24 September 1921 in Jena)

79.

Ostrowski, A.M.: On multiplication and factorization of polynomials. I. Lexicographic orderings and extreme aggregates of terms. Aequationes Math. 13(3), 201–228 (1975)MathSciNetCrossRef

80.

Ostrowski, A.M.: On the significance of the theory of convex polyhedra for formal algebra. SIGSAM Bull. 33(1), 5 (1999). (Translated from [78])CrossRef

81.

Pan, V.Y.: Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. J. Symbol. Comput. 33(5), 701–733 (2002)MathSciNetCrossRef

82.

Pauli, S.: Factoring polynomials over local fields. J. Symbol. Comput. 32(5), 533–547 (2001)MathSciNetCrossRef

83.

Poteaux, A.: Calcul de développements de Puiseux et application au calcul de groupe de monodromie d’une courbe algébrique plane. PhD thesis, Université de Limoges, France, (2008)

84.

Poteaux, A., Rybowicz, M.: Improving complexity bounds for the computation of Puiseux series over finite fields. In: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC’15, pp. 299–306. New York, NY, USA. ACM (2015)

85.

Poteaux, A., Schost, É.: Modular composition modulo triangular sets and applications. Comput. Complex. 22(3), 463–516 (2013)MathSciNetCrossRef

86.

Poteaux, A., Weimann, M.: Using approximate roots for irreducibility and equi-singularity issues in \(K [[x]] [y]\). Technical Report, arXiv:1904.00286, (2019)

87.

Poteaux, A., Weimann, M.: Computing Puiseux series: a fast divide and conquer algorithm. Ann. Henri Lebesgue 5, 1061–1102 (2021)MathSciNetCrossRef

88.

Poteaux, A., Weimann, M.: A quasi-linear irreducibility test in \({\mathbb{K} } [[x]] [y]\). Comput. Complex. 31, 6 (2022)MathSciNetCrossRef

89.

Poteaux, A., Weimann, M.: Local polynomial factorisation: improving the Montes algorithm. In: Hashemi, A. (ed.), Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pp. 149–157. ACM, New York, NY, USA, (2022)

90.

Puiseux, M.V.: Recherches sur les fonctions algébriques. J. Math. Pures et Appliquées 15, 365–480 (1850)

91.

Russell, P.: Hamburger-Noether expansions and approximate roots of polynomials. Manuscr. Math. 31, 25–95 (1980)MathSciNetCrossRef

92.

Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf. 7, 395–398 (1977)MathSciNetCrossRef

93.

Schönhage, A.: The fundamental theorem of algebra in terms of computational complexity. Math. Inst. Univ. of Tübingen, Technical Report (1982)

94.

Shoup, V.: New algorithms for finding irreducible polynomials over finite fields. Math. Comp. 54(189), 435–447 (1990)MathSciNetCrossRef

95.

Smith, S.: On the higher singularities of plane curves. Prod. Lond. Math. Soc. 6, 153–182 (1875)MathSciNet

96.

von Tschirnhaus, E.W.: Nova methodus auferendi omnes terminos intermedios ex data æquatione. Acta Eriditorium, 1683, 204–207

97.

van der Waerden, B.L. Algebra. Springer, 7th edition: Based in part on lectures by E. Artin and E, Noether (1991)

98.

Walker, R.J.: Algebraic Curves, volume 13 of Princeton mathematical series. Princeton University Press, (1950)

99.

Walsh, P.: A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function. Math. Comp. 69(231), 1167–1182 (2000)MathSciNetCrossRef

100.

Walsh, P.G.: On the complexity of rational Puiseux expansions. Pacific J. Math. 188(2), 369–387 (1999)MathSciNetCrossRef

101.

Watt, S.M.: A fixed point method for power series computation. In: Gianni, P. (ed.), Symbolic and Algebraic Computation. International Symposium ISSAC’ 88, Rome, Italy, July 4-8, 1988. Proceedings, volume 358 of Lect. Notes in Computer Sc., pp. 206–217. Springer-Verlag, (1989)

102.

Zariski, O.: Le problème des modules pour les branches planes. Hermann, Paris (1986)

Title: Plane curve germs and contact factorization
Authors: Joris van der Hoeven
Grégoire Lecerf
Publication date: 30-11-2024
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-024-00669-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"