Landau's function

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 S5 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 that :\lim_{n\to\infty}\frac{\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{n\ln n}}.

More precisely, :\ln g(n)=\sqrt{n\ln n}\left(1+\frac{\ln\ln n-1}{2\ln n}-\frac{(\ln\ln n)^2-6\ln\ln n+9}{8(\ln n)^2}+O\left(\left(\frac{\ln\ln 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\bigl(-c(\ln x)^{3/5}(\ln\ln x)^{-1/5}\bigr) for some constant c 0 by Ford, then :\ln g(n)=\sqrt{\operatorname{Li}^{-1}(n)}+O\bigl(R(\sqrt{n\ln n})\ln n\bigr).

The statement that :\ln g(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 indeed :g(n) \le \exp\left(1.05314\sqrt{n\ln n}\right).