В математике классическая формула обращения Мёбиуса - это отношение между парами арифметических функций , каждая из которых определяется другой суммой по делителям . Он был введен в теорию чисел в 1832 году Августом Фердинандом Мёбиусом . [1]
Большое обобщение этой формулы применяется к суммированию по произвольному локально конечному частично упорядоченному множеству , с классической формулой Мёбиуса, применяемой к множеству натуральных чисел, упорядоченных по делимости: см. Алгебру инцидентности .
Постановка формулы
Классическая версия утверждает, что если g и f - арифметические функции, удовлетворяющие
тогда
где μ - функция Мёбиуса, а суммы распространяются на все положительные делители d числа n (обозначенныев приведенных выше формулах). Фактически, исходная f ( n ) может быть определена с учетом g ( n ) с помощью формулы обращения. Эти две последовательности называются преобразованиями Мёбиуса друг друга.
Формула также верно , если е и г являются функциями из положительных целых чисел в некоторой абелевой группы ( если смотреть , как ℤ - модуль ).
На языке сверток Дирихле первую формулу можно записать как
где ∗ обозначает свертку Дирихле, а 1 - постоянная функция 1 ( n ) = 1 . Вторая формула записывается как
Многие конкретные примеры приведены в статье о мультипликативных функциях .
Теорема следует из того, что ∗ является (коммутативным и) ассоциативным и 1 ∗ μ = ε , где ε - тождественная функция для свертки Дирихле, принимающая значения ε (1) = 1 , ε ( n ) = 0 для всех n > 1. . Таким образом
- .
Существует версия продукта формулы обращения Мёбиуса на основе суммирования, указанная выше:
Серийные отношения
Позволять
чтобы
это его преобразование. Преобразования связаны между собой рядами: ряды Ламберта
и серии Дирихле :
где ζ ( s ) - дзета-функция Римана .
Повторяющиеся преобразования
Учитывая арифметическую функцию, можно сгенерировать бибесконечную последовательность других арифметических функций, многократно применяя первое суммирование.
Например, если начать с общей функции Эйлера φ и многократно применить процесс преобразования, получится:
- φ - тотентифицирующая функция
- φ ∗ 1 = I , где I ( n ) = n - тождественная функция
- I ∗ 1 = σ 1 = σ , функция делителя
Если исходной функцией является сама функция Мёбиуса, список функций будет следующим:
- μ функция Мёбиуса
- μ ∗ 1 = ε, где
- ε ∗ 1 = 1 , постоянная функция
- 1 ∗ 1 = σ 0 = d = τ , где d = τ - количество делителей числа n (см. Функцию делителей ).
Оба этих списка функций неограниченно расширяются в обоих направлениях. Формула обращения Мёбиуса позволяет обходить эти списки в обратном направлении.
Например, последовательность, начинающаяся с φ :
Сгенерированные последовательности, возможно, легче понять, если рассмотреть соответствующий ряд Дирихле : каждое повторное применение преобразования соответствует умножению на дзета-функцию Римана .
Обобщения
Связанная формула обращения более полезным в комбинаторике выглядит следующим образом : предположим , F ( х ) и G ( х ) являются сложные -значными функции , определенные на интервале [1, ∞) такое , что
тогда
Здесь суммы распространяются на все положительные целые числа n, которые меньше или равны x .
Это, в свою очередь, частный случай более общего вида. Если α ( n ) - арифметическая функция, обладающая обратным к Дирихле α −1 ( n ) , то если определить
тогда
Предыдущая формула возникает в частном случае постоянной функции α ( n ) = 1 , обратная к Дирихле которой равна α −1 ( n ) = μ ( n ) .
Частное применение первого из этих расширений возникает, если у нас есть (комплексные) функции f ( n ) и g ( n ), определенные на положительных целых числах, с
Определив F ( x ) = f (⌊ x ⌋) и G ( x ) = g (⌊ x ⌋) , мы выводим , что
Простым примером использования этой формулы является подсчет количества сокращенных дробей 0 <а/б<1 , где a и b взаимно просты и b ≤ n . Если мы позволим f ( n ) быть этим числом, то g ( n ) будет общим количеством дробей 0 < а/б<1 при b ≤ n , где a и b не обязательно взаимно просты. (Это потому, что каждая дробьа/бс НОД ( a , b ) = d и b ≤ n сводится к дробиа / д/б / д с участием б/d ≤ п/d, и наоборот.) Здесь несложно определить g ( n ) = п ( п - 1)/2, но вычислить f ( n ) сложнее.
Другая формула обращения (где мы предполагаем, что рассматриваемые ряды абсолютно сходятся):
Как и выше, это обобщается на случай, когда α ( n ) - арифметическая функция, обладающая обратным к Дирихле α −1 ( n ) :
Например, существует хорошо известное доказательство, связывающее дзета-функцию Римана с простой дзета-функцией, в котором используется последовательная форма обращения Мёбиуса в предыдущем уравнении, когда. А именно, представлением произведения Эйлера для
Эти тождества для альтернативных форм обращения Мебиуса можно найти в [2] . Более общая теория формул обращения Мебиуса, частично цитируемая в следующем разделе, посвященном алгебрам инцидентности, построена Ротой в [3].
Мультипликативная запись
Поскольку инверсия Мёбиуса применима к любой абелевой группе, не имеет значения, записывается ли групповая операция как сложение или как умножение. Это приводит к следующему варианту обозначений формулы обращения:
Доказательства обобщений
Первое обобщение можно доказать следующим образом. Мы используем соглашение Айверсона о том, что [условие] является индикаторной функцией условия, равной 1, если условие истинно, и 0, если ложно. Воспользуемся результатом, что
то есть 1 ∗ μ = i .
У нас есть следующее:
Доказательство в более общем случае, когда α ( n ) заменяет 1, по существу идентично, как и второе обобщение.
На поселениях
Для чугуна P множество, наделенное отношением частичного порядка, определим функцию Мёбиуса из Р рекурсивно
(Здесь предполагается, что суммирования конечны.) Тогда для , где K - коммутативное кольцо, имеем
если и только если
(См. Перечислительную комбинаторику Стэнли , том 1, раздел 3.7.)
Вклады Вайснера, Холла и Роты
Утверждение общей формулы обращения Мебиуса [для частично упорядоченных множеств] было впервые независимо дано Вейснером (1935) и Филипом Холлом (1936); оба автора были мотивированы проблемами теории групп. Похоже, что ни один из авторов не осознавал комбинаторные последствия своей работы и не развивал теорию функций Мёбиуса. В фундаментальной статье о функциях Мёбиуса Рота показал важность этой теории в комбинаторной математике и дал ее глубокое рассмотрение. Он отметил связь между такими темами, как включение-исключение, классическая теоретико-числовая инверсия Мёбиуса, проблемы раскраски и потоки в сетях. С тех пор под сильным влиянием Рота теория инверсии Мёбиуса и связанные с ней темы стали активной областью комбинаторики. [4]
Смотрите также
Заметки
- Перейти ↑ Möbius 1832 , pp. 105-123
- ^ Справочник NIST по математическим функциям, раздел 27.5.
- ^ [Об основах комбинаторной теории, I. Теория функций Мёбиуса | https://link.springer.com/content/pdf/10.1007/BF00531932.pdf ]
- ^ Bender & Goldman 1975 , стр. 789-803
Рекомендации
- Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Тексты для студентов по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, Руководство по ремонту 0434929 , Zbl 0335.10001
- Бендер, Эдвард А .; Гольдман, Дж. Р. (1975), "О приложениях обращения Мебиуса в комбинаторном анализе" , Amer. Математика. В месяц , 82 (8): 789-803, DOI : 10,2307 / 2319793 , JSTOR 2319793
- Ирландия, K .; Розен, М. (2010), Классическое введение в современную теорию чисел , Тексты для выпускников по математике (Книга 84) (2-е изд.), Springer-Verlag, ISBN 978-1-4419-3094-1
- Кунг, Джозеф PS (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
Внешние ссылки
- Формула обращения Мебиуса в ProofWiki
- Вайсштейн, Эрик В. «Преобразование Мёбиуса» . MathWorld .