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

Функция Мёбиуса <math>\mu(n)</math> — мультипликативная арифметическая функция, применяемая в теории чисел и комбинаторике, названа в честь немецкого математика Мёбиуса, который впервые рассмотрел её в 1831 году.

Определение

<math>\mu(n)</math> определена для всех натуральных чисел <math>n</math> и принимает значения <math>{-1,\;0,\;1}</math> в зависимости от характера разложения числа <math>n</math> на простые сомножители:

• <math>\mu(n)=1</math>, если <math>n</math> свободно от квадратов (то есть не делится на квадрат никакого простого числа) и разложение <math>n</math> на простые множители состоит из чётного числа сомножителей;
• <math>\mu(n)=-1</math>, если <math>n</math> свободно от квадратов и разложение <math>n</math> на простые множители состоит из нечётного числа сомножителей;
• <math>\mu(n)=0</math>, если <math>n</math> не свободно от квадратов.

По определению также полагают <math>\mu(1)=1</math>.

Свойства и приложения

• Функция Мёбиуса мультипликативна: для любых взаимно простых чисел <math>a</math> и <math>b</math> выполняется равенство <math>\mu(ab)=\mu(a)\mu(b)</math>.

• Сумма значений функции Мёбиуса по всем делителям целого числа <math>n</math>, не равного единице, равна нулю

<math>\sum_{d | n} \mu(d) = \begin{cases} 1,&n=1,\\ 0,&n>1.\end{cases}</math>

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

• <math>\sum\limits_{k=1}^n \mu(k)\left[\frac{n}{k}\right]=1.</math>

• <math>\sum\limits_{k=1}^{\infty} \frac{\mu(k n)}{k}=0,</math> где n - положительное целое число.

• <math>\sum\limits_{k=1}^{\infty} \frac{\mu(k)\ln k}{k}=-1.</math>

• Функция Мёбиуса тесно связана с дзета-функцией Римана. Так, через функцию Мёбиуса выражаются коэффициенты ряда Дирихле функции, мультипликативно обратной для дзета-функции Римана:

<math>\sum\limits_{n=1}^{\infty} \frac{\mu(n)}{n^{s}} = \frac{1}{\zeta(s)}</math>.

Ряд абсолютно сходится при <math>{\rm Re}\, s >1</math>, на прямой <math>{\rm Re}\, s = 1</math> - сходится условно, в области <math>1/2 < {\rm Re}\, s < 1</math> утверждение об условной сходимости ряда эквивалентно гипотезе Римана, а при <math>{\rm Re}\, s < 1/2</math> ряд заведомо не сходится, даже условно.

При <math>{\rm Re}\, s >1</math> справедлива также формула:

<math>\sum\limits_{n=1}^{\infty} \frac{|\mu(n)|}{n^{s}} = \frac{\zeta(s)}{\zeta(2s)}</math>

• <math>\sum\limits_{n=1}^{\infty} \frac{\mu(p n)}{n^{s}} = \frac{p^{s}}{(1-p^{s}) \zeta(s)}, </math> где p - простое число.

• Функция Мёбиуса связана с функцией Мертенса, также тесно связанной с задачей о нулях дзета-функции Римана

<math>M(n) = \sum_{k = 1}^n \mu(k).</math>

• Справедливы асимптотические соотношения:

<math>\frac{1}{x}\sum\limits_{n\leq x} \mu(n) = o(1)</math> при <math>x\rightarrow \infty</math>

<math>\frac{1}{x}\sum\limits_{n\leq x} |\mu(n)| = \frac{1}{\zeta(2)} + O(\frac{1}{\sqrt x}) </math>,

из которых следует, что существует асимптотическая плотность распределения значений функции Мёбиуса. Линейная плотность множества её нулей равна <math>1 - 1/\zeta(2) = 0,3920729</math>, а плотность множества единиц (или минус единиц) - <math>1/2\zeta(2) = 0,30396355</math>. На этом факте основаны теоретико-вероятностные подходы к изучению функции Мёбиуса.

Обращение Мёбиуса

Первая формула обращения Мёбиуса

Для арифметических функций <math>f</math> и <math>g</math>,

<math>g(n)=\sum_{d\,\mid\, n}f(d)</math>

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

<math>f(n)=\sum_{d\,\mid\, n}\mu(d)g(n/d)</math>.

Вторая формула обращения Мёбиуса

Для вещественнозначных функций <math>f(x)</math> и <math>g(x)</math>, определённых при <math>x\geqslant 1</math>,

<math> g(x) = \sum_{n\leqslant x} f\left(\frac{x}{n}\right)</math>

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

<math>f(x) = \sum_{n\leqslant x}\mu(n) g\left(\frac{x}{n}\right)</math>.

Здесь сумма <math>\sum_{n\leqslant x}</math> интерпретируется как <math>\sum_{n=1}^{\lfloor x\rfloor}</math>.

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

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

Пусть задано некоторое частично упорядоченное множество с отношением сравнения <math>\prec</math>. Будем считать, что <math>a \preccurlyeq b \iff a \prec b \lor a = b</math>.

Определение

Обобщённая функция Мёбиуса рекуррентно определяется соотношением.

<math>{\mu_A^*}(a,b) = \begin{cases}1, & a=b \\ -\sum \limits_{a \preccurlyeq z \prec b} {{\mu_A^*}(a,z)}, & a \prec b \\ 0, & b \prec a\end{cases}</math>

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

Пусть функции g и f принимают вещественные значения на множестве <math>A</math> и выполнено условие <math>g(x) = \sum \limits_{y \preccurlyeq x} {f(y)}</math>.

Тогда <math>f(x) = \sum \limits_{y \preccurlyeq x} {{\mu_A^*}(y,x) g(y)}</math>

Связь с классической функцией Мёбиуса

Если взять в качестве <math>A</math> множество натуральных чисел, приняв за отношение <math>a \prec b</math> отношение <math>a \mid b \land a \not = b</math>, то получим <math>{\mu_{\mathbb N}^*}(a,b) = \mu\left({\frac{b}{a}}\right)</math>, где <math>\mu</math> - классическая функция Мёбиуса.

Это, в частности, означает, что <math>\mu(n)={\mu_{\mathbb N}^*}(1,n)</math>, и далее определение классической функции Мёбиуса следует по индукции из определения обобщённой функции и тождества <math>\sum \limits_{k=1}^{n} {(-1)^k C_n^k} = 0</math>, так как суммирование по всем делителям числа, не делимого на полный квадрат, можно рассматривать как суммирование по булеану его простых множителей, перемножаемых в каждом элементе булеана.

См. также

• Свёртка Дирихле

Литература

• Виноградов И.М. Основы теории чисел. — 9-е изд. — М., 1981.
• Холл М. [eqworld.ipmnet.ru/ru/library/books/Holl1970ru.djvu Комбинаторика] = Combinatorial Theory. — М.: Мир, 1970. — 424 с.

Ссылки

• Лекторий МФТИ. Райгородский А.М. - [lectoriy.mipt.ru/lecture/AMRajgor-Comb-L050-1310090300131105/ Основы комбинаторики и теории чисел. Лекция №5], 2013.
• Лекторий МФТИ. Райгородский А.М. - [lectoriy.mipt.ru/lecture/AMRajgor-Comb-L060-1310160200131105/ Основы комбинаторики и теории чисел. Лекция №6], 2013.
• [ru.discrete-mathematics.org/fall2014/1/oktch/seminar_8_oktch_2014.pdf Обобщённая формула обращения Мёбиуса]

Отрывок, характеризующий Функция Мёбиуса

В это время дама компаньонка, жившая у Элен, вошла к ней доложить, что его высочество в зале и желает ее видеть.
– Non, dites lui que je ne veux pas le voir, que je suis furieuse contre lui, parce qu'il m'a manque parole. [Нет, скажите ему, что я не хочу его видеть, что я взбешена против него, потому что он мне не сдержал слова.]
– Comtesse a tout peche misericorde, [Графиня, милосердие всякому греху.] – сказал, входя, молодой белокурый человек с длинным лицом и носом.
Старая княгиня почтительно встала и присела. Вошедший молодой человек не обратил на нее внимания. Княгиня кивнула головой дочери и поплыла к двери.
«Нет, она права, – думала старая княгиня, все убеждения которой разрушились пред появлением его высочества. – Она права; но как это мы в нашу невозвратную молодость не знали этого? А это так было просто», – думала, садясь в карету, старая княгиня.

В начале августа дело Элен совершенно определилось, и она написала своему мужу (который ее очень любил, как она думала) письмо, в котором извещала его о своем намерении выйти замуж за NN и о том, что она вступила в единую истинную религию и что она просит его исполнить все те необходимые для развода формальности, о которых передаст ему податель сего письма.
«Sur ce je prie Dieu, mon ami, de vous avoir sous sa sainte et puissante garde. Votre amie Helene».
[«Затем молю бога, да будете вы, мой друг, под святым сильным его покровом. Друг ваш Елена»]
Это письмо было привезено в дом Пьера в то время, как он находился на Бородинском поле.


