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

DOI10.1007/S00493-009-2357-XzbMATH Open1212.14005arXivmath/0603256OpenAlexW2058434068WikidataQ57253833 ScholiaQ57253833MaRDI QIDQ987564FDOQ987564

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

Publication date: 13 August 2010

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Refined bounds on the number of connected components of sign conditions on a variety
• VC dimensions of principal component analysis
• VC density of definable families over valued fields
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• Bounds of Hausdorff measures of tame sets
• Bounds on the number of connected components for tropical prevarieties

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)