# Do all possible trees arise as orbit trees of some permutation groups?

## I.Motivation from descriptive set theory

(Contains some quotes from Maciej Malicki's paper.)

The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a compatible left-invariant metric, that is, a metric d inducing the group's topology, and such that d(zx,zy)=d(x,y) for all x,y,z in G. However, even if G is completely metrizable, it is not always true that G admits a metric that is left-invariant and complete at the same time.

Polish groups admitting a complete left-invariant metric are called CLI groups. We only focus on CLI subgroups of $S_{\infty}$, the symmetry group of natural numbers, for now. Malicki proved that a permutation group G is CLI iff the orbit tree of G is well-founded, i.e. every branch of the tree terminates at some finite level, where the concept orbit tree is defined as following.

## II.The problem

Let $G\leq S_{\infty}$ be a permutation group acting on $\mathbb{N}$ (starts from 1 for convenience). Define $G_n$ to be the n-point stabilizer, $G_n=\{g\in G|g(i)=i,1\leq i\leq n\}$, and $G_0=G$. We represent an infinite orbit $O$ of $G_n$ by a node $N$ on level $n$ (finite orbits do not count).

If $O_1$ is an infinite orbit of $G_k$, $O_2$ an infinite orbit of $G_{k+1}$ and $O_2\subset O_1$ (possibly the same), we correspondingly draw $N_2$ as a one-step extension of $N_1$.

Assuming $G$ is transitive, this process defines a map from $G$ to a rooted tree $T_G \subset\omega^{<\omega}$. We say it is the orbit tree of $G$ and it roughly describes how the orbits of $G$ split when we keep fixing more and more points. The natural inverse question is

For every tree $T\subset\omega^{<\omega}$, is there a group $G$ such that the orbit tree $T_G$ is isomorphic to $T$? Can we construct it?

## III.Some attempts

Since I do not know too much about group theory, especially not about infinite permutation groups, I started with some concrete examples. The construction was hard even for very simple finite trees, though. For instance, $\mathbb{Z}$ acting on $\mathbb{Z}$ realizes the tree of a single node. $\mathbb{Z}_{wr}\mathbb{Z}_2$(wr for wreath product) on $\mathbb{Z}\times 2$ realizes a "chain" of any finite depth, etc. But these seem to be too ad hoc.

I also received a generous hint from an expert, saying that

1. If $G$ is a permutation group on $\Omega$ and $\alpha\in\Omega$ and the orbits of $G_{\alpha}$ are $\Omega_{\lambda}(\lambda\in\Lambda)$ then $G_{\alpha}$ is a subdirect product of the restrictions $H_{\lambda}:=G_{\alpha}^{\Omega_{\lambda}}$. Specifically $G_{\alpha}$ can be embedded in the Cartesian product $\prod_{\lambda}H_{\lambda}$ such that the projections onto each factor are surjective.

2. Now let $G$ be a free group of countably infinite rank. We want to find a corefree subgroup $H$ of $G$ of countable index such that $H$ is free of infinite rank and has a specified number of double cosets $HxH$ for which $|H:x^{-1}Hx|$ is infinite ($H$ is going to play the role of $G_{\alpha}$). We know that every subgroup of a free group is free and many (most of them?) have infinite rank when $G$ has infinite rank. I don't think it is that hard to satisfy the condition about the number of cosets. If this is true then we can go from level 0 to level 1.

3. To go to level 2 we know that $H$ is a subdirect product of the $H_{\lambda}$. Suppose that all the infinite $H_{\lambda}$ are free of infinite rank and that the embedding of $H$ induces an isomorphism onto each of these. Now for each infinite $H_{\lambda}$ choose (corefree, infinite rank) $K_{\lambda}$ so that $H_{\lambda}$ and $K_{\lambda}$ play the roles of $G$ and $H$ in 2 to provide the correct number of infinite orbits at the next level. Can we choose the isomorphisms $H\rightarrow H_{\lambda}$ and a subgroup $K$ of $H$ such that $K$ maps onto $K_{\lambda}$ for each $\lambda$?

4.If the answers to these questions are yes, I think that you can then prove what you want.

It is not easy for me to comprehend his thought since I have no training in free groups. I have some vague doubts that

1. What is the action of $G$ on countably many things? $G$ naturally acts on itself by concatenation but this seems not correct.

2. Why must such an $H$ be a one-point stabilizer?

3. Moreover, the free group of countably infinite rank is countable itself. It is known that every countable group is CLI, hence its orbit tree must be well-founded. That is to say, $G$ may never realize ill-founded trees. I suspect we need to use other methods for non-CLI groups, taking inverse limit for example.

## IV.Possible modifications of the problem (not strict)

From the viewpoint of descriptive set theory, it is not necessary to realize every tree, "a subcollection of trees" which has the same Borel complexity as "all trees" will suffice. For example, we may properly "stretch" the tree so that there is at most one "event" (a node terminates or a node splits into more than one nodes) happens on each level. we may also require every splitting node to split infinitely, etc. As long as the transformation is Borel, we may choose the easiest class of trees to realize.

To realize the tree, we may also choose to fix finitely many points at one time if necessary.

If we only look at the well-founded trees, we may construct a big tree recursively. We know that the one-point stabilizer is isomorphic to a subdirect product of the restrictions on each orbit. But

Given transitive permutation groups $H_1$, $H_2$... (finitely or countably many) acting on $\mathbb{N}$, is there a transitive group $G$ such that $G_{\alpha}$ is isomorphic to the direct product of these $H_{\lambda}$?

My greedy hope (possibly incorrect!) is, there is such a group. If this is true, noticing that factors of direct product are "independent" of each other, we may fix points on orbits "one by one" and let other orbits "wait". Say the orbit tree of $H_{\lambda}$ is $T_{\lambda}$, then the orbit tree of $G$ will be of the shape that each subtree is a "stretched" $T_{\lambda}$. It will work since we only need to realize all "stretched" trees.

Please do not laugh at my silliness if I am miserably wrong :-P Thank you so much for your time and effort.

• Can't G1 have infinitely many orbits? Construct your group in the following fashion. Divide N into {1} and countably more disjoint infinite sets Sis. Let G be generated by transpositions between the 1 and the first element of Sis and the full permutation group on Si. I was not sure how G corresponded to the rooted tree – Nishant Chandgotia Apr 24 '11 at 6:54
• How are you relating a tree to an element in \omega^{<\omega}? Does this mean all finite sequences in natural numbers? If so why does the tree need to be finite? Probably I am misunderstanding the notation. Can you clarify? – Nishant Chandgotia Apr 24 '11 at 7:10
• Thank you for your comment. G_1 could have infinitely many orbits. But your construction will not obtain the wanted direct product. This is because g(a1,a2...)g^{-1}=(g(a1),g(a2)...) and it will introduce a lot more permutations. – Mingzhi Xuan Apr 24 '11 at 23:42
• a rooted tree is a subset(well, my fault) in \omega^{<\omega} that is closed under taking initial segment. For example, the set {(0),(0,0),(0,1),(0,2)} is the tree that has one root and three "branches", each terminates at level 1. But we usually think of it intuitively(as drawn on paper). As we fix more and more points in N, the orbits become smaller and smaller as a set. We intuitively draw a node for each orbit with infinite size. If O2 is a subset of O1, then N2(on the level below) is linked to N1. Thus we may draw the orbit tree. – Mingzhi Xuan Apr 24 '11 at 23:57