posts

Orbit-finite bijections can be smoothed

Leave a comment

In his recent post Bartek demonstrated an example of two equivariant sets with atoms that are related by a finitely supported bijection, but not by any equivariant bijection. We show that if the sets are orbit-finite then this situation is impossible.

Proposition. Let X and Y be two orbit-finite equivariant sets with atoms. If there exists a finitely supported bijection f \colon X \rightarrow Y then there exists an equivariant bijection F \colon X \rightarrow Y.

Let S be a finite set of atoms. An S-orbit of an element x is the set

    \[\{ \pi(x) \ | \ \pi \mbox{ acts as the identity on } S \}.\]

We introduce some terminology regarding S-orbits. An S-support of an element x contains those elements of the least support of x that do not belong to S, i.e., sup_S(x) = sup(x) \setminus S. An element which least support has an empty intersection with S is called S-free.

Recall that the dimension of an element x is the size of its least support. We define an S-dimension of x to be the size of its S-support. Each element of a single S-orbit has the same S-dimension. Therefore, we can also talk about an S-dimension of an S-orbit.

In equality atoms, every single-orbit set X (i.e. a set that consists of one \emptyset-orbit) is a disjoint union of finitely many S-orbits. Exactly one of these S-orbits contains all S-free elements of X.

Example. The single-orbit set A^{(2)} of pairs of distinct atoms is a union of three \{a\}-orbits. The first one consists of \{a\}-free pairs (it has \{a\}-dimension 2), the second one consists of pairs with the atom a on the first coordinate (it has \{a\}-dimension 1), and the third one consists of pairs with the atom a on the second coordinate (it also has \{a\}-dimension 1).

Proof. Let f \colon X \rightarrow Y be a bijection supported by a finite set S of atoms. Note that the function f has the following properties:
\bullet it maps S-orbits of X to S-orbits of Y,
\bullet it preserves the S-supports of elements (and hence also the S-dimension).

Let us first deal with the case when X is single-orbit. Take an S-free element x of X. It is not difficult to see that f maps x to an S-free element of Y of the same S-dimension. We define an equivariant function F \colon X \rightarrow Y by F(\pi(x))= \pi(f(x)), where \pi is any permutation of atoms.

The function F is well defined. Indeed, suppose that \pi(x)=\sigma(x). Since sup(f(x)) and S are disjoint sets of atoms, there exist permutations \pi' and \sigma' which act as \pi and \sigma on sup(f(x)) but are equal on S, i.e., \pi'|_S = \sigma'|_S. The bijection f is supported by S, so

    \[\pi(f(x))=\pi'(f(x)) = \sigma'(f(x)) = \sigma(f(x)).\]

Observe that F agrees with f on the S-free arguments, so it is injective on the set of S-free elements of X. Therefore, F is injective on the whole set X.

We have shown that F is an equivariant bijection between X and F(X). Hence, it induces a bijection between the set of S-orbits of X and the set of S-orbits of F(X). But the number of S-orbits of X is finite and equal to the number of S-orbits of Y, which proves that F(X)=Y.

Now suppose that X has an arbitrary number of orbits. We will define the equivariant bijection F for each orbit of X separately, starting from the orbits of the biggest dimension.

Let o_i(X) denote the number of S-orbits of X with the S-dimension i. We have that o_i(X) = o_i(Y) for every i \geq 0. Let N be the biggest i such that o_i > 0. In both X and Y there are o_N S-orbits of S-dimension N. It is not difficult to see that each of them is S-free and belongs to a different orbit of X or Y. Hence, in both X and Y there are o_N orbits of dimension N, denoted X_1, \ldots, X_{o_N} and Y_1, \ldots, Y_{o_N}, respectively. The function f induces a bijective correspondence between these sets. For every pair of corresponding orbits X_i and Y_i we define an equivariant bijection F_i \colon X_i \rightarrow Y_i similarly as in the single-orbit case above.

We call two sets with atoms S-isomorphic if they are related by some S-supported bijection. Let X' = X \setminus (X_1 \cup \ldots \cup X_{o_N}) and Y' = Y \setminus (Y_1 \cup \ldots \cup Y_{o_N}). Both those sets are equivariant. Moreover, X' and Y' are S-isomorphic. This follows from the following characterization: two orbit-finite sets with atoms are S-isomorphic if and only if there exists a bijection between the set of S-orbits of X and the set of S-orbits of Y such that the corresponding S-orbits are S-isomorphic. Hence, there exists an an S-supported bijection f' \colon X' \rightarrow Y' and the same construction can be repeated.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>