Kac-Rice formulas and the number of solutions of parametrized systems of polynomial equations

Feliu, Elisenda; Sadeghimanesh, AmirHosein

doi:10.1090/mcom/3760

Kac-Rice formulas and the number of solutions of parametrized systems of polynomial equations
HTML articles powered by AMS MathViewer

by Elisenda Feliu and AmirHosein Sadeghimanesh;

Math. Comp. 91 (2022), 2739-2769

DOI: https://doi.org/10.1090/mcom/3760

Published electronically: August 11, 2022

HTML | PDF | Request permission

Abstract:

Kac-Rice formulas express the expected number of elements a fiber of a random field has in terms of a multivariate integral. We consider here parametrized systems of polynomial equations that are linear in enough parameters, and provide a Kac-Rice formula for the expected number of solutions of the system when the parameters follow continuous distributions. Combined with Monte Carlo integration, we apply the formula to partition the parameter region according to the number of solutions or find a region in parameter space where the system has the maximal number of solutions. The motivation stems from the study of steady states of chemical reaction networks and gives new tools for the open problem of identifying the parameter region where the network has at least two positive steady states. We illustrate with numerous examples that our approach successfully handles a larger number of parameters than exact methods.

References

R. J. Adler and J. E. Taylor. 2007. Random Fields and Geometry, 1st ed. Springer-Verlag, New York.
Charalambos D. Aliprantis and Owen Burkinshaw, Principles of real analysis, North-Holland Publishing Co., New York-Amsterdam, 1981. MR 607327
Antonio Auffinger, Gérard Ben Arous, and Jiří Černý, Random matrices and complexity of spin glasses, Comm. Pure Appl. Math. 66 (2013), no. 2, 165–201. MR 2999295, DOI 10.1002/cpa.21422
Jean-Marc Azaïs and Mario Wschebor, Level sets and extrema of random processes and fields, John Wiley & Sons, Inc., Hoboken, NJ, 2009. MR 2478201, DOI 10.1002/9780470434642
C. P. Bagowski, J. Besser, C. R. Frey, and J. E. Ferrell. 2003. The JNK cascade as a biochemical switch in mammalian cells: Ultrasensitive and all-or-none responses, Curr. Biol. 13, no. 4, 315–320.
Saugata Basu, Antonio Lerario, Erik Lundberg, and Chris Peterson, Random fields and the enumerative geometry of lines on real and complex hypersurfaces, Math. Ann. 374 (2019), no. 3-4, 1773–1810. MR 3985123, DOI 10.1007/s00208-019-01837-0
Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869, DOI 10.1007/3-540-33099-2
Frédéric Bihan, Alicia Dickenstein, and Magalí Giaroli, Lower bounds for positive roots and regions of multistationarity in chemical reaction networks, J. Algebra 542 (2020), 367–411. MR 4031126, DOI 10.1016/j.jalgebra.2019.10.002
Russell Bradford, James H. Davenport, Matthew England, Scott McCallum, and David Wilson, Truth table invariant cylindrical algebraic decomposition, J. Symbolic Comput. 76 (2016), 1–35. MR 3461257, DOI 10.1016/j.jsc.2015.11.002
V. Chickarmane, C. Troein, U. A. Nuber, H. M. Sauro, and C. Peterson. 2006. Transcriptional dynamics of the embryonic stem cell switch, PLOS Comput. Biol. 9, no. 2, 123.
C. Conradi, E. Feliu, M. Mincheva, and C. Wiuf. 2017. Identifying parameter regions for multistationarity, PLOS Comput. Biol. 13, no. 10, 1005751.
Carsten Conradi and Dietrich Flockerzi, Switching in mass action networks based on linear inequalities, SIAM J. Appl. Dyn. Syst. 11 (2012), no. 1, 110–134. MR 2902612, DOI 10.1137/10081722X
Carsten Conradi, Alexandru Iosif, and Thomas Kahle, Multistationarity in the space of total concentrations for systems that admit a monomial parametrization, Bull. Math. Biol. 81 (2019), no. 10, 4174–4209. MR 4012471, DOI 10.1007/s11538-019-00639-4
C. Conradi and M. Mincheva. 2014. Catalytic constants enable the emergence of bistability in dual phosphorylation, J. R. S. Interface, 11, no. 95.
Solen Corvez and Fabrice Rouillier, Using computer algebra tools to classify serial manipulators, Automated deduction in geometry, Lecture Notes in Comput. Sci., vol. 2930, Springer, Berlin, 2004, pp. 31–43. MR 2090401, DOI 10.1007/978-3-540-24616-9_{3}
David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
P. Donnell, M. Banaji, A. Marginean, and C. Pantea. 2014. CoNtRol: an open source framework for the analysis of chemical reaction networks, Bioinformatics, 30, no. 11, 1633–1634.
Alan Edelman and Eric Kostlan, How many zeros of a random polynomial are real?, Bull. Amer. Math. Soc. (N.S.) 32 (1995), no. 1, 1–37. MR 1290398, DOI 10.1090/S0273-0979-1995-00571-9
P. Ellison, M. Feinberg, H. Ji, and D. Knight, Chemical reaction network toolbox, version 2.2. Available online at http://www.crnt.osu.edu/CRNTWin, 2012.
Matthew England, Russell Bradford, and James H. Davenport, Improving the use of equational constraints in cylindrical algebraic decomposition, ISSAC’15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2015, pp. 165–172. MR 3388296
Matthew England, Russell Bradford, and James H. Davenport, Cylindrical algebraic decomposition with equational constraints, J. Symbolic Comput. 100 (2020), 38–71. MR 4079042, DOI 10.1016/j.jsc.2019.07.019
Steven N. Evans, The expected number of zeros of a random system of $p$-adic polynomials, Electron. Comm. Probab. 11 (2006), 278–290. MR 2266718, DOI 10.1214/ECP.v11-1230
M. Feinberg, Chemical reaction network structure and the stability of complex isothermal reactors–II. Multiple steady states for networks of deficiency one, Chem. Eng. Sci. 43 (1988), no. 1, 1–25.
Martin Feinberg, The existence and uniqueness of steady states for a class of chemical reaction networks, Arch. Rational Mech. Anal. 132 (1995), no. 4, 311–370. MR 1365832, DOI 10.1007/BF00375614
Martin Feinberg, Foundations of chemical reaction network theory, Applied Mathematical Sciences, vol. 202, Springer, Cham, 2019. MR 3890056, DOI 10.1007/978-3-030-03858-8
Elisenda Feliu, Nidhi Kaihnsa, Timo de Wolff, and Oğuzhan Yürük, The kinetic space of multistationarity in dual phosphorylation, J. Dynam. Differential Equations 34 (2022), no. 2, 825–852. MR 4413372, DOI 10.1007/s10884-020-09889-6
E. Feliu and C. Wiuf. 2013. A computational method to preclude multistationarity in networks of interacting species, Bioinformatics, 29, no. 18, 2327–2334.
E. Feliu and C. Wiuf. 2013. Simplifying biochemical models with intermediate species, J. R. Soc. Interface, 10, no. 87, 20130484.
J. Gerhard, D. Jeffrey, and G. Moroz. 2010. A package for solving parametric polynomial systems, ACM Commun. Comput. Algebra, 43, no. 3–4, 61–72.
J. Gunawardena, Chemical reaction network theory for in-silico biologists, Available online at http://vcp.med.harvard.edu/papers/crnt, 2003.
T. Hahn, Cuba—a library for multidimensional numerical integration, Comput. Phys. Comm. 168 (2005), no. 2, 78–95. MR 2136794, DOI 10.1016/j.cpc.2005.01.010
Badal Joshi and Anne Shiu, Atoms of multistationarity in chemical reaction networks, J. Math. Chem. 51 (2013), no. 1, 153–178. MR 3009908, DOI 10.1007/s10910-012-0072-0
M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc. 49 (1943), 314–320. MR 7812, DOI 10.1090/S0002-9904-1943-07912-8
V. B. Kothamachu, E. Feliu, L. Cardelli, and O. S. Soyer. 2015. Unlimited multistability and boolean logic in microbial signalling, J. R. Soc. Interface, 12, no. 108, 20150234.
Daniel Lazard and Fabrice Rouillier, Solving parametric polynomial systems, J. Symbolic Comput. 42 (2007), no. 6, 636–667. MR 2325919, DOI 10.1016/j.jsc.2007.01.007
Ernst W. Mayr and Albert R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math. 46 (1982), no. 3, 305–329. MR 683204, DOI 10.1016/0001-8708(82)90048-2
Ernst W. Mayr and Stephan Ritscher, Dimension-dependent bounds for Gröbner bases of polynomial ideals, J. Symbolic Comput. 49 (2013), 78–94. MR 2997841, DOI 10.1016/j.jsc.2011.12.018
Stefan Müller, Elisenda Feliu, Georg Regensburger, Carsten Conradi, Anne Shiu, and Alicia Dickenstein, Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry, Found. Comput. Math. 16 (2016), no. 1, 69–97. MR 3451424, DOI 10.1007/s10208-014-9239-3
K. M. Nam, B. M. Gyori, S. V. Amethyst, D. J. Bates, and J. Gunawardena. 2020. Robustness and parameter geography in post-translational modification systems, PLOS Comput. Biol. 16, no. 5, 1007573.
L. Nicolaescu, On the Kac-Rice formula, Available online at https://www.researchgate.net/publication/267039543_On_the_Kac-Rice_formula, 2014.
A. B. Owen, Monte Carlo theory, methods and examples, http://statweb.stanford.edu/~owen/mc/, 2013.
Mercedes Pérez Millán, Alicia Dickenstein, Anne Shiu, and Carsten Conradi, Chemical reaction systems with toric steady states, Bull. Math. Biol. 74 (2012), no. 5, 1027–1065. MR 2909119, DOI 10.1007/s11538-011-9685-x
A. J. Rainal, Origin of Rice’s formula, IEEE Trans. Inform. Theory 34 (1988), no. 6, 1383–1387. MR 993433, DOI 10.1109/18.21276
S. O. Rice, Mathematical analysis of random noise, Bell System Tech. J. 23 (1944), 282–332. MR 10932, DOI 10.1002/j.1538-7305.1944.tb00874.x
Walter Rudin, Principles of mathematical analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976. MR 385023
Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill Book Co., New York, 1987. MR 924157
A. H. Sadeghimanesh, Polynomial superlevel set representation of the multistationarity region of chemical reaction networks, Preprint, arXiv:2003.07764, 2020.
A. H. Sadeghimanesh and M. England, Improving algebraic tools to study bifurcation sequences of population models, CASC 2021 Extended Abstracts, Sirius Mathematics Centre https://siriusmathcenter.ru/pr_img/1918100371/20210914/13241784/Program_010w, 7-10, 2021.
AmirHosein Sadeghimanesh and Elisenda Feliu, The multistationarity structure of networks with intermediates and a binomial core network, Bull. Math. Biol. 81 (2019), no. 7, 2428–2462. MR 3977620, DOI 10.1007/s11538-019-00612-1
A. H. Sadeghimanesh and E. Feliu, MCKR implementation, version 1.0. Available online at http://doi.org/10.5281/zenodo.4085079, 2020.
A. H. Sadeghimanesh and E. Feliu, MCKR repository of computations, version 1.0.0. Available online at https://doi.org/10.5281/zenodo.4026954, 2020.
T. Shiraishi, S. Matsuyama, and H. Kitano. 2010. Large-scale analysis of network bistability for human cancers, PLOS Comput. Biol. 6 no. 7, 1000851.
Jonathan E. Taylor, Joshua R. Loftus, and Ryan J. Tibshirani, Inference in adaptive regression via the Kac-Rice formula, Ann. Statist. 44 (2016), no. 2, 743–770. MR 3476616, DOI 10.1214/15-AOS1386
Liming Wang and Eduardo D. Sontag, On the number of steady states in a multiple futile cycle, J. Math. Biol. 57 (2008), no. 1, 29–52. MR 2393207, DOI 10.1007/s00285-007-0145-z
N. Donald Ylvisarer, The expected number of zeros of a stationary Gaussian process, Ann. Math. Statist. 36 (1965), 1043–1046. MR 177458, DOI 10.1214/aoms/1177700077