On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem

Consider a system of two polynomial equations in two variables: $$\begin{aligned} F(X,Y)=G(X,Y)=0, \end{aligned}$$F(X,Y)=G(X,Y)=0,where $$F \in \mathbb {R}[X,Y]$$F?R[X,Y] has degree $$d \ge 1$$d?1 and $$G \in \mathbb {R}[X,Y]$$G?R[X,Y] has $$t$$t monomials. We show that the system has only $$O(d^3t+d^2t^3)$$O(d3t+d2t3) 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$$t, and count only non-degenerate solutions. More generally, we show that if the set of solutions is infinite, it still has at most $$O(d^3t+d^2t^3)$$O(d3t+d2t3) connected components. By contrast, the following question seems to be open: if $$F$$F and $$G$$G have at most $$t$$t monomials, is the number of (non-degenerate) solutions polynomial in $$t$$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.