Editing Landau's function

{{Short description|Mathematical function}}
In [[mathematics]], '''Landau's function''' ''g''(''n''), named after [[Edmund Landau]], is defined for every [[natural number]] ''n'' to be the largest [[order (group theory)|order]] of an element of the [[symmetric group]] ''S''<sub>''n''</sub>. Equivalently, ''g''(''n'') is the largest [[least common multiple]] (lcm) of any [[integer partition|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''<sub>5</sub> 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)&nbsp;=&nbsp;6. There are arbitrarily long sequences of consecutive numbers ''n'', ''n''&nbsp;+&nbsp;1, ..., ''n''&nbsp;+&nbsp;''m'' on which the function ''g'' is constant.<ref>{{citation|last=Nicolas|first=Jean-Louis|author-link=Jean-Louis Nicolas|title=Sur l’ordre maximum d’un  élément dans le groupe ''S<sub>n</sub>'' des permutations|journal=[[Acta Arithmetica]]|volume=14|year=1968|pages=315–332|language=French}}</ref>

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, ... {{OEIS|A000793}} is named after [[Edmund Landau]], who proved in 1902<ref>Landau, pp. 92–103</ref> that
:<math>\lim_{n\to\infty}\frac{\ln(g(n))}{\sqrt{n \ln(n)}} = 1</math>
(where ln denotes the [[natural logarithm]]).  Equivalently (using [[Big O notation|little-o notation]]), <math>g(n) = e^{(1+o(1))\sqrt{n\ln n}}</math>.

More precisely,<ref name="mnr88">{{citation|last1=Massias|first1=J. P.|last2=Nicholas|first2=J. L.|last3=Robin|first3=G.|title=Évaluation asymptotique de l’ordre maximum d’un élément du groupe symétrique|journal=[[Acta Arithmetica]]|volume=50|year=1988|pages=221–242|language=French}}</ref>
:<math>\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).</math>

If <math>\pi(x)-\operatorname{Li}(x)=O(R(x))</math>, where <math>\pi</math> denotes the [[prime counting function]], <math>\operatorname{Li}</math> the [[logarithmic integral function]] with [[inverse function|inverse]] <math>\operatorname{Li}^{-1}</math>, and we may take <math>R(x)=x\exp\bigl(-c(\ln x)^{3/5}(\ln\ln x)^{-1/5}\bigr)</math> for some constant ''c'' > 0 by Ford,<ref>{{cite journal |author = Kevin Ford |title=Vinogradov's Integral and Bounds for the Riemann Zeta Function |journal=Proc. London Math. Soc. |date=November 2002 |volume=85 |issue=3 |pages=565–633 |url=https://faculty.math.illinois.edu/~ford/wwwpapers/zetabd.pdf |doi=10.1112/S0024611502013655 |arxiv=1910.08209 |s2cid=121144007 }}</ref> then<ref name="mnr88" />
:<math>\ln g(n)=\sqrt{\operatorname{Li}^{-1}(n)}+O\bigl(R(\sqrt{n\ln n})\ln n\bigr).</math>

The statement that
:<math>\ln g(n)<\sqrt{\mathrm{Li}^{-1}(n)}</math>
for all sufficiently large ''n'' is equivalent to the [[Riemann hypothesis]].

It can be shown that
:<math>g(n)\le e^{n/e}</math>
with the only equality between the functions at ''n'' = 0, and indeed
:<math>g(n) \le \exp\left(1.05314\sqrt{n\ln n}\right).</math><ref>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).</ref>

==Notes==
<references/>

== 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.&nbsp;497&ndash;506.
*J.-L. Nicolas, "On Landau's function ''g''(''n'')", in ''The Mathematics of Paul Erdős'', vol. 1, Springer-Verlag, 1997, pp.&nbsp;228&ndash;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}}

[[Category:Group theory]]
[[Category:Permutations]]
[[Category:Arithmetic functions]]