On the minimum value of the condition number of polynomials

Abstract

The condition number of a polynomial is a natural measure of the sensitivity of the roots under small perturbations of the polynomial coefficients. In 1993 Shub and Smale posed the problem of finding a sequence of univariate polynomials of degree N with condition number bounded above by N⁠. In Beltrán et al. (2021, A sequence of polynomials with optimal condition number. J. Amer. Math. Soc., 34, 219–244) it was proved that the optimal value of the condition number is of the form O(N−−√)⁠, and the sequence demanded by Shub and Smale was described by a closed formula for large enough N⩾N0 with N0 unknown, and by a search algorithm for the rest of the cases. In this paper we find concrete estimates for the constant hidden in the O(N−−√) term and we describe a simple formula for a sequence of polynomials whose condition number is at most N⁠, valid for all N=4M2⁠, with M a positive integer.