$\def\conf{\mathtt{conf}} \def\cov{\mathtt{cov}} \def\Int{\mathbb{Z}} \def\Real{\Bbb{R}} \def\Comp{\mathbb{C}} \def\ZN{\Int_N} \def\attr{{\mathcal{A}}} \def\U{{\mathcal U}} \def\Ed{{\mathcal E}} \def\Rd{{\Real}^d} \def\cN{{\mathbf N}} \def\OO{{\mathcal O}} \def\DD{{\mathcal D}} \def\HH{{\mathcal H}} \def\NN{{\mathcal N}} \def\VV{{\mathcal V}} \def\domain{{\mathcal{B}}} \def\ii{{\mathbf i}} \def\T{{\mathbb T}} \def\S{{\mathbb S}} \def\mod{{\mathit mod}} \def\Cycle{{\mathbf \sigma}} \def\prob{{\mathbb P}} \def\ex{{\mathbb E}} \def\codim{{\mathit{codim}}} \def\paths{{\mathcal P}} \def\sens{{\mathcal S}} \def\measurements{{\mathcal E}} \def\indep{{\mathcal I}} \def\one{\mathbb{I}} \def\dim{\mathtt{dim}} \def\nset{\mathbf{n}} \def\mset{\mathbf{m}} \def\Nat{\mathbb{N}} \def\types{\mathfrak{F}} \def\ideal{\mathcal{I}} \def\bz{\bar{z}} \def\bn{\bar{n}} \def\arrange{\mathcal{A}} \def\fld{\Bbbk} \def\attr{\mathfrak{A}} $

exotic configuration spaces

yuliy baryshnikov

UIUC, mathematics and ECE

supported by onr and afosr


For a topological space $X$, its (colored) configuration space is the collection of $n$-tuples of distinct points in $X$, or, equivalently, \[\color{lightgray}{ \conf(X,n)=X^n-\bigcup_{i\neq j}\Delta_{ij}, }\] the $n$-th Cartesian power of $X$ with the union of the diagonals $\Delta_{ij}=\{x_i=x_j\}$ removed.

These spaces (and their uncolored relatives, ${\conf(X,n)/S_n}$), introduced by Fadell and Neuwirth, have numerous applications, in partcular in quantum mechanics, Hamiltonian systems etc.

An archetypal example is the configuration space of $\Real^2$ with a long resume of wonderful properties:

  • It is a $K(\pi,1)$ space for $\pi$ the Artin braid group;
  • its cohomology ring is generated by $1$-dimensional classes $\omega_{ij}$ (orbital classes) modulo quadratic relations (Arnol'd's relations);
  • nice Poincare polynomial: \[ \sum \beta_k t^k=(1+t)\cdot\ldots\cdot(1+(n-1)t). \]

This space is an important building block in many areas, from knot theory to theoretical robotics...

In this talk we will be dealing with exotic relatives of the classical configuration spaces, exemplified by the no-k-equal spaces, introduced and studied by Bjőrner and Lovasz.

We will be using $\nset=\{1,2,\ldots,n\}$.

No-k-equal space $\conf_k(X,n)$ of $X$ is the $n$-th Cartesian power of $X$ with its $k$-diagonals removed, \[ \conf_k(X,n)=X^n-\bigcup_{|I|=k}\Delta_I, \] where $I\subset \nset, I=\{i_1 < i_2 < \ldots < i_k \}$, and $\Delta_I=\{x_{i_1}=x_{i_2}=\ldots=x_{i_k}\}$.

One can consider even more involved spaces. Take a finite collection $\types$ of types of points ("particles"). The interactions are encoded by a subset $I\subset \Nat^\types$ of particle populations at a point which are allowed to co-locate (that is $$ \bn=(n_1,\ldots,n_{|\types|})\in I $$ means that the having $n_f$ points of type $f\in \types$ at the same point $x$ is allowed).
We will concentrate on the case when $I$ is an ideal: for any $\bn'\preceq\bn\in I$, one has $\bn'\in I$.

