Урок мултипликативни функции 3 - генериращи функции

[krassi_holmz]

Урок мултипликативни функции 3 - генериращи функции
Препоръчва се запознаването с предишните два урока преди да прочетете това.

1. Обикновени генериращи функции (ordinary power series).
Нека [tex]A=\{a_i\}_0^{\infty}[/tex] e редица от цели (може да сa всякакви, но тук ще разглеждаме само цели) числа.
Обикновена генерираща функция на A се нарича формалната сума:
[tex]G(A;x)=\sum_{i=0}^{\infty} a_i x^i[/tex]
(означение по Wikipedia)
В някои случаи, когато [tex]f[/tex] е генериращата функция на [tex]A[/tex], ще пишем [tex]f\overset{\text{ops}}{\longleftrightarrow }A[/tex] (означение по generatingfunctionology)
Обикновените генериращи функции (ОГФ) ни дават мощен апарат за работа с редици.
Ще дам няколко примера, за да стане по-ясно:
Пример 1: Да намерим ОГФ на редицата A={1,1,1,1,...}. Като я вмъкнем във сумата, получаваме:
[tex]G(A;x)=\sum_{i=1}^{\infty}1.x^i=\frac{1}{1-x}[/tex]
Няма да се притесняваме при какви условия за х горното е вярно, защото горната сума е формална - няма да се интересуваме от замяната на х с някакво конкретно число.

Пример 2: Можем да намираме генериращите функции и на редици, които са дадени рекурсивно:
Нека [tex]F_n[/tex] е n-тото число на Фибоначи, [tex]F_0=0;F_1=1[/tex], ще намерим генериращата функция на редицата [tex]F=\{F_i\}_0^{\infty}[/tex].
Записваме формалната сума:
[tex]G(F;x)=1+1x+2x^2+3x^3+5x^4+...+F_ix^i+...=1+(0+1)x+(1+1)x^2+(1+2)x^3+...+(F_{i-2}+F_{i-1})x^i+...=1+x+x^2G(F;x)+xG(F;x)[/tex]
[tex]G(F;x)=1+xG(F;x)+x^2G(F;x)[/tex]
[tex](1-x-x^2)G(F;x)=1[/tex]
[tex]G(F;x)=\frac{1}{1-x-x^2}[/tex]
И така намерихме това, което търсим.

Няколко ОГФ се използват много често:
[tex]\left\{i^a\right\}_{i=0}^{\infty }\overset{\text{ops}}{\longleftrightarrow }\frac{1}{1-a x}[/tex]

Генериращите функции са толкова удобни, заради начина, по който сборът и произведението им променя съответните им редици.
Следват две очевидни правила (първото от което е по-очевидно от второто):
Нека [tex]A=\{a_i\}_{0}^{\infty};B=\{b_i\}_{0}^{\infty}.[/tex]
Правило 1: Ако [tex]C=\{a_i+b_i\}_{0}^{\infty}[/tex], то:
[tex]G(A,x)+G(B,x)=G(C,x)[/tex]
Правило 2: Ако [tex]C = A*B = \{\sum_{i=0}^n a_i b_{n-i}\}_{n=0}^{\infty}[/tex], то:
[tex]G(A;x)G(B;x)=G(C;x)[/tex]
Горната сума много прилича на конволюцията на Дирихле, нали?
Това е нормална конволюция. От сега нататък, за да не се бъркаме, когато става дума за Дирихлетова конволюция, ще я означавам с [tex]*_d[/tex].
Също както и Дирихлетовата, и нормалната конволюция притежава всички свойства, които се очаква да притежава:
Нека [tex]A=\{a_i\}_{0}^{\infty};B=\{b_i\}_{0}^{\infty};C=\{C_i\}_{0}^{\infty}.[/tex]
1. [tex]A*B=B*A[/tex]
2. [tex]A*(B*C)=(A*B)*C=A*B*C[/tex]
3. [tex]A*(B+C)=A*B+A*C[/tex]
Получава се поле спрямо редиците и операциите събиране и конволюция.
Ще се върнем към обикновените генериращи функции малко по-късно.

