On stable equivalence of semialgebraic sets

About four months ago, I posted a question on MathOverflow concerning a lemma in Richter-Gebert’s book Realization spaces of polytopes. Let me quickly explain the setup. We are dealing with semialgebraic sets in Rd\mathbb{R}^d which are defined by polynomials with rational coefficients. A general semialgebraic set is defined by a Boolean combination of equations, inequations and (strict or weak) inequalities. If the only Boolean junction required to write the set is conjunction, then the set is basic and if, in addition, only equations and strict inequalities are required, it is primary basic.

Primary basic semialgebraic sets are (one possible choice of) building blocks for general semialgebraic sets and they are compactly specified by a polynomial system of the form {ϕi(x)>0,ψj(x)=0}\{\, \phi_i(x) > 0, \, \psi_j(x) = 0 \,\} for ϕi,ψjQ[x]\phi_i, \psi_j \in \mathbb{Q}[x]. On these sets one seeks a notion of equivalence which preserves multiple of their characteristics simultaneously, in particular the homotopy type and the algebraic number type, i.e., what is the smallest field extension over Q\mathbb{Q} required to write down some point of the semialgebraic set? The definition of such a notion, called stable equivalence, in Richter-Gebert’s book is the subject of my question. Here it is:

Two primary basic semialgebraic sets WW and VV are rationally equivalent if there exists a homeomorphism between them which is in both directions defined by rational functions with rational coefficients. Next consider WRn+mW \subseteq \mathbb{R}^{n+m} and let VRnV \subseteq \mathbb{R}^n be its coordinate projection to the first nn coordinates. This is a stable projection if there exist polynomials ϕi,ψjQ[v,w]\phi_i, \psi_j \in \mathbb{Q}[v,w] which have degree 1 in the coordinates ww and such that we may recover WW from its projection VV via

W={(v,w)Rn+m:vV,  ϕi(v,w)>0,  ψj(v,w)=0}.W = \{\, (v,w) \in \mathbb{R}^{n+m} : v \in V, \; \phi_i(v,w) > 0, \; \psi_j(v,w) = 0 \,\}.

The sets are stably equivalent if they are in the same class of the smallest equivalence relation which is generated by rational equivalence and stable projection. Richter-Gebert states in his Lemma 2.5.2 that stably equivalent sets have the same homotopy type and algebraic number type. This is pretty obvious for the rational equivalences. In the rest of this article, I will concentrate on the stable projection part of this claim.

You may be wondering why the polynomials need to be affine-linear in the coordinates ww which should be “recovered” from the projection VV. This is required to preserve the algebraic number type. Solving equations of higher degree, such as w2=2w^2 = 2 may increase this measure of algebraic complexity, while linear equations surely do not. The proof for the algebraic number type in the book is slightly wrong but easily fixable and the statement holds (if the equations are affine, then there need not be purely rational ww coordinates, as is claimed, for every vVv \in V but Cramer’s rule implies that their coordinates are in the field extension of Q\mathbb{Q} generated by vv). This is the reason for restricting to affine-linear equations. To prevent a lingering confusion at this point, let me clarify that the inequalities being affine-linear is not necessary for any argument presented here — they could be non-linear if needed.

Notice that in the above definition, every fiber Fv=π1(v)F_v = \pi^{-1}(v) is the relative interior of a polyhedron. For my dissertation, I needed to extend this machinery to fibers which are more general convex sets, namely spectrahedra (the intersections of affine-linear spaces of symmetric matrices with the cone of positive-semidefinite matrices) — in that case I need some non-linear inequalities. The problem: there is no proof given in the book for the homotopy equivalence claim from which I could start. This led to my MathOverflow question.

A counterexample

My initial hope was to find a general theorem in a topology textbook of the sort “this diagram chase constructs a section, therefore the two spaces are homotopy-equivalent” but that did not happen. In the sections of Hatcher’s Algebraic Topology dedicated to fiber bundles and fibrations I found theorems that say, when VV is contractible, then we essentially have a fiber bundle. But the idea behind a stable projection is different: we want to deduce from the fact that the fibers FvF_v are uniformly defined (by the polynomials ϕi\phi_i and ψj\psi_j) and extremely simple (they are polyhedra, therefore convex and homotopically trivial with something as simple as straight line homotopies), that VV and WW should not differ in terms of homotopy. I discussed this view at length with my colleagues Andreas Kretschmer and Yuri Santos Rego for whose time and input I’m very thankful. This eventually led to the following simple counterexample to the claim in the book:

