Функция Мёбиуса: определение, свойства и обращение

Функция Мёбиуса $\mu(n)$ - простой на вид арифметический объект, который оказывается ключом к формуле обращения, представлению $1/\zeta(s)$ в виде ряда Дирихле и асимптотикам распределения бесквадратных чисел. Август Фердинанд Мёбиус ввёл её в 1832 году, и с тех пор она стала рабочим инструментом аналитической теории чисел и комбинаторики.

Определение

Функция $\mu: \mathbb{N} \to \{-1, 0, 1\}$ задаётся по разложению $n$ на простые множители:

$$\mu(n) = \begin{cases} 1, & n = 1, \\ (-1)^k, & n = p_1 p_2 \cdots p_k, \text{ все } p_i \text{ различны}, \\ 0, & \text{в разложении есть квадрат простого}. \end{cases}$$

Иначе говоря, $\mu(n) \neq 0$ тогда и только тогда, когда $n$ - бесквадратное (square-free) число, то есть не делится ни на один квадрат простого числа. Знак - это чётность числа простых множителей.

Несколько значений на маленьких аргументах:

• $\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(5) = -1$ - одно простое.
• $\mu(6) = \mu(2 \cdot 3) = 1$, $\mu(10) = 1$, $\mu(15) = 1$ - два разных простых.
• $\mu(30) = \mu(2 \cdot 3 \cdot 5) = -1$ - три разных простых.
• $\mu(4) = \mu(2^2) = 0$, $\mu(12) = \mu(2^2 \cdot 3) = 0$, $\mu(100) = 0$.

Подставь своё $n$ ниже и выбери, что нужно: значение $\mu(n)$, сумму Мертенса $M(x)$, обращение Мёбиуса или подсчёт бесквадратных чисел до $x$.

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

Функция Мёбиуса мультипликативна: если $\gcd(m, n) = 1$, то

$$\mu(mn) = \mu(m)\,\mu(n).$$

Проверка прямая: при взаимной простоте разложения $m$ и $n$ не пересекаются по простым, и квадрат в $mn$ появится тогда и только тогда, когда он уже был в $m$ или в $n$. Если оба бесквадратные с $k$ и $\ell$ простыми, то $mn$ - бесквадратное с $k + \ell$ простыми, и $(-1)^{k+\ell} = (-1)^k (-1)^\ell$.

Важно: $\mu$ не вполне мультипликативна. Для $\mu(p \cdot p) = \mu(p^2) = 0$, а $\mu(p)\mu(p) = 1$ - равенство ломается, когда $\gcd \neq 1$.

Ключевое тождество

Сердце почти всех применений - формула

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

Доказательство быстрое. При $n = 1$ сумма пуста, кроме $d = 1$, и равна $\mu(1) = 1$. Для $n > 1$ запишем $n = p_1^{a_1} \cdots p_k^{a_k}$. В сумму вкладываются только бесквадратные делители $d$, то есть произведения подмножеств $\{p_1, \ldots, p_k\}$. По биному

$$\sum_{d \mid n,\, d \text{ б/кв}} \mu(d) = \sum_{j=0}^{k} \binom{k}{j} (-1)^j = (1 - 1)^k = 0.$$

Эту формулу удобно читать как аналог индикатора единицы через делители.

Обращение Мёбиуса

Главное практическое применение - формула обращения, связывающая две арифметические функции $f$ и $g$, связанные суммированием по делителям.

Теорема. Пусть $f, g: \mathbb{N} \to \mathbb{C}$. Тогда

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

В обратную сторону симметрично: если знаешь сумму $g$, можешь «вытащить» $f$ свёрткой с $\mu$.

Доказательство - подстановка одной формулы в другую и применение ключевого тождества:

$$\sum_{d \mid n} \mu\!\left(\tfrac{n}{d}\right) \sum_{e \mid d} f(e) = \sum_{e \mid n} f(e) \sum_{d': d' \mid n/e} \mu(d') = \sum_{e \mid n} f(e) [n/e = 1] = f(n).$$

На языке свёртки Дирихле $f * g = \sum_{d \mid n} f(d) g(n/d)$ это запись $g = f * \mathbf{1}$ и $f = g * \mu$, где $\mu$ - обратный к константной единице $\mathbf{1}$ относительно свёртки: $\mathbf{1} * \mu = \varepsilon$, $\varepsilon(n) = [n = 1]$.

Классический пример - функция Эйлера: $\sum_{d \mid n} \varphi(d) = n$, откуда $\varphi(n) = \sum_{d \mid n} \mu(d) \cdot (n/d) = n \sum_{d \mid n} \mu(d)/d$.

Связь с дзета-функцией Римана

В аналитической теории чисел $\mu(n)$ задаёт ряд Дирихле, обратный к дзета-функции:

$$\frac{1}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s}, \quad \operatorname{Re} s > 1.$$

Это прямое следствие эйлерова произведения $\zeta(s) = \prod_p (1 - p^{-s})^{-1}$: при раскрытии $(1 - p^{-s})$ в произведении знак $-$ для каждого $p$, входящего в $n$ ровно один раз, и ноль для повторов - это в точности правило $\mu(n)$.

