[N] La formula di inversione di Mobius

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

F.V. ha proposto di dimostrare altrove la cosiddetta \"formula d\'inversione di Möbius\", in relazione a un problema di combinatorica assegnato da Catraga.
 
 Non me ne voglia alcuno se mi permetto d\'aprire un topic tutto nuovo per postare la soluzione del problema, ma per amore dell\'ordine, mi son detto che forse, in vista d\'un futuro riassetto del forum, sarebbe stato meglio procedere a questo modo...
 
 Lemma H.1: comunque fissato un r intero > 0, sia S := {1, 2, ..., r}. Allora, per ogni k = 1, 2, ..., r, il numero di possibili k-uple (i1, i2, ..., ik) di Sk tali che: i1 < i2 < ... < ik è pari al coefficiente binomiale Bin(r, k) di ordine r su k.
 
 Dim.: per ogni k = 1, 2, ..., r, sia detto n(k) il numero di possibili k-uple distinte (i1, i2, ..., ik) ottenute fissando k elementi differenti nell\'insieme S := {1, 2, ..., r} di modo tale che sia: i1 < i2 < ... < ik.
 
 Considerando che le possibili permutazioni della generica k-upla così costruita sono in numero pari a k!, e che fra le k! permutazioni così determinate n\'esiste una e una sola ordinata per componenti così come sopra precisato, se ne deduce che n(k) · k! eguaglia il numero di possibili disposizioni semplici degli r oggetti distinti di S in gruppi di k; ossia se ne conclude (in altri termini) che: n(k) · k! = r(r-1)...(r-k+1) = r!/(r-k)!, sicché: n(k) = r!/[(r-k)! · k!] = Bin(r, k), q.e.d.
 
 Teorema H.1: per ogni n intero > 0, risulta che: sum[d | n] µ(d) = Floor(1/n), ove µ(-) denota la mu di Möbius, Floor(-) la funzione che ad ogni x reale fa corrispondere la sua parte intera bassa (ossia il più grande intero <= x) e la somma a primo membro s\'intende estesa a tutti e soli i divisori interi positivi di n.
 
 Dim.: se n = 1, la tesi è banalmente soddisfatta, essendo: µ(1) = sum[d | 1] µ(d) = Floor(1/1) = 1. Assunto n > 1, si ponga dunque: n = prod[k=1...r] pka[k], ove r è in N0; p1, p2, ..., pr sono numeri primi (naturali) distinti ed a[k] è un intero positivo, per ogni k = 1, 2, ..., r.
 
 Allora, essendo S := {1, 2, ..., r}: sum[d | n] µ(d) = µ(1) + sum[k=1...r] sum[(i1, i2, ..., ik) -> Sk t.c. i1 < i2 < ... < ik] µ(pi1 · pi2 · ... · pik), pur di considerare che, per definizione, µ(d) è diverso da zero sse d = 1 oppure d non è divisibile per il quadrato di alcun numero primo.
 
 Di qui, ancora per definizione, si conclude che: sum[d | n] µ(d) = µ(1) + sum[k=1...r] sum[(i1, i2, ..., ik) -> Sk t.c. i1 < i2 < ... < ik] µ(pi1 · pi2 · ... · pik) = 1 + sum[k=1...r] sum[(i1, i2, ..., ik) -> Sk t.c. i1 < i2 < ... < ik] (-1)^k = [Per il lemma (H.1)] = 1 + sum[k=1...r] (-1)^k · Bin(r, k) = sum[k=0...r] (-1)^k · Bin(n, k) = [Dalla formula di Newton per lo sviluppo della potenza di un binomio] = (1-1)^r = 0 = Floor(1/n), dacché si è supposto n > 1. Di qui la tesi, q.e.d.
 
 Corollario H.1: per ogni n intero > 0, risulta che: µ(n) * u(n) = E(1/n), ove u(-) denota la funzione unità, definita ponendo u(n) := 1, per ogni n intero > 0; e \"*\" il prodotto convolutorio di Dirichlet per le funzioni aritmetiche.
 
 Dim.: è sufficiente osservare che, per ogni n intero > 0: µ(n) * u(n) := sum[d | n] µ(d) · u(n/d) := sum[d | n] µ(d) = E(1/n), in accordo al teorema (H.1), q.e.d.
 
 Veniamo così, e finalmente, al mirabile risultato enunciato da F.V.
 
 Formula d\'inversione di Möbius: siano f(-) e g(-) due qualsivoglia funzioni aritmetiche. Allora, per ogni n intero > 0: f(n) = sum[d | n, d > 0] g(d), sse: g(n) = f(n) * µ(n) := sum[d | n] f(d) · µ(n/d), ove \"*\" denota ancora la convoluzione di Dirichlet per le funzioni aritmetiche.
 
 Dim.: per ipotesi, comunque scelto un n intero > 0: f(n) = sum[d | n] g(d) = sum[d | n] g(d) · u(n/d) =: g(n) * u(n), ove u(-) rappresenta qui la cosiddetta funzione unitaria, di cui ho già sopra fornito una definizione.
 
 Del resto, per ogni n intero > 0: f(n) = g(n) * u(n) <==> [Poiché la mu di Möbius è una funzione invertibile rispetto al prodotto convolutorio di Dirichlet] <==> f(n) * µ(n) = [g(n) * u(n)] * µ(n) = [Considerando che il prodotto di Dirichlet è un\'operazione associativa e commutativa] = g(n) * [u(n) * µ(n)] = g(n) * [µ(n) * u(n)] = [Per il corollario (H.1)] = g(n) * Floor(1/n) = sum[d | n] g(d) · Floor(d/n) = g(n) · Floor(n/n) = g(n) · 1 = g(n), q.e.d.
 
 EDIT: il server dell\'SNS mi gioca brutti scherzi, ultimamente...
 
 
 \"[...] E sparve, ei dì nell\'ozio,
 chiuse in sì breve sponda,
 segno d\'immensa invidia
 e di pietà profonda,
 d\'inestinguibil odio
 e d\'indomato amor.\"
 
 Alessandro Manzoni, da Il cinque maggio [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 17-09-2004 07:30 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Siccome altrove Ossido mi ha fatto notare, e giustamente, che molte delle formule contenute nel messaggio precedente somigliano tanto - provo a citare testualmente - \"ai caratteri incisi sul disco di Festo o ai geroglifici dell\'isola di Pasqua\" (LOOOL!), beh... v\'inviterei - se mai dovessero non esservi chiari alcuni passaggi - a chiedere spiegazioni, anziché tacere! Son certo che qualcuno vi risponderà.
 
 Del resto, cosa avete da guadagnarci a starvene zitti e buoni aspettando che sia magari un altro a formulare la domanda che vi frulla per la testa da chissà quanti giorni e che proprio non trovate il coraggio di postare perché maybe l\'orco cattivo potrebbe divorarvi in un solo boccone, uh? Nulla, appunto... Pensate piuttosto a quel che avete da perdere! Ah, quasi dimenticavo... questo discorso si riferisce naturalmente a questa come ad ogni altra discussione del forum. E chiedo scusa ai boss se mi sono qui permesso d\'interpretare un ruolo che oggettivamente non mi compete. Saluti!
 
 
 \"Chi è maestro da cima a fondo prende sul serio solo le cose che riguardano i suoi allievi, persino se stesso.\" - F. W. Nietzsche, Al di là del bene e del male

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

Vabbé, ho capito... Dunque, perché non tutto sia perduto, vediamo un po\' di stuzzicarvi l\'appetito rivisitando, alla luce delle recenti scoperte, un problema discusso qui sul forum, seppur per altra via, quantomeno una mezza dozzina di volte...
 
 Teorema (di Gauss): utilizzando la formula d\'inversione di Möbius, dimostrare che, per ogni n intero > 0: n = sum[d | n] phi(n), ove phi(-) denota - al solito - la totiente di Eulero e la somma a secondo membro s\'intende estesa a tutti e soli i divisori naturali di n.
 
 
 \"Il vizio e la virtù non sono per l\'artista che la materia prima della propria arte.\" - Oscar Wilde [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 19-09-2004 18:21 ]