An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions

DOI10.1007/S00493-009-2357-XMaRDI QIDQ987564zbMATH OpenOpenAlexWikidataFDO

Authors Saugata Basu, Richard Pollack, Marie-Françoise Roy

Publication date 13 August 2010

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603256

zbMATH Keywords

semi-algebraically connected components

Mathematics Subject Classification ID

Topology of real algebraic varieties (14P25) Modular representations and characters (20C20) Semialgebraic sets and related spaces (14P10) Rings and algebras of continuous, differentiable or analytic functions (46E25)

Abstract: We prove an asymptotically tight bound (asymptotic with respect to the number of polynomials for fixed degrees and number of variables) on the number of semi-algebraically connected components of the realizations of all realizable sign conditions of a family of real polynomials. More precisely, we prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of a family of $s$ polynomials in $R[X_1,\mathrm{...},X_k]$ whose degrees are at most $d$ is bounded by [ frac{(2d)^k}{k!}s^k + O(s^{k-1}). ] This improves the best upper bound known previously which was [ {1/2}frac{(8d)^k}{k!}s^k + O(s^{k-1}). ] The new bound matches asymptotically the lower bound obtained for families of polynomials each of which is a product of generic polynomials of degree one.

Recommendations

• Refined bounds on the number of connected components of sign conditions on a variety
• scientific article; zbMATH DE number 1262423
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• Publication:3202245
• scientific article; zbMATH DE number 203206

Cites work

• scientific article; zbMATH DE number 1027930 (Why is no real title available?)
• scientific article; zbMATH DE number 863501 (Why is no real title available?)
• Algorithms in real algebraic geometry
• Homology theory for locally compact spaces
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Betti Numbers of Real Varieties
• On the Betti numbers of sign conditions
• On the homology groups of Stein spaces
• On the number of cells defined by a family of polynomials on a variety
• On the number of sets definable by polynomials
• On the number of zero-patterns of a sequence of polynomials
• Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
• There are asymptotically far fewer polytopes than we thought
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)

Cited in

(8)

• VC density of definable families over valued fields
• Refined bounds on the number of connected components of sign conditions on a variety
• VC dimensions of principal component analysis
• Bounds of Hausdorff measures of tame sets
• Bounds on the number of connected components for tropical prevarieties
• scientific article; zbMATH DE number 203206 (Why is no real title available?)
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• scientific article; zbMATH DE number 4177285 (Why is no real title available?)

This page was built for publication: An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987564)