THE AVERAGE ORDER OF A PERMUTATION

Richard Stong

Department of Mathematics Rice University Houston, TX 77005 stong@math.rice.edu

Submitted: May 11, 1998; Accepted: June 23, 1998

Abstract. We show that the average order μ_{n} of a permutation in S_{n} satisfies

log μ_{n} = C\sqrt{\frac{n}{log n}} + O ( \frac{\sqrt{n} log log n}{log n} ) ,

which refines earlier results of Erdős and Turán, Schmutz, and Goh and Schmutz.

1. Introduction.

For σ ∈ S_{n} let N(σ) be the order of σ in the group S_{n}. Erdős and Turán [2] showed that if one chooses a permutation uniformly at random from S_{n} then for n large log N(σ) is asymptotically normal with mean (log^{2} n)/2 and variance (log^{3} n)/3. Define the average order of an element of S_{n} to be

μ_{n} = \frac{1}{n!} ∑_{σ∈S_{n}} N(σ).

It turns out that log μ_{n} is much larger than (log^{2} n)/2, being dominated by the contribution of a relatively small number of permutations of very high order. This was first shown by Erdős and Turán [3], who showed that log μ_{n} = O (\sqrt{n/ log n}). This result was sharpened by Schmutz [6], and later by Goh and Schmutz [4] to show that log μ_{n} ∼ C\sqrt{n/ log n}, for an explicit constant C. The purpose of this note is to show that

log μ_{n} = C\sqrt{\frac{n}{log n}} + O (\frac{\sqrt{n} log log n}{log n}) ,

where C = 2.99047 … is an explicit constant defined below. Our argument shares some similarities with that of [4], but is more elementary and permits a more explicit bound on the error term. The proof will be divided into three steps. First we will give upper and lower bounds on μ_{n} involving the coefficients of a certain power series, then we will use a Tauberian theorem to bound these coefficients.

1991 Mathematics Subject Classification. Primary 11N37.

For a partition λ = (λ_{1}, λ_{2}, …, λ_{s}) let c_{i}(λ) be the number of parts of λ of size i, let |λ| = λ_{1} + λ_{2} + ⋯ + λ_{s} and let m(λ) = l.c.m.(λ_{1}, λ_{2}, …, λ_{s}). We will say that λ is a partition of |λ|. By a sub-partition of λ we will mean any subset of (λ_{1}, λ_{2}, …, λ_{s}) viewed as a partition of some smaller number. Then

μ_{n} = ∑_{|λ|=n} \frac{m(λ)}{1^{c_{1}(λ)}2^{c_{2}(λ)} … c_{1}(λ)!c_{2}(λ)! …}.

2. The Upper Bound.

Call a partition π = (π_{1}, π_{2}, …, π_{s}) minimal if for each sub-partition π′ of π we have m(π′) < m(π). For each partition λ of n choose a minimal sub-partition π with m(π) = m(λ) and write λ = π ∪ ω for some partition ω. Let M_{n} be the set of all minimal partitions π with |π| ≤ n and for any π ∈ M_{n} let Ω_{π} be the set of all partitions ω that occur with π in decompositions as above. Then

μ_{n} = ∑_{π∈M_{n}} ∑_{ω∈Ω_{π}} \frac{m(π)}{1^{c_{1}(π)}2^{c_{2}(π)} … 1^{c_{1}(ω)}2^{c_{2}(ω)} … c_{1}(π ∪ ω)!c_{2}(π ∪ ω)! …},

≤ ∑_{π∈M_{n}} \frac{m(π)}{π_{1}π_{2} …} ∑_{ω∈Ω_{π}} \frac{1}{1^{c_{1}(ω)}2^{c_{2}(ω)} … c_{1}(ω)!c_{2}(ω)! …},

≤ ∑_{π∈M_{n}} \frac{m(π)}{π_{1}π_{2} …},

where the first inequality follows by rewriting 1^{c_{1}(π)}2^{c_{2}(π)} … as π_{1}π_{2} … and using c_{i}(π ∪ ω) ≥ c_{i}(ω) and the second follows by noting that if the inner sum were over all partitions ω with |ω| = n − |π| instead of just a subset of them, then it would be 1.

