Ancora convoluzione

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Ancora convoluzione

Messaggio da kn » 10 apr 2009, 19:44

Due problemini facili, da lasciare ai giovani virgulti dell'oliForum:
1) Dimostrare che vale $ \displaystyle~\phi(n)=id_{\mathbb{N}}*\mu(n) $
2) Dimostrare che vale $ \displaystyle~u*\phi(n)=id_{\mathbb{N}}=n $

Non ho messo 'own' perché (molto) probabilmente sono identità conosciute...

Note:
(tutte le funzioni che consideriamo sono definite sui naturali positivi)
$ \displaystyle~\phi(x)= $numero di interi primi con n in $ \displaystyle~[1,n] $
$ \displaystyle~id_{\mathbb{N}}(x)=x,~~\forall x\in\mathbb{N} $ (la funzione identità)
$ \displaystyle~u(x)=1,~~\forall x\in\mathbb{N} $ (una funzione costante che dà sempre 1)
$ \displaystyle~\mu(x) $ (funzione di Moebius) vale 0 per x non square-free (se cioè nella fattorizzazione di n c'è almeno un fattore primo con esponente maggiore di uno) e $ \displaystyle(-1)^{\omega(x)} $ altrimenti ($ \displaystyle~\omega(x) $ è il numero di fattori primi distinti di x)
$ \displaystyle~* $ è l'operazione di convoluzione di due funzioni definita così: se f(x) e g(x) sono due funzioni, $ \displaystyle~f*g(n) := \sum_{d\mid n} f(d)~g\left(\frac{n}{d}\right) $

(Per alcune definizioni ho preso spunto da quelle di stefanos - tutti i diritti riservati)

Non uccidetemi se ho commesso qualche errore di notazione :oops:
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 11 apr 2009, 13:11

Uhm, esercizio bonus:

usare 1) per ricavare la formula per la $ \phi $ (è più interessante di quanto sembri la cosa....)

P.S. Buona Pasqua a tutti e soli quelli che scriveranno almeno un post in questo thread...
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.

stefanos
Messaggi: 229
Iscritto il: 02 giu 2008, 13:23
Località: Roma
Contatta:

Re: Ancora convoluzione

Messaggio da stefanos » 11 apr 2009, 14:02

kn ha scritto:(Per alcune definizioni ho preso spunto da quelle di stefanos - tutti i diritti riservati)
Che onore!

Btw, risolvo la bonus question xD

Lemma. Sia $ $f(n)$ $ una funzione moltiplicativa, $ $\mu(n)$ $ la solita funzione, come definita precedentemente; allora si ha la seguente relazione:
$ $\sum_{d|n} \mu(d)f(d) = \prod_{p|n}\left[1-f(p)\right]$ $
Dimostrazione. Siccome $ $\mu(n)$ $ e $ $f(n)$ $ sono funzioni moltiplicative, lo e` anche $ $\sum_{d|n} \mu(d)f(d)$ $: infatti, $ $\sum_{h|a} \mu(a)f(a) \sum_{k|b} \mu(b)f(b) = \sum_{h|a, k|b} \mu(h)\mu(k)f(h)f(k)$ $, ma poiche' $ $(a, b) = 1$ $, allora anche $ $(h, k) = 1$ $ (altrimenti ci sarebbero dei fattori in comune), quindi quella cosa li` e` uguale a $ $\sum_{h|a, k|b}\mu(hk)f(hk)$ $.
Ora, se e` moltiplicativa, mi basta studiarne il comportamento sulle potenze di primi, e poi moltiplico su tutti i divisori di $ $n$ $; considero il valore di quella espressione per $ $n=p^\alpha$ $: allora i suoi divisori sono del tipo $ $d=p^k$ $, e $ $\mu(p^k)$ $ vale $ $0$ $ se $ $k>1$ $, $ $-1$ $ se $ $k=1$ $ e $ $1$ $ se $ $k=0$ $, dunque l'espressione diventa $ $1\cdot f(1) - 1\cdot f(p) + 0.. = 1 - f(p)$ $ (ricordo che se $ $f(n)$ $ e` moltiplicativa, $ $f(1) = 1$ $, perche' $ $f(n) = f(1\cdot n) = f(1) f(n)$ $, oppure $ $f(n) \equiv 0$ $.. ma e` un caso poco interessante ;) ).
Questo significa che, chiamata $ $F(n) = \sum_{d|n} \mu(d)f(d)$ $, abbiamo che $ $F(n) = \prod_{p|n} F(p^{\mathrm{ord}_p(n)}) = \prod_{p|n} \left[1 - f(p)\right]$ $.

Be' a questo punto applico il lemma alla funzione $ $\phi(n) = \sum_{d|n}\mu(d)\frac{n}{d} = n \sum_{d|n} \mu(d)\cdot\frac{1}{d}$ $, dove la funzione $ $\frac{1}{n}$ $ e` chiaramente moltiplicativa (completamente, anche). Per il lemmetto abbiamo che $ $\phi(n) = n \prod_{d|n} \left(1-\frac{1}{p}\right)$ $, QED xD.

PS: Grazie, glad påsk anche a te!
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 11 apr 2009, 20:22

Perfetto. Io per ricavare la 1) ho usato il principio di inclusione-esclusione, da cui fattorizzando segue subito la formula 8)

