JOURNALOFTHE AMERICANMATHEMATICALSOCIETY Volume18,Number1,Pages157–192 S0894-0347(04)00467-9 ArticleelectronicallypublishedonSeptember2,2004 DIMENSION AND RANDOMNESS IN GROUPS ACTING ON ROOTED TREES MIKLO´SABE´RTANDBA´LINTVIRA´G 1. Introduction Let T = T(d) denote the infinite rooted d-ary tree and let H ⊆ Sym(d) be a permutation group. Let W(H) denote the infinite iterated wreath product of H acting on T with respect to H. For example, W(Sym(d)) is the full automorphism group of T(d). Let W (H) denote the n-fold wreath product of H, acting on T , n n the d-ary tree of depth n. The case H = C , the cyclic group of order p, is of particular interest. The p pro-p group W(p) = W(C ) obtained this way is called the group of p-adic auto- p morphisms. The groupW (p)is calledthe symmetric p-group ofdepthn, asitcan n also be obtained as the Sylow p-subgroup of the symmetric group Sym(pn). The first goal of this paper is to analyze the elements of W(H). We answer a question of Tura´n (see P´alfy and Szalay [1983]), which asks for an analogy of the famous theorem of Erd˝os and Tura´n [1965] about the distribution of orders of random elements in Sym(n). Let pKn denote the order of a random element of the symmetric p-groupWn(p) andletα bethe solutionoftheequationα(1−α)1/α−1 =1−1/pintheopenunit p interval. Theorem 1. We have K /n→α in probability. n p A similar result holds for general H (see Section 2). The proof of this theorem depends on a new measure-preserving bijection between conjugacy classes of ran- domelementsandGalton-Watsontrees,bringingthetheoryofstochasticprocesses to bear upon the subject. Theorem 1 was conjectured by Pa´lfy and Szalay [1983]; they proved the upper bound and that the variance of K remains bounded as n n → ∞. Puchta [2001] showed that the limit in Theorem 1 exists. In a related recentpaper, Evans [2002] studies the randommeasure givenby the eigenvalues of the natural representation of W (H). n ReceivedbytheeditorsFebruary16,2003. 2000 Mathematics Subject Classification. Primary 20E08, 60J80, 37C20; Secondary 20F69, 20E18,20B27,28A78. Key words and phrases. Groups acting on rooted trees, Galton-Watson trees, Hausdorff di- mension,prop-groups,genericsubgroups,symmetricp-group. The first author’s research was partially supported by OTKA grant T38059 and NSF grant #DMS-0401006. The second author’s research was partiallysupported by NSF grant #DMS-0206781 and the CanadaResearchChairprogram. (cid:1)c2004M.Ab´ertandB.Vir´ag 157 158 MIKLO´SABE´RTANDBA´LINTVIRA´G The next goal is to understand the subgroup structure of W(p). Since every countablybasedpro-pgroupcanbeembeddedintoW(p),weinvestigatesubgroups according to their Hausdorff dimension. We show that the Hausdorff spectrum for the closure of subgroups generated by 3 elements is the whole unit interval. More precisely, Theorem 2. For each λ∈[0,1] there exists a subgroup G⊆W(p) generated by 3 elements such that the closure of G is λ-dimensional. ThisresultleadstothesolutionofaproblemofShalev[2000],whoaskedwhether a finitely generated pro-p group can contain finitely generated subgroups of irra- tional Hausdorff dimension. Inthecontextofpro-finitegroupsHausdorffdimensionwasintroducedbyAber- crombie[1994]. ItwasdeeplyanalyzedbyBarneaandShalev[1997](seealsoShalev [2000] and Barnea et al. [1998]). They show that for closed subgroups, Hausdorff dimensionagreeswiththe lowerMinkowski(box)dimension. Inthe caseofW(H), thiscanbe computedfromthesizeofthecongruencequotientsG =GW[n]/W[n], n where W[n] denotes the stabilizer of level n in W. In fact, dim G is given by the H liminf of the density sequence (1) γ (G)=log|G |/log|W |. n n n Forinstance,theclosureofGrigorchuk’sgroup,asubgroupofW(2),hasdimension 5/8. Theorem2 is obtainedusing probabilisticmethods. These methods give the fol- lowinganalogueofthetheoremofDixon[1969]sayingthattworandomelementsof Sym(n) generate Sym(n) or the alternating group Alt(n) with probability tending to 1. Perhaps surprisingly, no deterministic construction is known for large sub- groupsofW (p)withaboundednumber ofgeneratorsasinthe followingtheorem. n Theorem3. Letε>0. LetGn bethesubg(cid:1)roupgeneratedbyth(cid:2)reerandomelements of the symmetric p-group W (p). Then P |G |>|W (p)|1−ε →1 as n→∞. n n n For the infinite group W(p), this takes the following form: with probability 1, three random elements generate a subgroup with 1-dimensional closure (see The- orem 7.2). We conjecture that the same holds for two elements instead of three. Since three random elements generate a spherically transitive subgroup with posi- tive probability, and W(p) is not topologically finitely generated, the above result shows the existence of a rich family of topologically finitely generated transitive full-dimensional subgroups of W(p). The analysisof randomlygeneratedsubgroupsallowsus to answera questionof Sidki [2001]. He asked whether the binary odometer (a.k.a. adding machine), an elementthatactsoneverylevelofT(2)asafull cycle,canbeembeddedinto afree subgroup of W(2). Call a subgroup G⊆W(H) strongly free if it is free and every nontrivial element fixes only finitely many vertices. For instance, both the trivial group and the cyclic subgroup generated by the odometer have this property. Theorem 4. Let G ⊆ W(H) be a strongly free subgroup and let g ∈ W(H) be a random element. Then the group (cid:5)G,g(cid:6) is strongly free with probability 1. Next,weexploreageneraldimensiontheoryofgroupsactingontherootedtrees T(p). The first result in this direction shows that closed subgroups of W(p) are ‘perfect’ in the sense of Hausdorff dimension. Recall that G(cid:1) denotes the derived subgroup of the group G. GROUPS ACTING ON ROOTED TREES 159 Theorem 5. Let G⊆W(p) be a closed subgroup. Then lim(γ (G)−γ (G(cid:1)))=0. n n In particular, dim G=dim G(cid:1). H H Asacorollary,solvablesubgroupsarezero-dimensional,andpositive-dimensional closed subgroups cannot be abstractly generated by countably many solvable sub- groups. Unlike the infinite group W(p), the finite symmetric p-groups W (p) do have n largeAbeliansubgroupsofdensity 1−1/p. However,they cannotbe gluedto form a large subgroup of W(p). The following theorem explains the background of this phenomenon. Theorem(cid:3)6. Let G ⊆ W(p) be a solvable subgroup with solvable length d. Then we have ∞ γ (G)≤Cd, where C is a constant depending on p only. n=0 n OnemotivationtostudydimensionofsubgroupsinW(p)comesfromthetheory of just infinite pro-p groups, which are regarded as the simple groups in the pro-p category. A group G is just infinite if every proper quotient of G is finite. By the characterizationofGrigorchuk[2000](whichisbasedonWilson[1971]),groupswith this property fall into two classes: one is the so-calledbranchgroups,which havea natural action on T(p) (see Section 9 for details). Boston [2000] suggests a direct connection between Grigorchuk’s classes and Hausdorff dimension; he conjectures that a just infinite pro-p group is branch if and only if it has an embedding into W(p) with positive-dimensional image. Inthefollowingwecontrastknownresultsaboutbranchgroupswithnewresults on 1-dimensional subgroups. We first show the following. Theorem 7. Let G ⊆ W(p) be a spherically transitive 1-dimensional closed sub- group. Then every nontrivial normal subgroup of G is 1-dimensional. It wouldbe interesting to see whether a similarresultholds for sphericallytran- sitive positive-dimensional closed subgroups. Wilson [2000] conjectured that every just infinite pro-p branchgroup contains a nonabelian free pro-p subgroup. An affirmative result is known if the group is not virtually torsion-free (see Grigorchuk et al. [2000a]). Another beautiful result in this vein is given by Zelmanov [2000] on groups satisfying the Golod-Shafarevich condition. In light of Boston’s conjecture it is natural to formulate the following. Conjecture 8. Let G⊆W(p) be a positive-dimensional closed subgroup. Then G contains a nonabelian free pro-p subgroup. This might be more attackable than Wilson’s originalconjecture. A step in this direction is the following. Theorem 9. Let G ⊆ W(p) be a spherically transitive 1-dimensional closed sub- group. Then G contains a nonabelian free pro-p subgroup. Another measure of largenessfor profinite groups is whether they contain dense freesubgroups(seePyberandShalev[2001]andSoiferandVenkataramana[2000]). Wilson [2000] showed that just infinite pro-p branch groups contain dense free subgroups. Let d(G) denote the minimal number of topological generators for G, which may be infinite. Theorem10. LetG⊆W(p)beaclosedsubgroupofdimension 1andletk ≥d(G). Then G contains a dense free subgroup of rank k. 160 MIKLO´SABE´RTANDBA´LINTVIRA´G In other words, the free group F is residually S, where S denotes the set of k congruence quotients of G. A common tool throughout the paper is the so-called orbit tree of a subgroup G ⊆ W(H), the quotient graph of T modulo the orbits of G. Orbit trees reflect the conjugacy relation (see Gawron et al. [2001]) and can be used to describe the structure of Abelian subgroups in W(p) (see Section 8). The key observation leading to Theorem 1 is the fact that the orbit tree of a random element is a Galton-Watson tree. A crucial step in Theorems 3 and 4 is that the orbit tree of a randomly generated subgroup has finitely many rays with probability 1, i.e., the closurehasfinitely manyorbitsonthe boundaryofT (Proposition3.10). Theorem 5 also traces back to estimates on orbit trees. Another tool used in the paper is word maps between the spaces W(p)k. A nontrivialwordw∈F canbethoughtofasamapW(H)k →W(H)viaevaluation. k Bhattacharjee[1995]provedthatrandomsubstitutionintoawordmapgives1with probability 0, or equivalently, the kernel of the map has Haar measure zero. As a result,randomelementsofW(H)generateafreesubgroupwithprobability1. The key result leading to Theorem 10 is the following generalization. Theorem 11. The kernel of a word map is not full dimensional in W(H)k. Another generalization leading to Theorem 4 is that random evaluation of a word map yields an element of W(H) which fixes only finitely many vertices with probability 1. Thestructureofthepaperisasfollows. Section2containstheproofofTheorem 1. Italsointroducesnotationanddiscussesconjugacyclassesandrandomelements inW(H). Section3discussestheorbitstructureofrandomsubgroups. InSection4 weexplorewordmapsandproveTheorems4and11. Sections5and6introducethe technical tools needed for proving Theorem 3, which is done in Section 7. Section 8 discusses small subgroups, and covers Theorems 5 and 6. Section 9 is about high-dimensional subgroups, and contains the proofs of Theorems 7, 8, 9, and 10. 2. Elements This section studies the statistical properties of elements of W(p). Random elements are described via the family tree of a Galton-Watson branching process. This allows us to answer Tura´n’s question (see Theorem 1). We first describe our notation for (iterated) wreath products. Let (H ,X ), i i 1 ≤ (cid:5) ≤ n, be a sequence of permutation groups where n might be infinite. Let d =|X |. For 0≤(cid:5)≤n, define the level (cid:5) as i i ∂T :=X ×...×X , (cid:3) 1 (cid:3) andthe tree T whichhas vertex setV(T ) givenby elements of the disjointunion n n of all levels. The sequence w ∈V(T ) is a child of v ∈V(T ) (or v is the parent of n n w) if w begins as v and has one extra element. The edge set E is the collection of {v,w} for all such v,w. Consider a map g that for each (cid:5)<n maps (2) ∂T →H . (cid:3) (cid:3)+1 Let W be the set of all such maps. An element g ∈ W acts on T bijectively via n the rule (3) (x ,...,x )g :=(xg(()),xg((x1)),...,xg((x1,...,x(cid:1)−1))), 1 (cid:3) 1 2 (cid:3) GROUPS ACTING ON ROOTED TREES 161 andW =H (cid:9)...(cid:9)H iseasilycheckedtobeasubgroupofAut(T ). Thisconstruc- n 1 n tionalsoworksinthecasen=∞,andthe notationW =...(cid:9)H (cid:9)H iscompatible 2 1 with the right actions we are considering. Ifnisfinite,thenthegroupstructureofW doesnotdependonthepermutation n representation of the last group H on Sym(n), only on the abstract structure of n H . This defines K (cid:9) H, where K is an abstract group. When we talk about n g ∈ H (cid:9)H , the wreath product of two groups, we will often use the shorthand 2 1 g(x) for g((x)), where x∈X . The rule (3) yields the multiplication rule 1 (gh)(x)=g(x)h(xg). WewillusethenotationW (H)forthewreathproductofncopiesofapermutation n group(H,X), and the shorthandW(H)=W∞(H). The most importantcasesare the symmetric p-group W (C ) and the full automorphism group W (Sym(d)) n p n of T . n If G is a group,and S ⊂G, then (cid:5)S(cid:6) denotes the groupabstractly generated by S, that is, the set of elements that can be obtained from S via repeated group operations. If G is a topological group, then we call the closure (cid:5)S(cid:6) the group topologically generated by S. Let G be a group acting on a tree T. Definition 2.1. The orbit tree of the group G is the quotient graph T of T G modulo the set of orbits of G. It is easy to check that orbit trees are in fact trees. For the purpose of Proposition 2.3 the orbit trees of group elements need to contain more information about the local structure of automorphisms. Let v be a vertex of a tree T = X∞, and let k denote the length of the orbit of v under an automorphismg. Then gk acts onthe child edges of v, which are labeled naturally by elements of X. Let (cid:5) (e) ⊆ X denote the orbit of the child edge e. For a set g (e.g. orbit) E of edges at the same level, let (cid:5) (E)=(cid:5) (e) for the lexicographically g g smallest e∈E. Definition2.2. Theorbittreeofatreeautomorphismgisthequotientgraph T of T modulo the set of orbits of g, together with the labeling (cid:5) of the edges of g g T . g The orbit tree of g ∈W(H) is an H-labeled tree, defined as follows. An H-labeled tree is a rootedtree together with anedge-labeling(cid:5) so that for v ∈V, (cid:5) is a bijection between the child edges of v and the cycles of some h ∈H. v Two H-labeled trees are called equivalent if (1) there exists a graph isomor- phism v (cid:11)→v(cid:1), e(cid:11)→e(cid:1) between them, and (2) for each v, there exists an h ∈H so v that (cid:5)(e(cid:1))=(cid:5)(e)hv for all child edges e(cid:1) of v(cid:1). The following extension of a theorem of Sushchansky [1984] is not difficult to check, and motivates the notion of orbit trees. Proposition 2.3. Two elements of W(H) are conjugates if and only if their orbit trees are equivalent. In most important cases, equivalence is only a little more than graph isomor- phism. We say that two labellings of a tree are equivalent if they define equivalent H-labeled trees. In the case H = Sym(d), two labellings are equivalent iff the length of the edge label cycles agree. In this case, it suffices to label edges by the 162 MIKLO´SABE´RTANDBA´LINTVIRA´G cycle lengths. If H = C , then any two labellings are equivalent. If H = C for 2 p p prime, then each vertex has either 1 or p children, and labeling is the same as cyclicly ordering the children whenever there are p of them. We now turn to the description of the orbit trees of random elements. Our conventionis that unless otherwise specified, the term random elements denotes independent random elements chosen according to uniform (in the infinite case Haar) measure. Definition 2.4. Labeled Galton-Watson (GW) trees. Let L¯ be the set of finite sequenceswithelementsfromasetoflabelsL,andletν beaprobabilitydis- tributiononL¯. We define the probabilitydistributionGW(ν) oninfinite trees with edges labeled by L by the following inductive construction. In the first generation, wehave1individual. Giventhe individualsatleveln,eachofthemhas asequence of child edges picked from the distribution ν independently. The other endpoints of the child edges form generation n+1. Note that the unlabeled tree is just a classical Galton-Watson process; once the unlabeledtreehasbeenlaiddown,eachfamilyislabelledindependentlyatrandom using a mechanism that only depends on the family size. Let(H,X)beapermutationgroup,andletν bethedistributionofthesequence H of orbits of a uniform random element. Proposition 2.5 (Random elements and GW trees). If g ∈ W(H) is a Haar random element, then the distribution of the orbit tree T is GW(ν ). g H Proof. We prove this by induction. The inductive hypothesis is that the first n levels of T have the same distribution as the first n levels of a GW(ν ) tree. g H Indeed, suppose this is true for n. Let w = (v,...,vgk−1) ∈ T be an orbit of g an element on level n of T. Then the child edges of w in T correspond to, and g are labeled by, orbits of gk(v). But gk(v) = g(v)g(vg)...g(vgk−1), and the factors on the right-hand side are chosen independently uniformly from H, which implies that their product also has uniform distribution. (cid:1) The simplest consequence of this is the following asymptotic law. Let r(H) denote the permutation rank of H, i.e. the number of orbits of the action of H on pairs of elements of X (e.g. r(H)=2 if H is 2-transitive on X). Corollary2.6. LetthegroupH betransitiveonX,andletg ∈W (H)berandom. n n Then as n→∞, nP(g fixes a vertex on level n)→2/(r(H)−1). n Proof. Let N be the number of fixed points of a random element of H on X; then it is well known that EN =1, EN2 =r, so Var N =r−1. A vertex at level n of T corresponds to a fixed point if and only if all of its gn ancestor edges are labeled by a fixed point. This happens if it lies in the subtree of T gained by removing all descendant subtrees which have an ancestor edge gn not labeled by a fixed point. Such a subtree has Galton-Watson distribution with branchingstructure givenby the number of fixed points N ofa randomelement in H. Since EN = 1, this is a critical tree, so by a theorem in branching processes (see Athreya and Ney [1972]) the probability that it survives until generation n is asymptotic to 2/(nVarN), proving the corollary. (cid:1) GROUPS ACTING ON ROOTED TREES 163 The following corollary is immediate. Corollary 2.7. Let H be transitive on X, and let g ∈W(H) be chosen according to Haar measure. Then g fixes only finitely many vertices of T with probability 1. Letforanintegern,letp(n)denotethehighestpowerofpdividingn. Leth∈H be a uniform random element, and let p be a prime. Let µ (k) = µ (k) denote p H,p the expected number of orbits v of h with p(|v|) = k. Let µˆ be the generating p function for µ : p (cid:4)∞ µˆ (z)= µ (k)zk p p k=0 and note that the sum has only finitely many nonzero terms. Proposition 2.8. Let g ∈W be a random element, and let n n logµˆ (eλ) p (4) α =min . p λ>0 λ Then Ep(|g |)/n→α and there exist c ,c >0 so that for all n, k we have n p 1 2 P[|p(|gn|)−Ep(|gn|)|≥k]≤c1e−c2k, in particular, Var(p(|g |)) remains bounded. n The bounded variance statement is somewhat surprising, since in most limit theorems variance increases with n (in most cases it is on the order of n). The asymptotics of the order of a typical element is immediate from this result. Corollary 2.9. As n→∞, we have (cid:4) log|g |/n→ α logp n p in probability, where the sum ranges over primes p dividing |H|. As a special case, we get an answer to Tur´an’s question, which we restate here. Let pKn denote the order of a random element of the symmetric p-group Wn(p) and let α be the solution of the equation p (5) α(1−α)1/α−1 =1−1/p in (0,1). Theorem 1. We have K /n→α in probability. n p Tura´n’s goal was to find a natural analogue of the theorem of Erdo˝s and Tura´n [1965] about the asymptotics of the order of a random element in Sym(n). Their paper started the area of statistical group theory. Theorem 1 was conjectured by Pa´lfy and Szalay [1983]; they proved the upper bound and a linear lower bound with a different constant. Puchta [2001] shows that the limit exists. He also stud- ies uniformly randomly chosen conjugacy classes in Puchta [2003]. In a related recentpapermotivatedby randommatrixtheory,Evans[2002]studies the random measure given by the eigenvalues of the natural representation of W (H). n Proof of Theorem 1. H is the cyclic group of order p, so µˆ (z)=1+z(p−1)/p. p 164 MIKLO´SABE´RTANDBA´LINTVIRA´G Let f(λ) = logµˆ (eλ). Then (4) equals the minimum of f(λ)/λ, and setting the p derivative to 0 we get (cid:1) (6) f(λ)/λ=f (λ). At equality, this expression gives α. The right-hand side is the logarithmic deriva- tiveofµˆ (eλ),soitequalsα=(eλ(p−1)/p)/(1+eλ(p−1)/p). Usingthis,weeasily p expressλ andthenf(λ) fromα. Substitution into (6)andalgebraicmanipulations giveEK /n→α , and convergencein probability follows since the variance of K n p n is bounded. (cid:1) For the proof of Proposition2.8, we need to understand the order of an element in terms of its orbit tree. A simple inductive argument shows that if v ∈ T is an g orbit, then its length is given by the product of the lengths of labels on the simple path π((),v) from the root () to v in T : g (cid:5) (7) |v|= |(cid:5)(e)|, e∈π((),v) and therefore (cid:4) (8) p(|v|)= p(|(cid:5)(e)|). e∈π((),v) Proposition 2.11 below shows that all properties about the length of orbits of W can be understood in terms of a branching random walk. n Let {pi}1≤i≤d be a sequence of primes. Consider an orbit o of an action group H on a set X, and let ex(o,X) denote the point in Zd whose ith coordinate is the exponent of the highest power of p dividing |o|. Let ex(H,X) denote the multiset i {ex(o) | o orbit of H}. Definition2.10. Letν beaprobabilitydistributiononthespaceS offinitemulti- sets of elements of Zd. A branching random walk is a probability measure on infinite sequences {Ξ ; n ≥ 0} with elements from S. It is constructed recursively n as follows. At time n=0 we have Ξ ={0}, the set containing the origin. 0 IfΞ isalreadyconstructed,theneachx∈Ξ has“offspring”x+Y ,...,x+Y , n n 1 N where N is random. Here (Y ,...,Y ) is picked from ν independently from the 1 N past and from the offspring of other individuals at time n. Ξ is the multi-set n+1 union of all the offspring of x∈Ξ . n We call the measure (cid:6) (cid:7) (cid:4)N µ(x)=E 1(Y =x) i i=1 the occupation measure of the BRW. Let µˆ denote the generating function for the measure µ. In our case, the relative offspring positions are given by the sequence {(p (|o|),...,p (|o|)) : o orbit of h}, 1 d where h is a uniform random element of H. Proposition 2.11 (Orbit lengths and BRW). Let g ∈ W(H) be a Haar random element, and let Ξ =ex((cid:5)g(cid:6),∂T ). Then {Ξ ; n≥0} is a branching random walk n n n on Zd. Proof. Thisisimmediatefromtheformula(8)andtheproofofProposition2.5. (cid:1) GROUPS ACTING ON ROOTED TREES 165 Since p(|g|) equals the maximum of p(|o|) for the orbits of g, we need to un- derstand the position of the highest element of Ξ . The corresponding questions n forthe branchingrandomwalkhavebeenansweredbyHammersley[1974], Biggins [1977], and Dekking and Host [1991]. The part of their results that is relevant to our setting is stated in the following theorem. Theorem 2.12. Let X denote the position of the greatest individual of a 1- n dimensional BRW whose occupation measure µ has finite support. Let logµˆ(eλ) α= inf . λ>0 λ Then EX /n→α, n and there exist c ,c >0 so that for all n, 1 2 P[|Xn−EXn|≥k]≤c1e−c2n. Here we present a sketch of the proof of the first statement in a simple case. Proof. Let µ∗n(k) denote the expected number of individuals at position k at time n. If we find the highest k for which this quantity is about 1, that means that on average there will be 1 individual at position k, and less than one individual at positions higher than k. Intuitively, this k seems to be a good guess for the position of the highest individual. There are technical arguments to make this intuition rigorous. The next step is to solve µ∗n(k)= k. By considering one step in the branching random walk one discovers the convolution formula (cid:4)k µ∗n(k)= µ∗n−1(j)µ(k−j) j=0 but convolution turns into product for generating functions: µ(cid:8)∗n =µˆn. For exam- ple, for the symmetric p-group, µˆ(z)n =(1+z(p−1)/p)n, and we are left with finding the power k of z for which the coefficient in the above expression is about 1. This gives the approximate equation (cid:9) (cid:10) (cid:9) (cid:10) n p k (9) = , α=k/n, k p−1 and by the Stirling formula the asymptotic version of this equation is (5). For the general case, the theory of large deviations is a standard tool for approximating µ∗n(αn) for large n. (cid:1) 3. Orbit trees of random subgroups Just as for single elements, there is a natural graph structure on the orbits of a subgroupG⊆W(H);seeDefinition2.1. Inthissection,weprovethattheorbittree ofrandomsubgroup(i.e. subgroupsgeneratedbyrandomelements)isamulti-type Galton-Watson tree. As a result, we show that the closure of a random subgroup has finitely many orbits on ∂T with probability 1, and compute the probability that it is transitive. 166 MIKLO´SABE´RTANDBA´LINTVIRA´G The following definition is a generalization of ordinary GW trees to the case when the branching mechanism may depend on the type of the individual. Definition 3.1. Multi-type GW trees. LetΥbeafinite orcountablesetcalled types. Let Υ¯ be a set of finite sequences of Υ. For each y ∈ Υ let µ be a y probability measure on Υ¯. A multi-type Galton-Watson tree GW(µ·) is a random treeconstructedasfollows. The firstgenerationconsistsofanindividualofagiven type y ∈ Υ. Individuals in generation n have children according to the measure µ , where y is the type of the individual. The children of a generation are picked y independently and they form the next generation. Letj ≥1,k ≥0,andlet(H,X)be apermutationgroup. Considerthe actionof the subgroupgeneratedby (j−1)k+1 random elements of H on X. Consider the list of the length of the orbits, and replace each element (cid:5) of this list by (cid:5)k. The distribution of the new list yields a probability measure µ on finite sequences H,j,k of integers. Proposition3.2. LetGbethesubgroupgeneratedbyj randomelementsofW(H). Then TG has multi-type Galton-Watson distribution GW(µH,j,·), where the types correspond to the length of the orbits. First we introduce some notation. Let G = H (cid:9)K be a permutation group, let G denote the stabilizer ofx, andlet G denote the subgroupof elements g ∈G x x+ x for which g(x) = id. The group G /G “ignores” the action everywhere except x x+ at x; it is naturally isomorphic to K. The following observation is immediate. Fact 3.3. Let G⊆W(H), and let T be the descendant subtree of the T at the G,v G orbit w of v ∈T. Then T is isomorphic to T with the labels multiplied by G,v Gv/Gv+ the length of w. Lemma 3.4. Let (H,X) be a permutation group and let K be a group. Consider the subgroup G generated by j Haar random elements of H (cid:9)K. Conditioned on the orbit V of x, G /G has the same distribution as a subgroup generated by x x+ |V|(j−1)+1 random elements of G. The following definition is needed for the proof. Definition 3.5. Let K be a group acting on a set X, and let S be a subset of K. The Schreier graph G(H,X,S) is a directed multi-graph whose vertex set is X, and the edge set is X ×S, where the edge (v,g) connects v to vg. Proof. Let g denote the randomly chosen generators of H. Consider the Schreier i graphG(G,V,{g ,...,g }),andletE denoteitsedgeset. Letπ denotethefunda- 1 j 1 mentalgroupofthe graph. It consistsofequivalence classesofcycles startingfrom x. The cycles may contain an edge in either direction. The equivalence relation is generated by adding or removing immediately retraced steps. It is well known that for a connected graph, π is a free group generated by 1 |E|−|V|+1 elements. Here is one way to specify a set of generators. Take a spanningtreeof(V,E). ForeachedgeeinthesetE ofedgesoutsidethespanning 0 tree,the pathwe followsthepathinthe treefromx toe−,movesalongeandthen back in the tree to x. Clearly, |E |=|E|−|V|+1. 0 Eachpath from x is described by a wordin the generatorsg and their inverses. i If two paths are equivalent, then the corresponding words w have evaluate at x to