Name
Title | ||
|---|---|---|
On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00454-014-9642-1 | Discrete & Computational Geometry |
Keywords | DocType | Volume |
Real algebraic geometry,Fewnomials,Wronskian | Journal | 53 |
Issue | ISSN | Citations |
1 | 0179-5376 | 0 |
PageRank | References | Authors |
0.34 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Koiran | 1 | 919 | 113.85 |
| Natacha Portier | 2 | 96 | 11.49 |
| Sébastien Tavenas | 3 | 14 | 5.19 |