функция Мёбиуса

Функция Мёбиуса $µ (n)$ — мультипликативная функция в теории чисел , введенная немецким математиком Августом Фердинандом Мёбиусом (также транслитерируемым Мёбиусом ) в 1832 году. ^[i]^[ii]^[2] Она повсеместно встречается в элементарной и аналитической теории чисел и большинстве часто появляется как часть своей тезки формулы обращения Мёбиуса . После работы Джан-Карло Роты в 1960-х годах в комбинаторику были введены обобщения функции Мёбиуса, которые также обозначаются $μ (x)$ .

Определение

Для любого положительного целого числа $n$ определите $µ (n)$ как сумму примитивных корней $n$ -й степени из единицы . Он имеет значения в ${-1, 0, 1}$ $в$ зависимости от разложения n на простые множители :

$µ (n) = +1$ , если $n$ — положительное целое число без квадратов с четным числом простых множителей.
$µ (n) = -1$ , если $n$ — положительное целое число без квадратов с нечетным числом простых множителей.
$µ (n) = - 0$ , если $n$ имеет квадрат простого множителя.

Альтернативно функцию Мёбиуса можно представить как

\mu (n)=\delta _ {\omega (n)\omega (n)}\lambda (n),

где $δ$ — дельта Кронекера , $λ (n)$ — функция Лиувилля , $ω (n)$ — количество различных простых делителей числа $n$ , а $Ω(n)$ — количество простых делителей числа $n$ , подсчитанных с кратностью.

Ее также можно определить как свертку Дирихле, обратную функции константы-1.

Ценности

Значения $μ (n)$ для первых 50 положительных чисел равны

Первые 50 значений функции показаны ниже:

Большие значения можно проверить:

Вольфрам Альфа
b-файл OEIS

Приложения

Математический ряд

Ряд Дирихле , порождающий функцию Мёбиуса , является (мультипликативной) обратной дзета-функцией Римана ; если $s$ — комплексное число с действительной частью больше 1, мы имеем

\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}.

Это можно видеть из произведения Эйлера.

{\frac {1}{\zeta (s)}}=\prod _{p{\text{ prime}}}{\left(1-{\frac {1}{p^{s}}}\right)}=\left(1-{\frac {1}{2^{s}}}\right)\left(1-{\frac {1}{3^{s}}}\right)\left(1-{\frac {1}{5^{s}}}\right)\cdots

Также:

$\sum \limits _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}={\frac {\zeta (s)}{\zeta (2s)}};$

$\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}=0;$

$\sum \limits _{n=1}^{\infty }{\frac {\mu (n)\ln n}{n}}=-1;$

$\sum \limits _{n=1}^{\infty }{\frac {\mu (n)\ln ^{2}n}{n}}=-2\gamma ,$ где – постоянная Эйлера . $\gamma$

Ряд Ламберта для функции Мёбиуса:

\sum _{n=1}^{\infty }{\frac {\mu (n)q^{n}}{1-q^{n}}}=q,

который сходится для $| д | < 1$ . Для простого числа $α \geq 2$ мы также имеем

\sum _{n=1}^{\infty }{\frac {\mu (\alpha n)q^{n}}{q^{n}-1}}=\sum _{n\geq 0}q^{\alpha ^{n}},|q|<1.

Алгебраическая теория чисел

Гаусс ^[1] доказал, что для простого числа $p$ сумма его примитивных корней конгруэнтна $µ (p - 1) (mod p)$ .

Если $F q$ обозначает конечное поле порядка $q$ (где $q$ обязательно является степенью простого числа), то число $N$ монических неприводимых многочленов степени $n$ над $F q$ определяется формулой: ^[3]

N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{\frac {n}{d}}.

Физика

Функция Мёбиуса также возникает в модели суперсимметрии примонного газа или свободного газа Римана . В этой теории фундаментальные частицы или «примоны» имеют энергию $log$ $p$ . При вторичном квантовании рассматриваются многочастичные возбуждения; они задаются как $log$ $n$ для любого натурального числа $n$ . Это следует из того, что факторизация натуральных чисел в простые числа единственна.

