Abstract:
We prove that a polynomial f ∈ R [x, y] with t non-zero terms, restricted to a real line y = a x + b, either has at most 6 t - 4 zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y - a x - b ∈ K [x, y] divides a lacunary polynomial f ∈ K [x, y], where K is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f, in the logarithm of the degree of f, in the degree of the extension K / Q and in the logarithmic height of a, b and f. © 2009 Elsevier Ltd. All rights reserved.
Referencias:
- Avendaño, M., Krick, T., Sombra, M., Factoring bivariate lacunary polynomials (2007) Journal of Complexity, 23, pp. 193-216
- Bates, D.J., Bihan, F., Sottile, F., Bounds on the number of real solutions to polynomial equations (2007) International Mathematics Research Notices, (114), pp. 114-117
- Bihan, F., Sottile: New fewnomial upper bounds from Gale dual polynomial systems (2007) Moscow Mathematics Journal, 7 (3), pp. 387-407
- Cucker, F., Koiran, P., Smale, S., A polynomial time algorithm for diophantine equations in one variable (1999) JSC, 27 (1), pp. 21-29
- Gomez, J., Niles, A., Rojas, J.M., 2007. New complexity bounds for certain real fewnomial zero sets (extended abstract). In: Effective Methods in Algebraic Geometry MEGA'07; Haas, B., A simple counter-example to Koushnirenko's conjecture (2002) Beiträge zur Algebra und Geometrie, 43 (1), pp. 1-8
- Hindry, M., Silverman, J.H., (2000) Diophantine Geometry: An Introduction, , Springer-Verlag, New York
- Kaltofen, E., Koiran, P., On the complexity of factoring bivariate supersparse (lacunary) polynomials ISSAC'05 Proc. 2005 Internat. Symp. Symbolic Algebraic Comput, pp. 208-215
- Kaltofen, E., Koiran, P., Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields ISSAC'06 Proc. 2006 Internat. Symp. Symbolic Algebraic Comput, pp. 162-168
- Khovanskii, A., (1991) Fewnomials, , AMS press, Providence, Rhode Island
- Landau, S., Factoring polynomials over algebraic number fields (1985) SIAM Journal on Computing, 14, pp. 184-195
- Lenstra, A.K., Lenstra, H.W., Lovasz, L., Factoring polynomials with rational coefficients (1982) Mathematishe Annalen, 261, pp. 515-534
- Lenstra, H.W., Finding small degree factors of lacunary polynomials (1999) Number Theory in Progress, 1, pp. 267-276
- Li, T.Y., Rojas, J.M., Wang, X., Counting real connected components of trinomial curves intersections and m-nomial hypersurfaces (2003) Discrete and Computational Geometry, 30 (3), pp. 379-414
- Perruci, D., Some bounds for the number of connected components of real zero sets of sparse polynomials (2005) Discrete and Computational Geometry, 34 (3), pp. 475-495
Citas:
---------- APA ----------
(2009)
. The number of roots of a lacunary bivariate polynomial on a line. Journal of Symbolic Computation, 44(9), 1280-1284.
http://dx.doi.org/10.1016/j.jsc.2008.02.016---------- CHICAGO ----------
Avendaño, M.
"The number of roots of a lacunary bivariate polynomial on a line"
. Journal of Symbolic Computation 44, no. 9
(2009) : 1280-1284.
http://dx.doi.org/10.1016/j.jsc.2008.02.016---------- MLA ----------
Avendaño, M.
"The number of roots of a lacunary bivariate polynomial on a line"
. Journal of Symbolic Computation, vol. 44, no. 9, 2009, pp. 1280-1284.
http://dx.doi.org/10.1016/j.jsc.2008.02.016---------- VANCOUVER ----------
Avendaño, M. The number of roots of a lacunary bivariate polynomial on a line. J. Symb. Comput. 2009;44(9):1280-1284.
http://dx.doi.org/10.1016/j.jsc.2008.02.016