Permutations of Maximal Order

Let $S_n$ denote the permutation group on n letters. Herein, we consider the following question, brought to light by Landau in 1902:

Question: What is the maximal order of an element in $S_n$ ?

By convention, we shall refer to this maximal order as $g(n)$ . Thus, for instance, Lagrange’s theorem gives the elementary bound $g(n) \leq n!$ . We may obtain sharper bounds by noting that $S_n$ is centerless, but tweaks like this will fail to give more than a gain of a multiplicative constant. A far more productive route comes from the following Proposition:

Proposition: Let $\{a_1,\ldots, a_k\}$ be a partition of n into positive integers. Then $\prod_i a_i \leq 3^{n/3}$ , with equality if and only if $a_i = 3$ for all i.

Proof: Let $\{a_1,\ldots, a_k\}$ be a partition of n such that $\prod a_i$ is maximized. If $a_i >3$ for any i, we have $2(a_i-2)>a_i$ , and the partition

$\{a_1,\ldots, a_{i-1}, 2, a_i-2,a_{i+1},\ldots, a_k\}$

admits a strictly larger product. Thus, we may assume that $a_i =2,3$ for all i. Furthermore, the relation $2^3 <3^2$ implies that in a maximal partition we may have $a_i =2$ for at most two such i. It now follows (by cases) that our maximal product $A(n)$ takes the form

$A(n) = \begin{cases} 3^{n/3}, \hspace{15.5 mm} n \equiv 0 \mod 3 \\ 4 \cdot 3^{(n-4)/3}, \quad n \equiv 1 \mod 3 \\ 2 \cdot 3^{(n-2)/3}, \quad n \equiv 2 \mod 3 \end{cases}.$

Our result follows from the inequalities $4 \cdot 3^{-4/3} < 2 \cdot 3^{-2/3} <1$ . $\square$

Note: buried under all of this is the fact that the function $f(x) = x^{1/x}$ attains a global maximum at $x=e$ , and that 3 is the closest integer to e (this also underlies the marginal appearance of 2, as the second closest integer approximation to e). This will become more evident as we continue.

As a Corollary, we obtain a new upper bound for the function $g(n)$ :

Corollary: For all n, we have $g(n) \leq 3^{n/3}$ , with equality if and only if $n=3$ .

Proof: We note that $g(n)$ is the maximum value of $\mathrm{lcm}(a_1,\ldots a_k)$ , as $\{a_i\}$ varies over the partitions of n. But $\mathrm{lcm}(a_1\ldots, a_k) \leq \prod a_i \leq 3^{n/3}$ , with equality if and only if (1) $a_i =3$ for all i and (2) the $\{a_i\}$ are pairwise coprime. In particular, equality holds above if and only if $n=3$ (achieved with the partition $\{3\}$ ). $\square$

Note: this result is stronger than the commonly-cited bound $g(n) < e^{n/e}$ , which holds for all n.

The bound arising from our Proposition is nevertheless weak in method (in that we have only used the fact that $\mathrm{lcm}(a_1,\ldots,a_k)$ divides $a_1\cdots a_k$ ), and to strengthen it significantly requires the Prime number theorem (PNT). In fact, Landau’s classical result

$\log g(n) \sim \sqrt{n \log n}$

(which we will derive after the fold) is equivalent to the PNT by means of elementary methods.

Our proof is split (quite naturally) into two sections: derivation of the sharp upper (resp. lower) bounds, and makes use of little more than the Prime Number Theorem. We shall write $a(n) \gtrsim b(n)$ (resp. $a(n) \lesssim b(n)$ ) provided that

$\displaystyle\liminf_{n \to \infty} \frac{a(n)}{b(n)} \geq 1$ $\left(\text{resp. } \displaystyle\limsup_{n \to \infty} \frac{a(n)}{b(n)} \leq 1 \right).$

Clearly, $a(n) \sim b(n)$ if and only if $a(n) \gtrsim b(n)$ and $a(n) \lesssim b(n)$ .

Theorem (Part I): We have $\log g(n) \gtrsim \sqrt{n \log n}$ .

Proof: Throughout, we let $p_i$ denote the i-th prime. The PNT implies (via summation by parts) that

$\sum_{i=1}^k p_i \sim \frac{1}{2}k^2 \log k.$

If k is taken maximal such that the left-hand sum remains at most n (considered as a function $k(n)$ ), then $n \sim \frac{1}{2}k(n)^2 \log k(n)$ , and inversion of this asymptotic relation gives

$k(n) \sim 2\sqrt{n} (\log n)^{-1/2}.$

Let $n\#$ denote the n-th primorial (i.e. $n\# = \prod^n p_i$ ). The partition of n consisting of the first $k(n)$ primes (and as many extra 1’s as necessary) implies the lower bound