One typical example: particles of two types that are not allowed to coincide: \[ \conf_{11}(X, m,n)=X^m\times X^n-\bigcup_{i\in\nset, j\in\mset} \Delta_{ij}. \] Here we have $m$ points $(x_1,\ldots,x_m)\in X^m$ of type 1, $(x_1,\ldots,x_m)$, and $n$ points $(y_1,\ldots,y_n)\in X^n$ of the type 2, and the forbidden diagonals are \[ \Delta_{ij}=\{x_i=y_j\}\subset X^m\times X^n. \] (These configuration spaces were used by Segal, McDuff and others to study the space of harmonic maps of $S^2$ into spheres.)

We are interested in computing the Betti numbers of such configuration spaces.


Topology of configuration spaces is relevant outside of physics. One particular class of examples comes from theoretical computer sciences via the Yao-Bjorner-Lovasz theory.
An algebraic decision tree is a computational model, based on "universal covering" of a flowchart. At each node, a polynomial of the input variables is computed. Leaves are marked by answers.

The total Betti number leads to lower bounds of the volume (depth) of the algebraic decision trees:

The depth of the algebraic decision trees deciding membership in a semi-algebraic set $C\subset \Real^d$ is bounded from below by \begin{equation} \Omega\left(\log \beta(C)\right) \end{equation} (the constants depending on the degrees of the polynomials $P_j$ and on the dimension $d$).

An alternative (weaker) estimate is through the Euler characteristics of $C$.

Another application comes from the control theory, where one is concerned with the dynamical systems \[ \dot{x}=f(x,u), \] with the speed of $x$ depending on $x$ itself and on controls $u\in U$. Assume some compact submanifold $\attr$ (a point, a periodic trajectory,...) with a tangent vector field $v$ is given.
Feedback stabilization to $\attr$ is a (piece-wise continuous) function $k:M\to U$ such that the dynamics defined by \[ \dot{x}=f(x,k(x)) \] coincides with $v$ on $\attr$ and has $\attr$ as an attractor.

It is immediate that feedback stabilization fails to exist, unless $\attr\sim_h M$.
The flow defined by $f(x,k(x))$ is necessarily discontinuous on some set (call it a cut corresponding to $k$).
How large or small a cut can be? One can show that the homology of the cut is defined by the mismatch of the homologies of $M$ and $\attr$.

no-k-equal arrangements

We start with the configuration spaces with just one particle type, with the ideal $I=\{1,2,\ldots,k\}$. We will denote the corresponding configuration spaces as $\conf_k$.
If $X=\Real^d$, the spaces $\conf_k(X,n)$ are understood pretty well: they are examples of subspace arrangement manifolds:
A (central) subspace arrangement (over a filed $\fld$) is a union of linear subspaces in $V=\fld^n$, \[ \arrange=\bigcup_\alpha L_\alpha. \] The variety $V-\arrange$ is called the manifold of $\arrange$.
We will denote the manifold of no-k-equal arrangement, over $\fld=\Real$ as $M^\Real_{n.k}$ (i.e. $\conf_k(\Real^1)$ in our nomenclature).
The manifold $M^\Real_{n,3}$ is especially interesting for its similarities with the braid arrangement $M^\Comp_{n,2}$. Both arrangements are of codimension 2, and both are $K(\pi,1)$ spaces (Arnold, Brieskorn; Khovanov, Davis, Januskiewicz...).
The cohomology rings are generated by the intersection indices with the "laser beam" relative classes, with their cup products having clear geometric interpretations.

