Computing Puiseux series: a fast divide and conquer algorithm

Poteaux, Adrien; Weimann, Martin

Annales Henri Lebesgue, Tome 4 (2021), pp. 1061-1102.

Soit $F\in 𝕂[X,Y]$ un polynôme de degré total $D$ défini au dessus d’un corps parfait $𝕂$ de caractéristique zéro ou plus grande que $D$. Sous l’hypothèse que $F$ est séparable par rapport à la variable $Y$, nous décrivons un algorithme qui calcule l’ensemble des parties singulières des séries de Puiseux de $F$ au-dessus de $X=0$ avec un nombre moyen d’opérations sur $𝕂$ borné par $Ø\tilde{}\left(D{\delta }_{}\right)$, où ${\delta }_{}$ est la valuation du résultant de $F$ et sa dérivée partielle en $Y$. Pour se faire, nous utilisons une stratégie de type “diviser pour régner” et nous remplaçons l’utilisation de factorisation univariée par l’évaluation dynamique. Comme premier corollaire principal, nous calculons les facteurs irréductibles de $F$ dans $𝕂\left[\right[X\left]\right]\left[Y\right]$ à precision $X^N$ en $Ø\tilde{}\left(D({\delta }_{}+N)\right)$ opérations arithmétiques. Comme second corollaire, nous calculons le genre de la courbe algébrique plane définie par $F$ en $Ø\tilde{}\left(D^3\right)$ opérations arithmétiques, et, si $𝕂=\mathbb{Q}$, en $Ø\tilde{}\left((h+1)D^3\right)$ opérations binaires via des algorithmes probabilites, où $h$ est la taille logarithmique de $F$.

Let $F\in 𝕂[X,Y]$ be a polynomial of total degree $D$ defined over a perfect field $𝕂$ of characteristic zero or greater than $D$. Assuming $F$ separable with respect to $Y$, we provide an algorithm that computes all singular parts of Puiseux series of $F$ above $X=0$ in an expected $Ø\tilde{}\left(D{\delta }_{}\right)$ operations in $𝕂$, where ${\delta }_{}$ is the valuation of the resultant of $F$ and its partial derivative with respect to $Y$. To this aim, we use a divide and conquer strategy and replace univariate factorisation by dynamic evaluation. As a first main corollary, we compute the irreducible factors of $F$ in $𝕂\left[\right[X\left]\right]\left[Y\right]$ up to an arbitrary precision $X^N$ with $Ø\tilde{}\left(D({\delta }_{}+N)\right)$ arithmetic operations. As a second main corollary, we compute the genus of the plane curve defined by $F$ with $Ø\tilde{}\left(D^3\right)$ arithmetic operations and, if $𝕂=\mathbb{Q}$, with $Ø\tilde{}\left((h+1)D^3\right)$ bit operations using probabilistic algorithms, where $h$ is the logarithmic height of $F$.

Classification : 14B05, 14H20, 14Q20, 68Q25
Mots clés : Puiseux series, complexity, dynamic evaluation

[AAMM17] Alvandi, Parisa; Ataei, Masoud; Moreno Maza, Marc On the Extended Hensel Construction and Its Application to the Computation of Limit Points, Proceedings of the 42nd international symposium on symbolic and algebraic computation, ISSAC 2017, Kaiserslautern, Germany, July 25–28, 2017, Association for Computing Machinery (2017), pp. 13-20 | DOI | Zbl

[Abh89] Abhyankar, Shreeram S. Irreducibility criterion for germs of analytic functions of two complex variables, Adv. Math., Volume 74 (1989) no. 2, pp. 190-257 | DOI | MR | Zbl

[Abh90] Abhyankar, Shreeram S. Algebraic Geometry for Scientists and Engineers, Mathematical Surveys and Monographs, 35, American Mathematical Society, 1990 | MR | Zbl

[BCS + 07] Bostan, Alin; Chyzak, Frédéric; Salvy, Bruno; Lecerf, Grégoire; Schost, Éric Differential Equations for Algebraic Functions, ISSAC 2007. Proceedings of the 32nd international symposium on symbolic and algebraic computation (ISSAC 2007), Waterloo, ON, Canada, July 29–August 1, 2007 (2007), pp. 25-32 | Zbl

