Let 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 ?
By convention, we shall refer to this maximal order as . Thus, for instance, Lagrange’s theorem gives the elementary bound . We may obtain sharper bounds by noting that 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 be a partition of n into positive integers. Then , with equality if and only if for all i.
Proof: Let be a partition of n such that is maximized. If for any i, we have , and the partition
admits a strictly larger product. Thus, we may assume that for all i. Furthermore, the relation implies that in a maximal partition we may have for at most two such i. It now follows (by cases) that our maximal product takes the form
Our result follows from the inequalities .
Note: buried under all of this is the fact that the function attains a global maximum at , 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 :
Corollary: For all n, we have , with equality if and only if .
Proof: We note that is the maximum value of , as varies over the partitions of n. But , with equality if and only if (1) for all i and (2) the are pairwise coprime. In particular, equality holds above if and only if (achieved with the partition ).
Note: this result is stronger than the commonly-cited bound , 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 divides ), and to strengthen it significantly requires the Prime number theorem (PNT). In fact, Landau’s classical result
(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 (resp. ) provided that
Clearly, if and only if and .
Theorem (Part I): We have .
Proof: Throughout, we let denote the i-th prime. The PNT implies (via summation by parts) that
If k is taken maximal such that the left-hand sum remains at most n (considered as a function ), then , and inversion of this asymptotic relation gives
Let denote the n-th primorial (i.e. ). The partition of n consisting of the first primes (and as many extra 1’s as necessary) implies the lower bound
Where is the usual Chebyshev -function, we note that. Thus the familiar asymptotic implies (in the case ) that
and hence , in which we have used the common asymptotic for the n-th prime. Substitution of this asymptotic into (1) gives
The expression at right simplifies to give the desired result.
Lemma: If has sum n, then .
Proof: Suppose that yields a maximal product. If , let ; then
and this gives a contradiction to maximality of the product . Thus is constant in i, whence .
Remark: this Lemma may be construed as the “continuous” analogue of the “discrete” result given in the Proposition above.
Theorem (Part II): We have . Coupled with Part I, it follows that .
Proof: Let be a collection of integers greater than 1 such that . If the prime p divides and , then
By induction, there now exists a collection of increasing, pairwise coprime integers satisfying and . Moreover, if is not a prime power we may write for integers which are coprime to the other (). But then
so without loss of generality we may assume that are an increasing collection of coprime prime powers. Let be prime, dividing . Then , and our condition that be increasing implies that , the i-th prime. In particular, must satisfy (as in Part I). We now claim that the asymptotic lower bound
holds. To the contrary, suppose that for infinitely many n. For such n, the set contains at most prime factors, hence at most primes less than . As , the short interval contains
primes (by the PNT). As this exceeds as , we may choose two primes which are coprime to each . As the are increasing, we have
Consequently, we have , whereas on the other hand as . But this contradicts maximality in the expression , and so our claim must hold. To conclude, our Lemma (as well as our upper and lower bounds on ) gives
Exercise: Let G be a group. We define the exponent of G as the least (if such an n exists) such that for all . Equivalently, we note that is the least common multiple of all the orders of elements in G. All finite groups have finite exponent, which necessarily divides by Lagrange’s theorem. Prove that
in which is the second Chebyshev function. Use this and the PNT to show that as . Use this to prove that for any . (This estimate is quite weak, despite invocation of the PNT.)
Exercise: Obviously, the largest subgroup of is the alternating group . As , the other large (in the sense of minimal index) subgroups of take the form (and intersections thereof with alternating groups). Let denote the maximal order of an element in . Prove that
as provided that remains . (See here for an explanation of little-o notation.)