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

В математике классическая формула обращения Мёбиуса — это соотношение между парами арифметических функций , каждая из которых определяется из другой суммой по делителям . Она была введена в теорию чисел в 1832 году Августом Фердинандом Мёбиусом . ^[1]

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

Классическая версия гласит, что если g и f — арифметические функции, удовлетворяющие

${\displaystyle g(n)=\sum _{d\mid n}f(d)\quad {\text{для каждого целого числа }}n\geq 1}$

затем

${\displaystyle f(n)=\sum _{d\mid n}\mu (d)g\left({\frac {n}{d}}\right)\quad {\text{для каждого целого числа }}n\geq 1}$

где μ — функция Мёбиуса , а суммы распространяются на все положительные делители d числа n (обозначенные в приведенных выше формулах как ). Фактически, исходная f ( n ) может быть определена по g ( n ) с помощью формулы обращения. Две последовательности называются преобразованиями Мёбиуса друг друга.${\displaystyle d\mid n}$

Формула также верна, если f и g являются функциями положительных целых чисел в некоторой абелевой группе (рассматриваемой как Z - модуль ).

На языке сверток Дирихле первую формулу можно записать как

${\displaystyle g={\mathit {1}}*f}$

где ∗ обозначает свертку Дирихле, а 1 — постоянная функция 1 ( n ) = 1. Вторая формула тогда записывается как

${\displaystyle f=\mu *g.}$

Множество конкретных примеров приведено в статье о мультипликативных функциях .

Теорема следует из того, что ∗ (коммутативна и) ассоциативна, а 1 ∗ μ = ε , где ε — тождественная функция для свертки Дирихле, принимающая значения ε (1) = 1 , ε ( n ) = 0 для всех n > 1. Таким образом,

${\displaystyle \mu *g=\mu *({\mathit {1}}*f)=(\mu *{\mathit {1}})*f=\varepsilon *f=f}$.

Заменив на , получим версию произведения формулы обращения Мёбиуса:${\displaystyle f,g}$${\displaystyle \ln f,\ln g}$

${\displaystyle g(n)=\prod _{d|n}f(d)\iff f(n)=\prod _{d|n}g\left({\frac {n}{d}}\right)^{\mu (d)},\forall n\geq 1.}$

Позволять

${\displaystyle a_{n}=\sum _{d\mid n}b_{d}}$

так что

${\displaystyle b_{n}=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)a_{d}}$

является его преобразованием. Преобразования связаны с помощью ряда: ряда Ламберта

${\displaystyle \sum _{n=1}^{\infty }a_{n}x^{n}=\sum _{n=1}^{\infty }b_{n}{\frac {x^{n}}{1-x^{n}}}}$

и ряд Дирихле :

${\displaystyle \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}=\zeta (s)\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s}}}}$

где ζ ( s ) — дзета-функция Римана .

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

Например, если начать с функции Эйлера φ и многократно применить процесс преобразования, то получится:

1. φ — функция тотиента
2. φ ∗ 1 = I , где I ( n ) = n — функция тождества
3. I ∗ 1 = σ ₁ = σ , функция делителя

Если начальной функцией является сама функция Мёбиуса, то список функций будет следующим:

1. μ , функция Мёбиуса
2. μ ∗ 1 = ε, где— единичная функция$${\displaystyle \varepsilon (n)={\begin{cases}1,&{\text{if }}n=1\\0,&{\text{if }}n>1\end{cases}}}$$
3. ε ∗ 1 = 1 , постоянная функция
4. 1 ∗ 1 = σ ₀ = d = τ , где d = τ — число делителей числа n (см. функцию делителей ).

Оба эти списка функций простираются бесконечно в обоих направлениях. Формула обращения Мёбиуса позволяет проходить эти списки в обратном направлении.

Например, последовательность, начинающаяся с φ, выглядит так:

${\displaystyle f_{n}={\begin{cases}\underbrace {\mu *\ldots *\mu } _{-n{\text{ factors}}}*\varphi &{\text{if }}n<0\\[8px]\varphi &{\text{if }}n=0\\[8px]\varphi *\underbrace {{\mathit {1}}*\ldots *{\mathit {1}}} _{n{\text{ factors}}}&{\text{if }}n>0\end{cases}}}$

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

Соответствующая формула обращения, более полезная в комбинаторике, выглядит следующим образом: предположим, что F ( x ) и G ( x ) — комплекснозначные функции, определенные на интервале [1, ∞) такие, что

${\displaystyle G(x)=\sum _{1\leq n\leq x}F\left({\frac {x}{n}}\right)\quad {\mbox{ для всех }}x\geq 1}$

затем

${\displaystyle F(x)=\sum _{1\leq n\leq x}\mu (n)G\left({\frac {x}{n}}\right)\quad {\mbox{ для всех }}x\geq 1.}$

Здесь суммы распространяются на все положительные целые числа n, которые меньше или равны x .

Это, в свою очередь, является частным случаем более общей формы. Если α ( n ) — арифметическая функция, имеющая обратную функцию Дирихле α ⁻¹ ( n ) , то если определить

${\displaystyle G(x)=\sum _{1\leq n\leq x}\alpha (n)F\left({\frac {x}{n}}\right)\quad {\mbox{ для всех }}x\geq 1}$

затем

${\displaystyle F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G\left({\frac {x}{n}}\right)\quad {\mbox{ для всех }}x\geq 1.}$

Предыдущая формула возникает в частном случае постоянной функции α ( n ) = 1 , обратная функция Дирихле которой равна α ⁻¹ ( n ) = μ ( n ) .

Конкретное применение первого из этих расширений возникает, если у нас есть (комплекснозначные) функции f ( n ) и g ( n ), определенные на положительных целых числах, причем

${\displaystyle g(n)=\sum _{1\leq m\leq n}f\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ для всех }}n\geq 1.}$

Определяя F ( x ) = f (⌊ x ⌋) и G ( x ) = g (⌊ x ⌋) , мы заключаем, что

${\displaystyle f(n)=\sum _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ для всех }}n\geq 1.}$

Простым примером использования этой формулы является подсчет количества сокращенных дробей 0 < ⁠а/б⁠ < 1 , где a и b взаимно просты и b ≤ n . Если мы допустим, что f ( n ) будет этим числом, то g ( n ) будет общим числом дробей 0 < ⁠а/б⁠ < 1 с b ≤ n , где a и b не обязательно взаимно просты. (Это потому, что каждая дробь ⁠а/б⁠ с gcd( a , b ) = d и b ≤ n можно свести к дроби ⁠а / д/б / д⁠ с ⁠б/г⁠ ≤ ⁠н/г⁠ , и наоборот.) Здесь легко определить g ( n ) = ⁠н ( н − 1)/2⁠ , но f ( n ) вычислить сложнее.

Другая формула обращения имеет вид (где мы предполагаем, что рассматриваемые ряды абсолютно сходятся):

${\displaystyle g(x)=\sum _{m=1}^{\infty }{\frac {f(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\mu (m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1.}$

Как и выше, это обобщается на случай, когда α ( n ) является арифметической функцией, имеющей обратную функцию Дирихле α ⁻¹ ( n ) :

${\displaystyle g(x)=\sum _{m=1}^{\infty }\alpha (m){\frac {f(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\alpha ^{-1}(m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1.}$

Например, существует хорошо известное доказательство, связывающее дзета-функцию Римана с простой дзета-функцией , которое использует основанную на ряде форму обращения Мёбиуса в предыдущем уравнении, когда . А именно, с помощью представления произведения Эйлера для ${\displaystyle s=1}$${\displaystyle \zeta (s)}$${\displaystyle \Re (s)>1}$

${\displaystyle \log \zeta (s)=-\sum _{p\mathrm {\ prime} }\log \left(1-{\frac {1}{p^{s}}}\right)=\sum _{k\geq 1}{\frac {P(ks)}{k}}\iff P(s)=\sum _{k\geq 1}{\frac {\mu (k)}{k}}\log \zeta (ks),\Re (s)>1.}$

Эти тождества для альтернативных форм обращения Мёбиуса можно найти в ^[2] . Более общая теория формул обращения Мёбиуса, частично цитируемая в следующем разделе об алгебрах инцидентности, построена Ротой в ^{[3] .}

Поскольку инверсия Мёбиуса применима к любой абелевой группе, не имеет значения, записана ли групповая операция как сложение или как умножение. Это приводит к следующему варианту записи формулы инверсии:

${\displaystyle {\mbox{if }}F(n)=\prod _{d|n}f(d),{\mbox{ then }}f(n)=\prod _{d|n}F\left({\frac {n}{d}}\right)^{\mu (d)}.}$

Первое обобщение можно доказать следующим образом. Мы используем соглашение Айверсона , что [условие] является индикаторной функцией условия, равной 1, если условие истинно, и 0, если ложно. Мы используем результат, что

${\displaystyle \sum _{d|n}\mu (d)=\varepsilon (n),}$

то есть, , где — единичная функция .${\displaystyle 1*\mu =\varepsilon }$${\displaystyle \varepsilon }$

У нас есть следующее:

${\displaystyle {\begin{aligned}\sum _{1\leq n\leq x}\mu (n)g\left({\frac {x}{n}}\right)&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}f\left({\frac {x}{mn}}\right)\\&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}\sum _{1\leq r\leq x}[r=mn]f\left({\frac {x}{r}}\right)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}\left[m={\frac {r}{n}}\right]\qquad {\text{rearranging the summation order}}\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{n|r}\mu (n)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\varepsilon (r)\\&=f(x)\qquad {\text{since }}\varepsilon (r)=0{\text{ except when }}r=1\end{aligned}}}$

Доказательство в более общем случае, когда α ( n ) заменяет 1, по сути идентично, как и второе обобщение.

Для частично упорядоченного множества P , множества, наделенного отношением частичного порядка , рекурсивно определим функцию Мёбиуса множества P следующим образом:${\displaystyle \leq }$${\displaystyle \mu }$

${\displaystyle \mu (s,s)=1{\text{ for }}s\in P,\qquad \mu (s,u)=-\sum _{s\leq t<u}\mu (s,t),\quad {\text{ for }}s<u{\text{ in }}P.}$

(Здесь предполагается, что суммы конечны.) Тогда для , где K — коммутативное кольцо, имеем ${\displaystyle f,g:P\to K}$

${\displaystyle g(t)=\sum _{s\leq t}f(s)\qquad {\text{ for all }}t\in P}$

если и только если

${\displaystyle f(t)=\sum _{s\leq t}g(s)\mu (s,t)\qquad {\text{ for all }}t\in P.}$

(См. «Перечислительную комбинаторику» Стэнли , том 1, раздел 3.7.) Классическая арифметическая функция Мёбиуса является частным случаем частично упорядоченного множества P положительных целых чисел, упорядоченных по делимости : то есть для положительных целых чисел s, t мы определяем частичный порядок как означающий, что s является делителем t . ${\displaystyle s\preccurlyeq t}$

Формулировка общей формулы обращения Мёбиуса [для частично упорядоченных множеств] была впервые независимо дана Вайснером (1935) и Филиппом Холлом (1936); оба автора были мотивированы проблемами теории групп. Ни один из авторов, по-видимому, не знал о комбинаторных последствиях своей работы и не развивал теорию функций Мёбиуса. В фундаментальной статье о функциях Мёбиуса Рота показал важность этой теории в комбинаторной математике и дал ее глубокое рассмотрение. Он отметил связь между такими темами, как включение-исключение, классическая теоретико-числовая инверсия Мёбиуса, проблемы раскраски и потоки в сетях. С тех пор, под сильным влиянием Роты, теория обращения Мёбиуса и связанные с ней темы стали активной областью комбинаторики. ^[4]

• последовательность Фэри
• Принцип включения-исключения

• Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Бакалаврские тексты по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, MR  0434929, Zbl  0335.10001
• Бендер, Эдвард А.; Голдман, Дж. Р. (1975), «О применении инверсии Мёбиуса в комбинаторном анализе», Amer. Math. Monthly , 82 (8): 789– 803, doi :10.2307/2319793, JSTOR  2319793
• Айрленд, К.; Розен, М. (2010), Классическое введение в современную теорию чисел , Graduate Texts in Mathematics (Книга 84) (2-е изд.), Springer-Verlag, ISBN 978-1-4419-3094-1
• Кунг, Джозеф ПС (2001) [1994], "Инверсия Мёбиуса", Энциклопедия математики , EMS Press
• Мёбиус, А.Ф. (1832), «Über eine besondere Art von Umkehrung der Reihen.», Journal für die reine und angewandte Mathematik , 9 : 105–123 .
• Стэнли, Ричард П. (1997), Перечислительная комбинаторика, т. 1, Cambridge University Press, ISBN 0-521-55309-1
• Стэнли, Ричард П. (1999), Перечислительная комбинаторика, т. 2, Cambridge University Press, ISBN 0-521-56069-1

• Вайсштейн, Эрик В. «Преобразование Мёбиуса». Математический мир .