On homotopy types of limits of semi-algebraic sets and additive complexity of polynomials
A polynomial \(P\in{\mathbb R}[X_1,\ldots,X_k]\) has \textit{additive complexity} at most \(a\in{\mathbb N}\) if there exists a straight line program allowing multiplication, division, and addition of polynomials which computes \(P\) by using at most \(a\) additions (and any number of multiplications and divisions) For a pair \(k, a\in{\mathbb N},\) denote with \({\mathcal A}_{k,a}\) the family of ordered finite lists \((P_1,\ldots, P_s)\) of polynomials in \({\mathbb R}[X_1,\ldots, X_k]\) with the sum of the additive complexities of the \(P_i\) being bounded by \(a.\)NEWLINENEWLINEThe main result of this paper is the following: \textit{The number of homotopy types of ordered lists in \({\mathcal A}_{k,a}\) does not exceed }\(2^{(k+a)^{{\mathcal O}(1)}}\). This result was conjectured in [\textit{S. Basu} and \textit{N. Vorobjov}, J. Lond. Math. Soc., II. Ser. 76, No. 3, 757--776 (2007; Zbl 1131.14060)], where the result was proven for elements in \({\mathcal A}^{\text{div-free}}_{k,a},\) the subset of \({\mathcal A}_{k,a}\) of polynomials having additive complexity at most \(a\) when the straight line program which computes them only allows multiplications and additions.NEWLINENEWLINETo prove this new result, the authors have to study Hausdorff limits of one-parameter semi-algebraic families. They show in the paper that the topological complexity (for instance the Betti numbers) of these limits are well controlled, and they prove that the number of homotopy types of such limits can be bounded singly exponentially in terms of the format of the formulas defining the family.
scientific article; zbMATH DE number 6363146