THE LARGEST PRIME DIVIDING THE MAXIMAL ORDER

OF AN ELEMENT OF S_{n}

Jon Grantham

Department of Mathematics University of Georgia Athens, GA 30602

Abstract. We define g(n) to be the maximal order of an element of the symmetric group on n elements. Results about the prime factorization of g(n) allow a reduction of the upper bound on the largest prime divisor of g(n) to 1.328\sqrt{n log n}.

Let S_{n} be the symmetric group on n letters.

Definition. g(n) = max {ord(σ) | σ ∈ S_{n}}.

The first work on g(n) was done by Landau [1] in 1903. He showed that log g(n) ∼ \sqrt{n log n} as n → ∞. In 1984, Massias [2] showed an upper bound for \frac{log g(n)}{\sqrt{n log n}},

log g(n) ≤ a\sqrt{n log n}  a = 1.05313 …  n ≥ 1,

with a attained for n = 1, 319, 166.

Let P (g(n)) be the largest prime divisor of g(n). In 1969, Nicolas [4] proved that P (g(n)) ∼ \sqrt{n log n} as n → ∞. In 1989, Massias, Nicolas, and Robin [3] showed that P (g(n)) ≤ 2.86\sqrt{n log n}, n ≥ 2. They conjectured that \frac{P (g(n))}{\sqrt{n log n}} achieves a maximum (1.265 …) for n ≥ 5 at n = 215, with P (g(215)) = 43. They note that improving this bound using the techniques of their proof would require “very extensive computation,” and even then would not be able to reduce the constant in the bound below 2.

Using different techniques, however, we can improve this result to the following

Theorem. For each integer n ≥ 5, we have

P (g(n)) ≤ 1.328\sqrt{n log n}.

Our proof begins with the simple observation that g(n) = max {ord(σ) | σ ∈ S′_{n}}, where S′_{n} is the subset of S_{n} consisting of elements that are the product of disjoint cycles of prime power length.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 20B40.

A portion of this research, including the computations, was done at the Supercomputing Research Center. The author would also like to thank the referee for helpful suggestions.

To see this, recall the fact that we can write any σ ∈ S_{n} as the product of disjoint cycles. Then ord(σ) is the least common multiple of the cycle lengths. Consider a cycle of length ab with (a, b) = 1, a, b > 1. The product of a cycle of length a with one of length b also has order ab and is a permutation on fewer elements. Thus, given any element of S_{n}, we may find another that has the same order and is a product of disjoint cycles of prime power length.

Definition. For each natural number M, let ℓ(M) = ∑_{p^{α}∥M} p^{α}.

We observe that ℓ(M) is the shortest length of a permutation of order M. Thus, we can characterize g(n) in terms of ℓ as follows:

g(n) = max {M | ℓ(M) ≤ n}.

In particular, ℓ(g(n)) ≤ n.

Nicolas [6] describes an algorithm for computing g(n). Employing a variation of this algorithm, I computed exact values of g(n) for n ≤ 500, 000 on a Sun 4/390. The accuracy of the computation was checked by calculating values of g(n) using the set G described in [3] and verifying that they matched those in the computations. Analysis of the computations confirmed that for 5 ≤ n ≤ 500, 000, \frac{P (g(n))}{\sqrt{n log n}} attains a maximum at n = 215.

Lemma 1 (Nicolas [5]). Let p, p′, and q be distinct primes, with q ≥ p + p′. If q divides g(n), then at least one of p and p′ divides g(n).

Proof. Suppose p and p′ are primes not dividing g(n). Assume there is a prime q ≥ p + p′ with q | g(n). Without loss of generality, p < p′. Choose k such that

p^{k} + p′ ≤ q ≤ p^{k+1} + p′ − 1.

Let M = \frac{p^{k}p′g(n)}{q}. Since q | g(n), M is an integer. Then

ℓ(M) ≤ ℓ(g(n)) + (p^{k} + p′ − q) ≤ ℓ(g(n)) ≤ n.

Thus, an element of order M can be written as a permutation on n letters. Also,

p^{k}p′ − q ≥ p^{k}p′ − p^{k+1} − p′ + 1 = p^{k}(p′ − p) − p′ + 1

≥ p(p′ − p) − p′ + 1 = (p − 1)(p′ − p − 1) ≥ 0.

Therefore, p^{k}p′ > q, so M > g(n). But g(n) is the maximal order of a permutation on n letters. Thus, we have a contradiction, and the lemma is proven.

Write q = P (g(n)). We immediately get the following

Corollary. At most one prime less than \frac{q}{2} fails to divide g(n).

