HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem

Pascal Koiran 1, 2, * Natacha Portier 1 Sébastien Tavenas 1
* Corresponding author
2 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Consider a system of two polynomial equations in two variables: $$F(X,Y)=G(X,Y)=0$$ where $F \in \rr[X,Y]$ has degree $d \geq 1$ and $G \in \rr[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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

Contributor : Pascal Koiran Connect in order to contact the contributor
Submitted on : Wednesday, July 23, 2014 - 10:53:21 AM
Last modification on : Saturday, September 11, 2021 - 3:17:29 AM
Long-term archiving on: : Tuesday, November 25, 2014 - 2:00:38 PM


Files produced by the author(s)


  • HAL Id : ensl-00871315, version 2
  • ARXIV : 1310.2447



Pascal Koiran, Natacha Portier, Sébastien Tavenas. On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem. Discrete and Computational Geometry, Springer Verlag, 2015, pp.16. ⟨ensl-00871315v2⟩



Record views


Files downloads