Twierdzenie Mobiusa o odwracaniu

patricia__88 · Post autor: **patricia__88** » 14 kwie 2012, o 10:47

Twierdzenie. Jeżeli \(\displaystyle{ f}\) jest dowolną funkcją arytmetyczną taką, że funkcja \(\displaystyle{ g}\) określona wzorem
\(\displaystyle{ g(m)=\sum_{d|m}f(d)}\) dla \(\displaystyle{ m\in\mathbb{N}}\)
jest funkcją multiplikatywną, to sama funkcja \(\displaystyle{ f}\) również jest multiplikatywna.

Dowód.
Dowód przeprowadzimy poprzez indukcję ze względu na \(\displaystyle{ m}\). Dla \(\displaystyle{ m=1}\) jest to oczywiste, ponieważ \(\displaystyle{ g(1)=\sum_{d|1}f(d)=1}\).
Załóżmy teraz, że \(\displaystyle{ m>1}\), a także załóżmy indukcyjnie, że \(\displaystyle{ f(m_1m_2)=f(m_1)f(m_2)}\), gdy \(\displaystyle{ (m_1,m_2)=1}\) i \(\displaystyle{ m_1m_2<m}\). Natomiast jeżeli \(\displaystyle{ m=m_1m_2}\) oraz \(\displaystyle{ (m_1,m_2)=1}\), to:
\(\displaystyle{ g(m_1m_2)=\sum_{d|m_1m_2}f(d)=\sum_{d_1|m_1}\sum_{d_2|m_2}f(d_1d_2)}\),
a także \(\displaystyle{ (d_1,d_2)=1}\), ponieważ wszystkie dzielniki liczby \(\displaystyle{ m_1}\) są względnie pierwsze ze wszystkimi dzielnikami liczby \(\displaystyle{ m_2}\).
Na mocy założenia indukcyjnego \(\displaystyle{ f(d_1d_2)=f(d_1)f(d_2)}\), poza przypadkiem, gdy \(\displaystyle{ d_1=m_1}\) i \(\displaystyle{ d_2=m_2}\). Mamy zatem
\(\displaystyle{ \left(\sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)\right)-f(m_1)f(m_2)+f(m_1m_2)=\\=g(m_1)g(m_2)-f(m_1)f(m_2)+f(m_1m_2)}\).
Jest to równe \(\displaystyle{ g(m_1m_2)=g(m_1)g(m_2)}\), zatem zachodzi także równość \(\displaystyle{ f(m_1m_2)=f(m_1)f(m_2)}\).
Odwrotnie, jeżeli funkcja \(\displaystyle{ f(m)}\) jest multiplikatywna, to odpowiadająca jej suma względem dzielników \(\displaystyle{ g(m)=\sum_{d|m}f(d)}\) musi być również multiplikatywna. Fakt ten zachodzi więc w obu kierunkach.

Nie do końca wszystko rozumiem w tym dowodzie, czy mógłby go ktoś rozpisać bardziej szczegółowo i bardziej indukcyjnie?

kammeleon18 · Post autor: **kammeleon18** » 29 kwie 2012, o 20:25

Wydaje mi się, że w kroku indukcyjnym dowodzimy prawdziwości tezy :"Funkcja f jest multiplikatywna dla 2-ch liczb, których iloczyn wynosi nie więcej niż \(\displaystyle{ m}\)" i indukujemy po \(\displaystyle{ m}\).

patricia__88 · Post autor: **patricia__88** » 16 cze 2012, o 12:53

SchmudeJanusz pisze:Wydaje mi się, że w kroku indukcyjnym dowodzimy prawdziwości tezy :"Funkcja f jest multiplikatywna dla 2-ch liczb, których iloczyn wynosi nie więcej niż \(\displaystyle{ m}\)" i indukujemy po \(\displaystyle{ m}\).

Nie bardzo rozumiem co masz myśli, możesz to pokazać?
I czy mógłby ktoś wytłumaczyć skąd to się wzięło:
\(\displaystyle{ g(m_1,m_2)=\left(\sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)\right)-f(m_1)f(m_2)+f(m_1m_2)=\\=g(m_1)g(m_2)-f(m_1)f(m_2)+f(m_1m_2)}\)
bo nie mogę tego zrozumieć.

kammeleon18 · Post autor: **kammeleon18** » 16 cze 2012, o 20:16

patricia__88 pisze: I czy mógłby ktoś wytłumaczyć skąd to się wzięło:
\(\displaystyle{ g(m_1,m_2)=\left(\sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)\right)-f(m_1)f(m_2)+f(m_1m_2)=\\=g(m_1)g(m_2)-f(m_1)f(m_2)+f(m_1m_2)}\)
bo nie mogę tego zrozumieć.

