Mobius Inversion (evirme) teoreminde indislerle oynama

Question

$$F(n)=\sum_{d\mid n} f(d) \;\;\; \text{ ancak ve ancak } \;\;\; f(n)=\sum_{d\mid n} \mu(d) F\left(\frac nd\right)$$ oldugu gibi $$F(n)=\sum_{d\mid n, \: d \text{ tek} }f(d) \;\;\; \text{ ancak ve ancak } \;\;\; f(n)=\sum_{d\mid n,\: d \text{ tek}} \mu(d) F\left(\frac nd\right)$$  olur mu, ya da $p=2$ asali yerine alelade bir $p$ asali icin $$F(n)=\sum_{d\mid n, \: p \not \; \mid d} f(d) \;\;\; \text{ ancak ve ancak } \;\;\; f(n)=\sum_{d\mid n,\: p \not \; \mid d} \mu(d) F\left(\frac nd\right)$$  olabilir mi, ya da alelade bir $e$ tamsayisi icin  $$F(n)=\sum_{d\mid n, \: e \not \; \mid d} f(d) \;\;\; \text{ ancak ve ancak } \;\;\; f(n)=\sum_{d\mid n,\: e \not \; \mid d} \mu(d) F\left(\frac nd\right)$$ olabilir mi? 

Bu indislerler ile ne derece oynayabiliriz?

Answer 1

Tamamen buradaki tum adimlara cevap vermesem de fazlasina cevap verecegim ve nasil gorebilecegimizi anlamis olacagiz. (En azindan ben boyle dusunuyorum).

Aritmetik olan bir  $f$ fonksiyonu $f(1)=1$ ve  $(n,m)=1$ oldugunda  $$f(nm)=f(n)f(m)$$ esitliklerini saglarsa bu fonksiyona carpimsal diyecegiz.

$\nu(n)$ aritmetik fonksiyonu $n$ pozitif tam sayisinin farkli asal bolenlerinin sayisi olsun.  Mobius fonksiyonunu su sekilde tanimlayacagiz:  $$\mu(n)=\begin{cases}(-1)^{\nu(n)} & \text{ eger  $n$ karesiz ise,}\\ 0 &\text{ diger durumlarda}.\end{cases}$$

Onerme 1:  $$\sum_{d\mid n} =\begin{cases}1 & \text{ eger $n=1$,} \\0 & \text{ diger durumlarda}\end{cases}$$ esitligi saglanir.

Ispat: Sonuc $n=1$ icin dogal/bariz olarak dogru. $n\ge 2$ oldugunu kabul edelim ve  $n=p_1^{e_1}\cdots p_k^{e_k}$ olacak sekilde $n$ tam sayisini biricik asal carpanlarina ayiralim. $N=p_1\cdots p_k$ olarak tanimlayalim.  Eger $n$ sayisinin bir tam boleni olan bir $d$ tam sayisi eger $N$ sayisini tam bolmuyorsa bu durumda $d$ karesiz olmaz ve $\mu(d)=0$ olur. Dolayisiyla  $$\sum_{d\mid n} \mu(d)=\sum_{d\mid N}\mu(d)$$ esitligi saglanir.  $N$ tam sayisinin her boleni $\{p_1,\cdots,p_k\}$ kumesinin bir elemani ile (birebir ve oreten sekilde) eslesir. Dolayisiyla  $$\sum_{d\mid n} \mu(d)=\sum_{d\mid N}\mu(d)=\sum_{l=0}^k\binom{k}{l}(-1)^{l}=(1-1)^k=0$$ esitligi saglanir.

Onerme 2: $f$ ve  $F$ aritmetik fonksiyonlar olsun. Bu durumda   $$f(n)=\sum_{d\mid n}F(d)$$ tum $n$ dogal sayilari icin saglanir ancak ve ancak  $$F(n)=\sum_{d\mid n} \mu(d)f(n/d)$$   tum $n$ dogal sayilari icin saglanir.

Ispat: Ilk olarak  $$\sum_{d\mid n} \mu(d)f(n/d)=\sum_{d\mid n} \mu(d)\sum_{e\mid (n/d )}F(e)=\sum_{e\mid n}F(e) \sum_{d|(n/e)}\mu(d)=F(n)$$ saglanir. Son esitlikte Onerme 1'in sonucunu kullandik. Ikinci olarak $$\sum_{d\mid n}F(d)=\sum_{d\mid n}\sum_{e\mid d} \mu(e)f(d/e)=\sum_{k \mid n} f(k)\sum_{e\mid (n/k)}\mu(e)=f(n)$$  saglanir. Son esitlikte yine Onerme 1'in sonucunu kullandik. 

Onerme 3: $$\sum_{d\mid n,p\not\:\mid d} \mu(d)=\begin{cases}1 & \text{eger $n=p^r$ esitligini saglayan bir  $r \ge 0$ var ise,} \\0 & \text{diger durumlarda}\end{cases}$$ esitligi saglanir.