$\log g(n) \gtrsim \log \left(k(n)\#\right).$

Where $\theta(x) = \sum_{p \leq x} \log p$ is the usual Chebyshev $\theta$ -function, we note that $e^{\theta(x)} = \prod_{p_i\leq x} p_i$ . Thus the familiar asymptotic $\theta(x) \sim x$ implies (in the case $x = p_n$ ) that

$1=\displaystyle\lim_{n \to \infty} \log e^{\theta(p_n)/p_n} =\displaystyle\lim_{n \to \infty}\log \left((n\#)^{1/p_n}\right)$

and hence $\log n\# \sim p_n \sim n\log n$ , in which we have used the common asymptotic for the n-th prime. Substitution of this asymptotic into (1) gives

$\log g(n) \gtrsim \log \left((2\sqrt{n} (\log n)^{-1/2})\#\right)\sim \frac{2\sqrt{n}}{\sqrt{\log n}}\log \left( \frac{2\sqrt{n}}{\sqrt{\log n}}\right).$

The expression at right simplifies to give the desired result. $\square$

Lemma: If $\{b_1,\ldots, b_\ell\} \subset \mathbb{R}^+$ has sum n, then $\prod b_i \leq (n/\ell)^\ell$ .

Proof: Suppose that $\{b_1\ldots, b_\ell\}$ yields a maximal product. If $b_i < b_j$ , let $\Delta =(b_i+b_j)/2>0$ ; then

$(b_i +\Delta)(b_j -\Delta)=b_ib_j+\Delta(b_i+b_j)-\Delta^2=b_ib_j+\Delta^2>b_ib_j$ ,

and this gives a contradiction to maximality of the product $\prod b_i$ . Thus $b_i$ is constant in i, whence $\prod b_i = (n/\ell)^\ell$ . $\square$

Remark: this Lemma may be construed as the “continuous” analogue of the “discrete” result given in the Proposition above.

Theorem (Part II): We have $\log g(n) \lesssim \sqrt{n \log n}$ . Coupled with Part I, it follows that $\log g(n) \sim \sqrt{n \log n}$ .

Proof: Let $\{a_1,\ldots, a_\ell\}$ be a collection of integers greater than 1 such that $\sum a_i \leq n$ . If the prime p divides $(a_i,a_j)$ and $\mathrm{ord}_p(a_i) \geq \mathrm{ord}_p(a_j)$ , then

$\mathrm{lcm}(a_1,\ldots,a_k) =\mathrm{lcm}(a_1,\ldots, a_{j-1}, a_j/p, a_{j+1},\ldots,a_\ell).$

By induction, there now exists a collection $\{b_1,\ldots, b_k\}$ of increasing, pairwise coprime integers satisfying $g(n) = \mathrm{lcm}(b_1,\ldots,b_k)$ and $\sum b_i \leq n$ . Moreover, if $b_i$ is not a prime power we may write $b_i = s t$ for integers $s,t >1$ which are coprime to the other $b_j$ ( $j\neq i$ ). But then

$g(n) = \mathrm{lcm}(b_1,\ldots, b_{i-1}, s,t,b_{i+1},\ldots,b_k),$

so without loss of generality we may assume that $\{b_1,\ldots, b_k\}$ are an increasing collection of coprime prime powers. Let $q_i$ be prime, dividing $b_i$ . Then $b_i \geq q_i$ , and our condition that $\{b_i\}$ be increasing implies that $b_i \geq p_i$ , the i-th prime. In particular, $k :=k(n)$ must satisfy $k(n) \lesssim 2\sqrt{n}(\log n)^{-1/2}$ (as in Part I). We now claim that the asymptotic lower bound

$k(n) \gtrsim \frac{\sqrt{n}}{3 \sqrt{\log n}}$

holds. To the contrary, suppose that $k(n) < \frac{1}{3}\sqrt{n}(\log n)^{-1/2}$ for infinitely many n. For such n, the set $\{b_i\}$ contains at most $k(n)$ prime factors, hence at most $k(n)$ primes less than $K:=\sqrt{n \log n}$ . As $n \to \infty$ , the short interval $[K/4, K/2]$ contains

$\pi(K/2)-\pi(K/4) \sim \left(\frac{1}{2}-\frac{1}{4}\right)\frac{K}{\log K} \sim \frac{\sqrt{n}}{2\sqrt{\log n}}$

primes (by the PNT). As this exceeds $k(n)$ as $n \to \infty$ , we may choose two primes $p,q \in [K/4,K/2]$ which are coprime to each $b_i$ . As the $b_i$ are increasing, we have

$n>b_k>\frac{n}{k(n)} > 3\sqrt{n \log n}.$

Consequently, we have $p+q < K = \sqrt{n\log n} <b_k$ , whereas on the other hand $pq>K^2/16 =n\log n/16 >n$ as $n \to \infty$ . But this contradicts maximality in the expression $g(n) = \mathrm{lcm}(b_1,\ldots,b_k)$ , and so our claim must hold. To conclude, our Lemma (as well as our upper and lower bounds on $k(n)$ ) gives

$\log g(n) \leq k(n) \log \big(\frac{n}{k(n)}\big) \lesssim \frac{2\sqrt{n}}{\sqrt{\log n}}\cdot\log \left(3\sqrt{n\log n}\right)\sim \sqrt{n\log n},$

as desired. $\square$

Exercise: Let G be a group. We define the exponent $E(G)$ of G as the least $n> 0$ (if such an n exists) such that $g^n =e$ for all $g \in G$ . Equivalently, we note that $E(G)$ is the least common multiple of all the orders of elements in G. All finite groups have finite exponent, which necessarily divides $\# G$ by Lagrange’s theorem. Prove that

$\log E(S_n) = \sum_{p^k \leq n} \log p := \psi(n),$

in which $\psi(n)$ is the second Chebyshev function. Use this and the PNT to show that $\log E(S_n) \sim n$ as $n \to \infty$ . Use this to prove that $g(n) \lesssim \alpha^n$ for any $\alpha >e$ . (This estimate is quite weak, despite invocation of the PNT.)

Exercise: Obviously, the largest subgroup of $S_n$ is the alternating group $A_n$ . As $n \to \infty$ , the other large (in the sense of minimal index) subgroups of $S_n$ take the form $S_k \times S_{n-k}$ (and intersections thereof with alternating groups). Let $h(n,k)$ denote the maximal order of an element in $S_{n-k} \times S_k$ . Prove that