{
"id": "1911.02540",
"version": "v1",
"published": "2019-11-06T18:24:47.000Z",
"updated": "2019-11-06T18:24:47.000Z",
"title": "How many zeros of a random sparse polynomial are real?",
"authors": [
"Gorav Jindal",
"Anurag Pandey",
"Himanshu Shukla",
"Charilaos Zisopoulos"
],
"categories": [
"math.PR",
"cs.CC",
"math.CA"
],
"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.",
"revisions": [
{
"version": "v1",
"updated": "2019-11-06T18:24:47.000Z"
}
],
"analyses": {
"keywords": [
"random sparse polynomial",
"expected number",
"real zeros",
"independent standard normal distributions",
"coefficients"
],
"note": {
"typesetting": "TeX",
"pages": 0,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}