2. Дирихлетови генериращи функции (Dirichlet series) (ДГФ).
Нека е дадена редицата [tex]A=\{a_i\}_0^{\infty}.[/tex]
Дирихлетова генерираща функция на А се нарича формалната сума:
[tex]DG(A;x)=\sum_{i=1}^{\infty}\frac{a_i}{i^x}.[/tex]
Eдин от най-простите и известни примери за функция е дзета-функцията на Риман, която е ДГФ на редицата [tex]\{1,1,1,...,\}[/tex] (да, това е функцията от знаменита хипотеза на Риман):
[tex]\zeta(x) = \sum_{i=1}^{\infty} \frac{1}{i^x}=DG(\{1,1,1,...\},x)[/tex]
Сега е моментът да отидете на адрес http://en.wikipedia.org/wiki/Dirichlet_series и да поразгледате. По-точно хвърлете едно око на Examples(примери). До края на този пост ще можете да доказвате (по-точно да извеждате) повечето от тях.
Да започнем с двете фундаментални свойства на ДГФ, които ги свързват с теорията на числата и с мултипликативните функции...
Нека [tex]A=\{a_i\}_{0}^{\infty};B=\{b_i\}_{0}^{\infty}.[/tex]
Правило 1: Ако [tex]C=\{a_i+b_i\}_{0}^{\infty}[/tex], то:
[tex]G(A,x)+G(B,x)=G(C,x)[/tex]
Правило 2: Ако [tex]C = A*_dB = \{\sum_{i|n} a_i b_{\frac{n}{i}}\}_{n=0}^{\infty}[/tex], то:
[tex]G(A;x)G(B;x)=G(C;x)[/tex] (Доказателството оставяме за упражнение)
Второто правило е важното - Дирихлетовата конволюция на две редици има ДГФ, равна на произведението на ДГФ-ите на двете редици!
Сега да си припомним някои означения от първия урок:
[tex]I(1)=1; x \neq 1 \to I(x)=0; I = {1,0,0,0,0,...}[/tex]
[tex]U(x)=1; U=\{1,1,1,1,...\}[/tex]
[tex]\mu=\{\mu(i)\}_{i=1}^{\infty}[/tex]
[tex]D(x)=x; D=\{1,2,3,4,...\}[/tex]
[tex]\phi=\{\phi(i)\}_{i=1}^{\infty}[/tex]
Всичките функции-редици отгоре са мултипликативните, киото намерихме преди. Ще се опитаме да намерим техните ДГФ-и.
Преди също използвах нотацията [tex]f[p,i]:=f(p^i)[/tex]. Сега ще я променя мъничко:
[tex]f_p(i):=f(p^i)[/tex].
Ще видим връзката между ОГФ на [tex]f_p[/tex] и ДГФ на [tex]f[/tex].
В пердишния урок показахме, че операторът [tex]\mathbb{U}[/tex] променя мултипликативната функция f по следния начин:
[tex]\mathbb{U}f_p(i)=\sum_{j=0}^i f_p(j)[/tex]
Може би някои от вас забелязват, че горният резултат може да се напише чрез ОБИКНОВЕНА конволюция:
[tex](U*_df)_p(i) = \sum_{j=0}^i f_p(j) U_p(i-j)[/tex]
Не е трудно да се забележи, че това правило може да се обобщи за поризволни мултипликативни функции, което ни дава връзката между ОГФ и ДГФ:
[tex]\{f*_dg\}_p(i) = \{f_p*g_p\}(i)[/tex]
Сега, когато искаме да изследваме дадена мултипликативна функция f, вместо директно да намерим нейната ДГФ, първо намираме ОГФ на [tex]f_p[/tex]

Но как ни помага това?
Както вече споменах, дзета-функцията на Риман е ДГФ на {1,1,1,...}=D, т.е.
[tex]DG(D;x)=\zeta(x)[/tex]
Да намерим [tex]D_p(i)[/tex]. По дефиниция:
[tex]D_p(i)=D(p^i)=1 \to D_p = \{1,1,1,1,...\}[/tex]
Сега, от началото на урока: [tex]G(D_p,x) = \frac{1}{1-x}[/tex].
Така, можем да кажем, че на мултипликативната функция [tex]D(n)[/tex] съответсват Дирихлетова генерирящя функция [tex]\zeta(x)[/tex] и обикновена генерираща ф-я [tex]\frac{1}{1-x}[/tex].
Това формално ще изразяваме по следния начин:
[tex]D\longleftrightarrow \zeta (x)\leftrightarrow \frac{1}{1-x}[/tex]
Такива връзки ще установим за всички останали мултипликативни функции.
Да започнем с функцията на Мюбус. Ние вече видяхме, че тя е обратна на U спрямо дирихлетовата конволюция, значи ДГФ-то й трябва да е реципрочното на ДГФ-то на U:
[tex]\frac{1}{\zeta (x)}=\sum _{i=1}^{\infty } \frac{\mu(i)}{i^x}[/tex].
Но ние ще докажем това и по двуг начин - чрез ОГФ на [tex]\mu_p[/tex].
Първо да намерим [tex]\mu_p[/tex]:
[tex]\mu_p(i) = \mu(p^i)= \{1,-1,0,0,0...\}_i[/tex]
Това може да се представи по-удобно чрез Кронекерската делта функция:
[tex]x=0 \to \delta _x = 1; x\neq 0 \to \delta _x = 0[/tex]
И мюбусовата функция се представя във вида:
[tex]\mu_p(i) = \delta_i - \delta_{i-1}[/tex]
Сега намирането на ОГФ на [tex]\mu_p[/tex] е просто:
[tex]G(\mu_p;x) = 1-x.[/tex]
Но ние вече сметнахме, че [tex]G(U_p;x)=\frac{1}{1-x}[/tex], т.е.
[tex]G(\mu_p;x)G(U_p;x)=1[/tex]
[tex]\mu_p * U_p = I[/tex]
[tex]\mu *_d U = I[/tex]
[tex]DG(\mu;x)DG(U;x)=1[/tex]
[tex]DG(\mu;x)=\frac{1}{DG(U;x)}=\frac{1}{\zeta(x)}[/tex]
[tex]\frac{1}{\zeta(x)} = \sum_{i=1}^{\infty} \frac{\mu(i)}{i^x}[/tex], което и трябваше да намерим.
[tex]\mu \longleftrightarrow \frac{1}{\zeta (x)}\leftrightarrow 1-x[/tex]

