×

On projections of semi-algebraic sets defined by few quadratic inequalities. (English) Zbl 1137.14042

Summary: Let \(S \subset \mathbb R^{k + m}\) be a compact semi-algebraic set defined by \(P_{1}\geq 0,, P_{\ell}\geq 0\), where \(P_{i}\in \mathbb R[X_{1},\ldots, X_{k}, Y_{1},\ldots, Y_{m}]\), and deg\((P_{i})\leq 2, 1\leq i \leq \ell\). Let \(\pi\) denote the standard projection from \(\mathbb R^{k + m}\) onto \(\mathbb R^{m}\). We prove that for any \(q >0\), the sum of the first \(q\) Betti numbers of \(\pi (S)\) is bounded by \((k + m)^{O (q \ell)}\). We also present an algorithm for computing the first \(q\) Betti numbers of \(\pi (S)\), whose complexity is \((k+m)^{2^{O(q\ell)}}\). For fixed \(q\) and \(\ell\), both the bounds are polynomial in \(k + m\).

MSC:

14P10 Semialgebraic sets and related spaces
68W30 Symbolic computation and algebraic computation

References:

[1] Barvinok, A.I.: Feasibility testing for systems of real quadratic equations. Discret. Comput. Geom. 10, 1-13 (1993) · Zbl 0812.12006 · doi:10.1007/BF02573959
[2] Barvinok, A.I.: On the Betti numbers of semi-algebraic sets defined by few quadratic inequalities. Math. Z. 225, 231-244 (1997) · Zbl 0919.14034 · doi:10.1007/PL00004307
[3] Basu, S.: On bounding the Betti numbers and computing the Euler characteristics of semi-algebraic sets. Discret. Comput. Geom. 22, 1-18 (1999) · Zbl 0973.14033 · doi:10.1007/PL00009443
[4] Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43, 1002-1045 (1996) · Zbl 0885.68070 · doi:10.1145/235809.235813
[5] Basu, S.: On different bounds on different Betti numbers. Discret. Comput. Geom. 30(1), 65-85 (2003) · Zbl 1073.14556
[6] Basu, S.: Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities, Found. Comput. Math. (2006, in press)
[7] Basu, S.: Single exponential time algorithm for computing the first few Betti numbers of semi-algebraic sets. J. Symb. Comput. 41(10), 1125-1154 (2006) · Zbl 1126.14065 · doi:10.1016/j.jsc.2006.07.001
[8] Basu, S.: Efficient algorithm for computing the Euler-Poincaré characteristic of semi-algebraic sets defined by few quadratic inequalities. Comput. Complex. 15, 236-251 (2006) · Zbl 1103.14032 · doi:10.1007/s00037-006-0214-5
[9] Basu, S., Pollack, R., Roy, M.-F.: Computing the first Betti number and the connected components of semi-algebraic sets. Found. Comput. Math. (2007, to appear) · Zbl 1192.14003
[10] Basu, S., Pollack, R., Roy, M.-F.: In: Algorithms in Real Algebraic Geometry, 2nd edn. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006) · Zbl 1102.14041
[11] Bredon, G.E.: Sheaf Theory. Springer, Berlin (1996)
[12] Deligne, P.: Théorie de Hodge III. Publ. Math. IHES 44, 5-77 (1974) · Zbl 0237.14003
[13] Dugger, D., Isaksen, D.: Topological hypercovers and A1-realizations. Math. Z. 246, 667-689 (2004) · Zbl 1055.55016 · doi:10.1007/s00209-003-0607-y
[14] Gabrielov, A., Vorobjov, N., Zell, T.: Betti numbers of semi-algebraic and sub-Pfaffian sets. J. Lond. Math. Soc. 69(2), 27-43 (2004) · Zbl 1087.14038 · doi:10.1112/S0024610703004939
[15] Gabrielov, A.: Counter-examples to quantifier elimination for fewnomial and exponential expressions. Preprint, available at http://www.math.purdue.edu/ agabriel/preprint.html · Zbl 1149.14044
[16] Grigor’ev, D., Pasechnik, D.V.: Polynomial time computing over quadratic maps I. Sampling in real algebraic sets. Comput. Complex. 14, 20-52 (2005) · Zbl 1082.14065 · doi:10.1007/s00037-005-0189-7
[17] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002) · Zbl 1044.55001
[18] Houston, K., An introduction to the image computing spectral sequence, Liverpool, 1996, Cambridge · Zbl 0964.58029
[19] Khovansky, A.G.: Fewnomials. American Mathematical Society, Providence (1991) · Zbl 0728.12002
[20] McCleary, J.: A User’s Guide to Spectral Sequences, 2nd edn. Cambridge Studies in Advanced Mathematics (2001) · Zbl 0959.55001
[21] Murray, M.: Bundle gerbes. J. Lond. Math. Soc. 54, 403-416 (1996) · Zbl 0867.55019
[22] Renegar, J.: On the computational complexity and geometry of the first order theory of the reals. J. Symb. Comput. 13, 255-352 (1992) · Zbl 0763.68042 · doi:10.1016/S0747-7171(10)80003-3
[23] Saint-Donat, B., Techniques de descente cohomologique, No. 270, 83-162 (1972), Berlin · Zbl 0317.14007 · doi:10.1007/BFb0061321
[24] Vassiliev, V.: In: Complements of Discriminants of Smooth Maps: Topology and Applications. Translations of Mathematical Monographs, vol. 98. American Mathematical Society, Providence (1992) · Zbl 0762.55001
[25] Zell, T.: Topology of definable Hausdorff limits. Discret. Comput. Geom. 33, 423-443 (2005) · Zbl 1068.14062 · doi:10.1007/s00454-004-1112-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.