Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets

Abstract. A classic result in real algebraic geometry due to Oleinik—Petrovskii, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. We prove better bounds on the individual Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. As a corollary we obtain a polynomial bound on the highest Betti numbers of basic semi-algebraic sets defined by quadratic inequalities.     

On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets

In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S R ^k defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form P _i =0, P _i ≥ 0, P _i ≤ 0, deg(P _i ) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by s ^k' (O(d)) ^k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by s ^k' 2 ^{O(k2 m4)} in case the total number of monomials occurring in the polynomials in is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Received September 9, 1997, and in revised form March 18, 1998, and October 5, 1998.     

Quantitative results on quadratic semi-algebraic sets

Quantitative semi-algebraic geometry studies accurate bounds on topological invariants (such as the Betti numbers) of semi algebraic sets in terms of the number of equations, their degree and their number of variables. For general semialgebric sets, these bounds have an exponential dependance in the number of variables. In contrast, for semi-algebraic sets defined by quadratic equation, the dependance is polynomial in the number of variables. The talk will include a survey of the main results known for general semi-algebraic sets before concentrating on the quadratic case. The lecture will use material from joint work with Saugata Basu and Dimitri Pasechnik.     

Applications of Klee’s Dehn–Sommerville Relations

We use Klee’s Dehn–Sommerville relations and other results on face numbers of homology manifolds without boundary to (i) prove Kalai’s conjecture providing lower bounds on the f-vectors of an even-dimensional manifold with all but the middle Betti number vanishing, (ii) verify Kühnel’s conjecture that gives an upper bound on the middle Betti number of a 2k-dimensional manifold in terms of k and the number of vertices, and (iii) partially prove Kühnel’s conjecture providing upper bounds on other Betti numbers of odd- and even-dimensional manifolds. For manifolds with boundary, we derive an extension of Klee’s Dehn–Sommerville relations and strengthen Kalai’s result on the number of their edges. I. Novik research partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748. E. Swartz research partially supported by NSF grant DMS-0600502.     

Topology of injective endomorphisms of real algebraic sets

Using only basic topological properties of real algebraic sets and regular morphisms we show that any injective regular self-mapping of a real algebraic set is surjective. Then we show that injective morphisms between germs of real algebraic sets define a partial order on the equivalence classes of these germs divided by continuous semi-algebraic homeomorphisms. We use this observation to deduce that any injective regular self-mapping of a real algebraic set is a homeomorphism. We show also a similar local property. All our results can be extended to arc-symmetric semi-algebraic sets and injective continuous arc-symmetric morphisms, and some results to Euler semi-algebraic sets and injective continuous semi-algebraic morphisms.Mathematics Subject Classification (2000):14Pxx, 14A10, 32B10     

Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem

Toda (in SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines in Bull. Am. Math. Soc. (NS) 21(1): 1–46, 1989) has been missing so far. In this paper we formulate and prove a real analogue of Toda’s theorem. Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques, we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry: the problem of deciding sentences in the first-order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result may be of independent interest to researchers in algorithmic semi-algebraic geometry.     

On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety

We extend the lower bounds on the complexity of computing Betti numbers proved in [P. Bürgisser, F. Cucker, Counting complexity classes for numeric computations II: algebraic and semialgebraic sets, J. Complexity 22 (2006) 147–191] to complex algebraic varieties. More precisely, we first prove that the problem of deciding connectedness of a complex affine or projective variety given as the zero set of integer polynomials is PSPACE-hard. Then we prove PSPACE-hardness for the more general problem of deciding whether the Betti number of fixed order of a complex affine or projective variety is at most some given integer.     

Socles of Buchsbaum modules, complexes and posets

The socle of a graded Buchsbaum module is studied and is related to its local cohomology modules. This algebraic result is then applied to face enumeration of Buchsbaum simplicial complexes and posets. In particular, new necessary conditions on face numbers and Betti numbers of such complexes and posets are established. These conditions are used to settle in the affirmative Kühnel's conjecture for the maximum value of the Euler characteristic of a 2k-dimensional simplicial manifold on n vertices as well as Kalai's conjecture providing a lower bound on the number of edges of a simplicial manifold in terms of its dimension, number of vertices, and the first Betti number.     

