Математика · объяснение и практика

Обращение Мёбиуса: как восстановить слагаемые по суммам делителей

Определяем знаки функции Мёбиуса, доказываем взаимное уничтожение по делителям и восстанавливаем f(n) из F(n)=Σf(d); учитываем квадраты простых.

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

Главная мысль

Если для каждого натурального n известно F(n)=Σ_{d|n}f(d), то f(n)=Σ_{d|n}μ(d)F(n/d). Здесь μ(1)=1; μ(d)=0, когда d делится на квадрат простого, а для произведения r различных простых μ(d)=(−1)ʳ. Обращение восстанавливает исходные значения, а не просто оценивает их.

Накопление по делимости отличается от обычной суммы подряд

Величина F(6) складывает f(1), f(2), f(3), f(6), но не f(4) и f(5). Поэтому разность F(6)−F(5) обычно не выделяет f(6), как это было бы у последовательных частичных сумм. Порядок накопления задаётся делителями, и обратное действие должно учитывать тот же порядок.

Функция Мёбиуса кодирует различные простые множители со знаком. Например, μ(2)=−1, μ(6)=1, μ(30)=−1, но μ(12)=0 из-за квадрата двойки. Значение зависит не от общего числа множителей с повторениями: повторная степень не меняет знак, а обращает коэффициент в ноль. Для единицы действует отдельное значение, соответствующее пустому произведению.

Сумма μ(d) по всем положительным делителям n равна единице при n=1 и нулю при n>1. Ненулевые члены выбирают подмножества различных простых делителей n. Если их r, сумма знаков равна (1−1)ʳ. Именно это уничтожение лишних вкладов делает возможным обратное преобразование.

Почему формула действительно оставляет только f(n)

Подставим в Σ_{d|n}μ(d)F(n/d) определение F. Получится сумма μ(d)f(e) по парам натуральных d,e, для которых de делит n. Сгруппируем её по e: коэффициент при f(e) равен сумме μ(d) по делителям n/e. Все суммы конечны, поэтому перестановка порядка не требует рассуждений о сходимости.

Когда e<n, отношение n/e больше единицы, и коэффициент равен нулю. Когда e=n, отношение равно единице и коэффициент равен одному. Поэтому остаётся ровно f(n). Известные значения F на неделителях n не нужны: формула использует только соответствующие делители.

Пример

Известно F(1)=2, F(2)=5, F(3)=6, F(6)=17. Восстановите f(6) и проверьте результат.

Ненулевые коэффициенты для делителей 6 равны 1,−1,−1,1. Получаем f(6)=17−6−5+2=8. Сначала также восстанавливаются f(1)=2, f(2)=5−2=3, f(3)=6−2=4. Их сумма вместе с восьмёркой равна 17, как требует исходное накопление по четырём делителям шести.

Как читать нулевые коэффициенты при простых квадратах

Для n=12 ненулевые μ(d) получаются при d=1,2,3,6. Поэтому f(12)=F(12)−F(6)−F(4)+F(2). Значения F(3) и F(1) имеют нулевые коэффициенты, потому что соответствующие отношения 4 и 12 содержат квадрат простого. Их отсутствие не означает, что эти исходные значения всегда равны нулю.

Можно писать формулу и как Σ_{e|n}μ(n/e)F(e), поменяв обозначение делителя. Важно поменять одновременно аргумент коэффициента и аргумент F. Запись μ(e)F(e) без такого соответствия в общем случае является другим выражением и не выполняет обращения.

Результат требует согласованных данных F на делителях. Для произвольных заданных чисел формула всё равно определит некоторое f, но не гарантирует его положительность или целочисленность без условий на данные. Если F получено суммированием целочисленных f, восстановление, конечно, возвращает те же целые числа.

Рекурсивная проверка и простые степени

Без готовых коэффициентов можно последовательно вычислять f(n)=F(n)−Σf(d), где в сумме только собственные делители n. Они меньше n, поэтому их значения уже известны при движении по возрастанию. При n=1 сумма пуста, и f(1)=F(1). Формула Мёбиуса выполняет то же восстановление сразу через накопленные F, не требуя хранить все промежуточные f.

Для простого p остаётся f(p)=F(p)−F(1). Для любой положительной степени pᵏ получается f(pᵏ)=F(pᵏ)−F(pᵏ⁻¹), поскольку только μ(1) и μ(p) ненулевые среди делителей степени. Эта проверка объясняет, почему нельзя продолжать чередование по всем степеням: например, лишнее прибавление F(pᵏ⁻²) вновь внесло бы уже устранённые исходные слагаемые.

От чтения к действию

А теперь — вы

Какой коэффициент получает F(9) в формуле восстановления f(36)?

Частые вопросы

Почему μ простого квадрата не равна +1?

Ноль необходим для обращения по делимости: ненулевые коэффициенты соответствуют выбору различных простых без повторения.

Нужны ли значения F между соседними делителями?

Нет. Для восстановления f(n) достаточно значений F на положительных делителях n.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться