In mathematics, Landau's function ''g''(''n''), named after

Edmund Landau Edmund Georg Hermann Landau (14 February 1877 – 19 February 1938) was a German mathematician who worked in the fields of number theory and complex analysis. Biography Edmund Landau was born to a Jewish family in Berlin. His father was Leopol ...

, is defined for every

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...

''n'' to be the largest order of an element of the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...

''S''_''n''. Equivalently, ''g''(''n'') is the largest

least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...

(lcm) of any

partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...

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 In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...

''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

, who proved in 1902 that :

\lim_\frac = 1

(where ln denotes the natural logarithm). Equivalently (using

little-o notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...

g(n) = e^

. The statement that :

\ln g(n)<\sqrt

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)\le e^

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

g(n) \le \exp\left(1.05314\sqrt\right).

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

Notes

References

* E. Landau, "Über die Maximalordnung der Permutationen gegebenen Grades n 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 el, sequencenumber=A000793, name=Landau's function on the natural numbers, formalname=Landau's function g(n): largest order of permutation of n elements. Equivalently, largest LCM of partitions of n Group theory Permutations Arithmetic functions