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

, 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 Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...

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 of ''n'', or the maximum number of times a

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...

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

''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 The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...

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

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 In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...

, is equivalent to the

Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in pu ...

. 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 ''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an ...

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