P-adic root isolation.

Sturm, Thomas ; Weispfenning, Volker

RACSAM, Tome 98 (2004), p. 239-258 / Harvested from Biblioteca Digital de Matemáticas

Abstract

We present an implemented algorithmic method for counting and isolating all p-adic roots of univariate polynomials f over the rational numbers. The roots of f are uniquely described by p-adic isolating balls, that can be refined to any desired precision; their p-adic distances are also computed precisely. The method is polynomial space in all input data including the prime p. We also investigate the uniformity of the method with respect to the coefficients of f and the primes p. Our method thus provides information analogous to that provided by well-established real methods as, e.g., Cauchy bounds and Sturm sequences over the reals.

Résumé

Presentamos un método algorítmico implementado para contar y aislar todas las raíces p-ádicas de polinomios f en una variable con coeficientes racionales. Las raíces de f se describen unívocamente mediante bolas p-ádicas que las aíslan y que pueden ser refinadas hasta cualquier precisión que se desee; sus distancias p-ádicas son también computadas con precisión. El método posee complejidad polinomial en todos los datos de entrada, incluído el primo p. También investigamos la uniformidad del método con respecto a los coeficientes de f y los números primos p. Nuestro método suministra información análoga a la que suministran métodos bien establecidos para los números reales, como por ejemplo, las cotas de Cauchy y la sucesión de Sturm.

Détail

Publié le : 2004-01-01

MR MR2136169 | Zbl 1156.68058

DMLE-ID : 4138