Ispat:  Sonuc $n=p^r$ esitligini saglayan bir $r\ge 0$ tam sayisi oldugunda dogal/bariz olarak dogru. $n\ne p^r$ esitsizliginin her $r\ge 0$ icin saglandigini kabul edelim ve  $n=p_1^{e_1}\cdots p_k^{e_k}$ olacak sekilde $n$ tam sayisini biricik asal carpanlarina ayiralim. $N=p_1\cdots p_t$ olarak tanimlayalim, buradaki asal carpanlar $p$ tam asalinin disindaki $n$ tam sayisinin asal carpanlari.  Eger $n$ sayisinin $p$ asalina bolunmeyen bir tam boleni olan bir $d$ tam sayisi eger $N$ sayisini tam bolmuyorsa bu durumda $d$ karesiz olmaz ve $\mu(d)=0$ olur. Dolayisiyla  $$\sum_{d\mid n,p\not\:\mid d} \mu(d)=\sum_{d\mid N}\mu(d)$$ esitligi saglanir.  $N$ tam sayisinin her boleni $\{p_1,\cdots,p_t\}$ kumesinin bir elemani ile (birebir ve oreten sekilde) eslesir. Dolayisiyla  $$\sum_{d\mid n,p\not\:\mid d} \mu(d)=\sum_{d\mid N}\mu(d)=\sum_{l=0}^t\binom{t}{l}(-1)^{l}=(1-1)^t=0$$ esitligi saglanir.

Onerme 4: $f$ ve  $F$ aritmetik fonksiyonlar olsun. Bu durumda $$f(n)=\sum_{d\mid n, p\not \:\mid d }F(d)$$ tum $n$  dogal sayilari icin saglanir ancak ve ancak   $$F(n)=\sum_{d\mid n, p\not \:\mid d} \mu(d)f(n/d)$$  tum $n$  dogal sayilari icin saglanir.

Ispat: Ilk olarak  $$\sum_{d\mid n, p\not \:\mid d} \mu(d)f(n/d)=\sum_{d\mid n, p\not \:\mid d} \mu(d)\sum_{e\mid (n/d)p\not \:\mid e}F(e)=\sum_{e\mid n,p\not \:\mid e}F(e) \sum_{d|(n/e),p\not \:\mid d}\mu(d)=F(n)$$ saglanir. Son esitlikte Onerme 3 kullaniliyor. Ikinci olarak  $$\sum_{d\mid n,p\not \:\mid d}F(d)=\sum_{d\mid n,p\not \:\mid d}\sum_{e\mid d,p\not \:\mid e} \mu(e)f(d/e)=\sum_{k \mid n,p\not \:\mid k} f(k)\sum_{e\mid (n/k),p\not \:\mid e}\mu(e)=f(n)$$   saglanir. Son esitlikte tekrar Onerme 3 kullaniliyor. 

Onerme 5: $f$ ve  $F$ aritmetik fonksiyonlar olsun. Bu durumda $$f(n)=\sum_{d\mid n, p\not \:\mid d }F\left(\frac nd\right)$$ tum $n$  dogal sayilari icin saglanir ancak ve ancak  $$F(n)=\sum_{d\mid n, p\not \:\mid d} \mu(d)f(n/d)$$ tum $n$  dogal sayilari icin saglanir.

Ispat: $p^u \mid \mid n$ olsun.  $$\sum_{d\mid n, p\not \:\mid d} \mu(d)f(n/d)=\sum_{d\mid n, p\not \:\mid d} \mu(d)\sum_{e\mid (n/d)p\not \:\mid e}F\left( \frac{n}{de}\right)=\sum_{k\mid n,p^u\mid \mid k}F(k) \sum_{d|(n/k),p\not \:\mid d}\mu(d)=F(n)$$ saglanir.   saglanir. Son esitlikte Onerme 3 kullaniliyor. Ikinci olarak  $$\sum_{d\mid n,p\not \:\mid d}F\left(\frac nd\right)=\sum_{d\mid n,p\not \:\mid d}\sum_{e\mid d,p\not \:\mid e} \mu(e)f\left(\frac n{de}\right)=\sum_{k\mid n,p\mid\mid k} f(k)\sum_{e\mid (n/k),p\not \:\mid e}\mu(e)=f(n).$$  saglanir. Son esitlikte tekrardan Onerme 3 kullaniliyor.

Bonus Onerme:  $f$ ve  $F$ aritmetik fonksiyonlar olsun. Bu durumda $$f(n)=\sum_{d\mid n}F\left(\frac nd\right)$$ tum $n$  dogal sayilari icin saglanir ancak ve ancak  $$\sum_{d\mid n, p\mid d}F\left(\frac nd\right)=f(n/p)$$ tum $p$ asalina tam bolunebilen $n$  dogal sayilari icin saglanir.

Ispat: $$\sum_{d\mid n, p\mid d}F\left(\frac nd\right)=\sum_{k\mid (n/p)}F\left(\frac n{kp}\right)=\sum_{k\mid (n/p)}F\left(\frac {n/p}{k}\right)=f(n/p)$$ saglanir.

Comments

En uste verdigim tanimi da hic kullanmamis... Yine de tanim tanimdir. 

---

Çok güzeller :)