The union of a coordinate axis and a hyperbola is not path-connected but its projection onto the other axis is.

Consider W={(v,w)R2:v(vw1)=0}W = \{\, (v,w) \in \mathbb{R}^2 : v(vw - 1) = 0 \,\}. This set is the union of the ww-axis with the hyperbola vw=1vw = 1. Its projection onto the vv-coordinate is the entire real line V=R1V = \mathbb{R}^1 and the definition of WW already proves that this projection is stable, because there is one equation defining WW in terms of vRv \in \mathbb{R} which has degree 1 in ww. But the line VV is path-connected whereas WW is not: for v0+v \to 0^+, the unique coordinate ww with (v,w)W(v,w) \in W tends to ++\infty while with v0v \to 0^-, this ww tends to -\infty. At v=0v=0, all ww give a point in the fiber F0F_0, but this does not path-connect the two branches of the hyperbola in the affine plane. Two spaces which differ in their path-connectedness cannot be homotopy-equivalent.

This counterexample can be “homogenized” to

W={(v,w,w)R3:w>0,  v(vww)=0}W = \{\, (v, w, w') \in \mathbb{R}^3 : w' > 0, \; v(vw - w') = 0 \,\}

so that its fibers are defined by homogeneous linear forms in ww. The space WW and its projection VV still differ in path-connectedness and therefore are a counterexample to homotopy equivalence under the slightly more restricted definition of stable projection in the article by Richter-Gebert and Ziegler: Realization spaces of 4-polytopes are universal.

Local sections are sufficient (but not necessary)

In the months following that discovery I think I obtained a fairly good understanding of why the definition in Richter-Gebert’s book fails to give homotopy equivalence and what can be done to fix it. This is in no small part thanks to resources pointed out by Richter-Gebert about earlier attempts to give a satisfying notion of stable equivalence, including his own variants of the definition. These are described in the last section. Before that, I want to give a few technical remarks and proof snippets from my perspective as a topology pedestrian.

Let us assume that WW and VV are primary basic semialgebraic sets, VV is the projection of WW and it is stable in the sense that W={(v,w)Rn+m:vV,  ϕi(v,w)>0,  ψj(v,w)=0}W = \{\, (v,w) \in \mathbb{R}^{n+m} : v \in V, \; \phi_i(v,w) > 0, \; \psi_j(v,w) = 0 \,\}, where I’m leaving the precise restrictions on ϕi\phi_i and ψj\psi_j unstated for the moment. But let’s assume that they are polynomials and that each fiber FvF_v is a convex set.

The most natural approach to proving homotopy equivalence of the set WW to its stable projection VV is to obtain a covering of it by local sections for the projection π\pi. That is, for every vVv \in V a small neighborhood UvU_v around vv and a continuous map sv:VUvWs_v: V \cap U_v \to W such that πsv\pi \circ s_v is the identity.

To show that this is sufficient for homotopy equivalence, let me recite some basic facts about the topology on semialgebraic sets. These facts can be pieced together from general results found among the first 40 pages of Bredon’s book Topology and geometry. Consider a primary basic semialgebraic set with its induced euclidean topology. This is surely a second-countable Hausdorff space because its ambient Rn\mathbb{R}^n is. It is locally closed (immediate from its defining polynomials) and locally compact which implies that it is paracompact. This in turn ensures the existence of subordinate partitions of unity to any open covering.

In a paracompact space, we may assume that (Uv)vV(U_v)_{v \in V} has been thinned out to a locally finite cover (Uv)vV(U_v)_{v \in V'} indexed by a subset VVV' \subseteq V. Then, we obtain functions ρv\rho_v which partition unity on VV and such that the support of ρv\rho_v is confined to a closed set inside UvU_v. This allows us to define a global section s(v~):=vVρv(v~)sv(v~).s(\tilde v) := \sum_{v \in V'} \rho_v(\tilde v) s_v(\tilde v). That this summation is finite follows from the local finiteness of the partition of unity. It is well-defined because ρv(v~)\rho_v(\tilde v) vanishes outside of the domain of svs_v due to the subordination of the ρ\rho’s. The function is continuous because ρv\rho_v and svs_v are continuous. Lastly, the sum is a convex combination of sv(v~)s_v(\tilde v) over finitely many vVv \in V. By definition svs_v satisfies sv(v~)Fv~s_v(\tilde v) \in F_{\tilde v} and π(sv(v~))=v~\pi(s_v(\tilde v)) = \tilde v. Since the fiber Fv~F_{\tilde v} is convex, this convex combination remains inside it. Thus ss is a section of π\pi.

As an aside: By standard analysis constructions, we can even demand ρv\rho_v smooth on the open neighborhood vUv\bigcup_v U_v of VV. Hence, the differentiability properties of ss depend entirely on how smooth we are able to make the local sections svs_v, but in the following I want to focus on the existence of continuous local sections only. You are invited to keep this in mind for the time when local sections are constructed.

Having the global section s:VWs: V \to W of π\pi, it is easy to recognize that s(V)s(V), which is a homeomorphic copy of VV inside of WW, is in fact a strong deformation retract of WW: since the fibers over VV are convex sets, straight-line homotopies retract WW onto s(V)Ws(V) \subseteq W. All we needed the section ss for was to choose a “representative point” continuously for every fiber of VV on WW. The homotopy itself is then very easy. This yields homotopy equivalence from local sections.

However, not every homotopy equivalence allows for the existence of local sections. Consider the semialgebraic set W={v<0,w=1}{v=0,1w1}{v>0,w=1}W = \{\, v < 0, \, w = -1 \,\} \cup \{\, v = 0, \, -1 \le w \le 1 \,\} \cup \{\, v > 0, \, w = 1 \,\}:

The graph of the sign function with an interval at 0 connecting the two signs.

This space is homeomorphic to a line R1R2\mathbb{R}^1 \subseteq \mathbb{R}^2. Its projection onto the vv-axis is the line R1\mathbb{R}^1 as well. Thus, we have homotopy equivalence but a local section at v=0v=0 does not exist because WW is almost everywhere the graph of a discontinuous function around v=0v=0.

The difficulty of obtaining local sections

Let’s see what the problem is with obtaining local sections in our setting. Fix vVv \in V and we may fix a point (v,w)Fv(v,w) \in F_v. The goal is to extend this particular solution ww to the system ϕi(v,w)>0\phi_i(v,w) > 0 and ψj(v,w)=0\psi_j(v,w) = 0 continuously to a small neighborhood of vv. Locally, the strict inequalities ϕi>0\phi_i > 0 make no problems at all, so we concentrate on the equations ψj=0\psi_j = 0. Now it simplifies the situation to assume that they are linear in ww and write them as a system Avw=bvA_v w = b_v where AvA_v is a matrix whose entries are polynomials in vv and bvb_v is a column vector of that sort. This system may be square, under- or overdetermined.

The parametrized family of matrices AvA_v has a generic rank in the affine space Rn\mathbb{R}^n. Let vv be any point in Rn\mathbb{R}^n and consider a minimal spanning set of columns of AvA_v. Their number rr is the rank and for them to be linearly independent means that there is a square submatrix in this collection of columns whose determinant does not vanish. Consider this same subdeterminant of AvA_v as a polynomial in vv. Since it does not vanish for some vRnv \in \mathbb{R}^n, its zero locus is a lower-dimensional variety and thus the rank of AvA_v is at least rr outside of this locus. This shows that the maximum rank of any particular AvA_v, vRnv \in \mathbb{R}^n, is in fact the rank attained by AvA_v almost everywhere. In every sufficiently small neighborhood of vv, the rank of AvA_v can only increase (if it does increase, that means vv is one of those special points in the vanishing locus of a determinant) — equivalently, the dimension of the solution space to the homogeneous equations Avw=0A_v w = 0 can only decrease. This holds on every irreducible real algebraic variety VV in place of Rn\mathbb{R}^n (the generic rank might be lower than on the entire space but that lower rank will be attained almost everywhere), but it is not necessarily true on primary semialgebraic sets.

Brushing that issue aside, if the rank is locally constant, that is, the generic rank is attained on every single point inside an open neighborhood of any chosen vv, then local sections are easy to construct by applying Cramer’s rule to the full-rank square submatrix examined in the previous paragraph: the particular solution ww extends to a unique surface of solutions for the systems Avw=bvA_v w = b_v around vv. A problem arises only at those points where the generic rank rises in every neighborhood. This is precisely the failure mode of the above counterexample at v=0v=0.

Stable equivalence kaleidoscope

After these detailed preparations, we are ready to see notions of stable projection which preserve homotopy type.

Constant-dimension Richter-Gebert

As argued in the previous section, if Richter-Gebert’s definition of stable projection would be strengthened to require that the fiber polyhedra have the same dimension locally around every point of VV, then we obtain local and, by convexity and partitions of unity, a global section.

Separated equations and inequalities

Suppose that the fibers in a stable projection are convex and are described either by (non-linear) strict inequalities or by linear equations in ww. In the case of strict inequalities, local sections obviously exist because around a given point (v,w)Fv(v,w) \in F_v any vv' close enough to vv can just use (v,w)Fv(v',w) \in F_{v'} by continuity of the strict inequalities. In the case of only linear equations, we have the global section v(v,0)v \mapsto (v,0). If you can decompose your projection into a sequence of such simple projections, homotopy equivalence follows.

The hyperbola counterexample above uses only a single affine equation in ww, so even if inequalities and equations are separated in the definition, affine equations are not admissible.

Bokowski and Sturmfels: product with Rm\mathbb{R}^m

In their fantastic book Computational synthetic geometry, Section 6.3, Bokowski and Sturmfels give a concise definition of stable equivalence while discussing the universality theorem of Mnëv which was brand new at the time. Two semialgebraic sets VV and WW are stably equivalent according to Bokowski and Sturmfels if there exists a locally biregular homeomorphism ff such that f(V×Rm)=Wf(V \times \mathbb{R}^m) = W. In this setup, rational equivalence and stable projection have been fused into one concept represented by the map ff. The homotopy equivalence of VV and WW is obvious: VV is just V×{0}V \times \{\,0\,\} which is a deformation retract of V×RmV \times \mathbb{R}^m and this is in turn homeomorphic to WW.

Günzel: product with a manifold

Günzel in The universal partition theorem for oriented matroids has a very similar definition of equivalence. He is interested in differential-geometric features, so the restriction to polynomials is dropped. The space Rm\mathbb{R}^m is replaced by a smooth manifold NN under a diffeomorphism ff. As far as I can see, the manifold is not claimed to be contractible, so that this does not necessarily entail homotopy equivalence of VV and W=f(V×N)W = f(V \times N). But if NN is contractible, then the proof is as easy as above. In any case, this product with a smooth manifold is probably the preservance of the “singularity structure” mentioned in Richter-Gebert and Ziegler’s bulletin cited above. This claim does not appear in the book version of the lemma.

Affine assignments and non-linear inequalities

In my own work about a universality theorem for Gaussian conditional independence models, I wanted to recover homotopy and algebraic number type as well as algorithmic complexity which is why I favor maps defined globally by polynomials instead of locally, as in Bokowski-Sturmfels. In addition, I found Richter-Gebert’s view of uniformly varying fibers more convenient in proofs than having this map around a product with Rm\mathbb{R}^m.

What I really needed for my spectrahedral fibers were affine-linear equalities in ww which were shown above to cause problems if the dimension of the solution space can vary. In my case, this could be cured by always having zero-dimensional linear spaces in the definition of the fibers. In fact, the definition of stable projection I use in my thesis is this: WW must be recoverable from VV as all (v,w,w)(v,w',w'') satisfying vVv \in V, ϕi(v,w)>0\phi_i(v,w') > 0 and wj=ψj(v)w_j'' = \psi_j(v), where ϕi\phi_i and ψj\psi_j are arbitrary rational functions such that all fibers are convex. The only equations are direct assignments of rational functions in vv to a subset ww'' of the lost coordinates. This may seem like a serious limitation but the Shor normal form, which plays an important role in the universality theorem for 4-polytopes as well, still works with affine assignments and convex fibers only. The existence of local sections is immediate and since the fibers are convex, the previous arguments for the existence of a global section apply.


My verdict on this issue is that the fibers need to have constant dimension. Convexity, unexpectedly, plays a large role in the proofs I presented, as they rely on a partition of unity to paste local sections together.

This was a long article which resulted from reading some amazing papers from the 90s and many long discussions with my colleagues in Magdeburg. I think I’ve gained a solid understanding of the problem and possible fixes. The exposition of this topic had a month or two more delay than they should have had because my thesis submission, the move to Leipzig and new projects took precedence. And it is still not over. I am in contact with Jürgen Richter-Gebert about the problem in his book and we are looking to establish a reading group with the aim of publishing a correction note in due time.