2019/11/06 by Gorav Jindal, Anurag Pandey, Jindal, Gorav +5
Computer Science · Mathematics · #Classical Analysis and ODEs (math.CA) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.CC #math.CA #math.PR
paper · pdf · doi:10.48550/arxiv.1911.02540
arxiv created 2019/11/06 · arxiv updated 2019/11/07
We investigate the number of real zeros of a univariate k-sparse polynomial f over the reals, when the coefficients of f come from independent standard normal distributions. Recently Bürgisser, Ergür and Tonelli-Cueto showed that the expected number of real zeros of f in such cases is bounded by O(√(k) log k). In this work, we improve the bound to O(√(k)) and also show that this bound is tight by constructing a family of sparse support whose expected number of real zeros is lower bounded by Ω(√(k)). Our main technique is an alternative formulation of the Kac integral by Edelman-Kostlan which allows us to bound the expected number of zeros of f in terms of the expected number of zeros of polynomials of lower sparsity. Using our technique, we also recover the O(log n) bound on the expected number of real zeros of a dense polynomial of degree n with coefficients coming from independent standard normal distributions.