Computing the roots of sparse high–degree polynomials that arise from the study of random simplicial complexes

Abstract

The problem of computing the roots of a particular sequence of sparse polynomials p_n(t) is considered. Each instance p_n(t) incorporates only the n + 1 monomial terms $t,t^{2},t^{4},\ldots ,t^{2^{n}}$ associated with the binomial coefficients of order n and alternating signs. It is shown that p_n(t) has (in addition to the obvious roots t = 0 and 1) precisely n − 1 simple roots on the interval (0,1) with no roots greater than 1, and a recursion relating p_n(t) and p_n+ 1(t) is used to show that they possess interlaced roots. Closed–form expressions for the Bernstein coefficients of p_n(t) on [0,1] are derived and employed to compute the roots in double–precision arithmetic. Despite the severe variation of the graph of p_n(t), and tight clustering of roots near t = 1, it is shown that for n ≤ 10, the roots on (0,1) are remarkably well–conditioned and can be computed to high accuracy using both the power and Bernstein forms.