Ancora convoluzione

[kn]

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

[federiko97]

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...

[stefanos]

(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!

[kn]

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 )

[Federiko]

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

[stefanos]

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.

[jordan]

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 )

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. []

[jordan]

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).[]