Sprowadza się to do tego że \(\displaystyle{ \sum_{d|{m_1}{m_2}}= \sum_{d|{m_1}}\sum_{d|{m_2}}}\)
Jeżeli m_1 i m_2 są względnie pierwsze to wszystkie dzielniki \(\displaystyle{ m_1m_2}\) są postaci \(\displaystyle{ d_1d_2}\), gdzie \(\displaystyle{ d_1|m_1}\) i \(\displaystyle{ d_2|m_2}\) oraz każda liczba postaci \(\displaystyle{ d_1d_2}\), gdzie \(\displaystyle{ d_1|m_1}\) i \(\displaystyle{ d_2|m_2}\) jest dzielnikiem \(\displaystyle{ m_1m_2}\).
Stąd \(\displaystyle{ \sum_{d|m}f(d)=\sum_{d|m}f(d_1d_2)=\sum_{d|m}f(d_1)f(d_2)=\sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)}\)

patricia__88 · Post autor: **patricia__88** » 17 cze 2012, o 11:36

SchmudeJanusz pisze: Sprowadza się to do tego że \(\displaystyle{ \sum_{d|{m_1}{m_2}}= \sum_{d|{m_1}}\sum_{d|{m_2}}}\)
Jeżeli m_1 i m_2 są względnie pierwsze to wszystkie dzielniki \(\displaystyle{ m_1m_2}\) są postaci \(\displaystyle{ d_1d_2}\), gdzie \(\displaystyle{ d_1|m_1}\) i \(\displaystyle{ d_2|m_2}\) oraz każda liczba postaci \(\displaystyle{ d_1d_2}\), gdzie \(\displaystyle{ d_1|m_1}\) i \(\displaystyle{ d_2|m_2}\) jest dzielnikiem \(\displaystyle{ m_1m_2}\).
Stąd \(\displaystyle{ \sum_{d|m}f(d)=\sum_{d|m}f(d_1d_2)=\sum_{d|m}f(d_1)f(d_2)=\sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)}\)

ok to rozumiem tylko nie wiem skąd się tutaj bierze jeszcze to:
\(\displaystyle{ -f(m_1)f(m_2)+f(m_1m_2)}\)

marcinz · Post autor: **marcinz** » 17 cze 2012, o 18:27

patricia__88 pisze: ok to rozumiem tylko nie wiem skąd się tutaj bierze jeszcze to:
\(\displaystyle{ -f(m_1)f(m_2)+f(m_1m_2)}\)

Bo w w tej sumie miałaś prawo zamienić \(\displaystyle{ f(d_1 d_2)=f(d_1)f(d_2)}\) dla \(\displaystyle{ d_1 d_2 < m}\) (to wynika z indukcji). Trzeba więc chwilowo zostawić w spokoju \(\displaystyle{ f(m_1 m_2)}\). W sumie \(\displaystyle{ \sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)}\) masz składnik \(\displaystyle{ f(m_1)f(m_2)}\), który musisz odjąć i dodać \(\displaystyle{ f(m_1 m_2)}\), żeby było równe wyjściowemu \(\displaystyle{ \sum_{d_1|m_1}\sum_{d_2|m_2}f(d_1d_2)}\).

patricia__88 · Post autor: **patricia__88** » 18 cze 2012, o 15:51

ehh nadal nie rozumiem, możesz to jakoś bardziej szczegółowo rozpisać?-- 19 cze 2012, o 15:41 --

marcinz pisze: W sumie \(\displaystyle{ \sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)}\) masz składnik \(\displaystyle{ f(m_1)f(m_2)}\), który musisz odjąć i dodać \(\displaystyle{ f(m_1 m_2)}\), żeby było równe wyjściowemu \(\displaystyle{ \sum_{d_1|m_1}\sum_{d_2|m_2}f(d_1d_2)}\).

Skąd wiadomo, że w sumie \(\displaystyle{ \sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)}\) znajduje się składnik \(\displaystyle{ f(m_1)f(m_2)}\) i dlaczego go odejmujemy, a następnie dodajemy \(\displaystyle{ f(m_1 m_2)}\)

eMaerthin · Post autor: **eMaerthin** » 19 cze 2012, o 19:17

patricia__88 pisze: Skąd wiadomo, że w sumie \(\displaystyle{ \sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)}\) znajduje się składnik \(\displaystyle{ f(m_1)f(m_2)}\)

