Можно ли восстановить исходные числа, если известна только их сумма? Математика формулы обращения Мёбиуса

1. Введение: фундаментальная обратная задача математики

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

Рассмотрим три классических примера:

Периодические строки и апериодические слова Линдона: Над алфавитом из $q$ символов существует ровно $g(n) = q^n$ строк длины $n$. Однако в это число входят вырожденные периодические строки, образованные повторением более короткого блока минимального периода $d \mid n$. Если $f(d)$ — число истинно апериодических строк минимального периода $d$, то выполняется сумма по делителям: $g(n) = \sum_{d \mid n} f(d)$
Сократимые и несократимые дроби (функция Эйлера $\varphi(n)$): Если сократить все $n$ дробей $\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}$, каждый приведенный знаменатель окажется делителем $d \mid n$. Поскольку существует ровно $\varphi(d)$ несократимых дробей со знаменателем $d$, получаем классическое тождество Гаусса: $n = \sum_{d \mid n} \varphi(d)$
Суммы по подмножествам и формула включений-исключений (PIE): Если каждое подмножество $A \subseteq S$ несет собственный вес $f(A)$, но измерима лишь накопленная сумма $g(B) = \sum_{A \subseteq B} f(A)$, как восстановить $f(B)$?

\[f(6) = g(6) - g(3) - g(2) + g(1)\]\[f(12) = g(12) - g(6) - g(4) + g(2)\]

Поразительно, но хотя $3$ и $1$ делят $12$, слагаемые $g(3)$ и $g(1)$ входят с коэффициентом $0$ (так как частные $12/3 = 4 = 2^2$ и $12/1 = 12 = 2^2 \cdot 3$ делятся на квадрат простого числа)!

В 1832 году немецкий математик Август Фердинанд Мёбиус решил эту задачу, введя функцию Мёбиуса $\mu(n)$. В 1964 году Джан-Карло Рота обобщил этот принцип на частично упорядоченные множества (посеты) и их алгебры инцидентности, доказав, что теоретико-числовое обращение Мёбиуса, принцип включений-исключений, основная теорема дискретного анализа и связь моментов с кумулянтами в теории вероятностей — это частные случаи единого уравнения $\mu = \zeta^{-1}$.

  flowchart TD
    A["Чистая первичная величина f(n)<br/>(Трудно наблюдать или считать напрямую)"] -->|"Сумма по делителям<br/>(Свертка Дирихле с 1: g = f * 1)"| B["Наблюдаемая сумма g(n) = Σ_{d|n} f(d)<br/>(Легко вычислить, содержит наложения)"]
    B -->|"Формула обращения Мёбиуса<br/>(Свертка с обратным элементом μ = 1⁻¹: f = g * μ)"| C["Точное восстановление f(n)<br/>f(n) = Σ_{d|n} μ(d) g(n/d)"]
    D["Функция Мёбиуса μ(n) ∈ {-1, 0, 1}<br/>0 если p²|n; (-1)^k для k различных простых"] -.->|"Точно компенсирует кратные учеты"| C

2. Функция Мёбиуса $\mu(n)$: определение, мультипликативность и основное тождество

2.1 Строгое определение

\[\mu(n) = \begin{cases} 1, & \text{если } n = 1, \\[4pt] (-1)^k, & \text{если } n = p_1 p_2 \cdots p_k \text{ — произведение } k \text{ различных простых чисел (свободно от квадратов)}, \\[4pt] 0, & \text{если } p^2 \mid n \text{ для некоторого простого } p. \end{cases}\]

$n$	Разложение на простые	Свободно от квадратов?	Число простых $k$	Функция Мёбиуса $\mu(n)$	Функция Мертенса $M(n) = \sum_{m=1}^n \mu(m)$
$1$	$1$ (пустое произведение)	Да	$0$	$+1$	$+1$
$2$	$2$	Да	$1$	$-1$	$0$
$3$	$3$	Да	$1$	$-1$	$-1$
$4$	$2^2$	Нет ($2^2 \mid 4$)	—	$0$	$-1$
$5$	$5$	Да	$1$	$-1$	$-2$
$6$	$2 \cdot 3$	Да	$2$	$+1$	$-1$
$7$	$7$	Да	$1$	$-1$	$-2$
$8$	$2^3$	Нет ($2^2 \mid 8$)	—	$0$	$-2$
$9$	$3^2$	Нет ($3^2 \mid 9$)	—	$0$	$-2$
$10$	$2 \cdot 5$	Да	$2$	$+1$	$-1$
$11$	$11$	Да	$1$	$-1$	$-2$
$12$	$2^2 \cdot 3$	Нет ($2^2 \mid 12$)	—	$0$	$-2$