On voronoi diagrams in theL p-metric in ℝD

We prove upper bounds on the number ofL _p-spheres passing throughD+1 points in general position in ℝ”, and on the sum of the Betti numbers of the intersection of bisectors in theL _p-metric, wherep is an even positive integer. The bounds found do not depend onp. Our result implies that the complexity of Voronoi diagrams (for point sites in general position) in theL _p-metric is bounded for increasingp. The proof for this upper bound involves the techniques of Milnor [12] and Thom [16] for finding a bound on the sum of the Betti numbers of algebraic varieties, but instead of the usual degree of polynomials we use their additive complexity, and apply results of Benedetti and Risler [2], [13]. Furthermore, we prove that inD dimensions and for evenp the number ofL _p-spheres passing throughD+1 points in general position is odd. In particular, combined with results of [8], [9], our results clarify the structure of Voronoi diagrams based on theL _p-metric (with evenp) in three dimensions. For the proof we use the theory of degree of continuous mappings in ℝ^D, which is a tool widely applied in nonlinear analysis [14]. This work was partially supported by Deutsche Forschungsgemeinschaft, Grant K1 655/2-1. A preliminary version of this paper was presented at the 11th Annual Symposium on Theoretical Aspects of Computer Science, France, 1994.     

A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities

In this paper we consider the problem of bounding the Betti numbers, b _i (S), of a semi-algebraic set S⊂ℝ ^k defined by polynomial inequalities P ₁≥0,…,P _s ≥0, where P _i ∈ℝ[X ₁,…,X _k ], s<k, and deg (P _i )≤2, for 1≤i≤s. We prove that for 0≤i≤k−1,

Critical Points of Real Polynomials and Topology of Real Algebraic T-Surfaces

The paper is devoted to a special class of real polynomials, so-called T-polynomials, which arise in the combinatorial version of the Viro theorem. We study the relation between the numbers of real critical points of a given index of a T-polynomial and the combinatorics of lattice triangulations of Newton polytopes. We obtain upper bounds for the numbers of extrema and saddles of generic T-polynomials of a given degree in three variables, and derive from them upper bounds for Betti numbers of real algebraic surfaces in defined by T-polynomials. The latter upper bounds are stronger than the known upper bounds for arbitrary real algebraic surfaces in . Another result is the existence of an asymptotically maximal family of real polynomials of degree min three variables with 31m ³/36 + O(m ²) saddle points.     

Semi-algebraic Complexity of Quotients and Sign Determination of Remainders

For two nonzero polynomials[formula]the successive signed Euclidean division yields algorithms, that is, semialgebraic computation trees, for tasks such as computing the sequence of successive quotients, deciding the signs of the sequence of remainders in a pointa∈R, deciding the number of remainders, or deciding the degree pattern of the sequence of remainders. In this paper we show lower bounds of ordermlog₂(m) for these tasks, within the computational framework of semi-algebraic computation trees. The inevitably long paths in semi-algebraic computation trees can be specified as those followed by certain prime cones in the real spectrum of a polynomial ring. We give in the paper a positive answer to the question posed in T. Lickteig (J. Pure Appl. Algebra110(2), 131–184 (1996)) whether the degree of the zero-set of the support of a prime cone provides a lower bound on the complexity of isolating the prime cone. The applications are based on the degree inequalities given by Strassen and Schuster and extend their work to the real situation in various directions.     

An Algebraic Study of Affine Real Ultrafilters

Abstract

The families of affine semi-algebraic sets over a real-closed field Kand semi-linear sets over an ordered field enjoy many closure properties with algebraic and geometric significance. This paper studies the natural closure properies of Minkowski sums and scalar dilation. It gives an extension of the underlying vector space structure that enables the study of an arithmetic on the abstract points of their associated spectra. This arithmetic satisfies certain cancellation principles that motivates an investigation into an algebraic object weaker than a group and culminates with a version of the Jordan-Hölder theorem. With the subsequent definition of dimension we show that the collection of affine real ultrafilters in K ⁿ is n-dimensional over the scalar ultrafilters.     

