On the number of real zeros of random fewnomials. (English) Zbl 1441.60014
Summary: Consider a system \(f_1(x)=0,\dots,f_n(x)=0\) of \(n\) random real polynomial equations in \(n\) variables, where each \(f_i\) has a prescribed set of exponent vectors described by a set \(A\subseteq\mathbb{N}^n\) of cardinality \(t\). Assuming that the coefficients of the \(f_i\) are independent Gaussians of any variance, we prove that the expected number of zeros of the random system in the positive orthant is bounded from above by \(\frac{1}{2^{n-1}}\binom{t}{n}\).
References:
| [1] | M. Avendan͂o, The number of roots of a lacunary bivariate polynomial on a line, J. Symbolic Comput., 44 (2009), pp. 1280-1284, https://doi.org/10.1016/j.jsc.2008.02.016. · Zbl 1170.12003 |
| [2] | A. T. Bharucha-Reid and M. Sambandham, Random Polynomials, Probab. Math. Statist., Academic Press, Orlando, FL, 1986. · Zbl 0615.60058 |
| [3] | F. Bihan, Polynomial systems supported on circuits and dessins d’enfants, J. Lond. Math. Soc. (2), 75 (2007), pp. 116-132, https://doi.org/10.1112/jlms/jdl013. · Zbl 1119.12002 |
| [4] | F. Bihan and B. El Hilany, A sharp bound on the number of real intersection points of a sparse plane curve with a line, J. Symbolic Comput., 81 (2017), pp. 88-96, https://doi.org/10.1016/j.jsc.2016.12.003. · Zbl 1429.14021 |
| [5] | F. Bihan and F. Sottile, New fewnomial upper bounds from Gale dual polynomial systems, Mosc. Math. J., 7 (2007), pp. 387-407, https://doi.org/10.17323/1609-4514-2007-7-3-387-407. · Zbl 1148.14028 |
| [6] | J. Bochnak, M. Coste, and M.-F. Roy, Real Algebraic Geometry, translated from the 1987 French original, revised by the authors, Ergeb. Math. Grenzgeb. (3) [Results in Mathematics and Related Areas (3)] 36, Springer-Verlag, Berlin, 1998, https://doi.org/10.1007/978-3-662-03718-8. |
| [7] | P. Bürgisser and I. Briquel, The Real Tau-Conjecture Is True on Average, preprint, https://arxiv.org/abs/1806.00417, 2018. · Zbl 1493.68138 |
| [8] | P. Bürgisser and F. Cucker, Condition: The Geometry of Numerical Algorithms, Grundlehren Math. Wiss. [Fundamental Principles of Mathematical Sciences] 349, Springer, Heidelberg, 2013, https://doi.org/10.1007/978-3-642-38896-5. · Zbl 1280.65041 |
| [9] | P. Bürgisser and A. Lerario, Probabilistic Schubert calculus, J. Reine Angew. Math., to appear, https://doi.org/10.1515/crelle-2018-0009. · Zbl 1436.32029 |
| [10] | R. Descartes, La Géométrie, Librairie Scientifique A. Hermann, 1886, digital reproduction by Project Gutenberg, 2008 (ebook number 26400), http://www.gutenberg.org/ebooks/26400. |
| [11] | M. Drton, B. Sturmfels, and S. Sullivant, Lectures on Algebraic Statistics, Oberwolfach Seminars 39, Birkhäuser, Basel, 2009, https://doi.org/10.1007/978-3-7643-8905-5. · Zbl 1166.13001 |
| [12] | A. Edelman and E. Kostlan, How many zeros of a random polynomial are real?, Bull. Amer. Math. Soc. (N.S.), 32 (1995), pp. 1-37, https://doi.org/10.1090/S0273-0979-1995-00571-9. · Zbl 0820.34038 |
| [13] | F. Horn and R. Jackson, General mass action kinetics, Arch. Rational Mech. Anal., 47 (1972), pp. 81-116, https://doi.org/10.1007/BF00251225. |
| [14] | R. Howard, The kinematic formula in Riemannian homogeneous spaces, Mem. Amer. Math. Soc., 106 (1993), 509, https://doi.org/10.1090/memo/0509. · Zbl 0810.53057 |
| [15] | I. Itenberg and M.-F. Roy, Multivariate Descartes’ rule, Beiträge Algebra Geom., 37 (1996), pp. 337-346. · Zbl 0870.14038 |
| [16] | M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc., 49 (1943), pp. 314-320, https://doi.org/10.1090/S0002-9904-1943-07912-8. · Zbl 0060.28602 |
| [17] | A. G. Khovanskiĭ, A class of systems of transcendental equations, Dokl. Akad. Nauk SSSR, 255 (1980), pp. 804-807. · Zbl 0569.32004 |
| [18] | A. G. Khovanskiĭ, Fewnomials, Transl. Math. Monogr. 88, Amer. Math. Soc., Providence, RI, 1991. · Zbl 0728.12002 |
| [19] | P. Koiran, Shallow circuits with high-powered inputs, in Proceeding of the Second Symposium on Innovations in Computer Science (ICS), Tsinghua University, Beijing, China, January 7-9, 2011, Tsinghua University Press, Beijing, 2011, pp. 309-320, https://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/5.html. |
| [20] | P. Koiran, N. Portier, and S. Tavenas, On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem, Discrete Comput. Geom., 53 (2015), pp. 48-63, https://doi.org/10.1007/s00454-014-9642-1. · Zbl 1325.14074 |
| [21] | P. Koiran, N. Portier, and S. Tavenas, A Wronskian approach to the real \(\tau \)-conjecture, J. Symbolic Comput., 68 (2015), pp. 195-214, https://doi.org/10.1016/j.jsc.2014.09.036. · Zbl 1302.68331 |
| [22] | E. Kostlan, On the distribution of roots of random polynomials, in From Topology to Computation: Proceedings of the Smalefest, Springer, New York, 1993, pp. 419-431. · Zbl 0788.60069 |
| [23] | J. M. Lee, Introduction to Smooth Manifolds, 2nd ed., Grad. Texts in Math. 218, Springer, New York, 2013. · Zbl 1258.53002 |
| [24] | G. Malajovich and J. M. Rojas, High probability analysis of the condition number of sparse polynomial systems, Theoret. Comput. Sci., 315 (2004), pp. 525-555, https://doi.org/10.1016/j.tcs.2004.01.006. · Zbl 1067.65053 |
| [25] | K. Phillipson and J. M. Rojas, Fewnomial systems with many roots, and an adelic tau conjecture, in Proceedings of the Bellairs Workshop on Tropical and Non-Archimedean Geometry (May 6-13, 2011, Barbados), Contemp. Math. 605, AMS, Providence, RI, 2013, pp. 45-71, https://doi.org/10.1090/conm/605/12111. · Zbl 1320.13035 |
| [26] | V. V. Prasolov, Problems and Theorems in Linear Algebra, translated from the Russian manuscript by D. A. Le\u\ites, Transl. Math. Monogr. 134, AMS, Providence, RI, 1994. · Zbl 0803.15001 |
| [27] | J. M. Rojas, On the average number of real roots of certain random sparse polynomial systems, in The Mathematics of Numerical Analysis (Park City, UT, 1995), Lectures in Appl. Math. 32, AMS, Providence, RI, 1996, pp. 689-699. · Zbl 0857.65055 |
| [28] | B. Shiffman and S. Zelditch, Random polynomials with prescribed Newton polytope, J. Amer. Math. Soc., 17 (2004), pp. 49-108, https://doi.org/10.1090/S0894-0347-03-00437-5. · Zbl 1119.60007 |
| [29] | B. Shiffman and S. Zelditch, Random complex fewnomials, I, in Notions of Positivity and the Geometry of Polynomials, Trends Math., Springer, Basel, 2011, pp. 375-400, https://doi.org/10.1007/978-3-0348-0142-3_20. · Zbl 1246.32006 |
| [30] | M. Shub and S. Smale, Complexity of Bézout’s Theorem II: Volumes and probabilities, in Computational Algebraic Geometry, F. Eyssette and A. Galligo, eds., Progr. Math. 109, Birkhäuser, Boston, MA, 1993, pp. 267-285, https://doi.org/10.1007/978-1-4612-2752-6_19. · Zbl 0851.65031 |
| [31] | F. Sottile, Real Solutions to Equations from Geometry, University Lecture Series 57, AMS, Providence, RI, 2011, https://doi.org/10.1090/ulect/057. · Zbl 1233.14001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
