# Optimal fewnomial bounds from Gale dual polynomial systems

Wednesday, April 4, 2007 - 11:15am - 12:15pm

Keller 3-180

Frank Sottile (Texas A & M University)

In 1980, Askold Khovanskii established his fewnomial bound for the number of real solutions to a system of polynomials, showing that the complexity of the set of real solutions to a system of polynomials depends upon the number of monomials and not on the degree. This fundamental finiteness result in real algebraic geometry is believed to be unrealistically large.

I will report on joint work with Frederic Bihan on a new fewnomial bound which is substantially lower than Khovanskii's bound and asymptotically optimal. This bound is obtained by first reducing a given system to a Gale system, and then bounding the number of solutions to a Gale system. Like Khovanskii's bound, this bound is the product of an exponential function and a polynomial in the dimension, with the exponents in both terms depending upon the number of monomials. In our bound, the exponents are smaller than in Khovanskii's.

I will also dicuss a continuation of this work with J Maurice Rojas in which we show that this fewnomial bound is optimal, in an asymptotic sense. We also use it to establish a new and significantly smaller bound for the total Betti number of a fewnomial hypersurface. Conditional independence models for Gaussian random variables are algebraic varieties in the cone of positive definite matrices. We explore the geometry of these varieties in the case of Bayesian networks.

I will report on joint work with Frederic Bihan on a new fewnomial bound which is substantially lower than Khovanskii's bound and asymptotically optimal. This bound is obtained by first reducing a given system to a Gale system, and then bounding the number of solutions to a Gale system. Like Khovanskii's bound, this bound is the product of an exponential function and a polynomial in the dimension, with the exponents in both terms depending upon the number of monomials. In our bound, the exponents are smaller than in Khovanskii's.

I will also dicuss a continuation of this work with J Maurice Rojas in which we show that this fewnomial bound is optimal, in an asymptotic sense. We also use it to establish a new and significantly smaller bound for the total Betti number of a fewnomial hypersurface. Conditional independence models for Gaussian random variables are algebraic varieties in the cone of positive definite matrices. We explore the geometry of these varieties in the case of Bayesian networks.