FoCM 2014 conference
Workshop A6 - Real Number Complexity
December 12, 17:30 ~ 18:00 - Room C11
On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem
Pascal Koiran
Ecole Normale Supérieure de Lyon, France - pascal.koiran@ens-lyon.fr
Consider a system of two polynomial equations in two variables: $$F(X,Y)=G(X,Y)=0$$ where $F \in \Bbb{R}[X,Y]$ has degree $d \geq 1$ and $G \in \Bbb{R}[X,Y]$ has $t$ monomials. We show that the system has only $O(d^3t+d^2t^3)$ real solutions when it has a finite number of real solutions. This is the first polynomial bound for this problem. In particular, the bounds coming from the theory of fewnomials are exponential in $t$, and count only nondegenerate solutions. More generally, we show that if the set of solutions is infinite, it still has at most $O(d^3t+d^2t^3)$ connected components.
By contrast, the following question seems to be open: if $F$ and $G$ have at most $t$ monomials, is the number of (nondegenerate) solutions polynomial in $t$?
The authors' interest for these problems was sparked by connections between lower bounds in algebraic complexity theory and upper bounds on the number of real roots of ``sparse like'' polynomials.
Joint work with Natacha Portier and Sébastien Tavenas.