Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I (Q1661547)

Consider a polynomial system in the variables \(X_0,\dots,X_n\) whose coefficients are unknown, unmeasurable, or otherwise unspecified. This situation is very frequent in applied algebra. To model it, one replaces the coefficients by indeterminate ``parameters'' \(a_1,\dots,a_\nu\) and studies the dependency of the solutions of the polynomial system on the parameter values. One can show that parameter space subdivides into strata (also defined by polynomial equations) where the formulas for the solutions of the original systems only depend on the stratum. The present paper discusses this theory and then focusses on the complexity of the resulting decompositions of parameter space. The main results are a sub-exponential bound on the degree of the strata (as quasi-projective varieties) and another sub-exponential bound on the number of strata. The paper is the first part of a series of papers by the same author on this fundamental problem, its history, and its solution.