2017/09/11 by Koiran, Pascal
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1709.03294
We give a separation bound for the complex roots of a trinomial f ∈ ℤ[X]. The logarithm of the inverse of our separation bound is polynomial in the size of the sparse encoding of f; in particular, it is polynomial in log (°f). It is known that no such bound is possible for 4-nomials (polynomials with 4 monomials). For trinomials, the classical results (which are based on the degree of f rather than the number of monomials) give separation bounds that are exponentially worse.As an algorithmic application, we show that the number of real roots of a trinomial f can be computed in time polynomial in the size of the sparse encoding of~f. The same problem is open for 4-nomials.