On Isolating Roots in a Multiple Field Extension

• Published in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
• Main Authors: Katsamaki, Christina, Rouillier, Fabrice
• Other Authors: Sorbonne Université (SU), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2023
• Subjects: Root isolation; Field extension; Bit-complexity; [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]; Tromso
• Online Access: https://hal.science/hal-04116621; https://hal.science/hal-04116621/document; https://hal.science/hal-04116621/file/Isolating_roots_in_a_multiple_field_extension__HAL_.pdf; https://doi.org/10.1145/3597066.3597107

International audience We address univariate root isolation when the polynomial's coefficients are in a multiple field extension. We consider a polynomial $F \in L[Y]$, where $L$ is a multiple algebraic extension of $\mathbb{Q}$. We provide aggregate bounds for $F$ and algorithmic and bit-complexity results for the problem of isolating its roots. For the latter problem we follow a common approach based on univariate root isolation algorithms. For the particular case where $F$ does not have multiple roots, we achieve a bit-complexity in $\tilde{\mathcal{O}}_B(n d^{2n+2}(d+n\tau))$, where $d$ is the total degree and $\tau$ is the bitsize of the involved polynomials.In the general case we need to enhance our algorithm with a preprocessing step that determines the number of distinct roots of $F$. We follow a numerical, yet certified, approach that has bit-complexity$\tilde{\mathcal{O}}_B(n^2d^{3n+3}\tau + n^3 d^{2n+4}\tau)$.