Landau's function

Template:Short description 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, ... (sequence A000793 in the OEIS) is named after Edmund Landau, who proved in 1902 that

$\underset{n\to \mathrm{\infty }}{\lim }\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}(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)).$

If $\pi (x)-\mathrm{Li}(x)=O(R(x))$, where $\pi$ denotes the prime counting function, $\mathrm{Li}$ the logarithmic integral function with inverse ${\mathrm{Li}}^{-1}$, and we may take $R(x)=x\exp (-c(\ln x{)}^{3/5}(\ln \ln x{)}^{-1/5})$ for some constant c > 0 by Ford, then

$\ln g(n)=\sqrt{{\mathrm{Li}}^{-1}(n)}+O(R(\sqrt{n\ln n})\ln n).$

The statement that

$\ln g(n)<\sqrt{{\mathrm{L}\mathrm{i}}^{-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 indeed

$g(n)\le \exp (1.05314\sqrt{n\ln n}).$

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.

External links

• Template:OEIS el