Функция Мёбиуса¶

Функция Мёбиуса — это мультипликативная арифметическая функция, определённая на множестве натуральных чисел и принимающая значения {−1, 0, 1}. Она играет фундаментальную роль в теории чисел, комбинаторике и теории функций, в частности, в формуле обращения Мёбиуса и в аналитической теории чисел.

¶Определение

Функция Мёбиуса, обозначаемая греческой буквой μ (мю) или μ(n), определяется следующим образом:

• μ(1) = 1.
• Если n делится на квадрат простого числа (то есть n не является свободным от квадратов), то μ(n) = 0.
• Если n является свободным от квадратов (то есть его разложение на простые множители содержит каждый простой множитель ровно один раз) и содержит k различных простых множителей, то μ(n) = (−1)^k.

Иными словами, μ(n) = 0 для чисел, у которых есть повторяющийся простой делитель; для чисел, не имеющих квадратных делителей, значение равно 1, если число имеет чётное количество простых множителей, и −1, если нечётное.

Например:

• μ(1) = 1.
• μ(2) = −1 (одно простое число, k=1).
• μ(3) = −1.
• μ(4) = 0 (делится на 2²).
• μ(5) = −1.
• μ(6) = 1 (два простых множителя: 2 и 3, k=2).
• μ(7) = −1.
• μ(8) = 0 (делится на 2²).
• μ(9) = 0 (делится на 3²).
• μ(10) = 1 (2 и 5, k=2).

¶Свойства

¶Мультипликативность

Функция Мёбиуса является мультипликативной: для любых взаимно простых натуральных чисел m и n выполняется равенство μ(mn) = μ(m) μ(n). Это свойство следует из определения, так как разложение на простые множители для взаимно простых чисел не пересекается.

¶Сумма по делителям

Одно из важнейших свойств функции Мёбиуса — сумма её значений по всем положительным делителям числа n равна 1, если n = 1, и 0, если n > 1:

\[ \sum_{d \mid n} \mu(d) = \begin{cases} 1, & n = 1, \\ 0, & n > 1. \end{cases} \]

Это свойство является ключевым для формулы обращения Мёбиуса.

¶Производящая функция

Ряд Дирихле для функции Мёбиуса имеет вид:

\[ \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}, \]

где ζ(s) — дзета-функция Римана. Этот ряд сходится при Re(s) > 1 и аналитически продолжается на всю комплексную плоскость, за исключением полюса в s = 1.

¶Связь с функцией Эйлера

Функция Мёбиуса связана с функцией Эйлера φ(n) (количество чисел, меньших n и взаимно простых с n) следующим образом:

\[ \varphi(n) = n \sum_{d \mid n} \frac{\mu(d)}{d}. \]

¶Формула обращения Мёбиуса

Формула обращения Мёбиуса — это классический результат, позволяющий выразить одну арифметическую функцию через другую. Пусть f(n) и g(n) — арифметические функции, связанные соотношением:

\[ g(n) = \sum_{d \mid n} f(d). \]

Тогда

\[ f(n) = \sum_{d \mid n} \mu(d) \, g\left(\frac{n}{d}\right). \]

Эта формула имеет широкое применение в теории чисел, комбинаторике и теории графов. Например, она используется для подсчёта количества неприводимых многочленов над конечным полем, для вычисления количества циклических подгрупп в конечных абелевых группах, а также в классической задаче о подсчёте количества чисел, взаимно простых с заданным числом.

¶История

Функция Мёбиуса была введена немецким математиком Августом Фердинандом Мёбиусом в 1832 году в его работе «Über eine besondere Art von Umkehrung der Reihen» («Об одном особом виде обращения рядов»). Мёбиус изучал её в контексте обращения рядов и теории чисел. Однако систематическое применение функции в теории чисел началось позже, в работах Леонарда Эйлера и Карла Фридриха Гаусса, которые независимо использовали её в различных контекстах. Название «функция Мёбиуса» закрепилось в конце XIX века.

¶Применения

¶Теория чисел

• Подсчёт количества простых чисел: Функция Мёбиуса используется в формуле для функции Мертенса M(n) = ∑_{k=1}^{n} μ(k), которая связана с гипотезой Римана. Гипотеза Мертенса (утверждавшая, что |M(n)| < √n для всех n > 1) была опровергнута в 1985 году, но её связь с распределением простых чисел остаётся важной.
• Формула включения-исключения: Функция Мёбиуса является инструментом для реализации принципа включения-исключения в арифметике. Например, количество чисел, не превосходящих N и взаимно простых с n, выражается через сумму по делителям n с коэффициентами μ(d).
• Дзета-функция Римана: Обратная величина дзета-функции выражается через ряд Дирихле с функцией Мёбиуса, что используется в аналитической теории чисел для изучения свойств простых чисел.

¶Комбинаторика