2.2 Мультипликативность и основное тождество

Мультипликативность: Если $\gcd(a, b) = 1$, то $\mu(ab) = \mu(a)\mu(b)$. Доказательство: Если $a$ или $b$ делится на квадрат $p^2$, то и $ab$ делится на $p^2$, так что обе части равны $0$. Если оба числа свободны от квадратов и содержат $r$ и $s$ простых множителей, то при $\gcd(a, b) = 1$ их простые делители не пересекаются и $\mu(ab) = (-1)^{r+s} = (-1)^r (-1)^s = \mu(a)\mu(b)$. $\blacksquare$
\[\sum_{d \mid n} \mu(d) = \varepsilon(n) := \begin{cases} 1, & n = 1, \\ 0, & n > 1. \end{cases}\]\[\sum_{d \mid n} \mu(d) = \sum_{j = 0}^{k} \binom{k}{j} (-1)^j 1^{k - j} = (1 - 1)^k = 0. \quad \blacksquare\]

3. Коммутативное кольцо арифметических функций со сверткой Дирихле

На пространстве арифметических функций $\mathcal{A} = \{f : \mathbb{N}^+ \to \mathbb{C}\}$ свертка Дирихле определяется формулой:

\[(f * g)(n) := \sum_{d \mid n} f(d)\,g\!\left(\frac{n}{d}\right) = \sum_{ab = n} f(a)\,g(b)\]

Множество $(\mathcal{A}, +, *)$ образует коммутативное кольцо с единицей $\varepsilon(n) = [n = 1]$ ($f * \varepsilon = f$). Для постоянной функции $\mathbf{1}(n) = 1$ суммирование по делителям совпадает со сверткой с $\mathbf{1}$: $g(n) = \sum_{d \mid n} f(d) = (f * \mathbf{1})(n)$, то есть $g = f * \mathbf{1}$. Основное тождество $\sum_{d \mid n} \mu(d) = \varepsilon(n)$ означает, что:

\[\mu * \mathbf{1} = \mathbf{1} * \mu = \varepsilon \quad \Longleftrightarrow \quad \mu = \mathbf{1}^{-1}\]

Функция Мёбиуса $\mu$ есть в точности обратный элемент по Дирихле к тождественной единице $\mathbf{1}$! Отсюда классическая формула обращения Мёбиуса доказывается в одну строчку:

\[g = f * \mathbf{1} \iff g * \mu = f * (\mathbf{1} * \mu) = f * \varepsilon = f \iff f(n) = \sum_{d \mid n} \mu(d)\,g\!\left(\frac{n}{d}\right) = \sum_{d \mid n} \mu\!\left(\frac{n}{d}\right) g(d)\]

Ряды Дирихле, дзета-функция Римана $\zeta(s)$ и гипотеза Римана

Сопоставляя каждой функции $f \in \mathcal{A}$ ее ряд Дирихле $D_f(s) = \sum_{n=1}^{\infty} \frac{f(n)}{n^s}$, мы переводим свертку в обычное произведение: $D_{f * g}(s) = D_f(s) D_g(s)$. Так как $D_{\mathbf{1}}(s) = \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$ — дзета-функция Римана, а $D_{\varepsilon}(s) = 1$, тождество $\mathbf{1} * \mu = \varepsilon$ немедленно дает:

\[\zeta(s) \sum_{n = 1}^{\infty} \frac{\mu(n)}{n^s} = 1 \quad \Longrightarrow \quad \frac{1}{\zeta(s)} = \sum_{n = 1}^{\infty} \frac{\mu(n)}{n^s} \qquad (\operatorname{Re}(s) > 1)\]