В свободном римановом газе может встречаться любое натуральное число, если считать примоны бозонами . Если их принять за фермионы , то принцип Паули исключает квадраты. Тогда оператор $(-1) F$ , который различает фермионы и бозоны, является не чем иным, как функцией Мёбиуса $µ (n)$ .

Свободный газ Римана имеет ряд других интересных связей с теорией чисел, включая тот факт, что статистическая сумма является дзета-функцией Римана . Эта идея лежит в основе попытки Алена Конна доказать гипотезу Римана . ^[4]

Характеристики

Функция Мёбиуса является мультипликативной (т. е. $µ (ab) = µ (a) µ (b)$ ), если $a$ и $b$ взаимно просты .

Доказательство : Учитывая два взаимно простых числа , мы проводим индукцию по . Если , то . В противном случае, так $m\geq n$ $mn$ $mn=1$ $\mu (mn)=1=\mu (m)\mu (n)$ $m>n\geq 1$
${\begin{aligned}0&=\sum _{d|mn}\mu (d)\\&=\mu (mn)+\sum _{d|mn;d<mn}\mu (d)\\&{\stackrel {\text{induction}}{=}}\mu (mn)-\mu (m)\mu (n)+\sum _{d|m;d'|n}\mu (d)\mu (d')\\&=\mu (mn)-\mu (m)\mu (n)+\sum _{d|m}\mu (d)\sum _{d'|n}\mu (d')\\&=\mu (mn)-\mu (m)\mu (n)+0\end{aligned}}$

Сумма функции Мёбиуса по всем положительным делителям $n$ (включая само $n$ и 1) равна нулю, за исключением случаев, когда $n = 1$ :

\sum _{d\mid n}\mu (d)={\begin{cases}1&{\text{if }}n=1,\\0&{\text{if }}n>1.\end{cases}}

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

Другие приложения $µ (n)$ в комбинаторике связаны с использованием теоремы перечисления Пойа в комбинаторных группах и комбинаторных перечислениях.

Существует формула ^[5] для вычисления функции Мёбиуса без непосредственного знания факторизации ее аргумента:

\mu (n)=\sum _{\stackrel {1\leq k\leq n}{\gcd(k,\,n)=1}}e^{2\pi i{\frac {k}{n}}},

т.е. $µ (n)$ является суммой примитивных корней $n$ -й степени из единицы . (Однако вычислительная сложность этого определения, по крайней мере, такая же, как и у определения произведения Эйлера.)

Другие тождества, которым удовлетворяет функция Мёбиуса, включают:

\sum _{k\leq n}\left\lfloor {\frac {n}{k}}\right\rfloor \mu (k)=1

\sum _{jk\leq n}\sin \left({\frac {\pi jk}{2}}\right)\mu (k)=1

Первый из них является классическим результатом, а второй был опубликован в 2020 году. ^[6]^[7] Аналогичные тождества справедливы и для функции Мертенса .

Доказательство формулы для Σ d | п μ ( d )

С использованием

\mu (n)=\sum _{\stackrel {1\leq k\leq n}{\gcd(k,\,n)=1}}e^{2\pi i{\frac {k}{n}}},

формула

\sum _{d\mid n}\mu (d)={\begin{cases}1&{\text{if }}n=1,\\0&{\text{if }}n>1\end{cases}}

можно рассматривать как следствие того факта, что сумма корней $n-$ й степени из единицы равна 0, поскольку каждый корень $n-$ й степени из единицы является примитивным корнем $d$ -й степени из единицы ровно для одного делителя $d$ числа $n$ .

Однако доказать это тождество можно и из первых принципов. Прежде всего отметим, что это тривиально верно, когда $n = 1$ . Предположим тогда, что $n > 1$ . Тогда существует биекция между факторами $d$ числа $n$ , для которых $µ (d) \neq 0$ , и подмножествами множества всех простых факторов числа $n$ . Утверждаемый результат следует из того, что каждое непустое конечное множество имеет равное число подмножеств нечетной и четной мощности.

