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

«Преобразование Мёбиуса» перенаправляется сюда. Не путать с преобразованием Мёбиуса .

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

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

Формулировка формулы

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

$g(n)=\sum _{d\mid n}f(d)\quad {\text{for every integer }}n\geq 1$

затем

$f(n)=\sum _{d\mid n}\mu (d)g\left({\frac {n}{d}}\right)\quad {\text{for every integer }}n\geq 1$

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

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

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

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

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

$f=\mu *g.$

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

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

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

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

$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.$

Серийные отношения

Позволять

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

так что

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

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

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

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

$\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 = ε , где $$\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 (см. функцию делителя ).

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

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

$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, ∞) , такие, что

$G(x)=\sum _{1\leq n\leq x}F\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}x\geq 1$

затем

$F(x)=\sum _{1\leq n\leq x}\mu (n)G\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}x\geq 1.$

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

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

$G(x)=\sum _{1\leq n\leq x}\alpha (n)F\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}x\geq 1$

затем

$F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}x\geq 1.$

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

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

$g(n)=\sum _{1\leq m\leq n}f\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ for all }}n\geq 1.$

Определив F ( x ) = f (⌊ x ⌋) и G ( x ) = g (⌊ x ⌋) , мы выводим, что

$f(n)=\sum _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ for all }}n\geq 1.$

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

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

$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 ) — арифметическая функция, обладающая обратной Дирихле α ⁻¹ ( н ) :

$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.$

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

$\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.$

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

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

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

${\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, если ложно. Мы используем результат, который

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

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

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

${\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 множество, наделенное отношением частичного порядка $\leq$, определим функцию Мёбиуса $\mu$ P помощью рекурсивно с

$\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.$

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

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

тогда и только тогда, когда

$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\preccurlyeq t$ это означает, что s является делителем t .

Вклад Вайснера, Холла и Роты

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

См. также

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

Ссылки

• Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Тексты для студентов по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN  978-0-387-90163-3 , МР   0434929 , Збл   0335.10001
• Бендер, Эдвард А.; Гольдман, младший (1975), «О применении обращения Мёбиуса в комбинаторном анализе» , Amer. Математика. Ежемесячно , 82 (8): 789–803, номер номера : 10.2307/2319793 , JSTOR   2319793.
• Ирландия, К.; Розен, М. (2010), Классическое введение в современную теорию чисел , Тексты для аспирантов по математике (книга 84) (2-е изд.), Springer-Verlag, ISBN  978-1-4419-3094-1
• Кунг, Джозеф PS (2001) [1994], «Обращение Мёбиуса» , Энциклопедия математики , EMS Press
• Мёбиус, А. Ф. (1832), «Об особом виде обращения ряда». , Журнал чистой и прикладной математики , 9 : 105–123.
• Стэнли, Ричард П. (1997), Перечислительная комбинаторика , том. 1, Издательство Кембриджского университета, ISBN  0-521-55309-1
• Стэнли, Ричард П. (1999), Перечислительная комбинаторика , том. 2, Издательство Кембриджского университета, ISBN  0-521-56069-1

Внешние ссылки

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