Bo \(\displaystyle{ m_1|m_1}\) i \(\displaystyle{ m_2|m_2}\) Przyjmij \(\displaystyle{ d_1=m_1}\), \(\displaystyle{ d_2=m_2}\)

patricia__88 · Post autor: **patricia__88** » 19 cze 2012, o 23:06

ok dzieki

-- 20 cze 2012, o 16:41 --

ale dlaczego dodajemy jeszcze do tego \(\displaystyle{ f(m_1)f(m_2)}\)

-- 21 cze 2012, o 14:48 --

eMaerthin pisze: Bo \(\displaystyle{ m_1|m_1}\) i \(\displaystyle{ m_2|m_2}\) Przyjmij \(\displaystyle{ d_1=m_1}\), \(\displaystyle{ d_2=m_2}\)

No tak, ale gdy przyjmiemy \(\displaystyle{ d_1=m_1}\), \(\displaystyle{ d_2=m_2}\) to wtedy będziemy mieli \(\displaystyle{ f(1)f(1)}\), bo \(\displaystyle{ f\left(\frac{m_1}{m_1}\right)=f(1)}\)-- 21 cze 2012, o 15:19 --Znalazłam ten sam dowód na pewnej angielskiej stronce. Brzmi on następująco:

Theorem 1. \(\displaystyle{ f(n)}\) is multiplicative iff its sum-function \(\displaystyle{ S_f(n)}\) is multiplicative.
Proof: Let \(\displaystyle{ f(n)}\) be multiplicative, and let \(\displaystyle{ x,y\in\mathbb{N}}\) such that \(\displaystyle{ (x,y) = 1}\). Further, let \(\displaystyle{ x_1,x_2, \ldots, x_k}\) and \(\displaystyle{ y_1,y_2, \ldots , y_m}\) be all divisors of \(\displaystyle{ x}\) and \(\displaystyle{ y}\), respectively. Then \(\displaystyle{ (x_i,y_j) = 1}\), and \(\displaystyle{ \{x_iy_j\}_{i,j}}\) are all divisors of \(\displaystyle{ xy}\).
\(\displaystyle{ \Rightarrow S_f(x) \cdot S_f (y) = \sum_{i=1}^{k}f(x_i) \sum_{j=1}^{m}f(y_j)= \sum_{i,j}f(x_i)f(y_j)= \sum_{i,j}f(x_iy_j)=S_f(xy)}\)
Hence \(\displaystyle{ S_f(n)}\) is multiplicative.
Conversely, if \(\displaystyle{ S_f(n)}\) is multiplicative, then let \(\displaystyle{ n_1,n_2\in\mathbb{N}}\) such that \(\displaystyle{ (n_1,n_2)=1}\) and \(\displaystyle{ n = n_1n_2}\). We will prove by induction on \(\displaystyle{ n}\) that \(\displaystyle{ f(n_1n_2) = f(n_1)f(n_2)}\). The statement is
trivial for \(\displaystyle{ n=1: f(1) = S_f (1)(= 1 or 0).}\) Assume that it is true for all \(\displaystyle{ m_1m_2<n}\). Then for our \(\displaystyle{ n_1,n_2}\) we have:
\(\displaystyle{ S_f(n_1n_2) = \sum_{d_i|n_i}f(d_1d_2)= \sum_{d_i|n_i, \\ d_1d_2<n}f(d_1d_2)+f(n_1n_2)=\sum_{d_i|n_i, \\ d_1d_2<n}f(d_1)f(d_2)+f(n_1n_2)}\)
On the other hand,
\(\displaystyle{ S_f(n_1)S_f(n_2)= \sum_{d_1|n_1}f(d_1) \sum_{d_2|n_2}f(d_2)= \sum_{d_i|n_i, \\ d_1d_2<n}f(d_1)f(d_2)+f(n_1)f(n_2)}\)
Since \(\displaystyle{ S_f(n_1n_2)=S_f(n_1)S_f(n_2)}\), equating the above two expressions and canceling appropriately, we obtain \(\displaystyle{ f(n_1n_2)=f(n_1)f(n_2)}\). This completes the induction step, and shows that \(\displaystyle{ f(n)}\) is indeed multiplicative.

Jak ma się on do dowodu, który przedstawiłam na początku tego tematu, chodzi mi o to nieszczęsne ostatnie odejmowanie i dodawanie elementów.

kammeleon18 · Post autor: **kammeleon18** » 22 cze 2012, o 19:37