Lemma 2. Suppose 0 < α < β < 1. If at least one prime in the interval (αq, βq) divides g(n), then at most one prime in the interval (\sqrt{β}q, \frac{(1+α)q}{2} ) fails to divide g(n).

Proof. If two primes in the interval (\sqrt{β}q, \frac{(1+α)q}{2} ) fail to divide g(n), call them p and p′. Let q′ be a prime in the interval (αq, βq) dividing g(n). Let M = \frac{pp′}{qq′} g(n). Then

ℓ(M) ≤ p + p′ − q − q′ + ℓ(g(n)) ≤ (1 + α)q − q − αq + ℓ(g(n)) = ℓ(g(n)).

But pp′ − qq′ > (\sqrt{β}q)^{2} − q(βq) = 0, so M > g(n), giving a contradiction.

Proof of Theorem. By the computations, we may take n > 500,000. We may also assume q ≥ 1.3\sqrt{500000 log 500000} > 3329. Using the results of Schoenfeld [8] for large q, and computations for small q > 3329, we see that there are always at least two primes in the intervals (α_{i}q, β_{i}q), with α_{1} = .2426, β_{1} = .25, α_{2} = .3746, β_{2} = .386, α_{3} = .4632, β_{3} = .4723, α_{4} = .5248, β_{4} = .5352, α_{5} = .57, β_{5} = .5812, α_{6} = .6044, β_{6} = .6162, α_{7} = .6312, β_{7} = .6435, α_{8} = .6534, β_{8} = .6652, and α_{9} = .6714, β_{9} = .6834. By Lemma 1, at most one of the two or more primes in any of the first three intervals fails to divide g(n). Applying Lemma 2, we get that at most one prime in each interval (\sqrt{β_{i}}q, \frac{(1+α_{i})q}{2} ) fails to divide g(n), for i ≤ 3. This fact in turn implies that at most one prime in each interval (α_{i}q, β_{i}q) fails to divide g(n) for 4 ≤ i ≤ 9. Applying Lemma 2 again, we see that at most one prime in each interval (\sqrt{β_{i}}q, \frac{(1+α_{i})q}{2} ) fails to divide g(n) for 1 ≤ i ≤ 9.

We note that these intervals cover (.5q, .8357q). So at most ten primes less than .8357q fail to divide g(n), and they can be at most \frac{q}{2}, \frac{(1+α_{1})q}{2} , …, and \frac{(1+α_{9})q}{2} .

Therefore,

g(n) ≥ \frac{q ∏_{p≤.8357q} p}{\frac{q}{2} ∏ \frac{1+α_{i}}{2} q}.

Taking logarithms, we get

log g(n) ≥ θ(.8357q) − log \frac{1}{2} − ∑ log (\frac{1 + α_{i}}{2} q),

where θ is the Chebyshev function, θ(x) = ∑_{p≤x} log p.

For q > 3329 the sum of the terms on the right is less than .01338q, so

log g(n) ≥ θ(.8357q) − .01338q.

Using the estimates for θ(x) in [7], we get

log g(n) ≥ .79307q.

From [3], 1.05314\sqrt{n log n} ≥ log g(n), so

1.328\sqrt{n log n} ≥ \frac{1.05314}{.79307}\sqrt{n log n} ≥ q.

It is likely that further computation would be able to show that \frac{P (g(n))}{\sqrt{n log n}} attains a maximum at n = 215 for all n ≥ 5.

References

1. E. Landau, Über die Maximalordnung der Permutationen gegebenen Grades, Archiv der Math. und Phys. (1903), 92–103.

2. J. P. Massias, Majoration explicite de l’ordre maximum d’un élément du groupe symétrique, Ann. Fac. Sci. Toulouse Math. 6 (1984), 269–280.

3. J. P. Massias, J. L. Nicolas and G. Robin, Effective Bounds for the Maximal Order of an Element in the Symmetric Group, Math. Comp. 53 (1989), 665–678.

4. J. L. Nicolas, Sur l’ordre maximum d’un élément dans le groupe S_{n} des permutations, Acta Arith. 14 (1968), 315–332.

5. J. L. Nicolas, Ordre maximal d’un élément du groupe des permutations et “highly composite numbers”, Bull. Soc. Math. France 97 (1969), 129–191.

6. J. L. Nicolas, Calcul de l’Ordre Maximum d’un Élément du Groupe Symétrique S_{n}, R.A.I.R.O. 3 (1969), 43–50.

7. J. B. Rosser and L. Schoenfeld, Approximate Formulas for Some Functions of Prime Numbers, Illinois J. Math. 6 (1962), 64–94.

8. L. Schoenfeld, Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x). II, Math. Comp. 30 (1976), 337–360.