For each minimal π = (π_{1}, π_{2}, …, π_{s}) choose integers (d_{1}, d_{2}, …, d_{s}) with the following properties:

(1) d_{i} divides π_{i},

(2) g.c.d. (d_{i}, d_{j}) = 1 for i ≠ j,

(3) ∏_{i=1}^{s} d_{i} = m(π). (An explicit construction of the d_{i} is given in [6].) Note that since π is minimal the d_{i} are all greater than 1. Define integers k_{i} by π_{i} = k_{i}d_{i}. Then π_{1}π_{2} … π_{s} = m(π)k_{1}k_{2} … k_{s}. Let D_{n} be the set of all unordered sets (d) = (d_{1}, d_{2}, …, d_{s}) of pairwise relatively prime integers greater than 1 with d_{1}+d_{2}+⋯+d_{s} ≤ n and for any (d) ∈ D_{n} let K_{(d)} be the set of all (k_{1}, k_{2}, …, k_{s}) with k_{1}d_{1} + k_{2}d_{2} + ⋯ + k_{s}d_{s} ≤ n. Then the bound above becomes

μ_{n} ≤ ∑_{(d)∈D_{n}} ∑_{(k)∈K_{(d)}} \frac{1}{k_{1}k_{2} …}.

The sets (d_{1}, d_{2}, …, d_{s}) can be broken up into two subsets: the prime elements and the composite elements. Any composite d_{i} must be divisible by some prime p with p ≤ \sqrt{n} and since the d_{i} are relatively prime p divides only one element. Therefore there are at most π(\sqrt{n}) < C \frac{\sqrt{n}}{log n} composite elements. Each composite element contributes at most ∑_{k=1}^{n} \frac{1}{k} = log n + O(1). Therefore all the composite elements

together contribute at most exp \{O (\frac{\sqrt{n} log log n}{log n})\} to μ_{n}. Let P_{n} be the set of all unordered sets (d) = (d_{1}, d_{2}, …, d_{s}) of distinct primes with d_{1} + d_{2} + ⋯ + d_{s} ≤ n. Then the bound above becomes

μ_{n} ≤ ∑_{(d)∈P_{n}} ∑_{(k)∈K_{(d)}} \frac{1}{k_{1}k_{2} …} exp \{O (\frac{\sqrt{n} log log n}{log n})\} .

The sum above can be rewritten in a convenient form. Let p_{1}, p_{2}, … be all the primes in order and consider infinite sequences (k_{1}, k_{2}, …) with only finitely many nonzero terms with ∑_{i=1}^{∞} k_{i}p_{i} ≤ n. Then the sum above is the sum over all such sequences of the product of the reciprocals of the nonzero k_{i}’s. Explicitly

μ_{n} ≤ ∑_{(k):Σk_{i}p_{i}≤n} ∏_{i:k_{i}≠0} \frac{1}{k_{i}} exp \{O (\frac{\sqrt{n} log log n}{log n})\} .

If we define a function h(t) and a sequence a_{m} by

h(t) = ∏_{p prime} (1 − log(1 − e^{−pt})) = ∑_{m=0}^{∞} a_{m}e^{−mt},

then the bound above says that

μ_{n} ≤ ∑_{m=0}^{n} a_{m} exp \{O (\frac{\sqrt{n} log log n}{log n})\} ,

Before analyzing the a_{m}’s in detail we will first derive a lower bound comparable to this upper bound.

3. The Lower Bound.

Consider only partitions λ of n of the following nice form λ = π ∪ ω where π = (π_{1}, π_{2}, …, π_{s}) and each π_{i} = k_{i}d_{i} where the d_{i} are distinct primes greater than \sqrt{n} and |ω| < q where q is the smallest prime larger than \sqrt{n}. For such a λ we have m(λ) ≥ d_{1}d_{2} … d_{s} and for all i either c_{i}(λ) = c_{i}(ω) or c_{i}(λ) = 1 and c_{i}(ω) = 0. In either case c_{i}(λ)! = c_{i}(ω)!. Therefore taking only the terms corresponding to these λ’s in our expression for μ_{n} above gives