Во второй раз, уже в конце Бородинского сражения, сбежав с батареи Раевского, Пьер с толпами солдат направился по оврагу к Князькову, дошел до перевязочного пункта и, увидав кровь и услыхав крики и стоны, поспешно пошел дальше, замешавшись в толпы солдат.
Одно, чего желал теперь Пьер всеми силами своей души, было то, чтобы выйти поскорее из тех страшных впечатлений, в которых он жил этот день, вернуться к обычным условиям жизни и заснуть спокойно в комнате на своей постели. Только в обычных условиях жизни он чувствовал, что будет в состоянии понять самого себя и все то, что он видел и испытал. Но этих обычных условий жизни нигде не было.
Хотя ядра и пули не свистали здесь по дороге, по которой он шел, но со всех сторон было то же, что было там, на поле сражения. Те же были страдающие, измученные и иногда странно равнодушные лица, та же кровь, те же солдатские шинели, те же звуки стрельбы, хотя и отдаленной, но все еще наводящей ужас; кроме того, была духота и пыль.
Пройдя версты три по большой Можайской дороге, Пьер сел на краю ее.
Сумерки спустились на землю, и гул орудий затих. Пьер, облокотившись на руку, лег и лежал так долго, глядя на продвигавшиеся мимо него в темноте тени. Беспрестанно ему казалось, что с страшным свистом налетало на него ядро; он вздрагивал и приподнимался. Он не помнил, сколько времени он пробыл тут. В середине ночи трое солдат, притащив сучьев, поместились подле него и стали разводить огонь.
Солдаты, покосившись на Пьера, развели огонь, поставили на него котелок, накрошили в него сухарей и положили сала. Приятный запах съестного и жирного яства слился с запахом дыма. Пьер приподнялся и вздохнул. Солдаты (их было трое) ели, не обращая внимания на Пьера, и разговаривали между собой.
– Да ты из каких будешь? – вдруг обратился к Пьеру один из солдат, очевидно, под этим вопросом подразумевая то, что и думал Пьер, именно: ежели ты есть хочешь, мы дадим, только скажи, честный ли ты человек?
– Я? я?.. – сказал Пьер, чувствуя необходимость умалить как возможно свое общественное положение, чтобы быть ближе и понятнее для солдат. – Я по настоящему ополченный офицер, только моей дружины тут нет; я приезжал на сраженье и потерял своих.
– Вишь ты! – сказал один из солдат.
Другой солдат покачал головой.
– Что ж, поешь, коли хочешь, кавардачку! – сказал первый и подал Пьеру, облизав ее, деревянную ложку.
Пьер подсел к огню и стал есть кавардачок, то кушанье, которое было в котелке и которое ему казалось самым вкусным из всех кушаний, которые он когда либо ел. В то время как он жадно, нагнувшись над котелком, забирая большие ложки, пережевывал одну за другой и лицо его было видно в свете огня, солдаты молча смотрели на него.
– Тебе куды надо то? Ты скажи! – спросил опять один из них.
– Мне в Можайск.
– Ты, стало, барин?
– Да.
– А как звать?
– Петр Кириллович.
– Ну, Петр Кириллович, пойдем, мы тебя отведем. В совершенной темноте солдаты вместе с Пьером пошли к Можайску.
Уже петухи пели, когда они дошли до Можайска и стали подниматься на крутую городскую гору. Пьер шел вместе с солдатами, совершенно забыв, что его постоялый двор был внизу под горою и что он уже прошел его. Он бы не вспомнил этого (в таком он находился состоянии потерянности), ежели бы с ним не столкнулся на половине горы его берейтор, ходивший его отыскивать по городу и возвращавшийся назад к своему постоялому двору. Берейтор узнал Пьера по его шляпе, белевшей в темноте.
– Ваше сиятельство, – проговорил он, – а уж мы отчаялись. Что ж вы пешком? Куда же вы, пожалуйте!
– Ах да, – сказал Пьер.
Солдаты приостановились.
– Ну что, нашел своих? – сказал один из них.
– Ну, прощавай! Петр Кириллович, кажись? Прощавай, Петр Кириллович! – сказали другие голоса.
– Прощайте, – сказал Пьер и направился с своим берейтором к постоялому двору.
«Надо дать им!» – подумал Пьер, взявшись за карман. – «Нет, не надо», – сказал ему какой то голос.
В горницах постоялого двора не было места: все были заняты. Пьер прошел на двор и, укрывшись с головой, лег в свою коляску.


Едва Пьер прилег головой на подушку, как он почувствовал, что засыпает; но вдруг с ясностью почти действительности послышались бум, бум, бум выстрелов, послышались стоны, крики, шлепанье снарядов, запахло кровью и порохом, и чувство ужаса, страха смерти охватило его. Он испуганно открыл глаза и поднял голову из под шинели. Все было тихо на дворе. Только в воротах, разговаривая с дворником и шлепая по грязи, шел какой то денщик. Над головой Пьера, под темной изнанкой тесового навеса, встрепенулись голубки от движения, которое он сделал, приподнимаясь. По всему двору был разлит мирный, радостный для Пьера в эту минуту, крепкий запах постоялого двора, запах сена, навоза и дегтя. Между двумя черными навесами виднелось чистое звездное небо.