Производящая функция Дирихле — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Применение)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 109: Строка 109:
 
<tex>f_n = \sum\limits_{k=0}^{t_n}(-1)^{k}\cdot\dbinom{t_n}{k}</tex>.
 
<tex>f_n = \sum\limits_{k=0}^{t_n}(-1)^{k}\cdot\dbinom{t_n}{k}</tex>.
 
Действительно, пусть разложение n на простые множители имеет вид <tex>n = p^{k_1}_1\cdot\ldots\cdot p^{k_{t_n}}_{t_n}</tex>. Тогда коэффициент при <tex>m^{−s}</tex> функции <tex>M(s)</tex> участвует в произведении с ненулевым коэффициентом в том и только в том случае, если <tex>m</tex>является произведением некоторого подмножества множества простых чисел <tex>n = p_1\ldots p_{t_n}</tex>. Число таких подмножеств из <tex>k</tex> элементов равно <tex>\dbinom{t_n}{k}</tex>, а знак соответствующего коэффициента при <tex>m^{−s}</tex> равен <tex>(-1)^{k}</tex>.
 
Действительно, пусть разложение n на простые множители имеет вид <tex>n = p^{k_1}_1\cdot\ldots\cdot p^{k_{t_n}}_{t_n}</tex>. Тогда коэффициент при <tex>m^{−s}</tex> функции <tex>M(s)</tex> участвует в произведении с ненулевым коэффициентом в том и только в том случае, если <tex>m</tex>является произведением некоторого подмножества множества простых чисел <tex>n = p_1\ldots p_{t_n}</tex>. Число таких подмножеств из <tex>k</tex> элементов равно <tex>\dbinom{t_n}{k}</tex>, а знак соответствующего коэффициента при <tex>m^{−s}</tex> равен <tex>(-1)^{k}</tex>.
 +
 +
}}
 +
{{Теорема
 +
|statement = Пусть <tex>f_n,g_n</tex> такие, что <tex>f_n = \sum\limits_{n\vdots k} g_k</tex>. Тогда <tex>g_n = \sum\limits_{n\vdots k} \mu_k\cdot f_k</tex>.
 +
|proof = Равенство <tex>f_n = \sum\limits_{n\vdots k} g_k</tex> означает, что <tex>F(s) = \zeta(s)\cdot G(s)</tex>, где <tex>F(s),G(s)</tex> {{---}} производящие функции Дирихле для последовательностей <tex>\{f_n\}_{n=1}^{\infty}</tex> и <tex>\{g_n\}_{n=1}^{\infty}</tex> соответственно. Домножим левую и правую части на <tex>M(s)</tex>. Получаем <tex>M(s)\cdot F(s) = M(s)\cdot\zeta(s)\cdot G(s)</tex>, а правая часть равна <tex>G(s)</tex> по предыдущей теореме.
  
 
}}
 
}}

Версия 23:23, 28 марта 2018

Определение:
Производящая функция Дирихле (англ. 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].


Утверждение:
Последовательность [math] \{a_n\}_{n=1}^{\infty} [/math] является мультипликативной тогда и только тогда, когда соответствующая ей производящая функция Дирихле имеет вид [math]A(s)= \prod\limits_p(1 + \sum\limits_{n=1}^\infty \dfrac{a_p}{p^ns})[/math], где [math]p[/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] является последовательностью количества делителей числа[1]. [math]\mu(n)[/math] — последовательность Мёбиуса [2]. [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\limits_{k=1}^{\infty} \dfrac{\mu_n}{n^s}[/math], где

[math]\mu_n = \begin{cases} (-1)^{t_n} \\ 0 \end{cases}[/math]
Доказательство:
[math]\triangleright[/math]

Перемножим функции [math]M(s)[/math] и [math]\zeta(s)[/math] и рассмотрим коэффициент при [math]n^{-s}[/math]. Назовём его [math]f_n[/math]. Тогда [math]f_n = \sum\limits_{k=0}^{t_n}(-1)^{k}\cdot\dbinom{t_n}{k}[/math].

Действительно, пусть разложение n на простые множители имеет вид [math]n = p^{k_1}_1\cdot\ldots\cdot p^{k_{t_n}}_{t_n}[/math]. Тогда коэффициент при [math]m^{−s}[/math] функции [math]M(s)[/math] участвует в произведении с ненулевым коэффициентом в том и только в том случае, если [math]m[/math]является произведением некоторого подмножества множества простых чисел [math]n = p_1\ldots p_{t_n}[/math]. Число таких подмножеств из [math]k[/math] элементов равно [math]\dbinom{t_n}{k}[/math], а знак соответствующего коэффициента при [math]m^{−s}[/math] равен [math](-1)^{k}[/math].
[math]\triangleleft[/math]
Теорема:
Пусть [math]f_n,g_n[/math] такие, что [math]f_n = \sum\limits_{n\vdots k} g_k[/math]. Тогда [math]g_n = \sum\limits_{n\vdots k} \mu_k\cdot f_k[/math].
Доказательство:
[math]\triangleright[/math]
Равенство [math]f_n = \sum\limits_{n\vdots k} g_k[/math] означает, что [math]F(s) = \zeta(s)\cdot G(s)[/math], где [math]F(s),G(s)[/math] — производящие функции Дирихле для последовательностей [math]\{f_n\}_{n=1}^{\infty}[/math] и [math]\{g_n\}_{n=1}^{\infty}[/math] соответственно. Домножим левую и правую части на [math]M(s)[/math]. Получаем [math]M(s)\cdot F(s) = M(s)\cdot\zeta(s)\cdot G(s)[/math], а правая часть равна [math]G(s)[/math] по предыдущей теореме.
[math]\triangleleft[/math]
Утверждение:
[math]\zeta(s) = \prod\limits_{p} \dfrac{1}{1 - p^{-s}}[/math], где [math]p[/math] принимает все простые значения.

См. также

Примечания

  1. ↑ Функция делителей
  2. ↑ Функция Мёбиуса

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Производящая_функция_Дирихле&oldid=64632»