For the $\conf_k(\Real,n)=M^\Real_{n,k}$ space, we denote $\mathtt{(J_0) [I_1] (J_1)...[I_{m}](J_m)}$ (here $J_o,I_1,J_1,\ldots$ form a partition of $\nset$ with all $I_l$ of size $(k-1)$) the cell given by \[ \begin{array}{cl} x_{j} \geq & \mathrm{for}\quad j\in J_0\\ \geq x_{i_1}=\ldots=x_{i_{k-1}}\geq &\mathrm{for}\quad j\in I_1\\ \vdots & \\ \geq x_{j'}& \mathrm{for}\quad j'\in J_m\\ \end{array} \] We call the classes dual to the cells $\mathtt{(J)[I](J')}$ elementary.
The ring structure for $M^\Real_{n,k}=\conf_k(\Real^1,n)$ is given by the following
The ring $H_*(M^\Real_{n,k})$ is the free commutative algebra generated by the elementary classes (of degree $(k-2)$) factored by \[\begin{align*} \ideal_1=&\langle\sum_{j\in J}(-1)^j\mathtt{(J-j)[I+j](J')}+\\ &\sum_{j'\in J'}(-1)^{j'}\mathtt{(J)[I+i'](J'-j')}\rangle \end{align*} \] and the quadratic ideal $\ideal_2$ generated by products of elementary cells having empty intersections.
As a corollary, one obtains a basis in $H^{*}(M^\Real_{n,k})$.
Define a tidy cell $\mathtt{(J_0)[I_1](J_1)...}$ as such that the largest index in $I_k\cup J_k$ is in $J_k$ (in particular, all $J_k, k\geq 1$ are non-empty).
Then $H^{m(k-2)}(M^\Real_{n,k})$ is spanned by the tidy cells with $m$ $\mathtt{[I]}$ blocks.

This allows one to deduce the exponential generating function for the Poincare polynomials of $M^\Real_{n,k}$:

\[ \sum_n P_n(t)\frac{z^n}{n!} =\frac{e^z}{1 +(-t)^{k-2}(e^z q_k(z) - 1)}, \] where \[ P_n(t))=\sum_m \beta_{m}(M^\Real_{n,k}) t^m \] and $q_k(z)=1-z+z^2/2!-\ldots \pm z^{k-1}/(z-1)!$.

One can see how much the Euler characteristics deviates from the total Betti number. Say, $\chi(M^\Real_{n,5})/n!\approx C_\chi(n) \times (1.9445443655968941..)^{-n}$, while $\beta(M^\Real_{n,5})/n!\approx C_\beta\times (1.889327221941516..)^{-n}$.

Euler characteristic for exotic configuration spaces

In general, to understand the cohomology structure even for the usual configuration spaces, even for manifolds is highly nonotrival (Totaro described cohomologies for smooth complex projective varieties, though).
We would like to deal with arbitrary compact definable sets in some o-minimal structure (esiest is to think about semi-algebraic or semi-linear sets).

We however will aim at an easier task of understanding of Euler characteristic of the configuration spaces. Triangulation theorem allows us to assume that $X$ has a stratification satisfying local conicity condition, \[ X=\amalg_\sigma X_\sigma\]

Again, we consider a finite collection $\types$ of types of points (particles). The interactions are encoded by a subset $I\subset \Nat^\types$ of particle populations at a point so that $I=\bn\in\Nat^\types$ is a subset of all collections of type populations that can be colocated; To each ideal we associate the corresponding (exponential) generating function $$ \psi_I(\bz)=\sum_{\bn\in I} \frac{\bz^\bn}{\bn!} $$

$$\begin{align*} \psi_I=&1+x+y+x^2/2+xy +y^2/2+ \\ &+x^3/6+ y^3/6+x^4/24+x^5/120+x^6/720.\\ \end{align*} $$

Our main result is an exponential generating function for the Euler characteristics
In the assumptions above, for a compact definable $X$ equipped with a conic stratification, $X=\amalg_\sigma X_\sigma$, we have:
The exponential generating function for the Euler characteristics of the $I$-configuration spaces is given by $$\begin{align*} \sum_\bn& \chi(\conf_I(X,\bn)) \frac{\bz^n}{\bn!}=\\ &\prod_\sigma \psi_I(\bz\check{\one}(X_\sigma))^{(-1)^{\dim(X_\sigma)}\chi(X_\sigma^c)}. \\ \end{align*}$$
In \[ \prod_\sigma \psi_I(\bz\check{\one}(X_\sigma))^{(-1)^{\dim(X_\sigma)}\chi(X_\sigma^c)} \]
  • the product in the right hand side is taken over all strata $X_\sigma$ of $X$;
  • the compactification $X^c_\sigma$ are homeomorphic to the complement in $X$ to small tubular neighborhoods of adjacent strata, $$ X^c_\sigma=X_\sigma-\cup_{\sigma'\prec \sigma} N^\circ X_{\sigma'}; $$
  • the constructible function $\check{\one}$ is Verdier dual to the constant function $\one = 1|_X$, or, equivalently, the (definable) Euler characteristics of a small ball around the point.

In particular, if $X$ is a manifold, the RHS reduces to $$ \psi_I((-1)^{\dim(X)}\bz)^{\chi(X)}. $$

Some examples

$${ \sum_\bn \chi(\conf_I(X,\bn)) \frac{\bz^n}{\bn!}=\prod_\sigma \left(\psi_I(\bz\check{\one}(X_\sigma))\right)^{(-1)^{\dim(X_\sigma)}\chi(X_\sigma^c)}. }$$

The case of standard configuration spaces for simplicial complexes was considered by S. Gal (major motivation for this work). His formula $$ \sum_n \chi(\conf(X,n))\frac{z^n}{n!}= \prod_\sigma (1 + (−1)^{\dim(X_\sigma)}(1 − \chi(L_\sigma))z)^{(−1)\dim(X_\sigma)} $$ (where $L_\sigma$ is the normal link of the simplex $\sigma$) corresponds to $\psi_I=1+z$ for the ideal of the standard configuration spaces.

If $X$ is the union of two 2-disks t ouching at a point, we have $$ \sum_n \chi(\conf(X,n))\frac{z^n}{n!}= (1-z)(1+z)^2=1+z-2\frac{z^2}{2}-6\frac{z^3}{6}. $$
The 1-dimensional homology of $\conf(X,2)$ are generated by the usual solar cycles:
...and an eight-shaped cycle:
Consider the space of black and white particles that are not allowed to interact, on $X=\S^2$. Then $$ \psi_I=\exp(x)+\exp(y)-1, $$ and $$ \sum_{m,n} \chi(\conf_I(X,(m,n))) \frac{x^m y^n}{m!n!}=(\exp(x)+\exp(y)-1)^2. $$ In particular, for $m,n \gt 0$, $\chi(\conf_I(S^2,(m,n)))=2$.

For three colors, $\chi(\conf(S^2,(m,n,p)))=0$ if $m,n,p>0$.
Consider $I=\{1,2\}$ (i.e. the no-3-equal configuration space), and $X$ a graph, i.e. a 1-dimensional simplical complex. Simplify the graph by removing all vertices of degree $2$. Then $$ \sum_{n} \chi(\conf_I(X,n)) \frac{x^n}{n!}=\frac{\prod_{v: d(v)\ge 3}(1-(d(v)-1)x+(d(v)-1)^2x^2)/2}{(1-x+x^2/2)^{|E|}}. $$ For example, for the graph below, $$ \begin{align*} \sum_{n} &\chi(\conf_I(X,n)) \frac{x^n}{n!}=\\ &1+x+\frac{x^2}{2}+12\frac{x^3}{6}+126\frac{x^4}{24}+870\frac{x^5}{120}+4770\frac{x^6}{720}+\ldots\\ \end{align*} $$
In general, presence of the term $(1-x+x^2/2)^{-|E|}$ suggests that most of the cohomology is coming from weakly interacting configuration spaces on the edges...


  • Applications in robotics and CS generate a need in industrial grade computations of topological invariants for configuration spaces;
  • Quite often, this can be done very explicitly;
  • There are some interesting leads to follow - computing Betti numbers for no-k-equal spaces on graphs, rendering the theory in terms species of definable structures etc.

thank you!