Landau's function explained

In mathematics, Landau's function g(n), named after Edmund Landau, is defined for every natural number n to be the largest order of an element of the symmetric group S_n. Equivalently, g(n) is the largest least common multiple (lcm) of any partition of n, or the maximum number of times a permutation of n elements can be recursively applied to itself before it returns to its starting sequence.

For instance, 5 = 2 + 3 and lcm(2,3) = 6. No other partition of 5 yields a bigger lcm, so g(5) = 6. An element of order 6 in the group S₅ can be written in cycle notation as (1 2) (3 4 5). Note that the same argument applies to the number 6, that is, g(6) = 6. There are arbitrarily long sequences of consecutive numbers n, n + 1, ..., n + m on which the function g is constant.

The integer sequence g(0) = 1, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 4, g(5) = 6, g(6) = 6, g(7) = 12, g(8) = 15, ... is named after Edmund Landau, who proved in 1902^[1] that

\lim _{n\toinfty} (ln (g(n)))/(\sqrt{n ln (n)) } = 1(where ln denotes the natural logarithm). Equivalently (using little-o notation), g(n) = e ^{(1+o(1))\sqrt{nln} }.

More precisely,

ln g(n) = \sqrt{n ln n}\left( 1+ (lnln n -1)/(- 2ln n) (( lnln n) ^{2-6lnln} n +9)/(+ O\left(\left( 8 ( ln n) ^{2}) (lnln n)/(ln n) \right) ^{3\right)\right).}

If

\pi(x) - \operatorname{Li}(x) = O(R(x)) , where \pi denotes the prime counting function, \operatorname{Li} the logarithmic integral function with inverse \operatorname{Li} ^{-1} , and we may take R(x) = x\exp l ( - c( ln x) ^{3/5} ( lnln x) ^{-1/5} r ) for some constant c > 0 by Ford,^[2] thenln g(n) = \sqrt{\operatorname{Li} ^{-1} (n)} + O l (R(\sqrt{n ln n}) ln n r ).

The statement that

ln g(n)<\sqrt{ Li ^{-1} (n)} for all sufficiently large n is equivalent to the Riemann hypothesis.

It can be shown that

g(n)\le e ^{n/e} with the only equality between the functions at n = 0, and indeedg(n) \le \exp\left( 1 . 05314 \sqrt{n ln n}\right). ^[3]

Notes

1. Landau, pp. 92–103
2. Kevin Ford . Vinogradov's Integral and Bounds for the Riemann Zeta Function . Proc. London Math. Soc. . November 2002 . 85 . 3 . 565–633 . 10.1112/S0024611502013655 . 1910.08209 . 121144007 .
3. Jean-Pierre Massias, Majoration explicite de l'ordre maximum d'un élément du groupe symétrique, Ann. Fac. Sci. Toulouse Math. (5) 6 (1984), no. 3-4, pp. 269–281 (1985).

References

• E. Landau, "Über die Maximalordnung der Permutationen gegebenen Grades [On the maximal order of permutations of given degree]", Arch. Math. Phys. Ser. 3, vol. 5, 1903.
• W. Miller, "The maximum order of an element of a finite symmetric group", American Mathematical Monthly, vol. 94, 1987, pp. 497 - 506.
• J.-L. Nicolas, "On Landau's function g(n)", in The Mathematics of Paul Erdős, vol. 1, Springer-Verlag, 1997, pp. 228 - 240.