Landau's function g(n) is defined for every natural number n to be the largest order of an element of the symmetric group Sn. Equivalently, g(n) is the largest least common multiple of any partition of n. 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 S5 can be written in cycle notation as (1 2) (3 4 5). 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 A000793. The sequence is named after Edmund Landau, who proved in 1902 (reference [1] below) that
- <math>\lim_{n\to\infty}\frac{\ln(g(n))}{\sqrt{n \ln(n)}} = 1</math>
(where ln denotes the natural logarithm). The statement that
- <math>ln~g(n)<\sqrt{Li^{-1}(n)}</math>
for all n, where Li-1 denotes the inverse of the logarithmic integral function, is equivalent to the Riemann hypothesis.
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, pp. 92-103.
- 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.
External links
On-Line Encyclopedia of Integer Sequences: Sequence A000793, Landau's function on the natural numbers.