Последний факт легко показать индукцией по мощности $| С |$ непустого конечного множества $S$ . Во-первых, если $| С | = 1$ , существует ровно одно подмножество нечетной мощности $S$ , а именно само $S$ , и ровно одно подмножество четной мощности, а именно $\emptyset$ . Далее, если $| С | > 1$ , затем разделите подмножества $S$ на два подкласса в зависимости от того, содержат они или нет некоторый фиксированный элемент $x$ в $S.$ Между этими двумя подклассами существует очевидная биекция, объединяющая в пары те подмножества, которые имеют одинаковое дополнение относительно подмножества ${x}$ . Кроме того, один из этих двух подклассов состоит из всех подмножеств множества $S \ { x }$ и, следовательно, по предположению индукции, имеет равное количество подмножеств нечетной и четной мощности. Эти подмножества, в свою очередь, взаимно соответствуют подмножествам $S , содержащим четную и нечетную мощность$ ${x}$ . Индуктивный шаг следует непосредственно из этих двух биекций.

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

Средний заказ

Среднее значение (в смысле средних порядков) функции Мёбиуса равно нулю. Это утверждение, по сути, эквивалентно теореме о простых числах . ^[8]

µ ( n ) разделы

$µ (n) = 0$ тогда и только тогда, когда $n$ делится на квадрат простого числа. Первые числа с этим свойством:

4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, .. (последовательность A013929 в OEIS ).

Если $n$ простое число, то $µ (n) = -1$ , но обратное неверно. Первое непростое $число n$ , для которого $µ (n) = -1,$ равно 30 = 2 × 3 × 5 . Первые такие числа с тремя различными простыми делителями ( сфенические числа ) — это

30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, ... (последовательность A007304 в OEIS ) .

и первые такие числа с 5 различными простыми делителями:

2310, 2730, 3570, 3990, 4290, 4830, 5610, 6006, 6090, 6270, 6510, 6630, 7410, 7590, 7770, 7854, 8610, 8778, 8970, 9030, 928 2, 9570, 9690, ... ( последовательность A046387 в OEIS ).

Функция Мертенса

В теории чисел другой арифметической функцией, тесно связанной с функцией Мёбиуса, является функция Мертенса , определяемая формулой

M(n)=\sum _{k=1}^{n}\mu (k)

для каждого натурального числа $n$ . Эта функция тесно связана с положениями нулей дзета-функции Римана . См. статью о гипотезе Мертенса для получения дополнительной информации о связи между $M (n)$ и гипотезой Римана .

Из формулы

\mu (n)=\sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}e^{2\pi i{\frac {k}{n}}},

отсюда следует, что функция Мертенса определяется выражением:

M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia},

где Fn _$—$ последовательность Фарея порядка $n$ .

Эта формула используется при доказательстве теоремы Франеля–Ландау . ^[9]

Обобщения

Алгебры инцидентности

В комбинаторике каждому локально конечному частично упорядоченному множеству (ЧУУ) ставится в соответствие алгебра инцидентности . Одним из выдающихся членов этой алгебры является «функция Мёбиуса» этого ЧУМ. Классическая функция Мёбиуса, рассматриваемая в этой статье, по существу равна функции Мёбиуса множества всех натуральных чисел, частично упорядоченных по делимости . См. статью об алгебрах инцидентности для точного определения и нескольких примеров этих общих функций Мёбиуса.

функция Поповича

Константин Попович ^[10] определил обобщенную функцию Мёбиуса $µ k = µ * ... * µ$ как $k$ -кратную свертку Дирихле функции Мёбиуса с самой собой. Таким образом, это снова мультипликативная функция с

\mu _{k}\left(p^{a}\right)=(-1)^{a}{\binom {k}{a}}\

где биномиальный коэффициент принимается равным нулю, если $a > k$ . Определение можно расширить до комплексного $k$ , прочитав бином как полином от $k$ . ^[11]

Реализации

