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

Let a1,ldots,am be distinct elements of a field K, and let Z(X)=prodi=1m (X-ai). We study the arithmetic complexity of computing the unique normalized Bezout pair s,t satisfying sZ+tZ'=1, with deg t<m and deg s<m-1. The classical product-tree approach requires O(MK(m)log m) field operations, where MK(m) denotes the cost of multiplying degree-<m polynomials over K. Thus, even when MK(m)=O(mlog m), the resulting bound is O(mlog2 m) rather than O(mlog 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(MK(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(MK(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(mlog m) nonscalar lower bound. Hence an O(mlog m) algorithm, if it exists in this model, would be asymptotically optimal. The reconstruction is genuinely characteristic-dependent: in characteristic p, all squarefree polynomials Xp+cX+d, with fixed cne 0, have the same normalized Bezout pair (0,c-1). Therefore the all-field, all-input O(mlog m) problem remains open; generically in characteristic zero, however, it is reduced to the corresponding arbitrary-node multipoint evaluation and interpolation problem.