Funció de Landau

En matemàtiques, la funció de Landau g(n), que rep el nom del matemàtic Edmund Landau, es defineix per a tot nombre natural n per ser l'ordre més gran d'un element del grup simètric Sn. De manera equivalent, g(n) és el mínim comú múltiple (mcm) més gran de qualsevol partició de n, o el nombre màxim de vegades que una permutació de n elements es pot aplicar recursivament sobre si mateixa abans de tornar a la seva seqüència inicial.

Per exemple, 5 = 2 + 3 i mcm(2,3) = 6. Cap altra partició de 5 produeix un mcm més gran, de manera que g (5) = 6. Un element d'ordre 6 del grup S5 es pot escriure en notació de cicle com a (1 2) (3 4 5). Tingueu en compte que el mateix argument s'aplica al nombre 6, és a dir, g (6) = 6. Hi ha seqüències arbitràriament llargues de nombres consecutius n, n + 1,... , n + m on la funció g és constant.[1]

La seqüència entera 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, ... (successió A000793 a l'OEIS) rep el nom d'Edmund Landau, qui va demostrar el 1902 [2] que

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

(on ln denota el logaritme natural). De manera equivalent (utilitzant la notació de Landau), g ( n ) = e ( 1 + o ( 1 ) ) n ln ⁡ n {\displaystyle g(n)=e^{(1+o(1)){\sqrt {n\ln n}}}} .

Més concretament,[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).}

Si π ( x ) − Li ⁡ ( x ) = O ( R ( x ) ) {\displaystyle \pi (x)-\operatorname {Li} (x)=O(R(x))} , on π {\displaystyle \pi } denota la funció de recompte de nombre primers, Li {\displaystyle \operatorname {Li} } la funció integral logarítmica amb inversa Li − 1 {\displaystyle \operatorname {Li} ^{-1}} , i podem prendre 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 )}} per a una constant c > 0 segons Ford,[4] aleshores [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 )}.}

La condició que

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

per a n prou gran és equivalent a la hipòtesi de Riemann.

Es pot demostrar que

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

amb l'única igualtat entre les funcions a n = 0, i de fet

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

Notes

  1. ↑ Nicolas, Jean-Louis (1968), "Sur l’ordre maximum d’un élément dans le groupe Sn des permutations", Acta Arithmetica 14: 315–332
  2. ↑ Landau, pp. 92–103
  3. ↑ 3,0 3,1 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 50: 221–242
  4. ↑ Kevin Ford «Còpia arxivada». Proc. London Math. Soc., 85, 3, November 2002, pàg. 565–633. Arxivat de l'original el 2022-02-01. arXiv: 1910.08209. DOI: 10.1112/S0024611502013655 [Consulta: 15 maig 2024].
  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).

Referències

  • E. Landau, "Über die Maximalordnung der Permutationen gegebenen Grades [Sobre l'ordre màxim de les permutacions d'un grau donat]", Arch. Matemàtiques. Phys. Ser. 3, vol. 5, 1903.
  • W. Miller, « L'ordre màxim d'un element d'un grup simètric finit », American Mathematical Monthly, vol. 94, 1987, pàg. – .
  • J.-L. Nicolas, "Sobre la funció de Landau g ( n )", a Les matemàtiques de Paul Erdős, vol. 1, Springer-Verlag, 1997, pp. 228 – 240.