# 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 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} , 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

$\log h(n,k) \sim \sqrt{n \log n}$

as $n \to \infty$ provided that $k:=k(n)$ remains $o(\sqrt{n \log n})$.  (See here for an explanation of little-o notation.)