Topological complexity and quantitative o-minimality

点击翻译按钮获取中文摘要

AbstractAward: DMS-0245628Principal Investigator: Andrei GabrielovThe principal investigator proposes to investigate thetopological complexity of definable sets in o-minimal structureson the real numbers, in particular, of the real semialgebraic andsub-Pfaffian sets. This research will be based on the new toolsfor computing homology of such sets: a spectral sequenceassociated with a surjective map, and the relative closureoperation on one-parametric families. The results will beapplied to the problems of quantitative o-minimality: thecomplexity of topological, geometric and algebraic operations ondefinable sets in o-minimal extensions of the real numbers. Theresults of the proposed research will advance quantitative andalgorithmic aspects of the o-minimal theory. As a broaderimpact, these results will provide a theoretical basis forcomputer algorithms for operations on sparse polynomials,exponential and trigonometric functions.Objects defined by systems of algebraic equations andinequalities (semi-algebraic sets) appear in many areas ofmathematics and its applications, such as control theory,robotics, and computer-aided design. Understanding thecomplexity of operations on such objects is crucial fordeveloping efficient computer algorithms. In many practicallyimportant cases, polynomials in the definition of asemi-algebraic set are sparse, i.e., have few non-zerocoefficients. Sparsity is not preserved by many naturaloperations, such as projection to a subspace or closure. Theresults of the proposed research would allow one to evaluate thecomplexity of operations on semi-algebraic sets in terms of thecomplexity of some auxiliary sets, retaining sparsity of theoriginal polynomials. This may drastically improve upper boundson the complexity of such operations, leading to more efficient,faster computer algorithms.