2017/08/30 by Poteaux, Adrien, Weimann, Martin
#12Y05 #13P05 #14Q20 #68W30 #Algebraic Geometry (math.AG) #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.09067
Let F∈ \mathbbK[X, Y ] be a polynomial of total degree D defined over a perfect field \mathbbK of characteristic zero or greater than D. Assuming F separable with respect to Y , we provide an algorithm that computes the singular parts of all Puiseux series of F above X = 0 in less than O(Dδ) operations in \mathbbK, where δ 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 factorization by dynamic evaluation. As a first main corollary, we compute the irreducible factors of F in \mathbbK[[X]][Y ] up to an arbitrary precision XN with O(D(δ+ N )) arithmetic operations. As a second main corollary, we compute the genus of the plane curve defined by F with O(D3) arithmetic operations and, if \mathbbK = ℚ, with O((h+1)D3) bit operations using a probabilistic algorithm, where h is the logarithmic heigth of F.