On the Betti numbers of sign conditions
HTML articles powered by AMS MathViewer
- by Saugata Basu, Richard Pollack and Marie-Françoise Roy
- Proc. Amer. Math. Soc. 133 (2005), 965-974
- DOI: https://doi.org/10.1090/S0002-9939-04-07629-4
- Published electronically: November 19, 2004
- PDF | Request permission
Abstract:
Let $\mathrm {R}$ be a real closed field and let ${\mathcal Q}$ and ${\mathcal P}$ be finite subsets of $\mathrm {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 \[ b_i({\mathcal P},{\mathcal Q}) \le \sum _{j=0}^{k’ - i} {s \choose j} 4^{j} d(2d-1)^{k-1}. \] 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 \[ \sum _{i = 0}^{k’}\sum _{j = 0}^{k’ - i} {s \choose j} 6^{j} d(2d-1)^{k-1}, \] making the bound $s^{k’} O(d)^k$ more precise.References
- Saugata Basu, Different bounds on the different Betti numbers of semi-algebraic sets, Discrete Comput. Geom. 30 (2003), no. 1, 65–85. ACM Symposium on Computational Geometry (Medford, MA, 2001). MR 1991587, DOI 10.1007/s00454-003-2922-9
- S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Discrete Comput. Geom. 22 (1999), no. 1, 1–18. MR 1692627, DOI 10.1007/PL00009443
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On the number of cells defined by a family of polynomials on a variety, Mathematika 43 (1996), no. 1, 120–126. MR 1401711, DOI 10.1112/S0025579300011621
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2003. MR 1998147, DOI 10.1007/978-3-662-05355-3
- J. Bochnak, M. Coste, M.-F. Roy Real algebraic geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, Bd. 36, Berlin : Springer-Verlag (1998).
- Robert M. Hardt, Semi-algebraic local-triviality in semi-algebraic mappings, Amer. J. Math. 102 (1980), no. 2, 291–302. MR 564475, DOI 10.2307/2374240
- I. G. Petrovskiĭ and O. A. Oleĭnik, On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR Ser. Mat. 13 (1949), 389–402 (Russian). MR 0034600
- J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 161339, DOI 10.1090/S0002-9939-1964-0161339-9
- Edwin H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York-Toronto-London, 1966. MR 0210112
- René Thom, Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press, Princeton, N.J., 1965, pp. 255–265 (French). MR 0200942
Bibliographic Information
- Saugata Basu
- Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
- MR Author ID: 351826
- 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
- 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
- © Copyright 2004 American Mathematical Society
- 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
- MathSciNet review: 2117195