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 Free Access

Abstract | References | Similar Articles | Additional Information

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.

- 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 https://doi.org/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 https://doi.org/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 https://doi.org/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** - 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 https://doi.org/10.2307/2374240 - I. G. Petrovskiĭ and O. A. Oleĭnik,
*On the topology of real algebraic surfaces*, Izvestiya 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 https://doi.org/10.1090/S0002-9939-1964-0161339-9 - Edwin H. Spanier,
*Algebraic topology*, McGraw-Hill Book Co., New York-Toronto, Ont.-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**

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

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

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