В комбинаторике функция Мёбиуса применяется в теории частично упорядоченных множеств (ЧУМ). Для любого конечного ЧУМ можно определить функцию Мёбиуса, обобщающую арифметическую функцию Мёбиуса. Эта комбинаторная функция Мёбиуса используется для обращения сумм по цепям и имеет приложения в перечислительной комбинаторике, теории графов и топологии.

¶Криптография

В криптографии функция Мёбиуса используется в некоторых алгоритмах, связанных с факторизацией чисел и построением псевдослучайных последовательностей. Например, она применяется в алгоритмах на основе решёток и в некоторых схемах шифрования с открытым ключом.

¶Функция Мертенса

Функция Мертенса M(n) определяется как сумма значений функции Мёбиуса для всех натуральных чисел от 1 до n:

\[ M(n) = \sum_{k=1}^{n} \mu(k). \]

Эта функция связана с распределением простых чисел и с гипотезой Римана. Гипотеза Римана эквивалентна утверждению, что для любого ε > 0 выполняется M(n) = O(n^{1/2 + ε}). Поведение функции Мертенса изучается в аналитической теории чисел; известно, что она неограниченно колеблется, принимая как положительные, так и отрицательные значения.

¶Примеры и таблицы

Ниже приведены значения функции Мёбиуса для первых 20 натуральных чисел:

¶Вариации и обобщения

• Функция Мёбиуса для частично упорядоченных множеств: В комбинаторике и теории решёток аналог функции Мёбиуса определяется для любого конечного ЧУМ. Она обобщает арифметическую функцию Мёбиуса и используется в формуле обращения Мёбиуса для ЧУМ.
• Функция Мёбиуса для колец многочленов: В теории чисел рассматривается функция Мёбиуса для многочленов над конечными полями, которая определяется аналогично арифметической, но для неприводимых многочленов.
• Функция Мёбиуса для групп: В теории групп можно определить функцию Мёбиуса для подгрупп конечных групп, используя решётку подгрупп.

¶Интересные факты

• Функция Мёбиуса принимает значение 0 для большинства натуральных чисел: плотность чисел, свободных от квадратов, равна 6/π² ≈ 0,6079, то есть около 60,8% чисел не имеют квадратных делителей.
• Значение μ(n) = 1 для чисел, являющихся произведением чётного числа различных простых чисел, например, для 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95.
• Значение μ(n) = −1 для чисел, являющихся произведением нечётного числа различных простых чисел, например, для всех простых чисел, а также для 30 (2·3·5), 42 (2·3·7), 66 (2·3·11), 70 (2·5·7), 78 (2·3·13), 102 (2·3·17), 105 (3·5·7), 110 (2·5·11), 114 (2·3·19), 130 (2·5·13), 138 (2·3·23), 154 (2·7·11), 165 (3·5·11), 170 (2·5·17), 174 (2·3·29), 182 (2·7·13), 186 (2·3·31), 190 (2·5·19), 195 (3·5·13), 222 (2·3·37), 230 (2·5·23), 231 (3·7·11), 238 (2·7·17), 246 (2·3·41), 255 (3·5·17), 258 (2·3·43), 266 (2·7·19), 273 (3·7·13), 282 (2·3·47), 285 (3·5·19), 286 (2·11·13), 290 (2·5·29), 310 (2·5·31), 318 (2·3·53), 322 (2·7·23), 345 (3·5·23), 354 (2·3·59), 357 (3·7·17), 366 (2·3·61), 370 (2·5·37), 374 (2·11·17), 385 (5·7·11), 390 (2·3·5·13), 399 (3·7·19), 402 (2·3·67), 406 (2·7·29), 410 (2·5·41), 418 (2·11·19), 426 (2·3·71), 429 (3·11·13), 430 (2·5·43), 434 (2·7·31), 435 (3·5·29), 438 (2·3·73), 442 (2·13·17), 445 (5·89), 447 (3·149), 451 (11·41), 453 (3·151), 454 (2·227), 455 (5·7·13), 458 (2·229), 462 (2·3·7·11), 465 (3·5·31), 466 (2·233), 469 (7·67), 470 (2·5·47), 471 (3·157), 473 (11·43), 474 (2·3·79), 478 (2·239), 481 (13·37), 482 (2·241), 483 (3·7·23), 485 (5·97), 486 (2·3⁵), 489 (3·163), 490 (2·5·7²), 493 (17·29), 494 (2·13·19), 495 (3²·5·11), 497 (7·71), 498 (2·3·83), 499 (простое), 500 (2²·5³).

¶Источники

• Виноградов И. М. Основы теории чисел. — М.: Наука, 1981.
• Чандрасекхаран К. Введение в аналитическую теорию чисел. — М.: Мир, 1974.
• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.
• Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. — Oxford University Press, 2008.
• Apostol T. M. Introduction to Analytic Number Theory. — Springer, 1976.