Do all possible trees arise as orbit trees of some permutation groups? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T02:55:31Z http://mathoverflow.net/feeds/question/61361 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61361/do-all-possible-trees-arise-as-orbit-trees-of-some-permutation-groups Do all possible trees arise as orbit trees of some permutation groups? Mingzhi Xuan 2011-04-12T04:02:55Z 2011-04-24T23:58:12Z <h2>I.Motivation from descriptive set theory</h2> <p>(Contains some quotes from Maciej Malicki's paper.)</p> <p>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.</p> <p>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 <em>orbit tree</em> of G is well-founded, i.e. every branch of the tree terminates at some finite level, where the concept <em>orbit tree</em> is defined as following.</p> <hr> <h2>II.The problem</h2> <p>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).</p> <p>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$.</p> <p>Assuming $G$ is transitive, this process defines a map from $G$ to a rooted tree $T_G \subset\omega^{&lt;\omega}$. We say it is the <em>orbit tree</em> 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</p> <blockquote> <p>For every tree $T\subset\omega^{&lt;\omega}$, is there a group $G$ such that the orbit tree $T_G$ is isomorphic to $T$? Can we construct it?</p> </blockquote> <hr> <h2>III.Some attempts</h2> <p>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 <em>ad hoc</em>.</p> <p>I also received a generous hint from an expert, saying that</p> <blockquote> 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. <p><p> 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. <p><p> 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$? <p><p> 4.If the answers to these questions are yes, I think that you can then prove what you want. </blockquote> <p>It is not easy for me to comprehend his thought since I have no training in free groups. I have some vague doubts that</p> <ol> <li><p>What is the action of $G$ on countably many things? $G$ naturally acts on itself by concatenation but this seems not correct.</p></li> <li><p>Why must such an $H$ be a one-point stabilizer?</p></li> <li><p>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.</p></li> </ol> <hr> <h2>IV.Possible modifications of the problem (not strict)</h2> <p>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.</p> <p>To realize the tree, we may also choose to fix finitely many points at one time if necessary.</p> <p>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</p> <blockquote> <p>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}$?</p> </blockquote> <p>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.</p> <p>Please do not laugh at my silliness if I am miserably wrong :-P Thank you so much for your time and effort.</p>