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_{5} 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, ... (sequence A000793 in OEIS) is named after Edmund Landau, who proved in 1902^{[1]} that
(where ln denotes the natural logarithm).
The statement that
for all n, where Li^{−1} denotes the inverse of the logarithmic integral function, is equivalent to the Riemann hypothesis.
Notes
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, SpringerVerlag, 1997, pp. 228–240.
External links
Full article ▸