Асимптотический закон распределения простых чисел эквивалентен $\sum_{n=1}^{\infty} \frac{\mu(n)}{n} = 0$, или $M(x) = \sum_{n \le x} \mu(n) = o(x)$.
Гипотеза Римана (RH) эквивалентна аналитичности $\frac{1}{\zeta(s)}$ в полуплоскости $\operatorname{Re}(s) > \frac{1}{2}$, что равносильно оценке функции Мертенса: $\text{Гипотеза Римана} \quad \Longleftrightarrow \quad M(x) = \sum_{n \le x} \mu(n) = O\!\left(x^{\frac{1}{2} + \varepsilon}\right) \quad (\forall \varepsilon > 0)$

4. Три классических приложения

Функция Эйлера $\varphi(n)$: Из $\sum_{d \mid n} \varphi(d) = n$ ($\varphi * \mathbf{1} = \mathrm{id}$) обращением с $\mu$ получаем $\varphi = \mathrm{id} * \mu$: $\varphi(n) = \sum_{d \mid n} \mu(d)\,\frac{n}{d} = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$
Апериодические ожерелья (слова Линдона) и неприводимые многочлены над $\mathbb{F}_q$: Как число $N_q(d)$ апериодических ожерелий длины $d$ над алфавитом из $q$ букв, так и число $I_q(d)$ нормированных неприводимых многочленов степени $d$ над конечным полем $\mathbb{F}_q$ (поскольку $x^{q^n} - x = \prod_{d \mid n} \prod_{\deg P = d} P(x)$) удовлетворяют соотношению $q^n = \sum_{d \mid n} d \cdot N_q(d) = \sum_{d \mid n} d \cdot I_q(d)$. Обращение Мёбиуса дает формулу Гаусса: $N_q(n) = I_q(n) = \frac{1}{n} \sum_{d \mid n} \mu\!\left(\frac{n}{d}\right) q^d$
Круговые (циклотомические) многочлены $\Phi_n(x)$: Из разложения $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$ мультипликативное обращение Мёбиуса дает: $\Phi_n(x) = \prod_{d \mid n} (x^d - 1)^{\mu(n/d)}$ Для $n = 12$ при $d \in \{1, 2, 3, 4, 6, 12\}$ и $\mu(12/d) \in \{0, +1, 0, -1, -1, +1\}$ сразу находим: $\Phi_{12}(x) = \frac{(x^{12} - 1)(x^2 - 1)}{(x^6 - 1)(x^4 - 1)} = \frac{x^6 + 1}{x^2 + 1} = x^4 - x^2 + 1$

5. Великое объединение Джан-Карло Роты (1964): посеты и алгебры инцидентности

Пусть $(P, \le)$ — локально конечное частично упорядоченное множество (посет) (каждый замкнутый интервал $[x, y] = \{z \in P \mid x \le z \le y\}$ конечен). В алгебре инцидентности $I(P)$ свертка по интервалам задается как:

\[(\alpha * \beta)(x, y) := \sum_{x \le z \le y} \alpha(x, z)\,\beta(z, y) \qquad (x \le y)\]

Единицей служит символ Кронекера $\delta(x, y) = [x = y]$. Дзета-функция посета $\zeta(x, y) = 1$ (при $x \le y$) имеет единственный обратный элемент $\mu = \zeta^{-1}$, определяемый рекуррентно: $\mu(x, x) = 1$ и $\mu(x, y) = -\sum_{x \le z < y} \mu(x, z)$ при $x < y$. Это дает обобщенную теорему обращения Мёбиуса на посетах:

\[g(y) = \sum_{x \le y} f(x) \quad \Longleftrightarrow \quad f(y) = \sum_{x \le y} g(x)\,\mu(x, y)\]

  flowchart TD
    R["Обобщенное обращение Мёбиуса по Роте (1964)<br/>μ = ζ⁻¹ в алгебре инцидентности I(P)<br/>g = f * ζ  ⇔  f = g * μ"]
    R --> P1["1. Линейная цепь (ℕ₀, ≤)<br/>0 < 1 < 2 < 3 < ..."]
    R --> P2["2. Булева решетка подмножеств (𝒫(S), ⊆)<br/>Включение A ⊆ B"]
    R --> P3["3. Решетка делимости (ℕ⁺, |)<br/>Делимость a | b"]
    R --> P4["4. Решетка разбиений множества (Π_n, ≤)<br/>Измельчение π ≤ σ"]
    P1 --> T1["μ(i, i) = 1, μ(i, i+1) = -1, иначе 0<br/>⇒ Основная теорема дискретного анализа<br/>f(n) = g(n) - g(n-1) (Δ = Σ⁻¹)"]
    P2 --> T2["μ(A, B) = (-1)^|B \ A|<br/>⇒ Принцип включений-исключений (PIE)<br/>и беспорядки D_n"]
    P3 --> T3["μ(a, b) = μ_классич(b/a)<br/>⇒ Классическое обращение Мёбиуса<br/>(Прямое произведение цепей степеней простых!)"]
    P4 --> T4["μ(0̂, 1̂) = (-1)^(n-1) (n-1)!<br/>⇒ Формула обращения моментов и кумулянтов<br/>в теории вероятностей"]

