ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 237-244 https://doi.org/10.26493/1855-3974.1664.4b6 (Also available at http://amc-journal.eu) Comparing the expected number of random elements from the symmetric and the alternating groups needed to generate a transitive subgroup Andrea Lucchini, Mariapia Moscatiello Université degli Studi di Padova, Dipartimento di Matematica "Tullio Levi-Civita" Received 5 April 2018, accepted 29 May 2018, published online 23 December 2018 Given a transitive permutation group of degree n, we denote by ey(G) the expected number of elements of G which have to be drawn at random, with replacement, before a set of generators of a transitive subgroup of G is found. We compare ey (Sym(n)) and Keywords: Transitive groups, generation, expectation. Math. Subj. Class.: 20B30, 20P05 1 Introduction Let n e N and suppose that we are in the following situation. There are two boxes, one is blue and one is red. The balls in the blue box correspond to the elements of Sym(n), the balls in the red box correspond to the elements of Alt(n). We choose one of the boxes, and then we extract balls from the chosen box, with replacement, until a transitive permutation group of degree n is generated. In order to minimize the number of extractions, is it better to choose the red box or the blue one? We are going to prove that the answer depends on the parity of n. If n is even the best choice is the blue box, if n is odd the red one. In order to formulate and discuss this problem in an appropriate way, we need to introduce some definitions. Let G be a transitive permutation group of degree n and x = (xm)meN be a sequence of independent, uniformly distributed G-valued random variables. We may define a random variable tg by setting tg = min{t > 1 | (xi,..., xt) is a transitive subgroup of Sym(n)} e [1, E-mail addresses: lucchini@math.unipd.it (Andrea Lucchini), moscatie@math.unipd.it (Mariapia Moscatiello) Abstract eT (Alt(n)). ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 234 Ars Math. Contemp. 16(2019)215-238 We denote with ex (G) = J21> i tP (tg = t) the expectation of the random variable tg. Thus ex(G) is the expected number of elements of G which have to be drawn at random, with replacement, before a set of generators of a transitive subgroup of G is found. The case when G = Sym(n) has been studied in [2, Section 5]. Denote by nn the set of partitions of n, i.e. nondecreasing sequences of natural numbers whose sum is n. Given w = (ni,..., nfc) G n„ with ni — • • • — nk1 > nk1+1 — • • • — n^+k2 > • • • > nfci +-----hkr-1 + i — • • • — nkt+-----+kr define — (-1)k-1(k - 1)!, n! l(w) — —i—i-1' ni!n2! • • • nk! v(w) — ki!k§! • • • kr!. It turns out (see [2, Theorem 9]) that for every n > 2, ^(w)t(w)2 ex (Sym(n)) = - in. V(w)(i(w) - 1)J where n^ is the set of partitions of n into at least two subsets. The aim of this paper is to consider the case G — Alt(n). Our main result is the following. Theorem 1.1. For every natural number n > 3 (-1)n+1n!(n - 1)! eT(Sym(n)) - ex(Alt(n)) = (n! - 1)(n! - 2) ' So the difference (Sym(n)) - (Alt(n)) tends to zero when n tends to infinity, but it is positive if n is odd and negative otherwise. To explain this behaviour notice that, if G < Sym(n), then P(tg — 1) concides with the probability Pt(G, 1) that one randomly chosen element g in G generates a transitive subgroup of Sym(n), i.e. that g is an n-cycle: in particular Pt(Sym(n), 1) — 1/n, Pt(Alt(n), 1) — 2/n if n is odd and PT(Alt(n), 1) — 0 if n is even. In [2, Section 5], it is proved that eT(Sym(n)) — 2 and 7982 2 — eT(Sym(2)) < eT(Sym(n)) < eT(Sym(4)) — 7982 ~ 2.1033. 3795 A similar result can be obtained in the alternating case. Theorem 1.2. Assume n > 3. 1. If n is odd, then § — eT(Alt(3)) < eT(Alt(n)) < 2. 2. If n is even, then 2 < eT(Alt(n)) < eT(Alt(4)) — 3ff - 2.3879. Moreover lim„^TO ct(Alt(n)) — 2. A. Lucchini andM. Moscatiello: Comparing the expected number of random elements from ... 239 2 Proof of Theorem 1.1 Let A = (X, <) be a finite poset. Recall that the Möbius function on the poset A is the unique function : X x X ^ Z, satisfying ^(x, y) = 0 unless x < y and the recursion formula y^ ^ I 1 if X = Z, y^L ' 10 otherwise. Let G be a transitive subgroup of Sym(n). We denote with Pq(G, t) the probability that t randomly chosen elements of G generate a transitive subgroup of Sym(n). Notice that tg > t if and only if (xi,..., xt) is not a transitive subgroup of G, so we have P(rG >t) = 1 - Pq(G, t). We get that eT (G) = E tP (tg = t) = E iE P (tg = m) t>1 t>1 \m>t (2.1) = EP(tg ^ t) = EP(tg > t) = E(! - Pt(G, t)). t>1 t>0 t>0 Consider the poset XG of the intransitive subgroups of G, let be the set of subgroups of G than can be obtained as intersection of maximal elements of the the poset XG, and let JG = IG U {G}. From [1, Section 2] we have that D triv^ PT,G(H,G) sr-^ ^T,G(H, G) PT(G,t)= ^ |G: H|t = ^ |G: H|t , HeLr(G) 1 1 HeJG 1 1 where ^T,G denotes the Mobius function on the lattice Lt(G) = XG U {G}. So in order to compute the function Pt(G, t) we need information about the subgroups in JG. Let Pn be the poset of partitions of {1,..., n}, ordered by refinement. The maximum i of Pn is {{1,..., n}} (the partition into only one part), while the minimum 0 is {{1}, {2},..., {n}} (the partition into n parts of size 1). The orbit lattice of G is defined as Pn(G) = {a G Pn | the orbits of some H < G are the parts of a}. If a = {Q1,..., Qfc} G Pn, then we define G(a) = (Sym(Q1) x • • • x Sym(Qfc)) n G. If a G Pn(G), then G(a) is the maximal element in the lattice of those subgroups of G whose orbits are precisely the parts of a. Notice that H G JG if and only if there exists a G Pn(G) with H = G(a); moreover ^t,G(G(a), G) = ^pn(G)(a, 1) so P (G t) V^ MPn(G)(a,1) (2 2) Pt(G,t)= ^ |G : G(a) |t . (2.2) ^ePn(G) | v y| We want now to use (2.2) in order to compute Pt(Sym(n), t) - Pt(Alt(n), t). Let P2,n be the subset of Pn consisting of the partitions of {1,..., n} into n - 1 parts (one of size 2, the others of size 1) and let = P2,n U {°}. The following two lemmas are immediate but crucial in our computation. 234 Ars Math. Contemp. 16(2019)215-240 Lemma 2.1. P„(Sym(n)) = P„ andP„(Alt(n)) = P„ \ Lemma 2.2. If a eVn \ P|,„, then 1. MP„(Sym(n))(a, 1) = MP„(Alt(n)) (a, 1) = MPn (a> 2. | Sym(n) : Sym(n)(a)| = | Alt(n) : Alt(n)(a)|. Lemma 2.3. We have 1. MP„(Sym(n))(Ö, i) = (-1)n-1(n - 1)!; 2. MP„(Ait(n))(Ö, i) = (-1)n-1(n - 1)! + ^^. Proof. We use the following known result (see for example [3, p. 128]): ({fii,..., Qfc}, 1) = (-1)k-1(k - 1)!. (2.3) This immediately implies MPn(Sym(n))(Ö, 1) = MPn (Ö, 1) = (-1)n-1(n - 1)!. Moreover MP„(Alt(n)) (Ö, Ö) = - 53 ^Pn(Alt(n)) (a? Ö) ff£P„(Alt(n))\{0> = - 53 ^Pn (a> Ö) = - Y^ ^Pn (°"> Ö)+ ^Pn (°"> Ö) = MPn (0, 1)+ ^Pn (a' Ö) = (-1)n-1 (n - 1)! + (n 2) (-1)n-2(n - 2)! ( — 1)n n! = (-1)n-1 (n - 1)! + ( 1)n n!. □ Theorem 2.4. For every natural number n > 2 Pt(Sym(n), t) - PT(Alt(n),t) = (-1)"+1(n -^ - ^. Proof. For every t G N (and using (2.3) and Lemma 2.3) let ni(n t)= V MPn(Sym("))(a 1) n1( ' ) ^ | Sym(n):Sym(n)(a)|4 (-1)n-2(n - 2)!24 _ (-1)n-2(n!)2t (n!)4 2(n!)4 MPn(Sym(n))(Ö , Ö) _(-1)n-1(n - 1)! n2(n ,t) n3(n,t) = r'n(Alt(")^ = (-1)n-1(n - 1)! + m | Alt(n) : Alt(n)(Ö)|* ^ ; v ; | Sym(n) : Sym(n)(Ö)|4 (n!)4 MPn(Alt(„)) (Ö,1) _(. u ,, (-1)n-2n! N( 2 2 t 2 A. Lucchini andM. Moscatiello: Comparing the expected number of random elements from ... 241 From (2.2), Lemma 2.1 and Lemma 2.2, we deduce that MP„(Sym(n))(^, 1) Pt (Sym(n),t) = ]T CT£P„(Sym(n)) E | Sym(n) : Sym(n)(a)|4 MP„(Alt(n))(^, 1) ff£P„(Alt(n)) | Alt(n) : Alt(n)(a)|i + E 1) + ff£?2,„(Sym(n)) MP„(Sym(n))(°, 1) | Sym(n) : Sym(n)(a)|4 MP„(Alt(n))(°, 1) | Sym(n) : Sym(n)(0)|4 | Alt(n) : Alt(n)(0)|t Pt(Alt(n), t) + ni(n,t) + %(n,t) - %(n,t) = Pt (Alt(n), t) + (-1)n(n - 1)!(2t - 1) (n) □ Proof of Theorem 1.1. Using equation (2.1) we obtain that eT(Sym(n)) - eT(Alt(n)) = E (Pt(Alt(n),t) - Pt(Sym(n),t)) t> 0 E t0 (-1)"+1(n - 1)!(2t - 1) (n) (-i)"+1(« -1)! |£ (£)t - E t = (-1)"+1(n - 1)! . n! . ,t>0 v 7 t>0 n! n! n! 2 n! 1 (-1)n+1n!(n - 1)! (n! - 1)(n! - 2) ' □ 3 Examples In this section we want to verify Theorem 1.1 in the particular case when n G {3,4} using some direct, elementary arguments to compute eT(Sym(n)) and eT(Alt(n)). First assume n = 3. Notice that rAlt(3) is a geometric random variable with parameter 2, so eT(Alt(3)) = 2' To generate a transitive subgroup of Sym(3) first of all we have to search for a nontrivial element of Sym(3). The numbers of trials needed to obtain a nontrivial element x of Sym(3) is a geometric random variable of parameter |: its expectation is equal to E0 = | .If this element has order 3, we have already obtained a transitive subgroup. However, with probability p1 = §, the nontrivial element x is a transposition: in this case in order to generate a transitive subgroup we need to find an element y G (x) and the number of trials needed to find y G (x) is a geometric random variable with parameter 2 and expectation E1 = 2. Definitely 6 3 3 21 eT(Sym(3)) = E + P1E = - + - • - = -. 5 5 2 10 234 Ars Math. Contemp. 16(2019)215-242 In particular 913 3 eT(Sym(3)) - eT(Alt(3)) = - - - = -, according with Theorem 1.1. Now assume n = 4. The transitive subgroups of Alt(4) are the noncyclic subgroups. Thus the subgroup (xi,..., xt) of Alt(4) is transitive if and only if there exist 1 < i < j < t such that xj = 1 and xj (xj). The numbers of trials needed to obtain a nontrivial element x of Alt(4) is a geometric random variable of parameter 12 and expectation E0 = 11. With probability p1 = H the nontrivial element x has order 2: in this case the number of trials needed to find an element y ^ (x) is a geometric random variable of parameter 10 and expectation E1 = 12 .On the other hand, with probability p2 = ii the nontrivial element x has order 3: in this second case the number of trials needed to find an element y ^ (x) is a geometric random variable of parameter 12 and expectation E2 = 12. Thus 394 eT (Alt(4)) = Eo + P1E1 + p2E2 = —. 165 The case of Sym(4) is more complicated. To generate a transitive subgroup of Sym(4) first of all we have to search for a nontrivial element of Sym(4). The numbers of trials needed to obtain a nontrivial element x of Sym(4) is a geometric random variable of parameter 23: its expectation is equal to E0 = |0 .If x is a 4-cycle, then we have already generated a transitive subgroup. With probability p1 = 23, x is a product of two disjoint transposition: in this case to generate a transitive subgroup it is sufficient to find an element y ^ (x) and the number of trials needed to find such an element is a geometric random variable of parameter 20 and expectation E1 = 24. With probability p2 = , x is a 3-cycle: to generate a transitive subgroup we need an elements y which does not normalizes (x): the number of trials needed to find such an element is a geometric random variable of parameter 14 and expectation E2 = 11. Finally, with probability p3 = 23, x is a transposition. To find an element y ^ (x) we need E3 = 22 trials. If y is a 4-cycle or a 3-cycle with | supp(y) n supp(x)| = 1 or a product of two disjoint transpositions (a, b) (c, d) with x {(a, b), (c, d)}, then we have already generated a transitive subgroup. With probability q1 = 22, (x, y) is an intransitive subgroup of order 4: to generate a transitive subgroup we need an elements z (x, y). The number of trials needed to find such an element is a geometric random variable of parameter 20 and expectation E2 = 20. With probability q2 = 22, (x, y) = Sym(3) and to generate a transitive subgroup we need other E| = 28 trials. Definitely eT (Sym(4)) = Eo + P1E1 + P2E2 + ps(E3 + 91 Ei + 92 E2) 24 3 24 8 24 6 (24 2 24 8 24 A 7982 + ™ • ™ + ™ • ttt + ™ ™ + ™ • ™ + 23 23 20 23 18 23 122 22 20 22 18 / 3795 In particular 7982 394 72 eT(Sym(4)) - eT(Alt(4)) = 3795 165 253 according with Theorem 1.1. A. Lucchini andM. Moscatiello: Comparing the expected number of random elements from ... 243 4 Proof of Theorem 1.2 Lemma 4.1. Let e = 0 if n is even, e =1 if n is odd. Then ,, 2e 1 2 3n eT(Alt(n)) < 2 - 2_ +-_ + _-+ _-^-. n n — 1 n(n — 1) — 2 n(n — 1)(n — 2) — 6 Proof. Since an element of Alt(n) generates a transitive subgroup if and only if it is a cycle of length n, we have that P^(Alt(n), 1) = 2e/n. Let now t > 2 and let X\ , . . . , Xt £ Alt(n) and Y = (xi,... ,xt) < Alt(n). If Y is contained in an intransitive maximal subgroup, then Y is contained in a subgroup conjugate to Sym(k) x Sym(n — k) for some 1 < k < LJ. Let k g {1,..., n — 1}. The probability that Y is contained in a subgroup conjugate to Sym(k) x Sym(n — k) is bounded by (k) t. So , ) i-t 1 — Pt(Alt(n), t) < ]T Notice that Ef n\ 1 t n /n 1 t 1 \k) < 2V3, 30 = (1 — Pt (Alt(n), 0)) + (1 — Pt (Alt(n), 1)) + £(1 — Pt (Alt(n), t)) t> 2 < 2—i+§( n1-•+(n)1-'+n (3)1-N 2e 1 1 n 1 = 2 — - + -r + 7n-7 + n - 1 (2) - 1 2 (3) - 1 _ 2e 1 2 3n n n — 1 n(n — 1) — 2 n(n — 1)(n — 2) — 6 Proof of Theorem 1.2. Let = ( — 1)"+1n!(n — 1)! f(n)= (n! — 1)(n! — 2) ' In [2, Section 5] it has been proved that limn^w (Sym(n)) = 2. This implies lim ex(Alt(n)) = lim (ex(Sym(n)) — f(n)) = lim ex(Sym(n)) — lim f (n) = 2. n^w n^w n^w n^w Moreover, again by [2, Section 5], if n > 2, then 2 < eT(Sym(n)) < eT(Sym(4)) - 2.1033. (4.1) 1 5. Notice that |f (n)| is a decreasing function and that f (n) < 0 if n is even, f (n) > 0 otherwise. Assume that n is even: ex(Alt(n)) = ex(Sym(n)) - f (n) > 2 - f (n) > 2, ex(Alt(n)) = ex(Sym(n)) - f (n) < ex(Sym(4)) - f (4) = ex(Alt(4)). Assume that n is odd: it follows immediately from Lemma 4.1, that ex(Alt(n)) < 2 if n > 9. Moreover eT (Alt(5)) eT (Alt(7)) 2205085 1.8842, 1170324 1493015628619946854486 779316363245447358045 1.9158. Finally 1440 3 eT(Alt(n)) = eT(Sym(n)) - f (n) > 2 - f (5) > 2 - — > 3 = eT(Alt(3)). □ References [1] E. Detomi and A. Lucchini, Some generalizations of the probabilistic zeta function, in: T. Hawkes, P. Longobardi and M. Maj (eds.), Ischia Group Theory 2006, World Scientific Publishing, Hackensack, NJ, 2007 pp. 56-72, doi:10.1142/9789812708670_0007, proceedings of the conference in honor of Akbar Rhemtulla held in Ischia, March 29 - April 1, 2006. [2] A. Lucchini, The expected number of random elements to generate a finite group, Monatsh. Math. 181 (2016), 123-142, doi:10.1007/s00605-015-0789-5. [3] R. P. Stanley, Enumerative Combinatorics, Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997, doi:10.1017/ cbo9780511805967.