Campuses:

New fewnomial upper bounds from Gale dual polynomial<br/><br/>systems

Thursday, September 21, 2006 - 9:30am - 10:20am
EE/CS 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, thereby showing that
the complexity
of real solutions to a polynomial system depends upon the number
of monomials
and not the degree. This fundamental finiteness result in real
algebraic
geometry was proven by induction on the number of monomials and
the bound is
unrealistically large.

I will report on joint work with Frederic Bihan on a new
fewnomial bound which
is substantially lower than Khovanskii's bound. This bound is
obtained by
first reducing a given system to a Gale system, which comes from
the Gale dual
to the exponent vectors in the original 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.
MSC Code: 
52B35
Keywords: