Is the distribution of the orders of the cyclic groups generated by elements of $S_n$ known?

Question

A week ago I was playing around with a card-shuffle method corresponding to an element of $S_{52}$, and the order of the cyclic group generated was 272 (ie, 272 shuffles returns the deck to original order).

I was curious as to whether this was higher or lower than expected. A full calculation would require computing the orders of the cyclic groups generated by all $52!$ elements of $S_{52}$, which is computationally infeasible, so instead I ran a Monte-Carlo simulation of the orders of the cyclic groups generated by uniformly-distributed randomly-chosen elements of $S_{52}$:

dat52 = ParallelTable[
   GroupOrder[PermutationGroup[{RandomPermutation[52]}]], {10^6}];

Here is a coarse log-$x$-axis histogram of the results:

Histogram[dat52, "Log"]

The spike near 40 is not a statistical artifact; the results are only perturbed by $1/\sqrt{N}$ noise, which in this case is astronomically tiny (see the $y$-axis).

I was curious to see if there was any finer structure, so I made the following histogram-like image (right-click and open in a new tab to see large 4320 x 2320 pixel image):

The $x$-axis is logarithmic as before, and the $y$-axis goes up to about 24,000 counts (not labeled). As you can see, there is a lot of fine structure in the distribution of group orders.

Similarly, here is the histogram profile of the group orders of the elements of $S_{51}$ (full-size is 4320 x 2320 pixels):

Here is $S_{53}$ (full-size is 4580 x 2020 pixels):

And here is $S_{256}$ (full-size is 10020 x 4020 pixels):

Naturally, I'm curious whether there is anything known about these distributions, either structurally (ie, an explicit formula for the distribution counts of $S_n$), or asymptotically (ie, the smoothed profile tends towards so-and-so distribution as $n\to\infty$). Does anyone know, or is this beyond current mathematics?

From the comments in this question, it seems like this is a hard problem, but I was still curious as to what extent the structure is explainable.

Answer 1

The question can be factored into two questions: what is the joint distribution of the cycle lengths of a random permutation, and what is the lcm of all cycle lengths? The second question is an annoyingly delicate arithmetic question (e.g. the lcm depends delicately on whether a large cycle happens to have prime length) so I am tempted to ignore it to concentrate on the first question.

Here is what I know about cycle lengths of random permutations. First, it's a nice exercise to show that the expected number of cycles of length $k \le n$ in a permutation of $n$ elements is $\frac{1}{k}$, and hence the total expected number of cycles is

$$H_n = \sum_{k=1}^n \frac{1}{k} \approx \log n.$$

When $k \ll n$ one can make much stronger statements: as $n \to \infty$, the number of cycles of length $k \ll n$ is asymptotically Poisson with parameter $\frac{1}{k}$. Moreover, for various $k \ll n$ these Poisson random variables are asymptotically jointly independent. See this blog post for some details.

Unfortunately, I don't know much about large $k$.

Edit: An upper bound for the lcm of the cycle lengths is their product, and we can say something about that. The product is just $\prod k^{c_k}$ where $c_k$ is the number of cycles of length $k$, so the logarithm of the product is

$$\sum_{k=1}^n c_k \log k.$$

If we assume that the $c_k$ are, for all $k$, jointly Poisson with parameter $\frac{1}{k}$, then we can compute the moments of this logarithm. For example, its expected value is

$$\sum_{k=1}^n \frac{\log k}{k} \approx \frac{(\log n)^2}{2}.$$

Plugging in $n = 52$ gives that the exponential of the expected value of the logarithm of the product is about $2400$, which is at least within an order of magnitude of what you got.