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

详细信息    查看全文

• 作者：Pascal Koiran ; Natacha Portier ; Sébastien Tavenas
• 关键词：Real algebraic geometry ; Fewnomials ; Wronskian
• 刊名：Discrete and Computational Geometry
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：53
• 期：1
• 页码：48-63
• 全文大小：210 KB
• 参考文献：1. Avenda?o, M.: The number of roots of a lacunary bivariate polynomial on a line. J. Symb. Comput. 44(9), 1280-284 (2009) CrossRef
  2. Basu, S., Pollack, R.D., Roy, M.-F.: Algorithms in Real Algebraic Geometry, vol. 10. Springer, Berlin (2006)
  3. Bihan, F., Sottile, F.: New fewnomial upper bounds from Gale dual polynomial systems. Mosc. Math. J. 7(3), 387-07 (2007)
  4. Bihan, F., Sottile, F.: Fewnomial bounds for completely mixed polynomial systems. Adv. Geom. 11(3), 541-56 (2011) CrossRef
  5. Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998) CrossRef
  6. Borodin, A., Cook, S.: On the number of additions to compute specific polynomials. SIAM J. Comput. 5(1), 146-57 (1976) CrossRef
  7. Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Automata Theory and Formal Languages. 2nd GI Conference Kaiserslautern, pp. 134-83. Springer, New York (1975)
  8. Grenet, B., Koiran, P., Portier, N., Strozecki, Y.: The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent. In: Proceedings of FSTTCS. http://arxiv.org/abs/1107.1434 (2011)
  9. Grigoriev, D.: Notes of the Scientific Seminars, LOMI, vol. 118, pp. 25-2 (1982)
  10. Khovanski?, A.G.: Fewnomials. Translations of Mathematical Monographs. American Mathematical Society, Providence (1991)
  11. Koiran, P.: Shallow circuits with high-powered inputs. In: Proceedings of the Second Symposium on Innovations in Computer Science (ICS). http://arxiv.org/abs/1004.4960 (2011)
  12. Koiran, P., Portier, N., Tavenas, S.: A Wronskian approach to the real \(\tau \) -conjecture. Effective Methods in Algebraic Geometry (MEGA). http://arxiv.org/abs/1205.1015 (2013)
  13. Kushnirenko, A.: Letter to Frank Sottile. http://www.math.tamu.edu/sottile/research/pdf/Kushnirenko (2008)
  14. Li, T.-Y., Rojas, J.M., Wang, X.: Counting real connected components of trinomial curve intersections and m-nomial hypersurfaces. Discrete Comput. Geom. 30(3), 379-14 (2003) CrossRef
  15. Risler, J.-J.: Additive complexity and zeros of real polynomials. SIAM J. Comput. 14, 178-83 (1985) CrossRef
  16. Sottile, F.: Real Solutions to Equations from Geometry. University Lecture Series. American Mathematical Society, Providence, RI (2011)
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444

文摘

Consider a system of two polynomial equations in two variables: $$\begin{aligned} F(X,Y)=G(X,Y)=0, \end{aligned}$$ where \(F \in \mathbb {R}[X,Y]\) has degree \(d \ge 1\) and \(G \in \mathbb {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 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)\) connected components. By contrast, the following question seems to be open: if \(F\) and \(G\) have at most \(t\) monomials, is the number of (non-degenerate) 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.