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 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.[1]

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[2] that

\lim _{n\to \infty }{\frac {\ln(g(n))}{\sqrt {n\ln(n)}}}=1

(where ln denotes the natural logarithm). In other words, $g(n)=e^{(1+o(1)){\sqrt {n\ln n}}}$ .

The statement that

\ln g(n)<{\sqrt {\mathrm {Li} ^{-1}(n)}}

for all sufficiently large n, where Li⁻¹ denotes the inverse of the logarithmic integral function, is equivalent to the Riemann hypothesis.

It can be shown that

g(n)\leq e^{n/e}

with the only equality between the functions at n = 0, and indeed

g(n)\leq \exp \left(1.05314{\sqrt {n\ln n}}\right).

[3]

Notes

Nicolas, Jean-Louis (1968), "Sur l'ordre maximum d'un élément dans le groupe S_n des permutations", Acta Arithmetica (in French), 14: 315–332
Landau, pp. 92–103
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).

gollark: But there must be moderately reusable libraries for this now.

gollark: I mean, the web and layouts and stuff are 8281837373 hard.

gollark: What if we make a simpler browser using Scheme, as Brendan Eich was *going* to do?

gollark: TTech™? How creative.

gollark: What they are saying is that values have types and not variables.

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

OEIS sequence A000793 (Landau's function on the natural numbers)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Nicolas, Jean-Louis (1968), "Sur l'ordre maximum d'un élément dans le groupe S_n des permutations", Acta Arithmetica (in French), 14: 315–332

[2] Landau, pp. 92–103

[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).