On homotopy types of limits of semi-algebraic sets and additive complexity of polynomials
type: Item
instance of: scholarly article
title: On homotopy types of limits of semi-algebraic sets and additive complexity of polynomials
zbMATH Open document ID: 1333.14056
DOI: 10.4171/JEMS/468
author: Sal Barone
author: Saugata Basu
published in: Journal of the European Mathematical Society (JEMS)
publication date: 2014-10-31T00:00:00Z
full work available at URL: https://arxiv.org/abs/1102.0080
reviewed by: Carlos D'Andrea
Mathematics Subject Classification ID: 14P10
Mathematics Subject Classification ID: 14P25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 6363146
zbMATH Keywords: semi-algebraic sets
zbMATH Keywords: additive complexity
zbMATH Keywords: homotopy types
zbMATH Keywords: Hausdorff limit
MaRDI profile type: MaRDI publication profile
arXiv ID: 1102.0080
cites work: On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
cites work: On the number of topological types occurring in a parameterized family of arrangements
cites work: Q5290253
cites work: Algorithms in real algebraic geometry
cites work: On the number of homotopy types of fibres of a definable map
cites work: Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
cites work: Q3996250
cites work: Poset fiber theorems
cites work: Q3770650
cites work: On the Number of Additions to Compute Specific Polynomials
cites work: Q4233742
cites work: Betti numbers of semialgebraic sets defined by quantifier-free formulae
cites work: BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
OpenAlex ID: W2963477322
review text: 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.
description: scientific article; zbMATH DE number 6363146