Математика
Максима
geeksforgeeks C++, Python3, Java, C#, PHP, Javascript
Розеттский код
Мудрец

Смотрите также

Примечания

^ Харди и Райт, Примечания к гл. XVI: «... $μ (n)$ неявно встречается в работах Эйлера еще в 1748 году, но Мёбиус в 1832 году был первым, кто систематически исследовал его свойства». (Харди и Райт 1980, примечания к главе XVI)
^ В Disquisitiones Arithmeticae (1801) Карл Фридрих Гаусс показал, что сумма примитивных корней ( $mod p$ ) равна $µ (p - 1)$ (см. #Свойства и приложения), но он больше не использовал эту функцию. В частности, он не использовал инверсию Мёбиуса в «Исследованиях» . ^[1] Disquisitiones Arithmeticae переведена с латыни на английский и немецкий языки. Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

Цитаты

^ ab Gauss 1986, ст. 81.
^ Мёбиус 1832, стр. 105–123.
^ Джейкобсон 2009, §4.13.
^ Бост и Конн 1995, стр. 411–457.
^ Харди и Райт 1980, (16.6.4), с. 239.
^ Апостол 1976.
^ Клайн 2020.
^ Апостол 1976, §3.9.
^ Эдвардс 1974, гл. 12.2.
^ Поповичи 1963, стр. 493–499.
^ Шандор и Крстичи 2004, с. 107.

Источники

Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Тексты для студентов по математике, Нью-Йорк; Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, МР 0434929, Збл 0335.10001
Бост, Ж.-Б.; Конн, Ален (1995), «Алгебры Гекке, факторы типа III и фазовые переходы со спонтанным нарушением симметрии в теории чисел», Selecta Mathematica , New Series, 1 (3): 411–457, doi : 10.1007/BF01589495, S2CID 116418599
Делеглиз, Марк; Риват, Жоэль (1996), «Вычисление суммирования функции Мёбиуса», Experimental Mathematics , 5 (4): 291–295, doi : 10.1080/10586458.1996.10504594, S2CID 574146
Эдвардс, Гарольд (1974), Дзета-функция Римана , Минеола, Нью-Йорк: Dover Publications, ISBN 0-486-41740-9
Гаусс, Карл Фридрих (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) , Х. Мазер (немецкий переводчик) (2-е изд.), Нью-Йорк: Челси, ISBN 0-8284-0191-8
Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae , Артур А. Кларк (английский переводчик) (исправленное 2-е изд.), Нью-Йорк: Springer , ISBN 0-387-96254-9
Харди, штат Джорджия ; Райт, Э.М. (1980) [первое издание опубликовано в 1938 году], Введение в теорию чисел (5-е изд.), Оксфорд: Oxford University Press , ISBN 978-0-19-853171-5– через Интернет-архив
Клайн, Джеффри (2020), «Единичные суммы функций Мёбиуса и Мертенса» (PDF) , Журнал целочисленных последовательностей , 23 (8): 1–17
Джейкобсон, Натан (2009) [впервые опубликовано в 1985 г.], Основная алгебра I (2-е изд.), Dover Publications, ISBN 978-0-486-47189-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
Пегг, Эд-младший (2003), «Функция Мёбиуса (и числа без квадратов)», Математические игры Эда Пегга{{cite web}}: CS1 maint: multiple names: authors list (link)
Поповичи, Константин П. (1963), «Обобщение функции Мёбиуса», Studii şi Cercetări Matematice , 14 : 493–499, MR 0181602
Шандор, Йожеф; Крстичи, Борислав (2004), Справочник по теории чисел II , Дордрехт: Kluwer Academic, ISBN 1-4020-2546-7, Збл 1079.11001
Шандор, Йожеф; Митринович, Драгослав С.; Крстичи, Борислав, ред. (2006), Справочник по теории чисел I , Дордрехт: Springer-Verlag , стр. 187–226, ISBN 1-4020-4215-9, Збл 1151.11300

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

Вайсштейн, Эрик В. «Функция Мёбиуса». Математический мир .