Generic Characteristic-Zero Equivalence Between Derivative Bezout Inversion and Multipoint Evaluation

arXiv:2609.17578v1 Announce Type: cross 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 eg t<m and eg 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(mlog m), the resulting bound is O(mlog^2 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(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(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 X^p+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.

Source: arXiv cs.LG | 2026-09-17