Un'altra proprietà trovata in uno dei post (molto didattici) di stefanos (sotto le finte spoglie di Federiko, un utente fittizio che usano tutti quando vogliono nascondere la loro identità)
4) $ \displaystyle~\mu*u(n) = \mathcal{I}(n) $ (anche se questa forse andrebbe in Combinatoria :roll: )
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
Federiko
Messaggi: 226
Iscritto il: 15 mag 2008, 19:24
Località: Roma

Messaggio da Federiko » 11 apr 2009, 20:48

OFF TOPIC: NON SONO UN UTENTE FITTIZIO!!!! anzi ce ne sono molti più di quanti credete, che non posso rivelare, ma io sono vero!
CUCCIOLO

stefanos
Messaggi: 229
Iscritto il: 02 giu 2008, 13:23
Località: Roma
Contatta:

Messaggio da stefanos » 11 apr 2009, 20:58

Guarda, stavo per scriverlo io xD

Comunque, bonus question, chi vuole puo` dimostrare la 1 a partire dalla definizione di $ $\phi(n)$ $ e dalla 4. :D

Buon lavoro.
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 12 lug 2009, 00:27

kn ha scritto:Un'altra proprietà trovata in uno dei post (molto didattici) di stefanos (sotto le finte spoglie di Federiko, un utente fittizio che usano tutti quando vogliono nascondere la loro identità)
4) $ \displaystyle~\mu*u(n) = \mathcal{I}(n) $ (anche se questa forse andrebbe in Combinatoria :roll: )
Dimostrazione 1.
Una funzione aritmetica $ f(\cdot):\mathbb{N}_0 \to \mathbb{C} $ si definisce moltiplicativa se $ f(1)=1 $ e $ f(nm)=f(n)f(m) $ per ogni $ (n,m) \in \mathbb{N}_0^2 $ tali che $ (n,m)=1 $.
Lemma. Date due funzioni aritmetiche moltiplicative $ a(\cdot),b(\cdot) $, anche il prodotto di convoluzione $ a*b(\cdot) $ è moltiplicativo (vedi qui il Teorema 2.2).
Per $ n=1 $ abbiamo ovviamente che $ \displaystyle~\mu*u(1) = \mathcal{I}(1)=1 $. Se $ n \in \mathbb{N}\setminus \{0,1\} $ sia $ \displaystyle \prod_{i=1}^r{p_i^{\alpha_i}} $ la fattorizzazione canonica di $ n $, allora $ \displaystyle~\mu*u(n) = \prod_{i=1}^r{ \mu*u(p_i^{\alpha_i})} $. Adesso per ogni $ \alpha_i \in \mathbb{N}_0 $ abbiamo che $ \mu*u(p_i^{\alpha_i})=\sum_{j=0}^{\alpha_i}{\mu(p_i^j)}=1+\mu(p_i)=0 $. L'identità è dimostrata. []

Dimostrazione 2.
Se $ n=1 $ l'identità è verificata. Per cui supponiamo in seguito $ n \in \mathbb{N} \setminus \{0,1\} $. Mantendo le notazioni della dimostrazione precedente abbiamo che $ \displaystyle \mu*u(n)=\sum_{d \mid n}{\mu(d)} $.Ma, visto che, se per qualche $ (p,x) \in \mathbb{P} \times \mathbb{N} $ si verifica $ p^{x+2} \mid n $ vale $ \mu(p^{x+2})=0 $, allora $ \displaystyle \mu*u(n) $ prenderà come addendi non nulli tutti e i soli fattori liberi da quadrati propri di n. Ciò significa che $ \displaystyle \mu*u(\prod_{i=1}^r{p_i^{\alpha_i}})=\mu(1)+\sum_{i=1}^r{\mu(p_i)}+\sum_{1 \le i<j \le r}{\mu(p_ip_j)} \ldots $. Quindi sarà esattamente $ \displaystyle \sum_{i=0}^k{(-1)^i\binom{k}{i}} $, che, come noto, è lo sviluppo di $ (1-1)^k $. L'identità è di nuovo dimostrata. []
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Ancora convoluzione

Messaggio da jordan » 12 lug 2009, 00:43

kn ha scritto:2) Dimostrare che vale $ \displaystyle~u*\varphi(n)=id_{\mathbb{N}}=n $
Dimostrazione 1.
Per definizione $ \displaystyle x^n-1=\prod_{d \mid n}{\phi_d(x)} $, dove $ \phi_d(\cdot) $ rappresenta il $ d $-esimo polinomio ciclotomico. Ovviamente $ deg(\phi_d(x))=\varphi(d) $ per cui la tesi segue eguagliando i gradi delle due espressioni.[]

Dimostrazione 2.
Consideriamo le $ n $ frazioni $ \frac{a}{n} $ dove $ a \in \{1,2,\ldots,n\} $. Se riduciamo tutte queste frazioni ai minimi termini avremo che sono tutte della forma $ \frac{x}{d} $, dove $ (x,d)=1 $, $ d \mid n $ e $ x $ assume tutti e soli gli $ \varphi(d) $ valori coprimi con $ d $ e minori di esso. Come prima abbiamo $ \displaystyle n=\sum_{d \mid n}{\varphi(d)} $.[]

Dimostrazione 3.
Per quanto dimostrato al punto 1 (da stefanos, o dal principio di inclusione-esclusione di kn) vale $ u*\varphi(n)=u*\mu*id_{\mathbb{N}}(n)=\mathcal{I}(n)*id_{\mathbb{N}}(n)=n $ (il prodotto di convoluzione è ovviamente commutativo).[]
The only goal of science is the honor of the human spirit.

Rispondi