[BGY80] Brent, Richard P.; Gustavson, Fred G.; Yun, David Y. Y. Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, Volume 1 (1980) no. 3, pp. 259-295 | DOI | Zbl

[BK86] Brieskorn, Egbert; Knörrer, Horst Plane Algebraic Curves, Birkhäuser, 1986 (translated from the German by John Stillwell) | DOI | Zbl

[BNS13] Bauch, Jens-Dietrich; Nart, Enric; Stainsby, Hayden D. Complexity of the OM Factorizations of Polynomials over Local Fields, LMS J. Comput. Math., Volume 16 (2013), pp. 139-171 | DOI | MR | Zbl

[BP94] Bini, Dario; Pan, Victor Y. Polynomial and matrix computations. Fundamental algorithms. Vol. 1., Progress in Theoretical Computer Science, Birkhäuser, 1994 | Zbl

[Cas86] Cassel, John W. S. Local Fields, London Mathematical Society Student Texts, 3, Cambridge University Press, 1986 | Zbl

[Che51] Chevalley, Claude Introduction to the Theory of Algebraic Functions of One Variable, Mathematical Surveys, 6, American Mathematical Society, 1951 | Zbl

[CK91] Cantor, David; Kaltofen, Erich On fast multiplication of polynomials over arbitrary algebras, Acta Inf., Volume 28 (1991) no. 7, pp. 693-701 | DOI | MR | Zbl

[CSTU02] Cormier, Olivier; Singer, Michael F.; Trager, Barry M.; Ulmer, Felix Linear differential operators for polynomial equations, J. Symb. Comput., Volume 34 (2002) no. 5, pp. 355-398 | DOI | MR | Zbl

[DDD85] Dora, Jean Della; Dicrescenzo, Claire; Duval, Dominique About a New Method for Computing in Algebraic Number Fields, EUROCAL 85. European Conference on Computer Algebra Linz, Austria, April 1–3 1985 Proceedings Vol. 2: Research Contributions (Caviness, Bob F., ed.) (Lecture Notes in Computer Science), Volume 204, Springer (1985) | DOI

[DP16] Duval, Dominique; Poteaux, Adrien Death of Marc Rybowicz, Aged 52, ACM Commun. Comput. Algebra, Volume 50 (2016) no. 4, p. 191-191 | DOI | MR | Zbl

[DSMM + 05] Dahan, Xavier; Schost, Éric; Maza Moreno, Marc; Wu, Wenyuan; Xie, Yuzhen On the complexity of the D5 principle, SIGSAM Bull., Volume 39 (2005) no. 3, pp. 97-98 | DOI

[Duv89] Duval, Dominique Rational Puiseux Expansions, Compos. Math., Volume 70 (1989) no. 2, pp. 119-154 | Numdam | MR | Zbl

[Eic66] Eichler, Martin Introduction to the Theory of Algebraic Numbers and Functions, Academic Press Inc., 1966 | Zbl

[G13] von zur Gathen, Joachim von zur; Gerhard, Jürgen Modern Computer Algebra, Cambridge University Press, 2013 | DOI | Zbl

[GBGPPP17] García Barroso, Evelia Rosa; González Pérez, Pedro Daniel; Popescu-Pampu, Patrick Variations on inversion theorems for Newton–Puiseux series, Math. Ann., Volume 368 (2017) no. 3, pp. 1359-1397 | DOI | MR | Zbl

[HP98] Huang, Xiaohan; Pan, Victor Y. Fast Rectangular Matrix Multiplication and Applications, J. Complexity, Volume 14 (1998) no. 2, pp. 257-299 | DOI | MR | Zbl

[Kal88] Kaltofen, Erich Greatest Common Divisors of Polynomials Given by Straight-line Programs, J. Assoc. Comput. Mach., Volume 35 (1988) no. 1, pp. 231-264 | DOI | MR | Zbl

[KS99] Kako, Fujio; Sasaki, Tateaki Solving Multivariate Algebraic Equations by Hensel Construction, Japan J. Ind. Appl. Math., Volume 16 (1999), pp. 257-285 | MR | Zbl

[KT78] Kung, H. T.; Traub, Joseph F. All algebraic functions can be computed fast, J. Assoc. Comput. Mach., Volume 25 (1978) no. 2, pp. 245-260 | DOI | MR | Zbl