μ_{n} ≥ ∑_{π} \frac{1}{k_{1}k_{2} …} ∑_{ω} \frac{1}{1^{c_{1}(ω)}2^{c_{2}(ω)} … c_{1}(ω)!c_{2}(ω)! …} = ∑_{π} \frac{1}{k_{1}k_{2} …},

where the outer sum runs over all π which occur in some partition as above and the second equality follows by noting that the inner sum is over all partitions ω with |ω| = n − |π| and hence is 1. This lower bound can be rewritten as we did for the upper bound. Let q = q_{1} < q_{2} < … be all the primes greater than \sqrt{n} in order and consider all infinite sequences (k_{1}, k_{2}, …) with only finitely many terms nonzero such that n − q < ∑_{i=1}^{∞} k_{i}q_{i} ≤ n. Then as above the lower bound is the sum over all such sequences of the product of the reciprocals of the nonzero k_{i}’s. Define a functions z_{n}(t) and sequences b_{m}^{(n)} by

z_{n}(t) = ∏_{p>\sqrt{n} prime} 1 − log (1 − e^{−pt}) = ∑_{m=0}^{∞} b_{m}^{(n)}e^{−mt}.

Then the lower bound above becomes

μ_{n} ≥ ∑_{m=n−q+1}^{n} b_{m}^{(n)}.

We need only relate the b_{m}^{(n)} to the a_{m} defined earlier. Unfortunately the sum above extends over only a short range of indices; we must first correct this imbalance.

For any m ≤ n − q and any prime q_{i} greater than \sqrt{n} and any sequence (k) that contributes to b_{m}^{(n)} we obtain a sequence that contributes to b_{m+q_{i}}^{(n)} by adding one to k_{i}. In the worst case this changes k_{i} from 1 to 2 and halves the contribution of this term. Therefore b_{m}^{(n)} ≤ 2b_{m+q_{i}}^{(n)}. Since there is a prime p between (n − m)/2 and n − m (which we may assume is greater than \sqrt{n} since we may always take p = q) we may halve the distance from m to n by one application of this inequality. After at most log_{2} n applications of the above inequality we obtain b_{m}^{(n)} ≤ nb_{s}^{(n)} for some n − q < s ≤ n. Therefore we have

∑_{m=0}^{n} b_{m}^{(n)} ≤ n^{2} ∑_{m=n−q+1}^{n} b_{m}^{(n)}

therefore with only negligible error we may replace the sum in the lower bound above by the sum over all m ≤ n.

To compare this sequence to the a_{m}’s note that

h(t) = z_{n}(t) ∏_{p≤\sqrt{n} prime} (1 − log(1 − e^{−pt})) .

If the second factor on the right hand side is expanded as ∑_{m=0}^{∞} c_{m}^{(n)}e^{−mt}, then

a_{m} = ∑_{k=0}^{m} b_{k}^{(n)}c_{m−k}^{(n)}.

The second factor of h(t) is a product of π(\sqrt{n}) < C \frac{\sqrt{n}}{log n} terms each of which

contributes at most 1 + ∑_{k=1}^{m} \frac{1}{k} = log m + O(1) to c_{m}^{(n)}. Therefore for all m ≤ n

we see c_{m}^{(n)} ≤ exp \{O (\frac{\sqrt{n} log log n}{log n})\}, so a_{m} ≤ ∑_{k=0}^{m} b_{k}^{(n)} exp \{O (\frac{\sqrt{n} log log n}{log n})\}. Summing over m gives

μ_{n} ≥ \frac{1}{n^{2}} ∑_{m=0}^{n} b_{m}^{(n)} ≥ ∑_{m=0}^{n} a_{m} exp \{−O (\frac{\sqrt{n} log log n}{log n})\} .

Combining this with the upper bound above gives

log μ_{n} = log ∑_{m=0}^{n} a_{m} + O (\frac{\sqrt{n} log log n}{log n}) .

To complete the proof we need only bound log ∑_{m=0}^{n} a_{m}.