Combinatorial bounds on Hilbert functions of fat points in projective space

We study Hilbert functions of certain non-reduced schemes A supported at finite sets of points in , in particular, fat point schemes. We give combinatorially defined upper and lower bounds for the Hilbert function of A using nothing more than the multiplicities of the points and information about which subsets of the points are linearly dependent. When N=2, we give these bounds explicitly and we give a sufficient criterion for the upper and lower bounds to be equal. When this criterion is satisfied, we give both a simple formula for the Hilbert function and combinatorially defined upper and lower bounds on the graded Betti numbers for the ideal I_A defining A, generalizing results of Geramita et al. (2006) [16]. We obtain the exact Hilbert functions and graded Betti numbers for many families of examples, interesting combinatorially, geometrically, and algebraically. Our method works in any characteristic.     

Semi-algebraic Absolute Valued Algebras with an Involution

Abstract

Let A be an absolute valued algebra. In El-Mallah (El-Mallah,M. L. (1988). Absolute valued algebras with an involution. Arch. Math. 51: 39–49) we proved that,if A is algebraic with an involution,then A is finite dimensional. This result had been generalized in El-Amin et al. (El-Amin,K.,Ramirez,M. I.,Rodriguez,A. (1997). Absolute valued algebraic algebras are finite dimensional. J. Algebra 195:295–307),by showing that the condition “algebraic” is sufficient for A to be finite dimensional. In the present paper we give a generalization of the concept “algebraic”,which will be called “semi-algebraic”,and prove that if A is semi-algebraic with an involution then A is finite dimensional. We give an example of an absolute valued algebra which is semi-algebraic and infinite dimensional. This example shows that the assumption “with an involution” cannot be removed in our result.     

Empty Simplices of Polytopes and Graded Betti Numbers

The conjecture of Kalai, Kleinschmidt, and Lee on the number of empty simplices of a simplicial polytope is established by relating it to the first graded Betti numbers of the polytope and applying a result of Migliore and the author. This approach allows us to derive explicit optimal bounds on the number of empty simplices of any given dimension. As a key result, we prove optimal bounds for the graded Betti numbers of any standard graded K-algebra in terms of its Hilbert function.     

Estimates of characteristic numbers of real algebraic varieties

We give some explicit bounds for the number of cobordism classes of real algebraic manifolds of real degree less than d, and for the size of the sum of Betti numbers with Z/2 coefficients for the real form of complex manifolds of complex degree less than d.     

Cohomology of the moduli of parabolic vector bundles

The purpose of this paper is to compute the Betti numbers of the moduli space ofparabolic vector bundles on a curve (see Seshadri [7], [8] and Mehta & Seshadri [4]), in the case where every semi-stable parabolic bundle is necessarily stable. We do this by generalizing the method of Atiyah and Bott [1] in the case of moduli of ordinary vector bundles. Recall that (see Seshadri [7]) the underlying topological space of the moduli of parabolic vector bundles is the space of equivalence classes of certain unitary representations of a discrete subgroup Γ which is a lattice in PSL (2,R). (The lattice Γ need not necessarily be co-compact). While the structure of the proof is essentially the same as that of Atiyah and Bott, there are some difficulties of a technical nature in the parabolic case. For instance the Harder-Narasimhan stratification has to be further refined in order to get the connected strata. These connected strata turn out to have different codimensions even when they are part of the same Harder-Narasimhan strata. If in addition to ‘stable = semistable’ the rank and degree are coprime, then the moduli space turns out to be torsion-free in its cohomology. The arrangement of the paper is as follows. In § 1 we prove the necessary basic results about algebraic families of parabolic bundles. These are generalizations of the corresponding results proved by Shatz [9]. Following this, in § 2 we generalize the analytical part of the argument of Atiyah and Bott (§ 14 of [1]). Finally in § 3 we show how to obtain an inductive formula for the Betti numbers of the moduli space. We illustrate our method by computing explicitly the Betti numbers in the special case of rank = 2, and one parabolic point.