Discovering the roots: uniform closure results for algebraic classes under factoring
Pranjal Kumar Dutta, Nitin Saxena, Amit Sinhababu · 2018
Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the number of roots r is small but the multiplicities are exponentially large. Our method sets up a linear system in r unknowns and iteratively builds the roots as formal power series. For an algebraic circuit f(x1,…,xn) of size s we prove that each factor has size at most a polynomial in: s and the degree of the squarefree part of f. Consequently, if f1 is a 2Ω(n)-hard polynomial then any nonzero multiple ∏i fiei is equally hard for arbitrary positive ei’s, assuming that ∑ideg(fi) is at most 2O(n).