SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Aug 28, 2026 · UTC

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-prog

Read original source ↗ Open in workspace

recordType

paper

region

Global