JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 28, No 1 (2008)

Persi Diaconis¹ , Jason Fulman² and Robert Guralnick²

¹Department of Mathematics and Statistics Stanford CA 94305 USA
²University of Southern California Department of Mathematics Los Angeles CA 90089-2532 USA

The number of fixed points of a random permutation of {1,2,\cdots , n} has a limiting Poisson distribution. We seek a generalization, looking at other actions of the symmetric group. Restricting attention to primitive actions, a complete classification of the limiting distributions is given. For most examples, they are trivial - almost every permutation has no fixed points. For the usual action of the symmetric group on k-sets of {1,2,\cdots , n}, the limit is a polynomial in independent Poisson variables. This exhausts all cases. We obtain asymptotic estimates in some examples, and give a survey of related results.

1. Aldous, D.: Probability Approximations via the Poisson Clumping Heuristic. Applied Mathematical Sciences, vol.
77. Springer, New York (1989)
2. Arratia, R., Tavaré, S.: The cycle structure of random permutations. Ann. Probab. 20, 1567-1591 (1992)
3. Aschbacher, M.: Finite Group Theory, 2nd edn. Cambridge Studies in Advanced Mathematics, vol.
10. Cambridge University Press, Cambridge (2000)
4. Aschbacher, M.: On the maximal subgroups of finite classical groups. Invent. Math. 76, 469-514 (1984)
5. Aschbacher, M., Scott, L.: Maximal subgroups of finite groups. J. Algebra 92, 44-80 (1985)
6. Babai, L.: On the order of uniprimitive permutation groups. Ann. Math. 113, 553-568 (1981)
7. Barbour, A., Holst, L., Janson, S.: Poisson Approximation. Oxford Science Publications. Clarendon, New York (1992)
8. Baril, J., Vajnovszki, V.: Gray code for derangements. Discrete Appl. Math. 140, 207-221 (2004)
9. Benkart, G., Doty, S.: Derangements and tensor powers of adjoint modules for sln. J. Algebr. Comb. 16, 31-42 (2002)
10. Bidigare, P., Hanlon, P., Rockmore, D.: A combinatorial description of the spectrum of the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99, 135-174 (1999)
11. Bóna, M.: On a balanced property of derangements. Electron. J. Comb. 13, 12 (2006). Research Paper 102 (electronic)
12. Boston, N., Dabrowski, T., Foguel, P., Gies, P., Leavitt, J., Ose, D., Jackson, D.A.: The proportion of fixed-point-free elements of a transitive permutation group. Commun. Algebra 21, 3259-3275 (1993)
13. Bovey, J.: The probability that some power of a permutation has small degree. Bull. Lond. Math. Soc. 12, 47-51 (1980)
14. Buhler, J., Lenstra, H.W. Jr., Pomerance, C.: Factoring integers with the number field sieve. In: The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol.
1554. Springer, Berlin (1993)
15. Cameron, P.: Permutation Groups. London Mathematical Society Student Texts, vol.
45. Cambridge University Press, Cambridge (1999)
16. Cameron, P.: Derangements and p-elements in permutation groups. Online lecture notes (2007), available at:
17. Cameron, P., Cohen, A.M.: On the number of fixed point free elements in a permutation group. Discrete Math. 106/107, 135-138 (1992)
18. Chatterjee, S., Diaconis, P., Meckes, E.: Exchangeable pairs and Poisson approximation. Probab. Surv. 2, 64-106 (2005) (electronic)
19. Chowla, S.: The Riemann zeta and allied functions. Bull. Am. Math. Soc. 58, 287-303 (1952)
20. Cohen, S.D.: The distribution of polynomials over finite fields. Acta Arith. 17, 255-271 (1970)
21. Désarménien, J.: Une autre interprétation du nombre de dérangements. Sém. Lothar. Comb. 9, 11-16 (1984)
22. Désarménien, J., Wachs, M.: Descent classes of permutations with a given number of fixed points. J. Comb. Theory Ser. A 64, 311-328 (1993)
23. Diaconis, P.: Group Representations in Probability and Statistics. Institute of Mathematical Statistics Lecture Notes, vol.
11. Hayward (1988)
24. Diaconis, P., Fill, J., Pitman, J.: Analysis of top to random shuffles. Comb. Probab. Comput. 1, 135- 155 (1992)
25. Diaconis, P., Holmes, S.: Matchings and phylogenetic trees. Proc. Natl. Acad. Sci. USA 95, 14600- 14602 (1998)
26. Diaconis, P., Holmes, S.: Random walk on trees and matchings. Electron. J. Probab. 7, 1-17 (2002)
27. Diaconis, P., McGrath, M., Pitman, J.: Riffle shuffles, cycles, and descents. Combinatorica 15, 11-29 (1995)
28. Diaconis, P., Shahshahani, M.: On the eigenvalues of random matrices. J. Appl. Probab. A 31, 49-62 (1994)
29. Dixon, J.: Random sets which invariably generate the symmetric group. Discrete Math. 105, 25-39 (1992)
30. Dixon, J.: The probability of generating the symmetric group. Math. Z. 110, 199-205 (1969)
31. Dixon, J., Mortimer, B.: Permutation Groups. Graduate Texts in Mathematics,
163. Springer, Berlin (1996)
32. Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press (1996)
33. Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, New York (1968)
34. Fulman, J.: Card shuffling and the decomposition of tensor products. Pac. J. Math. 217, 247-262 (2004)
35. Fulman, J.: Convergence rates of random walk on irreducible representations of finite groups. J. Theor. Probab. 21, 193-211 (2008)
36. Fulman, J., Guralnick, R.: Derangements in simple and primitive groups. In: Groups, Combinatorics, and Geometry, Durham, 2001, pp. 99-121. World Scientific, Singapore (2003)
37. Fulman, J., Guralnick, R.: Derangements in subspace actions of classical groups. Preprint
38. Fulman, J., Guralnick, R.: Derangements in classical groups for non-subspace actions. Preprint
39. Fulman, J., Guralnick, R.: The probability of generating an irreducible subgroup. Preprint
40. Gluck, D., Magaard, K.: Absolute fourth moments and finiteness of linear groups. Commun. Algebra 34, 3387-3407 (2006)
41. Goncharov, V.: Sur la distribution des cycles dans les permutations. C. R. (Dokl.) Acad. Sci. URSS (N.S.) 35, 267-269 (1942)
42. Guralnick, R.: Monodromy groups of coverings of curves. In: Galois Groups and Fundamental Groups. Math. Sci. Res. Inst. Publ., vol. 41, pp. 1-46. Cambridge Univ. Press, Cambridge (2003)
43. Guralnick, R., Kantor, W.: Probabilistic generation of finite simple groups. J. Algebra 234, 743-792 (2000)
44. Guralnick, R., Kimmerle, W.: On the cohomology of alternating and symmetric groups and decomposition of relation modules. J. Pure Appl. Algebra 69, 135-140 (1990)
45. Guralnick, R., Magaard, K.: On the minimal degree of a primitive permutation group. J. Algebra 207, 127-145 (1998)
46. Guralnick, R., Wan, D.: Bounds for fixed point free elements in a transitive group and applications to curves over finite fields. Isr. J. Math. 101, 255-287 (1997)
47. James, G., Kerber, A.: The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications, vol.
16. Addison-Wesley, Reading (1981) J Algebr Comb (2008) 28: 189-218
48. Jordan, C.: Recherches sur les substitutions. J. Liouville 17, 351-367 (1872)
49. Kantor, W., Lubotzky, A.: The probability of generating a finite classical group. Geom. Dedic. 36, 67-87 (1990)
50. Korsh, J., LaFollette, P.: Constant time generation for derangements. Inf. Process. Lett. 90, 181-186 (2004)
51. Kurzweil, H., Stellmacher, B.: The Theory of Finite Groups: an Introduction. Springer, Berlin (2004)
52. Lenstra, H.W. Jr., Stevenhagen, P.: Chebotarev and his density theorem. Math. Intel. 18, 26-37 (1996)
53. Liebeck, M.: On the order of maximal subgroups of finite classical groups. Proc. Lond. Math. Soc. 50, 426-446 (1985)
54. Liebeck, M., Praeger, C., Saxl, J.: A classification of the maximal subgroups of the finite alternating and symmetric groups. J. Algebra 111, 365-383 (1987)
55. Liebeck, M., Praeger, C., Saxl, J.: On the O'Nan-Scott theorem for finite primitive permutation groups. J. Austral. Math. Soc. Ser. A 44, 389-396 (1988)
56. Lovász, L., Plummer, M.: Matching Theory. Annals of Discrete Mathematics, vol.
29. North Holland, Amsterdam (1986)
57. Luczak, T., Pyber, L.: On random generation of the symmetric group. Comb. Probab. Comput. 2, 505-512 (1993) 58. de Montmort, P.R.: Essay d'Analyse sur les Jeux de Hazard, 1st edn. (1708), 2nd edn. (1713). Jacques Quillau, Paris. Reprinted 2005 by AMS/Chelsea, New York
59. Mortimer, B.: Permutation groups containing affine groups of the same degree. J. Lond. Math. Soc.