Generic Characteristic-Zero Equivalence Between Derivative B\'ezout Inversion and Multipoint Evaluation

Abstract:Let $a_1,\ldots,a_m$ be distinct elements of a field $K$, and let $Z(X)=\prod_{i=1}^m (X-a_i)$. We study the arithmetic complexity of computing the unique normalized Bezout pair $s,t$ satisfying $sZ+tZ'=1$, with $°t<m$ and $°s<m-1$. The classical product-tree approach requires $O(M_K(m)\log m)$ field operations, where $M_K(m)$ denotes the cost of multiplying degree-$<m$ polynomials over $K$. Thus, even when $M_K(m)=O(m\log m)$, the resulting bound is $O(m\log^2 m)$ rather than $O(m\log m)$. Over an infinite field of characteristic zero, we prove that, in the generic rational straight-line-program model, computing all coefficients of the canonical Bezout pair is equivalent, up to an additive $O(M_K(m))$ cost, to arbitrary-node multipoint polynomial evaluation and to interpolation. The main ingredient is an explicit differential reconstruction that recovers $Z$ from $(s,t)$ in $O(M_K(m))$ arithmetic operations on a nonempty Zariski-open subset. Combining this reconstruction with automatic differentiation and transposition yields the complexity equivalence. We further transfer Strassen's lower bound for the elementary symmetric functions to the Bezout problem, obtaining an $\Omega(m\log m)$ nonscalar lower bound. Hence an $O(m\log m)$ algorithm, if it exists in this model, would be asymptotically optimal. The reconstruction is genuinely characteristic-dependent: in characteristic $p$, all squarefree polynomials $X^p+cX+d$, with fixed $c\ne 0$, have the same normalized Bezout pair $(0,c^{-1})$. Therefore the all-field, all-input $O(m\log m)$ problem remains open; generically in characteristic zero, however, it is reduced to the corresponding arbitrary-node multipoint evaluation and interpolation problem.

Symbolic Computation (cs.SC); Machine Learning (cs.LG)

arXiv:2609.17578 [cs.SC]

(or arXiv:2609.17578v1 [cs.SC] for this version)

https://doi.org/10.48550/arXiv.2609.17578 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.