18
$\begingroup$

I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one expects that the probability for two permutations of $\frak S_n$ to have the same order goes to 0 as n goes to infinity. Indeed experimentally this seems to happen with speed $O(1/n^2)$

I know that Wilf proved an asymptotic for a permutation in $\frak S_n$ to be of order $d$ (https://www.math.upenn.edu/~wilf/website/Asymptotics%20of%20exp%28P%28z%29%29.pdf) but I don't think it can be used directly.

On the other hand it is clear that the probability that two permutations have same order is more than probability that two permutations are conjugate. This is $K/n^2$ according to Flajolet et al. (http://arxiv.org/abs/math/0606370), but here again I failed to generalize the method for the order.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ One observation (sorry if already obvious). Letting $p_j$ be the probability a random permutation has order $j$, you're considering the "collision probability" $\sum_j p_j^2$. It suffices to essentially ignore all $j$ having $p_j = o(1/n^2)$ in this sum: If we consider $S = \sum_{j: p_j \leq 1/n^{2+\epsilon}} p_j^2$, with the constraint $\sum_j p_j \leq 1$, then by convexity $S$ is maximized by setting each $p_j = 1/n^{2+\epsilon}$ and having $n^{2+\epsilon}$ of them, hence $S \leq \frac{1}{n^{2+\epsilon}} = o(1/n^2)$. So you only need consider orders having probability $\Omega(1/n^2)$. $\endgroup$
    – usul
    Commented Feb 6, 2016 at 16:22
  • $\begingroup$ Another reference to add: arxiv.org/abs/1809.10912 $\endgroup$
    – Sean Eberhard
    Commented Oct 8, 2018 at 23:41

3 Answers 3

Reset to default
6
$\begingroup$

Nice problem! I claim that $\limsup n^2 p(n) = \infty$.

Suppose $k < n/2$ is such that $n-k$ is divisible by $L_k = \text{lcm}(1,2,\dots,k)$. Then if $\pi \in S_n$ has a cycle of length $n-k$ (this happens with probability $1/(n-k)$) then $\text{ord}(\pi) = n-k$, so the probability gets a contribution of $1/(n-k)^2 \geq 1/n^2$ from such $\pi$. Let $K_n$ be the set of all such $k$. Then $p(n) \geq |K_n|/n^2$.

Now the great thing about $n \mapsto K_n$ is that it is "lower semicontinuous on $\widehat{\mathbf{Z}}$". What I mean is this: Suppose $K = K_n$, and let $k = \max K$. Then the condition that $K_n \supset K$ is $L_k$-periodic, so provided we alter $n$ only by multiples of $L_k$, the set $K_n$ can only get bigger. Moreover, note that we would have $n \in K_n$, except for our stipulation that $k < n/2$. It follows that $$ K_{n + L_n} \supset K_n \cup \{n\}. $$ This shows that $|K_n|$ gets arbitrarily large, which proves the claim.

I have no idea about the $\liminf$! The above argument constructs very particular $n$ (of the shape $n_1 + \dots + n_k$, where each $n_i$ is large and highly divisible in comparison with $n_{i-1}$), and the lower bound is very weak besides (roughly $\log^*(n)/n^2$), so it's tempting to conjecture that the $\liminf$ is finite. But I'm not sure this is supported by the numerics. From the numerics it just looks like we're forgetting something.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for this very nice proof that my conjecture is wrong :) Together with the paper of Acan et al. you mentioned this gives me a much clearer view of the problem. $\endgroup$
    – thibo
    Commented Oct 9, 2018 at 14:02
  • 1
    $\begingroup$ The new version 2 of arxiv.org/pdf/1809.10912.pdf gives a quite convincing answer: $$n^{-2} \leq \lim p(n) \leq n^{-2+o(1)},$$ thanks! $\endgroup$
    – thibo
    Commented Jan 4, 2019 at 12:36
8
$\begingroup$

For two random permutations of $n$ letters, let $p_1(n)$ be the probability they are conjugate and $p_2(n)$ be the probability they have the same order. I computed these exactly up to $n=70$. In the following, the blue diamonds are $n^2p_1(n)$ and the red circles are $n^2p_2(n)$.

The ratio $p_2(n)/p_1(n)$ is some sort of weighted average of how many different partitions of $n$ have the same lcm, with popular partitions weighted more. I would have guessed this would slowly increase, but that isn't visible. The wriggliness of $p_2(n)$ presumably reflects the fact that the number of partitions with the same order as a given partition is some complicated arithmetic function.

Maple was struggling by the time it got to $n=70$ but a C program should be able to reach $n=100$ or maybe further.

plots as described

Improve this answer
$\endgroup$
1
4
$\begingroup$

That the probability is at least $O(1/n^2)$ is immediate, since the probability that both permutations are $n$-cycles is $1/n^2.$ For the upper bound, there is a convergence speed estimate by Zacharovas, see in particular theorems 3 and 4, which should give you what you want.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Those theorems might provide the order of the upper bound, but I'm dubious. They certainly won't give the precise value. The problem is that the number of permutations of given order depends a lot on the factorization of the order and so jumps up and down a lot. The cumulative asymptotics in those theorems smooths away the irregularities, but the irregularities are critical for answering the question. To illustrate what I'm getting at: even orders are usually much more popular than the adjacent odd orders, which is invisible in the asymptotics but effects the answer by a factor of 2. $\endgroup$
    – Brendan McKay
    Commented Feb 6, 2016 at 3:52
  • $\begingroup$ @BrendanMcKay I am not contesting your claim, but I don't think that the OP is asking for the asymptotics, but just for the upper bound. $\endgroup$
    – Igor Rivin
    Commented Feb 6, 2016 at 16:04
  • 1
    $\begingroup$ In Thm 3, consider $x$ near the central point $x_0=\frac12\log^2 n$. I think that if you change the order by $n^{O(1)}$, the value of $x$ changes by so little that the change in the estimate is buried in the error term. So the theorem hides wriggles big enough to wipe out any nontrivial upper bound. This leads me to suspect that the probability of equal order comes mostly from orders very far from $x_0$. For example the $n$-cycles you mention lie in the extreme lower tail of this distribution. $\endgroup$
    – Brendan McKay
    Commented Feb 7, 2016 at 0:13
  • 1
    $\begingroup$ @IgorRivin Indeed a upper bound would already interest me but I don't see how the theorems of Zacharovas could help me in this case. Are you suggesting a concentration inequality? $\endgroup$
    – thibo
    Commented Feb 10, 2016 at 11:09
  • 1
    $\begingroup$ Also I agree with @BredanMcKay saying that the tail of the distribution has to be considerate. There is an interesting article of Goh and Schmutz [math.drexel.edu/~eschmutz/PAPERS/musn.pdf] dealing with the expected value of the order that says that "small set of exceptional permutations contributes significantly" to the mean of the order. $\endgroup$
    – thibo
    Commented Feb 10, 2016 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .