Функция Ландау ${\displaystyle g(n)}$ в теории чисел , названная в честь немецкого математика Эдмунда Ландау , определяется для любого натурального числа n как наибольший порядок элемента симметрической группы ${\displaystyle S_{n}}$ .

Определения

Эквивалентные определения: ${\displaystyle g(n)}$ равно наибольшему из наименьших общих кратных (НОК) по всем разбиениям числа n , или максимальному числа раз, которое подстановка из n элементов может быть последовательно применена до первого появления первоначальной последовательности. Таким образом, формально:

${\displaystyle g(n)=\max \limits _{k_{1}+\ldots +k_{m}=n}HOK(k_{1},\ldots ,k_{m})}$ .

Например, 5 = 2 + 3 и НОК(2,3) = 6. Никакое другое разбиение не даёт бо́льшее наименьшее общее кратное, следовательно ${\displaystyle g(5)=6}$ . Элемент порядка 6 в группе ${\displaystyle S_{5}}$ может быть записан в виде произведения двух циклов: (1 2) (3 4 5).

Свойства

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 , названа в честь Эдмунда Ландау , доказавшего в 1902 году , что

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

(где ln обозначает натуральный логарифм ).

При этом локальные максимумы выражения под знаком предела случаются при n = 2, 3, 5, 7, 9, 10, 12, 17, 19, 30, 36, 40, … (последовательность в OEIS ).

Утверждение о том, что

${\displaystyle \ln g(n)<{\sqrt {\operatorname {Li} ^{-1}(n)}}}$

для всех n , где ${\displaystyle \operatorname {Li} ^{-1}}$ обозначает обратную функцию к интегральному логарифму , эквивалентно гипотезе Римана .

Другие соотношения:

• ln НОК (1, 2, …, n) ${\displaystyle \leqslant \ln g\left({\frac {n(n+1)}{2}}\right)\sim n{\sqrt {\ln n}}}$ . Первое неравенство следует из того, что ${\displaystyle 1+2+\dots +n={\frac {n(n+1)}{2}}}$ — одно из разбиений, вторая асимптотика из утверждения Ландау.
• Пусть gpf( g(n) ) — наибольший простой множитель g(n) . Значения этой функции при n=2, 3, … будут 2, 3, 2, 3, 3, 3, 5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 11, … (последовательность в OEIS ). J.-L. Nicolas в 1969 показал, что ${\displaystyle \operatorname {gpf} (g(n))\sim {\sqrt {n\ln n}}}$ . J.-P. Massias et al. (1988, 1989) показали, что для всех ${\displaystyle n\geqslant 2}$ ${\displaystyle \operatorname {gpf} (g(n))\leqslant 2{,}86{\sqrt {n\ln n}}}$ , а J. Grantham (1995) показал, что для всех ${\displaystyle n\geqslant 5}$ константа 2,86 может быть улучшена до 1,328.

Примечания

Литература

• E. Landau , «Über die Maximalordnung der Permutationen gegebenen Grades [О максимальном порядке перестановки заданного порядка]», 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.

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• последовательность в OEIS — функция Ландау для натуральных чисел.