4. The Tauberian Theorem.

We will apply the following result of Erdős and Turán [3].

Lemma (Erdős and Turán) Let f(t) = ∑_{m=0}^{∞} a_{m}e^{−mt} and suppose

log f(t) = \frac{A}{t log 1/t} + O (\frac{log log 1/t}{t(log 1/t)^{2}} ) as t → 0^{+}.

Then

∑_{m=0}^{n} a_{m} = exp \{2\sqrt{2A\frac{n}{log n}} + O (\frac{\sqrt{n} log log n}{log n})\} .

Thus we need only analyze log h(t) as t → 0^{+}. As in [3] we have

log h(t) = ∑_{p prime} log (1 − log(1 − e^{−pt})) = ∫_{0}^{∞} log (1 − log(1 − e^{−xt})) dπ(x),

= ∫_{0}^{∞} \frac{tπ(x)e^{−xt}}{(1 − e^{−xt}) (1 − log(1 − e^{−xt}))} dx,

= ∫_{0}^{∞} \frac{π(s/t)e^{−s}}{(1 − e^{−s}) (1 − log(1 − e^{−s}))} ds.

The integrand is bounded by C_{1}t^{−1} for s small (using the bound π(x) ≤ x). Therefore the contribution to the integral from the interval [0, t^{1/2}) is bounded by C_{1}t^{−1/2}. Hence we may replace the lower endpoint by t^{1/2} with only a negligible error. For any x we have

π(x) = \frac{x}{log x} + O (\frac{x}{(log x)^{2}} ) ,

(see for example [5, Thm 23, p. 65]) hence

π(s, t) = \frac{1}{t} \frac{s}{log 1/t + log s} + O (\frac{1}{t} \frac{s}{(log 1/t + log s)^{2}} ) .

Since s ≥ t^{1/2} we have log s ≥ −1/2 log(1/t) and thus

π(s, t) = \frac{s}{t log 1/t} − \frac{s log s}{t log 1/t(log 1/t + log s} + O (\frac{s}{t(log 1/t)^{2}} ) ,

= \frac{s}{t log 1/t} + O (\frac{s(1 + | log s|)}{t(log 1/t)^{2}}) .

Plugging this into the integral and extending the lower endpoint back to 0 (which again introduces only negligible error terms) gives

log h(t) = \frac{1}{t log 1/t} ∫_{0}^{∞} \frac{se^{−s}}{(1 − e^{−s}) (1 − log(e^{−s}))} ds + O (\frac{1}{t(log 1/t)^{2}} ) .

So the Tauberian theorem of Erdős and Turán gives

log μ_{n} = 2\sqrt{2A}\sqrt{\frac{n}{log n}} + O (\frac{\sqrt{n} log log n}{log n})

where

\begin{aligned}A & = ∫_{0}^{∞} \frac{se^{−s}}{(1 − e^{−s}) (1 − log(1 − e^{−s}))} ds = ∫_{0}^{∞} \frac{log(s + 1)}{e^{−s} − 1} ds \\ & = ∑_{n=1}^{∞} \frac{e^{n}}{n} E_{1}(n) = 1.11786415 …. \end{aligned}

where E_{1}(n) is the exponential integral (see [1, Eqn. 5.1.1, p. 228]).

Acknowledgements. The author was partially supported by an Alfred P. Sloan Research Fellowship.

References

1. M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, National Bureau of Standards, Washington DC, 1972.

2. P. Erdős and P. Turán, On some problems of a statistical group theory, III,, Acta Math. Acad. Sci. Hungar. 18 (1967), 309–320.

3. P. Erdős and P. Turán, On some problems of a statistical group theory, IV, Acta Math. Acad. Sci. Hungar. 19 (1968), 413–435.

4. W. Goh and E. Schmutz, The expected order of a random permutation, Bull. Lond. Math. Soc. 23 (1991), 34–42.

5. A. E. Ingham, The Distribution of Prime Numbers, Cambridge University Press, Cambridge, 1990.

6. E. Schmutz, Proof of a conjecture of Erdős and Turán, Jour. No. Th. 31 (1989), 260–271.