The number of roots of a lacunary bivariate polynomial on a line (Q1030257): Difference between revisions

A direct consequence of Descartes' rule of signs is that the number of real roots of a (sparse) univariate polynomial \(f \in {\mathbb R}[x]\) with \(t\) non-zero terms is bounded by \(2t-1\). In this paper, the author proves a generalization of this theorem, namely that a (sparse) bivariate polynomial \(f \in {\mathbb R}[x,y]\) with \(t\) non-zero terms restricted to a real line \(y = ax+b\), either has at most \(6t-4\) zeros or vanishes over the whole line. The author's result can also be seen as a refinement, to the case where the trinomial is a linear polynomial, of a result of \textit{T.-Y. Li, J. M. Rojas} and \textit{X. Wang} [Discrete Comput. Geom. 30, No. 3, 379--414 (2003; Zbl 1059.14071)] which shows that the number of common isolated or non-degenerate roots of a trinomial and a polynomial with at most \(t\) non-zero terms (both in \({\mathbb R}[x,y]\)), \(t\geq 3\), is bound above by \(2^t-2\). From this result, the author derives an alternative polynomial-time algorithm for checking whether a given linear form \(y-ax-b \in K[x,y]\) divides a polynomial \(f \in K[x,y]\), \(K\) a real number field. Other, more general, algorithms for this purpose can be found in \textit{E. Kaltofen} and \textit{P. Koiran} [ Proc. ISSAC'05, ACM, New York, 208--215 (2005), ISSAC 2006, ACM, New York, 162--168 (2006)] and \textit{M. Avendaño, T. Krick} and \textit{M. Sombra} [J. Complexity 23, No. 2, 193--216 (2007; Zbl 1170.12004)]. The algorithm in the current paper is bit-wise polynomial in the number of non-zero terms of \(f\), the logarithm of the degree of \(f\), the degree of the extension \(K/{\mathbb Q}\) and the logarithmic height of \(a,b\) and \(f\).