Формула обращения Мёбиуса: вывод и применения

Если арифметическая функция $f$ задана как сумма значений другой функции $g$ по всем делителям аргумента, обращение Мёбиуса даёт явное выражение для $g$ через $f$. Это не отдельная теорема для частных случаев, а универсальная техника инверсии, из которой выводятся формула для тотиента Эйлера, подсчёт неприводимых многочленов над конечным полем и связь $1/\zeta(s)$ с рядом Дирихле для $\mu$.

Точная формулировка

Пусть $f, g: \mathbb{N} \to \mathbb{C}$ связаны соотношением

$$f(n) = \sum_{d \mid n} g(d), \qquad n \in \mathbb{N}.$$

Тогда, эквивалентно,

$$g(n) = \sum_{d \mid n} \mu(d)\, f\!\left(\tfrac{n}{d}\right) = \sum_{d \mid n} \mu\!\left(\tfrac{n}{d}\right) f(d).$$

Обе записи равны: суммирование идёт по парам $(d, n/d)$, разница только в том, какой элемент пары обозначен буквой $d$. Импликация обратима: из $g(n) = \sum_{d \mid n} \mu(d) f(n/d)$ обратно следует $f(n) = \sum_{d \mid n} g(d)$.

Набросок доказательства

Ключ - тождество для функции Мёбиуса:

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

Подставим определение $f$ в правую часть обращения и поменяем порядок суммирования. Пара $(d, e)$ с $d \mid n$ и $e \mid n/d$ - то же самое, что пара $(d, e)$ с $de \mid n$:

$$\sum_{d \mid n} \mu(d)\, f\!\left(\tfrac{n}{d}\right) = \sum_{d \mid n} \mu(d) \sum_{e \mid n/d} g(e) = \sum_{e \mid n} g(e) \sum_{d \mid n/e} \mu(d).$$

Внутренняя сумма равна $[n/e = 1]$, то есть единице только при $e = n$. Все остальные слагаемые обнуляются, остаётся $g(n)$. Это и есть требуемое равенство.

Тот же приём работает в обратную сторону, поэтому соотношения $f = \sum g$ и $g = \sum \mu f$ - две стороны одной биекции на пространстве арифметических функций.

Тотиент Эйлера

Классический пример. Известно, что $\sum_{d \mid n} \varphi(d) = n$ - каждый делитель $d$ считает дроби $k/n$ со знаменателем ровно $n/d$ после сокращения, а всего таких дробей $n$ штук. Возьмём $f(n) = n$ и $g(n) = \varphi(n)$. Обращение даёт:

$$\varphi(n) = \sum_{d \mid n} \mu(d)\, \frac{n}{d} = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$

Последнее равенство получается раскрытием суммы по бесквадратным делителям $d = p_{i_1} \cdots p_{i_k}$ - каждое слагаемое - это произведение $-1/p$ по выбранным простым. Сумма факторизуется в произведение Эйлера. Это та самая формула, по которой в практических задачах считают $\varphi(n)$ через разложение на простые.

Число неприводимых многочленов над конечным полем

Пусть $N_q(n)$ - число нормированных неприводимых многочленов степени $n$ над $\mathbb{F}_q$. Тогда $x^{q^n} - x$ разлагается в произведение всех неприводимых многочленов, чьи степени делят $n$:

$$q^n = \sum_{d \mid n} d \cdot N_q(d).$$

Обозначим $f(n) = q^n$ и $g(d) = d \cdot N_q(d)$. Обращение Мёбиуса даёт замкнутую формулу Гаусса:

$$N_q(n) = \frac{1}{n} \sum_{d \mid n} \mu(d)\, q^{n/d}.$$

Например, для $q = 2$, $n = 6$: делители $\{1, 2, 3, 6\}$, $\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(6) = 1$. Получаем $N_2(6) = (2^6 - 2^3 - 2^2 + 2^1)/6 = (64 - 8 - 4 + 2)/6 = 9$. Без обращения Мёбиуса задача требовала бы прямого перебора многочленов.

Аддитивная версия

Соотношение $f = \sum g$ можно записать и для функций со значениями в любой абелевой группе - не только в $\mathbb{C}$. Если $f(n) = \sum_{d \mid n} g(d)$ выполнено как тождество в $\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}$ или кольце многочленов, обращённое равенство тоже даёт корректную формулу. Это и эксплуатируется в формуле для $N_q(n)$: правая часть всегда целая, потому что левая исходно целая, а обращение - обратимая линейная операция.

Для функций, заданных через произведение $f(n) = \prod_{d \mid n} g(d)$, есть мультипликативный аналог: $g(n) = \prod_{d \mid n} f(n/d)^{\mu(d)}$. Из него выводится, например, разложение $n$-го кругового многочлена $\Phi_n(x)$ через $x^d - 1$.

Производящие функции и ряды Дирихле

Соответствие $f \leftrightarrow F(s) = \sum_{n \geq 1} f(n)/n^s$ переводит свёртку Дирихле $(f * g)(n) = \sum_{d \mid n} f(d) g(n/d)$ в обычное произведение рядов: $F(s) \cdot G(s) = \sum (f * g)(n)/n^s$.

Соотношение $f = 1 * g$, где $1$ - функция, тождественно равная единице, на языке рядов выглядит как $F(s) = \zeta(s) \cdot G(s)$, потому что $\zeta(s) = \sum 1/n^s$. Деление даёт формальное равенство:

$$G(s) = \frac{F(s)}{\zeta(s)} = F(s) \sum_{n \geq 1} \frac{\mu(n)}{n^s}.$$

Перемножая ряды и собирая коэффициент при $1/n^s$, снова получаем поточечную формулу обращения. Эта картинка объясняет, почему функция Мёбиуса появляется в выражении $1/\zeta(s) = \sum \mu(n)/n^s$: она реализует обратный элемент к $\mathbf{1}$ относительно свёртки Дирихле.

Обобщение на частично упорядоченные множества

В 1964 году Рота заметил, что та же конструкция работает для любой локально конечной частично упорядоченной структуры. Для произвольного частично упорядоченного множества $P$ определяется функция Мёбиуса $\mu_P(x, y)$ так, чтобы $\sum_{x \leq z \leq y} \mu_P(z, y) = [x = y]$. Тогда из $f(y) = \sum_{x \leq y} g(x)$ автоматически следует $g(y) = \sum_{x \leq y} \mu_P(x, y) f(x)$.

Классический Мёбиус $\mu(n)$ - частный случай для частично упорядоченного множества натуральных чисел с делимостью, где $\mu_P(d, n) = \mu(n/d)$. Обобщённая теория Рота даёт, например, элегантные доказательства формулы включений-исключений (для частично упорядоченного множества подмножеств конечного множества), формулы для хроматического многочлена графа и подсчёта циклов в группах.

Типовые задачи

1. Подсчёт ожерелий. Сколько различных бусинных ожерелий из $n$ бусин $k$ цветов с точностью до циклического сдвига? Формула Бернсайда даёт $\frac{1}{n} \sum_{d \mid n} \varphi(d)\, k^{n/d}$. Если же фиксировать ожерелья без поворотной симметрии (то есть с минимальным периодом ровно $n$), их число $L(n, k) = \frac{1}{n} \sum_{d \mid n} \mu(d)\, k^{n/d}$. Это та же формула Гаусса в другой обёртке - апериодические слова длины $n$ над алфавитом из $k$ символов.

2. Сумма Эйлера через включение-исключение. Формула $\varphi(n) = n \prod (1 - 1/p)$ - это включение-исключение по событиям «$k$ делится на $p_i$» среди $k = 1, \ldots, n$. Каждый Мёбиус-коэффициент в $\sum \mu(d) n/d$ кодирует знак вклада подмножества простых.

3. Свёрточные тождества. Из $\sigma(n) = \sum_{d \mid n} d$ и обращения Мёбиуса следует $n = \sum_{d \mid n} \mu(d) \sigma(n/d)$. Аналогичные тождества дают красивые формулы для функции количества делителей $\tau(n)$, суммы $k$-х степеней делителей $\sigma_k(n)$ и Якобиевой функции.

Частые ошибки

• Перепутаны аргументы $\mu$ и $f$. Правильно: $g(n) = \sum_{d \mid n} \mu(d) f(n/d) = \sum_{d \mid n} \mu(n/d) f(d)$. Запись $\sum \mu(n/d) f(n/d)$ не имеет смысла.
• Применение к функции с другим типом аргумента. Обращение работает на множестве натуральных чисел с делимостью. Для функций над сравнениями или с непрерывным аргументом нужна другая (обобщённая) версия Мёбиуса.
• Забыли проверить локальную конечность. В обобщении Рота сумма $\sum_{x \leq z \leq y}$ должна быть конечной для всех пар $x \leq y$ - иначе $\mu_P$ не определена.
• Игнор знаков. Знак $\mu(d) = (-1)^k$ зависит от числа простых делителей; легко промахнуться, забыв что $\mu(1) = +1$, а не ноль.
• Перемножение рядов без сходимости. Тождество $G(s) = F(s)/\zeta(s)$ как ряды Дирихле выполняется формально (на уровне коэффициентов), но для аналитической работы нужна абсолютная сходимость в нужной полуплоскости.

FAQ

Где взять значения функции $\mu(n)$? Из определения: $\mu(1) = 1$, $\mu(p) = -1$ для простого $p$, $\mu(p_1 \cdots p_k) = (-1)^k$ для попарно различных простых, $\mu(n) = 0$, если $n$ делится на квадрат простого. Для конкретных $n$ удобно сначала разложить на простые.

Чем обращение Мёбиуса отличается от включения-исключения? Принцип включения-исключения - частный случай обращения для частично упорядоченного множества подмножеств конечного множества с порядком по вложению. Классическое обращение Мёбиуса в теории чисел - то же самое для множества делителей.

Можно ли применить формулу обращения, если $f(n)$ задана только на конечном множестве $n$? Да, формула чисто алгебраическая: для конкретного $n$ значение $g(n)$ зависит только от значений $f$ на делителях $n$. Если эти значения известны - обращение даёт ответ независимо от поведения $f$ дальше.

Коротко

Формула обращения Мёбиуса - биекция на пространстве арифметических функций, превращающая «суммы по делителям» в «суммы со знаком функции Мёбиуса». Из неё выводятся компактная формула для тотиента Эйлера, формула Гаусса для числа неприводимых многочленов над конечным полем и тождество $1/\zeta(s) = \sum \mu(n)/n^s$ на языке рядов Дирихле. Обобщение Рота переносит конструкцию на произвольные локально конечные частично упорядоченные множества, объединяя обращение Мёбиуса и формулу включений-исключений в единую схему.