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

Поделись знанием:
Перейти к: навигация, поиск

В математике Свёртка Дирихле — это бинарная операция, определённая для арифметических функций, используемая в теории чисел. Она была изобретена и исследована немецким математиком Петером Густавом Леженом Дирихле.





Определение

Если f и g — две арифметические функции (то есть функции, отображающие множество натуральных чисел во множество комплексных чисел), то мы можем определить новую функцию <math>f*g</math>, называемую свёрткой Дирихле функций f и g как

<math>(f*g)(n) = \sum_{d\mid n} f(d)g\left(\frac{n}{d}\right) = \sum_{ab=n}f(a)g(b)</math>

где сумма берётся по всем натуральным делителям d числа n, или, что эквивалентно, по всем парам <math>(a, b)</math> натуральных чисел, произведение которых равно n.

Свойства

Множество арифметических функций по поточечному сложению (то есть функция <math>f+g</math> определяется соотношением <math>(f+g)(n)=f(n)+g(n)</math>) и свёртка Дирихле образуют коммутативное кольцо, или кольцо Дирихле. Единицей кольца будет функция <math>\epsilon</math>, определённая как <math>\epsilon(n)=1</math>, если <math>n=1</math> и <math>\epsilon(n)=0</math>, если <math>n>1</math>. Обратимыми элементами являются все функции f такие, что <math>f(1)\neq 0</math>.

В частности, свёртка Дирихле является[1] ассоциативной:

<math>(f*g)*h=f*(g*h),</math>

дистрибутивной по сложению

<math>f*(g+h)=f*g+f*h=(g+h)*f,</math>

коммутативной,

<math>f*g=g*f,</math>

и имеет нейтральный элемент,

<math>f*\epsilon=\epsilon*f=f.</math>

Для каждой функции f, для которой <math>f(1)\neq 0</math> существует функция g такая, что <math>f*g=\epsilon</math>, называемая обращением Дирихле функции f.

Свёртка Дирихле двух мультипликативных функций снова мультипликативна, и каждая мультипликативная функция имеет мультипликативное обращение Дирихле. Статья о мультипликативных функциях содержит некоторые сходные соотношения свёртки, важные для мультипликативных функций.

Если f — вполне мультипликативная функция, то <math>f(g*h)=(fg)*(fh)</math>, где умножение функций определяется как их поточечная композиция.[2] Свёртка двух вполне мультипликативных функций не всегда является вполне мультипликативной.

Примеры

В приведённых ниже формулах используются следующие обозначения

<math>\epsilon</math> — единица по умножению кольца.
1 — это постоянная функция, значения которой равны 1 для всех n. (То есть <math>1(n)=1</math>.) Запомните, что 1 — это не единица кольца.
<math>1_C</math>, где <math>C\subseteq\mathbb{Z}</math>, — индикаторная функция. (То есть <math>1_C(n)=1</math>, если <math>n\in C</math>, иначе равна нулю)
<math>\operatorname{Id}</math> — тождественная функция (то есть <math>\operatorname{Id}(n)=n</math>)
<math>\operatorname{Id}_k</math> — k-я степень тождественной функции. (То есть <math>\operatorname{Id}_k = n^k.</math>)
Прочие функции можно найти в статье арифметическая функция.
  • <math>1*\mu=\epsilon</math> (обращение Дирихле единичной функции равно функции Мёбиуса.) Отсюда следует, что
  • <math>\lambda * 1=1_S,</math> где <math>S=\{1;4;9;16;...\}</math> — множество квадратов
  • <math>\sigma_k=\operatorname{Id}_k*1,</math> где <math>\sigma_k(n) =\sum\limits_{d\mid n}d^k</math> — сумма k-х степеней делителей числа
  • <math>\operatorname{Id}=\sigma*\mu</math>
  • <math>1=\tau*\mu</math>
  • <math>\tau^3*1=(\tau*1)^2</math>
  • <math>J_k*1=\operatorname{Id}</math>
  • <math>(\operatorname{Id}_{s}J_r)*J=J_{s+r}</math>
  • <math>\sigma=\varphi*\tau.</math> Доказательство: выполним свёртку обеих частей с 1 в тождестве <math>\operatorname{Id}=\varphi*1.</math>

Обращение Дирихле

