How Many Zeros of a Random Sparse Polynomial Are Real?

Gorav Jindal, Anurag Pandey, Himanshu Shukla, Charilaos Zisopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

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ürgisser, Ergür and Tonelli-Cueto showed that the expected number of real zeros of f in such cases is bounded by [EQUATION]. In this work, we improve the bound to [EQUATION] 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 [EQUATION]. 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.
Original languageEnglish
Title of host publicationISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation
EditorsAngelos Mantzaflaris
PublisherACM
Pages273-280
Number of pages8
ISBN (Electronic)9781450371001
DOIs
Publication statusPublished - 21 Jul 2020
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Symbolic and Algebraic Computation - Virtual, Kalamata, Greece
Duration: 20 Jul 202023 Jul 2020
Conference number: 45
https://issac-conference.org/2020/program.php

Conference

ConferenceInternational Symposium on Symbolic and Algebraic Computation
Abbreviated titleISSAC
CountryGreece
CityKalamata
Period20/07/202023/07/2020
Internet address

Keywords

  • random polynomials
  • real tau conjecture
  • sparse polynomials

Fingerprint Dive into the research topics of 'How Many Zeros of a Random Sparse Polynomial Are Real?'. Together they form a unique fingerprint.

  • Cite this

    Jindal, G., Pandey, A., Shukla, H., & Zisopoulos, C. (2020). How Many Zeros of a Random Sparse Polynomial Are Real? In A. Mantzaflaris (Ed.), ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (pp. 273-280). ACM. https://doi.org/10.1145/3373207.3404031