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

Не слід плутати з символами Ландау.

Функція Ландау g (n) в теорії чисел, названа на честь німецького математика Едмунда Ландау, визначається для будь-якого натурального числа n як найбільший порядок елемента симетричної групи S_n .


1. Визначення

Еквівалентні визначення: g (n) одно найбільшому з найменших загальних кратних (НОК) за всіма Розбиття числа n, або максимальному числа раз, яке підстановка з n елементів може бути послідовно застосована до першої появи первісної послідовності. Таким чином, формально:

g (n) = \ max \ limits_ {k_1 + \ ldots + k_m = n} HOK (k_1, \ ldots, k_m) .

Наприклад, 5 = 2 + 3 і НОК (2,3) = 6. Ніяке інше розбиття не дає більшу найменше спільне кратне, отже g (5) = 6 . Елемент порядку 6 в групі S_5 може бути записаний у вигляді добутку двох циклів: (1 2) (3 4 5).


2. Властивості

Цілочисельна послідовність 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], що

\ 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, ... (послідовність A103635 в OEIS).

Твердження про те, що

\ Ln g (n) <\ sqrt {\ mathrm {Li} ^ {-1} (n)}

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

Інші співвідношення:

  • НОК (1, 2, ..., n) \ Leqslant g \ left (\ frac {n (n +1)} {2} \ right) \ sim e ^ {\ sqrt {\ frac {n (n +1)} {2} \ ln \ frac {n ( n +1)} {2}}} . Перше нерівність випливає з того, що 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, ... (послідовність A129759 в OEIS). J.-L. Nicolas в 1969 показав, що gpf (g (n)) \ sim \ sqrt {n \ ln n} . J.-P. Massias et al. (1988, 1989) показали, що для всіх n \ geqslant 2 , gpf (g (n)) \ leqslant \ sqrt {n \ ln n} , А J. Grantham (1995) показав, що для всіх n \ geqslant 5 , Константа 2,86 може бути поліпшена до 1,328.

Примітки

  1. 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.