Te dwa dowody są praktycznie takie same.
W tym po polsku otrzymujemy równość \(\displaystyle{ g(m_1m_2)= g(m_1)g(m_2)-f(m_1)(f(m_2)+f(m_1m_2)}\) i z faktu \(\displaystyle{ g(m_1m_2)= g(m_1)g(m_2)}\) otrzymujemy \(\displaystyle{ f(m_1)(f(m_2)=f(m_1m_2)}\)
Z kolei w tym angielskim po prostu obliczamy ile to jest \(\displaystyle{ g(m_1m_2)}\) i przyrównujemy to do \(\displaystyle{ g(m_1)g(m_2)}\)
W tym angielskim w sumach w indeksach napisane jest że \(\displaystyle{ d_1d_2<n}\), tego brakuje w tym polskim i można się nie domyślić. Chodzi tu o \(\displaystyle{ \sum_{d_1d_2<n}^{} f(d_1d_2)}\) itp.
Podsumowując, dowody są w swej istocie takie same, tylko w tym polskim nie jest wyjaśnione dość dobrze czym są \(\displaystyle{ d_1}\) i \(\displaystyle{ d_2}\)

Czy to pomogło?:)

patricia__88 · Post autor: **patricia__88** » 22 cze 2012, o 19:47

A myślałam, że ten polski jest bardziej dokładny. Hmm czy mógłbyś uzupełnić dowód polski o brakujące rzeczy, które są natomiast w angielskim? I zamienić te dziwne \(\displaystyle{ g(m_1m_2)= g(m_1)g(m_2)-f(m_1)(f(m_2)+f(m_1m_2)}\) na wersję angielską? Nie do końca wszystko rozumiem po angielsku, a będę naprawdę wdzięczna mając wreszcie ten dowód porządnie napisany.-- 22 cze 2012, o 20:48 --Albo skoro uważasz, że angielski jest bardziej przejrzysty, to może lepiej go zastosować? Chociaz nie do końca wszystkie zwroty rozumiem.

kammeleon18 · Post autor: **kammeleon18** » 23 cze 2012, o 12:20

Twierdzenie:
Dla dowolnych względnie pierwszych liczb naturalnych \(\displaystyle{ k}\),\(\displaystyle{ l}\) \(\displaystyle{ f(k)f(l)=f(k \cdot l)}\)
Dowód:
Z multiplikatywności g
\(\displaystyle{ g(k)g(1)=g(1 \cdot k)=g(k)}\), stąd \(\displaystyle{ g(1)=1}\), a zatem \(\displaystyle{ f(1)=1}\).
Łatwo więc sprawdzić, że \(\displaystyle{ f(1)f(1)=f(1 \cdot 1)}\)
Załóżmy, że teza zachodzi dla wszystkich par liczb \(\displaystyle{ n_1}\), \(\displaystyle{ n_2}\) takich że \(\displaystyle{ n_1n_2<n}\). Udowodnimy, że zachodzi również dla par liczb których iloczyn wynosi \(\displaystyle{ n}\).
Niech \(\displaystyle{ n=m_1m_2}\), gdzie \(\displaystyle{ m_1}\)i \(\displaystyle{ m_2}\) są względnie pierwsze. W szczególności, jeżeli \(\displaystyle{ n}\) jest liczbą pierwszą to jedna z tych liczb jest równa \(\displaystyle{ 1}\).
\(\displaystyle{ g(m_1)g(m_2)= \sum_{d_1|m_1}^{} f(d_1)\sum_{d_2|m_2}^{} f(d_2)=}\)
\(\displaystyle{ = \sum_{d_1|m_1, d_2|m_2}^{} f(d_1)f(d_2)}\)
Z założenia indukcyjnego
\(\displaystyle{ f(d_1)f(d_2)=f(d_1d_2)}\) dla \(\displaystyle{ d_1d_2 <m_1m_2}\), a zatem
\(\displaystyle{ \sum_{d_1|m_1, d_2|m_2}^{} f(d_1)f(d_2)=}\)
\(\displaystyle{ [\sum_{d_1|m_1, d_2|m_2, d_1d_2 < m_1m_2}^{} f(d_1)f(d_2)]+ f(m_1)f(m_2)+(f(m_1m_2)-f(m_1m_2))=\sum_{d_1|m_1, d_2|m_2, }^{} f(d_1d_2)+f(m_1)f(m_2)-f(m_1m_2)=}\)
\(\displaystyle{ =g(m_1m_2)+f(m_1)f(m_2)-f(m_1m_2)}\)

a zatem \(\displaystyle{ g(m_1)g(m_2)=g(m_1m_2)+f(m_1)f(m_2)-f(m_1m_2)}\).
Funkcja g jest multiplikatywna, więc \(\displaystyle{ g(m_1)g(m_2)=g(m_1m_2)}\), stąd wnioskujemy, że \(\displaystyle{ f(m_1)f(m_2)-f(m_1m_2)=0}\), czyli po prostu
\(\displaystyle{ f(m_1)f(m_2)=f(m_1m_2)}\)
A zatem na mocy zasady indukcji matematycznej teza zachodzi dla dowolnej pary względnie pierwszych liczb naturalnych.

Słowo komentarza co do

\(\displaystyle{ \sum_{d_1|m_1, d_2|m_2}^{} f(d_1)f(d_2)=}\)
\(\displaystyle{ [\sum_{d_1|m_1, d_2|m_2, d_1d_2 < m_1m_2}^{} f(d_1)f(d_2)]+ f(m_1)f(m_2)+(f(m_1m_2)-f(m_1m_2))=\sum_{d_1|m_1, d_2|m_2, }^{} f(d_1d_2)+f(m_1)f(m_2)-f(m_1m_2)=}\)
\(\displaystyle{ =g(m_1m_2)+f(m_1)f(m_2)-f(m_1m_2)}\)

Tutaj z sumy\(\displaystyle{ \sum_{d_1|m_1, d_2|m_2}^{} f(d_1)f(d_2)}\) zabieramy ostatni składnik \(\displaystyle{ f(m_1)f(m_2)}\) , ponieważ nie można go (korzystając z zał. ind.) zamienić na \(\displaystyle{ f(m_1m_2)}\). Następnie zamieniamy te, które można tak zamienić (czyli te pary \(\displaystyle{ d_1}\) i \(\displaystyle{ d_2}\), że \(\displaystyle{ d_1d_2<m_1m_2=n}\)) i dodajemy do tego \(\displaystyle{ f(m_1m_2)}\) żeby cała suma ładnie zwinęła się do \(\displaystyle{ g(m_1m_2)}\). Skoro dodaliśmy tam \(\displaystyle{ f(m_1m_2)}\) to musimy to odjąć, żeby nie zmienić wartości całego wyrażenia, także to w tym miejscu powstaje nam to nieszczęsne \(\displaystyle{ f(m_1)f(m_2)-f(m_1m_2)}\).

Czy teraz już wszystko jasne?

patricia__88 · Post autor: **patricia__88** » 24 cze 2012, o 21:45

SchmudeJanusz pisze: Następnie zamieniamy te, które można tak zamienić (czyli te pary \(\displaystyle{ d_1}\) i \(\displaystyle{ d_2}\), że \(\displaystyle{ d_1d_2<m_1m_2=n}\)) i dodajemy do tego \(\displaystyle{ f(m_1m_2)}\) żeby cała suma ładnie zwinęła się do \(\displaystyle{ g(m_1m_2)}\). Skoro dodaliśmy tam \(\displaystyle{ f(m_1m_2)}\) to musimy to odjąć, żeby nie zmienić wartości całego wyrażenia, także to w tym miejscu powstaje nam to nieszczęsne \(\displaystyle{ f(m_1)f(m_2)-f(m_1m_2)}\).

Do tego momentu wszystko jasne,jednak pomyliłeś znaki, powinno być \(\displaystyle{ -f(m_1)f(m_2)+f(m_1m_2)}\)Mógłbyś to dodanie \(\displaystyle{ f(m_1m_2)}\) wytłumaczyć jakoś w inny sposób?:)

kammeleon18 · Post autor: **kammeleon18** » 24 cze 2012, o 22:13

Znaki się zgadzają :> \(\displaystyle{ f(m_1)f(m_2)}\) jest z plusem, bo zabrałem to z sumy. A \(\displaystyle{ f (m_1m_2)}\) jest z minusem bo dodałem to do tamtej sumy, to potem muszę odjąć to co tam się dzieje to generalnie dodawanie czegoś w jednym miejscu żeby odjąć w drugim.

patricia__88 · Post autor: **patricia__88** » 24 cze 2012, o 22:46

patricia__88 pisze:
\(\displaystyle{ \left(\sum_{d_1|m_1}f(d_1)\sum_{d_2|m_2}f(d_2)\right)-f(m_1)f(m_2)+f(m_1m_2)=\\=g(m_1)g(m_2)-f(m_1)f(m_2)+f(m_1m_2)}\).

Jednak ja miałam w książce odmienne znaki. Czy to pomyłka?