Функция Ландау

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

Определения

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

[math]\displaystyle{ g(n)=\max\limits_{k_1+\ldots+k_m=n} HOK(k_1, \ldots, k_m) }[/math].

Например, 5 = 2 + 3 и НОК(2,3) = 6. Никакое другое разбиение не даёт бо́льшее наименьшее общее кратное, следовательно [math]\displaystyle{ g(5) = 6 }[/math]. Элемент порядка 6 в группе [math]\displaystyle{ S_5 }[/math] может быть записан в виде произведения двух циклов: (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, … — последовательность A000793 в OEIS, названа в честь Эдмунда Ландау, доказавшего в 1902 году^[1], что

[math]\displaystyle{ \lim_{n\to\infty}\frac{\ln(g(n))}{\sqrt{n \ln(n)}} = 1 }[/math]

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

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

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

[math]\displaystyle{ \ln g(n)\lt \sqrt{\operatorname{Li}^{-1}(n)} }[/math]

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

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

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

Примечания

↑ Landau, pp. 92-103

Литература

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. Landau Function (англ.) на сайте Wolfram MathWorld.
последовательность A000793 в OEIS — функция Ландау для натуральных чисел.

[1] Landau, pp. 92-103

[1]