tailieunhanh - Báo cáo toán học: "Asymptotics of generating the symmetric and alternating groups"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Asymptotics of generating the symmetric and alternating groups. | Asymptotics of generating the symmetric and alternating groups John D. Dixon School of Mathematics and Statistics Carleton University Ottawa Ontario K2G 0E2 Canada jdixon@ Submitted Jul 18 2005 Accepted Oct 8 2005 Published Nov 7 2005 MSC 2000 Primary 20B30 Secondary 20P05 05A16 20E05 Abstract The probability that a random pair of elements from the alternating group An generates all of An is shown to have an asymptotic expansion of the form 1 1 n 1 n2 4 n3 23 n4 171 n5 . . This same asymptotic expansion is valid for the probability that a random pair of elements from the symmetric group Sn generates either An or Sn. Similar results hold for the case of r generators r 2 . 1 Introduction In 5 I proved that the probability that a random pair of elements from the symmetric group Sn will generate either Sn or An is at least 1 2 loglogn 2 for large enough n. This estimate was improved by Bovey and Williamson 3 to 1 exp ylog n . Finally Babai 1 showed that the probability has the asymptotic form 1 1 n O 1 n2 . Unlike the earlier estimates the proof of Babai s result uses the classification of finite simple groups. Babai s result depends on two elementary results from 5 namely the probability tn that a pair of elements in Sn generates a transitive group is 1 1 n O 1 n2 and the probability that a pair of elements generates a transitive imprimitive group of Sn is n2-n 4. Using the classification he shows that the probability that a pair of elements generates a primitive subgroup of Sn different from An or Sn is n n for all sufficiently large n. Thus the probability that a pair of elements of Sn generates a transitive group but does not generate either Sn or An is O n2-n 4 n n O n-k for all k. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R56 1 The object of the present paper is to show that there is an asymptotic series of the form tn 1 V ck nk so that tn 1 ci n C2 n2 . cm nm O 1 nm 1 for m 1 2 . . By what we have just said the same asymptotic series is .