Забравих да спомена, че ОГФ и ДГФ на единичния елемент I(n) са най-лесните:
[tex]I\longleftrightarrow 1\leftrightarrow 1[/tex]

Сега да намерим ДГФ на идентитета [tex]D[/tex].
1. Намираме [tex]D_p(i) = D(p^i) = p^i[/tex]
2. Намираме ОГФ на [tex]D_p[/tex]:
[tex]G(D_p;x) = p^0 x^0 + p^1 x^1 + p^2 x^2 +...+p^k x^k +... = \frac{1}{1-p x}[/tex].
А какво можем да кажем за ДГФ на D(n)? Да го разпишем:
[tex]DG(D;x)=\frac{1}{1^{-x}}+\frac{2}{2^{-x}}+...=\frac{1}{1^{-(x-1)}}+\frac{1}{2^{-(x-1)}}+...=\zeta(x-1)[/tex].
Това означава:
[tex]D\longleftrightarrow \zeta (x-1)\leftrightarrow \frac{1}{1-p x}.[/tex]
Сега да видим функцията на Ойлер:
[tex]\phi_p(i) = p^i-p^{i-1};\phi_p(0) := 1[/tex]
[tex]G(\phi_p;x) = 1 + \sum_{i=1}^{\infty}(p^i-p^{i-1})x^i = 1 + \frac{x(p-1)}{1-p x} = \frac{1-x}{1-p x}[/tex].
Тук започва да си личи мощността на нашия метод: трябва да разложим нашата ф-я по някакъв начин на функции, които вече са ни известни:
[tex]G(\phi_p;x)=\frac{1}{\frac{1}{1-x}}\frac{1}{1-px} \to DG(\phi;x) = \frac{1}{\zeta(x)}\zeta(x-1)=\frac{\zeta(x-1)}{\zeta(x)}[/tex], което може да се запише:
[tex]\phi \longleftrightarrow \frac{\zeta (x-1)}{\zeta (x)}\leftrightarrow \frac{1-x}{1-p x}[/tex],
или:
[tex]\frac{\zeta(x-1)}{\zeta(x)} = \sum_{i=1}^{\infty}\frac{\phi(i)}{i^x}[/tex], което е още един пример от Уикипедия.
Сега ще въведем още една мултипликативна ф-я:
[tex]\sigma_a(n)[/tex] e сумата на а-тите степени на всички делители на n:
[tex]\sigma_a(n) = \sum_{i|n} i^a[/tex].
В Уикипедията е даден пример с ДГФ на сигмата. Ще можем ли сами да си го изведем?
Разбира се! Само че тук има малка техническа трудност - ще трябва да разгледаме два подслучая:
1. а=0. Сега [tex]\sigma_0(n)[/tex] е броят на (положителните) делителите на n (заедно с 1 и n). Следваме предишните стъпки: Първо трябва да намерим [tex]{\sigma_0}_p(i)[/tex]
Имаме:
[tex]{\sigma_0}_p(i) = \sigma_0(p^i) = i+1.[/tex]
[tex]G({\sigma_0}_p;x) = 1+2x+3x^2+...+(i+1)x^i+...=\frac{1}{(1-x)^2}[/tex]
И сега, понеже знаем, че на [tex]\frac{1}{1-x}[/tex] съответства [tex]\zeta(x)[/tex], получаваме, че:
[tex]DG(\sigma_0;x) = \zeta^2(x)[/tex].
----
Сега, малко отклонение - да видим на коя редица е ДГФ функцията [tex]\zeta(x-a)[/tex].
Видяхме, че когато a=1, се получава идентитетът. И това ни дава следа как да постъпим в общия случай: Избираме си [tex]A(n)=n^a[/tex]. Тогава:
[tex]DG(A;x) = \sum_{i=1}^{\infty}\frac{i^a}{i^{-x}} = \sum_{i=1}^{\infty}\frac{1}{i^{(-x-a)}} = \zeta(x-a)[/tex].
Сега остава да намерим ОГФ на [tex]A_p[/tex]:
[tex]A_p(i)=A(p^i)=(p^i)^a=p^{ai}[/tex]
[tex]G(A_p;x)=\sum_{i=0}^{\infty}p^{ai} x^i = \frac{1}{1-p^a x}[/tex].
Или можем да запишем всичко получено за А със:
[tex]n^a\longleftrightarrow \zeta (x-a)\leftrightarrow \frac{1}{1-p^a x}[/tex].
----
Сега можем да продължим с [tex]\sigma_a(x)[/tex].
Имаме:
[tex]{\sigma_a}_p (i) = \sigma_a(p^i) = \sum_{j=0}^i p^{aj} = \frac{1-p^{a(i+1)}}{1-p^a}[/tex].
[tex]G({\sigma_a}_p;x)=\sum_{i=0}^{\infty} \frac{1-p^{a(i+1)}}{1-p^a} x^i =...=\frac{1}{(1-x)(1-p^a x)}.[/tex]
И така стигнахме до:
[tex]DG(\sigma_a;x) = \zeta(x)\zeta(x-a).[/tex]
[tex]\sigma _0\longleftrightarrow \zeta ^2(x)\leftrightarrow \frac{1}{(1-x)^2}[/tex]
a!=0:
[tex]\sigma _a\longleftrightarrow \zeta (x) \zeta (x-a)\leftrightarrow \frac{1}{(1-x) \left(1-p^a x\right)}[/tex]
[tex]\zeta(x)\zeta(x-a) = \sum_{i=1}^{\infty} \frac{\sigma_a(i)}{i^x}[/tex], което е поредния пример от Уикипедията.
Сега например, ако а=1, получаваме функцията [tex]\sigma_1(n)=d(n)[/tex] - сумата на делителите на n. Като ползваме горното, получаваме (тривиално) равенство:
[tex]d=U*_d D; D=d*_d \mu[/tex]
[tex]n=\sum_{i|n}d(i)\mu(\frac ni)[/tex]
И за накрая, ще докажем следващият след него:
[tex]\frac{\zeta(x)\zeta(x-a)\zeta(x-b)\zeta(x-a-b)}{\zeta(2x-a-b)} = \sum_{i=1}^{\infty}\frac{\sigma_a(i)\sigma_b(i)}{i^x}[/tex].
И това е като предишното, само че изисква повече сметки. За да не разглеждаме случаи, ще приемем а!=0, b!=0.
[tex]\{\sigma_a\sigma_b\}_p(i)=\sigma_a(p^i)\sigma_b(p^i)=\frac{1-p^{a(i+1)}}{1-p^a}\frac{1-p^{b(i+1)}}{1-p^b}[/tex]
[tex]G(\{\sigma_a\sigma_b\}_p;x) =\sum_{i=0}^{\infty}\frac{1-p^{a(i+1)}}{1-p^a}\frac{1-p^{b(i+1)}}{1-p^b}x^i [/tex]
Следват МНОГО МНОГО изчисления, и най-накрая се получава:
[tex]G(\{\sigma_a\sigma_b\}_p;x) = \frac{1-p^{a+b}x^2}{(1-x)(1-p^ax)(1-p^bx)(1-p^{a+b}x^2)} [/tex].
Оттук:
[tex]DG(\sigma_a\sigma_b;x) = \frac{\zeta(x)\zeta(x-a)\zeta(x-b)\zeta(x-a-b)}{\zeta(x^2-a-b)}[/tex];
[tex]\left\{\sigma _a \sigma _b\right\}\longleftrightarrow \frac{\zeta (x) \zeta (x-a) \zeta (x-b) \zeta (x-a-b)}{\zeta \left(x^2-a-b\right)}\leftrightarrow \frac{1-p^{a+b} x^2}{(1-x) \left(1-p^a x\right) \left(1-p^b x\right) \left(1-p^{a+b} x\right)}[/tex]
И оттук:
[tex]\frac{\zeta (x) \zeta (x-a) \zeta (x-b) \zeta (x-a-b)}{\zeta \left(x^2-a-b\right)} = \sum_{i=1}^{\infty}\frac{\sigma_a(i)\sigma_b(i)}{i^x}[/tex].

Ае. Толкова от мен засега. Тия функции може още много да се човъркат, ама някой друг път...

[Реклама]