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

* Auteur correspondant
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.
Keywords :
Type de document :
Rapport
2013, pp.16
Domaine :

Littérature citée [14 références]

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00871315
Contributeur : Pascal Koiran <>
Soumis le : mercredi 23 juillet 2014 - 10:53:21
Dernière modification le : mardi 24 avril 2018 - 13:52:35
Document(s) archivé(s) le : mardi 25 novembre 2014 - 14:00:38

### Fichiers

dense_sparse.corrections.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

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

### Citation

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. 2013, pp.16. 〈ensl-00871315v2〉

### Métriques

Consultations de la notice

## 141

Téléchargements de fichiers