Landau's function (original) (raw)

From Wikipedia, the free encyclopedia

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 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_5 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 → ∞ ln ⁡ ( g ( n ) ) n ln ⁡ ( n ) = 1 {\displaystyle \lim _{n\to \infty }{\frac {\ln(g(n))}{\sqrt {n\ln(n)}}}=1} {\displaystyle \lim _{n\to \infty }{\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 ) ) n ln ⁡ n {\displaystyle g(n)=e^{(1+o(1)){\sqrt {n\ln n}}}} {\displaystyle g(n)=e^{(1+o(1)){\sqrt {n\ln n}}}}.

More precisely,[3]

ln ⁡ g ( n ) = n ln ⁡ n ( 1 + ln ⁡ ln ⁡ n − 1 2 ln ⁡ n − ( ln ⁡ ln ⁡ n ) 2 − 6 ln ⁡ ln ⁡ n + 9 8 ( ln ⁡ n ) 2 + O ( ( ln ⁡ ln ⁡ n ln ⁡ n ) 3 ) ) . {\displaystyle \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).} {\displaystyle \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).}

If π ( x ) − Li ⁡ ( x ) = O ( R ( x ) ) {\displaystyle \pi (x)-\operatorname {Li} (x)=O(R(x))} {\displaystyle \pi (x)-\operatorname {Li} (x)=O(R(x))}, where π {\displaystyle \pi } {\displaystyle \pi } denotes the prime counting function, Li {\displaystyle \operatorname {Li} } {\displaystyle \operatorname {Li} } the logarithmic integral function with inverse Li − 1 {\displaystyle \operatorname {Li} ^{-1}} {\displaystyle \operatorname {Li} ^{-1}}, and we may take R ( x ) = x exp ⁡ ( − c ( ln ⁡ x ) 3 / 5 ( ln ⁡ ln ⁡ x ) − 1 / 5 ) {\displaystyle R(x)=x\exp {\bigl (}-c(\ln x)^{3/5}(\ln \ln x)^{-1/5}{\bigr )}} {\displaystyle R(x)=x\exp {\bigl (}-c(\ln x)^{3/5}(\ln \ln x)^{-1/5}{\bigr )}} for some constant c > 0 by Ford,[4] then[3]

ln ⁡ g ( n ) = Li − 1 ⁡ ( n ) + O ( R ( n ln ⁡ n ) ln ⁡ n ) . {\displaystyle \ln g(n)={\sqrt {\operatorname {Li} ^{-1}(n)}}+O{\bigl (}R({\sqrt {n\ln n}})\ln n{\bigr )}.} {\displaystyle \ln g(n)={\sqrt {\operatorname {Li} ^{-1}(n)}}+O{\bigl (}R({\sqrt {n\ln n}})\ln n{\bigr )}.}

The statement that

ln ⁡ g ( n ) < L i − 1 ( n ) {\displaystyle \ln g(n)<{\sqrt {\mathrm {Li} ^{-1}(n)}}} {\displaystyle \ln g(n)<{\sqrt {\mathrm {Li} ^{-1}(n)}}}

for all sufficiently large n is equivalent to the Riemann hypothesis.

It can be shown that

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

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

g ( n ) ≤ exp ⁡ ( 1.05314 n ln ⁡ n ) . {\displaystyle g(n)\leq \exp \left(1.05314{\sqrt {n\ln n}}\right).} {\displaystyle g(n)\leq \exp \left(1.05314{\sqrt {n\ln n}}\right).}[5]

  1. ^ Nicolas, Jean-Louis (1968), "Sur l'ordre maximum d'un élément dans le groupe Sn des permutations", Acta Arithmetica (in French), 14: 315–332
  2. ^ Landau, pp. 92–103
  3. ^ a b Massias, J. P.; Nicholas, J. L.; Robin, G. (1988), "Évaluation asymptotique de l'ordre maximum d'un élément du groupe symétrique", Acta Arithmetica (in French), 50: 221–242
  4. ^ Kevin Ford (November 2002). "Vinogradov's Integral and Bounds for the Riemann Zeta Function" (PDF). Proc. London Math. Soc. 85 (3): 565–633. arXiv:1910.08209. doi:10.1112/S0024611502013655. S2CID 121144007. Archived from the original (PDF) on 2022-02-01. Retrieved 2023-12-20.
  5. ^ 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).