Permutations of Maximal Order

ropeLet 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 thate^{\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

\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.)

One response to “Permutations of Maximal Order

  1. Pingback: Maximal Products of a Given Sum | a. w. walker·

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s