Consider a system of polynomial equations with parametric coefficients over an arbitrary ground field. We show that the variety of parameters can be represented as a union of strata. For values of the parameters from each stratum, the solutions of the system are given by algebraic formulas depending only on this stratum. Each stratum is a quasiprojective algebraic variety with degree bounded from above by a subexponential function in the size of the input data. The number of strata is also subexponential in the size of the input data. Thus, here we avoid double exponential upper bounds on the degrees and solve a long-standing problem
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Ayad, “Complexity of solving parametric polynomial systems,” Zap. Nauchn. Semin. POMI, 387, 5–52 (2011).
A. L. Chistov, “Polynomial complexity algorithm for factoring polynomials and constructing components of a variety in subexponential time,” J. Sov. Math., 34, No. 4, 1838–1882 (1986).
A. L. Chistov, “An improvement of the complexity bound for solving systems of polynomial equations,” Zap. Nauchn. Semin. POMI, 390, 299–306 (2011).
A. L. Chistov, “A bound for the degree of a system of equations determining the variety of reducible polynomials,” St. Petersburg Math. J., 24, No. 3, 513–528 (2013).
A. L. Chistov, “Computations with parameters: a theoretical background,” J. Math. Sci., 215, No. 6, 769–781 (2016).
A. L. Chistov, “Efficient absolute factorization polynomials with parametric coefficients,” J. Math. Sci., 224, No. 2, 360–384 (2017).
A. L. Chistov, “Efficient algorithms for factoring polynomials and their applications,” Thesis for the degree of Doctor of Physical and Mathematical Sciences, Leningrad (1987).
A. L. Chistov, “Systems with parameters, or efficiently solving systems of polynomial equations 33 years later. I,” J. Math. Sci., 232, No. 2, 177–203 (2018).
A. L. Chistov, H. Fournier, L. Gurvits, and P. Koiran, “Vandermonde matrices, NP-completeness, and transversal subspaces,” Found. Comput. Math., 3, No. 4, 421–427 (2003).
D. Lazard and F. Rouillier, “Solving parametric polynomial systems,” J. Symbolic Comput., 42, No. 6, 636–667 (2007).
D. Lazard, “Résolution des systémes d’équations algébriques,” Theoret. Comput. Sci., 15, 77–110 (1981).
D. Lazard, “Commutative algebra and computer algebra,” Lect. Notes Comput. Sci., 144, 40–48 (1983).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 468, 2018, pp. 138–176.
Rights and permissions
About this article
Cite this article
Chistov, A.L. Systems with Parameters, or Efficiently Solving Systems of Polynomial Equations 33 Years Later. II. J Math Sci 240, 594–616 (2019). https://doi.org/10.1007/s10958-019-04378-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-019-04378-8