Title:
How many zeros of random sparse polynomials are real?
Abstract:
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\"urgisser, Erg\"ur
and Tonelli-Cueto showed that the expected number of real zeros of $f$ in
such cases is bounded by $O(\sqrt{k} \log k)$. In this work, we improve the
bound to $O(\sqrt{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 $\Omega(\sqrt{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.