Если задана арифметическая функция f, то её обращение Дирихле <math>g=f^{-1}</math> может быть вычислена рекурсивно (точнее каждое значение <math>g(n)</math> выражается через <math>g(m)</math> для <math>m<n</math>) через определение обращения Дирихле.

Для <math>n=1</math> <math>g(1)=f^{-1}(1)</math> — определена при <math>f(1)\neq 0</math>

И в общем для всех <math>n>1</math>

<math>g(n)=\frac{-1}{f(1)} \sum_\stackrel{d\mid n} {d < n}f\left(\frac{n}{d}\right) g(d).</math>

<math>g(n)</math> определено, если <math>f(1)\neq 0</math>. Таким образом, функция f имеет обращение Дирихле тогда и только тогда, когда <math>f(1)\neq 0.</math>

Ряды Дирихле

Если f — арифметическая функция, то можно определить её ряд Дирихле, производящую функцию как

<math>\operatorname{DG}(f;s) = \sum\limits_{n=1}^{+\infty}\frac{f(n)}{n^s}</math>

для всех таких комплексных аргументов s, для которых ряд сходится. Произведение рядов Дирихле связано с её свёрткой Дирихле следующим образом:

<math>\operatorname{DG}(f;s) \operatorname{DG}(g;s) = \operatorname{DG}(f*g;s)</math>

для всех s, для которых оба ряда слева сходятся, причём хотя бы один сходится абсолютно (заметим, что просто сходимость обоих рядов слева не влечёт сходимость ряда справа!). Это похоже на теорему сходимости, если понимать ряд Дирихле как преобразование Фурье.

См. также

Напишите отзыв о статье "Свёртка Дирихле"

Примечания

  1. Доказательства изложены в Chan, ch. 2
  2. Доказательство в статье en:Completely multiplicative function#Proof of pseudo-associative property.

Ссылки

  • Chan Heng Huat. Analytic Number Theory for Undergraduates. — World Scientific Publishing Company, 2009. — ISBN 981-4271-36-5.
  • Hugh L. Montgomery. Multiplicative number theory I. Classical theory. — Cambridge: Cambridge Univ. Press, 2007. — Vol. 97. — P. 38. — ISBN 0-521-84903-9.
  • A class of residue systems (mod r) and related arithmetical functions. I. A generalization of Möbius inversion, стр. 13—23.
  • Arithmetical functions associated with the unitary divisors of an integer, стр. 66—80.
  • The number of unitary divisors of an integer, стр. 879—880.
  • On an integers' infinitary divisors, стр. 395—411.
  • Arithmetic functions associated with infinitary divisors of an integer, стр. 373—383.
  • (2003) «The Möbius function: generalizations and extensions». Adv. Stud. Contemp. Math. (Kyungshang) 6: 77–128.
  • [algo.inria.fr/csolve/try.pdf Unitarism and Infinitarism](недоступная ссылка — история) (2004). [web.archive.org/20060901011841/algo.inria.fr/csolve/try.pdf Архивировано из первоисточника 1 сентября 2006].

Отрывок, характеризующий Свёртка Дирихле

– Продай матушку, – ударяя на последнем слоге, говорил другой солдат, обращаясь к немцу, который, опустив глаза, сердито и испуганно шел широким шагом.
– Эк убралась как! То то черти!
– Вот бы тебе к ним стоять, Федотов.
– Видали, брат!
– Куда вы? – спрашивал пехотный офицер, евший яблоко, тоже полуулыбаясь и глядя на красивую девушку.
Немец, закрыв глаза, показывал, что не понимает.
– Хочешь, возьми себе, – говорил офицер, подавая девушке яблоко. Девушка улыбнулась и взяла. Несвицкий, как и все, бывшие на мосту, не спускал глаз с женщин, пока они не проехали. Когда они проехали, опять шли такие же солдаты, с такими же разговорами, и, наконец, все остановились. Как это часто бывает, на выезде моста замялись лошади в ротной повозке, и вся толпа должна была ждать.
– И что становятся? Порядку то нет! – говорили солдаты. – Куда прешь? Чорт! Нет того, чтобы подождать. Хуже того будет, как он мост подожжет. Вишь, и офицера то приперли, – говорили с разных сторон остановившиеся толпы, оглядывая друг друга, и всё жались вперед к выходу.
Оглянувшись под мост на воды Энса, Несвицкий вдруг услышал еще новый для него звук, быстро приближающегося… чего то большого и чего то шлепнувшегося в воду.
– Ишь ты, куда фатает! – строго сказал близко стоявший солдат, оглядываясь на звук.
– Подбадривает, чтобы скорей проходили, – сказал другой неспокойно.
Толпа опять тронулась. Несвицкий понял, что это было ядро.
– Эй, казак, подавай лошадь! – сказал он. – Ну, вы! сторонись! посторонись! дорогу!
Он с большим усилием добрался до лошади. Не переставая кричать, он тронулся вперед. Солдаты пожались, чтобы дать ему дорогу, но снова опять нажали на него так, что отдавили ему ногу, и ближайшие не были виноваты, потому что их давили еще сильнее.
– Несвицкий! Несвицкий! Ты, г'ожа! – послышался в это время сзади хриплый голос.
Несвицкий оглянулся и увидал в пятнадцати шагах отделенного от него живою массой двигающейся пехоты красного, черного, лохматого, в фуражке на затылке и в молодецки накинутом на плече ментике Ваську Денисова.
– Вели ты им, чег'тям, дьяволам, дать дог'огу, – кричал. Денисов, видимо находясь в припадке горячности, блестя и поводя своими черными, как уголь, глазами в воспаленных белках и махая невынутою из ножен саблей, которую он держал такою же красною, как и лицо, голою маленькою рукой.
– Э! Вася! – отвечал радостно Несвицкий. – Да ты что?
– Эскадг'ону пг'ойти нельзя, – кричал Васька Денисов, злобно открывая белые зубы, шпоря своего красивого вороного, кровного Бедуина, который, мигая ушами от штыков, на которые он натыкался, фыркая, брызгая вокруг себя пеной с мундштука, звеня, бил копытами по доскам моста и, казалось, готов был перепрыгнуть через перила моста, ежели бы ему позволил седок. – Что это? как баг'аны! точь в точь баг'аны! Пг'очь… дай дог'огу!… Стой там! ты повозка, чог'т! Саблей изг'ублю! – кричал он, действительно вынимая наголо саблю и начиная махать ею.
Солдаты с испуганными лицами нажались друг на друга, и Денисов присоединился к Несвицкому.
– Что же ты не пьян нынче? – сказал Несвицкий Денисову, когда он подъехал к нему.
– И напиться то вг'емени не дадут! – отвечал Васька Денисов. – Целый день то туда, то сюда таскают полк. Дг'аться – так дг'аться. А то чог'т знает что такое!
– Каким ты щеголем нынче! – оглядывая его новый ментик и вальтрап, сказал Несвицкий.
Денисов улыбнулся, достал из ташки платок, распространявший запах духов, и сунул в нос Несвицкому.
– Нельзя, в дело иду! выбг'ился, зубы вычистил и надушился.
Осанистая фигура Несвицкого, сопровождаемая казаком, и решительность Денисова, махавшего саблей и отчаянно кричавшего, подействовали так, что они протискались на ту сторону моста и остановили пехоту. Несвицкий нашел у выезда полковника, которому ему надо было передать приказание, и, исполнив свое поручение, поехал назад.
Расчистив дорогу, Денисов остановился у входа на мост. Небрежно сдерживая рвавшегося к своим и бившего ногой жеребца, он смотрел на двигавшийся ему навстречу эскадрон.
По доскам моста раздались прозрачные звуки копыт, как будто скакало несколько лошадей, и эскадрон, с офицерами впереди по четыре человека в ряд, растянулся по мосту и стал выходить на ту сторону.
Остановленные пехотные солдаты, толпясь в растоптанной у моста грязи, с тем особенным недоброжелательным чувством отчужденности и насмешки, с каким встречаются обыкновенно различные роды войск, смотрели на чистых, щеголеватых гусар, стройно проходивших мимо их.
– Нарядные ребята! Только бы на Подновинское!
– Что от них проку! Только напоказ и водят! – говорил другой.
– Пехота, не пыли! – шутил гусар, под которым лошадь, заиграв, брызнула грязью в пехотинца.
– Прогонял бы тебя с ранцем перехода два, шнурки то бы повытерлись, – обтирая рукавом грязь с лица, говорил пехотинец; – а то не человек, а птица сидит!
– То то бы тебя, Зикин, на коня посадить, ловок бы ты был, – шутил ефрейтор над худым, скрюченным от тяжести ранца солдатиком.
– Дубинку промеж ног возьми, вот тебе и конь буде, – отозвался гусар.


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