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
Ancora convoluzione
Ancora convoluzione
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
- federiko97
- Messaggi: 44
- Iscritto il: 03 nov 2008, 20:36
- Località: Roma
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...
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.
Re: Ancora convoluzione
Che onore!kn ha scritto:(Per alcune definizioni ho preso spunto da quelle di stefanos - tutti i diritti riservati)
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]
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]
Perfetto. Io per ricavare la 1) ho usato il principio di inclusione-esclusione, da cui fattorizzando segue subito la formula
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 )
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 )
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
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.
Buon lavoro.
Comunque, bonus question, chi vuole puo` dimostrare la 1 a partire dalla definizione di $ $\phi(n)$ $ e dalla 4.
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]
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]
Dimostrazione 1.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 )
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.
Re: Ancora convoluzione
Dimostrazione 1.kn ha scritto:2) Dimostrare che vale $ \displaystyle~u*\varphi(n)=id_{\mathbb{N}}=n $
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.