Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

On the Betti numbers of sign conditions


Authors: Saugata Basu, Richard Pollack and Marie-Françoise Roy
Journal: Proc. Amer. Math. Soc. 133 (2005), 965-974
MSC (2000): Primary 14P10; Secondary 14P25
DOI: https://doi.org/10.1090/S0002-9939-04-07629-4
Published electronically: November 19, 2004
MathSciNet review: 2117195
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let ${\mbox{\rm R}}$ be a real closed field and let ${\mathcal Q}$ and ${\mathcal P}$ be finite subsets of ${\mbox{\rm R}}[X_1,\ldots,X_k]$ such that the set ${\mathcal P}$ has $s$ elements, the algebraic set $Z$ defined by $\bigwedge_{Q \in {\mathcal Q}}Q=0$ has dimension $k'$ and the elements of ${\mathcal Q}$ and ${\mathcal P}$ have degree at most $d$. For each $0 \leq i \leq k',$ we denote the sum of the $i$-th Betti numbers over the realizations of all sign conditions of ${\mathcal P}$ on $Z$ by $b_i({\mathcal P},{\mathcal Q})$. We prove that

\begin{displaymath}b_i({\mathcal P},{\mathcal Q}) \le\sum_{j=0}^{k' - i} {s \choose j} 4^{j} d(2d-1)^{k-1}. \end{displaymath}

This generalizes to all the higher Betti numbers the bound ${s \choose k'}O(d)^k$ on $b_0({\mathcal P},{\mathcal Q})$. We also prove, using similar methods, that the sum of the Betti numbers of the intersection of $Z$ with a closed semi-algebraic set, defined by a quantifier-free Boolean formula without negations with atoms of the form $P \geq 0$ or $P\leq 0$ for $P\in {\mathcal P}$, is bounded by

\begin{displaymath}\sum_{i = 0}^{k'}\sum_{j = 0}^{k' - i} {s \choose j} 6^{j} d(2d-1)^{k-1}, \end{displaymath}

making the bound $s^{k'} O(d)^k$ more precise.


References [Enhancements On Off] (What's this?)

  • 1. S. BASU Different bounds on the Different Betti Numbers of Semi-algebraic Sets, Discrete and Computational Geometry, 30:65-85, 2003. MR 1991587 (2004f:14082)
  • 2. S. BASU On Bounding the Betti Numbers and Computing the Euler Characteristics of Semi-algebraic Sets, Discrete and Computational Geometry, 22:1-18, 1999. MR 1692627 (2000d:14061)
  • 3. S. BASU, R. POLLACK, M.-F. ROY On the number of cells defined by a family of polynomials on a variety, Mathematika , Vol 43, 120-126, 1996. MR 1401711 (97h:14076)
  • 4. S. BASU, R. POLLACK, M.-F. ROY Algorithms in real algebraic geometry. Algorithms and Computation in Mathematics, Vol 10, Springer-Verlag (2003). MR 1998147
  • 5. J. BOCHNAK, M. COSTE, M.-F. ROY Real algebraic geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, Bd. 36, Berlin : Springer-Verlag (1998).
  • 6. R. M. HARDT Semi-algebraic Local Triviality in Semi-algebraic Mappings Amer. J. Math. 102, 291-302 (1980). MR 0564475 (81d:32012)
  • 7. O. A. OLEINIK, I. B. PETROVSKII On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13, 389-402, (1949). MR 0034600 (11:613h)
  • 8. J. MILNOR On the Betti numbers of real varieties, Proc. AMS 15, 275-280, (1964). MR 0161339 (28:4547)
  • 9. E. H. SPANIER Algebraic Topology, McGraw-Hill Book Company, 1966. MR 0210112 (35:1007)
  • 10. R. THOM Sur l'homologie des variétés algébriques réelles, Differential and Combinatorial Topology, Ed. S.S. Cairns, Princeton Univ. Press, 255-265, (1965). MR 0200942 (34:828)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 14P10, 14P25

Retrieve articles in all journals with MSC (2000): 14P10, 14P25


Additional Information

Saugata Basu
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Email: saugata@math.gatech.edu

Richard Pollack
Affiliation: Courant Institute of Mathematical Sciences, New York University, New York, New York 10012
Email: pollack@cims.nyu.edu

Marie-Françoise Roy
Affiliation: IRMAR (URA CNRS 305), Université de Rennes, Campus de Beaulieu 35042 Rennes cedex, France
Email: mfroy@maths.univ-rennes1.fr

DOI: https://doi.org/10.1090/S0002-9939-04-07629-4
Keywords: Betti numbers, sign conditions, semi-algebraic sets
Received by editor(s): July 3, 2002
Received by editor(s) in revised form: October 10, 2003
Published electronically: November 19, 2004
Additional Notes: The first author was supported in part by NSF grant CCR-0049070 and an NSF Career Award 0133597.
The second author was supported in part by NSA grant MDA904-01-1-0057 and NSF grants CCR-9732101 and CCR-0098246.
Communicated by: Michael Stillman
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society