[L19] van der Hoeven, Joris; Lecerf, Grégoire Accelerated tower arithmetic, J. Complexity, Volume 55 (2019), 101402 | DOI | MR | Zbl

[L20] van der Hoeven, Joris; Lecerf, Grégoire Directed evaluation, J. Complexity, Volume 60 (2020), 101498 | DOI | MR | Zbl

[LG14] Le Gall, François Powers of Tensors and Fast Matrix Multiplication, Proceedings of the 39th international symposium on symbolic and algebraic computation, ISSAC 2014, Kobe, Japan, July 23–25, 2014, Association for Computing Machinery (2014), pp. 296-303 | DOI | Zbl

[MS16] Moroz, Guillaume; Schost, Éric A Fast Algorithm for Computing the Truncated Resultant, Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, Waterloo, Canada, July 20–22, 2016 (2016), pp. 341-348 | DOI | Zbl

[Mus75] Musser, David R. Multivariate Polynomial Factorization, J. ACM, Volume 22 (1975) no. 2, pp. 291-308 | DOI | MR | Zbl

[Per99] Peral, Jesús Montes Polígonos de Newton de orden superior y aplicaciones aritméticas, Ph. D. Thesis, Universitat de Barcelona, Spain (1999)

[PR08] Poteaux, Adrien; Rybowicz, Marc Good reduction of Puiseux series and complexity of the Newton–Puiseux algorithm over finite fields, ISSAC ’08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation (2008), pp. 239-246 | DOI

[PR11] Poteaux, Adrien; Rybowicz, Marc Complexity bounds for the rational Newton–Puiseux algorithm over finite fields, Appl. Algebra Eng. Commun. Comput., Volume 22 (2011) no. 3, pp. 187-217 | DOI | MR | Zbl

[PR12] Poteaux, Adrien; Rybowicz, Marc Good reduction of Puiseux series and applications, J. Symb. Comput., Volume 47 (2012) no. 1, pp. 32-63 | DOI | MR | Zbl

[PR15] Poteaux, Adrien; Rybowicz, Marc Improving complexity bounds for the computation of Puiseux series over finite fields, Proceedings of the 40th international symposium on symbolic and algebraic computation, ISSAC 2015, Bath, UK, July 6–9, 2015, Association for Computing Machinery (2015), pp. 299-306 | DOI | Zbl

[PS06] Pascal, Cyril; Schost, Éric Change of order for bivariate triangular sets, Proceedings of the 2006 international symposium on symbolic and algebraic computation, ISSAC 06, Genova, Italy, July 9–12, 2006, Association for Computing Machinery (2006), pp. 277-284 | Zbl

[PS13a] Poteaux, Adrien; Schost, Éric Modular Composition Modulo Triangular Sets and Applications, Comput. Complexity, Volume 22 (2013) no. 3, pp. 463-516 | DOI | MR | Zbl

[PS13b] Poteaux, Adrien; Schost, Éric On the complexity of computing with zero-dimensional triangular sets, J. Symb. Comput., Volume 50 (2013), pp. 110-138 | DOI | MR | Zbl

[Sho94] Shoup, Victor Fast Construction of Irreducible Polynomials over Finite Fields, J. Symb. Comput., Volume 17 (1994) no. 5, pp. 371-391 | DOI | MR | Zbl

[SS71] Schönage, Arnold; Strassen, Volker Fast multiplication of large numbers. (Schnelle Multiplikation großer Zahlen), Computing, Volume 7 (1971), pp. 281-292 | DOI | Zbl

[Tei74] Teissier, Bernard Cycles évanescents, sections planes et conditions de Whitney, Singularités à Cargèse (Astérisque), Volume 1973, Société Mathématique de France, 1974 no. 7-8, pp. 285-362 | Numdam | MR | Zbl

[Wal50] Walker, Robert J. Algebraic Curves, Princeton Mathematical Series, 13, Princeton University Press, 1950 | MR | Zbl

[Wei16] Weimann, Martin Bivariate Factorization Using a Critical Fiber, Found. Comput. Math., Volume 17 (2016) no. 5, pp. 1219-1263 | DOI | MR | Zbl