Из тождества $\zeta(s) \cdot \zeta(s)^{-1} = 1$ выводится свёртка $\mathbf{1} * \mu = \varepsilon$ - то есть ключевое тождество выше.

Функция Мертенса и связь с гипотезой Римана

Сумма

$$M(x) = \sum_{n \leq x} \mu(n)$$

называется функцией Мертенса. Простая граница $|M(x)| \leq x$ тривиальна; нетривиальные оценки связаны с распределением нулей $\zeta(s)$.

• Теорема о простых числах эквивалентна $M(x) = o(x)$.
• Гипотеза Римана эквивалентна оценке $M(x) = O(x^{1/2 + \varepsilon})$ для любого $\varepsilon > 0$.
• Гипотеза Мертенса утверждала более сильное $|M(x)| \leq \sqrt{x}$ и была опровергнута в 1985 году Одлыжко и те Риле - но конкретный контрпример пока не найден, известно лишь, что он существует.
• Гипотеза Литтлвуда (теорема, 1914) гарантирует, что $M(x)/\sqrt{x}$ не ограничено сверху и снизу.

Несмотря на жёсткие колебания знака, в среднем $\mu$ ведёт себя «как случайный» $\pm 1$ - это содержательное проявление неупорядоченности простых чисел.

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

Число бесквадратных чисел до $x$. Обозначим $Q(x) = \#\{n \leq x : n \text{ бесквадратно}\}$. Через индикатор $[n \text{ б/кв}] = \sum_{d^2 \mid n} \mu(d)$ получаем

$$Q(x) = \sum_{n \leq x} \sum_{d^2 \mid n} \mu(d) = \sum_{d \leq \sqrt{x}} \mu(d) \lfloor x/d^2 \rfloor \sim \frac{x}{\zeta(2)} = \frac{6x}{\pi^2}.$$

Доля бесквадратных чисел - $6/\pi^2 \approx 0{,}6079$.

Среднее $\mu(n)/n$. Сумма $\sum_{n \leq x} \mu(n)/n$ стремится к нулю при $x \to \infty$ - это снова эквивалент теоремы о простых числах.

Включение–исключение. Для подсчёта чисел, не делящихся ни на одно из простых $p_1, \ldots, p_k$ до $N$, выражение через $\mu$ компактно:

$$\#\{n \leq N : \gcd(n, p_1 \cdots p_k) = 1\} = \sum_{d \mid p_1 \cdots p_k} \mu(d) \lfloor N/d \rfloor.$$

Это работающая форма решета Лежандра - фундамент решета Эратосфена и более тонких решет Бруна и Сельберга.

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

• Считать $\mu(n^2) = \mu(n)^2$. Нет: $\mu(n^2) = 0$ для всех $n > 1$, тогда как $\mu(n)^2$ - индикатор бесквадратности.
• Применять обращение Мёбиуса к функциям, не связанным суммированием по делителям. Формула работает только для пар $(f, g)$, у которых $g(n) = \sum_{d \mid n} f(d)$.
• Считать, что $\sum_{n \leq x} \mu(n) = 0$ строго - на самом деле $M(x)$ постоянно «болтается» вокруг нуля с медленно растущей амплитудой, нулевым значение бывает лишь в отдельных точках.
• Путать мультипликативность ($\gcd = 1$) и полную мультипликативность (для любых $m, n$). Мёбиус - только мультипликативная.
• Забывать про знак: $\mu(p_1 p_2 p_3) = -1$, не $+1$. Считают простые в разложении, а не их позицию.

FAQ

Можно ли по $\mu(n)$ восстановить $n$? Нет, $\mu$ принимает всего три значения, поэтому она «теряет» структуру. По таблице $\mu(d)$ для $d \mid n$ можно восстановить множество бесквадратных делителей и через них - радикал $\operatorname{rad}(n) = \prod_{p \mid n} p$, но не показатели простых.

Как быстро посчитать $\mu(n)$ на большом интервале? Решетом Эратосфена за $O(N \log \log N)$. Для одного $n$ - сначала факторизуют $n$, потом смотрят знак: если есть квадрат - ноль, иначе $(-1)^k$ по числу простых.

Что общего у $\mu$ и принципа включения–исключения? Прямая связь: классическая формула $|A_1 \cup \cdots \cup A_k| = \sum (-1)^{|S|+1} |A_S|$ - частный случай обращения Мёбиуса на решётке подмножеств. Знак $(-1)^{|S|}$ совпадает с $\mu(d)$ для $d$, равного произведению соответствующих простых, - отсюда универсальность $\mu$ в комбинаторных подсчётах.

Коротко

Функция Мёбиуса $\mu(n)$ - индикатор бесквадратности со знаком чётности числа простых множителей. Её мультипликативность и ключевое тождество $\sum_{d \mid n} \mu(d) = [n = 1]$ открывают обращение Мёбиуса: переход между $g(n) = \sum_{d \mid n} f(d)$ и $f(n) = \sum_{d \mid n} \mu(n/d) g(d)$. Через ряды Дирихле $\mu$ задаёт $1/\zeta(s)$, а её частичные суммы $M(x)$ упираются в гипотезу Римана. На уровне приложений $\mu$ - мостик к решетам, формулам Эйлера для $\varphi$, асимптотике числа бесквадратных и систематической форме включения–исключения.