scientific article; zbMATH DE number 1305293
A motivation to the paper is the following question of \textit{F. Cucker, P. Koiran} and \textit{S. Smale} [J. Symb. Comput. 27, 21-29 (1999; Zbl 0920.11085)]: can one find all rational zeros of a sparse integer polynomial \(\sum _{i} a_i x^i\) (that given by the list of pairs \((i, a_i)\) with \(a_i\neq 0\)) in polynomial time ? The author shows that this is indeed the case. More generally, there is a deterministic algorithm such that for a sparse polynomial \(f\) with coefficients in a number field \(K\), and a positive integer \(d\), the algorithm finds all monic irreducible factors of \(f\) (in \(K[x]\)) of degree at most \(d\), and their multiplicities, in time at most \((l+d)^c\), where \(l\) denotes the ``length of the input data, and \(c\) is a positive absolute and effectively computable constant. The precise definition of the length of the input data is given in his earlier paper [Bull. Am. Math. Soc. 26, 211-244 (1992; Zbl 0759.11046)], and it is essentially the number of bits needed to spell out the data in binary. There are also several auxiliary algorithms, one of which finds the cyclotomic factors of \(f\). The key proposition uses the uniform lower bound on the Mahler measure, \(\log M(\alpha)\geq 2\big(\log (3d)\big)^{-3}\), where \(\alpha\) is a non-cyclotomic algebraic number of degree at most \(d\), \(d \geq 2\). For the entire collection see [Zbl 0911.00025].
- Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
- scientific article; zbMATH DE number 1305294
- On the factorization of lacunary polynomials
- scientific article; zbMATH DE number 1852134
- scientific article; zbMATH DE number 681099
- Bounded-degree factors of lacunary multivariate polynomials
- scientific article; zbMATH DE number 1305288
- Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach
- Factors of low individual degree polynomials
- Factors of low individual degree polynomials
- The number of roots of a lacunary bivariate polynomial on a line
- Some speed-ups and speed limits for real algebraic geometry
- Computing sparse multiples of polynomials
- Root separation for trinomials
- Intersection multiplicity of a sparse curve and a low-degree curve
- Sublinear root detection and new hardness results for sparse polynomials over finite fields
- Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
- On testing the divisibility of lacunary polynomials by cyclotomic polynomials
- Sparse bivariate polynomial factorization
- Lacunaryx: computing bounded-degree factors of lacunary polynomials
- On lacunary polynomial perfect powers
- Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
- Diophantine equations with three monomials
- The Diophantine problem for systems of algebraic equations with exponents
- Knapsack and the power word problem in solvable Baumslag–Solitar groups
- Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\)
- Detecting lacunary perfect powers and computing their roots
- Cyclotomic identity testing and applications
- On transcendence of numbers related to Sturmian and Arnoux-Rauzy words
- Transcendence of Hecke-Mahler series
- Factoring sparse polynomials fast
- New bounds on quotient polynomials with applications to exact division and divisibility testing of sparse polynomials
- Algorithms for near solutions to polynomial equations
- Factoring bivariate sparse (lacunary) polynomials
- Computational complexity of sentences over fields
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4252162)