Посет $(P, \le)$	Отношение порядка $x \le y$	Функция Мёбиуса $\mu(x, y)$	Фундаментальная теорема из $f = g * \mu$
Линейная цепь $(\mathbb{N}_0, \le)$	Неравенство $i \le j$	$1$ ($j=i$), $-1$ ($j=i+1$), $0$ (иначе)	Дискретный анализ $f(n) = g(n) - g(n-1)$
Булева решетка $(\mathcal{P}(S), \subseteq)$	Включение $A \subseteq B$	$(-1)^{	B \setminus A
Решетка делимости $(\mathbb{N}^+, \mid)$	Делимость $a \mid b$	$\mu_{\text{классич}}(b/a) \in \{-1, 0, 1\}$	Классическое обращение Мёбиуса $f(n) = \sum_{d \mid n} \mu(n/d) g(d)$
Решетка разбиений $(\Pi_n, \le)$	Измельчение $\pi \le \sigma$	$\mu(\pi, \hat{1}) = (-1)^{	\pi

\(n\)	Разложение на простые	Свободно от квадратов?	Число простых \(k\)	Функция Мёбиуса \(\mu(n)\)	Функция Мертенса \(M(n) = \sum_{m=1}^n \mu(m)\)
\(1\)	\(1\) (пустое произведение)	Да	\(0\)	\(+1\)	\(+1\)
\(2\)	\(2\)	Да	\(1\)	\(-1\)	\(0\)
\(3\)	\(3\)	Да	\(1\)	\(-1\)	\(-1\)
\(4\)	\(2^2\)	Нет (\(2^2 \mid 4\))	—	\(0\)	\(-1\)
\(5\)	\(5\)	Да	\(1\)	\(-1\)	\(-2\)
\(6\)	\(2 \cdot 3\)	Да	\(2\)	\(+1\)	\(-1\)
\(7\)	\(7\)	Да	\(1\)	\(-1\)	\(-2\)
\(8\)	\(2^3\)	Нет (\(2^2 \mid 8\))	—	\(0\)	\(-2\)
\(9\)	\(3^2\)	Нет (\(3^2 \mid 9\))	—	\(0\)	\(-2\)
\(10\)	\(2 \cdot 5\)	Да	\(2\)	\(+1\)	\(-1\)
\(11\)	\(11\)	Да	\(1\)	\(-1\)	\(-2\)
\(12\)	\(2^2 \cdot 3\)	Нет (\(2^2 \mid 12\))	—	\(0\)	\(-2\)

Посет \((P, \le)\)	Отношение порядка \(x \le y\)	Функция Мёбиуса \(\mu(x, y)\)	Фундаментальная теорема из \(f = g * \mu\)
Линейная цепь \((\mathbb{N}_0, \le)\)	Неравенство \(i \le j\)	\(1\) (\(j=i\)), \(-1\) (\(j=i+1\)), \(0\) (иначе)	Дискретный анализ \(f(n) = g(n) - g(n-1)\)
Булева решетка \((\mathcal{P}(S), \subseteq)\)	Включение \(A \subseteq B\)	$(-1)^{	B \setminus A
Решетка делимости \((\mathbb{N}^+, \mid)\)	Делимость \(a \mid b\)	\(\mu_{\text{классич}}(b/a) \in \{-1, 0, 1\}\)	Классическое обращение Мёбиуса \(f(n) = \sum_{d \mid n} \mu(n/d) g(d)\)
Решетка разбиений \((\Pi_n, \le)\)	Измельчение \(\pi \le \sigma\)	$\mu(\pi, \hat{1}) = (-1)^{	\pi