Running summarizing tools on a new article

Abstract: Let a1, . . . , am be distinct elements of a field and let Z(X) = Πi(X − ai). We study the total arithmetic complexity of the canonical Bézout pair sZ + tZ′ = 1, deg t < m, deg s < m − 1. The standard product-tree route uses O(MF(m) logm) field operations. Even when MF(m) = O(m logm), this is O(m log2 m) rather than O(m logm). Our main result identifies the missing logarithm. Over an infinite field of characteristic zero, in the generic rational straight-line-program model, computing all coefficients of (s, t) is equivalent, up to O(MF(m)) operations, to arbitrary-node multipoint evaluation and to interpolation. The new direction rests on an explicit quasi-linear reconstruction of Z from (s, t) on a nonempty Zariski-open set. It also transfers Strassen’s Ω(m logm) nonscalar lower bound for elementary symmetric functions to the Bézout problem, showing that the requested order would be optimal. The reconstruction is genuinely characteristic-dependent: in characteristic p, the squarefree polynomials Xp + cX + d all have the same canonical pair (0, c−1) for fixed c ̸= 0. Thus the all-field, all-input O(m logm) question is not resolved here; it is reduced generically in characteristic zero to the corresponding arbitrary-node evaluation problem.