Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation

Abstract

Let $a_1,\dots ,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+t{Z}^{\prime }=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.