Производящая функция Дирихле

Определение:

Производящая функция Дирихле (англ. Dirichlet generating functions) последовательности [math]\{a_n\}_{n=1}^{\infty}[/math] — это формальный ряд вида: [math]A(s)= \dfrac{a_1}{1^s} + \dfrac{a_2}{2^s} + \dfrac{a_3}{3^s} + \dots = \sum\limits_{n=1}^\infty \dfrac{a_n}{n^s}[/math],

Примечание

• Нумерация коэффициентов производящих функций Дирихле начинается с единицы, а не с нуля, как это было в случае обыкновенных производящих функций.
• Вместо переменной [math]x[/math] используется [math]s[/math]. Это изменение связано больше с традициями, чем с математикой.
• Принято писать [math] \dfrac{a_n}{n^s} [/math] вместо [math] {a_n}{n^{-s}} [/math]. Это считается более удобной формой.

Применение

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

Определение:

Мультипликативная функция (multiplicative function) — функция [math]f(m)[/math], такая что [math]f(m_1 m_2) = f(m_1)f(m_2)[/math] для любых чисел [math]m_1[/math] и [math]m_2[/math] [math]f(1)=1[/math].

Примеры

Самой известной среди производящих функций Дирихле является дзета-функция Римана.

Определение:

Дзета-функция Римана (англ. The Riemann zeta function) — производящая функция Дирихле, отвечающая последовательности [math] \{a_n\}_{n=1}^{\infty} [/math], состоящей из единиц: [math]\zeta (s)={\dfrac {1}{1^{s}}}+{\dfrac {1}{2^{s}}}+{\dfrac {1}{3^{s}}}+\ldots ,[/math]

Таблица содержит известные производящие функции. Первая из них — это дзета-функция Римана, состоящая из единиц. [math][\zeta(s)]^2[/math] является последовательностью количества делителей числа. [math]\mu(n)[/math] — последовательность Мёбиуса . [math]H(n)[/math] — последовательность факторизаций числа, [math]\phi(n)[/math] — функция Эйлера.

[math]f(s)[/math]	Последовательность	[math]{a_n}[/math]
[math]\zeta(s)[/math]	[math]1[/math]	[math]1, 1, 1, 1, 1, 1, 1, 1, \dots[/math]
[math]1/\zeta(s)[/math]	[math]\mu(n)[/math]	[math]1, -1, -1, 0, -1, 1, -1, 0, \dots[/math]
[math][\zeta(s)]^2[/math]	[math]d(n)[/math]	[math]1, 2, 2, 3, 2, 4, 2, 4, \dots[/math]
[math]\dfrac{\zeta(s-1)}{\zeta(s)}[/math]	[math]\phi(n)[/math]	[math]1, 1, 2, 2, 4, 2, 6, 4, \dots[/math]
[math]\dfrac{1}{[2-\zeta(s)]}[/math]	[math]H(n)[/math]	[math]1, 1, 1, 2, 1, 3, 1, 4, \dots[/math]

Операции

Умножение

Если [math]A(s)[/math] и [math]B(s)[/math] — производящие функции Дирихле двух последовательностей [math]\{a_n\}_{n=1}^\infty[/math] и [math]\{b_n\}_{n=1}^\infty[/math] соответственно, то [math]A(s)B(s) = \dfrac{a_1b_1}{1^s} + \dfrac{a_1b_2 + a_2b_1}{2^s} + \dfrac{a_1b_3 + a_3b_1}{3^s} + \dfrac{a_1b_4 + a_2b_2 + a_4b_1}{4^s} + \dots = \sum\limits_{n} \dfrac{\sum\limits_{kl=n} {a_kb_l}}{n^s}[/math], где внутренние суммирование ведется по всем разложением числа [math]n[/math] в произведение двух сомножителей. Таким образом, использование производящих функций Дирихле позволяет контролировать мультипликативную структуру натуральных чисел.

Сложение

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

Единица

Роль единицы при умножении производящих функций Дирихле играет функция [math]1 = 1 ^ {-s}[/math].

Обратимость

Любая производящая функция Дирихле [math]A(s)[/math] с ненулевым свободным членом, [math]a_1 \neq 0[/math], обратима: для нее существует функция [math]B(s)[/math], такая что [math]A(s)B(s) = 1[/math].

Действительно, по правилу перемножения функций имеем [math]A(s)B(s) = \dfrac{a_1b_1}{1^s} + \dfrac{a_1b_2 + a_2b_1}{2^s} + \dfrac{a_1b_3 + a_3b_1}{3^s} + \dfrac{a_1b_4 + a_2b_2 + a_4b_1}{4^s} + \dots = \sum\limits_{n} \dfrac{\sum\limits_{kl=n} {a_kb_l}}{n^s}[/math], что в нашем случае равно [math]1 = 1 ^ {-s}[/math]. Получаем, что [math]a_1b_1 = 1[/math], тогда [math]b_1 = \dfrac{1}{a_1}[/math]. Остальные слагаемые равны [math]0[/math]. Рассмотрим их. Известно, что коэффициент перед [math]\dfrac{1}{n^s}[/math] равен [math]\sum\limits_{kl=n} {a_kb_l} = {a_1b_n} + \sum\limits_{kl=n,k\neq 1} {a_kb_l}[/math]. Отсюда [math]{b_n} = -\dfrac{\sum\limits_{kl=n,k\neq 1} {a_kb_l}}{a_1}[/math].

Свойства производящих функций Дирихле

Теорема:

Функция Мёбиуса имеет вид: [math]M(s) = \dfrac{1}{\zeta(s)} = \sum_{k=1}^{\infty} \dfrac{\mu_n}{n^s}[/math], где [math]\mu_n = \begin{cases} (-1)^t_n \\ 0 \end{cases}[/math]

Доказательство:

[math]\triangleright[/math]

Для доказательства покажем, что перед каждой проверкой условия в цикле while [math] f [/math] является предпотоком. Перед началом цикла, после завершения операции [math] \mathrm{initializePreflow}[/math], [math] f [/math] является предпотоком. Внутри цикла выполняются лишь операции проталкивания и подъёма. Операция подъёма не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъёма не зависит, будет ли [math] f [/math] предпотоком. Операция [math] \mathrm{push}[/math][math](u, v)[/math] применяется, если [math] e(u) \gt 0 [/math], увеличивая поток через ребро [math] (u, v) [/math] на величину, не превышающую избыточный поток вершины [math] u [/math] и остаточную пропускную способность ребра [math] (u, v) [/math]. Следовательно, если перед выполнением операции проталкивания [math] f [/math] являлся предпотоком, то и после выполнения проталкивания [math] f [/math] останется предпотоком. После завершения алгоритма для каждой вершины [math] u \in V \setminus \{s, t\} [/math] справедливо, что [math] e(u) = 0 [/math], что следует непосредственно из леммы ([math]1[/math]), леммы ([math]2[/math]) и того, что перед выполнением операций проталкивания или подъёма [math] f [/math] является предпотоком. Но тогда [math] f [/math] удовлетворяет условию сохранения потока, то есть сам является потоком. Поскольку из леммы ([math]1[/math]) следует, что [math] h [/math] является функцией высоты и после завершения алгоритма, то по лемме ([math]3[/math]) в остаточной сети [math] G_f [/math] нет пути из [math] s [/math] в [math] t [/math]. Но тогда по теореме Форда-Фалкерсона [math] f [/math] — максимальный поток.

[math]\triangleleft[/math]

См. также

• Производящая функция

Источники информации

• С.К.Ландо, Леции о производящих функциях, 2007 год
• Dirichlet Generating Function
• Dirichlet generating functions