Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks. (Q2370623): Difference between revisions

The authors develop a number of statistical aspects of symmetric groups, mostly dealing with the distribution of cycles in various subsets of \(S_n\), asymptotic properties of characters of symmetric groups and estimates for the multiplicities of the root number functions of these groups. Many relevant applications are presented. One of these is a proof of a well known conjecture of Roichman concerning the mixing time of random walks on symmetric groups. Let \(c\) be a non-trivial conjugacy class in \(S_n\), denote by \(t_1(c)\) the least even integer such that \(t_1(c)\) elements chosen at random from \(c\) have, with probability at least \(1-1/n\), no common fixed point, and let \(t_2(c)\) be the mixing time for the random walk generated by \(c\): then, for \(n\) large enough, \(t_1(c)\leq t_2(c)\leq 10t_1(c)\). The other main applications are related with Fuchsian groups and their subgroup growth. An asymptotic estimate is given for the number \(s_n(\Gamma)\) of subgroups of index \(n\) in a Fuchsian group \(\Gamma\). Moreover the authors prove a finiteness result for the number of Fuchsian presentations for such a group, which resolves a long-standing problem of Roger Lyndon: each Fuchsian group \(\Gamma\) has only finitely many presentations of the form \(\Gamma=\langle x_1,\dots,x_r,y_1,\dots,y_r,u_1,v_1,\dots,u_t,v_t\mid x_1^{a_1}=\cdots=x_r^{a_r}=x_1\cdots x_ry_1^{e_1}\cdots y_s^{e_s}[u_1,v_1]\cdots[u_t,v_t]=1\rangle\). Moreover there are at most finitely many non-isomorphic Fuchsian groups \(\Delta\) with \(s_n(\Gamma)=s_n(\Delta)(1+\mathcal O(n^{-A}))\) for every \(A>0\).