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

krassi_holmz

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

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

Пример 2: Можем да намираме генериращите функции и на редици, които са дадени рекурсивно:
Нека $F_n$ е n-тото число на Фибоначи, $F_0=0;F_1=1$ , ще намерим генериращата функция на редицата $F=\{F_i\}_0^{\infty}$ .
Записваме формалната сума:
$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)$
$G(F;x)=1+xG(F;x)+x^2G(F;x)$
$(1-x-x^2)G(F;x)=1$
$G(F;x)=\frac{1}{1-x-x^2}$
И така намерихме това, което търсим.

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

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

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

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

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

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

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

Реклама